blevins@mcnc.org (Donald W. Blevins) (02/09/89)
I would like to hear opinions on the use of feature that we have added to our own SIMD machine. As a background, it is based on the NASA MPP, but with some important new changes. The machine is a SIMD, 2D mesh (includes diagonals). Each PE is bit-serial, and has access to 1k bits of static ram locally. We have the capability to locally modify the SIMD global address, and thus generate an offset unique to each PE. We know of several applications that can use this feature, but we are unable to quantify the performance improvement. Do you know of an algorithm(s) that can make use of this feature, and what the performance improvement is over the same machine without this feature? Thanks. Don Blevins MCNC
halldors@paul.rutgers.edu (Magnus M Halldorsson) (02/10/89)
In article <4361@hubcap.UUCP> blevins@mcnc.org (Donald W. Blevins) writes: > I would like to hear opinions on the use of feature that we > have added to our own SIMD machine. ... > We have the capability to locally modify the SIMD global address, > and thus generate an offset unique to each PE. > > Do you know of an algorithm(s) that can make use of this feature, > and what the performance improvement is over the same machine > without this feature? I believe this can be a very useful feature. It allows each PE to work on data of a different format. A place where I originally ran into this possibility, was into performing local sorting, i.e. internal sort within the PE. Local sorting usually appears as the initial step in merge-splitting extension of parallel sorting algorithms (where N > p). Without independent addressing, one is restricted to contingent sorting methods (Odd-Even merge,Bitonic merge) with best case of n * log^2 (n) behaviour. With the feature, a heapsort would be possible, shaving off a log(n) factor. Given the 1K bit size of local memory, it is not certain that this would produce noticable improvements in this case. Another useful place, is in dealing with multiple objects of varying sizes. Magnus