Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!hubcap!aklietz
From: aklietz@ncsa.uiuc.edu (Alan Klietz)
Newsgroups: comp.parallel
Subject: Re: SIMD (CM2) indirect addressing (was SIMD Extensions)
Message-ID: <5918@hubcap.clemson.edu>
Date: 5 Jul 89 12:24:51 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 57
Approved: parallel@hubcap.clemson.edu

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:

Given a set of PEs { P(i) | 0 <= i < n }, we want each PE to
fetch a word from the PE at f(P(i)).   The inverse of f is undefined.

        Input:  f(i), 0 <= i < n, indirection function
                x(i), set of values to dereference
                T(i), temporary index array

        Output: { y | y(i) = f(x(i)) }

Without loss of generality, we assume i = P(i) and that there
exists a value called nil not in the domain or range of any function.

        for all i
                y(i) := nil, T(i) := nil
        repeat
                more := false
                for all f(i) | f(i) is not nil, do
                        T(f(i)) := i     // send-with-overwrite
                for all T(i) | T(i) is not nil, do
                        more := true
                        y(T(i)) := x(i)  // send
                        T(i) := nil
                for all y(i) | y(i) is not nil, do
                        f(i) := nil
        until more = false

Note that f(x(i)) never appears on the RHS of any assignment.

Assuming the forall statements are O(log n), the total time required
is O(k log n) where

        k = max( ||{{i,j} | f(i) = f(j)}|| ) + 1
            i,j

The best case is when f is invertible, where it is O(log n).
The worst case is when f is constant, where it is O (n log n).

--
Alan E. Klietz
University of Illinois at Urbana-Champaign
National Center for Supercomputing Applications
152 Computing Applications Building
605 E. Springfield Avenue
Champaign, IL  61820
Ph: +1 217 244 8024            ARPA:  aklietz@ncsa.uiuc.edu