Investigation and Development of Task Pools for Dynamic Load Balancing in Irregular Applications

Project Details

• Funded by: DFG
  

Project Participants

• Project Manager: Prof. Dr. Thomas Rauber
  
• Project Staff: Dr. Ralf Hoffmann, PD Dr. Matthias Korch, Andreas Prell, M.Sc.
  

Project Description

Task pools are used for dynamic load balancing in irregular applications. Depending on their input, the applications start by creating a number of tasks during an initialization phase which are stored in the task pool. These tasks are executed by letting all participating processors remove and execute tasks from the task pool until all tasks have been processed. During its execution, a task can create new tasks. The visualization of the hierarchy of task creation leads to a directed acyclic graph, consisting of several trees. If one also considers additional dependences not resulting from the hierarchical relations, graphs are obtained that are considerably more complex. 

To achieve an efficient execution of task based algorithms, two different strategies can be pursued. The first possibility is optimizing the latency of the schedule of the task graph by applying heuristical methods. This approach has the advantage that it reduces the execution time towards the asymptotic optimum of the algorithm. But the heuristical selection of tasks can be expensive, because possibly many conditions have to be regarded and global information about the task graph may be required. In contrast to this, the second approach tries to minimize the time necessary to access the task pool. For that purpose, an arbitrary execution order of the tasks is allowed, and simple data structures are used that can be manipulated very quickly. Additionally, the data structures are organized such that waiting times and synchronization overhead is reduced. This second approach has the advantage that it leads to a lower overhead of the task pools. But it presumes that only executable tasks are inserted into the task pool and that the structure of the task graph leads to a good schedule on the given number of processors even for an arbitrary execution order of the tasks. 

The targets of the project are the search for new organization forms of task pools with lower overhead and better scalability, the use and implementation of efficient synchronization mechanisms, and the development of parallel data structures that enable detention-free access to shared data. 

The current project phase considers load balancing strategies for (heterogeneous) multicore systems in order to efficiently execute task-based applications on such platforms. Current processors like the Cell processor and future architectures present new challenges for the programmer. A sufficient number of parallel computatons needs to be available to utilize the large number of cores. Different cores may have a different computational power due to hardware optimizations for specific calculations. Also economic aspects play an important role in future systems. The clock frequency might be dynamically adjusted to save energy, to protect from overheating, or to temporarily provide more computational power. These dynamically changing parameters need to be taken into consideration for the programming model.