Xref: utzoo comp.theory:1253 comp.parallel:1921
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!emory!hubcap!walker
From: walker@m.cs.uiuc.edu (William Walker)
Newsgroups: comp.theory,comp.parallel
Subject: parallel permutation
Message-ID: <11841@hubcap.clemson.edu>
Date: 26 Nov 90 14:12:42 GMT
Sender: fpst@hubcap.clemson.edu
Organization: University of Illinois at Urbana
Lines: 22
Approved: parallel@hubcap.clemson.edu

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
-------------------------------------------------------------------------------