# Presentation: 661713

## A Compiler Algorithm for Exploiting Page-Mode Memory Access in Embedded-DRAM Devices

- MSP4

*Jaewook Shin*, Jacqueline Chame and Mary Hall

- November 18, 2002

## Overview

- Motivation
- Background
- Unroll-and-jam
- Statement reordering
- Algorithm
- Selecting a loop to unroll
- Controlling register pressure
- Sorting addresses
- Experiments
- Algorithm implemented in SUIF
- 4 kernels
- Simulation results
- Conclusion

- PACT'02

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

- Motivation

- row
- select

- column
- select

- open-row
- buffer

- DRAM

- PACT'02

## Unroll-and-jam

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

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

- Original loop nest

- Background

- j-loop is unrolled

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

- Inner loops are fused together

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

- Spatial reuse

- Temporal reuse

- PACT'02

## Statement Reordering

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

- Background

- 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

- Algorithm

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

- Algorithm

- 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

- Algorithm

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

- Algorithm

- PACT'02

## Computing Unroll Amount (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]

- Algorithm

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

- Algorithm

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

- Algorithm

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

- Algorithm

- PACT'02

## Sorting Addresses

- Algorithm

- 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

## Experimental Methodology

- Algorithm developed for DIVA processing-in-memory devices
- Implemented in SUIF compiler
- Demonstrated on four kernels
- Matrix-Matrix Multiplication (MMM)
- Vector-Matrix Multiplication (VMM)
- Finite Impulse Response filter (FIR)
- Yellow Under Violet (YUV)
- Executed on DIVA simulator

- Experiment

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

**DIVA (Data IntensiVe Architecture)**

- Experiment

- 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

- Experiment

- Superword
- Extended C

- PACT'02

## Simulation Parameters

- Experiment

| 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

- Experiment

- PACT'02

## Speedup Breakdown

- Experiment

- PACT'02

## Related Research

- Moyer(’93)
- Developed a compiler technique called “access reordering”
- Panda et al.(’98)
- Developed a series of techniques to exploit page mode in high-level synthesis
- McKee et al.(’00)
- Designed Stream Memory Controller (SMC) for access ordering by hardware

- Conclusion

- PACT'02

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