# Presentation: 661710

## Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures

- PACT’02

*Jaewook Shin*, Jacqueline Chame and Mary Hall

- September 23, 2002

## Motivation

- Multimedia applications are becoming increasingly important.
- Multimedia Extension Architectures
- Intel SSE, Motorola AltiVec, ...
- New compiler technology for new optimization goals
- Exploit fine-grain parallelism supported by architecture
***Exploit reuse of data in the large register files****** ***

- PACT'02

## Overview

- Motivation
- Background
- Unroll-and-jam
- Scalar replacement
- Algorithm
- Unroll amount selection for unroll-and-jam
- Register requirement analysis
- Superword replacement
- Packing in registers
- Experiments
- Reduction in dynamic memory accesses
- Speedup
- Conclusion

- PACT'02

## Superword-Level Parallelism (SLP)

- Definition: Fine grain parallelism in aggregate data objects larger than a machine word
- Architectural features include:
- Variable-sized data fields
- Support to rearrange data fields
- Superword register file

- Motivation

- PACT'02

## Superword-Level Locality (SLL)

**Superword-Level Locality (SLL)**

- Definition: Exploit data reuse in superword registers
- Large capacity register file is used 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

- Motivation

- 256 bits

- 32

- DIVA

- 128 bits

- 32

- AltiVec

- ...

- ...

- PACT'02

## Unroll-and-jam

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

- Background

- PACT'02

## Scalar vs. Superword Replacement

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

- Background

- 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

- Algorithm

- PACT'02

## What is required ?

- Unroll amount selection
- Code generation

- Algorithm

- PACT'02

## Assumptions

- Array subscript expressions are linear functions of loop index variables
- No reuse of registers within an iteration of the transformed loop
- Registers allocated for caching data are live throughout the loop body
- No data reuse across iterations of the transformed loop
- Only loop independent reuse opportunities are exploited

- Algorithm

- PACT'02

## Unroll Amount Selection: Optimization Goal

- Algorithm

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

- PACT'02

## Reuse in Scalar vs. Superword Register

**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]

- Algorithm

- PACT'02

## Register Requirement Analysis

**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 !

- Algorithm

- 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], ... |

- Algorithm

- SWS(SuperWord Size): Number of data elements that fit in a superword register

- PACT'02

## Unroll Amount Selection

**Unroll Amount Selection**

- Search for 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.

- Algorithm

- 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 scalar memory accesses

- Algorithm

- PACT'02

## Packing in Registers

- p

- temp1

- p

- replicate(a, 0)

- p = shift_and_load(p, temp1)

- w = *((float *)&a + 0);
- x = *((float *)&b + 0);
- y = *((float *)&c + 0);
- z = *((float *)&d + 0);
- *((float *)&p + 0) = w;
- *((float *)&p + 1) = x;
- *((float *)&p + 2) = y;
- *((float *)&p + 3) = z;

- temp1 = replicate(a, 0);
- temp2 = replicate(b, 0);
- temp3 = replicate(c, 0);
- temp4 = replicate(d, 0);
- p = shift_and_load(p, temp1);
- p = shift_and_load(p, temp2);
- p = shift_and_load(p, temp3);
- p = shift_and_load(p, temp4);

- Packing through memory

- Packing in registers

- In some cases, data must be packed into a superword register.
- Alignment, non-unit stride array references
-  Packing through memory is expensive.  Packing in superword registers

- Algorithm

- PACT'02

## Packing in Registers

- p

- temp2

- p

- replicate(a, 0)

- p = shift_and_load(p, temp2)

- w = *((float *)&a + 0);
- x = *((float *)&b + 0);
- y = *((float *)&c + 0);
- z = *((float *)&d + 0);
- *((float *)&p + 0) = w;
- *((float *)&p + 1) = x;
- *((float *)&p + 2) = y;
- *((float *)&p + 3) = z;

- temp1 = replicate(a, 0);
- temp2 = replicate(b, 0);
- temp3 = replicate(c, 0);
- temp4 = replicate(d, 0);
- p = shift_and_load(p, temp1);
- p = shift_and_load(p, temp2);
- p = shift_and_load(p, temp3);
- p = shift_and_load(p, temp4);

- Packing through memory

- Packing in registers

- In some cases, data must be packed into a superword register.
- Alignment, non-unit stride array references
-  Packing through memory is expensive.  Packing in superword registers

- Algorithm

- PACT'02

## Packing in Registers

- p

- temp3

- p

- replicate(a, 0)

- p = shift_and_load(p, temp3)

- w = *((float *)&a + 0);
- x = *((float *)&b + 0);
- y = *((float *)&c + 0);
- z = *((float *)&d + 0);
- *((float *)&p + 0) = w;
- *((float *)&p + 1) = x;
- *((float *)&p + 2) = y;
- *((float *)&p + 3) = z;

- temp1 = replicate(a, 0);
- temp2 = replicate(b, 0);
- temp3 = replicate(c, 0);
- temp4 = replicate(d, 0);
- p = shift_and_load(p, temp1);
- p = shift_and_load(p, temp2);
- p = shift_and_load(p, temp3);
- p = shift_and_load(p, temp4);

- Packing through memory

- Packing in registers

- In some cases, data must be packed into a superword register.
- Alignment, non-unit stride array references
-  Packing through memory is expensive.  Packing in superword registers

- Algorithm

- PACT'02

## Packing in Registers

- p

- temp4

- p

- replicate(a, 0)

- p = shift_and_load(p, temp4)

- w = *((float *)&a + 0);
- x = *((float *)&b + 0);
- y = *((float *)&c + 0);
- z = *((float *)&d + 0);
- *((float *)&p + 0) = w;
- *((float *)&p + 1) = x;
- *((float *)&p + 2) = y;
- *((float *)&p + 3) = z;

- temp1 = replicate(a, 0);
- temp2 = replicate(b, 0);
- temp3 = replicate(c, 0);
- temp4 = replicate(d, 0);
- p = shift_and_load(p, temp1);
- p = shift_and_load(p, temp2);
- p = shift_and_load(p, temp3);
- p = shift_and_load(p, temp4);

- Packing through memory

- Packing in registers

- In some cases, data must be packed into a superword register.
- Alignment, non-unit stride array references
-  Packing through memory is expensive.  Packing in superword registers

- Algorithm

- PACT'02

## Experimental Flow

- Packing in registers

**Experimental Flow**

- Macintosh G4

- Superword extended gcc

- G4 executable

- C/ Fortran program

- Unroll-and-Jam

- MIT-SLP

- Superword instruction
-  extended C program

- Experiment

- Identify data reuse

- Data dependence analysis

- Select unroll amounts

- Register requirement analysis

- PACT'02

## Reduction in Dynamic Memory Accesses

- Vector Mem. Acc. Removed(%)

- Scalar Mem. Acc. Removed(%)

- Experiment

- PACT'02

## Speedup Breakdown

- Experiment

- PACT'02

## Related Research

- Conclusion

| Locality in Scalar Registers | Superword-Level Parallelism | Locality in caches |
| --- | --- | --- |
| Wolf(92),
Carr and Kennedy(94),
Jimenez(99) | Cheong and Lam(97),
Larsen and Amarasinghe(00),
Sreraman and Govindarajan(00),
Commercial products
  - Code Warrior 7
  - Vast/AltiVec
  - Intel C compiler | Wolfe(89),
Ferrante et al(91),
Lam et al(91),
Wolf(92),
Esseghir(93),
Temam et al(93,95),
Carr et al(94), 
Coleman and McKinley(95),
Gosh et al(97,98),
Chame and Moon(99),
Rivera and Tseng(99),
Sarkar and Megiddo(00),
Chatterjee(01), ... |
| Scalar registers that do not have spatial locality | No data locality at superword register level |  Conflict misses
 Simpler storage management |

- PACT'02

## Conclusion

- An algorithm for compiler-controlled caching in a superword register file
- Optimizations
- Superword Replacement, Packing in Registers
- Speedups over SLP from 1.3 to 2.8X
- Compatible and complementary with locality optimizations for cache

- PACT'02

## Scalar vs. Superword Replacement

- Background

- PACT'02

## Branch-And-Bound Search

- The size of search space for ‘fir’ : 629
- The largest search space was for ‘image correlation’
-  29356
- Took 0.34 seconds

- Search

- PACT'02

## Algorithm Implementation

- Implementation

- Scc
- Perfect
- Swldep
- Swl
- Annun
- Tile
- Rulb
- Unroller

- Osort
- Align
- Rvlse
- S2c
- Doctor
- Rmsma.pl
- Regpack.pl

- MIT-SLP

- C / Fortran Program

- Superword instruction
- Extended C program

- PACT'02

## Superword Instruction Extended C Program: An Example

- Implementation

- int A[100], B[100], C[100];
- main(){
- 	vector signed int sv1;
- 	vector signed int sv2;
- 	vector signed int sv3;
- 	sv1 = vec_ld(0, A);
- 	sv2 = vec_ld(0, B);
- 	sv3 = vec_add(sv1, sv2);
- 	vec_st(sv3, 0, C);
- }

- PACT'02

## Reduction in Dynamic Memory Accesses

- Experiment

- Vector+Scalar Mem. Acc. Removed(%)

- PACT'02