# Presentation: 134985

## Scientific Kernels on VIRAM and Imagine

**Leonid Oliker**
**Future Technologies Group**
- NERSC/LBNL
- _[www.](http://www.nersc.gov/~oliker)__[nersc](http://www.nersc.gov/~oliker)__[.](http://www.nersc.gov/~oliker)__[gov](http://www.nersc.gov/~oliker)__[/~](http://www.nersc.gov/~oliker)__[oliker](http://www.nersc.gov/~oliker)_
- Xiaoye Li, Parry Husbands, Adam Janin, Manikandan Narayanan, Kathy Yelick

## Motivation

**Observation: Current cache-based supercomputers perform at a small fraction of peak for memory intensive problems (particularly irregular ones)**
**E.g. Optimized Sparse Matrix-Vector Multiplication runs at ~ 20% of peak on 1.5GHz P4**
**Even worse when parallel efficiency considered**
**Overall ~10% across application benchmarks**
**Is memory bandwidth the problem?**
**Performance directly related to how well memory system performs**
**But “gap” between processor performance and DRAM access times continues to grow (60%/yr vs. 7%/yr)**

## Solutions?

**Better Software**
**ATLAS, FFTW, Sparsity, PHiPAC**** **
**Power and packaging are important too!**
**New buildings and infrastructure needed for many recent/planned installations**
**Alternative Architectures**
**One idea: Tighter integration of processor and memory**
**BlueGene/L (~ 25 cycles to main memory)**
**VIRAM**
**Uses PIM technology in attempt to take advantage of large on-chip bandwidth available in DRAM**** **
**Imagine**
**Stream aware memory hierarchy to support SIMD controlled VLIW clusters**

## VIRAM Overview

- MIPS core (200 MHz)
- Main memory system
- 13 MB of on-chip DRAM
- Large on-chip bandwidth6.4 GBytes/s peak to vector unit
- Vector unit
- Energy efficient way to express fine-grained parallelism and exploit bandwidth
- Typical power consumption: 2.0 W
- Peak vector performance
- 1.6/3.2/6.4 Gops
- 1.6 Gflops (single-precision)
- Fabrication by IBM
- Tape-out in O(1 month)
- Our results use simulator with Cray’s vcc compiler

**Notes:**
This figure presents the floorplan of Vector IRAM. It occupies nearly 300 square mm and 150 million transistors in a 0.18um CMOS process by IBM. Blue blocks on the floorplan indicate DRAM macros or compiled SRAM blocks. Golden blocks are those designed at Berkeley. They included synthesized logic for control and the FP datapaths, and full custom logic for register files, integer datapaths and DRAM.

Vector IRAM operates at 200MHz. The power supply is 1.2V for logic and 1.8V for DRAM. The peak performance for the vector unit is 1.6 giga ops for 64bit integer operations. Performance doubles or quadruples for 32 and 16b operations respectively. Peak floating point performance is 1.6 Gflops. 

There are several interesting things to notice on the floorplan. First the overall design modularity and scalability. It mostly consists of replicated DRAM macros and vector lanes connected through a crossbar. Another very interesting feature is the percentage of this design directly visible to software. Compilers can control any part of the design that is registers, datapaths or main memory. They do that by scheduling proper arithmetic or load store instructions. The majority of our design is used for main memory, vector registers and datapaths. On the other hand, if you take a look at a processor like Pentium 3, you will see that less than 20% of its are is used for datapaths and registers. The rest is caches and dynamic issue logic. While this usually work for the benefit of applications, they cannot be controlled by compiler and they cannot be turned off when not necessary. 

## Our Task

**Evaluate use of processor-in-memory (PIM) chips as a building block for high performance machines**
**For now focus on serial performance**
**Benchmark VIRAM on Scientific Computing kernels**
**Originally for multimedia applications**
**Can we use on-chip DRAM for vector processing vs. the conventional SRAM? (DRAM denser)**
**Isolate performance limiting features of architectures**
**More than just memory bandwidth**

## Benchmarks Considered

**Transitive-closure (small & large data set)**
**NSA Giga-Updates Per Second (GUPS, 16-bit & 64-bit)**
**Fetch-and-increment a stream of “random” addresses**
**Sparse matrix-vector product:**
** ****Order 10000, #nonzeros 177820**
**Computing a histogram **
**Different algorithms investigated: 64-elements sorting kernel; privatization; retry**
**2D unstructured mesh adaptation**

|  | Transitive | GUPS | SPMV | Histogram | Mesh |
| --- | --- | --- | --- | --- | --- |
| Ops/step | 2 | 1 | 2 | 1 | N/A |
| Mem/step | 2 ld 1 st | 2 ld 2 st | 3 ld | 2 ld 1 st | N/A |

## The Results

- Comparable performance with lower clock rate

## Power Efficiency

**Large power/performance advantage for VIRAM from**
**PIM technology**
**Data parallel execution model**

## Ops/Cycle

## GUPS

**1 op, 2 loads, 1 store per step**
**Mix of indexed and unit stride operations**
**Address generation key here (only 4 per cycle on VIRAM)**

## Histogram

**1 op, 2 loads, 1 store per step**
**Like GUPS, but duplicates restrict available parallelism and make it more difficult to vectorize**
**Sort method performs best on VIRAM on real data**
**Competitive when histogram doesn’t fit in cache**

## Which Problems are Limited by Bandwidth?

**What is the bottleneck in each case?**
**Transitive and GUPS are limited by bandwidth (near 6.4GB/s peak)**
**SPMV and Mesh limited by address generation, bank conflicts, and parallelism**
**For Histogram lack of parallelism, not memory bandwidth**

## VIRAMSummary and Future Directions

**Performance advantage**
**Large on applications limited only by bandwidth**
**More address generators/sub-banks would help irregular performance**
**Performance/Power advantage**
**Over both low power and high performance processors**
**Both PIM and data parallelism are key**
**Performance advantage for VIRAM depends on application**
**Need fine-grained parallelism to utilize on-chip bandwidth**
**Future steps**
**Validate our work on real chip!**
**Extend to multi-PIM systems**
**Explore system balance issues**
**Other memory organizations (banks, bandwidth vs. size of memory)**
**# of vector units**
**Network performance vs. on-chip memory**

## General purpose processors badly suited
Large caches not useful
Low memory bandwidth
Superscalar methods of increasing ILP inefficient
Power consumption 
Application-specific ASICs
Good, but expensive/slow to design.
Solution: general purpose “stream processors”
Exploit producer-consumer locality
High arithmetic requirement
Homogenous computation (SIMD controlled VLIW clusters)
Unique (but limited) control logic

**Large caches not useful**
**Low memory bandwidth**
**Superscalar methods of increasing ILP inefficient**
**Power consumption **
- Application-specific ASICs
**Good, but expensive/slow to design.**
- Solution: general purpose “stream processors”
- Exploit producer-consumer locality
- High arithmetic requirement
- Homogenous computation (SIMD controlled VLIW clusters)
- Unique (but limited) control logic

**IMAGINE:****The need for stream processors**

**Notes:**
New Stream Languages
Elegant languages for elegant applications. 
Increased programmer productivity and performance at the same time. 
Eg. StreamIt, Brook, SCORE.

Instead of these babble, use one diagram with stream application in the middle and technology/stream arch/stream languages attacking from all sides. 
Have those NOT just/BUT for: below this diagram 

Also, their main advantage over traditional ASICs is their programmability => better compilation and usability more important for success! 

Traditionally, use application-specific ASICs: but want general purpose chips to reduce time/cost
Low power consumption very desirable

More programmability => More user base => fast time-to-market (think about all hacks to code in MMX! – not elegant) 

## Bandwidth Hierarchy

- 4GB/s

- 32GB/s

**SDRAM**

**SDRAM**

**SDRAM**

**SDRAM**

**Stream **
**Register File**

**ALU Cluster**

**ALU Cluster**

**ALU Cluster**

- 544GB/s

**ALU Cluster**

**ALU Cluster**

**ALU Cluster**

**ALU Cluster**

**ALU Cluster**

**SIMD/VLIW **
**Control**

**Peak BW:**

## IMAGINE ARITHMETIC CLUSTERS:

**Each cluster contains 3 ADD, 2 MULT, 1 DIV/SQRT, ****1 scratch pad register unit, & 1 cluster communication unit**
**32 bit operations: subword operations support 16 and 8 bit data.**
**Local registers on functional units hold 16 words each (total 1.5 KB local registers per cluster)**
**Clusters receive VLIW-style instructions broadcast from microcontroller.**

## VIRAM vs. IMAGINE

|  | VIRAM | ImagineMemory | ImagineSRF |
| --- | --- | --- | --- |
| Memory Bandwidth | 6.4 | 2.7 | 32 |
| Peak Flops (32-bit) | 1.6 | 20 | 20 |
| Peak Flop per Word | 1 | 30 | 2.5 |
| Clock Speed | 200 | 500 |  |
| Data Width Support | 15x18mm  | 12x12mm |  |
| Chip Area | 64/32/16 bit | 32/16/8 bit |  |
| Transistors | 130 Million | 21 Million |  |
| Power Consumption | 2 Watts | 4 Watts |  |

**Notes:**
Area split (bet. Mem and comp.), power, Hz... bring out the important differences
Tell about some common things like multimedia support (round, shiftadd...), subword operations (vpw..) 
Tell about how both processor’s performance is mainly dependent on ability to overlap memory operations with kernel operations on parallel (1 Memory Fnal unit in VIRAM Vs 2 in Imagine) 

Main difference in number of memory units, off vs on memory, 

Stream Operations atomic in Imagine but Chaining supported in VIRAM! 

## Sqmat Microbenchmark: Scalable Synthetic Probe

**Used to gain insight into the architectures and capture performance crossover point**
**Sqmat contains abundant fine-grain parallelism, no data dependencies, and “multi-word” records**
**Sqmat squares a set of ****L ****matrices of size ****NxN ****repeatedly ****M ****times**
**Varying ****N,M**** controls size of comp kernel and ops/word**
**Varying ****L**** controls vector/stream length**
**Start with low end of performance spectrum and work our way up to high efficiency**

## Sqmat:Low ops/word

** **

| N | 1  | 2  | 3  | 4  | 5 |
| --- | --- | --- | --- | --- | --- |
| VIRAM | 4.0% | 19.0% | 25.5% | 25.3% | 36.9% |
| Imagine | 0.1% | 0.7% | 1.4% | 2.3% | 2.9% |

**% of algorithmic peak for varying N with M=1 and L =16**

**% of algorithmic peak for varying L with M=1 and N=3 **

## Sqmat:High ops/word

| M | 1 | 10 | 20 |
| --- | --- | --- | --- |
| VIRAM | 39% | 82% | 89% |
| Imagine | 7% | 38% | 49% |

**% of algorithmic performance for varying M with N=3 and L=1024**

** ****Imagine achieves less then 50% efficiency even though there are 30 multiplications for each memory access**

|  | Imagine (N=5) |  |  |  |
| --- | --- | --- | --- | --- |
| Ops/Word | 100 | 200 | 300 | 400 |
| % Peak | 86% | 89% | 90% | 91% |

**Achieving high efficiency using long streams and high computation**

**To achieve 90% efficiency on Imagine, requires large (N=5) ****computational kernel and many ops per word**

## Sqmat:Performance Crossover 

**Performance crossover for N=3 and M=10**

**VIRAM performance flattens while Imagine continues to grow.  At L=1024, Imagine raw power becomes apparent - requiring 33% fewer cycles and 4x improvement in MFlop/s**
** ****Codes are better suited for each architecture depending on their computational characteristics **

## Low Comp Intensity Example:SPMV

|  |  | VIRAM |  |  | Imagine |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| MatrixRowsnnz | PerfMetric | CRS | Seg-Sum | Ell-pack | CRS | Stream | Ell-pack |
| Lshape10086958 | % Peak | 2.8% | 7.4% | 31% | 1.1% | 0.8% | 1.2% |
|  | Cycles | 66823 | 23802 | 5666 | 40300 | 48190 | 37930 |
|  | MFlops | 44 | 118 | 496 | 170 | 142 | 186 |
| LgeDIS10000177820 | % Peak | 3.2% | 8.4% | 32% | 1.5% | 0.6% | 6.3% |
|  | Cycles | 802070 | 567491 | 641512 | 742310 | 1840380 | 753540 |
|  | MFlops | 91 | 135 | 511 | 240 | 97 | 1088 |

**Performance is low using original matrix due to lack of parallelism (only 8 and 18 nnz per row).  But VIRAM achieves much higher fraction of peak**
**Ellpack (filled) version shows better performance on both arch, but VIRAM still showing better performance characteristics**
**Note that padding matrices to create equal row lengths can reduce the fraction of useful operations arbitrarily low (but equally across both architectures)**

## High Comp Intensity Example:Complex QR Decomposition

|  |  | VIRAM | Imagine |
| --- | --- | --- | --- |
| Matrix | Metric |  |  |
| MITRERT_STAP192x96complexmatrix | % peak | 34.1% | 65.5% |
|  | Cycles | 5188817 | 712770 |
|  | MFlop/s | 546 | 13100 |

**Both use block variants of the Householder QR - rich in BLAS3 operations**
**Use of complex elements increases computational intensity (ops/word)**
**VIRAM version is a port of CLAPACK, involves inserting vectorization directives into BLAS routines and minimizing strided access**
**Imagine uses blocks of 8 columns and requires complicated indexing logic**
**VIRAM only sustains 34% of peak due to large stride memory access**
**Imagine performs at 65% of peak with an impressive speed of over 13GFlop**
**Demonstrates significant performance that can be achieved on Imagine****for applications with high operations per memory access**

## VIRAM and IMAGINE:Current usability problems

**VIRAM**
**Compiler poor at basic block scheduling**
**No automatic unroll/software pipelining**
**Hand-tweaking assembly**
**No ISA support for multi-word records **
**Degrades memory performance**
**Increases program complexity**

**Imagine**
**Programmer exposed to memory hierarchy**
**2 levels of programming**
**Number of clusters (8) exposed in ISA**
**Not portable**
**Hard to handle streams with (size % clusters) != 0**
**Burden on programmer**
**Complicated control logic**
**Brook language attempts to address these issues**

**Notes:**
 Programming model (vcc and streamC/kernelC) – add it with RGB->YIQ code slide – should we couple it with RGB->YIQ code

say about vpw ease vs subword operations (as in MMX that requires packing and unpacking) and no problem with special alignment (hw treats unaligned opns properly) 
Imagine exposes cluster numbers (through commucdata insns..) and it is more work to handle anything not a multiple of 8 ! (eg. autocorr) 

Some quirks with both tool systems: (not fundamental issues) 
Compiler vectorizes all code pretty well but usual compiler optimization like loop-invariant hoisting, code scheduling, loop unrolling, fixed point operations... not done well. A good quality compiler can obviate assembly coding 
Imagine requires profiling each code before running it. Again is entirely an implementation artifact. 

## Observations:VIRAM and IMAGINE

**Relative performance depends on computational requirements per data element (Bytes/Flop)**
**Different balance of memory organization**
**Programming complexity is high for both approaches, although VIRAM is based on established vector technology**
**For well-suited applications Imagine processor can sustain over 10GFlop/s (simulated results)**
**Large number of homogeneous computation required to sufficiently saturate Imagine while VIRAM can operate on small vector sizes**
**IMAGINE can take advantage of consumer-producer locality**
**Both present significant reduction in power and space**