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.