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.