We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Automatic Mapping of System of N-Dimensional Affine Recurrence Equations (SARE) onto Distributed Memory Parallel Systems.
- Authors
Marongiu, Alessandro; Palazzari, Paolo
- Abstract
Automatic extraction of parallelism from algorithms, and the consequent parallel code generation, is a challenging problem. In this work, we present a procedure for automatic parallel code generation in the case of algorithms described through Set of Affine Recurrence Equations (SARE); starting from the original SARE description in an N-dimensional iteration space, the algorithm is converted into a parallel code for an (eventually virtual) m-dimensional distributed memory parallel machine (m < N). In the paper, we demonstrate some theorems which are the mathematical basis for the proposed parallel generation tool. The projection technique used in the tool is based on the polytope model. Some affine transformations are introduced to project the polytope from the original iteration space onto another polytope, preserving the SARE semantic, in the processor-time (t, p) space. Points in (t, p) are individuated through the m-dimensional p coordinate and the n-dimensional t coordinate, resulting in N = n + m. Along with polytope transformation, a methodology to generate the code within processors is given. Finally, a cost function, used to guide the heuristic search for the polytope transformation and derived from the actual implementation of the method on an MPP SIMD machine, is introduced.
- Subjects
MATHEMATICAL mappings; PARALLEL algorithms; ITERATIVE methods (Mathematics); PARALLEL computers; POLYTOPES; MICROPROCESSORS; HEURISTIC
- Publication
IEEE Transactions on Software Engineering, 2000, Vol 26, Issue 3, p262
- ISSN
0098-5589
- Publication type
Article
- DOI
10.1109/32.842951