9-Fork-Join Pattern

1 . Fork-Join Pattern Parallel Computing CIS 410/510 Department of Computer and Information Science Lecture 9 – Fork-Join Pattern 

2 . Outline q  What is the fork-join concept? q  What is the fork-join pattern? q  Programming Model Support for Fork-Join q  Recursive Implementation of Map q  Choosing Base Cases q  Load Balancing q  Cache Locality and Cache-Oblivious Algorithms q  Implementing Scan with Fork-Join q  Applying Fork-Join to Recurrences Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 2 

3 . Fork-Join Philosophy When you come to a fork in the road, take it. (Yogi Bera, 1925 –) Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 3 

4 . Fork-Join Concept q  Fork-Join is a fundamental way (primitive) of expressing concurrency within a computation q  Fork is called by a (logical) thread (parent) to create a new (logical) thread (child) of concurrency ❍  Parent continues after the Fork operation ❍  Child begins operation separate from the parent ❍  Fork creates concurrency q  Join is called by both the parent and child ❍  Child calls Join after it finishes (implicitly on exit) ❍  Parent waits until child joins (continues afterwards) ❍  Join removes concurrency because child exits Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 4 

5 . Fork-Join Concurrency Semantics q  Fork-Join is a concurrency control mechanism ❍  Fork increases concurrency ❍  Join decreases concurrency q  Fork-Join dependency rules ❍  A parent must join with its forked children ❍  Forked children with the same parent can join with the parent in any order ❍  A child can not join with its parent until it has joined with all of its children q  Fork-Join creates a special type of DAG ❍  What do they look like? Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 5 

6 . Fork Operation q  Fork creates a child thread q  What does the child do? q  Typically, fork operates by assigning the child thread with some piece of “work” ❍  Child thread performs the piece of work and then exits by calling join with the parent q  Child work is usually specified by providing the child with a function to call on startup q  Nature of the child work relative to the parent is not specified Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 6 

7 . Join Operation q  Joininforms the parent that the child has finished q  Child thread notifies the parent and then exits ❍  Might provide some status back to the parent q  Parent thread waits for the child thread to join ❍  Continues after the child thread joins q  Two scenarios 1. Child joins first, then parent joins with no waiting 2. Parent joins first and waits, child joins and parent then continues Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 7 

8 . Fork-Join Heritage in Unix q  Fork-Join comes from basic forms of creating processes and threads in operating system q  Forking a child process from a parent process ❍  Creates a new child process with fork() ❍  Process state of parent is copied to child process ◆ process ID of parent stored in child process state ◆ process ID of child stored in parent process state ❍  Parent process continues to next PC on fork() return ❍  Child process starts execution at next PC ◆ process ID is automatically set to child process ◆ child can call exec() to overlay another program Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 8 

9 . Fork-Join Heritage in Unix (2) q  Joining a child process with a parent process ❍  Child process exits and parent process is notified ◆ if parent is blocked waiting, it unblocks ◆ if parent is not waiting, some indication is made ◆ child process effectively joins ❍  Parent process calls waitpid() (effectively join) for a particular child process ◆ if the child process has called join(), parent continues ◆ if the child process has not called join(), parent blocks q  Fork-Join also implemented for threads Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 9 

10 . Fork-Join “Hello World” in Unix Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 10 

11 . Fork-Join in POSIX Thread Programming q  POSIX standard multi-threading interface ❍  For general multi-threaded concurrent programming ❍  Largely independent across implementations ❍  Broadly supported on different platforms ❍  Common target for library and language implementation q  Provides primitives for ❍  Threadcreation and management ❍  Synchronization Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 11 

12 . Thread Creation #include <pthread.h> int pthread_create( pthread_t *thread_id, const pthread_attr_t *attribute, void *(*thread_function)(void *),void *arg); q  thread_id ❍  thread’s unique identifier q  attribute ❍  contain details on scheduling policy, priority, stack, ... q  thread_function ❍  function to be run in parallel (entry point) q  arg ❍  arguments for function func Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 12 

13 . Example of Thread Creation void *func(void *arg) { int *I=arg; … main()   }      pthread_create(func)   func()   void main() { int X; pthread_t id; … pthread_create(&id, NULL, func, &X); … } Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 13 

14 . Pthread Termination void pthread_exit(void *status) q  Terminates the currently running thread q  Implicitly called when function called in pthread_create returns Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 14 

15 . Thread Joining int pthread_join( pthread_t thread_id, void **status); q  Waits for thread thread_id to terminate ❍  Either by returning ❍  Or by calling pthread_exit() q  Status receives the return value or the value given as argument to pthread_exit() Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 15 

16 . Thread Joining Example main()   void *func(void *){ …  pthread_create(func)   func()   } pthread_join(id)   pthread_t id; pthread_exit()   int X; … pthread_create(&id, NULL, func, &X); … pthread_join(id, NULL); … Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 16 

17 . General Program Structure q  Encapsulate parallel parts in functions q  Use function arguments to parameterize thread behavior q  Call pthread_create() with the function q  Call pthread_join() for each thread created q  Need to take care to make program “thread safe” Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 17 

18 . Pthread Process Management q  pthread_create() ❍  Creates a parallel thread executing a given function ❍  Passes function arguments ❍  Returns thread identifier q  pthread_exit() ❍  terminates thread. q  pthread_join() ❍  waits for particular thread to terminate Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 18 

19 . Pthreads Synchronization q  Create/exit/join ❍  Provide some coarse form of synchronization ❍  “Fork-join” parallelism ❍  Requires thread creation/destruction q  Need for finer-grain synchronization ❍  Mutex locks ❍  Condition variables Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 19 

20 . Pthreads “Hello World” Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 20 

21 . Fork-Join Pattern q  Control flow divides (forks) into multiple flows, then combines (joins) later q  During a fork, one flow of control becomes two q  Separate flows are “independent” ❍  Does “independent” mean “not dependent” ? ❍  No, it just means that the 2 flows of control “are not constrained to do similar computation” q  During a join, two flows become one, and only this one flow continues Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 21 

22 . Fork-Join Pattern q  Fork-Join directed graph: Fork   Independent work Is it possible for B() and C() to have dependencies Join   between them? Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 22 

23 . Fork-Join Pattern q  Typical divide-and-conquer algorithm implemented with fork-join: Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 23 

24 . Fork-Join Pattern for Divide-Conquer Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 24 

25 . Fork-Join Pattern for Divide-Conquer K  =  2      (2-­‐way  fork-­‐join)   N  =  3      (3  levels  of  fork-­‐join)   Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 25 

26 . Fork-Join Pattern for Divide-Conquer ​2↑3 =8-­‐way  parallelism   Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 26 

27 . Fork-Join Pattern q  Selecting the base case size is critical q  Recursion must go deep enough for plenty of parallelism q  Too deep, and the granularity of sub-problems will be dominated by scheduling overhead q  With K-way fork-join and N levels of fork-join, can have up to KN-way parallelism Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 27 

28 . Fibonacci Example q  Recursive Fibonacci is simple and inefficient long fib ( int n ) { if (n < 2) return 1; else { long x = fib (n-1); long y = fib(n-2); return x + y; } } Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 28 

29 . Fibonacci Example q  Recursive Fibonacci is simple and inefficient q  Are there dependencies between the sub-calls? q  Can we parallelize it? Introduction to Parallel Computing, University of Oregon, IPCC Lecture 9 – Fork-Join Pattern 29