# Presentation: 045449

## Superword-Level Parallelism in the Presence of Control Flow

- CGO’05

- Jaewook Shin
- Mary Hall
- Jacqueline Chame

- March 22 2005

## Multimedia Extension Architectures

- Multimedia applications are becoming increasingly important.
- Most microprocessors have multimedia extensions.
- SIMD parallelism
- Variable-sized data fields

- PACT'02

## Superword-Level Parallelism (SLP)

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

|  | SLP | Vector Parallelism |
| --- | --- | --- |
| Strided Memory Access ? | NO | YES |
| Vector Length | 32 elements | 64 elements |
| Instruction Latency | ~1 | 1 per element |
| Aligned Memory Access ? | YES | NO |

- Most compilers for multimedia extensions are based on conventional vectorization techniques.

- PACT'02

## SLP Compiler (Larsen & Amarasinghe)

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

**for (i=0; i<16; i+=4){**
** ****a[i+0] = b[i+0] + c[i+0];**
** ****a[i+1] = b[i+1] + c[i+1];**
** ****a[i+2] = b[i+2] + c[i+2];**
** ****a[i+3] = b[i+3] + c[i+3];**
**}**

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

- Unroll by 4

- Pack isomorphic statements

- 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

## Our 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(            )**

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

- PACT'02

## Algorithm

- If-conversion:
- Park and Schlansker’s RK-algorithm
- SELECT
- Insert the minimum number of SELECT instructions
- Use reaching definition based on predicate covering
- Unpredicate
- Try to reduce the number of conditional branches
- Use predicate covering

- PACT'02

## PHG represents relationships among predicates.

- Predicate Hierarchy Graph (PHG)

**pT1, pF1 = pset (c1); <TRUE>**

**...**

**pT2, pF2 = pset (c2); <TRUE>**

**...**

**pT3, pF3 = pset (c3); <pT1>**

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**...**

**...**

- PACT'02

## Predicate Covering

- A predicate *p* is covered by a set of predicates *G* if *p* = *true* *p’**G* such that *p’ = true*.

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**I1 <pF3>**
**I2 <pT3>**
**I3 <pT1>**

**pT3**

**pF3**

**G={}**

- Q: Predicate covering
- predecessors of I3 ?

**pT1**

**pT3****}**

**...**

**...**

**,****pF3****}**

**,pT1}**

- PACT'02

## SELECT Algorithm

**TRUE**

**pT1**

**pF1**

**pT2**

**pF2**

**pT3**

**pF3**

**T**

**F**

**T**

**T**

**F**

**F**

**d1: Va=V1; <pF3>**
**d2: Va=V2; <pT3>**
**u3: Vc=Va; <pT1>**

- SELECT is not necessary for the first reaching definition

**d1: Va=V1; **
**d2: Va=SELECT(Va,V2,pT3);**
**u3: Vc=Va; **

**...**

**...**

- PACT'02

## Predicate CFG Generator

- Find the predicate covering predecessors for each predicated instruction.

**I1 <pF3>**
**I2 <pT3>**
**I3 <pT1>**

**I1**

**I2**

**I3**

**if(pT1){**
**  ****if(pF3)**
**	****I1;**
**  ****else**
**	****I2;**
**  ****I3;**
**}**

- (a) predicated
- scalar code

- (b) CFG

- (c) code generated

- PACT'02

## Unpredicate Algorithm

- Schedule each instruction within an existing basic block where it is safe.
- If no such basic block exists, use ‘predicate CFG generator’.

**I1 <p>**
**I2 <****¬****p>**
**I3 <TRUE>**
**I4 <p>**
**I5 <****¬****p>**

**I1**

**I2**

**I3**

- (a) predicated
- scalar code

- (b) predicate CFG
- generator

- (c) unpredicate

**I4**

**I5**

**I1**
**I4**

**I2**
**I5**

**I3**

**p**

**p**

**p**

**¬****p**

**¬****p**

**¬****p**

**TRUE**

**TRUE**

- PACT'02

## Our Implementation

- superword
- level locality

- unroll

- alignment
- analysis

- remove superword
- predicates(SELECT)

- parallelize

- if-conversion

- remove scalar
- predicates (unpredicate)

- output
- C code

- original
- C code

- our previous work

- new for this paper

- superword
- replacement

- MIT SLP compiler

- PACT'02

## Applications

- Kernels
- Chroma: 	Chroma keying of two images
- Sobel: 		Sobel edge detection
- TM: 		Template Matching
- Max: 		Max value search
- transitive: 	Shortest path search
- Functions from UCLA MediaBench
- MPEG2-dist1: 		dist1 of MPEG2 encoder
- EPIC-unquantize: 	unquantize_image of unepic
- GSM-Calculation: 	Calculation_of_the_LTP_parameters of 				gsmencode
- Two data set sizes
- Large: Representative data set
- Small:  Isolates parallelization effects

- PACT'02

## Experimental Flow

- SLP
- compiler

- Control flow extension

- GCC – AltiVec extended

- PowerPC G4

- Original
- C code

- Baseline

- SLP

- SLP-CF

- PACT'02

## Overall Improvements: large data

- PACT'02

## Overall Improvements: small data

- PACT'02

## Related Research

- Vectorization techniques for conditionals
- Sreraman and Govindarajan(IJPP’00)
- Bik et. al.(IJPP’02)
- Architectures with SELECT
- Multimedia Extension Architectures: AltiVec
- Processing-In-Memory: DIVA
- Vector machines: Smith et. al.(ISCA’00)
- Phi-predication: Chuang et. al.(CGO’03)
- Requires scalar SELECT
- Predicate CFG generator: Mahlke(’96)

- PACT'02

## Conclusion

- Compiler system to exploit SLP in the presence of control flow
- Compiler algorithms to
- Minimum SELECTs
- Restore efficient control flow
- In an experiment with 5 kernels and 3 benchmarks, the performance improved by 1.97X ~ 15.07X.

- PACT'02

## Predicate Covering Predecessors

- A predicate ***p*** is covered by a set of predicates ***G*** if ***p*** = *true* ***p’******G*** such that ***p’**** = true*.
- Given a sequence of predicated instructions, Predicate covering predecessors of an instruction ***I ***guarded by a predicate*** ******p****** ***is
- The first set ***S*** of textually preceding instructions of ***I***
- The predicate set ***G*** of ***S*** cover the predicate ***p*** of ***I***
- For each instruction ***I’******S*** and its predicate ***p’******G, ***
***p’**** *is not covered by any subset of predicates guarding instructions between I’ and I
***P*** and ***p’*** are not mutually exclusive

- PACT'02

## Is PHG inaccurate ?

- PHG is said to be inaccurate and limited in representation.
- We use a subset of predicate analyses based on PHG.
- Predicate deposit type: only Conditional
- No false positive for the following properties
- Mutually exclusive
- Predicate covering
- Leads to possibly conservative but always correct code
- Predicate analyses can be replaced with any other predicate analysis system

- PACT'02

## Reverse If-Conversion (RIC) ?

- RIC assumes no operations are inserted nor removed during RIC.
-  Superword instructions are inserted and scalar instructions are removed in our case.
- RIC uses
*predicate define operations* to preserve control dependences
- implicit *predicate merge operations* to preserve control anti-dependence
-  The original CFG can be partially or totally removed in our case.

- PACT'02