Parallel Scheduling of Task Graphs with Minimal Memory Requirements

Many computing systems are constrained by the amount of available shared memory they are allowed to use. Modeling an application with a task graph makes it possible to analyze and optimize its memory usage. We therefore address the problem of finding a parallel schedule of a given task graph that minimizes its memory peak (the maximum memory usage at any point), which is an NP-complete problem. We start by reusing a previous technique that is able to find the optimal sequential schedule for a large class of task graphs, optimal in the sense that the memory peak is the smallest possible one. From this optimal sequential schedule, a dynamic parallel schedule can be derived with a list scheduling algorithm, which we adapt to take into account memory requirements. Provided that the memory constraint is equal to the memory peak of the sequential schedule, our approach always succeeds in producing a parallel schedule that meets the given memory constraint, and that enjoys relatively good speedup (2.68 on average for 4 processors). When the memory constraint is less harsh, the resulting speedup is significantly more substantial (3.57 on average for 4 processors). We compare with the previous state of the art on multiple applications expressed as task graphs, scientific workflows and signal processing filters. When the given memory constraint is close to the minimum, our approach always succeeds in finding a parallel schedule meeting this constraint, whereas the other approaches mostly fail. When the given memory constraint is significantly higher, our approach is comparable to others in terms of speedup, but much faster and it can deal successfully with very large task graphs (up to 50,000 nodes) using a naive Python implementation.