2007 | OriginalPaper | Chapter
Loop Parallelization in Multi-dimensional Cartesian Space
Authors : Saeed Parsa, Shahriar Lotfi
Published in: Perspectives of Systems Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Loop parallelization is of great importance to automatic translation of sequential into parallel code. We have applied Diophantine equations to compute the basic dependency vector sets covering all possible non-uniform dependencies between loop iterations. To partition the resultant dependencies space into multi-dimensional tiles of suitable shape and size, a new genetic algorithm is proposed in this article. Also, a new scheme based on multi-dimensional wave-fronts is developed to convert the multi-dimensional parallelepiped tiles into parallel loops. The problem of determining optimal tiles is NP-hard. Presenting a new constraint genetic algorithm in this paper the tiling problem is for the first time solved, in Cartesian spaces of any dimensionality.