Return to search

Task Pool Teams for Implementing Irregular Algorithms on Clusters of SMPs

The characteristics of irregular algorithms make a parallel implementation difficult, especially for PC clusters or clusters of SMPs. These characteristics may include an unpredictable access behavior to dynamically changing data structures or strong irregular coupling of computations. Problems are an unknown load distribution and expensive irregular communication patterns for data accesses and redistributions. Thus the parallel implementation of irregular algorithms on distributed memory machines and clusters requires a special organizational mechanism for a dynamic load balance while keeping the communication and administration overhead low. We propose task pool teams for implementing irregular algorithms on clusters of PCs or SMPs. A task pool team combines multithreaded programming using task pools on single nodes with explicit message passing between different nodes. The dynamic load balance mechanism of task pools is generalized to a dynamic load balance scheme for all distributed nodes. We have implemented and compared several versions for task pool teams. As application example, we use the hierarchical radiosity algorithm, which is based on dynamically growing quadtree data structures annotated by varying interaction lists expressing the irregular coupling between the quadtrees. Experiments are performed on a PC cluster and a cluster of SMPs.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:swb:ch1-200600537
Date06 April 2006
CreatorsHippold, Judith, Rünger, Gudula
ContributorsTU Chemnitz, SFB 393
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:preprint
Formattext/html, text/plain, image/png, image/gif, text/plain, image/gif, application/pdf, application/x-gzip, text/plain, application/zip
SourcePreprintreihe des Chemnitzer SFB 393, 02-18

Page generated in 0.0028 seconds