Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!hubcap!rjc
From: rjc@CS.UCLA.EDU (Robert Collins)
Newsgroups: comp.parallel
Subject: Re: SIMD (CM2) indirect addressing (was SIMD Extensions)
Message-ID: <5929@hubcap.clemson.edu>
Date: 6 Jul 89 13:27:25 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 34
Approved: parallel@hubcap.clemson.edu

In article <5918@hubcap.clemson.edu> aklietz@ncsa.uiuc.edu (Alan Klietz) writes:
>In article <5902@hubcap.clemson.edu> rjc@CS.UCLA.EDU (Robert Collins) writes:
>>Yes, your basic CM array reference takes a long time.  Everyone gets
>>bitten by this one :-).  It runs in time O(n), where n is the
>>**number of elements in your array**.  This is *bad* for big arrays.
>
>If "indirect addressing" means what I think it does -- each PE
>grabs a value from an arbitrary address in an arbitrary PE -- then
>there exists an algorithm in time O(k log n) to do the equivalent 
>operation by repeatedly using the send operator.
>
>Algorithm: [ deleted ]

On the CM2, you can do it a lot faster than Alan's algorithm, if you use
the "fast" arrays described in my article (from which the above quote is
extracted--the quote is about "slow" arrays).

The indirect addressing that I spoke of was an arbitrary index in an
array within the processor.  There are also send/get operations that
write to/read from an arbitrary index of such arrays on an arbitary
processor.  These operations will allow the sort of indirect addressing
that is described above (well, actually only to a close approximation--but
probably good enough for all practical purposes).

I do not know the algorithm used by the router microcode, but it will be
faster than the (deleted) algorithms (one would hope).  If you have
really nasty collision patterns, things can slow down considerably.  It
seems like I usually end up with nasty collision patterns :-).

Rob

-------------------------------------------------------------------------------
rjc@cs.ucla.edu	            C++/Paris on the CM2:  Object Oriented SIMD madness
-------------------------------------------------------------------------------