# Presentation: 928237

## Compiler Techniques To Exploit DIVA Features 

- Jaewook Shin

- Apr. 13. 2004

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

**DIVA (Data IntensiVe Architecture)**

- 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

- PACT'02

## Multimedia Extensions

- Additions to all major ISAs
- SIMD operations

- PACT'02

## Using Multimedia Extensions

- Library calls and inline assembly
- Difficult to program
- Not portable
- Different extensions to the same ISA
- MMX and SSE
- SSE vs. 3DNow!
- Need automatic compilation

- PACT'02

## Vector Compilation

- Pros:
- Successful for vector computers
- Large body of research
- Cons:
- Involved transformations
- Targets loop nests

- PACT'02

## Superword Level Parallelism (SLP)

- Small amount of parallelism
- Typically 2 to 8-way
- Exists within basic blocks
- Uncovered with a simple analysis
- Independent isomorphic operations
- New paradigm

- PACT'02

## 1.  Independent ALU Ops

**R = R + XR * 1.08327**
**G = G + XG * 1.89234**
**B = B + XB * 1.29835**

- PACT'02

## 2.  Adjacent Memory References

**R = R + X[i+0]**
**G = G + X[i+1]**
**B = B + X[i+2]**

- PACT'02

## Exploiting SLP with SIMD Execution

- Benefit:
- Multiple ALU ops  One SIMD op
- Multiple ld/st ops  One wide mem op
- Cost:
- Packing and unpacking
- Reshuffling within a register

- PACT'02

## Packing/Unpacking Costs

- Packing source operands
- Unpacking destination operands

**A = f()**
**B = g()**

**C = A + 2**
**D = B + 3**

**E = C / 5**
**F = D * 7**

**C   A   2**
**D   B   3**

**=   +**

- PACT'02

## SLP Extraction Algorithm

- Identify adjacent memory references

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Identify adjacent memory references

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Follow def-use chains

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Follow def-use chains

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Follow use-def chains

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Follow use-def chains

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## SLP Extraction Algorithm

- Follow use-def chains

**A = X[i+0]**
**C = E * 3**
**B = X[i+1]**
**H = C – A**
**D = F * 5**
**J = D - B**

- PACT'02

## Evaluating SLP Compiler

- SLP compiler implemented in SUIF
- Tested on two benchmark suites
- SPEC95fp
- Multimedia kernels
- Performance measured two ways:
- Compared to vector parallelism
- Speedup on AltiVec

- PACT'02

## SLP vs. Vector Parallelism

- PACT'02

## Speedup on AltiVec

**6.7**

- PACT'02

## SLP vs. Vector Parallelism

- Extracted with a simple analysis
- SLP is fine grain  basic blocks
- Superset of vector parallelism
- Unrolling transforms VP to SLP
- Handles partially vectorizable loops

- PACT'02

## SLP vs. Vector Parallelism

- }

*Basic block*

- PACT'02

## SLP vs. Vector Parallelism

*Iterations*

- PACT'02

## SLP vs. ILP

- Subset of instruction level parallelism
- SIMD hardware is simpler
- Lack of heavily ported register files
- SIMD instructions are more compact
- Reduces instruction fetch bandwidth

- PACT'02

## SLP and ILP

- SLP & ILP can be exploited together
- Many architectures can already do this
- SLP & ILP may compete
- Occurs when parallelism is scarce
- Unroll the loop more times
- When ILP is due to loop level parallelism

- PACT'02

## SLP: Conclusions

- Multimedia architectures abundant
- Need automatic compilation
- SLP is the right paradigm
- 20% non-vectorizable in SPEC95fp
- SLP extraction successful
- Simple, local analysis
- Provides speedups from 1.24 – 6.70
- Found SLP in general-purpose codes
- “Exploiting Superword Level Parallelism with Multimedia Instruction Sets” by Samuel Larsen and Saman Amarasinghe (PLDI’00)

- 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

- 256 bits

- 32

- DIVA

- 128 bits

- 32

- AltiVec

- ...

- ...

- PACT'02

## Scalar vs. Superword Replacement

- Identifies array references to the same memory 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

## Unroll Amount Selection: Optimization Goal

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

- PACT'02

## Register Requirement Analysis

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

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

- 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

- Identify data reuse

- Data dependence analysis

- Select unroll amounts

- Register requirement analysis

- PACT'02

## Speedup Breakdown

- PACT'02

## CCC: Conclusion

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

- PACT'02

## PMA: Motivation

- Increasing number of embedded systems are employing DRAM.
- DRAM access time is a significant fraction of memory latency.
- Embedded DRAM Systems: DRAM access time
- Conventional Systems: L1 + L2 + System bus + Off-chip interface + DRAM access time
- DRAMs support a faster access mode when there is spatial locality (page mode).
- User or compiler must expose opportunities for page mode accesses to memory controller.

- PACT'02

## DRAM Access Modes

- DRAMs are organized as a matrix
- Random mode accesses: select row + select column
- Selected row is brought into the open row buffer.
- Page mode accesses
- Access to words in the current open row
- Access time is roughly 3 times faster.

- row
- select

- column
- select

- open-row
- buffer

- DRAM

- PACT'02

## Statement Reordering

- Improve spatial locality at DRAM page level
- Group together accesses to same page

- Statements reordered

- for(i=0;i<32;i++)
-    for(j=0;j<32;j+=2)
-       for(k=0;k<32;k++)
-          load A[i][k]
-          load A[i][k]
-          load B[k][j]
-          load B[k][j+1]
-          load C[i][j]
-          load C[i][j+1]
-                ...
-          store C[i][j]
-          store C[i][j+1]

- PACT'02

## Algorithm For Automatically Exploiting Page Mode Accesses

- Select a loop to unroll
- Goal: Reduce # of random mode accesses of the loop nest
- Determine unroll amount
- Large enough to fully expose page mode opportunities
- Small enough to avoid register spill
- Apply transformations
- Unroll-and-jam
- Statement reordering

- PACT'02

## Selecting A Loop To Unroll

- For each loop *l*
- Verify legality of code transformations
- Compute unroll amount that maximize page mode opportunities
- Compute random mode accesses of loop nest when *l* is unrolled
- Choose the loop with smallest # of random mode accesses

- PACT'02

## Computing Unroll Amounts

- Minimum unroll amount *X**l* that maximizes spatial locality at the page level for loop *l*:
- Where
- 	P is the page size
- 	A is a set of array references in loop nest
*a *is an array reference variant in the lowest dimension with respect to* l*
*T(a)* is type size of *a*
*C(a, l)* is the coefficient of the index variable* l* in the lowest dimension subscript of *a*

- PACT'02

## Computing Unroll Amounts (cont.)

- Example 1:
*P* = 32 bytes
- A = { a, b }
- T(a) = 4 bytes, T(b) = 8 bytes
- C(a, i) = 1, C(b, i) = 1
- for(i=0; i<1024; i++)
*	**	**   *load a[i]
- 		   load b[i]

- a[i]

- a[i+1]

- a[i+2]

- a[i+3]

- b[i]

- b[i+1]

- b[i+2]

- b[i+3]

- page boundary

- page boundary

- b[i+4]

- b[i+5]

- b[i+6]

- b[i+7]

- page boundary

- higher address

- lower address

- random mode

- page mode

- PACT'02

## Computing Unroll Amounts (cont.)

- Example 2:
*P* = 32 bytes
- A = { a, b }
- T(a) = 4 bytes, T(b) = 8 bytes
- C(a, i) = 2, C(b, i) = 1
- for(i=0; i<1024; i++)
*	**	**   *load a[2i]
- 		   load b[i]

- a[2i]

- a[2i+2]

- a[2i+4]

- a[2i+6]

- b[i]

- b[i+1]

- b[i+2]

- b[i+3]

- page boundary

- higher address

- lower address

- page boundary

- random mode

- page mode

- PACT'02

## Selecting A Loop With Smallest # Of Random Mode Accesses

- For each loop *l*, compute # of random mode accesses.
- Group references into uniformly generated sets
- Ex:  G1 = { B[i], B[i+1], B[i+8], ...}, G2 = { C[i+3], C[i+5] }, ...
- Assuming the unrolled copies of references will be reordered,
- # random mode accesses = # pages accessed
- where                 is the footprint size in number of pages
- Choose a loop *l** *with the smallest *R**l** *

- PACT'02

## Controlling Register Pressure

- Adjust unroll amount so that # of registers used is less than or equal to # of registers available
- Compute register requirement for loop nest
- Ex:  For an array reference *B[i] *and an unroll amount* X**i**,*
- 	where *T(B[i])* is the type size of B[i], *W* is the register width.
- The total number of registers required (*TNR*) can be derived for all groups of uniformly generated sets.
- If TNR is greater than # of available registers, reduce the unroll amount.

- PACT'02

## Experimental Flow

- C program

- Parallelization (SLP)

-  Select a loop to unroll
-  Compute unroll amounts
-  Control register pressure
-  Unroll-and-jam

- Compiler controlled caching

- Statement reordering

- SLP
- version

- gcc

- Simulator

- Superword
- Extended C

- PACT'02

## Simulation Parameters

| Parameters | Value | Unit |
| --- | --- | --- |
| Random-mode latency | 12 | Cycles |
| Page-mode latency | 4 | Cycles |
| Page size | 256 | Bytes |

-  Based on the IBM Cu-11 embedded DRAM specs

- PACT'02

## Percentage of Page Mode Accesses

- PACT'02

## Speedup Breakdown

- PACT'02

## PMA: Conclusion

- A compiler algorithm to exploit DRAM page mode in embedded DRAM systems
- Speedups
- Statement reordering: 1.04 ~ 1.16 (PMA over CCC version)
- Overall: 1.25~2.19 (PMA over SLP version)
- Implementation issues
- Conflict between the goals of exploiting page mode and ILP
- Controlling register pressure
- Exploiting page mode will be more important.
- Increasing number of embedded DRAM systems

- PACT'02

## Compiler Techniques To Exploit DIVA Features 

- Thank you !

## Optimizing Program Performance

- To achieve the best speedup:
- Maximize parallelization
- Minimize packing/unpacking
- Many packing possibilities
- Worst case: *n *ops  *n! *configurations
- Different cost/benefit for each choice

- PACT'02

## Observation 1:Packing Costs can be Amortized

**A = B + C**
**D = E + F**

**Observation 1:****Packing Costs can be Amortized**

- Use packed result operands

**G = A - H**
**I = D - J**

- PACT'02

## Observation 1:Packing Costs can be Amortized

**Observation 1:****Packing Costs can be Amortized**

- Use packed result operands
- Share packed source operands

**A = B + C**
**D = E + F**

**G = B + H**
**I = E + J**

**A = B + C**
**D = E + F**

**G = A - H**
**I = D - J**

- PACT'02

## Observation 2: Adjacent Memory is Key

- Large potential performance gains
- Eliminate ld/str instructions
- Reduce memory bandwidth
- Few packing possibilities
- Only one ordering exploits pre-packing

- PACT'02

## Unroll-and-jam

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

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

- 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

## Reduction in Dynamic Memory Accesses

- Vector Mem. Acc. Removed(%)

- Scalar Mem. Acc. Removed(%)

- PACT'02

## Simplifying Assumptions

- Affine array subscript expressions
- Only array references are reordered.
- Lowest dimension of array objects are aligned to page boundaries.
- Array objects are aligned to page boundaries.
- Lowest dimension sizes are multiples of a page size.
- Compiler backend does not reorder memory accesses.
- Hardware supports a single open-row buffer.

- PACT'02

## Sorting Addresses

- for(i=2; i<130; i+=4)
-     load A[i]
-     load A[i+2]
-     load A[i+1]
-     load A[i+3]
-         ...

- for(i=2; i<130; i+=4)
-     load A[i]
-     load A[i+1]
-     load A[i+2]
-     load A[i+3]
-         ...

- page boundary

- higher address

- lower address

- random mode

- page mode

- Unsorted

- Sorted

- PACT'02