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

从我们口袋里的智能手机到数据中心的计算节点，多核处理器无处不在。多核处理器设备的速度和能源效率的关键是在计算机程序中找到足够的并行性，以保持尽可能多的多核活动。从历史上看，计算机和人类都不擅长为多核处理器找到足够的并行性。这使得许多核心闲置，使多核设备缓慢而低效。这个项目通过帮助计算机和人们提取以前未考虑到的并行性来解决这个问题，研究者和其他人已经证明存在并行性，但由于它跨越了整个程序的大部分而被隐藏起来。这个项目的新奇之处在于新的方法和工具来帮助计算机和人们从多核处理器程序中提取这种以前未被考虑到的并行性。该项目的影响是提高从智能手机到数据中心的所有多核设备的性能和能源效率。研究者和其他人先前的工作证明了在从循环中提取可扩展并行性时考虑循环关键路径的适用性和重要性。尽管循环关键路径方法取得了成功，但它错过了许多机会，其收益似乎已经停滞不前。问题是最优的循环局部决策常常忽略了考虑整个程序关键路径所揭示的机会。为了实现这些机会，该项目超越了循环级优化，将早期基于关键路径的方法中的经验教训应用于整个程序。这个项目的目标是通过利用跨循环调用和程序的非循环部分的并发性来实现更高程度的并行性。这个项目的任务包括分析来自动态数据依赖的信息，以公开整个程序的关键路径，使编译器和程序员都可以很容易地访问这些信息，并指导新的编译器转换，以创建更可伸缩和更有效的程序并行版本。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.