Task Pool Teams: a hybrid programming environment for irregular algorithms on SMP clusters

摘要

Clusters of symmetric multiprocessors (SMPs) are popular platforms for parallel programming since they provide large computational power for a reasonable price. For irregular application programs with dynamically changing computation and data access behavior, a flexible programming model is needed to achieve efficiency. In this paper we propose Task Pool Teams as a hybrid parallel programming environment to realize irregular algorithms on clusters of SMPs. Task Pool Teams combine task pools on single cluster nodes by an explicit message passing layer. They offer load balance together with multi-threaded, asynchronous communication. Appropriate communication protocols and task pool implementations are provided and accessible by an easy-to-use application programmer interface. As application examples we present a branch and bound algorithm and the hierarchical radiosity algorithm.