LOWER TIME AND PROCESSOR BOUNDS FOR EFFICIENT MAPPING OF UNIFORM DEPENDENCE ALGORITHMS INTO SYSTOLIC ARRAYS
T. Andronikos, Nectarios Koziris, Z. Tsiatsoulis, G. Papakonstantinou, Panayiotis D. Tsanakas · International Journal of Parallel Emergent and Distributed Systems · 1997
One of the most promising areas of research is the area of automatic parallelization of sequential algorithms, where the primary objective is the execution of the algorithm in optimal parallel lime. For this purpose, methods of detecting and exploiting all inherent parallelism must be devised. Once optimal execution time is ensured, other prerequisites, e.g., the minimization of the number of processing elements (in the case of systolic arrays) or the minimization of the communication overhead (in the case of distributed memory architectures), should be accomplished too. In this paper we study the automatic parallelization of DO(FOR)-loops; we propose an algorithm that partitions the index space into distinct dependence chains and assigns them to different processing elements. We estimate that our method is always optimal in time and, for a specific subclass of nested DO(FOR)-loops, is also optimal in the number of systolic cells.