PPj-94c 10. Concurrent and functional programming Overview 1. Pure functional programs do not have side-effects: operands of an operation and arguments of a call can be evaluated in any order, in particular concurrently 2. Recursive task decomposition can be parallelized according to the paradigm bag of subtasks 3. Lazy evaluation of lists leads to programs that transform streams, can be parallelized according the pipelining paradigma 4. Dataflow languages and dataflow machines support stream programming 5. Concurrency notions in functional languages: Message passing in Erlang Actors in Scala (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94c Objectives: Understand close relation between FP and concurrency In the lecture: Explain * the items. -------------------------------------------------------------------------------- PPj-94d Recursive adaptive quadrature computation b fun quad (f, l, r, area, eps) = y integral f(x) dx f(x) let m = (r-l)/2 and a fl = f(l) and fm = f(m) and fr = f(r) and (f(a)+f(m))/2 * larea = (fl+fm)*(m-l)/2 and (m-a) rarea = (fm+fr)*(r-m)/2 and in a b x m = if abs(larea+rarea-area)>eps (b-a)/2 then let Compute an approximation of the integral over f(x) between a and b. lar = quad(f,l,m,larea,eps) and Recursively refine the interval into rar = quad(f,m,r,rarea,eps) two subintervals until the sum of the areas of the two trapezoids differs in (lar+rar) less than eps from the area of the big end trapezoid. else area end See [G. Andrews: Foundations of Multithreaded, initial call: Parallel, and Distributed Programming, Addison Wesley, 2000, pp. 17-19] quad (f,a,b,(f(a)+f(b)/2*(b-a),0.001) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94d Objectives: Understand the recursive quadrature computation In the lecture: Explain * the task, * the approximation idea, * the functional notation -------------------------------------------------------------------------------- PPj-94e Recursive adaptive quadrature computation b fun quad (f, l, r, area, eps) = y integral f(x) dx f(x) let m = (r-l)/2 and a fl = f(l) and fm = f(m) and fr = f(r) and (f(a)+f(m))/2 * larea = (fl+fm)*(m-l)/2 and (m-a) rarea = (fm+fr)*(r-m)/2 and in a b x m = if abs(larea+rarea-area)>eps (b-a)/2 then let Compute an approximation of the co integral over f(x) between a and b. lar = quad(f,l,m,larea,eps) and // Recursively refine the interval into rar = quad(f,m,r,rarea,eps) two subintervals until the sum of the oc areas of the two trapezoids differs in (lar+rar) less than eps from the area of the big end trapezoid. else area Fork two concurrent processes. end See [G. Andrews: Foundations of Multithreaded, initial call: Parallel, and Distributed Programming, Addison Wesley, 2000, pp. 17-19] quad (f,a,b,(f(a)+f(b)/2*(b-a),0.001) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94e Objectives: Parallelized refinement In the lecture: Explain * the dynamics of the refinement -------------------------------------------------------------------------------- PPj-94f Streams in functional programming Linear lists are fundamental data structures in functional programming, e.g. in SML: datatype 'a list = nil | :: of 'a * 'a list Eager evaluation: all elements of a list are to be computed, before any can be accessed. Lazy evaluation only those elements of a list are computed which are going to be accessed. That can be achieved by replacing the (pointer to) the tail of the list by a parameterless function which computes the tail of the sequence when needed: datatype 'a seq= Nil | Cons of 'a * (unit->'a seq) Lazy lists are called streams. Streams establish a useful programming paradigm: Programming the creation of a stream can be separated from programming its use. stream consumer producer summarize sequence of numbers use random numbers random numbers decide upon convergence iterate approximations decide upon solution enumerate solutions space Functions on streams can be understood as communicating concurrent processes. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94f Objectives: Understand streams in functional programming In the lecture: Explain * the notion of streams, * the programming paradigm -------------------------------------------------------------------------------- PPJ-94g Examples for stream functions (1) produce a stream of numbers: int -> int seq fun from k = Cons (k, fn()=> from (k+1)); consume the first n elements into a list: quotesingle a seq * int -> quotesingle a list fun take (xq, 0) = [] | take (Nil, n) = raise Empty | take (Cons(x, xf), n) = x :: take (xf (), n - 1); transform a stream of numbers: int seq -> int seq fun squares Nil = Nil | squares (Cons (x, xf)) = Cons (x * x, fn() => squares (xf())); take (squares (from 1), 10); 1 4 9... take 10 squares 1 2 3... from 1 (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94g Objectives: Understand simple stream functions In the lecture: Explain * structure of stream functions, * classify: producer, consumer, transformer, -------------------------------------------------------------------------------- PPJ-94h Examples for stream functions (2) add the numbers of two streams: int seq * int seq -> int seq fun add (Cons(x, xf),Cons(y, yf)) = Cons (x+y, fn() => add (xf(), yf())) | add _ = Nil; 50 51 52... from 0 take 10 50 52 54 56... add from 50 Filter-Schema: pred (quotesingle a -> bool) -> quotesingle a seq -> quotesingle a seq filter fun filter pred Nil = Nil 0 1 2 ... | filter pred (Cons(x,xf)) = if pred x then Cons (x, fn()=> filter pred (xf())) else filter pred (xf()); (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94h Objectives: Combine streams In the lecture: Explain the examples -------------------------------------------------------------------------------- PPJ-94i Recursive stream composition fun sift p = filter (fn n => n mod p <> 0); p fun sieve (Cons(p,nf)) = sift: Cons (p, fn() => sieve (sift p (nf()))); eliminate multiples of p val primes = sieve (from 2); take (primes, 25); sieve: 2 hd hd Compute prime primes tl from numbers: tl Sieve of sieve sift Eratosthenes All recursively constructed sift-sieve-pairs can execute concurrently! (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94i Objectives: Understand recursive composition of streams In the lecture: The recursion is explained -------------------------------------------------------------------------------- PPj-94j Sieve of Eratosthenes in CSP A pipeline of filters: L processes are created, each sends a stream of numbers to its successor. The first number p received is a prime. It is used to filter the following numbers. Finally, each process holds a prime in p. process Sieve[1] for [1 = 3 to n by 2] Sieve[2] ! i # pass odd numbers to Sieve[2] process Sieve[i = 2 to L] int p, next Sieve[i-1] ? p # p is a prime do Sieve[i-1] ? next -># receive next candidate if (next mod p)!=0 -> Sieve[i+1] ! next # pass it on fi od [G. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming, Addison Wesley, 2000, pp. 326-328] (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94j Objectives: Pipeline of processes In the lecture: The communication is explained and compared to the stream functions. -------------------------------------------------------------------------------- PPj-94k Dataflow languages Textual languages: Lucid: stream computations by equations, no side effects; 1976, Wadge, Ashcroft SISAL: (Streams and Iteration in a Single Assignment Language), no side-effects, fine- grained parallelization by compiler, 1983 Visual languages: Prograph (Acadia University 1983): dataflow and object-oriented LabVIEW (National Instruments, 1986): Nodes represent stream processing functions connected by wires, concurrent execution triggered by available input. Strong support of interfaces to instrumentation hardware. (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94k Objectives: Pointers to dataflow languages In the lecture: General information on these languages is given. -------------------------------------------------------------------------------- PPj-94l Language Erlang Erlang developed 1986 by Joe Armstrong, et.al at Ericsson * multi-paradigm: functional and concurrent * initial application area: telecommunication requirements: distributed, fault-tolerant, soft-real-time, non-stopping software * processes communicate via asynchronous message passing * single-assignment variables, no shared memory between processes Explanations and examples taken from [J. Armstrong, R. Virding, C. Wikström, M. Williams: Concurrent Programming in ERLANG, Second Edition, Ericsson Telecommunications Systems Laboratories, Prentice Hall,1996] http://www.erlang.org (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94l Objectives: Characteristics of Erlang In the lecture: Explain background -------------------------------------------------------------------------------- PPj-94m Basic communication constructs process creation: Pid = spawn(Module, FunctionName, ArgumentList) asynchonous message send: Initial example Pid ! Message A module that creates counter The operands are expressions which processes: yield a process id and a message. -module(counter). selective receive: -export([start/0,loop/1]). receive start() -> Pattern1 [when Guard1] -> spawn(counter, loop, [0]). Actions1 ; Pattern2 [when Guard2] -> loop(Val) -> Actions2 ; receive ... increment -> end loop(Val + 1) end. Searches the process' mailbox for a message that matches a pattern, and receives it. clients send increment messages to it Can not block on an unexpected message! (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94m Objectives: Understand send and selective receive constructs In the lecture: Explain the constructs -------------------------------------------------------------------------------- PPj-94n Complete example: Counter Interface functions are -module(counter). called by client -export([start/0,loop/1,increment/1,value/1,stop/1]). processes. \%\% First the interface functions. They send 3 start() -> spawn(counter, loop, [0]). kinds of increment(Counter) -> Counter ! increment. messages. value(Counter) -> self() gives Counter ! {self(),value}, the client's pid, receive {Counter,Value} -> Value to reply to it. end. The counter stop(Counter) -> Counter ! stop. process identifies itself \%\% The counter loop. in the reply. loop(Val) -> receive increment -> loop(Val + 1); The receive is {From,value} -> From ! {self(),Val}, iterated (tail- loop(Val); recursion). stop -> true; Unexpected Other -> loop(Val) messages are end. removed (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94n Objectives: Understand the constructs in context In the lecture: Explain the constructs -------------------------------------------------------------------------------- PPj-94o Example: Allocation server (interface) A server maintains two lists of free and allocated resources. Clients call a function allocate to request a resource and a function free to return that resource. -module(allocator). -export([start/1,server/2,allocate/0,free/1]). The two lists of free and allocated resources are start(Resources) -> initialized. Pid = spawn(allocator, server, [Resources,[]]), register associates the register(resource_alloc, Pid). pid to a name. \% The interface functions. The calls of allocate allocate() -> request(alloc). andfree are transformed free(Resource) -> request({free,Resource}). into different kinds of messages. Thus, request(Request) -> implementation details resource_alloc ! {self(),Request}, are not disclosed to receive {resource_alloc,Reply} -> Reply clients. end. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94o Objectives: Understand a non-trivial server implementation In the lecture: Explain the techniques -------------------------------------------------------------------------------- PPj-94p Example: Allocation server (implementation) The function server server(Free, Allocated) -> receives the two kinds of receive messages and transforms {From,alloc} -> them into calls of s_allocate(Free, Allocated, From); s_allocate and {From,{free,R}} -> s_free. s_free(Free, Allocated, From, R) end. s_allocate([R|Free], Allocated, From) -> s_allocate returns yes From ! {resource_alloc,{yes,R}}, and the resource or no, server(Free, [{R,From}|Allocated]); and updates the two lists s_allocate([], Allocated, From) -> in the recursive server From ! {resource_alloc,no}, call. server([], Allocated). s_free: member checks s_free(Free, Allocated, From, R) -> whether the returned case member({R,From}, Allocated) of resource R is in the free true -> From ! {resource_alloc,ok}, list, returns ok and server([R|Free], updates the lists, delete({R,From}, Allocated)); or it returns error. false ->From ! {resource_alloc,error}, server(Free, Allocated) The server call loops. end. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94p Objectives: Understand a non-trivial server implementation In the lecture: Explain the techniques -------------------------------------------------------------------------------- PPJ-94q Scala: object-oriented and functional language Scala: Object-oriented language (like Java, more compact notation), augmented by functional constructs (as in SML); object-oriented execution model (Java) functional constructs: * nested functions, higher order functions, currying, case constructs based on pattern matching * functions on lists, streams,... provided in a big language library * parametric polymorphism; restricted local type inference object-oriented constructs: * classes define all types (types are consequently oo - including basic types), subtyping, restrictable type parameters, case classes * object-oriented mixins (traits) general: * static typing, parametric polymorphism and subtyping polymorphism * very compact functional notation * complex language, and quite complex language description * compilable and executable together with Java classes * since 2003, author: Martin Odersky, www.scala.org, docs.scala-lang.org (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94q Objectives: Overview over properties of Scala In the lecture: Brief explanations are given -------------------------------------------------------------------------------- PPj-94r Actors in Scala (1) An actor is a lightweight process: Example: orders and cancellations * actor { body } creates a val orderMngr = actor { process that executes body while (true) * asynchronous message passing receive { case Order(sender, item) => * send: p ! msg puts msg into p's val o = mailbox handleOrder(sender,item) sender ! Ack(o) * receive operation searches the case Cancel(sender, o) => mailbox for the first message that if (o.pending) { matches one of the case patterns cancelOrder(o) (as in Erlang) sender ! Ack(o) * case x is a catch-all pattern } else sender ! NoAck case x => junk += x } } val customer = actor { [P. Haller, M. Odersky: Actors That Unify orderMngr ! Order(self, myItem) Threads and Events; in A.L. Murphy and J. receive { Vitek (Eds.): COORDINATION 2007, LNCS case Ack(o) => ... 4467, pp. 171endash 190, 2007. (c) Springer- Verlag Berlin Heidelberg 2007] } } (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94r Objectives: Understand actors in Scala In the lecture: Explain * the constructs using the example, * asynchronous message passing via unordered mailbox * sender is explicitly transmitted for reply: common pattern -------------------------------------------------------------------------------- PPj-94s Actors in Scala (2) Constructs used to simplify replying: Example: orders and cancellations * The sender of a received message val orderMngr = actor { is stored in sender while (true) * reply(msg) sends msg to receive { sender case Order(item) => val o = * a !? msg sends msg to a, waits handleOrder(sender,item) for a reply, and returns it. reply(Ack(o)) case Cancel(o) => if (o.pending) { cancelOrder(o) reply(Ack(o)) } else reply(NoAck) case x => junk += x } } val customer = actor { [P. Haller, M. Odersky: Actors That Unify orderMngr !? Order(myItem) Threads and Events; in A.L. Murphy and J. match { Vitek (Eds.): COORDINATION 2007, LNCS case Ack(o) => ... 4467, pp. 171endash 190, 2007. (c) Springer- Verlag Berlin Heidelberg 2007] } } (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 94s Objectives: Scala provides simplifying notations In the lecture: Explain the simplifying constructs -------------------------------------------------------------------------------- PPJ-95 11. Check your knowledge (1) Introduction 1. Explain the notions: sequential, parallel, interleaved, concurrent execution of processes. 2. How are Threads created in Java (3 steps)? Properties of Parallel Programs 3. Explain axioms and inference rules in Hoare Logic. 4. What does the weakest precondition wp (s, Q) = P mean? 5. Explain the notions: atomic action, at-most-once property. 6. How is interference between processes defined? 7. How is non-interference between processes proven? 8. Explain techniques to avoid interference between processes. Monitors 9. Explain how the two kinds of synchronization are used in monitors. 10.Explain the semantics of condition variables and the variants thereof. 11.Which are the 3 reasons why a process may wait for a monitor? 12.How do you implement several conditions with a single condition variable? (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 95 Objectives: Understand and repeat the material In the lecture: * Answer some of the questions. -------------------------------------------------------------------------------- PPJ-95a Check your knowledge (2) 13.Signal-and-continue requires loops to check waiting-conditions. Why? 14.Explain the properties of monitors in Java. 15.When can notify be used instead of notifyAll? 16.Where does a monitor invariant hold? Where has it to be proven? 17.Explain how monitors are systematically developed in 5 steps. 18.Formulate a monitor invariant for the readers/writers scheme? 19.Explain the development steps for the method "Rendezvous of processes". 20.How are waiting conditions and release operations inserted when using the method of counting variables? Barriers 21.Explain duplication of distance at the example prefix sums. 22.Explain the barrier rule; explain the flag rules. 23.Describe the tree barrier. 24.Describe the symmetric dissemination barrier. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 95a Objectives: Understand and repeat the material In the lecture: * Answer some of the questions. -------------------------------------------------------------------------------- PPJ-96 Check your knowledge (3) Data parallelism 25.Explain how list ends are found in parallel. 26.Show iteration spaces for given loops and vice versa. 27.Explain which dependence vectors may occur in sequential (parallel) loops. 28.Explain the SRP transformations. 29.How are the transformation matrices used? 30.Which transformations can be used to parallelize the inner loop if the dependence vectors are (0,1) and (1,0)? 31.How are bounds of nested loops described formally? Asynchronous messages 32.Explain the notion of a channel and its operations. 33.Explain typical channel structures. 34.Explain channel structures for the client/server paradigm. 35.What problem occurs if server processes receive each from several channels? 36.Explain the notion of conversation sequences. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 96 Objectives: Understand and repeat the material In the lecture: * Answer some of the questions. -------------------------------------------------------------------------------- PPJ-97 Check your knowledge (4) 37.Which operations does a node execute when it is part of a broadcast in a net? 38.Which operations does a node execute when it is part of a probe-and-echo? 39.How many messages are sent in a probe-and-echo scheme? Messages in distributed systems 40.Explain the worker paradigm. 41.Describe the process interface for distributed branch-and-bound. 42.Explain the technique for termination in a ring. Synchronous messages 43.Compare the fundamental notions of synchronous and asynchronous messages. 44.Explain the constructs for selective wait with synchronous messages. 45.Why are programs based on synchronous messages more compact and less redundant than those with asynchronous messages? 46.Describe a server for resource allocation according to the scheme for synchronous messages. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 97 Objectives: Understand and repeat the material In the lecture: * Answer some of the questions. -------------------------------------------------------------------------------- PPJ-98 Check your knowledge (5) Concurrent and functional programming 47.Explain why paradigms in functional and concurrent programming match well. 48.What are benefits of stream programming? 49.Compare implementations of the Sieve of Eratosthenes using streams or CSP. 50.Explain concurrency in Erlang, in particular selective receive. 51.Explain the characteristics of Scala, in particular its Actors. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Parallel Programming WS 2014/2015 / Slide 98 Objectives: Understand and repeat the material In the lecture: * Answer some of the questions. --------------------------------------------------------------------------------