SHF: Medium: Collaborative Research: Automatic Locality Management for Dynamically Scheduled Parallelism

动态调度并行的自动局部性管理当今的多核和多核计算机以并行处理的形式提供了越来越多的计算能力，同时具有多层层次结构的复杂内存组织，并且访问不同级别之间的成本相差数量级。当软件显示空间和时间局部性时，意味着它在相对较小的时间范围内读取和写入彼此接近的内存地址，它能够主要访问快速缓存中的数据，而不是在缓慢的主存储器中，并提供良好的顺序和并行性能。不幸的是，使用高级托管编程语言编写的软件很难确保或预测空间和时间局部性的数量，这是由于缺乏低级程序员控制，以及特定硬件平台与线程调度器和内存管理器之间的复杂性和相互作用。本项目探索在具有复杂内存层次结构的并行计算机上执行的高级管理编程语言的自动局部性管理技术。使用在项目中开发的理论模型、高效算法和实际实现，程序员能够独立于目标硬件推断其程序的预期位置，而运行时系统（包括线程调度器和内存管理器）将程序映射到特定的硬件以实现既定的性能界限。特别地，该项目解决了通过高级垃圾收集并行函数式编程语言的运行时系统自动管理局部性的问题。我们使用了一种综合的方法，同时考虑了调度、内存分配和内存回收，从而允许线程调度程序影响内存管理器，反之亦然。本研究计划的一个关键见解是将程序的分配数据视为任务和调度器映射堆的分层集合。这种观点指导了理论成本模型，该模型使程序员能够在高层次上推断局部性，控制何时创建和垃圾收集具有可证明边界的堆的有效算法，以及在并行函数式编程语言中提供自动局部性管理的实际实现。智力上的优点是在理解线程调度和内存管理与现代并行硬件上的局部性的相互作用方面取得了进展，开发了高级的、与机器无关的成本模型，并综合了编程语言、算法理论和系统设计来解决自动局部性管理的挑战。更广泛的影响是软件质量和程序员生产力的改进，在教育和研究中可用的并行功能编程语言的创建，以及将结果集成到课程和扩展活动中。

Automatic Locality Management for Dynamically Scheduled ParallelismToday's multicore and manycore computers provide increasing amounts of computational power in the form of parallel processing coupled with a complex memory organization with many levels of hierarchy and orders of magnitude difference in cost between accessing different levels. When software exhibits spatial and temporal locality, meaning that it reads and writes memory addresses that are close to one another in relatively small time span, it is able to primarily access data in fast caches, rather than in slow main memory, and deliver good sequential and parallel performance. Unfortunately, with software written in high-level managed programming languages it is difficult to ensure or to predict the amount of spatial and temporal locality, due to the lack of low-level programmer control and the complexities of and interactions between the specific hardware platform and the thread scheduler and the memory manager. This project explores techniques for automatic management of locality in high-level managed programming languages executing on parallel computers with sophisticated memory hierarchies. Using the theoretical models, efficient algorithms, and practical implementations being developed in the project, programmers are able to reason about the expected locality of their programs independent of the target hardware, while a runtime system, including thread scheduler and memory manager, maps the program onto specific hardware to achieve the established performance bounds.In particular, this project addresses the problem of automatically managing locality via the runtime system of a high-level garbage-collected parallel functional programming language. A comprehensive approach that considers scheduling, memory allocation, and memory reclamation together is used, allowing the thread scheduler to influence the memory manager and vice versa. A key insight of this research program is to view the allocated data of a program as a hierarchical collection of task- and scheduler-mapped heaps. This view guides the theoretical cost model that enables a programmer to reason about locality at a high-level, the efficient algorithms that control when to create and to garbage collect a heap with provable bounds, and the practical implementation that delivers automatic locality management in a parallel functional programming language. The intellectual merits are advances in understanding the interaction of thread scheduling and memory management with locality on modern parallel hardware, the development of high-level, machine-independent cost model, and a synthesis of programming languages, algorithmic theory, and system design to address the challenges of automatic locality management. The broader impacts are improvements in software quality and programmer productivity, the creation of a parallel functional programming language usable in both education and research, and the integration of results into courses and outreach activities.