Conflict-Free Scheduling of Nested Loop Algorithms on Lower Dimensional Processor Arrays

TitleConflict-Free Scheduling of Nested Loop Algorithms on Lower Dimensional Processor Arrays
Publication TypeConference Paper
Year of Publication1992
AuthorsYang, Z, Shang, W, Fortes, JAB
Conference NameParallel Processing Symposium, 1992. Proceedings., Sixth International
Date Published03/1992
AbstractIn practice, it is interesting to map n-dimensional algorithms, or algorithms with n nested loops, onto (k-1)-dimensional arrays where k<n. The paper considers some open problems in a previous work by Shang and Fortes (1990). A procedure is proposed to test if or not a given mapping has computational conflicts and a lower bound on the total execution time is provided. Based on the testing procedure and the lower bound, the complexity and the optimality of the optimization procedure in the previous work is improved. The integer programming formulation is also discussed and used to find the optimal time mapping for the 5-dimensional bit level matrix multiplication algorithm into a 2-dimensional bit level processor array