Hashing in Massively Parallel Computation

9408445 Abello The problem of supporting interprocessor communication in massively parallel computers raises two competing issues. To avoid bottlenecks in memory access, it may be necessary to perform hashing; i.e., to randomize the mapping of memory addresses to their physical locations. On the other hand, it is usually more efficient to access long contiguous blocks of memory than a random set of individual memory locations, and therefore it is desirable to preserve the physical locality of memory addresses. The study of the tradeoffs between these issues has only recently been initiated. However, several mathematical techniques have emerged as possible approaches for the extension of this research. This research plans to exploit these techniques to develop a robust theory of locality and randomness with applications to the complexity theory of parallel computation. ***