# Presentation: 043330

## Towards High-Level Programming Models for Petaflops Architectures  Hans P. Zima

*Institute for Software Science, University of Vienna, Austria   *
- and
*Jet Propulsion Laboratory, California Institute of Technology,*
*   **Pasadena, California, USA    *
- zima@jpl.nasa.gov
**Workshop on Petaflops Programming**
**SC2003, Phoenix, Arizona, November 18, 2003**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Programming models bridge the gap between “reality” and the underlying system  

Key Issue: Level of Abstraction                                    
     Abstraction implies loss of information:
         –  gain in simplicity, productivity, verifiability, portability
         -- potential degradation of performance    

For sequential machines, the evolution of programming models and languages has consistently led to higher levels of abstraction.                           For parallel architectures, the opposite is true.

**Key Issue: ****Level of Abstraction*****                                    ***
***     ******Abstraction implies loss of information:***
**         ****–  *****gain in*** ***simplicity, productivity, verifiability, portability***
***         ******-- ******potential degradation of performance******    ***
**For sequential machines, the evolution of programming models and languages has consistently led to higher levels of abstraction.                           *****For parallel architectures, the opposite is true.***

**Programming Models**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Exploiting performance on current HEC architectures requires low-level control and “heroic” programmers

This has led to fragmented programming models as exemplified by MPI-based programming
explicit processors: local views of data
program state associated with memory regions
explicit communication intertwined with the algorithm

Higher-level paradigms, such as HPF, have not been broadly accepted–mainly due to performance problems

**This has led to ****fragmented programming models ****as exemplified by MPI-based programming**
***explicit processors: local views of data***
***program state associated with memory regions***
***explicit communication intertwined with the algorithm***
**Higher-level paradigms, such as HPF, have not been broadly accepted–mainly due to performance problems**

**Today’s HEC Programming Model is Low Level**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## The HPF IdeaAn Almost Trivial Example(Jacobi) 

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Parallel Jacobi with MPI

**do while *****(*****.not. *****converged)***
**     ****do  *****J=1,M***
**          ****do  *****I=1,N***** **
**                *****B(I,J) = 0.25 * (A(I-1,J)+A(I+1,J)+***
***                                          ******A(I,J-1)+A(I,J+1))***** **
**          ****end do **
**      ****end do**
***     ******A(1:N,1:N) = B(1:N,1:N) ***
***    ***

**local**
**computation**

**initialize MPI ****             *****    ***

**if *****(MOD(myrank,2) *****.eq. *****1) *****then call MPI_SEND*****(B(1,1),N,...,myrank-1,..)***
**                                                ****call MPI_RCV*****(A(1,0),N,...,myrank-1,..)***** **
**                 ****if *****(myrank *****.lt. *****s-1) *****then **
**                                                       ****call MPI_SEND*****(B(1,M),N,...,myrank+1,..)***
**                                                         ****call MPI_RCV*****(A(1,M+1),N,...,myrank+1,..)***
**endif            **
**  ****else  ...                     **
**...                                      **

- Assuming block column distribution:

- ...

## Parallel Jacobi with HPF

**do while *****(*****.not. *****converged)***
**     ****do  *****J=1,N***
**          ****do  *****I=1,N***** **
**                *****B(I,J) = 0.25 * (A(I-1,J)+A(I+1,J)+***
***                                          ******A(I,J-1)+A(I,J+1))***** **
**          ****end do **
**      ****end do**
***     ******A(1:N,1:N) = B(1:N,1:N) ***
***    ***

**global**
**computation**

** ****processors  *****P(NUMBER_OF_PROCESSORS)***
** ****distribute(*,BLOCK) onto *****P :: A, B***

**Communication is automatically generated by the compiler**
**A change of distribution requires modification of just one **
** ****line in the source program; no change of the algorithm**

## Observations

**The HPF code is far simpler than the MPI code**
**Compiler-generated object code as good as MPI code**
***parallelization of the loop ***
***static analysis of access patterns and communication***
***aggregation  and fusion of communication***
**The data distribution directives can (in this case) be generated automatically from the sequential code**

***So why did HPF-1 fail?***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## HPF Problems

**HPF lacks important functionality**
***data distributions do not support advanced algorithms adequately (HPF-1)***
***lack of flexibility for processor-mapping and data/thread affinity (HPF-1)***
***focus on support for array types and SPMD data parallelism***
**HPF includes features that are difficult to implement**
***alignment***
***templates***
***...***
**Conventional architectures do not support well dynamic and irregular features (e.g., runtime resolution for subscripted subscripts; inspector-executor paradigm)**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## HPF-2

**HPF-2 is an improvement, but it came too late and was based on an ambiguous “standard”**
***better support for irregular problems (distributions, on-clause)***
***not enough investment into commercial compiler technology***
***not enough flexibility in critical areas (communication scheduling)***
**HPF+/JA-HPF plasma code reached 12.5 TFLOPS on Earth Simulator  **
***explicit high-level formulation of communication patterns***
***explicit high-level control of communication schedules***
***explicit high-level control of halos***

***However:***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Petaflops Architectures Can Support High-Level Programming Models

**High-performance networks and multithreading can contribute to tolerating memory latency and improving memory bandwidth**
**Hardware support for locality-aware programming**
**Abandoning global cache coherence in favor of a more flexible scheme can eliminate a major source of bottlenecks**
**Lightweight processors (possibly in the millions) can be used both as a computational fabric and a service layer**
***exploitation of spatial locality***
***lightweight synchronization***
***an introspection infrastructure for fault tolerance, performance tuning, and intrusion detection***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Issues for Petaflops Programming

**The major goal must be**** ****Productivity**
***performance***
***programmability – time to solution***
***portability***
***robustness***
**This requires significant progress in many fields**
***parallel programming languages***
***compiler technology***
***runtime systems***
***intelligent programming environments***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Operating System and Runtime Environment

**Fault prevention and fault tolerance**
***fault anticipation***
***graceful degradation***
***effective hierarchical recovery mechanisms****** ***
**Autonomous introspective hardware/software**** ****infrastructure for security and self-optimization**
***intrusion detection, prevention, and recovery***
***load balancing and locality management***
***performance analysis, prediction, and feedback-oriented tuning***

***The massive parallelism and complexity of future Petaflops ***
***architectures makes fault tolerance and autonomous system***
***operation key requirements***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Program/

**and Feedback-Oriented Tuning**

**Program/**
**Performance**
** ****Data Base**
** **

* ***execution of instrumented **
**      ****application program**

**compiler**

**instrumenter**

**data collection**

**analysis**
**agent**

**invariantchecking agent**

**simplification**
**agent**

**Performance Exception Handler**

**data reduction and filtering**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Cascade

**Cascade is a DARPA-funded HPCS project **
***Led by Cray Inc. (Burton Smith)***
***Partners: Caltech/JPL, Notre Dame U, Stanford U***
**Architecture Highlights**
***High performance network***
***Locales with heavyweight processors and caches for support of temporal locality***
***Smart memory with lightweight processors***
***Support for both UMA and NUMA views of memory ***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Cascade Global Hardware Architecture

**Smart Memory**

**HWP**

**SW-controlled Cache**

**Smart Memory**

**HWP**

**SW-controlled Cache**

- ...

**Global Interconnection Network**

- Local Interconnection Network

-  **PIM**

- LWP

-    M

- LWP

- LWP

-  **PIM**

-  **PIM**

- ...

**Locale**

**Locale**

-    M

-    M

**Lightweight**
**Processors**

**Cascade Global Hardware Architecture**

## Design Criteria of the Cascade High Productivity Language

***Avoid the fragmented programming model****** ***
***Balance generality against the need for details***
**Provide support for:**
**Explicit parallel programming**
**Locality-aware programming**
**interoperability with legacy codes (MPI, Coarray Fortran, UPC, etc.)**
**Generic programming**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## Design Highlights of the Cascade Language

**The ****Concrete Language**** enhances HPF and ZPL**
***Generalized HPF-type data distributions***
***Domains are first-class objects; can be tied to distributions and data structures ***
***Support for automatic partitioning of dynamic graph-based data structures***
***High-level control for communication (halos,...)?***
**The***** *****Abstract Language***** *****supports generic programming**
***abstraction of types: type inference from context***
***abstraction of iteration: generalization of the CLU iterator***
***data structure inference: system-selected implementation for programmer-specified object categories***

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ

## The current programming practice will not survive
program development is becoming too expensive
generalizing the “MPI paradigm”  for Petaflops architectures is nontrivial

A higher level programming paradigm needs strong support from architecture design, language, compiler, and tool technology

The existence of massive parallelism will require introspective and autonomous self-optimizing systems 

***program development is becoming too expensive***
***generalizing the “MPI paradigm”  for Petaflops architectures is nontrivial***
**A higher level programming paradigm needs strong support from architecture design, language, compiler, and tool technology**
**The existence of massive parallelism will require introspective and autonomous self-optimizing systems **

**Conclusion**

- Workshop on Petaflops Programming     SC2003, Phoenix, AZ