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

Lecture 4: KPN programming flow

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]

Recall: Lecture 1--3

q The reason for parallelism, fundamentals and mainstream programming models

q Problems with compilers and task based programming models

q The formalisms of MoCs for parallel programming

q In this lecture

q An example of a tool flow for KPN (and its details)

KPNs – Recall

q Graph representation of applications

q Processes communicate only over FIFO buffers

q Good model for streaming applications

q Good match for signal processing & multi-media

q Stereo digital audio filter

fft_l

filter_l

ifft_l

src

sink

fft_r

filter_r

ifft_r

P n Tran sfo rmSd fTo K p n (D, S);

P n Tran sfo rmTo ArrayAccess(D,

C o l l ectC h an n el AccessR an ges(D,

S);

P ro p agateC h an n el AccessR an g es(D,

S);

P n StreamFacto ry

streamFacto ry(B as eP a th );

{

swi tch (tran sTarget)

case Tran sM VP :

P n Tran sfo rmTemp l ateIn st an ti at e(D,

S);

EraseP n P ro cessTemp l ate s(D);

P n P ri n tFo rM VP (D, S);

b reak;

case Tran sP th read :

P n Tran sfo rmP th read s(D, S, traces);

EraseP n Defs(D);

b reak;

case Tran sSystemC :

P ri n tFo rSystemC (D, S, traces,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sVP Utg:

P ri n tFo rVP Utg(D, S,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sVP Umap :

P ri n tFo rVP Umap (D, S,

strM ap p i n gFi l eName,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sIn val i d :

assert(fal se);

b reak;

}

#i n cl u d e "P n Tran sfo rm.h "

#i n cl u d e "P n TVP Utg.h "

#i n cl u d e "P n TVP Umap .h "

#i n cl u d e "cl an g/AST/ASTC o n tex t.h "

#i n cl u d e "P n StreamFacto ry.h "

u si n g n amesp ace

cl an g;

vo i d

cl an g::P n Tran sfo rm(Tran sT arg et

tran sTarget,

b o o l traces,

co n st std ::stri n g &

strM ap p i n gFi l eName,

ASTC o n text

&C tx,

{

!= Tran sIn val i d );

Sema &S, co n st

l l vm::sys::P ath &B aseP ath )

assert(tran sTarget

Tran sl ati o n Un i tDecl

*D =

C tx.getTran sl ati o n Un i tDecl();

P n Tran sfo rmSi zeo f(D, S);

P n Tran sfo rmTask(D,

swi tch (tran sTarget)

case Tran sSystemC :

S);

{

case Tran sVP Utg:

case Tran sVP Umap :

P n TC o p yi n g(D, S);

b reak;

d efau l t:

;

}

P n Tran sfo rmP th read s(D, S, traces);

EraseP n Defs(D);

b reak;

case Tran sSystemC :

P ri n tFo rSystemC (D, S, traces,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sVP Utg:

P ri n tFo rVP Utg(D, S,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sVP Umap :

P ri n tFo rVP Umap (D, S,

strM ap p i n gFi l eName,

streamFacto ry);

EraseP n Defs(D);

b reak;

case Tran sIn val i d :

assert(fal se);

b reak;

&B aseP ath )

{

!= Tran sIn val i d );

assert(tran sTarget

Tran sl ati o n Un i tDecl

*D =

C tx.getTran sl ati o n Un i tDecl();

P n Tran sfo rmSi zeo f(D, S);

P n Tran sfo rmTask(D,

swi tch (tran sTarget)

case Tran sSystemC :

case Tran sVP Utg:

case Tran sVP Umap :

S);

{

P n TC o p yi n g(D, S);

b reak;

d efau l t:

;

}

Programming flow: Overview

KPN Application

Architecture model

MEM

subsystem

DMAs,

sema-

phores

PMU

A15

VLIW DSP

L1,L2

NoC

Peripherals

Communication

support

HW queues

Network

Processor

Packet DMA

Analysis

Synthesis

Code generation

Non-functional

specification

Property models (timing,

energy, error, …)

PNargs_ifft_r.ID = 6U;

PNargs_ifft_r.PNchannel_freq_coef = filtered_coef_right

PNargs_ifft_r.PNnum_freq_coef = 0U;

PNargs_ifft_r.PNchannel_time_coef = sink_right

PNargs_ifft_r.channel = 1;

sink_left = IPCllmrf_open(3, 1, 1);

sink_right = IPCllmrf_open(7, 1, 1);

PNargs_sink.ID = 7U;

PNargs_sink.PNchannel_in_left = sink_left

PNargs_sink.PNnum_in_left = 0U;

PNargs_sink.PNchannel_in_right = sink_right

PNargs_sink.PNnum_in_right = 0U;

taskParams.arg0 = (xdc_UArg)&PNargs_src

taskParams.priority = 1;

ti_sysbios_knl_Task_create((ti_sysbios_knl_Task_FuncPtr

&taskParams, &eb);

glob_proc_cnt++;

hasProcess = 1;

taskParams.arg0 = (xdc_UArg)&PNargs_fft_l

taskParams.priority = 1;

ti_sysbios_knl_Task_create((ti_sysbios_knl_Task_FuncPtr

ft_Templ, &taskParams, &eb);

glob_proc_cnt++;

hasProcess = 1;

taskParams.arg0 = (xdc_UArg)&PNargs_ifft_r

taskParams.priority = 1;

ti_sysbios_knl_Task_create((ti_sysbios_knl_Task_FuncPtr

fft_Templ, &taskParams, &eb);

glob_proc_cnt++;

hasProcess = 1;

taskParams.arg0 = (xdc_UArg)&PNargs_sink

taskParams.priority = 1;

Language: C for process networks

q FIFO Channels

typedef struct { int i; double d; } my_struct_t;

__PNchannel my_struct_t S;

__PNchannel int A = {1, 2, 3}; / Initialization /

__PNchannel short C[2], D[2], F[2], G[2];

q Processes & networks

__PNkpn AudioAmp __PNin(short A[2]) __PNout(short B[2])

__PNparam(short boost){

while (1)

__PNin(A) __PNout(B) {

for (int i = 0; i < 2; i++)

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

}}

__PNprocess Amp1 = AudioAmp __PNin(C) __PNout(F) __PNparam(3);

__PNprocess Amp2 = AudioAmp __PNin(D) __PNout(G) __PNparam(10);

[Sheng14]

Architecture model

q System model including:

q Topology, interconnect, memories

q Computation: cost tables (as backup)

q Communication: cost function (no contention)

q Example: Texas Instruments Keystone

…

[Oden13]

Architecture model: Communication

q Piecewise curve-fitting from measurements

[Oden13]

Architecture model: Communication (2)

q Models for Network on Chips (NoC)

q Channels can be mapped to

q Local scratchpad (producer or consumer)

q Global SDRAM

Cost model & measurement

2 (cid:13)0 0 0

1 (cid:13)5 0 0

1 (cid:13)0 0 0

(cid:84)

(cid:70)

(cid:77)

(cid:68)

(cid:90)

(cid:68)

5 0 0

(cid:56)(cid:83)(cid:74)(cid:85)(cid:70) (cid:85)(cid:80) (cid:84)(cid:68)(cid:83)(cid:66)(cid:85)(cid:68)(cid:73)(cid:81)(cid:66)(cid:69)

(cid:51)(cid:70)(cid:66)(cid:69) (cid:71)(cid:83)(cid:80)(cid:78) (cid:84)(cid:68)(cid:83)(cid:66)(cid:85)(cid:68)(cid:73)(cid:81)(cid:66)(cid:69)

(cid:56)(cid:83)(cid:74)(cid:85)(cid:70) (cid:85)(cid:80) (cid:51)(cid:34)(cid:46)

(cid:51)(cid:70)(cid:66)(cid:69) (cid:71)(cid:83)(cid:80)(cid:78) (cid:51)(cid:34)(cid:46)

Static access costs

114

140

(cid:45)(cid:80)(cid:68)(cid:66)(cid:77)(cid:77)(cid:90) (cid:68)(cid:80)(cid:79)(cid:84)(cid:86)(cid:78)(cid:70) (cid:85)(cid:80)(cid:76)(cid:70)(cid:79)

(cid:45)(cid:80)(cid:68)(cid:66)(cid:77)(cid:77)(cid:90) (cid:81)(cid:83)(cid:80)(cid:69)(cid:86)(cid:68)(cid:70) (cid:85)(cid:80)(cid:76)(cid:70)(cid:79)

(cid:51)(cid:70)(cid:78)(cid:80)(cid:85)(cid:70)(cid:77)(cid:90) (cid:68)(cid:80)(cid:79)(cid:84)(cid:86)(cid:78)(cid:70) (cid:85)(cid:80)(cid:76)(cid:70)(cid:79)

(cid:51)(cid:70)(cid:78)(cid:80)(cid:85)(cid:70)(cid:77)(cid:90) (cid:81)(cid:83)(cid:80)(cid:69)(cid:86)(cid:68)(cid:70) (cid:85)(cid:80)(cid:76)(cid:70)(cid:79)

[Arnold13]

203

229

1 (cid:13)0 2 4

2 (cid:13)0 4 8

3 (cid:13)0 7 2

4 (cid:13)0 9 6

5 (cid:13)1 2 0

6 (cid:13)1 4 4

7 (cid:13)1 6 8

8 (cid:13)1 9 2

5 0

1 0 0

1 5 0

2 0 0

2 5 0

(cid:67)(cid:90)(cid:85)(cid:70)(cid:84)

(cid:68)(cid:90)(cid:68)(cid:77)(cid:70)(cid:84)

hs-serialhs-serialhs-serialhs-serialhs-serialparallelRouter(1,0)FPGA-InterfaceRouter(1,1)Router(0,1)Router(0,0)Duo-PE0Duo-PE1FECDuo-PE2SDDuo-PE6Duo-PE7Duo-PE5Duo-PE3CMADPLL, PMGTADPLL, PMGTADPLL, PMGTAVS Contr.UART-GPIOADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLL, PMGTADPLLADPLLDDR-SDRAM-InterfaceTomahawk2_coreAPPDuo-PE4ADPLL, PMGTVDSPRISCVDSPRISCVDSPRISCVDSPRISCVDSPRISCVDSPRISCVDSPRISCADPLL, PMGTVDSPRISCConstraints

q Timing constraints

q Process throughput

q Latencies along paths

q Time triggering

q Mapping constraints

q Processes to processors

q Channels to primitives

q Platform constraints

3 ms

1 ms

q Subset of resources (processors or memories)

q Utilization

Algorithmic description

q Extended application specification

q Selected processes are algorithmic kernels with algorithmic parameters

q Extended platform model

q SW/HW accelerated kernels and their implementation parameters

FFT HW

ACC

Points Data

format

Types & parameters

Latency equations

Interfacing

[Castrill10, Castrill11]

Analysis and synthesis: Overview

CPN

application

Analysis: Instrumentation,

profiling, tracing

Sequential performance

estimation

Time-annotated traces

Architecture

model

Mapping and

scheduling

Parallel perf.

estimation

Mapping

configuration

Non-functional

specification

Increase resources

Tracing: Dealing with dynamic behavior

q KPNs do not have firing semantics

q White model of processes: source code analysis and tracing

q Tracing: instrumentation, token logging and event recording

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Elapsed time

between events?

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Sequential performance estimation

q Fine-grained: Sometimes within code

basic-blocks

q IR-level instrumentation

q Cost tables for different architectures

q Execution count in between events

q Advanced: Emulate effect of target

compilers and back annotate to IR

Sequential performance estimation (2)

q Processor models

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

[Eusse14]

Execution counts, branch stats and execution traces

Processor performance models: Results

± 15% Error

Average gain:

248x (PD-RISC)

67x (TI DSPs)

(CA vs. profiling + estimation time)

[Eusse14]

Courtesy: J. Eusse

Parallel performance estimation

Mapping

configuration

Time-annotated traces

Trace Replay

Module

(TRM)

Architecture

model

Context

switch

Blocked

time

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

...

Resources

Grantt Chart, platform utilization,

channel profiles, ...

q Discrete event simulator to evaluate a solution

q Replay traces according to mapping

q Extract costs from architecture file (NoC modeling, context switches, communication)

Trace-based synthesis

Non-functional

specification

Time-annotated traces

Mapping,

scheduling,

buffer sizing

Mapping

configuration

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Architecture

model

[Castrill10b, Castrill13]

q Synthesis based on code and trace analysis (using simple heuristics)

q Mapping of processes and channels

q Scheduling policies

q Buffer sizing

Trace-based algorithms

q Event traces can be represented as large dependence graphs

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Blocking read

Blocking write, size(chan. 2) = 1

Blocking write, size(chan. 2) = 2

Trace-based algorithms (2)

q Event traces can be represented as large dependence graphs

q Possible to reason about

q Channel sizes and memory allocation

q Mapping and scheduling onto heterogeneous processors

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

...

......

size(chan. 2) = 2, size(chan. 1,3) = 1

...

Dealing with heterogeneity: group-based mapping (GBM)

1) Initialize: All to all

2) Select element: Trace

graph critical path

3) Reduce group

4) Assess & propagate

5) Quasi-homogeneous

[Castrill12]

Mapping for HW accelerators

q Not only mapping but also configuration

q Match algorithmic parameters with implementation parameters

q Adjust synchronization and communication protocols

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Algorithm library

Plain code

[Castrill10, Castrill11]

Platform model + characterization of special components

N: Algorithmic actors

F: Existing implementation in target platform

Multiple traces

q Different input à different behavior (traces)

q Characterize behaviors and impact on mapping performance

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

...

Mapping

configuration

Mapping

configuration

Mapping

configuration

…

[Goens15]

Multiple traces (2)

q Different input à different behavior (traces)

q Characterize behaviors and impact on mapping performance

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

)

(

[Goens15]

Behavior

...

Mapping

configuration

Mapping

configuration

Mapping

configuration

Multiple traces (3)

q Behavior difference as metric in trace/history monoid

1.9

Random KPNs: Slow down w.r.t.

optimum vs. trace distance

à No correlation

1.8

JPEG application:

Observed trace groups

140

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

1.7

1.6

1.5

1.4

1.3

1.2

1.1

[Goens15]

120

100

0.5

0.6

0.7

0.8

0.9

Normalized Trace Distance

0.5

1.5

Trace Distance Normalized with d(0,ref)

Increasing resources

q Add resources to the synthesis until constraints are met

Mapping and

scheduling

Parallel perf.

estimation

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

Increase resources

q Add processors and memories

q Easy for homogeneous platforms

q Non trivial for heterogeneous platforms

Increasing resources: Exploit symmetries

q Identify mapping equivalent classes due to HW symmetries

Tracing

Mapping

Seq. perf.

estimation

Par. perf.

estimation

Resources

[Goens15]

q Do not evaluate equivalent mappings

q Reduce search space when adding resources

q Multiple traces (revisit)

q Random traces: 5 out of 83 classes account for

50% of all optimal mappings

q Application to multi-application analysis

Code generation

CPN

application

Mapping

configuration

Code generation

Architecture

model

PNargs_ifft_r.ID = 6U;

PNargs_ifft_r.PNchannel_freq_coef = filtered_coef_right;

PNargs_ifft_r.PNnum_freq_coef = 0U;

PNargs_ifft_r.PNchannel_time_coef = sink_right;

PNargs_ifft_r.channel = 1;

sink_left = IPCllmrf_open(3, 1, 1);

sink_right = IPCllmrf_open(7, 1, 1);

PNargs_sink.ID = 7U;

PNargs_sink.PNchannel_in_left = sink_left;

PNargs_sink.PNnum_in_left = 0U;

PNargs_sink.PNchannel_in_right = sink_right;

PNargs_sink.PNnum_in_right = 0U;

taskParams.arg0 = (xdc_UArg)&PNargs_src;

taskParams.priority = 1;

...

Debugging info

q Take mapping configuration and generate code accordingly

q From architecture model: APIs, configuration parameters, …

Nucleus programming flow: Code generation

q Bare-metal implementation

cpn-cc (target)

C code for

non-nuclei

Control+config

(HW flavors)

Flavor config

(SW flavors)

C compiler 1

0x0 def 0x8

0x4 def 0x1000

...

0x- MAC R1,R2,R3

...

Configured

SW flavors

int main() {

...

fft_cfg(...);

...

while (1) {

...

}}

Control code

Linker 2

Linker 1

SW-Flavor

(unconfigured)

0x0 def $STRIDE$

0x4 def $BASE$

...

0x- MAC R1,R2,R3

...

Flavor library

Debugging with virtual platforms

q Interactive debugging

q Get snapshots of the system state

q Full system stop

q Track progress irrespective of mapping

OS-descriptor

Debugging info

Debugging layer

Internal state of the MPSoC schedule:

assigned, blocked and running tasks

[Castrill11]

Virtual platform

Debugging with virtual platforms (2)

q Deterministic replay and automatic bug exploration

[Murillo14]

Evaluation and results

q Virtual platforms: SystemC models of full systems

q Explore heterogeneous architectures

q Easier to integrated state-of-the-art accelerators

q Configurable accuracy

q Real platforms for validation

q Speedup on commercial platforms

q Code generation against vendor stacks

Example: multi-media applications

q Platform: 2 RISCs, 4 VLIW, 7 Memories

Example: multi-media applications (2)

q Dealing with real-time constraints

Tool: ~1 min. for LP-AF, ~7 min. for MJPEG

Sim.: ~6 days for LP-AF, ~24 for MJPEG ~10 days (~x103)

~10 min.

Example: With HW acceleration

q Application: MIMO OFDM receiver

q Hardware

q Platform 1: Baseline software

q Platform 2: Optimized software

q Platform 3: Optimized SW + HW

Achieved rate @ 100 MHz

1758241,75

7680

128000

)

(

1,00E+06

1,00E+04

1,00E+02

1,00E+00

bsp1 (sw,

unoptimized)

bsp2 (sw,

optimized)

bsp3 (hw)

ARM

src

sink

Mem

VLIW VLIW VLIW

Library 1: SW

implementations

Library 2: SW

optimized

ARM

src

sink

MemMem

Mem

Demap

Library 3:

SW+HW accel.

Custom Interconnect

VLIW

FFT

Viterbi

Manual vs. Automatic: TI Keystone

Image processing

Audio filtering application

[Aguilar14]

LTE digital

receiver

TRM vs. Actual execution: TI Keystone

Makespan error < 20% (Avg. 7%)

Speedup error < 8% (Avg. 5%)

Parallel Programming with Models of Computation

Parallel Programming with Models of Computation