walker@m.cs.uiuc.edu (William Walker) (11/26/90)
I have encountered the following problem in the course of programming a SIMD machine. Can anyone suggest an algorithm or a reference to an algorithm? Imagine a SIMD machine with N computation sites. Generate a random permutation of the integers 1 through N (inclusive) and place one value at each computation site. In other words, at the end of the computation each site should have a unique random value between 1 and N (inclusive). Assume a general router, but no shared memory. My present solution is to generate the permutation serially on the host computer and send it to the SIMD processor. Hence, even a communication-intensive distributed algorithm will probably be faster than the host-to-SIMD bottleneck. Please email responses to walker@cs.uiuc.edu. I will post a summary if anyone is interested. ------------------------------------------------------------------------------- Bill Walker walker@cs.uiuc.edu (217) 344-1312 Department of Computer Science, University of Illinois 1304 West Springfield Avenue, Urbana, Illinois 61801-2987 -------------------------------------------------------------------------------