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.

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