A Locality-Conscious Load-Balancing Based on Negotiations in Dynamic Unstructured Mesh Computations

摘要

We propose an open-architecture multi-agent load-balancing capability that currently makes use of a leading geometric mesh partitioning engine (Chaco) at runtime. At runtime, mesh solver application may initially create hundreds of light-weight threads, each handling a small submesh by calling Chaco partitioning engine in a preprocessing stage. The multi-agent is a set of SMP-based load balancers (agents) that run on the same multiprocessor but do not share any data structure with the parallel application solver threads. These agents monitor and collect system and solver data frequently from the multi-threaded parallel application solver. The proposed load-balancer controls dynamic changes in mesh sizes (adaptive unstructured mesh) by dividing out grown threads into smaller sub-domains served by smaller lightweight threads through further calls to the Chaco library. These calls deal only with sub-domains of much smaller mesh sizes than the complete application mesh. This divide-and-conquer process is deemed necessary when a sub-domain (submesh) served by a solver thread grows out beyond certain threshold limits and thus creates an imbalance. The multi-agents use information extracted at runtime to continuously monitor and adjust the workload imbalance of the application's light-weight threads through negotiations. Through negotiation among each other, agents incrementally develop plans to migrate application threads around the SMPs or for an application thread to call the partitioning library and spawn a number of application threads, each having a smaller mesh partition- the divide-and-conquer step. Migrating threads along with their local data maintains locality. Monitored system data include: processor idle time, memory usage, remote memory accesses, communication cost, and other load information.