SHF: AF: Small: Locality with Dynamic Parallelism

随着最近具有许多并行核心的计算机占据主导地位，以及大型数据中心的广泛使用，为这些机器提供高级、简单和通用的并行代码开发方法的需求变得至关重要。要有效地开发这种并行代码有许多挑战，但可以肯定的是，一个主要的困难是处理通信成本——或者从另一个角度来看，利用局部性。不幸的是，这一挑战在具有多种局部性形式的现代并行机器上变得更加困难——网络延迟和带宽、共享和分布式缓存、分区内存以及各种组织中的辅助存储。为了解决这个问题，这个项目正在开发一种方法，让程序员在不需要知道他们正在使用的特定并行机器的任何细节的情况下了解并行代码的局部性。在这种方法中，程序员表达了他们的算法的完全动态并行性，而不描述它是如何映射到处理器上的，并给出了一个简单的高级模型来分析局部性。该研究基于这样一个猜想：局部性应该被程序员视为算法或代码的属性，而不是机器的属性。为了确保真实机器能够充分利用模型中分析的局部性，研究人员正在开发将“算法局部性”映射到各种形式的机器局部性的调度方法，包括共享缓存、分布式缓存、缓存树和分布式内存机。研究结果既包括在特定机器组织上这种调度器的理论界限，也包括在一组基准应用程序上的实验验证。

With the recent dominance of computers with many parallel cores, and the widespread use of large data centers, the need to supply high-level, simple and general approaches to developing parallel codes for these machines has become critical. There are many challenges to effectively developing such parallel codes, but certainly a principle difficulty is dealing with communication costs - or when looked at from the other side, taking advantage of locality. Unfortunately this challenge has only become more difficult on modern parallel machines that have many forms of locality - network latency and bandwidth, shared and distributed caches, partitioned memories, and secondary storage in a variety of organizations.To address this problem this project is developing an approach for programmers to understand locality in their parallel code without needing to know any details of the particular parallel machine they are using. In the approach programmers express the full dynamic parallelism of their algorithm without describing how it is mapped onto processors, and are given a simple high-level model for analyzing locality. The research is based on the conjecture that locality should be viewed by the programmer as a property of the algorithm or code and not the machine. To ensure that real machines can take proper advantage of the locality analyzed in the model, the research is developing scheduling approaches that map the "algorithm locality" onto various forms of machine locality, including shared caches, distributed caches, trees of caches, and distributed memory machines. The results of the research include both theoretical bounds for such schedulers on specific machine organizations, and experimental validation on a set of benchmark applications.