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

SHF：中：协作研究：动态调度并行性的自动局部性管理

• 批准号: 1408981
• 负责人: Matthew Fluet
• 金额: $ 23.67万
• 依托单位: Rochester Institute of Tech
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-06-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1408981&HistoricalAwards=false
• 关键词: SHF; Medium; Collaborative; Research; Automatic

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.

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