Adaptive runtime management of spatial and temporal heterogeneity of dynamic SAMR applications

Structured adaptive mesh refinement (SAMR) techniques provide an effective means for dynamically concentrating computational effort and resources to appropriate regions in the application domain and have the potential for enabling highly accurate solutions to simulations of complex systems. However, due to the dynamism and space-time heterogeneity exhibited by these techniques, their scalable parallel implementation continues to present significant challenges.; This thesis aims at designing and evaluating an adaptive runtime management system for parallel SAMR applications by explicitly considering their spatial and temporal heterogeneity on large systems. The key idea is to identify relatively homogenous regions in the computational domain at runtime and apply the most appropriate algorithms that address local requirements of these regions. A hybrid space-time runtime management strategy based on this idea has been developed, which consists of three components. First, adaptive hierarchical strategies dynamically apply multiple partitioners to different regions of the application domain, in a hierarchical manner, to match the local requirements. Novel clustering and partitioning algorithms are developed. The strategy allows incremental repartitioning and rescheduling and concurrent operations. The second component is an application-level pipelining strategy, which trades space for time when resources are sufficiently large and under-utilized. The third component is an application-level out-of-core strategy, which trades time for space when resources are scarce in order to improve the performance and enhance the survivability of applications.; The proposed solutions have been implemented and experimentally evaluated on large-scale systems including the IBM SP4 cluster at San Diego Supercomputer Center with up to 1280 processors. These experiments demonstrate the performance benefits of the developed strategies. Finally, the GridMate simulator is developed to investigate applicability of theses strategies in Grid environments.