SHF: Small: Locality-Aware Concurrency Platforms

现代机器具有复杂的内存层次结构，由许多级别的“缓存”组成，必须有效地利用这些“缓存”来获得性能。如果一个程序的执行能够有效地利用底层缓存层次结构，那么它就具有良好的局部性或缓存效率。由于处理器的速度比内存访问延迟的增长速度更快，因此优化程序的局部性通常比最小化处理器上执行的指令数量更为重要。随着“多核”系统的流行，局部性优化变得更加关键，因为处理器上内核数量的增加会给每个内核可用的内存带宽和容量带来压力。然而，为现有的多核机器编写有效利用缓存层次结构的并行程序是一项挑战。本项目旨在开发一个并行编程平台，使程序员可以在并行机器上编程而不用担心局部性，并且该平台以高效缓存的方式转换和执行程序。在智力方面，这项研究将促进对调度算法、编译器转换和运行时自动化的理解。该项目更广泛的重要性在于，程序员将能够为多核系统编写可移植、高性能和缓存效率高的程序，同时与编写缓存效率高的代码的传统方法相比，大大减少了编程工作量。这个项目制作的平台将在万维网上免费提供，这可以实现高效的软件。编写高效缓存的并行程序具有挑战性，因为并行程序中的局部性是算法设计、调度和底层机器配置的函数，而这些因素通常是紧密耦合的。此外，在并行平台上，性能取决于负载平衡和缓存效率，而这两者通常是相互竞争的目标。为了设计一个位置感知的并行编程平台，该项目将采用一种集成的方法，将调度理论、算法设计、运行时系统支持和编译器转换结合起来。在调度理论领域，pi将系统地研究负载平衡和缓存效率之间的权衡，并设计为两者提供合理保证的调度器。由于缓存效率也取决于程序本身，因此pi将研究缓存效率算法的设计模式，并利用这一经验来研究一组程序转换，以将普通程序转换为可以以缓存效率方式执行的程序。这些见解将在一个由编译器和运行时系统组成的原型并发平台中实现，以便研究有效的机制，以支持以缓存高效的方式调度并行程序的可证明的良好策略。

Title: SHF: Small: Locality-Aware Concurrency PlatformsModern machines have complex memory hierarchies consisting of many levels of "cache" that must be utilized effectively to gain performance. A program is said to have good locality or cache efficiency if its execution can utilize the underlying cache memory hierarchy effectively. Since the speed of processors is growing faster than the memory access latency, it is often more important to optimize one's program for locality than to minimize the number of instructions executed on the processor. With the prevalence of "multicore" systems, optimizing for locality becomes even more critical, since increase in the number of cores on a processor puts pressure on both the memory bandwidth and capacity available for each core. Writing parallel programs that utilize the cache hierarchy effectively for existing multicore machines is challenging, however. This project aims to develop a parallel programming platform that enables the programmer to program a parallel machine without worrying about locality, and the platform transforms and executes the program in a cache-efficient way. In terms of intellectual merits, this research will advance the understanding of scheduling algorithms, compiler transformations, and runtime automation. The project's broader importance is that programmers will be able to write portable, high-performant and cache-efficient programs for multicore systems while significantly reducing the programming effort compared to the traditional approach in writing cache-efficient code. The platform produced by this project will be made freely available on the World Wide Web, which can enable highly-efficient software.Writing cache-efficient parallel programs is challenging, because locality in a parallel program is a function of algorithm design, scheduling, and underlying machine configuration, and these factors are often tightly coupled. In addition, on parallel platforms, the performance depends on both load-balancing and cache efficiency, and these are often competing objectives. To design a locality-aware parallel programming platform, the project will take an integrated approach that combines efforts in scheduling theory, algorithmic design, runtime system support, and compiler transformations. In the realm of scheduling theory, the PIs will systematically study the trade-offs between load-balancing and cache efficiency, and design schedulers that provide sensible guarantees for both. Since cache-efficiency also depends on the program itself, the PIs will study the design patterns of cache-efficient algorithms and draw on this experience to investigate a set of program transformations to convert an ordinary program into one that can be executed in a cache efficient manner. These insights will be implemented in a prototype concurrency platform consisting of a compiler and a runtime system in order to study efficient mechanisms to support provably good policies developed for scheduling parallel programs in a cache-efficient manner.