08-PPMI: Basic Building Blocks

1 .CSC2/458 Parallel and Distributed Systems PPMI: Basic Building Blocks Sreepathi Pai February 13, 2018 URCS 

2 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution 

3 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution 

4 .Very Simplified Programmer’s View of Multicore core core core core core PC PC PC PC PC • Multiple program counters (PC) • MIMD machine • To what do we set these PCs? • Can the hardware do this automatically for us? 

5 .Automatic Parallelization to the Rescue? for(i = 0; i < N; i++) { for(j = 0; j < i; j++) { // something(i, j) } } • Assume a stream of instructions from a single-threaded program • How do we split this stream into pieces? 

6 .Thread-Level Parallelism • Break stream into long continuous streams of instructions • Much bigger than issue window on superscalars • 8 instructions vs hundreds • Streams are largely independent • Best performance on current hardware • “Thread-Level Parallelism” • ILP • DLP • MLP 

7 .Parallelization Issues • Assume we have a parallel algorithm • Work Distribution • How to split up work to be performed among threads? • Communication • How to send and receive data between threads? • Synchronization • How to coordinate different threads? • A form of communication 

8 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution 

9 .Types of Parallel Programs (Simplified) Let’s assume all parallel programs consist of “atomic” tasks. • All tasks identical, all perform same amount of work • Count words per page (many pages) • Matrix Multiply, 2D-convolution, most “regular” programs • All tasks identical, but perform different amounts of work • Count words per chapter (many chapters) • Graph analytics, most “irregular” programs • Different tasks • Pipelines • Servers (Tasks: Receive Request, Process Request, Respond to Request) 

10 .Scheme 1: One task per thread, same work Count words per page of a book. 

11 .Work assigned once to threads (Static) 

12 .How many threads? • As many as tasks • As many as cores • Less than cores • More than cores 

13 .Hardware and OS Limitations • As many as tasks • Too many, OS scheduler limitations • As many as cores • Reasonable default • Less than cores • If hardware bottleneck is saturated • More than cores • May help to cope with lack of ILP 

14 .Scheme 2: Multiple tasks per thread, differing work Count words per chapter of a book. 

15 .Static Work Assignment Assign chapters evenly. 

16 .Static Work Assignment Chapters are of different lengths leading to load imbalance 

17 .Assigning chapters by size of chapters • Not always possible • May not know size of all chapters • Bin-packing problem • NP-hard 

18 .Dynamic (Greedy) Balancing • Create a set of worker threads (thread pool) • Place work (i.e. chapters) into a parallel worklist • Each worker thread pulls work off the worklist • When it finishes a chapter, it pulls more work off the worklist 

19 .Dynamic Balancing Parallel Worklist 

20 .Generalized Parallel Programs • Threads can create additional work (“tasks”) • Tasks may be dependent on each other • Form a dependence graph • Same ideas as thread pool • Except only “ready” tasks are pulled off worklist • As tasks finish, their dependents are marked ready • May have thread-specific worklists • To prevent contention on main worklist 

21 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution 

22 .Multiprocessing • Simplest way to take advantage of multiple cores • Run multiple processes • fork and wait • Traditional way in Unix • “Processes are cheap” • Not cheap in Windows • Nothing-shared model • Child inherits some parent state • Only viable model available in some programming languages • Python • Shared nothing: Communication between processes? 

23 .Communication between processes • Unix Interprocess Communication (IPC) • Filesystem • Pipes (anonymous and named) • Unix sockets • Semaphores • SysV Shared Memory 

24 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution 

25 .Multithreading • One process • Process creates threads (“lightweight processes”) • How is a thread different from a process? [What minimum state does a thread require?] • Everything shared model • Communication • Read and write to memory • Relies on programmers to think carefully about access to shared data • Tricky 

26 .Multithreading Programming Models Roughly in (decreasing) order of power and complexity: • POSIX threads (pthreads) • C++11 threads may be simpler than this • Thread Building Blocks from Intel • Cilk • OpenMP 

27 .POSIX Threads on Linux • Processes == Threads for scheduler in Linux • 1:1 threading model • See OS textbook • pthreads provided as a library • gcc test.c -lpthread • OS scheduler can affect performance significantly • Especially with user-level threads 

28 .Multithreading Components • Thread Management • Creation, death, waiting, etc. • Communication • Shared variables (ordinary variables) • Condition Variables • Synchronization • Mutexes (Mutual Exclusion) • Barriers • (Hardware) Read-Modify-Writes or “Atomics” 

29 .Outline Multiprocessor Machines Archetypes of Work Distribution Multiprocessing Multithreading and POSIX Threads Non-blocking I/O or ‘Asynchronous’ Execution