# Presentation: 667252

## Vectorization for Modern Architectures 

- Jaewook Shin

## The Fastest Computer: BG/L

- PACT'02

## Overview

- Introduction
- What-is / why SIMD ?
- Multimedia extensions
- Automatic parallelization
- Vectorization for vector machines
- Superword-Level Parallelization
- Issues
- Conclusion

- PACT'02

## Multiple Levels of Parallelism

**Multiple Levels of Parallelism**

- Computers

- Processors

- Threads

- Instructions

- Data

- Grid

- BG/L

- Netscape

- ILP

- SIMD

- PACT'02

## Scalar vs. SIMD Operation

**Scalar: add r1,r2,r3**

**1**

**2**

**+**

**3**

**r3**

**r2**

**r1**

- PACT'02

## Why SIMD ?

- More parallelism
- When parallelism is abundant
- SIMD in addition to ILP
- Simple design
- Replicated functional units
- Small die area
- No heavily ported register files
- Die area:
- MAX-2(HP): 0.1%
- VIS(Sun): 3.0%
- Must be explicitly exposed to the hardware
- By the compiler or by the programmer

- PACT'02

## Multimedia / Scientific Applications

- Image
- Graphics : 3D games, movies
- Image recognition
- Video encoding/decoding : JPEG, MPEG4
- Sound
- Encoding/decoding: IP phone, MP3
- Speech recognition
- Digital signal processing: Cell phones
- Scientific applications
- Double precision GEneral Matrix-Matrix multiplication (DGEMM)
- Y[] = a*X[] + Y[] (SAXPY)

- PACT'02

## Characteristics of Multimedia Applications

- Regular data access pattern
- Data items are contiguous in memory
- Short data types
- 8, 16, 32 bits
- Data streaming through a series of processing stages
- Some *temporal reuse* for such data streams
- Sometimes ...
- Many constants
- Short iteration counts
- Requires *saturation arithmetic*

- PACT'02

## Multimedia Extensions

- At the core of multimedia extensions
- SIMD parallelism
- Variable-sized data fields:
- 	Vector length = register width / type size

**WIDE UNIT**

- PACT'02

## Multimedia Extension (cont.)

- Additions to all major ISAs
- Alignment
- AltiVec: Only aligned memory accesses
- SSE: Unaligned memory accesses are more expensive.
- Not all operations are directly supported:
- AltiVec: No division, no 32-bit integer muliplication

| PowerPC | AltiVec | 128 |
| --- | --- | --- |
| Intel | MMX/SSE | 64/128 |
| AMD | 3DNOW! | 64 |
| Sun | VIS | 64 |
| HP | MAX2 | 64 |
| MIPS V | MDMX | 64 |
| Alpha | MVI | 64 |

- PACT'02

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

**PIM: DIVA (Data IntensiVe Architecture)**

- 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

## Super Computer: BlueGene/L PowerPC 440 Double FPU

**Super Computer: BlueGene/L PowerPC 440 Double FPU**

- PACT'02

## Programming Multimedia Extensions

- Language extension
- Programming interface similar to function call
- C: built-in functions, Fortran: intrinsics
- Most native compilers support their own multimedia extensions
- AltiVec: dst = vec_add(src1, src2);
- SSE2: dst = _mm_add_ps(src1, src2);
- GCC: -faltivec, -msse2
- BG/L: dst = __fpadd(src1, src2);
- No Standard !

- PACT'02

## Programming Multimedia Extensions (cont.)

- 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

## Overview

- Introduction
- What-is / why SIMD ?
- Multimedia extensions
- Automatic parallelization
- Vectorization for vector machines
- Superword-Level Parallelization*
- Issues
- Alignment
- Strided memory access

- PACT'02

## Automatic Parallelization by Compiler

- Two approaches
- Targeting loops
- Vector machines
- Vectorization
- Targeting basic blocks
- Multimedia extensions
- Superword-Level Parallelization

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

**compiler**

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

- PACT'02

## Parallelizing Compilers

- Research compilers
- SLP compiler (MIT, Sam Larsen)
- Vectorizing SUIF Compiler (U. Toronto, Derek De Vries)
- ...
- Commercial compilers
- Intel compiler
- XL compilers for BG/L (IBM)
- GCC 4.0.1
- VAST/AltiVec (Crescent Bay Software)
- ...
- Most compilers for multimedia extensions are based on conventional vectorization techniques.

- PACT'02

## Vectorization

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

- PACT'02

## Vectorization (cont.)

**for (i=0; i<64; i++){**
**   ****Rb = b[i];**
**   ****Rc = c[i];**
**   ****Ra = Rb + Rc;**
**   ****a[i] = Ra;**
**}**

**for (i=0; i<64; i+=4)**
**   ****for (j=0; j<4; j++){**
**      ****Rb = b[i+j];**
**      ****Rc = c[i+j];**
**      ****Ra = Rb + Rc;**
**      ****a[i+j] = Ra;**
**   ****}**

**for (i=0; i<64; i+=4){**
**   ****for (j=0; j<4; j++)**
**      ****Rb[j] = b[i+j];**
**   ****for (j=0; j<4; j++)**
**      ****Rc[j] = c[i+j];**
**   ****for (j=0; j<4; j++)**
**      ****Ra[j] = Rb[i+j]+Rc[i+j];**
**   ****for (j=0; j<4; j++)**
**      ****a[i+j] = Ra[j];**
**}**

**vector int Va, Vb, Vc;**
**for (i=0; i<64; i+=4){**
**   ****Vb = b[i:i+3];**
**   ****Vc = c[i:i+3];**
**   ****Va = Vb + Vc;**
**   ****a[i:i+3] = Va;**
**}**

- PACT'02

## Superword-Level Parallelism (SLP)

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

|  | SLP
(Multimedia Extensions) | Vector Parallelism |
| --- | --- | --- |
| Strided Memory Access ? | NO | YES |
| Vector Length | ≤32 elements | ≥64 elements |
| Instruction Latency | ~1 | 1 per element |
| Aligned Memory Access ? | YES | NO |
| Exists within ? | Basic block | Loop |

- 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

## 3.  Vectorizable Loops

**   ****A[i+0] = A[i+0] + B[i+0]**

**3.  Vectorizable Loops**

- PACT'02

## 3.  Vectorizable Loops

**for (i=0; i<100; i+=4)**
**   ****A[i+0] = A[i+0] + B[i+0]**

**A[i+1] = A[i+1] + B[i+1]**
**A[i+2] = A[i+2] + B[i+2]**
**A[i+3] = A[i+3] + B[i+3]**

- PACT'02

## 4.  Partially Vectorizable Loops

**for (i=0; i<16; i+=1)**
**   ****L = A[i+0] – B[i+0]**
**   ****D = D + abs(L)**

- PACT'02

## 4.  Partially Vectorizable Loops

**for (i=0; i<16; i+=2)**
**   ****L = A[i+0] – B[i+0]**
**   ****D = D + abs(L)**

**L = A[i+1] – B[i+1]**
**D = D + abs(L)**

- PACT'02

## Exploiting SLP with SIMD Execution

- Benefit:
- Multiple ALU ops  One SIMD op
- Multiple ld/st ops  One wide mem op

- 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

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

- PACT'02

## Packing/Unpacking Costs

**Packing/Unpacking Costs**

- Packing source operands

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

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

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

**=   +**

- 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

## Optimizing Program Performance

- To achieve the best speedup:
- Maximize parallelization
- Minimize packing/unpacking

- PACT'02

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

## Large potential performance gains
Eliminate ld/str instructions

Few packing possibilities
Only one ordering exploits pre-packing

- Eliminate ld/str instructions
- Few packing possibilities
- Only one ordering exploits pre-packing

**Observation 2:****Adjacent Memory is Key**

- 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

## SLP vs. Vector Parallelism

- }

*Basic block*

- PACT'02

## SLP vs. Vector Parallelism

*Iterations*

- 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

**Dynamic SUIF instructions eliminated**

- PACT'02

## SLP vs. ILP

- Subset of instruction level parallelism
- SIMD hardware is simpler
- 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
- 	ex) MPC7450:
- 	2 vector integer units, 1 vector FPU, 1 vector permute unit
- Mix well with scalar instructions
- SLP & ILP may compete
- Occurs when parallelism is scarce
- Unroll the loop more times
- When ILP is due to loop level parallelism

- PACT'02

## Issues

- Alignment
- Strided memory access
- Cache misses
- Control flow
- Profitability model
- True data dependence
- Function calls
- Inlined assembly code
- Indirect memory accesses
- Loop bounds varying during run time
- ...

- PACT'02

## Overall Improvements Over Scalar (small)

- PACT'02

## Conclusion

- SIMD parallelism cannot be replaced by other types of parallelism.
- SLP suits the requirements of modern SIMD architectures better than the conventional technique.
- Research opportunities to exploit SIMD parallelism

- PACT'02

## Backup Slides

- Alignment
- Strided memory access
- More on vectorization

- PACT'02

## Alignment

- Most multimedia extensions require aligned memory accesses.
- Aligned memory access ?
- A memory access is aligned to 16 byte boundary if the address is multiple of 16.
- Ex) For 16 byte memory accesses in AltiVec, the last 4 bits of the address are ignored.

- PACT'02

## Alignment Code Generation

- Aligned memory access
- The address is always a multiple of 16 bytes
- Just one superword load or store instruction

**float a[64];**
**for (i=0; i<64; i+=4)**
**   ****Va = a[i:i+3];**

- ...

- PACT'02

## Alignment Code Generation (cont.)

- Misaligned memory access
- The address is always non-zero constant offset away from the 16 byte boundaries.
- Static alignment: For a misaligned load, issue two adjacent aligned loads followed by a merge.

**float a[64];**
**for (i=0; i<60; i+=4)**
**   ****Va = a[i+2:i+5];**

- ...

- PACT'02

## Alignment Code Generation (cont.)

- Unaligned memory access
- The offset from 16 byte boundaries is varying or not enough information is available.
- Dynamic alignment: The merging point is computed during run time.

**float a[64];**
**for (i=0; i<60; i++)**
**   ****Va = a[i:i+3];**

- ...

- PACT'02

## Alignment Analysis

- Iterative data flow analysis

**2n+0**

**2n+1**

**4n+0**

**4n+2**

**4n+1**

**4n+3**

**8n+0**

**8n+4**

**8n+2**

**8n+6**

**8n+1**

**8n+5**

**8n+3**

**8n+7**

****

- 8n+0

- 4n+2

**n+0**

- PACT'02

## Transfer Functions

- a = gcd(a1, a2, |b1-b2|)
- b = b1 % a

- a = gcd(a1, a2)
- b = (b1+b2) % a

- a = gcd(a1, a2)
- b = (b1 – b2) % a

- a = gcd(a1a2, a1b2, a2b1, C)
- b = (b1b2) % a

**Meet**

**Add**

**Subtract**

**Multiply**

- PACT'02

## Strided Memory Accesses:Packing Through Memory

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

- w

- x

- y

- z

- Memory

- Registers

**p**

- PACT'02

## Strided Memory Accesses: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

- temp1

- PACT'02

## Strided Memory Accesses:Packing in Registers

- p

- temp2

- p

- replicate(b, 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

- temp2

- PACT'02

## Strided Memory Accesses:Packing in Registers

- p

- temp3

- p

- replicate(c, 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

- temp3

- PACT'02

## Strided Memory Accesses:Packing in Registers

- p

- temp4

- p

- replicate(d, 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

- temp4

- PACT'02

## Strided Memory Accesses:Power of 2 Interleaved Data

- Fully interleaved data require δlogδ steps, where δ is interleave factor.
- Dorit Nuzman et. al., PLDI ‘06

**Strided Memory Accesses:****Power of 2 Interleaved Data**

- src1

- src2

- dst

- PACT'02

## Vectorization: Dependence Issues

- True cyclic dependences of distance smaller than the vector length can prevent vectorization.

**for (i=4; i<64; i++){**
**   ****Ra = a[i-2];**
**   ****Rb = b[i];**
**   ****Ra = Ra + Rb;**
**   ****a[i] = Ra;**
**}**

**for (i=4; i<64; i+=4){**
**   ****Va = a[i-2:i+1];**
**   ****Vb = b[i:i+3];**
**   ****Va = Va + Vb;**
**   ****a[i:i+3] = Va;**
**}**

**for (i=4; i<64; i+=2){**
**   ****Va = a[i-2:i-1];**
**   ****Vb = b[i:i+1];**
**   ****Va = Va + Vb;**
**   ****a[i:i+1] = Va;**
**}**

- PACT'02

## Vectorization: Involved Transformations

- Loop interchange:
- Vectorize one of the outer loops
- Choose loop with larger iteration count
- Loop distribution:
- Partial vectorization
- Node split:
- Break cyclic dependences with an anti-dependence
- And more...
- Loop skewing, loop peeling, Index set splitting, reduction recognition, ...

- PACT'02

## References

- S. Larsen and S. Amarasinghe, *Exploiting Superword Level Parallelism with Multimedia Instruction Sets*, PLDI 2000
- S. Larsen, E. Witchel, and S. Amarasinghe, Increasing and Detecting Memory Address Congruence, PACT 2002
- J. Shin, M. Hall and J. Chame, *Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures*, PACT 2002
- D. Nuzman, I. Rosen, A. Zaks, Auto-Vectorization of Interleaved Data for SIMD, PLDI 2006

- PACT'02