Concurrent Scheduling of High-Level Parallel Programs on Multi-GPU Systems

Modern supercomputers are no longer just faster versions of the machines from a few decades ago; they are vast collections of thousands of specialized processors working together. To get the most out of these massive systems, scientists rely on software that can automatically decide which part of a calculation goes to which processor and how data moves between them. This is a difficult task because the software must manage memory and communication without slowing down the actual work. If the system spends too much time figuring out where to put data or how to keep it consistent, the powerful processors sit idle, wasting energy and time. The challenge is to make these decisions quickly enough that the computer never stops to think, keeping the flow of work as smooth as the flow of water in a river.

Researchers at the University of Innsbruck have developed a new way to handle this scheduling problem for systems equipped with many graphics processing units, or GPUs. These chips are designed to handle massive amounts of parallel work, but coordinating hundreds of them requires a sophisticated manager. The team introduced a method called instruction-graph scheduling, which acts as a detailed, low-level map of every single operation the computer needs to perform. Instead of making decisions on the fly as each step is needed, the system builds a complete plan that includes memory allocation, data transfers, and the actual calculations. This plan is generated while the computer is already working on previous tasks, effectively allowing the scheduler to look ahead and prepare the next steps without interrupting the current flow.

The core of this approach is a shift in how the software views the work. Previously, the system would generate a high-level list of tasks and then figure out the specific details, like memory copying, only when it was time to execute them. This often led to delays because the system had to stop and analyze dependencies in the middle of a calculation. The new method breaks every task down into its smallest components, such as allocating a specific block of memory or sending a small piece of data to a neighbor processor. By arranging these tiny steps into a single, interconnected graph, the system can see exactly which steps can happen at the same time. This allows the computer to overlap communication with calculation, meaning data can be moving between processors while the chips are busy crunching numbers, rather than waiting for one to finish before the other begins.

To test this idea, the researchers integrated their system into a software framework called Celerity, which is designed to run complex simulations on clusters of GPUs. They ran three different scientific applications to see how well the new scheduler performed compared to the standard version. One application simulated the gravitational pull between billions of particles, another modeled how sound bounces around a room, and the third tracked how waves move through a medium. In each case, they measured how much faster the program ran as they added more GPUs, a metric known as strong scaling. The results showed that the new approach consistently outperformed the baseline system, especially as the number of processors grew large. On a system with 128 GPUs, the new scheduler allowed the room-simulation application to run more than twice as fast as the old method, while the particle simulation saw a significant boost in speed as well.

A key innovation in this work is a technique called scheduler lookahead, which solves a specific problem related to memory usage. In many simulations, the amount of data a program needs to store can change from one step to the next. Without a way to predict these changes, the software might allocate a small block of memory, only to find it too small a moment later, forcing it to allocate a larger one and copy all the data over. This resizing process is slow and can waste valuable time. The new system looks ahead at the upcoming tasks to see if the memory requirements are growing. If it detects a pattern where the data size will increase, it waits to allocate the memory until it knows the final size needed, avoiding the costly resizing step entirely. This is particularly effective for applications where the data grows steadily, allowing the system to allocate the correct amount of memory in one go.

The researchers also built a system architecture that separates the work of planning from the work of doing. They created a dedicated thread, or a separate line of execution, that is responsible solely for building these detailed instruction graphs. Meanwhile, other threads handle the actual execution of the instructions on the GPUs. This separation ensures that the process of planning the next steps never gets in the way of the current steps being performed. The two processes run side by side, communicating through a streamlined queue that passes instructions from the planner to the executor. This design minimizes the time the system spends waiting, ensuring that the GPUs are kept busy with useful work rather than sitting idle while the software figures out what to do next.

The experiments were conducted on the Leonardo supercomputer in Italy, a machine with thousands of processors and high-speed connections. The team used real-world scientific codes to ensure their findings would hold up in practical scenarios. They found that while the new method did not change the fundamental limits of how much data could be stored or how large a problem could be, it significantly improved the efficiency of how that work was distributed. The improvements were most noticeable in applications where the data access patterns were complex or changing, as the system could better hide the time spent on communication and memory management. For applications with very short calculation steps, the new scheduler reduced the overhead enough to keep the system scaling efficiently even with a large number of processors.

This work demonstrates that the way software manages the internal logistics of a supercomputer is just as important as the raw power of the hardware itself. By moving the heavy lifting of scheduling out of the critical path and into a parallel process, the researchers have shown that it is possible to keep these massive machines running at peak efficiency. The instruction-graph approach provides a way to visualize and manage the complex web of dependencies that exist in modern parallel programs, turning what was once a bottleneck into a streamlined pipeline. As supercomputers continue to grow in size and complexity, techniques like this will be essential for ensuring that scientists can get the most out of their investments, allowing them to solve problems that were previously too large or too slow to tackle.