Parallel programming with models

of computation

Prof. Dr.-Ing. Jeronimo Castrillon

Tunis, Tunisia. December 2-4, 2015

Chair for Compiler Construction

Georg-Schumann-Str. 7A, 2 OG

[email protected]

Lecture 2: Compilers and task-based

programming models

Parallel programming with models of computation

Prof. Dr.-Ing. Jeronimo Castrillon

Tunis, Tunisia. December 2-4, 2015

Chair for Compiler Construction

Georg-Schumann-Str. 7A, 2 OG

[email protected]

Agenda

09:00 AM

12:30 PM

14:00 PM

LB1-I

HO-I

LB2-I

break

LB2-I (cont)

break

LB2-II

HO-II

LB3-I

break

LB3-II

HO-III

LB4/Q&A

LB1-I

17:30 PM

Recall: Lecture 1

q Why parallelism?

q Programming models

q Basics of computer architectures (including parallel ones)

q Fundamentals of parallelism (concurrency, types, Amdahl/Gustafson, …)

q Example of standard programming models (MPI, Pthreads, OpenMP)

Recall: Lecture 1 (2)

q Pthreads/OpenMP – Shared memory

q Easy to introduce races (when/how to use private?)

q Easy to introduce locks

q MPI: Message Passing Interface – Distributed memory

q Large API: 152!

q Easy to introduce deadlocks

q In this lecture:

http://nerds-

central.blogspot.de/2011/11/atomicinteger-

volatile-synchronized-and.html

q Why not stick to sequential programming? – Limits of compilers

q Easier models – Task-based programming

Contents

q Basics of compilers

q Auto-parallelizing compilers

q Task-based programming models

Basics of compilers

Compiler phases

Frontend

Middle-end

Backend

q IR: Intermediate representation

q Frontend: Legal code è IR

q (Typ.) Target-independent

q Middle-end: IR è Optimized IR

q (Typ.) Target-independent

q Backend: IR è Target code

q Target-dependent

Java

Fortran

Pentium

Sparc

MIPS

Java

Fortran

Pentium

Sparc

MIPS

Adapted from: A. Appel: Modern Compiler Implementation in C.

Front-end

q Deals with the language syntax and semantics to produce an interanal model

(i.e., the IR)

while (y < z)

{

int x = a + b;

y += x;

Frontend

}

Middle-end

q Further analysis (e.g., dataflow) and model transformation

Middle-

end

Backend

q Target-specific optimization and transformations

Backend

Linear IR: Three-address code (TAC)

q “High-level assembly”

q Each operation has at most 3 operands

q x = y op z

q Representation used by many compilers

q Example: LLVM

int main()

{

int a, b, c;

a = 2; b = 3;c = 5;

c += (a*b) >> a;

c += foo(a);

return 0;

}

define i32 @main() #0 {

t2 = t1 >> 2

t3 = t2 – 7

t4 = t2 + t3

%1 = alloca i32, align 4

%a = alloca i32, align 4

%b = alloca i32, align 4

%c = alloca i32, align 4

store i32 0, i32* %1

store i32 2, i32* %a, align 4

store i32 3, i32* %b, align 4

store i32 5, i32* %c, align 4

%2 = load i32* %a, align 4

%3 = load i32* %b, align 4

%4 = mul nsw i32 %2, %3

%5 = load i32* %a, align 4

%6 = ashr i32 %4, %5

%7 = load i32* %c, align 4

%8 = add nsw i32 %7, %6

store i32 %8, i32* %c, align 4

%9 = load i32* %a, align 4

%10 = call i32 @foo(i32 %9)

%11 = load i32* %c, align 4

%12 = add nsw i32 %11, %10

store i32 %12, i32* %c, align 4

ret i32 0}

Int: 32 bits

c +=

(a*b) >> a

Calling

conventions

Flow analysis: Intuition

q Better representation of program facts not directly visible in the TAC IR

q Branching, loops, definition of variables, …

è Collected information is key for optimizations

x = 10 * 2

_t1 = x < z

if _t1 goto L1

u = y + z

goto L2:

L1:

u = y – z

L2:

z = u + x

x = 20

x = 10 * 2

_t1 = x < z

if _t1 goto L1

Control flow

graph

Basic block

u = y + z

u = y - z

z = u + 20

z = u + x

Data-flow analysis

q Collect information about the possible set of values at various points in a

program for performing sound optimizations and code generation

q Examples:

q Where is a variable defined?

q Could some statement use a variable definition?

q Principle

out[p1]

out[p2]

Join function

in[n]

n (stmt,BB,...)

in[n] = joinp

out[n] = fn(in[n])

pred(n)(out[p])

Transfer function

out[n]

Program point

Data-flow analysis: Principle of operation

q Data-flow equations

in[n] = joinp

out[n] = fn(in[n])

pred(n)(out[p])

q Typical join and transfer functions:

in[n] =

out[p]

pred(n)

out[n] = gen[n]

(in[n]

[

kill[n])

(efficient implementation via

bit-vectors)

II -

out[p1]

out[p2]

in[n]

n (stmt,BB,...)

out[n]

q in[n]

data coming directly before n

q out[n] data outgoing directly after n

q gen[n] data produced by n

q kill[n] data destroyed by n

Solving the data-flow system of equations

q The equations for each statement (or

basic-block) depend on each other

è System of equations

q Iterative solution

q Initialize the in-sets

q Iteratively compute the out-sets,

update the in-sets, until no changes

are observed

q Termination? Nice application of

theory of semi-lattices

in[n1] =

out[p]

out[n1] = gen[n1]

[

in[n2] =

pred(n1)

(in[n1]

kill[n1])

out[p]

out[n2] = gen[n2]

pred(n2)

(in[n2]

kill[n2])

[

…

II -

Dataflow analysis: Example

q Information collected stored in use-def or def-use chains

q Needed if computation is mapped to another core

1: a = 5

2: c = 1

3: L1: if (a > c) goto L2;

{1}

{2,4}

4: c = c + c;

5: goto L1;

6: L2: a = c – a;

7: c = 0;

Control and dataflow: Example

Source: Leupers, Sheng, Castrillon. “Software Compilation Techniques for MPSoCs”. Springer 2010

Limits of dataflow analysis

q Conservative: Cannot produce wrong code

q For sound analysis: Suppose all paths can be taken (“flow insesitive”)

q Pointer access “*p = z” could potentially modify every variable x

q Analyze uses of the address operator “&”

q If not possible to reduce the set of affected variables suppose all can be modified

q Point-to and alias analysis are difficult!

Dependence analysis

q A dependency between two statements s1 and s2

indicates that s2 cannot be executed before s1

q Read after write (RAW, true dependence): s1

defines a variable, then s2 reads it (see

reachable definitions)

s1: a = b + c;

s2: d = a * x;

q Write after write (WAW, output dependence): s1

defines a variable, then s2 defines it again

q Write after read (WAR, anti-dependence): s1 uses

a variable, then s2 defines it

s1: a = b - c;

s2: a = b * x;

s1: x = a - c;

s2: a = b * y;

q Control dependency: s1 controls whether or not s2

is executed

s1: if (x) goto L1

...

s2: L1: a = b * y;

Dependence analysis in arrays

s1: A[i] = b - c;

...

s2: x = A[k] + d;

Whether or not there is RAW

dependency depends on i and k

q In general: analysis needed to reason about potential parallel schedules

q In arrays

q Impossible in the general case

q Possible, but difficult for special cases, i.e., afine index expressions

Dependence analysis in arrays: Example

q Example

s0: for (i=2; i<=4; i++) {

s1: b[i] = a[3*i-5] + 2;

s2: a[2*i+1] = 100;}

Dare to put

#openmp parallel for?

q Is there a dependency between the statements within an iteration?

è Solve 3i-5 = 2i+1 è i = 6, but 6 ∉ [2,4] è No dependency!

q What about across iterations?

è We look for an integer solution to 3i1-5 = 2i2+1

è Pairs (i1 = 2k, i2 = 3k-3) are valid solutions

è Solution k = 2: (4,3) ∈ [2,4] è RAW on a[7] (written in it. 3, read in it. 4)

Middle-end: Compiler optimization

q Optimizations: Enabled by analysis (control, dataflow)

q Classical optimizations

q Improve performance on single cores

q Expose more instruction-level parallelism (ILP)

q Newer optimizations

q Vectorize, use SIMD instructions

q Extract DLP and TLP (more on this later)

Optimizations: Examples

q Loop invariants and semantic preserving transformations

for (i=0; i < k; i++)

{

z = x/y;

a = z * A[i];

}

z = x/y;

for (i=0; i < k; i++)

{

a = z * A[i];

}

What if y = 0 and

k <= 0?

q Improving ILP: Loop unrolling

for (i=0; i < N; i++) {

C[i] = A[i]*B[i];

}

for (i=1; i < N; i+=2) {

C[i-1] = A[i-1]*B[i-1];

C[i] = A[i]*B[i];

}

if (N%2) C[N-1] = A[N-1]*B[N-1];

Backend (recall)

q Target dependent

Backend

Backend phases

Optimized IR

Code

selection

asm

∞ regs

allocation

asm

k regs

Scheduling

Machine code

q Code selection: Uses pattern matching

q Map IR code to assembly instructions (assume fixed code shape, i.e., IR is “optimal”)

q Combine operations, use addressing modes (assume infinite registers)

q Register allocation

q Assign registers to variables (change storage pattern, i.e., inserts load/stores)

q Scheduling

q Reorder operations to hide latencies, assume a fixed program (set of operations)

Backend-phases: Relation to Multicore-compilers

q Both require a machine model

q Code selection

q Cost of operations (instructions)

q Resource usage (reservation tables in VLIWs)

q Register allocation

q How to intelligently map data: Goes beyond register file (caches, scratchpads, …)

q Scheduling (and mapping)

q Which functional unit executes what and when

q Works on dependence graphs (similar to task graphs – see later)

Scheduling: Basics

Def. Scheduling is the reordering of instructions for a given target architecture

(constraints) to increase performance

q Scheduling in a compiler shares common principles with scheduling/mapping in

dataflow/task graphs

q Scheduling with resource constraints is NP complete: Need heuristics

q Basics

q Dependence graphs

q ASAP/ALAP

q List scheduling

q SW pipelining

Static (compile-time) vs. Dynamic (run-time)

q Static (compile-time)

q Avoids extra hardware (e.g., pipeline-interlocks & out-of-order execution): VLIW vs.

Superscalar

q Can observe the entire program

q Has more time to optimize the schedule

q Dynamic (run-time)

q More precise: Some dependencies only known at run-time

A[i] = x;

= A[k];

ST [r1],r2

LD r3,[r4]

Static: i = k?

Dynamic: r1 = r4?

Data dependency graph

Def. Given a basic-block BB, its dependency graph is an edge-weighted

directed acyclic graph G = (V,E,W) where nodes represent the instructions of BB

and there is an edge e = (u,v) ∈ E if due to dependencies, u has to execute

before v. The edge-weight we ∈ W models the latency of the architecture.

q Possible schedule: Any topological sort of the graph (more on this later)

q WAR dependency: Depending on target architecture, usually means “u cannot

execute after v”

Data dependency graph: Example

t0 = t1 + t2

t1 = t0 + t1

t3 = t2 + t4

t0 = t1 + t0

t5 = t3 + t4

t6 = t2 + t7

t0 = t1 + t2

t1 = t0 + t1

t3 = t2 + t4

t0 = t1 + t0

t3 = t2 + t4

t5 = t3 + t4

t6 = t2 + t7

Adapted from: http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/

Possible schedules: Topological sort

t3 = t2 + t4

t0 = t1 + t2

t6 = t2 + t7

t5 = t3 + t4

t1 = t0 + t1

t0 = t1 + t0

t3 = t2 + t4

t0 = t1 + t2

t5 = t3 + t4

t3 = t2 + t4

t0 = t1 + t2

t6 = t2 + t7

t1 = t0 + t1

t0 = t1 + t0

t5 = t3 + t4

t6 = t2 + t7

t0 = t1 + t0

Which one is better?

Heuristics, e.g., schedule

first instructions with many

outgoing edges

Adding edge weights: RISC processor

t3 = t2 + t4

t0 = t1 + t2

t6 = t2 + t7

t5 = t3 + t4

t1 = t0 + t1

t0 = t1 + t0

Option 1

10 11 12 13 14 15 16

t3 = t2 + t4 IF ID EX MM WB

t5 = t3 + t4

t0 = t1 + t2

t1 = t0 + t1

t0 = t1 + t0

t6 = t2 + t7

IF ID EX MM WB

Adding edge weights: RISC processor

t3 = t2 + t4

t0 = t1 + t2

t6 = t2 + t7

t5 = t3 + t4

t1 = t0 + t1

t0 = t1 + t0

Option 2

10 11 12 13 14 15 16

t0 = t1 + t2

IF ID EX MM WB

t3 = t2 + t4

IF ID EX MM WB

Saved cycles

t6 = t2 + t7

t1 = t0 + t1

t5 = t3 + t4

t0 = t1 + t0

IF ID EX MM WB

Basic algorithms: ASAP

q ASAP: As soon as possible – schedule the earliest ignoring resource constraints

q Intuition: The earliest time depends on the predecessors and the latencies

Def. Given a dependency graph G = (V,E,W), ASAP(v) denotes the earliest

scheduling time for every v ∈ V and is defined as:

• ASAP(v) = 1 if pred(v) = ∅

• ASAP(v) = maxu∈pred(v)(ASAP(u) + w(u,v))

q Relevance: The ASAP time represents an absolute lower bound

ASAP: Example (edge weights: 1)

t = 1

t = 2

t = 3

t = 4

t = 5

Basic algorithms: ALAP

q ALAP: As late as possible – schedule the latest ignoring resource constraints

while keeping same duration as ASAP

Def. Given a dependency graph G = (V,E,W), the critical path length (Lc) is the

length of the paths in the graph with maximum edge weights

Def. Given a dependency graph G = (V,E,W), ALAP(v) for every v ∈ V is

defined as:

• ALAP(v) = Lc if succ(v) = ∅

• ALAP(v) = minu∈succ(v)(ALAP(u) – w(v,u))

ASAP: Example (edge weights: 1)

t = 1

t = 2

t = 3

t = 4

t = 5

ALAP: Example (edge weights: 1)

t = 1

t = 2

t = 3

t = 4

t = 5

ASAP & ALAP

q Theoretical optimum: Serves to restrict search

q Critical path: All nodes for which ASAP(v) = ALAP(v)

q Mobility: ALAP(v) – ASAP(v)

q If every node v is scheduled within [ASAP(v), ALAP(v)] è Optimal schedule

q ASAP & ALAP: Ignore resource constraints

q Requires 4 ALUs!

List scheduling

q Widespread heuristic algorithm for local scheduling, i.e, within basic-blocks

q Simple and efficient

q Idea: Build dependency graph and repeatedly

q Get ordered ready set of statements, i.e., statements whose predecessors are

already scheduled

q Select a node from the ready set (according to priority)

q Insert the node in the partial schedule (in the best possible slot)

Algorithm

Proc ListSched(Graph G)

S = empty schedule

O = ∅

while O ≠ V

// Ordered nodes

R = ReadySet(G) // R = {v ∈ V; v ∉ O, pred(v)⊆O}

v = SelectNode(R) // Heuristic selection

S = Insert(S,v) // Insert v in the earliest possible time

O = O ∪{v}

return S

List scheduling: Select heuristics

q In case |R| > 1: Good selection of a node to schedule is crucial

q Most famous ones

q Select node with the most successors (increases options)

q Select node on the dynamic critical path

q Many others, although less used

q Complexity: Dominated by the construction of the dependency graph O(|V|2)

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

+/-

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

Example

q Assumptions

q ISA with 2 multipliers and 2 ALU (+/-)

q Instructions take 1 cycle

q Select heuristic: Dynamic critical path

Time

t = 1

t = 2

t = 3

t = 4

t = 5

t = 6

+/-

VLIW example: TI C6201

int dotp(short a[], short b[])

{ int sum0, sum1, i;

sum0 = sum1 = 0;

for (i = 0; i < 100; i += 2) {

sum0 += a[i] * b[i];

sum1 += a[i+1] * b[i+1];

}

return sum0 + sum1;

}

Registers A0 - A15

Registers B0 - B15

D DL

D S1

L 1

D S1 S2

DS1

DDATA_I1

(load data)

DDATA_I2

(load data)

DDATA_O1

(store data)

DADR1

(address)

DADR2

(address)

DDATA_O2

(store data)

Cross Paths

40-bit Write Paths (8 MSBs)

40-bit Read Paths/Store Paths

LOAD

sum0

sum1

Dependency

graph

VLIW example: TI C6201 (2)

LOAD

Registers A0 - A15

Registers B0 - B15

sum0

sum1

LDH .D2 ++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2 +B4(2),B5 || LDH .D1 +A4(2),A6

NOP 3

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP

ADD .L1 A6,A0,A0

|| ADD .S1 A5,A3,A3

D DL

D S1

L 1

D S1 S2

DS1

DDATA_I1

(load data)

DDATA_I2

(load data)

DDATA_O1

(store data)

DADR1

(address)

DADR2

(address)

DDATA_O2

(store data)

Cross Paths

40-bit Write Paths (8 MSBs)

40-bit Read Paths/Store Paths

Using max. 2 parallel loads

3 more cycles delay before

Multiply

SW Pipelining

q Equivalent of instruction pipelining

Instructions

for statements in a loop

q Widely used for VLIW

q SW Pipeline for a loop

for (...)

}

t0 = t1 + t2

IF ID EX MM WB

t3 = t2 + t4

IF ID EX MM WB

t6 = t2 + t7

IF ID EX MM WB

Loop-carried

dependency

ILP Pipeline

Iteration

Iteration 1

Iteration 2

A B C D

Iteration 3

Iteration 4

Different iterations

at same time

A B C D

Principle

q Analyze data dependencies inside a loop

q Unroll loop body to eliminate loop-carried dependencies (conceptually)

q Find kernel with operations that repeat

B A

C B A

D C B A

D C B

D C

B A

C B A

D C B A

D C B

D C

Loop prolog

Loop kernel

Loop epilog

Problem overview

q Given a graph with operations,

q A description of instructions from the target architecture

q A set of reservation tables

q Find the kernel for software pipelining

q Which operations belong to kernel?

q How long is the kernel?

q Then: Generate code accordingly

Example: TI C6201 (recall)

LOAD

Registers A0 - A15

Registers B0 - B15

sum0

sum1

D DL

D S1

L 1

D S1 S2

DS1

DDATA_I1

(load data)

DDATA_I2

(load data)

DDATA_O1

(store data)

DADR1

(address)

DADR2

(address)

DDATA_O2

(store data)

Cross Paths

40-bit Write Paths (8 MSBs)

40-bit Read Paths/Store Paths

int dotp(short a[], short b[])

{ int sum0, sum1, i;

sum0 = sum1 = 0;

for (i = 0; i < 100; i += 2) {

sum0 += a[i] * b[i];

sum1 += a[i+1] * b[i+1];

}

return sum0 + sum1;

LDH .D2 ++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2 +B4(2),B5 || LDH .D1 +A4(2),A6

NOP 3

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1 A6,A0,A0

|| ADD .S1 A5,A3,A3

}57

Example: Adding control

++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2

LDH .D2 *+B4(2),B5

NOP 3

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1

A6,A0,A0

|| LDH .D1 *+A4(2),A6

|| ADD .S1 A5,A3,A3

L: LDH .D2 ++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2 *+B4(2),B5

SUB .L2 B0,1,B0

[B0] B .S1 L

|| LDH .D1 *+A4(2),A6

NOP 1

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1 A6,A0,A0 || ADD .S1 A5,A3,A3

Reservation

table: 1

Iteration

LDH LDH

MPY MPY

New iteration can

be scheduled here

SUB

ADD

Example: Finding kernel

++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2

LDH .D2 *+B4(2),B5

NOP 3

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1

A6,A0,A0

|| LDH .D1 *+A4(2),A6

|| ADD .S1 A5,A3,A3

L: LDH .D2 ++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2 *+B4(2),B5

SUB .L2 B0,1,B0

[B0] B .S1 L

|| LDH .D1 *+A4(2),A6

NOP 1

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1 A6,A0,A0 || ADD .S1 A5,A3,A3

Reservation

table: Fully

unrolled

LDH LDH LDH LDH LDH LDH LDH LDH LDH

MPY

Kernel repeats

from cycle 7

onwards

SUB

ADD

SUB

ADD

Prolog

Example: Code generation

++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2

LDH .D2 *+B4(2),B5

NOP 3

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1

A6,A0,A0

|| LDH .D1 *+A4(2),A6

|| ADD .S1 A5,A3,A3

SW pipelining: 4.5x speedup

L: LDH .D2 ++B4(4),B6 || LDH .D1 ++A4(4),A5

LDH .D2 *+B4(2),B5

SUB .L2 B0,1,B0

[B0] B .S1 L

|| LDH .D1 *+A4(2),A6

NOP 1

MPY .M1X B6,A5,A5

MPY .M1X B5,A6,A6

NOP 1

ADD .L1 A6,A0,A0 || ADD .S1 A5,A3,A3

Jump executed after 5 cycles è After

two iterations!

// Prolog

L3:

LDH LDH

MPY

ADD

SUB

ADD

ADD .L2 B6,B5,B5 || MPY .M2X B4,A0,B6 || [ B0] B .S1 L3

|| LDH .D2 +B7(2),B4 || LDH .D1 +A3(2),A0

ADD .L1 A5,A4,A4 || MPY .M1X B4,A0,A5 || [ B0] SUB .L2 B0,1,B0

|| LDH .D2 ++B7(4),B4 || LDH .D1 ++A3(4),A0

// Epilog

Algorithm sketch

q Optimal SW pipelining: NP complete è Heuristic

q Iterative modulo scheduling (Rau, 1994)

q Search for kernel of length ∆

q Start growing ∆ until it is possible to build a schedule

q Starting point for ∆: Obtaining “minimal ∆” also NP complete

q Use estimation based on the target architecture and the properties of the

dependency graph

Modulo scheduling

q Why modulo scheduling

q When trying to fit a computation

within a kernel of length ∆, move

statements across iterations

q Example

§ 2-slot VLIW

§ ∆ = 3

§ load delay: 4

Respect dependency: Schedule

addition after t > 5 cycles

è Place in kernel: t mod ∆

Slot 1

Fi = A[i]

Slot 1

Fi = A[i]

Slot 1

Fi = A[i]

Slot 2

Xi = Fi+...

✗

Slot 2

Xi-1 = Fi-1+…

Slot 2

Y = …

Xi-2 = Fi-2+…

Agenda

09:00 AM

12:30 PM

14:00 PM

LB1-I

HO-I

LB2-I

break

LB2-I (cont)

break

LB2-II

HO-II

LB3-I

break

LB3-II

HO-III

LB4/Q&A

LB1-I

17:30 PM

Auto-parallelizing compilers

Auto-parallelizing: The idea

Sequential

code

Compiler

Parallel code

(OpenMP, Pthreads,…)

q Keep sequential programming: It’s easy and widespread

q Let the compiler do all the work

q Analyze: instrument, profile, trace memory, estimate performance, …

q Parallelize: exploit locality, identify parallel regions, insert synchronization, …

q Generate correct code (deal with APIs complexity)

Analysis

q Instrumentation

q Insert code into application

q Collect information at runtime (profile, memory trace, …)

Analysis: Example

q Information collected after running instrumented application

Analysis: Memory traces

q Memory traces: Important for

q Dynamic dependence analysis: unsafe, but often more insightful than static analysis

q Locality analysis

Good temporal

and spatial

Bad temporal

Bad spatial

locality

Time

Analysis: Performance estimation

q To reason about parallel execution

q Execution of computation on multiple resources

q Costs of communication and synchronization

q Methods (some details in lecture 4)

q Table-based on IR

q Emulation of target-specific transformation at IR level

q Worst-case-execution time (WCET) analysis

Improving locality and extracting parallelism

q Locality

q Important for cache utilization

q Loop transformations (more on this below)

q Extracting parallelism

q Graph partitioning:

q Pattern matching: identify known parallel patterns (TLP, DLP, PLP, reduction, …)

identify threads working on “almost” different data sets

Metrics for partitioning

q Load distribution

q It does not make sense to create a thread that does almost nothing

q Synchronization

q Reduce the amount of waiting (related to a good load balance)

q Communication

q Should be small: Min ratio-cut in graphs

Parallelism patterns: Graphs and metrics

q Example TLP

q Estimated performance depends on the kind and location of the dependency

Parallelism patterns: Graphs and metrics (2)

q Similar for DLP and PLP

q DLP: Depends on the cost for spawning workers (e.g., fix OpenMP threads)

q PLP: Perform pipeline balancing

Example: Generating OpenMP

q EP: Application in the NAS parallel benchmark

q Autom...

Parallel Programming with Models of Computation

Parallel Programming with Models of Computation