Back to search

National Technical University of Athens (NTUA)

ΑΥΤΟΜΑΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΣΕΙΡΙΑΚΩΝ ΑΛΓΟΡΙΘΜΩΝ

Abstract

dc:description

THIS 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/8870

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ανδρόνικος, Θεόδωρος. ΑΥΤΟΜΑΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΣΕΙΡΙΑΚΩΝ ΑΛΓΟΡΙΘΜΩΝ. National Technical University of Athens (NTUA), 1997. http://hdl.handle.net/10442/hedi/8870