# Presentation: 540316

## Parallelization of a Dynamic Unstructured Application using Three Leading Paradigms

_**Leonid Oliker**_
- NERSC
- Lawrence Berkeley National Laboratory
- www.nersc.gov/~oliker
_**Rupak Biswas**_
- MRJ Technology Solutions
- NASA Ames Research Center
- www.nas.nasa.gov/~rbiswas

## Motivation and Objectives

**Real-life computational simulations generally require irregular data structures and dynamic algorithms**
**Large-scale parallelism is needed to solve these problems within a reasonable time frame**
**Several parallel architectures with distinct programming methodologies have emerged**
**Report experience with the parallelization of a dynamic unstructured mesh adaptation code using three popular programming paradigms on three****state-of-the-art supercomputers **

## 2D Unstructured Mesh Adaptation

**2D Unstructured Mesh Adaptation**

**Powerful tool for efficiently solving computational problems with evolving physical features (shocks, vortices, shear layers, crack propagation)**
**Complicated logic and data structures**
**Difficult to parallelize efficiently**
**Irregular data access patterns (pointer chasing)**
**Workload grows/shrinks at runtime (dynamic load balancing)**
**Three types of element subdivision**

## Parallel Code Development

**Programming paradigms**
**Message passing (MPI)**
**Shared memory (OpenMP-style pragma compiler directives)**
**Multithreading (Tera compiler directives)**
**Architectures**
**Cray T3E          ****  SGI Origin2000          ****  Tera MTA**
**Critical factors**
**Runtime**
**Scalability**
**Programmability**
**Portability**
**Memory overhead**

## Test Problem

**Test Problem**

**Computational mesh to simulate flow over airfoil**
**Mesh geometrically refined 5 levels in specific regions to better capture fine-scale phenomena**

**14,605 vertices**
**28,404 triangles**

**   ****488,574 vertices**
**1,291,834 triangles**

_**Serial Code**_
**6.4 secs on 250 MHz R10K**

## Distributed-Memory Implementation

**512-node T3E (450 MHz DEC Alpha procs)**
**32-node Origin2000 (250 MHz dual MIPS R10K procs)**
**Code implemented in MPI within PLUM framework**
**Initial dual graph used for load balancing adapted meshes**
**Parallel repartitioning of adapted meshes (ParMeTiS)**
**Remapping algorithm assigns new partitions to processors**
**Efficient data movement scheme (predictive & asynchronous)**
**Three major steps (****refinement, repartitioning, remapping****)**
**Overhead**
**Programming (to maintain consistent D/S for shared objects)**
**Memory (mostly for bulk communication buffers)**

## Overview of PLUM

_**INITIALIZATION**_

**Initial Mesh**

**Partitioning**

**Mapping**

**Overview of PLUM**

**Y**

**Y**

**N**

**N**

**Repartitioning**

**Reassignment**

**Remapping**

**Balanced?**

**Expensive?**

_**LOAD BALANCER**_

_**FLOW SOLVER**_

## Performance of MPI Code

**More than 32 procs required to outperform serial case**
**Reasonable scalability for refinement & remapping**
**Scalable repartitioner would improve performance**
**Data volume different due to different word sizes**

## Shared-Memory Implementation

**32-node Origin2000 (250 MHz dual MIPS R10K procs)**
**Complexities of partitioning & remapping absent**
**Parallel dynamic loop scheduling for load balance**
**GRAPH_COLOR strategy (significant overhead)**
**Use SGI’s native pragma directives to create IRIX threads**
**Color triangles (new ones on the fly) to form independent sets**
**All threads process each set to completion, then synchronize**
**NO_COLOR strategy (too fine grained)**
**Use low-level locks instead of graph coloring**
**When thread processes triangle, lock its edges & vertices**
**Processors idle while waiting for blocked objects**

## Performance of Shared-Memory Code

**Performance of Shared-Memory Code**

**Poor performance due to flat memory assumption**
**System overloaded by false sharing**
**Page migration unable to remedy problem**
**Need to consider data locality and cache effects to improve performance (****require partitioning & reordering****)**
**For ****GRAPH_COLOR**
_**Cache misses**_**15 M (serial) to****85 M (P=1)**
_**TLB misses**_**7.3 M (serial) to****53 M (P=1)**

## Multithreaded Implementation

**8-processor 250 MHz Tera MTA**
**128 streams/proc, flat hashed memory, full-empty bit for sync **
**Executes pipelined instruction from different stream at each clock tick**
**Dynamically assigns triangles to threads**
**Implicit load balancing**
**Low-level synchronization variables ensure adjacent triangles do not update shared edges or vertices simultaneously**
**No partitioning, remapping, graph coloring required**
**Basically, the NO_COLOR strategy**
**Minimal programming to create multithreaded version**

## Performance of Multithreading Code

**Sufficient instruction level parallelism exists to tolerate memory access overhead and lightweight synchronization**
**Number of streams changed via compiler directive**

## Schematic of Different Paradigms

_**Shared memory**_

_**Multithreading**_

_**Distributed memory**_

**Before and after adaptation (P=2 for distributed memory)**

## Comparison and Conclusions

**Different programming paradigms require varying numbers of operations and overheads**
**Multithreaded systems offer tremendous potential for solving some of the most challenging real-life problems on parallel computers**