Don't Be Too Clever: Routing BMMC Permutations on the MasPar MP-2

The authors implemented and measured several methods to perform BMMC permutations on the MasPar MP-2. Each method is coded in C and MPL and uses only the global router to transfer data among processors. Implementation in MPL limits the amount of control the programmer has over the global router. The methods used were a naive method; the PE method, which adapts the block BMMC algorithm for parallel disk systems to treat processor elements as independent devices; and the cluster method, which adapts the block BMMC algorithm to treat clusters of processor elements as independent devices. The authors also implemented variations of the first two methods to compute virtual-processor numbers in Gray-code order. Our results indicate that for random BMMC permutations, the best method overall is the naive method with the Gray-code variation. The PE methods are almost as good, especially when each processor element has several items to route. For some permutations, however, the naive method perfo..