SHF: Small: The Whole Program Critical Path Approach to Parallelism

多核处理器无处不在，从我们口袋里的智能手机到数据中心的计算节点。 在具有多核处理器的设备中，提高速度和能效的关键是在计算机程序中找到足够的并行性，以保持尽可能多的多核处于活动状态。 从历史上看，计算机和人都不善于为多核处理器找到足够的并行性。 这使得许多内核处于空闲状态，使多核设备速度缓慢且效率低下。 这个项目通过帮助计算机和人们提取以前未考虑的并行性来解决这个问题，研究人员和其他人已经证明存在并行性，但由于它跨越整个程序的大部分而被隐藏。 该项目的新颖之处是新的方法和工具，帮助计算机和人们在多核处理器的程序中提取这种以前未被考虑的并行性。该项目的影响是提高了从智能手机到数据中心的所有多核设备的性能和能源效率。研究人员和其他人之前的工作证明了在从循环中提取可扩展并行性时考虑循环关键路径的适用性和重要性。 尽管循环关键路径方法取得了成功，但它错过了许多机会，而且它的收益似乎已经稳定下来。问题是，最佳的循环局部决策往往忽略机会，通过考虑整个程序的关键路径。为了实现这些机会，这个项目超越了循环级优化，通过应用在早期的关键路径为基础的方法，整个程序的经验教训。 该项目的目标是通过利用跨循环调用和程序的非循环部分的并发性来实现显着更高的并行度。 该项目的任务包括分析来自动态数据依赖的信息，以暴露整个程序的关键路径，使这些信息易于为编译器和程序员访问，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的评估来支持。影响审查标准。

Multicore processors are everywhere, from the smartphones in our pockets to compute nodes in data centers. The key to speed and energy efficiency in devices with multicore processors is in finding enough parallelism in computer programs to keep as many of the multiple cores active as possible. Historically, both computers and people have not been very good at finding enough parallelism for multicore processors. This leaves many cores idle, making multicore devices slow and inefficient. This project addresses this problem by helping computers and people extract previously unconsidered parallelism, parallelism that the investigator and others have shown to exist but is hidden because it spans large portions of the whole program. The project's novelties are new methods and tools to help computers and people extract this previously unconsidered parallelism in programs for multicore processors. The project's impacts are increased performance and energy efficiency for all multicore devices, from smartphones to data centers.Prior work by the investigator and others demonstrated the applicability and importance of considering the loop critical path in extracting scalable parallelism from loops. Despite the successes of the loop critical path approach, it misses many opportunities, and its gains seem to have plateaued. The problem is that optimal loop-local decisions often dismiss opportunities revealed by considering the whole program critical path. To realize these opportunities, this project goes beyond loop-level optimization by applying the lessons learned in earlier critical-path-based approaches to entire programs. This project's aim is a dramatically higher degree of parallelism realized by exploiting concurrency across loop invocations and through non-loop sections of programs. This project's tasks include analyzing information from dynamic data dependences to expose the whole program critical path, making this information readily accessible to both compilers and programmers, and guiding new compiler transformations to create even more scalable and efficient parallel versions of programs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.