B.Robic.
Optimization of parallel algorithm mappings onto regular processor arrays.
Ph.D. Thesis, University of Ljubljana, Slovenia, 1993, in Slovene.

The first chapter stresses the importance of mapping parallel algorithms onto parallel computer architectures. Some basic facts and concepts of data-driven computing are given in Chapter 2 while a regular data-driven processor array is introduced in Chapter 3. Chapter 4 describes a well-known procedure for mapping parallel algorithms onto these arrays. Chapter 5 shows that mapped algorithms generally exhibit serious drawbacks, such as slow execution while at the same time occupying a too large area. Reasons for these drawbacks are discovered by analyzing the mapping procedure. Moreover, NP-completeness is proved for several possible improvements of the mapping procedure. Hence, Chapter 6 deals with the possibility to improve algorithm mappings instead of the mapping procedure. A physical model is introduced to serve as a mental tool during the design of four heuristic optimization algorithms used to transform initial algorithm mappings. Several measures are introduced and, applied to experimental results, are used to evaluate the average improvements of initial algorithm mappings and the quality of heuristic algorithms.