Parallel Programming Strategies for Irregular Adaptive Applications
PARALLEL PROGRAMM ING STRATEGIES FORIRREGULAR ADAPTIVE APPLICATIONSR. BiswasNASA Ames Research CenterMoffett Field, CA 94035-1000rbiswas@nas.nasa.govAchieving scalable performance for dynamic irregular applications is eminently challenging [1].Traditional message-passing approaches have been making steady progress towards this goal;however, they suffer from complex implementation requirements. The use of a global addressspace greatly simplifies the programming task, but can degrade the performance for suchcomputations. In this work, we examine two typical irregular adaptive applications, DynamicRemeshing and N-Body, under competing programming methodologies and across variousparallel architectures [2]. The Dynamic Remeshing application simulates flow over an airfoil,and retmes localized regions of the underlying unstructured mesh. The N-Body e×per_mentmodels two neighboring Plummer galaxies that are about to undergo a merger. Both problemsdemonstrate dramatic changes in processor workloads and interprocessor communication withtime; thus, dynamic load balancing is a required component.We investigate several critical factors of the parallel code development, including performance,programmability, scalability, algorithmic features, and portability. We compare the most popularimplementation strategy, message passing with MPI, against a number of alternate approaches.First, we evaluate the effectiveness of using the SHMEM communication library, which usessymmetric address spaces for individual processes, allowing one-sided communication. Next, weexamine an implementation using the OMP programming strategy, which uses shared-memoryalgorithms and OpenMP-style compiler directives on systems supporting global addressing. Thecache-coherent shared address space (CC-SAS) paradigm is tested next. It is similar to OMP butfocuses on spatial locality through methods such as data remapping and replication, which aretraditionally not considered in shared-memory programming. Experimental results using hybridprogramming are then reported. Here, two layers of parallelism are combined by implementingOpenMP codes within shared-memory multiprocessors (SMPs), while using message passingbetween the SMP nodes. Finally, we present results on the Cray MTA that uses multithreading tohide latency, rather than using data caches.Experiments were performed on several parallel systems: the distributed-memory Cray T3E, thehardware-supported CC-NUMA SGI Origin2000, the latest generation of IBM POWER3 8-waySP cluster, and the Cray MTA multithreaded computer. Results indicate that it is possible toachieve message-passing performance using shared-memory programming techniques bycarefully following the same high-level strategies, and that multithreaded systems offertremendous potential but are not well suited for all classes of applications.References[1] L. Oliker and R. B iswas, "Parallelization of a Dynamic Unstructured Algorithm Using ThreeLeading Programming Paradigms," IEEE Transactions on Parallel and Distributed Systems,v. 11, p. 931-940, 2000.[2] H. Shah, J.P. Singh, L. Oliker, and R. Biswas, "'A Comparison of Three ProgrammingModels for Adaptive Applications on the Origin2000," CD_ROM Proceedings of SC2000Conference, Dallas, TX, 2000.