National Technical University of Athens (NTUA)
Δρομολόγηση φωλιασμένων βρόχων με τη χρήση μεθόδων υπολογιστικής γεωμετρίας
Abstract
dc:descriptionOne of the major problems in the area of parallel processing, is scheduling nested loops. This thesis studies the problem of scheduling nested loops with uniform dependencies, focusing onto the geometric properties of the index space and the dependence vectors of the problem. Initially, a new algorithm for mapping onto distributed memory architectures is presented. The followed technique is based on mapping onto systolic arrays. After the index space transformation is performed, the transformed index space needs to be partitioned and mapped to the given architecture. The partitioning is made along the directions of the transformed index space boundaries. This method achieves optimal load balancing between processors, although scheduling complexity is not optimal. After that, the geometric properties of the index space considered in the uniform nested loop problems are studied. The formal expressions that give the execution wavefront of any time instance are presented. Although they can only be solved by integer linear programming techniques, it is the first time they are computed in closed form. Some special cases are also noted. In these cases, certain inequalities between the algorithm dependence vectors hold and the complexity of computing the execution wavefront decreases dramatically: it can be computed in polynomial or even linear time. Based on the above geometric properties, a technique for scheduling any nested loop problem that follows the unit execution - zero communication time model - UET is presented. This scheduling method is nearly optimal. In addition to the above, we introduce a method of reducing problems that consider the unit execution - unit communication time model - UET-UCT to pure UET equivalent ones. This is one of the main contributions of our work, as it enables any scheduling technique of the bibliography for the UET cases, to apply to any problem that considers unit communication cost. During the scheduling algorithms presented in this thesis, a new method of computing the hyperplane vector Π is concerned. This method is explicitly based on the algorithm dependence vectors and on how these vectors allow the execution of the index space points. Actually, it is a revision of the convex hull computing method, called QuickHull. It should be noted that, in comparison with all other methods of the bibliography, it achieves quite a small complexity. Finally, the generalization of the above scheduling techniques for n-dimensional problems is presented. Certain simulation programs have been implemented, in order to testify the scheduling methods of this thesis. The proposed geometric method is compared with the hyperplane one, as well as with the exhaustive scheduling procedure, also called optimal. The comparison results are analytically presented.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2002
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Drositis, Ioannis
- Δροσίτης, Ιωάννης
Subjects
dc:subject × 15- Δρομολόγηση
- Φωλιασμένοι βρόχοι
- Κόστος επικοινωνίας
- Υπολογιστική γεωμετρία
- Κυρτό περίγραμμα
- Scheduling
- Nested loops
- Communication cost
- Computational geometry
- Convex hull
- UET - UCT
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/16725