Abstract:
Graph Traverse Scheduling, GTS [ALTB89], was developed as a technique suitable for parallelizing DO loops with cycles on their dependence graph, but actually, GTS is a generalization of many loop restructuring techniques. The improvements achieved with its application in front of other techniques are the reduction of synchronizations, the introduction of scalar optimizations and the better use of the memory hierarchy. The purpose of this work has been the implementation of this new technique for a particular existing shared-memory multiprocessor and its integration on a source-to-source restructuring compiler. We studied the limitations imposed by the architecture to the technique and modified it in order to adapt the generated parallel code to the architecture. Finally, we measured the improvements of the new scheduling comparing the execution time of some example loops obtained by the commercial parallelizer with the execution time obtained by GTS. © Springer-Verlag Berlin Heidelberg 1994.
Registro:
Documento: |
Artículo
|
Título: | Implementation of GTS |
Autor: | Barrado, C.; Labarta, J.; Borensztejn, P.; Maritsas D.; Theodoridis S.; Halatsis C.; Philokyprou G.; Commision of the European Union; et al.; General Secretariat of Research and Technology; Greek Ministry of Cultural Affairs; Intracom; Ministry of Education |
Filiación: | Departamento de Arquitectura de Computadores, UPC, Barcelona, Spain Facultad de Ciencias Exactas y Naturales, Buenos Aires, Argentina
|
Palabras clave: | Memory architecture; Scheduling; Dependence graphs; ITS applications; Memory hierarchy; Parallel code; Re-structuring techniques; Restructuring compilers; Scalar optimization; Shared memory multiprocessor; Parallel architectures |
Año: | 1994
|
Volumen: | 817 LNCS
|
Página de inicio: | 555
|
Página de fin: | 576
|
Título revista: | 6th International Conference on Parallel Architectures and Languages Europe, PARLE 1994
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v817LNCS_n_p555_Barrado |
Referencias:
- Aho, A., Sheti, R., Ullman, J., (1986) Principles of Compiler Design, , Reading, MA: Addison-Wesley
- (1985) Fx/Series Architecture Manual, , Alliant Computer Systems Corp
- (1988) Product Summary, , Alliant Computer Corporation, Dec
- Ayguadé, E., Labarta, J., Torres, J., Borensztejn, P., GTS: Parallelization and Vectorization of Tight Recurrences (1989) Proc. Of the Supercomputing'89, pp. 531-539
- Ayguadé, E., Labarta, J., Torres, J., Llaberia, J.M., Valero, M., (1991) ”Parallelism Evaluation and Partitioning of Nested Loops for Shared Memory Multiprocessors”, , chap. 11 of Advances in Languages and Compilers for Parallel Processing, PITMAN
- Borensztejn, P., Labarta, J., Barrado, C., Measures of Parallelism at Compile Time (1993) Euromicro Workshop on Parallel and Distributed Processing
- Callaghan, D., Cocke, J., Kennedy, K., Estimating Interlock and Improving Balance for pipelined arquitectures (1987) Proc. Of the International Conference on Parallel Processing, pp. 295-304
- Cytron, R., DOACROSS: Beyong Vectorization for Multiprocessors (1986) Proc. Of the International Conference on Parallel Procesing, pp. 836-844
- Midkiff, S., (1986) Automatic Generation of Synchronization Instructions for Parallel Processors, , MS. Thesis, CSRD No. 588, Center of Supercomputing Research and Development, University of Illinois, IL, May
- Midkiff, S., Padua, D., Compiler Algorithms for Synchronization (1987) IEEE Transactions on Computers, Vol C-36, 12, pp. 1485-1495. , Dec
- Padua, D., Wolfe, M., Advanced Compiler Optimizations for Supercomputers (1986) Communications of the ACM, 29 (12), pp. 1184-1201. , December
- Pointer, L., (1989) Perfect Report: 1, , CSRD No. 896, Center of Supercomputing Research and Development, University of Illinois, IL, July
- Polychronopoulos, C., Kuck, D., Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel Supercomputres (1987) IEEE Transactions on Computers, C-36 (12). , December
- Polychronopoulos, C., Parafrase-2: An Environment for Parallelizing, Partitioning, Synchronizing and Scheduling of Programs on Multiprocessors (1989) Proc of the International Conference on Parallel Processing, 2, pp. 39-48A4 - Commision of the European Union; et al.; General Secretariat of Research and Technology; Greek Ministry of Cultural Affairs; Intracom; Ministry of Education
Citas:
---------- APA ----------
Barrado, C., Labarta, J., Borensztejn, P., Maritsas D., Theodoridis S., Halatsis C., Philokyprou G.,..., Commision of the European Union; et al.; General Secretariat of Research and Technology; Greek Ministry of Cultural Affairs; Intracom; Ministry of Education
(1994)
. Implementation of GTS. 6th International Conference on Parallel Architectures and Languages Europe, PARLE 1994 , 817 LNCS, 555-576.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v817LNCS_n_p555_Barrado [ ]
---------- CHICAGO ----------
Barrado, C., Labarta, J., Borensztejn, P., Maritsas D., Theodoridis S., Halatsis C., et al.
"Implementation of GTS"
. 6th International Conference on Parallel Architectures and Languages Europe, PARLE 1994 817 LNCS
(1994) : 555-576.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v817LNCS_n_p555_Barrado [ ]
---------- MLA ----------
Barrado, C., Labarta, J., Borensztejn, P., Maritsas D., Theodoridis S., Halatsis C., et al.
"Implementation of GTS"
. 6th International Conference on Parallel Architectures and Languages Europe, PARLE 1994 , vol. 817 LNCS, 1994, pp. 555-576.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v817LNCS_n_p555_Barrado [ ]
---------- VANCOUVER ----------
Barrado, C., Labarta, J., Borensztejn, P., Maritsas D., Theodoridis S., Halatsis C., et al. Implementation of GTS. Lect. Notes Comput. Sci. 1994;817 LNCS:555-576.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v817LNCS_n_p555_Barrado [ ]