National Technical University of Athens (NTUA)
ΑΥΤΟΜΑΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΣΕΙΡΙΑΚΩΝ ΑΛΓΟΡΙΘΜΩΝ
Abstract
dc:descriptionTHIS DISSERTATION STUDIES THE PROBLEM OF OPTIMAL PARALLELIZATION OF NESTED FOR(DO) LOOPS WITH UNIFORM DEPENDENCIES. AN OPTIMAL PARALLELIZATION IS A SCHEDULE THAT ACHIEVES THE MINIMUM PARALLEL EXECUTION TIME WHILE USING THE MINIMUM NUMBER OF PROCESSORS. UPPER AND LOWER BOUNDS ON THE NUMBER OF PROCESSORS NECESSARY TO ACCOMPLISH THE OPTIMAL PARALLEL TIME ARE PROVED. A GENERAL METHODOLOGYTHAT MAPS ALGORITHMS OF THIS CLASS INTO SYSTOLIC ARRAYS AND ACHIEVES THE ABOVEBOUDS IS PROPOSED. PARTICULAR EMPHASIS IS GIVEN TO LINEAR SCHEDULES. THE EXISTING ALGORITHMS FOR CALCULATING THE OPTIMAL LINEAR SCHEDULE WERE EXPONENTIAL IN THE NUMBER OF DEPENDENCE VECTORS AND THE DIMENSION OF THE INDEX SPACE. FOR 2 - DIMENSIONAL AND 3 - DIMENSIONAL INDEX SPACES, ALGORITHMS WITH POLYNOMIAL TIME COMPLEXITY IN THE NUMBER OF DEPENDENCE VECTORS ARE PROPOSED. THESE ALGORITHMS ACTUALLY SOLVE THE OPTIMAL LINEAR SCHEDULE PROBLEM FOR FAMILIES OF ALGORITHMS. GRIDS ARE A SPECIAL CASE OF NESTED FRO (DO) LOOPS WITH UNIFORM DEPENDENCIES. FOR A GENERALIZED FORM OF GRIDS, THE PROBLEM OF FINDING AN OPTIMAL SCHEDULE, ASSUMING NO COMMUNICATION COST (UET CASE) OR ASSUMING UNIT COMMUNICATION COST (UET - UCT CASE) WAS SOLVED AND AN EFFICIENT ALGORITHM THAT PRODUCES THE OPTIMAL SCHEDULE WAS PROPOSED.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 1997
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ανδρόνικος, Θεόδωρος
Subjects
dc:subject × 19- ΒΕΛΤΙΣΤΟΣ ΠΑΡΑΛΛΗΛΟΣ ΧΡΟΝΟΣ
- ΒΕΛΤΙΣΤΟΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ
- ΕΛΑΧΙΣΤΟΣ ΑΡΙΘΜΟΣ ΕΠΕΞΕΡΓΑΣΤΩΝ
- ΕΛΑΧΙΣΤΟΣ ΠΑΡΑΛΛΗΛΟΣ ΧΡΟΝΟΣ
- ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΙ ΑΛΓΟΡΙΘΜΩΝ
- ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΦΩΛΙΑΣΜΕΝΩΝ FOR (DO) ΒΡΟΓΧΩΝ
- Πλέγματα
- Συστολικές διατάξεις
- ALGORITHM TRANSFORMATION
- Grids
- MINIMUM NUMBER OF PROCESSORS
- NESTED FOR (DO) LOOPS PARALLELIZATION
- OPTIMAL PARALLEL TIME
- OPTIMAL SCHEDULE
- Systolic arrays
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/8870