Optimal Scheduling of Parallel Tasks with Known Dependencies

Question

This is maybe a trivial question, but I am stuck with the problem.

Suppose we have a general graph:

$$G=(V,E)$$

Each edge represents a task, each vertex represents a data for the task (hence each task works with two vertices).

When two tasks with common vertex run in parallel, some computation time is lost because two tasks cannot use the same vertex at the same time (one have to wait).

I am thinking about the following approaches:

• Create a table of locks telling whether the vertex is free to use or locked. The run all tasks and each taks will wait until the required data are free (maybe setting priority of the waiting tasks to low would suffice).
• Pick maximum number of edges that have no common vertices (better way then greedy algorithm?) and then run all corresponding tasks without locking. Repeat until there are remaining edges.

I am not sure which approach is more efficient. Any ideas/insights? I am totally new to parallel programming...

Answer 1

I work on similar problems, i.e. task-based parallelism, and use something similar to your first approach. This is usually referred to as "dynamic scheduling" or "data-dependent execution" vs. "static scheduling", i.e. your second approach.

The efficiency of this approach is highly dependent on how you implement your locks, and what the threads do if a task cannot be computed. I use atomic compare-and-swap operations to implement the locks, and fast task queues to find tasks that have free locks.

It is also worthwhile for each thread to look for tasks that require resources (vertices) that it has previously owned, as this can improve caching behaviour.