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 3: Models of Computation & Dataflow

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&2

q The reason for parallelism and its fundamentals

q Standard programming models and their flaws

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

q Task-based programming – A simple and easy model

q In this lecture

q What are Models of Computation (MoCs)

q MoC-based programming models

Contents

q Introduction to MoCs

q Dataflow MoCs

q Process Networks

Introduction to MoCs

Model of Computation (MoC): Definitions

A model of computation is the definition of the set of allowable operations used

in computation and their respective costs. It is used for measuring the complexity

of an algorithm in execution time and or memory space

Wikipedia: From Computational theory

Model of computation are abstract specifications of how a computation can

progress

http://c2.com/cgi/wiki?Models OfComputation

A Model of computation is a collection of rules that govern the interaction of

components

Ptolemaeus, C. (Ed.). System Design, Modeling, and Simulation using Ptolemy II Ptolemy.org, 2014

Model of Computation (MoC): Definitions

A model of computation is the definition of the set of allowable operations used

in computation and their respective costs. It is used for measuring the complexity

of an algorithm in execution time and or memory space

Wikipedia: From Computational theory

q Computability/complexity theory

q Power: Which class of (mathematical) functions can be computed

q Complexity: In what time/space?

q Expressiveness: Ease with which computations are expressed

q Typical models: Finite state machines (FSM, automata), push-down automata

(Grammars), Turing machine, lambda calculus, …

Example: FSM – Automata for regular languages

Def.: An Non-deterministic finite automaton is a 5-tuple (Q,Σ,Δ,q0,F), where Q

is a finite set of states, Σ is an alphabet (input) and

Δ : Transition relation

q0: Is an initial state (q0 ∈ Q)

F : Set of final (acceptor) states (F ⊆ Q)

[{

(⌃

✓

⇥

✏

)

}

⇥

ε denotes the empty string

q Given an NFA in current state q, the next state is decided by

q Input: Move to q’ by reading a ∈ Σ if (q,a,q’) ∈ Δ

q ε-moves: By moving to state q’, if (q,ε,q’) ∈ Δ

q An NFA accepts a string if a state can be reached that is in F

q Every NFA can be converted in a deterministic finite automaton (DFA)

Example: FSM – Use & power

q Used in many domains: electronic design automation, hardware design,

communication protocol design, language parsing, biology, linguistics, …

q Power: weaker than Turing machine

q Memory is restricted to the number of states (finite)

q Example

Source: Wikipedia

Example: FSM – Regular languages

q Automata can recognize regular languages (generated by regular expressions)

q Example: Odd binary numbers

q Regular expression

q Automaton

q Deterministic version

R = (0|1)*1

Example: Push-down automaton (PDA)

Def.: An PDA is a 7-tuple (Q,Σ,𝚪,Δ,q0,Z,F), where Q is a finite set of states, Σ is

the input alphabet, 𝚪 is a finite stack alphabet and

(⌃

Δ : Transition relation

q0,Z: Is an initial state (q0 ∈ Q) and Z is the initial stack symbol (Z ∈ 𝚪)

F : Set of final (acceptor) states (F ⊆ Q)

)

}

[ {

⇤

⇥

✓

⇥

✏

Kleene operator

q NFA/DFA: Cannot parse context free languages (see nesting)

q PDAs are therefore more powerful, but still weaker than Tuning Machines

q Computation: for (p, a, A, q, 𝛼) ∈ Δ

q In state p with top of stack A, the PDA may read a and move to state q

q Also: pop A from the stack and replace it by 𝛼 ∈ 𝚪*

Example: Turing machine

Def.: A Turing Machine is a 7-tuple (Q,𝚪,b,Σ,δ,q0,F), where Q is a finite set of

states, 𝚪 is the tape alphabet, b is the blank symbol (can occur infinitely), and

Σ ⊆𝚪-{b}: input alphabet

: (Q

δ : Transition function

q0: Is an initial state (q0 ∈ Q)

F : Set of final (acceptor) states (F ⊆ Q)

F )

⇥

⇥ {

L, R

}

q A Turing machine can simulate every what a computer can do

q Reads input symbol from a tape with infinite cells

q Depending on the state, it writes a symbol in the cell, moves the tape on cell to

the right or left (L,R) and transitions to another state (or halts)

(Parallel) Models of Computation (MoCs): Rules

A Model of computation is a collection of rules that govern the interaction of

components

Ptolemaeus, C. (Ed.). System Design, Modeling, and Simulation using Ptolemy II Ptolemy.org, 2014

q What are the components

q Threads, processes, actors, tasks or procedures

q Execution and concurrency

q Order and determinism

q Communication mechanisms: How do components

exchange data

q Asynchronous or rendezvous, perfect or lossy

MoCs & properties

q Depending on the rules, MoCs feature different properties

q Properties

q Makes it easier for automatic tools to understand and synthesize code

q Relate to the power: what can be computed with the model

q Examples

q Can the application run on bounded memory?

q Can we compute the maximal throughput?

q Is the execution deterministic?

MoCs: Overview

In this lecture: Dataflow and

process networks

Ptolemaeus, C. (Ed.). System Design, Modeling, and Simulation using Ptolemy II Ptolemy.org, 2014

Dataflow models: Introduction

q Also a graph representation: Nodes & edges are called actors & channels

q Implicit repetition, common in streaming, signal processing applications

q Communication: only through channels

q Multiple flavors of models: Rules that determine when an actor fires

q A graph models multiple possible executions:

Processor

…

Time

Dataflow models: Introduction (2)

q Also a graph representation: Nodes & edges are called actors & channels

q Implicit repetition, common in streaming, signal processing applications

q Communication: only through channels

q Multiple flavors of models: Rules that determine when an actor fires

q A graph models multiple possible executions:

Processor

What now?

…

Time

Dataflow models: Examples

q Homogeneous Synchronous Dataflow (HSDF): every actor has a fixed behavior

All actors, when fired, consumes

one token from each channel and

produce one toke to every output

channel

q Synchronous Dataflow (SDF): Allow multiple, different rates

a3 always writes 1 token to e4

3 1

Dataflow models: Examples (2)

q Cyclo-Static Dataflow (CSDF): every actor has a set of fixed behaviors

(1,0,0)

(0,2)

(0,1,0)

a1: writes 1 token, then 0,

then 0 to e2

More on this later

q Dynamic dataflow: set of firing rules per actor

Process Networks: Examples

q Process networks: nodes are called “processes” instead of actors

q Processes does not have the firing semantics of actors

q Kahn process networks (KPN): nodes are now called processes

p1: writes any amount of tokens

to e2 at any time

Other MoCs: Hewitt’s actors (‘73)

q Related concept of actors and firing: Basis of concurrent computation

q Actors can receive messages from any other actor

q Upon receiving a message an actor can

q Send a finite amount of messages to other actors

q Create a finite number of actors

q Define how to respond to the next message

q Unbounded nondeterminism: The delay to service a request can be

unbounded due to contention on shared resources, while still guaranteeing that

the request will eventually be serviced.

q Used in practice: Erlang, Twitter and Microsoft

Dataflow MoCs

Acknowledgements

q The material presented here has been inspired on

q Presentations from Marco Bekooij,

NxP and University of Twente

q Book from S. Sriram, S.S. Bhattacharyya

Homogeneous synchronous dataflow graph (HSDF)

Def.: An HSDF is an annotated multi-graph G=(V,E,W). V is the set of actors and

E ⊆ VxV the set of channels. W = {w1,...,w|E|}, with we the set of initial tokens on

edge e (also called delays)

q Example

What next?

HSDF: Actors

q Actors are stateless

q Actors can represent functions, tasks, …

q Different to a procedural call!

q When tokes are present, the actor “fires” (=executes)

q Other models have more complex firing rules

q Actors are untimed, but a firing duration can be added (need not be constant)

q Actors only interact with their environment through token

consumption/production

HSDF: Channels

q Channels store tokens

q Channels have by definition unbounded capacity

q Usually channels have First-in First-out (FIFO)

semantics, i.e., tokens can be consumed in the order

that they were produced

HSDF: Tokens

q Tokens are indivisable

q The arrival of a token is an event

q Tokens are usually used to represent data

q Tokens can also represent space or synchronization

moments

Firing rules

q In general tells (more details later)

q Which conditions in the input channels lead to a firing

q For HSDF

q Need one token on each input channel

q A firing rule does not specify the production behavior

q For HSDF

q A firing produce one token in every output channel

Enabling, starting and finish time

q Notation

q Ia, Oa: Set of inputs an ouputs of actor a

q tk(i)/tk(o): Time of arrival/production of k-th token in input i, or output o

q ek(a): k-th enabling of actor a

q Enabling

q Starting time sk(a) can be anytime after enabling and finish time, fk(a), after

ek(a) = maxi

Ia (tk(i))

a duration ρk(a)

ek(a)



sk(a), fk(a) = sk(a) + ⇢k(a)

Self-timed execution

q Zero-delay

q Token consumption: atomically at sk(a)

q Token production: atomically at fk(a)

q Self-time execution: Actor starts as soon as data is there

Oa, tk(o) = ⇢k(a) + maxi

Ia (tk(i))

Auto-concurrency

q If input is produced faster than the firing duration, actor executions overlap

maxi

Ia (tk(i))

q Then (k-1)-th overlaps with k-th execution

maxi

Ia (tk

1(i)) < ⇢k

1(a)

q Consequence: Tokens can overtake each other

Under what circumstances?

Auto-concurrency

q If input is produced faster than the firing duration, actor executions overlap

maxi

Ia (tk(i))

q Then (k-1)-th overlaps with k-th execution

maxi

Ia (tk

1(i)) < ⇢k

1(a)

q Consequence: Tokens can overtake each other

q If the (k-1)-th duration is longer than the k-th duration

1(a)

⇢k

⇢k(a)

As a consequence

of adding time:

FIFO semantics

may be violated

sk-1(a)

sk(a)

tk(o)

tk-1(o)

Time

Conditions for FIFO behavior

q Most analysis techniques requires FIFO behavior (monotonicity and linearity do

not, discussed later)

q Condition 1: Constant firing durations

k, ⇢k(a) = ⇢0(a)

q Condition 2: Enforce sequential behavior (no auto-concurrency)

tk(o) = ⇢k(a) + maxi

Ia (tk(i))

Conditions for FIFO behavior

q Most analysis techniques requires FIFO behavior (monotonicity and linearity do

not, discussed later)

q Condition 1: Constant firing durations

k, ⇢k(a) = ⇢0(a)

q Condition 2: Enforce sequential behavior (no auto-concurrency)

o’

tk(o) = ⇢k(a) + maxi

Ia (tk(i))

tk(o) = ⇢k(a) + max(maxi

Ia{

i0}

(tk(i)), tk

1(o))

Deadlocks

q Recall: Deadlocks can inadvertently occur when using threads/message passing

q Can we guarantee deadlock-freedom in HSDF?

Deadlocks: Condition for HSDF

An HSDF Graph deadlocks iff there is a cycle without initial tokens

q Token conservation: The number of tokens in any cycle of an HSDFG is

Does not depend on

durations!

conserved over all possible firings (and is equal to the path delay of the cycle)

q Intuition: only actors in the cycle can consume/produce tokens, so they simply move

tokens from one edge to the next

q Proof (è)

q If there is a cycle w/o tokens, then it will remain like that (token conservation)

q Every actor in the cycle has at least a channel w/o tokens and can therefor not fire

q Proof (ç): If the graph deadlocks after some firings, actor a1 is never fired

q There must be a channel (a2,a1) w/o tokens, and another (a3,a2), and (a4,a3), …

q Sequence continues, but the |V| is finite è there mus be a cycle in that path

HSDF: Blocked schedule

q Execute entire “graph iterations” before starting next one

q Which actors can execute first?

q Imagine the graph w/o edges with delays

Processors

To compute a blocked schedule:

Re-use the techniques for DAG

scheduling!

PE2

PE1 a4

Block

Time

HSDF: Blocked schedule (2)

q Block schedule: Essentially apply any of the techniques from Lecture 2

q Improving the schedule

q Retiming

§ Known for reducing the critical path in VLSI

§ Cut-set techniques to move delays around

q Unfolding

§ Make N copies of the graph iteration

§ Similar to loop unrolling

Unfolding: Intuition

q Copy the graph N times

q Respect dependencies across iterations

a21

a31

a22

a32

a23

a33

a11

a41

a12

a42

a13

a43

HSDF: Overlapped schedule

q Allow successive iterations of the graph to overlap

Processors

PE2

PE1 a4

PE2

PE1 a4

Time

HSDF: Overlapped schedule (2)

q Allow successive iterations of the graph to overlap

q Overlapped schedules are fundamentally superior than blocked schedules with

unfolding and retiming

K. K. Parhi and D. G. Messerschmitt. Static rate-optimal scheduling of iterative data-flow

programs via optimum unfolding. IEEE Transactions on Computers, 1991.

q Techniques: similar to Software Pipelining (see before)

PE2

PE1 a4

Time

HSDF: Enforcing schedules

q Scheduling decisions (and other decisions) can be modeled directly in the graph

q How to delay the execution of a3?, how to prevent a4 from executing earlier?

PE2

PE1 a4

Time

Modeling FIFO buffers

q Apart from modeling scheduling decisions, one can also model bounded FIFOs

q Unbounded buffer

q FIFO with capacity ‘c’

HSDF: Maximum cycle mean (MCM)

q The MCM relates to the maximum throughput of an HSDF

q Given an HSDF G=(V,E)

q Let O(G) be the set of all cycles

q A cycle C=((vi,vi+1),(vi+2,vi+3),…,(vi+n-1, vi))

Recall: w(e) is the

amount of delays

M CM (G) = maxC

O(G)

C ⇢(v)

v:(u,v)

(v,u)

C w(e)

HSDF: Maximum cycle mean (MCM) (2)

q The MCM is fundamental for digital system design

q Problem: There is an exponential number of simple cycles in a graph

q Many algorithms have been proposed (for further reading)

Ali Dasdan. 2004. Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans. Des. Autom. Electron. Syst. 9, 4

(October 2004), 385-418.

HSDF: MCM examples

M CM (G) = maxC

O(G)

q How many cycles?

C ⇢(v)

v:(u,v)

(v,u)

C w(e)

x delay tokens

q C1=((a1,a1)), C2=((a2,a2)), C3=((a1,a2)(a2,a1))

M CM (G) = max

⇢(a1)

⇢(a2)

⇢(a1) + ⇢(a2)

✓

◆

HSDF: MCM examples

M CM (G) = maxC

O(G)

C ⇢(v)

v:(u,v)

(v,u)

C w(e)

q Critical cycle determines the throughput

(1)

(2)

M CM (G) = max (1, 2, 1) = 2

M CM (G) = max (1, 2, 3) = 3

HSDF: MCM and throughput

(2)

(4)

How is that possible if

ρ(a2)=4?

q What is the maximum throughput?

q Which schedule?

M CM (G) = max

✓

2 + 4

◆

= 3

2 firings every 6

cycles

Time

Admissible schedule & Monotonicity

Def.: A schedule of a graph σ is admissible if for all actors a and firing k there is

at least a token on all channels at time sk(a)

A self-time execution has monotonic temporal behavior, i.e., σ ⩽ σ’ if

q If a firing duration became shorter

q Time between enabling and start is shorter

q The number of initial tokens is increased

q Recall: self-time: actor executes as soon as data is there

Oa, tk(o) = ⇢k(a) + maxi

Ia (tk(i))

q Consequence: Average throughput (MCM-1) increases if response time decreases

Synchronous dataflow graph (SDF)

Def.: An SDF is an annotated multi-graph G=(V,E,W). V is the set of actors and E

⊆ VxV the set of channels. W = {w1,...,w|E|} ⊂N3 is a set of annotations for

every channel e = (a1,a2), we=(pe,ce,de): pe is the number of tokens produced by

a firing of a1, ce the tokens consumed by a2 and de the amount of delay tokens

q Note that an HSDF is a special case of an SDF with we=(1,1,de) for all edges

Synchronous dataflow graph (SDF)

Def.: An SDF is an annotated multi-graph G=(V,E,W). V is the set of actors and E

⊆ VxV the set of channels. W = {w1,...,w|E|} ⊂N3 is a set of annotations for

every channel e = (a1,a2), we=(pe,ce,de): pe is the number of tokens produced by

a firing of a1, ce the tokens consumed by a2 and de the amount of delay tokens

q Example

3 1

What next?

3 1

Rate inconsistency and deadlocks

q We are interested in a schedule that executes forever on bounded memory

q Forever means: no deadlocks

q Bounded memory: means consistent rates

q Example

1 1

Leads to unbounded

accumulation of tokens on

channel (a1,a3)

Complete cycle

Def.: Given an SDF G=(V,E,W), a complete cycle is a sequence of actor firings

that brings the SDF to its initial state

q Example

3 1

How many executions of each

actor would be required?

Topology matrix

Def.: Given an SDF G=(V,E,W), its topology matrix 𝚪 has a row for every

channel and a column for every actor. [𝚪ik] = pik – cik (i.e. the amount of tokens

produced minus those consumed by actor k on/from channel i)

q Example

3 1

= 0

Topology matrix (2)

q State of an SDF: tokens in the queues

q The topology matrix can be used to update the state after a firing

3 1

= 0

s1 = s0 + 0

0 1

= 0

· 0

+ 0

= 0

Topology matrix (3)

q State of an SDF: tokens in the queues

q The topology matrix can be used to update the state after a firing

3 1

= 0

s2 = s1 + 0

0 1

= 0

· 0

+ 0

= 0

Topology matrix and complete cycles

q Complete cycle: sequence of firing that brings the SDF to the original state

sn = s0 +

(v1 + v2 +

+ vn) = s0

(v1 + v2 +

· · ·

+ vn) =

~r = 0

· · ·

A connected SDF G=(V,E,W), with consistent rates, is guaranteed to have

rank(𝚪)= |V| – 1, which ensures that 𝚪

q Intuition: If only the trivial solution is possible (r=0), then every other would lead

to unbounded accumulation of tokens in the channels

Repetition vector

Def.: Given an SDF G=(V,E,W) with consistent rates and topology matrix 𝚪, the

repetition vector is the smallest integer vector in the null space of 𝚪, i.e., the

smallest integer vector such that

~r = 0

q Example

3 1

~r = 0

~r = (1, 3, 2)T

From SDF to HSDF

q Intuition

q Given a repetition vector r=(q1,q2,…qn)

q Make qi copies of actor ai (need to adapt the ports)

q Connect actors so that production and consumption correspond to original SDFG

a21

3 1

~r = (1, 3, 2)T

a11

a22

a31

a32

a23

From SDF to HSDF (2)

q Actors: the number of actors depends on the repetition vector and can be

exponential in the worst case

q After transformation

q Buffer sizing for HSDF

q Blocked/overlapped scheduled as with HSDFs

q There are other methods to deal with SDFs w/o going via HSDF

Cyclo-static Synchronous dataflow graph (CSDF)

Def.: A CSDF is an annotated multi-graph G=(V,E,D,P) where D={d1,…d|E|} is a

set of edge delays and P={P1,…P|V|} represents actor phases. The phases of

actor ak, are a sequence Pk=(pk

production and consumption rates on output and input channels. The production

rates of actor ak on edge eu are sequence of integers (xu

similar for consumption

m), where each phase specifies the

k,2,…, xu

1,…,pk

k,1, xu

k,m) –

q An SDF is a special case of a CSDF in which every actor has only one phase

q The n-th execution of an actor produces xu

k,y tokens on edge eu, with

y = ((n

1) mod m) + 1

Cyclo-static Synchronous dataflow graph (CSDF)

Def.: A CSDF is an annotated multi-graph G=(V,E,D,P) where D={d1,…d|E|} is a

set of edge delays and P={P1,…P|V|} represents actor phases. The phases of

actor ak, are a sequence Pk=(pk

production and consumption rates on output and input channels. The production

rates of actor ak on edge eu are sequence of integers (xu

similar for consumption

m), where each phase specifies the

k,2,…, xu

1,…,pk

k,1, xu

k,m) –

q Example

(1,0,0)

(0,2)

(0,1,0)

Different phase length

on each channel?

(1,0,0)

(1,1,1)

Cyclo-static Synchronous dataflow graph (CSDF)

Def.: A CSDF is an annotated multi-graph G=(V,E,D,P) where D={d1,…d|E|} is a

set of edge delays and P={P1,…P|V|} represents actor phases. The phases of

actor ak, are a sequence Pk=(pk

production and consumption rates on output and input channels. The production

rates of actor ak on edge eu are sequence of integers (xu

similar for consumption

m), where each phase specifies the

k,2,…, xu

1,…,pk

k,1, xu

k,m) –

q Example: Execution

Can we do more?

(1,0,0)

(0,2)

(1,0,0)

(0,1,0)

(0,2)

(0,1,0)

Cyclo-static Synchronous dataflow graph (CSDF)

Def.: A CSDF is an annotated multi-graph G=(V,E,D,P) where D={d1,…d|E|} is a

set of edge delays and P={P1,…P|V|} represents actor phases. The phases of

actor ak, are a sequence Pk=(pk

production and consumption rates on output and input channels. The production

rates of actor ak on edge eu are sequence of integers (xu

similar for consumption

m), where each phase specifies the

k,2,…, xu

1,…,pk

k,1, xu

k,m) –

q Example: Execution

(1,0,0)

(0,2)

(1,0,0)

(0,1,0)

(0,2)

(0,1,0)

CSDF: Execution example

(1,0,0)

(0,2)

(1,0,0)

(0,1,0)

(0,2)

(0,1,0)

(1,0,0)

(0,2)

(1,0,0)

(0,1,0)

(0,2)

(0,1,0)

(1,0,0)

(0,2)

(0,1,0)

(0,2)

(0,1,0)

Why CSDF?

q Allows finer granularity of the modeling (better than SDF)

(0,1,0)

(0,2)

q In CSDF some phases of a2 can be scheduled ahead of time, instead of waiting for

6 tokens to arrive! (recall previous slide)

q CSDF: Also decidable verification of bounded memory and deadlock-freedom

q Better granularity could be also achieved by modifying the SDF representation

q Usually this creates higher memory requirements (see next slide)

Why CSDF? (2)

Finer granularity lead to

faster schedule, at the cost

of more memory

Bilsen, Greet, et al. "Cycle-static dataflow." Signal Processing, IEEE Transactions on 44.2 (1996): 397-408.

Why CSDF? (3)

q CSDF allows to profit from granularity w/o increasing memory requirements

Bilsen, Greet, et al. "Cycle-static dataflow." Signal Processing, IEEE Transactions on 44.2 (1996): 397-408.

Topology matrix

Def.: Given a CSDF G=(V,E,D,P), its topology matrix 𝚪 has a row for every

channel and a column for every actor. [𝚪ik] = Xik – Yik. Where Xik and Yik are the

accumulated production and consumption of all phases.

q Recall that an actor has a set of phases Pk

q Production rates of actor ak on edge eu: (xu

k,1, xu

k,2,…, xu

k,m)

Xik =

Pk|

j=1

k,j

Yik =

k,j

Pk|

j=1

Topology matrix

Def.: Given an CSDF G=(V,E,D,P), its topology matrix 𝚪 has a row for every

channel and a column for every actor. [𝚪ik] = Xik – Yik. Where Xik and Yik are the

accumulated production and consumption of all phases.

q Example

(1,0,0)

(0,2)

6 phases:

In: (0,2,0,2,0,2)

Out: (0,1,0,0,1,0)

(0,1,0)

Xik =

Pk|

j=1

k,j Yik =

k,j

Pk|

j=1

1 1

Repetition vector

Def.: Given an CSDF G=(V,E,D,P) with topology matrix 𝚪, its repetition vector

q = (q1,…q|V|)...

Parallel Programming with Models of Computation

Parallel Programming with Models of Computation