Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!wuarchive!emory!hubcap!fpst
From: bjornl@sics.se (Bj|rn Lisper)
Newsgroups: comp.parallel
Subject: Re: Mapping DO Loops onto Hypercubes
Message-ID: <1991May23.180156.9201@hubcap.clemson.edu>
Date: 23 May 91 15:51:26 GMT
References: <1991May20.124350.27749@hubcap.clemson.edu>
Sender: news@sics.se
Organization: Swedish Institute of Computer Science, Kista
Lines: 24
Approved: parallel@hubcap.clemson.edu
In-Reply-To: ouyang@TINMAN.CS.NYU.EDU's message of 18 May 91 20: 35:40 GMT
Apparently-To: comp-parallel@sunic.sunet.se

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