Hashing in Massively Parallel Computation

9408445阿贝罗在大规模并行计算机中支持处理器间通信的问题提出了两个相互竞争的问题。为了避免存储器访问中的瓶颈，可能需要执行散列；即，使存储器地址到其物理位置的映射随机化。另一方面，访问长的连续内存块通常比随机设置单个内存位置更有效，因此希望保留内存地址的物理局部性。对这些问题之间权衡取舍的研究直到最近才开始。然而，已经出现了几种数学方法，作为扩展这项研究的可能方法。这项研究计划利用这些技术来开发一个稳健的局部性和随机性理论，并将其应用于并行计算的复杂性理论。***

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