# Presentation: 725229

## Introducing Control Flow into Vectorized Code

***PACT’07: September. 19. 2007***

## Outline

- Introduction
- Automatic vectorization
- Vectorization in the presence of control flow
- Nested control flow in vector codes
- Experimental results
- Conclusion

## The Fastest Computer: BG/L

| Rank | Manufacturer | Family | Processor | Rmax | Site | #Proc |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | IBM (‘05) | BG/L | PowerPC 440 | 280 | LLNL | 131072 |
| 2 | Cray (’06) | XT3 | Opteron Dual Core 2.6 | 101.7 | ORNL | 23016 |
| 3 | Cray (’06) | XT3 | Opteron Dual Core 2.4 | 101.4 | Sandia | 26544 |
| 4 | IBM (’05) | BG/L | PowerPC 440 | 91 | IBM | 40960 |
| 5 | IBM (’07) | BG/L | PowerPC 440 | 82 | BNL | 36864 |

- * Taken from top500.org

## Levels of Parallelism

***Levels of Parallelism***

- ...

- ...

- ...

## Scalar vs. SIMD Operation

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

**1**

**2**

**+**

**3**

**r3**

**r2**

**r1**

## Automatic Vectorization: ICC, GCC, XLC, ...

- for (i=0; i<1024; i++)
-     C[i] = A[i]+B[i];

- for (i=0; i<1024; i+=4)
-     C[i:i+3] = A[i:i+3]+B[i:i+3];

## Issues

- Control flow
- Vectorization in the presence of complex control flow
- Overhead of executing all control paths
- Function calls
- Function calls are not vectorized.
- Function calls prevent vectorization.
- Alignment
- Aligned: 0, 16, 32, ...
- Misaligned: 4, 20, 36, ...
- Unaligned: 0, 8, 16, ...
- ETC
- Nonunit strides
- Dependences
- ...

- 2004,**2007**

- 2005

## Vectorization in the Presence of Control Flow (2005)

- for (i=0; i<1024; i++){
-   if (A[i]>0)
-     C[i]= B[i];
-   else
-     D[i]=D[i-1];
- }

- for (i=0; i<1024; i++){
-   P=A[i]>0;
-   NP=!P;
-   C[i]= B[i];        <P>
-   D[i]=D[i-1];     <NP>
- }

- for (i=0; i<1024; i++){
-   vP=A[i:i+3]>(0,0,0,0);
-   vNP=vec_not(vP);
-   C[i:i+3]=B[i:i+3];        <vP>
-   (NP1,NP2,NP3,NP4)=vNP;
-   D[i]=D[i-1];               <NP1>
-   D[i+1]=D[i];              <NP2>
-   D[i+2]=D[i+1];          <NP3>
-   D[i+3]=D[i+2];          <NP4>
- }

- for (i=0; i<1024; i++){
-   vP=A[i:i+3]>(0,0,0,0);
-   vNP=vec_not(vP);
-   C[i:i+3]=vec_sel(C[i:i+3],B[i:i+3],vP);
-   (NP1,NP2,NP3,NP4)=vNP;
-   D[i]=D[i-1];               <NP1>
-   D[i+1]=D[i];              <NP2>
-   D[i+2]=D[i+1];          <NP3>
-   D[i+3]=D[i+2];          <NP4>
- }

- for (i=0; i<1024; i++){
-   vP=A[i:i+3]>(0,0,0,0);
-   vNP=vec_not(vP);
-   C[i:i+3]=vec_sel(C[i:i+3],B[i:i+3],vP);
-   (NP1,NP2,NP3,NP4)=vNP;
-   if(NP1)D[i]=D[i-1];
-   if(NP2)D[i+1]=D[i];
-   if(NP3)D[i+2]=D[i+1];
-   if(NP4)D[i+3]=D[i+2];
- }

**If-conversion**

**vectorization**

**Remove**
**vector**
**predicates**

**Remove**
**scalar**
**predicates**

**IN**

**OUT**

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

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

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

## BOSCC by Example (2004)

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

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

**vectorization**

**Bypass**
**vector**
**instructions**

## Existing Approach: single-level BOSCCs

***Existing Approach: single-level BOSCCs***

- Scalar
- CFG

- Vector
- CFG

## Our Approach: nesting BOSCCs (2007)

- Scalar
- CFG

- Vector
- CFG

## Key Idea: Inverse-Implies

- Definition: A inverse-implies B iff ¬A   ¬B.
- A region of instructions guarded by one vector predicate (B) can be nested inside another (A) if  ¬A   ¬B.

- branch-on-none(A) LA;
- 	...
- LA:
- branch-on-none(B) LB;
- 	...
- LB:

- branch-on-none(A) LA;
-    ...BOSCC region A...
-    ...BOSCC region B...
- LA:

- branch-on-none(A) LA;
-    ...BOSCC region A...
- branch-on-none(B) LB;
-    ...BOSCC region B...
- LB:
- LA:

- Nest BOSCCs!

- Nest BOSCC regions!

## ¬A  ¬B if ...

- A is an ancestor* of B: All conditions used to compute B are derived directly or indirectly from A.
- B implies* A: A subset of conditions used to compute B are used to compute A.

- * Ph.D. dissertation, Scott Mahlke, 1995

**if(b[i]<0){**
**  ****b[i]=0;**
**  ****if(a[i]>9){**
**    ****c[i]=1;**
**    ****goto L1;**
**  ****}**
**}**
**else{**
**  ****b[i]=1;**
**  ****if(a[i]>0){**
**    ****L1;**
**    ****c[i]=2;**
**  ****}**
**}**

- p2

- C code

- CFG

- Inverse-Implies Graph

- T

- F

- T

- T

- F

- F

**P2 is an ancestor of p5.**

**P5 implies p6.**

## Algorithm

- Collect the instructions guarded by the same or the descendant predicate so that they are textually contiguous.
- Post-DFS order of II-graph
- Insert BOSCCs
- Reverse post-DFS order of II-graph
- Profitability of a BOSCC based on conditional probability of the nested predicate being true with respect to the nesting predicate

- branch-on-none(A) LA;
-    ...BOSCC region A...
- branch-on-none(B) LB;
-    ...BOSCC region B...
- LB:
- LA:

- P(B|A)=P(A∩B)/P(A)
-       =P(B)/P(A)
- ex)P(A)=10%,P(B)=10%
-    P(B|A)=100%

## Nesting Over Single-Level BOSCCs

## vec_any_*

**if (a[i] > 0){**
**    ...**
**}**

**pT = vec_cmpgt(a[i:i+3],(0,0,0,0));**
**if(vec_any_ne(pT,(0,0,0,0))){**
**  ...**
**}**

- Previous approach

- Our
- approach

**if(****vec_any_gt****(a[i:i+3],(0,0,0,0))){**
**  ****pT = vec_cmpgt(a[i:i+3],(0,0,0,0));**
**  ...**
**}**

## vec_any_* Over vec_any_ne Only

## Predicate Restoring vs. Predicate Preserving

## Predicate Restoring Over Predicate Preserving

## Overall Speedups Over the Scalar Baseline

**Notes:**
1.3(dist1)~19.79(chroma)

## Conclusion

- By nesting BOSCCs,
- we can bypass multiple predicate regions by a single BOSCC and,
- even the associated BOSCCs are bypassed.
- Experiments on 14 benchmarks show the speedups of 1~1.94 over the previous BOSCC generation technique.
- A significant portion of the vectorization overhead in the presence of arbitrarily complex control flow is eliminated.
- Future work
- Whole function vectorization
- Look for more applications

## Questions ?

## Why SIMD ?

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

- Low cost

- High performance

## Programming SIMD Units

- Language extension: No Standard !
- Programming interface similar to function call
- C: built-in functions, Fortran: intrinsics
- Most native compilers support SIMD intrinsics of the machine
*AltiVec: dst = vec_add(src1, src2);*
*SSE2: dst = _mm_add_ps(src1, src2);*
*BG/L: dst = __fpadd(src1, src2);*
- GCC: -faltivec, -msse2
- Library calls: not portable (as is) !
- BG/L: MASS, MASSV, ESSL
- Ex: y = sqrt(x) vs. vsqrt(Y,X,500)
-  **Need automatic tools.**

## Approach 1: Loop-Level Automatic Vectorization

- for (i=0; i<1024; i++)
-     C[i] = A[i]+B[i];

- for (i=0; i<1024; i+=4)
-   for (ii=0; ii<4; ii++)
-     C[i+ii] = A[i+ii]+B[i+ii];

- for (i=0; i<1024; i+=4){
-   for (ii=0; ii<4; ii++) tA[ii] = A[i+ii];
-   for (ii=0; ii<4; ii++) tB[ii] = B[i+ii];
-   for (ii=0; ii<4; ii++) tC[ii] = tA[ii]+ tB[ii];
-   for (ii=0; ii<4; ii++) C[i+ii] = tC[ii];
- }

- for (i=0; i<1024; i+=4){
-   vA = vec_ld(&A[i]);
-   vB = vec_ld(&B[i]);
-   vC = vec_add(vA,vB);
-   vec_st(vC,&C[i]);
- }

- Strip
- mining

- Loop
- distribution

- Code
- generation

## Approach 2: Basic Block-Level Automatic Vectorization

- for (i=0; i<1024; i++)
-     C[i] = A[i]+B[i];

- for (i=0; i<1024; i+=4){
-   sA0 = A[i+0];
-   sB0 = B[i+0];
-   sC0 = sA0+sB0;
-   C[i+0]=sC0;
-   ...
-   sA3 = A[i+3];
-   sB3 = B[i+3];
-   sC3 = sA3+sB3;
-   C[i+3]=sC3;
- }

- for (i=0; i<1024; i+=4){
-   (sA0,sA1,sA2,sA3)=A[i:i+3];
-   (sB0,sB1,sB2,sB3)=B[i:i+3];
-   (sC0,sC1,sC2,sC3)=
-   (sA0,sA1,sA2,sA3)+(sB0,sB1,sB2,sB3);
-   C[i:i+3] = (sC0,sC1,sC2,sC3);
- }

- for (i=0; i<1024; i+=4){
-   vA = vec_ld(&A[i]);
-   vB = vec_ld(&B[i]);
-   vC = vec_add(vA,vB);
-   vec_st(vC,&C[i]);
- }

- unrolling

- Packing
- Isomorphic
- statements

- Code
- generation

## Inverse Implies Graph of logf

***Inverse Implies Graph of logf***