Search for a command to run...
The scheduling of applications represented as task graphs has been extensively studied in the literature, where the goal is often to minimize the total execution time. When accounting for the memory needs of tasks, many algorithms that strive to minimize the peak memory have been proposed, so that the execution can fit on a processor with limited memory. However, minimizing the peak memory may lead to a high memory consumption on average, which would deteriorate the performance when several such applications must be executed in parallel. In this case, one would hence rather minimize the average memory consumption over time for each application, since peak usage is likely not to happen at the same time for all applications. In this work, we formalize the problem of minimizing the average memory consumption of a task graph, with two different models, and we present optimal algorithms for some particular task graphs (k-chains, pumpkins). Building on these algorithms, we design heuristics for general graphs. We evaluate them through simulations, using both synthetic task graphs and task graphs coming from real applications, such as QR eliminations. The results show that the heuristics often return solutions close to the optimal for a single task-graph application, and achieve in addition reasonably small peak memory usage. In a parallel setting, as we anticipated, minimizing the average memory of each application turns out to be more efficient than using a classical algorithm that focuses on minimizing the peak memory, hence demonstrating the usefulness of average memory consumption optimization.