Problem decomposition plays a central role in the design of parallel applications. It determines how the problem is to be divided into (sub)tasks, which can be executed in parallel. Basically, problem decomposition can be carried out statically (i.e. tasks are identified and defined prior to program execution) or in a dynamic manner, where tasks are generated (on demand) at runtime. In the latter case, tasks are explicit objects within the parallel program, which can be dynamically assigned to idle processors for execution. For ISPs a static approach to decomposition can result in significant processor idling, since a task’s computational complexity typically can not be derived from program input. Thus, dynamic problem decomposition becomes mandatory.

Dynamic problem decomposition requires explicit load balancing, i.e. tasks have to be assigned to processors at runtime. The task pool model implemented in Cohesion decouples problem decomposition and load balancing by a data structure holding tasks that result from dynamic decomposition operations. It can either be organized in a centralized or in a distributed manner. In a centralized approach, a master node maintains a global task pool from which idle processors can fetch new tasks. To be able to serve task requests in a timely fashion, the master prompts active nodes to perform problem decomposition, whenever the size of the task pool falls below a given threshold. A drawback of this approach is, that the cost of maintaining an accurate view of all nodes’ state becomes a sequential bottleneck for large numbers of nodes. Furthermore, tasks resulting from decomposition operations must first be transferred to the master node before they can be assigned to a worker. Together, these shortcomings can seriously limit the overall efficiency. Thus Cohesion implements the distributed task pool model, where a task pool is located on every node: decomposition and load balancing are accomplished autonomously by each node. Because there is no global knowledge, distributed load balancing tends to be more scalable but less efficient than centralized approaches. However, since tasks resulting from local decomposition operations are transferred directly between nodes (and are not relayed by a master node), losses in efficiency are at least partially leveled out.