# Presentation: 881548

## Vectorization for Modern Architectures (II)

- Jaewook Shin

## Want more ?

- Control flow
- SLP in the presence of control flow
- Introducing control flow back
- Superword-Level Locality (SLL)

- 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

## One Approach

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

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

**Unpredicate**

- PACT'02

## Extend for Control Flow

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

**for (i=0; i<16; i+=4){**
**  ****pred = a[i:i+3] != (0, 0, 0, 0);**
**  ****old  = b[i:i+3];**
**  ****new  = old + (1, 1, 1, 1);**
**  ****b[i:i+3] = ****SELECT****(old, new, pred);**
**}**

- Overhead:
**Both control flow paths are always executed !**

- PACT'02

## An Optimization:Branch-On-Superword-Condition-Code

**for (i=0; i<16; i+=4){**
**  ****pred = a[i:i+3] != (0, 0, 0, 0);**
**  ****branch-on-none****(pred) L1;**
**    ****old  = b[i:i+3];**
**    ****new  = old + (1, 1, 1, 1);**
**    ****b[i:i+3] = SELECT(old, new, pred);**
**  ****L1****:**
**}**

- PACT'02

## Branch-On-Superword-Condition-Code (BOSCC)

**branch-on-none****( src  ) <target label>;**

**branch-on-all****( src  ) <target label>;**

- PACT'02

## An Optimization:Branch-On-Superword-Condition-Code

**Overhead **can be** reduced **for some input data sets ...

**for (i=0; i<16; i+=4){**
**  ****pred = a[i:i+3] != (0, 0, 0, 0);**
**  ****branch-on-none****(pred) L1;**
**    ****old  = b[i:i+3];**
**    ****new  = old + (1, 1, 1, 1);**
**    ****b[i:i+3] = SELECT(old, new, pred);**
**  ****L1****:**
**}**

- bypass

- ... but BOSCC can **increase overhead**
- because we introduce the branch instruction.

- PACT'02

## Understanding BOSCC profitability

- Consider the following kernel :

**for (i=0; i<datasize; i++){**
**  ****temp = A[i];**
**  ****if (temp == B[i])**
**    ****C[i] = temp + D[i];**
**}**

- PACT'02

## Sensitivity to True Density

- Vector Length = 4, Data fit in L1 cache.

- PACT'02

## Exponential Decrease in Taken BOSCC

- A branch-on-none is taken when all fields in a superword are false.
- Given a true density D,
- the probability for one field to be false is 1-D.
- The probability for four fields in a superword to be false at the same time is (1-D)^4.
- A branch cost is highest when its percentage to be taken is around 50 %.
- The percentage of taken BOSCC when vector length is 4 is 50 % when scalar true density is 16 %.

- PACT'02

## An Observation: By Using BOSCCs ...

- Assume a simple of model of parallelization where
-  one scalar instruction is mapped to one parallel instruction, and
- the cost of BOSCCs is zero.
- We guarantee that each parallel instruction is executed once iff the corresponding scalar instruction is executed at least once for  vector length iterations.
- This means that parallelized codes are always faster than the scalar original.

- 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

## Loop Skewing

- Reshape iteration space to uncover parallelism
- DO I = 1, 8
- 	DO J = 1, 4
- 			(0,1)
- S:		A(I,J) = A(I-1,J) + A(I,J-1)
- 			(1,0)
- 	ENDDO
- ENDDO

- PACT'02

## Loop Skewing

**J**

**I**

- 1, 1 = 0, 1 + 1, 0
- 1, 2 = 0, 2 + 1, 1
- 1, 3 = 0, 3 + 1, 2
- 1, 4 = 0, 4 + 1, 3
- 2, 1 = 1, 1 + 2, 0
- 2, 2 = 1, 2 + 2, 1
- 2, 3 = 1, 3 + 2, 2
- 2, 4 = 1, 4 + 2, 3
- 3, 1 = 2, 1 + 3, 0
- 3, 2 = 2, 2 + 3, 1
- 3, 3 = 2, 3 + 3, 2
- 3, 4 = 2, 4 + 3, 3
- 4, 1 = 3, 1 + 4, 0
- 4, 2 = 3, 2 + 4, 1
- ...

**Parallelism not apparent****.**

- PACT'02

## Loop Skewing:  j=I+J

- DO I = 1, N
- 	DO j = I+1, I+N
- S:		A(I,j-I) = A(I-1,j-I) + A(I,j-I-1)
- 	ENDDO
- ENDDO
***Loop interchange to..***
- DO j = 2, N+N
- 	DO I = max(1,j-N), min(N,j-1)
- S:		A(I,j-I) = A(I-1,j-I) + A(I,j-I-1)
- 	ENDDO
- ENDDO

- PACT'02

## Loop Skewing

- The accesses pattern to A changes as follows.

- I, J =I-1,J + I,J-1(I, K)
- ----  -----   ----- -----
- 1, 1 = 0, 1 + 1, 0 (1, 2)
- 1, 2 = 0, 2 + 1, 1 (1, 3)
- 2, 1 = 1, 1 + 2, 0 (2, 3)
- 1, 3 = 0, 3 + 1, 2 (1, 4)
- 2, 2 = 1, 2 + 2, 1 (2, 4)
- 3, 1 = 2, 1 + 3, 0 (3, 4)
- 1, 4 = 0, 4 + 1, 3 (1, 5)
- 2, 3 = 1, 3 + 2, 2 (2, 5)
- 3, 2 = 2, 2 + 3, 1 (3, 5)
- 4, 1 = 3, 1 + 4, 0 (4, 5)
- 2, 4 = 1, 4 + 2, 3 (2, 6)
- 3, 3 = 2, 3 + 3, 2 (3, 6)
- 4, 2 = 3, 2 + 4, 1 (4, 6)
- 5, 1 = 4, 1 + 5, 0 (5, 6)
- 3, 4 = 2, 4 + 3, 3 (3, 7)
- 4, 3 = 3, 3 + 4, 2 (4, 7)
- 5, 2 = 4, 2 + 5, 1 (5, 7)
- 	...

**I**

**j=2     3       4      5      6      7**

- PACT'02

## Loop Skewing

- Disadvantages:
- Varying vector length
- Not profitable if Nj is small
- If vector startup time is more than speedup time, this is not profitable
- Vector loop bounds must be recomputed on each iteration of outer loop
- Apply loop skewing if everything else fails

- PACT'02

## References

- J. Shin, M. Hall and J. *Chame, **Superword-Level Parallelism in the Presence of Control Flow*, CGO 2005
- J. Shin, M. Hall and J. Chame, *Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures*, PACT 2002
- J. Shin, J. Chame and M. Hall, *Evaluating Compiler Technology for Control-Flow Optimizations for Multimedia Extension*, MSP6, 2004

- PACT'02