# Presentation: 191825

## HPCToolkit for  Top-Down

**Robert Fowler**
**John Mellor-Crummey Nathan Tallent**
**Gabriel Marin **
**(and others)**
**Department of Computer Science**
**Rice University**

**HPCToolkit for  Top-Down**
**Analyzing Node Performance**

- (soon: http://www.cs.rice.edu/~rjf/newstuff/RiceTools_5_2003.ppt)

## Outline

**Other Stuff**
**Motivation**
**Compilation Tools**
**HPCTools Toolkit**
**hpcview**
**bloop**
**what you can do with it**

- 2

## What we (Rice Parallel Compilers Group) do –
Code optimization
Aggressive (mostly source-to-source) compilation.
Hand application of optimizing transformations.
Try out transformations by hand first.
Work on real codes with algorithm, library, and application developers.
We spend a lot of time (too much?) analyzing  executions.  Why?
Deeply pipelined, out of order, superscalar  processors with non-blocking caches and deep memory hierarchies.
Aggressive ( -O4), bad, and/or idiosyncratic vendor compilers.
Amdahl’s law says that you have to get all the pieces right.
What we did –-
Built tools to meet our needs w.r.t.  the run/analyze/tune cycle.
They were so useful that we are now distributing them
Why I’m here --
To kickstart some collaboration on performance work.
To present the tools
To identify targets of opportunity for future projects.

**Code optimization**
**Aggressive (mostly source-to-source) compilation.**
**Hand application of optimizing transformations.**
**Try out transformations by hand first.**
**Work on real codes with algorithm, library, and application developers.**
**We spend a lot of time (too much?) analyzing  executions.  Why?**
**Deeply pipelined, out of order, superscalar  processors with non-blocking caches and deep memory hierarchies.**
**Aggressive ( -O4), bad, and/or idiosyncratic vendor compilers.**
**Amdahl’s law says that you have to get all the pieces right.**
**What we did –-**
**Built tools to meet ****our needs**** w.r.t.  the run/analyze/tune cycle.**
**They were so useful that we are now distributing them**
**Why I’m here --**
**To kickstart some collaboration on performance work.**
**To present the tools**
**To identify targets of opportunity for future projects.**

**Background**

## Short to long term interests

- Immediate Impact Supporting Applications in “Expeditions”

- Long Term Research Affecting Future HPC Systems

- Performance diagnosis tools.

- Hand application of aggressive transformations
- to important codes.

- Compilation for Processor-in-Memory Architectures.

- Source-to-sourcetransformation tools.

- High Performance Script-Programming Systems

- High Perf. Libraries and Components

- Fundamental compiler
- algorithms.

- Scalable, rapidlyconvergingalgorithms forapplications

- Compiler optimizationfor Explicit SPMD
- Languages (UPC, CAF)

- 1B

- Work towards vertical integration along this spectrum.

**Short to long term interests**

## Itanium-2 Compiler/Performance Fun!

| NAS SP | Hand-coded | dHPF |
| --- | --- | --- |
| ORC 2.0 | 325 sec | 345 sec |
| EFC 7.1 | 175 sec | 610 sec |

- (1)

- (2)

- WRF sequential execution times:
- 	900 MHz I2   .67 sec/iteration
- 	667 MHz EV67  .92 sec/iteration

- (3)

- efc does not have a “-g3”option, i.e. you can either
- Profile and debug or turn on optimization.

- (900MHz dual-processor McKinley)

## The Rice Co-Array Fortran Compiler

**Near production-quality F90 front end from Open64**
**Working prototype for a CAF subset **
**allocate co-arrays using static constructor-like strategy**
**co-array access**
**remote data access uses ARMCI get/put**
**process local data access uses load/store**
**synch_all, synch_team synchronization**
**multi-dimensional array section operations **
**Successfully compiled and executed NAS MG **
**platforms: SGI Origin, Itanium2 + Myrinet**
**performance similar to hand-coded MPI**
**We haven’t started to apply aggressive optimizations.**

**The Rice Co-Array Fortran Compiler**

## NAS MG Efficiency (Class C)

- Itanium-2/
- Myrinet 2000/
- efc

## Source-to-source loop translator 

- 4A

- Current capabilities
- Apply code motion to enable fusion
- Skew spatial loops to enable fusion and blocking
- Fuse loops at multiple levels
- Reduce storage for fused and blocked code
- Block and unroll loops to reuse values in registers
- Generate code with a guard-free core
- Planned enhancements
- Skew temporal loops to improve temporal locality
- Status
- Ready for user trials if you can run on SPARC or SGI
- Porting (~.5M lines of legacy C++) to Linux/IA32 compilers.

## Performance Results

**Automatic N-level fusion and storage optimization **
**applied to the NCOMMAS Runga-Kutta Kernel.  (Origin 2k)**

- 5C

| Code | Cycles | L1 Misses | L2 Misses | TLB Misses |  |
| --- | --- | --- | --- | --- | --- |
| Original | 1 | 1 | 1 | 1 |  |
| 1-level fusion | 0.94 | 1.31 | 0.85 | 0.45 |  |
| 1-level fusion w/ array contraction | 0.67 | 1.42 | 0.41 |  | 0.06 |
| 2-level fusion w/
array contraction | 0.69 | 1.14 | 0.39 | 0.06 |  |
| 1-level fusion w/ unroll-and-jam | 0.94 | 1.16 | 0.72 | 0.47 |  |

## Hardware Performance Counters

**What they do**
**count “events”**
**record information about an instruction as it executes**
**Utility**
**capture information about performance critical details that is otherwise inaccessible**
**cache and TLB misses, mispredicted branches, etc.**
**Ways to exploit them**
**instrument code to start, stop, read, reset counters**
**typically a manual process**
**sample events during execution**

- 3

## Sample-based Performance Analysis

**Each time an event threshold count is exceeded**
**sample the program counter**
**record it in a histogram**
**Map sampled PC values back to source lines**
**Advantages**
**provides a high-level view of where “events” happen during execution **
**can be started at launch time without prior preparation**
**NOTE: on Alpha EV67, most sampling is instruction based rather than event based**

- 4

## hpcview

**A tool for exploring profile-like data**
**Evaluate node performance of large scientific applications**
**Pinpoint key code fragments and issues**
**Complementary to tools for analyzing parallel efficiency**

- 5

## Approach

**Gather multiple performance metrics from hardware performance counters, simulation, and other sources**
** ****ssrun on SGI, papirun on Linux, DCPI and uprofile on Tru64.**
**Compute user-specified derived tuning metrics with an expression interpreter**
**e.g. wasted time = cycles - FLOPS**
**Correlate metrics with program structure and source code**
**Provide integrated user interface based on hypertext browsing technology**

- Works for all languages, programming models and large applications

- 6

## Support a Hierarchy of Views

**Problem**
**line-level performance statistics may be inaccurate, and offer a myopic view of program performance**
**Goal**
**language-independent solution that enables construction of hierarchical program views**
**Approach**
**recover program structure through analysis of application binaries with bloop tool**

- 7

**Source code**

**Hierarchical display of metrics**

**Files**

**Navigation**

- 8

## Hierarchical display of metrics

- Source Text Pane

- Files

- 14% of cycles spent in this
- loop

## Slide 17

## Assessment of HPCView Functionality

**Top down analysis focuses attention where it belongs **
**sorted views put the important things first**
**Integrated browsing interface facilitates exploration**
**rich network of connections makes navigation simple**
**Hierarchical, loop-level reporting facilitates analysis**
**more sensible view when statement-level data is imprecise**
**Binary analysis handles multi-lingual applications and libraries**
**succeeds where language and compiler based tools can’t**
**Sample-based profiling, aggregation and derived metrics**
**reduce manual effort in analysis and tuning cycle**
**Multiple metrics provide a better picture of performance**
**Platform independent analysis tool**
**Limited by quality of the compiler, instrumentation.**

- 20

## bloop

**Recovers loop nesting structure from application binaries**
**identify basic blocks**
**recover control flow graph (CFG)**
**identify natural loop nests in CFG**
**Map machine instructions to source lines using symbol table**
**Normalize output to recover source-level view**
**Current binary formats**
**MIPS, Alpha, Pentium4, IA64, Sparc**

- 9

## <PGM n="/apps/smg98/test/smg98">
   ...
   <F n="/apps/smg98/struct_linear_solvers/smg_relax.c">
      <P n="hypre_SMGRelaxFreeARem">
         <L b="146" e="146">
            <S b="146" e="146"/>
         </L>
      </P>
      <P n="hypre_SMGRelax">
         <L b="297" e="328">
            <S b="297" e="297"/>
            <L b="301" e="328">
               <S b="301" e="301"/>
               <L b="318" e="325">
                  <S b="318" e="325"/>
               </L>
               <S b="328" e="328"/>
            </L>
            <S b="302" e="302"/>
         </L>
      </P>
      ...
   </F>
 </PGM>

-    ...
-    <F n="/apps/smg98/struct_linear_solvers/smg_relax.c">
-       <P n="hypre_SMGRelaxFreeARem">
-          <L b="146" e="146">
-             <S b="146" e="146"/>
-          </L>
-       </P>
-       <P n="hypre_SMGRelax">
-          <L b="297" e="328">
-             <S b="297" e="297"/>
-             <L b="301" e="328">
-                <S b="301" e="301"/>
-                <L b="318" e="325">
-                   <S b="318" e="325"/>
-                </L>
-                <S b="328" e="328"/>
-             </L>
-             <S b="302" e="302"/>
-          </L>
-       </P>
-       ...
-    </F>
-  </PGM>

**Recovered Program Structure**

- 10

## Flattening for Top Down Analysis

**Problem **
**strict hierarchical view of a program is too rigid**
**want to compare program components at the same level as peers**
**Solution **
**enable a scope’s descendants to be flattened to compare their children as peers**

**flatten**

**Current scope**

- 11

**unflatten**

## Using HPCTools Toolkit

- ssrun –fcy_hwc a.out ; prof –lines a.out.fcy_hwc.f123

**platform dependent**
**profile**

**source**

**hyperlinked**
** ****database**

**portable profile**

**ptran**

**hpcview**

**a.out**

**bloop a.out**

**program **
**structure**

**portable profile**

**...**

**configuration file**

- 12

## hpcview Configuration File

** **** ****<****TITLE**** ****name****="POP 4-way shmem, model_size=medium" /> **** **** **
**<****PATH**** ****name****="." /> **** **** **
**<****PATH**** ****name****="./compile" /> **** **** **
**<****PATH**** ****name****="../sshmem" /> **** **** **
**<****PATH**** ****name****="../source" /> - **
**<****METRIC name****="pcc"**** displayName****="Cycles">**** **** **
**     ****<****FILE**** ****name****="pop.fcy_hwc.pxml" /> **** **** **
**</****METRIC****> **
**<****METRIC name****="dc"**** displayName****="L1 miss">**** **** **
**     ****<****FILE**** ****name****="pop.fdc_hwc.pxml" /> **** **** **
**</****METRIC****> **
**<****METRIC name****="dsc"**** displayName****="L2 miss">**** **** **
**     ****<****FILE**** ****name****="pop.fdsc_hwc.pxml" /> **** **** **
**</****METRIC****> **
**<****METRIC name****="fp"**** displayName****="FP insts">**** **** **
**     ****<****FILE**** ****name****="pop.fgfp_hwc.pxml" /> **** **** **
**</****METRIC****> **
**<****METRIC name****="rat"**** displayName****="cy per FLOP">- **
**     ****<****COMPUTE****> **
**         ****<math> <apply> <divide/> <ci>pcc</ci> <ci>fp</ci> </apply> </math>**
**     ****</****COMPUTE****>**** **** **
**</****METRIC****>**** **** **
**</****HPCVIEW****>**

**hpcview Configuration File**

**Paths to interesting **
**source directories**

**Heading on Display**

**Metrics defined by Platform Independent Profile Files **

**Expression for derived metric **

- 13

## Some Uses for hpcview

**Identifying unproductive work**
**where is the program spending its time not performing FLOPS**
**Memory hierarchy utilization**
**bandwidth utilization: misses x line size/cycles**
**is prefetching being used? is it helping or hurting?**
**Cross architecture comparisons**
**what program features cause performance differences?**
**Explore the gap between peak and observed performance **
**(max instructions per cycle * cycles) - graduated instructions**
**Evaluating load balance in a parallelized code**
**how do profiles for different processes compare**

- 14

## papirun/papiprof

**papirun: open-source equivalent of SGI’s “ssrun”**
**initiate sample-based profiling of an execution**
**collect data about user program and all dynamic libraries**
**current implementation for Linux**
**papiprof: prof-like tool for use with papirun**
**interpret profiles collected with papirun**
**output styles**
**ascii profile format**
**XML-based profile format for use with HPCView**

- 15

## Getting/Using HPCToolkit

**At NCSA – Currently no supported installations.  **
**(Will work anywhere PAPI can generate profiles.)**
**Old URL:**_** **__**[http://www.cs.rice.edu/~dsystem/hpctools/](http://www.cs.rice.edu/~dsystem/hpctools/)**_
**New URL:**_** **__**[http://hipersoft.cs.rice.edu/hpctoolkit](http://hipersoft.cs.rice.edu/hpctoolkit)**_
**Getting Started:**
**Old distribution regime --  Source and a variety of binary tarballs.**
**New distribution regime --  Use CVS to get a source distribution.**
**Using an installed copy:**
**setenv HPCTOOLKIT <where it’s installed>**
**source $HPCTOOLKIT/Sourceme-csh**
**(Modify examples in the distribution.)**

- 21

## The End

## Sample Flowgraph from an Executable

**Loop nesting structure**
**blue: outermost level**
**red: loop level 1**
**green loop level 2**

**Observation**
**optimization complicates **
**program structure!**

- 11

## Normalizing Program Structure

**Coalesce duplicate lines**
**(1) if duplicate lines appear in different loops**
**find least common ancestor in scope tree; merge corresponding loops along the paths to each of the duplicates**
**purpose: re-rolls loops that have been split**
**(2) if duplicate lines appear at multiple levels in a loop nest**
**discard all but the innermost instance**
**purpose: handles loop-invariant code motion**
**apply (1) and (2) repeatedly until a fixed point is reached**

**Constraint:**** ****each source line must appear at most once**

- 12

- 1