# Presentation: 510861

## Compiler Optimizations for Architectures Supporting Superword-Level Parallelism

- USC/ISI

- Jaewook Shin

- June 10 2005

## Multimedia Extension Architectures

- Multimedia applications are becoming increasingly important.
- Most microprocessors have multimedia extensions.
- SIMD parallelism
- Variable-sized data fields

**WIDE UNIT**

- PACT'02

## Superword-Level Parallelism (SLP)

- Fine grain SIMD parallelism in aggregate data objects larger than a machine word

|  | SLP | Vector Parallelism |
| --- | --- | --- |
| Strided Memory Access ? | NO | YES |
| Vector Length | 32 elements | 64 elements |
| Instruction Latency | ~1 | 1 per element |
| Aligned Memory Access ? | YES | NO |

- Most compilers for multimedia extensions are based on conventional vectorization techniques.

- PACT'02

## SLP Compiler (Larsen & Amarasinghe)

**for (i=0; i<16; i++)**
**  ****a[i] = b[i] + c[i];**

**for (i=0; i<16; i+=4){**
** ****a[i+0] = b[i+0] + c[i+0];**
** ****a[i+1] = b[i+1] + c[i+1];**
** ****a[i+2] = b[i+2] + c[i+2];**
** ****a[i+3] = b[i+3] + c[i+3];**
**}**

**for (i=0; i<16; i+=4)**
**  ****a[i:i+3] = b[i:i+3] + c[i:i+3];**

- Unroll by 4

- Pack isomorphic statements

- PACT'02

## Control Flow and the SLP Compiler

**for (i=0; i<16; i++)**
**  ****if (a[i] != 0)**
**    ****b[i]++;**

**Only parallelizes within a basic block !**

- PACT'02

## Our Research

- This Research
- Extend SLP to increase its effectiveness and applicability
- Develop compiler technology for DIVA architecture
- Focus of this talk
- SLP in the presence of control flow
- Compiler controlled caching in superword register file: Superword-Level Locality (SLL)

- PACT'02

## SLP in the Presence of Control Flow

**for (i=0; i<16; i++)**
**  ****if (a[i] != 0)**
**    ****b[i]++;**

**for (i=0; i<16; i+=4){**
**  ****Vcond = a[i:i+3] != (0, 0, 0, 0);**
**  ****Vtemp = b[i:i+3]  + (1, 1, 1, 1);**
**  ****b[i:i+3] = ****Combine**** ****b[i:i+3] ****and**** Vtemp**
**             ****according to**** Vcond;**
**}**

- PACT'02

## Superword-Level Locality (SLL)

- Definition: Exploit data reuse in superword registers
- Large capacity register file as a compiler controlled cache.
- Differences from data reuse in caches
- Eliminates memory access cycles completely
- Storage has to be named explicitly
- Differences from data reuse in scalar registers
- Spatial reuse in superword registers

- 256 bits

- 32

- DIVA

- 128 bits

- 32

- AltiVec

- ...

- ...

- PACT'02

## Superword-Level Locality (SLL): Example

- Before

- for(i=1;i<=32;i++)
-    for(j=0;j<32;j++)
-        A[i][j] = A[i-1][j] + B[j]

- After

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j+=4)
-        SV1 = B[j:j+3]
-        SV2 = A[i-1][j:j+3] + SV1
-        A[i+1][j:j+3] = SV2 + SV1
-        A[i][j:j+3] = SV2

**6X reduction**

- 3072

**# memory accesses**

- 512

- PACT'02

## DIVA (Data IntensiVe Architecture)

- DRAM Array (~32 MB)

- DRAM Page (2048 bits)

**I-Cache (4KB)**

- Wide registers, 32x256b (1KB)

- Scalar registers, 32x32b (128B)

**Wide Functional Unit**

- Scalar functional unit

**Superword-Level**
**Parallelism**

**Page Mode Memory Accesses**

- PACT'02

## 2nd Generation DIVA PIM Chip

- Fabrication technology
- TSMC 0.18m
- Size
- 10.5mm x 11.5mm, 56.6 million transistors
- Package
- 35mm, 420 BGA
- Status
- 140MHz
- ~1W
- Integrated in HP Long’s Peak IA64 server

- BGA Top View

- BGA Bottom View

- PACT'02

## PIM-enhanced HP IA64 System 

- Two 2nd Generation PIM cards in HP Long’s Peak IA64 host
- Could host four boards with eight PIM chips

- PACT'02

## Contributions

- Algorithms to exploit SLP in the presence of control flow
- Algorithms for compiler controlled caching  in superword registers (Superword-Level Locality)
- Implementation and evaluation of the proposed techniques
- DIVA-specific optimizations: Page-mode memory access

- PACT'02

## Overview

- SLP in the presence of control flow
- Superword-Level Locality (SLL)
- Compiler implementation
- Experimental results
- Related work
- Conclusion

- PACT'02

## SLP in the Presence of Control Flow (SLPCF)

**for (i=0; i<16; i++)**
**  ****if (a[i] != 0)**
**    ****b[i]++;**

**for (i=0; i<16; i+=4){**
**  ****Vcond = a[i:i+3] != (0, 0, 0, 0);**
**  ****Vtemp = b[i:i+3]  + (1, 1, 1, 1);**
**  ****b[i:i+3] = ****Combine**** ****b[i:i+3] ****and**** Vtemp**
**             ****according to**** Vcond;**
**}**

- PACT'02

## SLPCF: Key Concepts

- Borrow from optimizations for architectures supporting predicated execution
- Derive a large basic block of predicated instructions
- SELECT operations merge data values for different control flow paths
- Restore control flow

- remove superword
- predicates(SELECT)

- parallelize

- if-conversion

- remove scalar
- predicates (unpredicate)

- PACT'02

## If-Conversion

**if (a != 0)**
**	****b = b + 1;**

**cond = a != 0;**
**pT, pF = ****pset****(cond);**

**b = b + 1;      <pT>**

- PACT'02

## SELECT instruction

**= SELECT(            )**

**3            2 , 3 , 1**
**2            2 , 3 , 0**
**3            2 , 3 , 1**
**2            2 , 3 , 0**

- dst

- src1

- src2

- predicate

**Va = Vb + (1, 1, 1, 1);      <Vp>**

**Vtemp = Vb + (1, 1, 1, 1); **
**Va = ****SELECT****(Va, Vtemp, Vp);**

- PACT'02

## Unpredicate

**bred[i] = 100;    <****¬****p>**
**bgre[i] = fgre;   <p>**
**bgre[i] = 100;    <****¬****p>**
**bblu[i] = fblu;   <p>**
**bblu[i] = 100;    <****¬****p>**

**if (p) {**
**  ****bred[i] = fred;**
**  ****bgre[i] = fgre;**
**  ****bblu[i] = fblu;**
**}else{**
**  ****bred[i] = 100;**
**  ****bgre[i] = 100;**
**  ****bblu[i] = 100;**
**}**

- PACT'02

## Algorithm

- If-conversion:
- Park and Schlansker’s RK-algorithm
- SELECT
- Insert the minimum number of SELECT instructions
- Use reaching definition based on predicate covering
- Unpredicate
- Try to reduce the number of conditional branches
- Use predicate covering

- PACT'02

## PHG represents relationships among predicates.

- Predicate Hierarchy Graph (PHG)

**pT1, pF1 = pset (c1); <TRUE>**

**...**

**pT2, pF2 = pset (c2); <TRUE>**

**...**

**pT3, pF3 = pset (c3); <pT1>**

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**...**

**...**

- PACT'02

## Predicate Covering

- A predicate *p* is covered by a set of predicates *G* if *p* = *true* *p’**G* such that *p’ = true*.

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**I1 <pF3>**
**I2 <pT3>**
**I3 <pT1>**

**pT3**

**pF3**

**G={}**

- Q: Predicate covering
- predecessors of I3 ?

**pT1**

**pT3****}**

**...**

**...**

**,****pF3****}**

**,pT1}**

- PACT'02

## SELECT Algorithm

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**d1: Va=V1; <pF3>**
**d2: Va=V2; <pT3>**
**u3: Vc=Va; <pT1>**

- SELECT is not necessary for the first reaching definition

**d1: Va=V1; **
**d2: Va=SELECT(Va,V2,pT3);**
**u3: Vc=Va; **

**...**

**...**

- PACT'02

## Predicate CFG Generator

- Find the predicate covering predecessors for each predicated instruction.

**I1 <pF3>**
**I2 <pT3>**
**I3 <pT1>**

**I1**

**I2**

**I3**

**if(pT1){**
**  ****if(pF3)**
**	****I1;**
**  ****else**
**	****I2;**
**  ****I3;**
**}**

- (a) predicated
- scalar code

- (b) CFG

- (c) code generated

- PACT'02

## Unpredicate Algorithm

- Schedule each instruction within an existing basic block where it is safe.
- If no such basic block exists, use ‘predicate CFG generator’.

**I1 <p>**
**I2 <****¬****p>**
**I3 <TRUE>**
**I4 <p>**
**I5 <****¬****p>**

**I1**

**I2**

**I3**

- (a) predicated
-       scalar code

- (b) predicate CFG
- generator

- (c) unpredicate

**I4**

**I5**

**I1**
**I4**

**I2**
**I5**

**I3**

**p**

**p**

**p**

**¬****p**

**¬****p**

**¬****p**

**TRUE**

**TRUE**

- PACT'02

## Overview

- SLP in the presence of control flow
- Superword-Level Locality (SLL)
- Compiler implementation
- Experimental results
- Related work
- Conclusion

- PACT'02

## SLL: Key Concepts

- Unroll-and-jam
- To shorten reuse distance
- Superword replacement
- To remove redundant superword memory accesses
- Determine unroll factors such that
- Reuse is increased
- Register requirements are constrained

- unroll-and-jam

- parallelize

- determine unroll
- amounts

- superword
- replacement (SWR)

- PACT'02

## Unroll-and-jam

- Unrolls outer loops and fuses the resulting inner loops together
- Shortens the distance between uses

- PACT'02

## Scalar vs. Superword Replacement

- Identifies array references to the same address
- Replaces array references with scalar/superword variables

- Original loop nest

- for(i=1;i<=32;i+=2)
-    for(j=0;j<32;j++)
-        A[i][j] = A[i-1][j] + B[j]
-        A[i+1][j] = A[i][j] + B[j]

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j+=4)
-        A[i][j:j+3] = A[i-1][j:j+3] + B[j:j+3]
-        A[i+1][j:j+3] = A[i][j:j+3] + B[j:j+3]

- Superword-level parallelization

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j++)
-        T1 = B[j]
-        T2 = A[i-1][j] + T1
-        A[i+1][j] = T2 + T1
-        A[i][j] = T2

- Scalar replacement

- Superword replacement

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j+=4)
-        SV1 = B[j:j+3]
-        SV2 = A[i-1][j:j+3] + SV1
-        A[i+1][j:j+3] = SV2 + SV1
-        A[i][j:j+3] = SV2

- 1.5X

- 4X

- 1.5X

- 6X

- PACT'02

## Putting it all together

- Unroll-and-jam

- Original loop nest

- for(i=1;i<=32;i++)
-    for(j=0;j<32;j++)
-        A[i][j] = A[i-1][j] + B[j]

- for(i=1; i<=32; i++)
-    for(j=0; j<32; j+=4)
-        A[i][j:j+3] = A[i-1][j:j+3] + B[j:j+3]

- Superword-level parallelization

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j+=4)
-        A[i][j:j+3] = A[i-1][j:j+3] + B[j:j+3]
-        A[i+1][j:j+3] = A[i][j:j+3] + B[j:j+3]

- Superword replacement

- for(i=1; i<=32; i+=2)
-    for(j=0; j<32; j+=4)
-        SV1 = B[j:j+3]
-        SV2 = A[i-1][j:j+3] + SV1
-        A[i+1][j:j+3] = SV2 + SV1
-        A[i][j:j+3] = SV2

- PACT'02

## What is required ?

- Unroll amount selection
- Find unroll factors *<X**1**, X**2**, ..., X**n**>* for loops 1 to n
- Goal: Maximize data reuse in superword registers exposed by unroll-and-jam
- Constraint: The number of superword registers required does not exceed the available registers of the register file.
- Register requirement analysis
- Spatial locality
- Code generation
- Superword replacement
- Packing in superword registers

- PACT'02

## Assumptions

- Array subscript expressions are linear functions of loop index variables
- Registers allocated for caching data are live throughout the loop body

- PACT'02

## Register Requirement Analysis

- Derives the number of superword registers required for a particular unroll amount and array references.
- Example: *A[i]** *when *i* loop is unrolled by* **X*

- superword registers are required !

- A[i+0]

- A[i+(X-2)]

- ...

- A[i+1]

- A[i+2]

- A[i+3]

- A[i+(X-1)]

- High address

- superword

- Low address

- PACT'02

## Register Requirement Analysis(cont.)

- For *A[ai+b]** *and an unroll amount* **X*

| Coefficient | Number of registers |
| --- | --- |
| a = 0 | 1 |
| a < SWS |  |
| a ≥ SWS | X |

- The current implementation can also deal with

| Array References | Example |
| --- | --- |
| Multiple index variables | A[ai+bj+c] |
| Multi-dimensional arrays | A[ai+b][cj+d] |
| Group of array references | A[ai+b1][cj+d1], A[ai+b2][cj+d2], ... |

- PACT'02

## Overview

- SLP in the presence of control flow
- Superword-Level Locality (SLL)
- Compiler implementation
- Experimental results
- Related work
- Conclusion

- PACT'02

## Our Implementation

- superword
- level locality

- unroll

- alignment
- analysis

- remove superword
- predicates(SELECT)

- parallelize

- if-conversion

- remove scalar
- predicates (unpredicate)

- output
- C code

- original
- C code

- new for this work

- superword
- replacement

- MIT SLP compiler

- PACT'02

## Benchmarks

| Name | Description | Source |
| --- | --- | --- |
| VMM | Vector-matrix multiply | MIT |
| FIR | Finite impulse response filter | MIT |
| YUV | RGB to YUV color conversion | MIT |
| MMM | Matrix-matrix multiply | MIT |
| swim | Shallow water model | SpecFP |
| tomcatv | Mesh generation | SpecFP |
| Chroma | Chroma keying of two images | In house |
| Sobel | Sobel edge detection | In house |
| TM | Template matching | Sandia |
| Max | Max value search | In house |
| transitive | Shortest path search | DIS stressmark |
| MPEG2-dist1 | MPEG2 encoder (dist1) | UCLA mediabench |
| EPIC-unquantize | EPIC unepic (unquantize_image) | UCLA mediabench |
| GSM-Calculation | GSM gsmencode (Calculation...) | UCLA mediabench |

- PACT'02

## Experimental Flow

- SLP
- compiler

- Control flow extension

- GCC – AltiVec extended

- PowerPC G4

- Original
- C code

- Baseline

- SLP

- SLPCF

- SLL

- SLPCF
- +SLL

- MIT-SLP
- compiler

- MIT-SLP

- PACT'02

## Combined Speedups for the Two Techniques : large data

- PACT'02

## Combined Speedups for the Two Techniques : small data

**15**

- PACT'02

## Packing for Efficient Code Generation

- PACT'02

## Superword-Level Locality

- PACT'02

## Summary of Results

**Overall speedups over sequential versions:  **
**1.05X to 19.22X on 14 benchmarks**
- SLP in the presence of control flow:
- Additional speedups for 8 of 14 benchmarks
- 1.13X ~ 3.89X over without our control flow approach
- Superword-Level Locality(SLL):
- Additional speedups for 9 of 14 benchmarks
- 1.29X ~ 3.90X over without SLL
- Packing for efficient code generation:
- Additional speedups for 5 of 14 benchmarks
- 1.08X ~ 2.96X over without our new packing algorithm
- Branch-on-superword-condition-code (BOSCC)
- Additional speedups for 3 of 14 benchmarks
- 1.20X ~ 1.40X over without BOSCC
- Page-mode memory access
- Additional speedups for 4 data intensive kernels
- 1.25X ~ 2.19X over SLP alone

- PACT'02

## Related Research

| Locality in Scalar Registers | Locality in caches | Superword-Level Parallelism | Predicates |
| --- | --- | --- | --- |
| Wolf(92),
Carr and Kennedy(94)
Jimenez(99) | Wolfe(89),
Ferrante et al(91),
Lam et al(91),
Wolf(92),
Temam et al(93,95),
Carr et al(94), 
Chame and Moon(99),
Rivera and Tseng(99),
Sarkar and Megiddo(00),
Chatterjee(01), ... | Cheong and Lam(97),
Larsen and Amarasinghe(00),
Sreraman and Govindarajan(00),
Bik et. al.(02) | Chuang et. al.(03)
Mahlke(96) |
| - No spatial locality | - Conflict misses
- Simpler storage management | - No data locality at superword register level | - Scalar SELECT
- Our basis |

- PACT'02

## Conclusion

- A compilation system for architectures supporting SLP with emphases on
- SLP in the presence of control flow
- Locality in superword registers
- Implementation in SUIF
- Experimental evaluation on 14 benchmarks
- Speedups over sequential :
- For the above two techniques: 1.05X ~ 15.00X
- For all our techniques: 1.05X ~ 19.22X

- PACT'02

## References

- SLP in the presence of control flow
- J. Shin, M. Hall and J. *Chame, Superword-Level Parallelism in the Presence of Control Flow*, CGO’05
- Compiler-controlled caching in superword registers
- J. Shin, M. Hall and J. Chame, *Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures*, PACT’02
- J. Shin, J. Chame and M. Hall, *Exploiting Superword-Level Locality in Multimedia Extension Architectures*, Journal of Instruction Level Parallelism(JILP) vol. 5
- Branch-on-superword-condition-code
- J. Shin, J. Chame and M. Hall, *Evaluating Compiler Technology for Control-Flow Optimizations for Multimedia Extension*, MSP6, 2004
- Page-mode memory access
- J. Shin, J. Chame and M. Hall, *A Compiler Algorithm for Exploiting Page-Mode Memory Access in Embedded-DRAM Devices*, MSP4, 2002
- DIVA, a PIM-based data-Intensive architecture
- M. Hall, P. Kogge, J. Koller, P. Diniz, J. Chame, J. Draper, J. LaCoss, J. Granacki, J. Brockman, A. Srivastava, W. Athas, V. Freeh, J. Shin and J. Park, *Mapping Irregular Applications to DIVA, a PIM-based Data-Intensive Architecture*, SC’99
- J. Chame, J. Shin and M. Hall, *Compiler Transformations for Exploiting Bandwidth in PIM-Based Systems*, Workshop on Solving the Memory Wall Problem ’00
- J. Draper, J. Chame, M. Hall, C. Steele, T. Barrett, J. LaCoss, J. Granacki, J. Shin, C. Chen, C. W. Kang, I. Kim and G. Daglikoca, *The Architecture of the DIVA Processing-In-Memory Chip*, ICS’02

- PACT'02

## Future Work

- Experiments on DIVA hardware
- Measure performance and compare with AltiVec
- Unique ISA features
- New applications
- Knowledge discovery
- Optimizing for multi-core devices

- PACT'02

## Thank you !

- Questions ...

- PACT'02

## Compiler Technology for SLP

- MIT SLP compiler: Larsen and Amarasinghe(2000)
- Automatically finds SLP within a basic block
- Other optimization opportunities
- SLP in the presence of control flow
- Locality in superword registers

- PACT'02

## DIVA (1998~ )

- Problem: Memory wall
- Solution: Processing-In-Memory(PIM)
- Features:
- Processors and DRAM in a single chip
- 32-byte wide registers
- No data cache
- Compiler:
- Fully automated parallelizing compiler based on the MIT SLP compiler
- GCC backend for DIVA

- PACT'02

## Data Reuse

- Data used multiple times
- A[i][j] and A[i-1][j] have reuse.
- B[j] has reuse.

- for(i=1;i<=32;i++)
-    for(j=0;j<32;j++)
-        A[i][j] = A[i-1][j] + B[j];

- PACT'02

## Unroll Amount Selection

- Unroll amounts that maximize reuse in superword registers
- Prune search space
- Exploit monotonicity at each dimension
- Avoid register pressure

- Search space for FIR

- Unroll amount
- j-loop

- Unroll amount i-loop

- # Mem. Acc.

- PACT'02

## Reuse in Scalar vs. Superword Register

| Reuse | Scalar | Superword |
| --- | --- | --- |
| Self spatial | No | Yes |
|  | for(i=0; i<N; i++) 
A[i] | for(i=0; i<N; i+=4) 
A[i:i+3] |
| Group spatial | No | Yes |
|  | for(i=0; i<N; i++)
A[i], A[i+2] | for(i=0; i<N; i++)
A[i], A[i+2]  |

- A[i]

- A[i+2]

- A[i]

- PACT'02

## Unroll Amount Selection

- Find unroll factors *<X**1**, X**2**, ..., X**n**>* for loops 1 to n
- Goal: Maximize data reuse in superword registers exposed by unroll-and-jam
- Constraint: The number of superword registers required does not exceed the available registers of the register file.

- PACT'02

## Code Generation Optimizations

- Superword Replacement
- Exploit reuse opportunities
- Temporal reuse: similar to scalar replacement
- Spatial reuse: sliding windows such as FIR
- Unaligned memory accesses
- Packing in registers
- Replaces packing through memory
- Reduces memory accesses

- PACT'02

## Effects of Prepacking

- PACT'02

## Overall Improvements Over Scalar (large)

- PACT'02

## Overall Improvements Over Scalar (small)

- PACT'02

## Superword-Level Locality

- PACT'02

## Superword-Level Locality

- PACT'02

## Data Sheet

- BGA: Ball Grid Array
- DIVA:
- AltiVec G4 (533 MHz):
- 32 KB L1 split cache
- 1 MB L2 unified cache

- PACT'02

## Prepacking: Packing for Low Overhead

- pack isomorphic statements
- Ex) Y[i+0] = X[i+0] + X[i+1]
- 	 Y[i+1] = X[i+1] + X[i+2]
- 	 Y[i+2] = X[i+2] + X[i+3]
- 	 Y[i+3] = X[i+3] + X[i+4]

- Pack isomorphic data dependence graphs

- V_load V1  X[i:i+3]
- V_load V2  X[i+1:i+4]
- V_add V3  V1, V2
- V_store V3  Y[i:i+3]

- 	V_load V  X[i:i+1]
- 	V_store V  &V
- 	load S1  &V+0
- 	load S2  &V+1
- 	add S3  S1, S2
- 	store S3, Y[i]
- 		...

- PACT'02

## Benchmarks

- Kernels without conditionals
- VMM, FIR, YUV, MMM
- SPECfp benchmark
- swim, tomcatv
- Kernels with conditionals
- Chroma, Sobel, TM, Max, transitive
- Functions from UCLA MediaBench
- MPEG2-dist1, EPIC-unquantize, GSM-Calculation
- Two data set sizes
- Large: Representative data set
- Small:  Footprint in cache isolates parallelism effects

- PACT'02