ouyang@TINMAN.CS.NYU.EDU (Pei OuYang) (05/19/91)
I am interested in mapping Fortran nested DO loops onto hypercube computers,
where a nested DO loop can be modeled by an iteration space and a set of
dependence vectors.
I have seen articles on mapping meshes and trees onto hypercubes, mapping
DO loops onto systolic arrays, but cannot find articles addressing the
problem above. Is there any difficulty in solving this problem or is it
impractical?
Could someone tell me related papers and/or comment on this problem?
Thank you in advance for your help.
=========================================================
Pei Ouyang Department of Computer Science
ouyang@cs.nyu.edu New York University
(212)998-3083 251 Mercer Street
New York, N.Y. 10012
=========================================================news@UCSD.EDU (Kevin Sanders) (05/22/91)
In article <1991May20.124350.27749@hubcap.clemson.edu> ouyang@TINMAN.CS.NYU.EDU (Pei OuYang) writes: > >I am interested in mapping Fortran nested DO loops onto hypercube computers, >where a nested DO loop can be modeled by an iteration space and a set of >dependence vectors. .... A reasonable book on this subject is "Dependence Analysis for Supercomputing", by Utpal Banerjee, available from Kluwer Academic publishers (1988). The book demonstrates a method for determining dependence, limited to DO loops and assignment statements. It utilizes an integer programming technique to determine dependencies; this technique is restricted to DO loops whose indices are used in _linear_ functions only. | || | Kevin Sanders |_||_| NCR/Teradata JDO /\V/\V/\ (619) 597-3602 /_//_/\_\\_\ kevin.sanders@sandiego.ncr.com
bjornl@sics.se (Bj|rn Lisper) (05/23/91)
In article <1991May20.124350.27749@hubcap.clemson.edu> ouyang@TINMAN.CS.NYU.EDU (Pei OuYang) writes: >I am interested in mapping Fortran nested DO loops onto hypercube computers, >where a nested DO loop can be modeled by an iteration space and a set of >dependence vectors. >I have seen articles on mapping meshes and trees onto hypercubes, mapping >DO loops onto systolic arrays, but cannot find articles addressing the >problem above. Is there any difficulty in solving this problem or is it >impractical? The dimension of the iteration space is the number of nested loops: thus, iterations are most conveniently mapped to a space-time of the same dimension, which implies that the processor grid has this dimension minus one. I think you're best off by first mapping to the grid of natural dimension and then embedding that grid into the hypercube, for instance by binary-reflected Gray codes. Do you aim at fine-grain SIMD hypercubes (i.e. CM) or mesage-based MIMD hypercubes (Intel, NCUBE)? A fine-grain cube should be fine executing embedded systolic algorithms right off. A message-based MIMD cube would probably suffer from the fine granularity of systolic algorithms: thus, some kind of clustering becomes necessary. Bjorn Lisper