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.