# Presentation: 238336

## A Curmudgeon’s Outlook on Petaflops Programming 

- Rusty Lusk
- Mathematics and Computer Science Division
- Argonne National Laboratory

## The Optimist’s View of Petaflops Programming

- Today’s cumbersome programming models and languages will soon disappear as they are replaced by a simple, elegant language (as yet unknown) for expressing the desired results of complex computations without specifying _*how*_ the computation is carried out.
- This will happen because advanced compiler technology will translate this elegant language into instructions (as yet unknown) for an elegant abstract computer.
- The instructions will be executed at blazing speed by a grillion-processor computer with an elegant execution model of a type as yet unknown.
- No one will have to do anything hard (except maybe the computer architects and the compiler writers).
- Writing petaflops applications will be a _*piece of cake*_!

## The Curmudgeon’s View of Petaflops Programming

- Will MPI predominance persist?
- Yes.
- Are new parallel programming paradigms probable?
- No.
- Could architecture help prevent programming pain?
- Yes, but it won’t.
- How should compilers promote petaflops programming?
- Forget parallelism.  It is too hard. Sequential matrix-matrix multiply is hard enough.

## Jeez, What Makes You Such a Curmudgeon?

- Wounds and scars
- The programming model/language landscape is _*very*_ complicated and unpredictable; pitfalls abound.
- Apparently elegant and powerful ideas fail to have long-term impact, sometimes for “unfair” reasons.
- Those who program, at every level, value their _*productivity*_ above other considerations.
- And they reserve the right to define the term.
- If programmers don’t feel something makes them more productive, they won’t adopt it.
- Three personal case studies follow.
- The perils of optimism

## Case Study 1:  The Ultimate Computer Language

- In 1979 the Argonne group decided to redo its 8-year old project (the world’s best automated theorem prover, written in IBM 360 assembly language with a layer of PL/1 on top) in order to attain
- Portability
- Parallelism
- Better software engineering
- We were willing to learn any new language or technology, but the choices were slim:
- C was still proprietary
- Fortran was too limited
- PL/1 was not portable
- Lisp was too slow

## Case Study 1 (continued): The Ultimate Computer Language

- The choice was clear:  a new language was being formulated by a broadly-based international community, to replace both COBOL and FORTRAN, add all desirable features, even parallelism:  Ada!
- Since Ada compilers weren’t ready yet, we wrote 250,000 lines of the portable language that could most easily be translated into Ada when it became available: Pascal!
- The first Ada compiler took two minutes to compile “Hello world”.  By the time Ada became good enough for a substantial community to use, we had junked the Pascal code.
- Neither Ada nor Pascal ever made it into the mainstream.
- Lesson:  you can try really hard and still get it wrong.  It is not that application groups are too timid to try new things.

## Case Study 2:  The Ultimate Parallel Execution Model in Search of a Programming Model

- In 1984, Argonne acquired the first commercial parallel computer, the shared-memory Denelcor HEP.
- Every memory location had a “full/empty” bit, and there were machine instructions to
- Wait until empty, then store and set the bit to “full”
- Wait until full, the load and set the bit to “empty”
- This is really cool.  Very fine grain synchronization.  Architecture in service of compilers.
- But how to write user programs?
- I.e., user-level programming model, language, compiler
- HEP Fortran was an elegant, thin layer of access to the hardware.

## Case Study 2 (continued): The Ultimate Parallel Execution Model in Search of a Programming Model

- The idea was to promote the hardware model right into the language:
- A and $A are different variables
- A = B             normal assignment
- $A = B            wait until A is empty, then assign
- A = $B            wait until B is full, then assign
- Optimist’s plan: take a sequential Fortran program, decorate some of its variables with $’s, and voila!  A parallel program.
- If you didn’t try this yourself, it is difficult to convey to you how painful this turned out to be for non-trivial algorithms
- E.g,      C = $B**2      is _*very*_ different from     C = $B*$B
- But this wasn’t the worst part;  the profligate use of locks turned out to be analogous to the profligate use of branch instructions:  a bad idea from the point of view of program structure.
- A higher-level model/language never had time to evolve.

## Case Study 2 (continued): The Ultimate Parallel Execution Model in Search of a Programming Model

- Eventual partial solution: use the $ variables to implement monitors (an existing programming model for shared objects), and program with these (hiding the locks in a way analogous to hiding branch instructions in if and while statements).
- This worked for us, but monitors were most appropriate for simple programs, and shared-memory machines eventually gave way to distributed-memory machines.
- This architecture is still a very nice idea, but it is not clear (yet) how to serve it up to the programmer and software engineer.
- The programming model to exploit it hasn’t yet been found, and finding it still might not be enough.
- Lesson:  a productive programming model / language /environment is necessary before even the most elegant hardware design can take hold.

## Case Study 3:  The Perfect Model and Language for Parallelism

- There is a programming paradigm that, for small and moderate-sized programs, offers
- Exceedingly compact code
- Portability
- Verifiability (the specification is the program, in a meaningful sense.)
- Automatic fine-grained parallelism
- Logic programming (Prolog and variants)
- In collaboration with groups in England and Sweden, Argonne produced an implementation of OR-parallel Prolog.
- The Japanese 5th-generation project was the best known effort in this direction.

## quicksort([X|Xs], Ys]) :-
    partition(Xs, X, Littles, Bigs),
    quicksort(Littles, Ls),
    quicksort(Bigs, Bs),
    append(Ls, [X|Bs], Ys).
quicksort([], []).

partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y, partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls, [X|Bs]) :- X  >  Y, partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

-     partition(Xs, X, Littles, Bigs),
-     quicksort(Littles, Ls),
-     quicksort(Bigs, Bs),
-     append(Ls, [X|Bs], Ys).
- quicksort([], []).
- partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y, partition(Xs, Y, Ls, Bs).
- partition([X|Xs], Y, Ls, [X|Bs]) :- X  >  Y, partition(Xs, Y, Ls, Bs).
- partition([], Y, [], []).
- append([], Ys, Ys).
- append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

- Example:  Quicksort

## Case Study 3 (continued):  The Perfect Model and Language for Parallelism

- So why not Prolog?
- Too hard.  The programming model is equivalent to first-order symbolic logic.  It is powerful but unfamiliar to programmers.
- Prolog compilers still too slow.
- The 5th-generation project created special-purpose hardware for speed, but it is hard for special-purpose hardware to keep up with the mainstream.  Time ran out.
- Not a good match for scientific applications (although perhaps could be extended for that purpose).
- Explicit control of parallelism turned out to be necessary for performance.
- Software engineering issues for very large projects, I/O.
- Lesson:  Even an elegant, high-level, portable, parallel model with hardware support is not enough to have long-term impact.

## Ten years ago:  How I Learned to Stop Worrying and Love MPI

- To our monitors (see case study 2) we added a simple send/receive for networks of heterogeneous machines, and wrote portable parallel programs using the resulting system, called p4.
- Vendors supplied individual high-performance message-passing libraries (nx, EUI, CMMD, etc) for their own machines.
- PVM achieved wide success because of its _*portability.*_
- In 1992 the MPI Forum convened, to try to define a new message passing interface that would
- Be portable
- Not inhibit performance
- Add a number of features not in existing systems (modularity, heterogeneity
- Why did this work out so well?

## Productivity

- One reason applications use MPI is because they find it a *productive* approach.
- We should look at what has made MPI a success.
- The success of Global Arrays is due to some of the same aspects.
- Any successful alternative programming model must address some of the same issues.
- Use of libraries is the key to productivity (e.g. PETSc).
- It is not clear how to relate application productivity, which might use a high-level approach (e.g. MATLAB) to the model/language used in the library (e.g. MPI)
- These considerations may not apply to small programs with short lives, but to the libraries that support large, complex applications.

## Some Reasons MPI is Successful

- Complete – many flavors of message passing are provided
- Multiple send modes
- Extensive collective operations
- I/O is included
- No active messages or interrupt-driven receives
- Allows maximum performance
- E.g., does not require buffering, allows thread safety
- Small subset easy to learn and use
- Easy to port existing message-passing codes, and MPI itself
- New “high-level” ideas proving useful, even beyond MPI
- Communicators encapsulate process groups and contexts
- Datatypes express non-contiguous, typed data
- Profiling interface provides generalized access for tools
- Modularity provided by communicators allows encapsulation of MPI calls in libraries

## Why Has MPI Succeeded?(Important to understand when contemplating alternatives)

- Open process of definition
- All invited, but hard work required
- All drafts and deliberations open at all times
- First decision was not to standardize on any existing system
- Portability
- Need not lead to lowest common denominator approach
- MPI semantics allow aggressive implementations
- Ubiquitous; applications can be developed anywhere
- Performance
- MPI can help manage the memory hierarchy
- Collective operations can provide scalability
- Cooperates with optimizing compilers
- Simplicity
- MPI (i. e., MPI-2) has 275 functions; is that a lot?
- Can write serious MPI applications with 6 functions
- Economy of concepts, for example communicators, datatypes

## Why Has MPI Succeeded?(continued)

- Modularity
- MPI supports component-based software with communicators
- Support for libraries means some applications may contain no MPI calls
- Composability
- MPI works with other tools (compilers, debuggers, profilers)
- Provides precise interactions with multithreaded programs
- Completeness
- Any parallel algorithm can be expressed
- Easy things are not always easy with MPI, but
- Hard things are possible
- Transparency
- What you code is what you get

## The Current Situation

- Many MPI implementations
- From all vendors
- From multiple open-source sources
- Standardization (and adoption of the standard!) provides an attractive target for
- Implementation research (e.g., MPICH2 has brand-new collective operations and a completely new way of managing datatypes).
- Design and implementation of libraries
- (Less directly) computer and network architecture
- New Global Address Space (GAS) languages (UPC, Co-Array Fortran, Titanium) offer higher-level of abstraction for applications
- Don’t yet offer versions of some features applications and libraries need and MPI addresses (e.g. I/O, modularity)
- But they are coming along fast.
- Many libraries, both general and applications specific, built on MPI.
- Not many applications/libraries yet taking advantage of the new programming model provided by MPI-2.

## Let’s go back to those questions again...

- Will MPI predominance persist?
- Yes, because it has many features needed by an interface at its particular level.  It may evolve, but it already has important features (the remote memory operations) that have not yet been exploited.
- Are new parallel programming paradigms probable?
- They will either be at levels above MPI and will have to address a smaller range of applications or provide all of the functionality of MPI, which is a lot.
- Could architecture help prevent programming pain?
- It could, but indirectly, by supporting the runtime system that supports the languages and libraries above.
- How should compilers promote petaflops programming?
- Work on the sequential part.
- Provide languages that can be implemented on a wide range of machines.  Both special-purpose and complete languages are needed.

## Things to Look Out For

- Beware the assumption that there must be only one type of solution.
- An implementation of MATLAB can use a ScaLAPACK library written in terms of OpenMP and MPI.  Which is the parallel programming paradigm being used?
- The lowest portable interface, however, has particular significance.  So far, MPI is the best we have here.
- Beware the bogus benchmark!
- Measurements of programmer productivity on small exercises shed little light on the productivity of a team developing a large, complex application system.
- If a program is written in two ways, be sure that each is required to produce the same result.
- Beware parochialism
- A narrow target is hard to support in the long run.

## An Example Potential Petaflops Application

- The FLASH code simulates matter accumulation  on the surface of compact stars, nuclear ignition of the accumulated (and stellar) matter, and the subsequent evolution of the star’s interior, surface, and exterior, leading to X-ray bursts, novae, and Type 1 supernovae.
- Medium-sized (300,000 lines of Fortran-90, C, and Python).
- Fluid-dynamics, nuclear burning, MHD, AMR
- Relies heavily on an AMR library
- No MPI calls in the application code!

**FLASH App**

**Problem Description language**

**Paramesh, other parallel libraries**

**MPI**

**All parallel machines**

## View of the Optimistic Curmudgeon

- Petaflops programming _*will*_ be done, using multiple approaches simultaneously.
- Hardware choices will provide different points in the space defined by cpu speed, memory size, memory bandwidth and latency, network bandwidth and latency, parallelism, and price.
- Hardware platforms will come with their own OS’s and runtime systems.  Networks will be available both integrated and separate, depending on platform.
- New languages will be built on both MPI and lower-level runtime systems.
- Library development will flourish, building up from MPI-2.
- Applications development systems will freely choose from a toolkit of languages and libraries that suit their requirements.
- Writing petaflops applications will be a _*piece of cake*_!

## The End

## Outline

- The DOE Office of Science Center for Programming Models for Scalable Parallel Computing
- Who
- Goals
- Approach
- Productivity
- In the small
- In the large
- What to do about it
- Focus on research that produces results that we can use

## Programming Models for Scalable Parallel Computing         (www.pmodels.org)

**Coordinating Principal Investigator:**
- Ewing Lusk – Argonne National Laboratory
**Co-Principal Investigators (Laboratories):**
- William Gropp – Argonne National Laboratory
- Ricky Kendall – Ames Laboratory
- Jarek Nieplocha – Pacific Northwest National Laboratory
**Co-Principal Investigators (Universities):**
- Barbara Chapman – University of Houston
- Guang Gao – University of Delaware
- John Mellor-Crummey – Rice University
- Robert Numrich – University of Minnesota
- Dhabaleswar Panda – Ohio State University
- Marc Snir – University of Illinois
- Thomas Sterling – California Institute of Technology
- Marianne Winslett  – University of Illinois
- Katherine Yelick – University of California, Berkeley

## Problem Statement

- Problem:  Current programming models have _*enabled*_ development of scalable applications on current large-scale computers, but the application development process itself remains complex, lengthy, and expensive, obstructing progress in scientific application development.
- Solution:   _*Facilitate*_ application development by providing standard libraries, convenient parallel programming languages, and petaflops-targeted advanced programming models.
- Goals:  An array of attractive options for convenient, efficient, _*development*_ of scalable, efficient scientific applications for terascale computers

## Obstacles to Development of Scalable Applications

- Cumbersome programming models
- Lack of support for component software
- Mismatch between application structure and programming model
- Mismatch between programming model and machine organization
- Loss of transparency in communication subsystems
- Impacts debugging, tuning
- Hardware complexity
- Managing I/O

## Current Practice(for portable, parallel, scalable codes)

- Standard programming languages with mature compilers
- Fortran-(77,90,95), C, C++
- coupled with
- Communication libraries
- MPI-1 (a community standard)
- Global Arrays
- Shmem (successful on T3E)
- often supporting
- General or domain-specific libraries
- ScaLAPACK
- PETSc
- NWChem
- ...

## Current Exploratory Research

- Libraries
- MPI-2 implementations and extensions
- Global Arrays implementations and extensions
- Portable SHMEM implementation
- Languages
- Early compilers for Global Address Space languages:
- UPC
- Co-Array Fortran
- Titanium
- Portable, but not all highly optimized or containing all necessary features
- OpenMP directives, function calls with C, Fortran
- Advanced Models
- Multi-threading for multi-threading hardware, PIMS
- Parcels and percolation

## A Three-Pronged Approach to Next-Generation Programming Models

- Extensions to existing library-based models
- MPI (-3)
- Global Arrays and extensions
- Portable SHMEM
- Robust implementations of language-based models
- UPC
- Co-Array Fortran
- Titanium
- OpenMP optimizations
- Advanced models for advanced architectures
- Multithreaded, PIM-based machines, Gilgamesh, etc.
- Virtualization of processors
- Virtualization of memory system
- Hierarchical parallelism

## Technical Challenges

- Finding the library extensions application developers need
- Implementing libraries scalably
- Refining the definitions of experimental parallel languages to make them more convenient
- Defining portable runtime library that can provide communications services for multiple languages
- Implementing the runtime library scalably and portably
- Providing interoperability among models and languages
- Defining a programming model suitable for petaflops architectures
- Determining critical hardware mechanisms for efficient scalable execution
- Testing advanced programming models with applications

## Relationships Among the Parts

**Model Instances**

- EARTH

- Titanium

- GPSHMEM

- GA

- MPI-2

- MPI

- UPC

- CAF

- OpenMP + MPI

- OpenMP

**Implementation Substrate**

- Panda Parallel I/O

- CAF Packages/ Modules

- Common Runtime

- ARMCI

- ADI-3

- Open64 Compiler

- HDF-5

## Programming Models and Productivity

- The issue of metrics for productivity applied to programming models is more complex than it looks.
- Everything depends on the “program” being studied.
- Most scientific applications are better described as *systems* rather than *programs.*
- Let us consider at least two types of “productivity”:
- Productivity “in the small”
- Productivity “in the large”
- Actually, there is a range, with some discontinuities.

## Productivity in the Small

- It can be misleading in the long run to study
- Small programs (unless they really tell us about big ones)
- Throwaway programs (unless these are the real apps)
- Kernels (by definition, are worth lots of attention)
- Comparing programming models on such programs is relatively easy, and has been done in the classroom, but may not produce answers that we can really apply.
- What programming model and/or language yields the most compact, portable, verifiable, parallel, easy-to-write version of, say, quicksort?
- My answer: Prolog (the ultimate executable specification).
- Prolog is a specific execution model for the logic programming model
- This doesn’t tell us much.

## quicksort([X|Xs], Ys]) :-
    partition(Xs, X, Littles, Bigs),
    quicksort(Littles, Ls),
    quicksort(Bigs, Bs),
    append(Ls, [X|Bs], Ys).
quicksort([], []).

partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y, partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls, [X|Bs]) :- X  >  Y, partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

-     partition(Xs, X, Littles, Bigs),
-     quicksort(Littles, Ls),
-     quicksort(Bigs, Bs),
-     append(Ls, [X|Bs], Ys).
- quicksort([], []).
- partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y, partition(Xs, Y, Ls, Bs).
- partition([X|Xs], Y, Ls, [X|Bs]) :- X  >  Y, partition(Xs, Y, Ls, Bs).
- partition([], Y, [], []).
- append([], Ys, Ys).
- append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

- Quicksort

## Productivity in the Large

- One reason applications use MPI is because they find it a *productive* approach.
- We should look at what has made MPI a success.
- The success of Global Arrays is due to some of the same aspects.
- Any successful alternative programming model must address some of the same issues.
- Use of libraries is the key to productivity (e.g. PETSc)
- It is not clear how to relate application productivity to the model/language used in the library
- These considerations may not apply to productivity in the small, which remains a legitimate target, just not the only one.

## Some Reasons MPI is Successful

- Complete – many flavors of message passing are provided
- Multiple send modes
- Extensive collective operations
- I/O is included
- No active messages or interrupt-driven receives
- Allows maximum performance
- E.g., does not require buffering, allows thread safety
- Small subset easy to learn and use
- Easy to port existing message-passing codes, and MPI itself
- New “high-level” ideas proving useful, even beyond MPI
- Communicators encapsulate process groups and contexts
- Datatypes express non-contiguous, typed data
- Profiling interface provides generalized access for tools
- Modularity provided by communicators allows encapsulation of MPI calls in libraries

## Why Has MPI Succeeded?(Important to understand when contemplating alternatives)

- Open process of definition
- All invited, but hard work required
- All drafts and deliberations open at all times
- Portability
- Need not lead to lowest common denominator approach
- MPI semantics allow aggressive implementations
- Ubiquitous; applications can be developed anywhere
- Performance
- MPI can help manage the memory hierarchy
- Collective operations can provide scalability
- Cooperates with optimizing compilers
- Simplicity
- MPI (i. e., MPI-2) has 275 functions; is that a lot?
- Can write serious MPI applications with 6 functions
- Economy of concepts, for example communicators, datatypes

## Why Has MPI Succeeded?(continued)

- Modularity
- MPI supports component-based software with communicators
- Support for libraries means some applications may contain no MPI calls
- Composability
- MPI works with other tools (compilers, debuggers, profilers)
- Provides precise interactions with multithreaded programs
- Completeness
- Any parallel algorithm can be expressed
- Easy things are not always easy with MPI, but
- Hard things are possible
- Transparency
- What you code is what you get
-     Some people find MPI’s underbelly quite handsome!

## Programming Models and Productivity

- We still seek ways to program (specify the behavior of a complex system) in the most productive way.
- Parallelism and performance to be taken for granted
- It is important to measure the productivity of those creating the entire system and maintaining it, including:
- I/O, both local and remote
- Graphics
- Interactivity
- Fault tolerance
- Maintenance
- Porting in both space and time
- Productivity in the small is not the same as productivity in the large.
- In a nutshell, the metrics are different

## What Should We Do?

- Understand productivity issues in development, use, and maintenance of large-scale, complex, long-lived applications
- Improve current productive approaches
- Implementation research in MPI (esp. Put/Get), OpenMP, others
- Provide libraries that allow high-level programming by application developers
- Develop promising known, but still embryonic, near-term models/languages to the point of real usability
- GAS languages simplify programming when threads need remote data at unpredictable times
- Interoperability will be the key to adoption by applications
- Develop metrics appropriate to productivity in the large
- Conduct *appropriate* experiments
- Understand abstract execution models for petaflops machines
- Create programmer-efficient mechanisms for specifying such execution

## Productivity Experiments in the Small

- Classroom experiments an obviously successful idea
- Some ideas:
- Study more alternatives than MPI vs. OpenMP
- UPC and CAF, for example
- Need robust implementations of the alternatives
- Explore mixed approaches (assumes interoperability)
- Study impact of programming environments
- Editing, debugging, and tuning tools, for example
- Include comparisons of high-level libraries
- PETSc vs. Hypre, for example

## Productivity Experiments in the Large

- Fund > 30 groups of size 10-25 develop applications that are developed over ~8 years and last 50.
- (purpose-based benchmarks )
- Allow them to choose the programming models, languages, software practices, tools, even machines, that *they* believe makes them more productive.
- Watch what they do and learn what speeds them up and what slows them down.
- Choice of programming models may turn out to have a small effect compared to other choices made.
- Tools may look more important, but models impact tools....
- Fortunately, we are currently carrying out this experiment.
- Unfortunately, we are not observing it carefully.
- Designing, organizing, and documenting observations could be a valuable contribution.