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

Princeton University, Princeton NJ

Investigators

Abstract

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.