CSE332: Data AbstractionsLecture 18: Introduction to Multithreading and Fork-Join ParallelismDan GrossmanSpring 2010Changing a major assumptionSo far in 142, 143, 311, and 332, we have assumedOne thing happened at a timeCalled sequential programming – everything part of one sequenceRemoving this assumption creates major challenges & opportunities– Programming: Divide work among threads of execution and coordinate (synchronize) among them– Algorithms: How can parallel activity provide speed-up (more throughput: work done per unit time)– Data structures: May need to support concurrent access (multiple threads operating on data at the same time)Spring 2010 2CSE332: Data AbstractionsA simplified view of historyWriting correct and efficient multithreaded code is often much more difficult than for single-threaded (i.e., sequential) code– Especially in common languages like Java and C– So typically stay sequential if possibleFrom roughly 1980-2005, desktop computers got exponentially faster at running sequential programs– About twice as fast every couple yearsBut nobody knows how to continue this– Increasing clock rate generates too much heat– Relative cost of memory access is too high– But we can keep making “wires exponentially smaller”(Moore’s “Law”), so put multiple processors on the same chip (“multicore”)Spring 2010 3CSE332: Data AbstractionsWhat to do with multiple processors?• Next computer you buy will likely have 4 processors– Wait a few years and it will be 8, 16, 32, …– The chip companies have decided to do this (not a “law”)• What can you do with them?– Run multiple totally different programs at the same time• Already do that? Yes, but with time-slicing– Do multiple things at once in one program• Our focus – more difficult• Requires rethinking everything from asymptotic complexity to how to implement data-structure operationsSpring 2010 4CSE332: Data AbstractionsParallelism ExampleParallelism: Increasing throughput by using additional computational resources (code running simultaneously)Example in pseudocode (not Java, yet): sum elements of an array– This example is bad style for reasons we’ll see– If you had 4 processors, might get roughly 4x speedupSpring 2010 5CSE332: Data Abstractionsint sum(int[] arr){res = new int[4];len = arr.length;FORALL(i=0; i < 4; i++) { //parallel iterationsres[i] = help(arr,i*len/4,(i+1)*len/4);}return res[0]+res[1]+res[2]+res[3];}int help(int[] arr, int lo, int hi) {result = 0;for(j=lo; j < hi; j++)result += arr[j];return result;}Concurrency ExampleConcurrency: Allowing simultaneous or interleaved access to shared resources from multiple clientsExample in pseudocode (not Java, yet): chaining hashtable– Essential correctness issue is preventing bad interleavings– Essential performance issue not preventing good concurrencySpring 2010 6CSE332: Data Abstractionsclass Hashtable<K,V> {…Hashtable(Comparator<K> c, Hasher<K> h) { … };void insert(K key, V value) {int bucket = …;prevent-other-inserts/lookups in table[bucket];do the insertionre-enable access to arr[bucket];}V lookup(K key) {(like insert, but can allow concurrent lookups to same bucket)}}Parallelism vs. ConcurrencyNote: These terms are not yet standard, but the difference in perspective is essential– Many programmers confuse themParallelism: Use more resources for a faster answerConcurrency: Correctly and efficiently allow simultaneous accessThere is some connection:– Many programmers use threads for both– If parallel computations need access to shared resources, then something needs to manage the concurrencyCSE332: Next 3-4 lectures on parallelism, then 3-4 on concurrencySpring 2010 7CSE332: Data AbstractionsAn analogyCSE142 idea: Writing a program is like writing a recipe for a cook– One cook who does one thing at a time!Parallelism:– Have lots of potatoes to slice? – Hire helpers, hand out potatoes and knives– But not too many chefs or you spend all your time coordinatingConcurrency:– Lots of cooks making different things, but only 4 stove burners– Want to allow simultaneous access to all 4 burners, but not cause spills or incorrect burner settingsSpring 2010 8CSE332: Data AbstractionsShared memoryThe model we will assume is shared memory with explicit threadsOld story: A running program has– One call stack (with each stack frame holding local variables) – One program counter (current statement executing)– Static fields– Objects (created by new) in the heap (nothing to do with heap data structure)New story:– A set of threads, each with its own call stack & program counter• No access to another thread’s local variables– Threads can (implicitly) share static fields / objects•To communicate, write somewhere another thread readsSpring 2010 9CSE332: Data AbstractionsShared memory Spring 2010 10CSE332: Data Abstractions…Heap for all objects and static fieldsThreads, each with ownunshared call stack and currentstatement (pc for “program counter”)– local variables are numbers/nullor heap referencespc=0x……pc=0x……pc=0x……Other modelsWe will focus on shared memory, but you should know several other models exist and have their own advantages• Message-passing: Each thread has its own collection of objects. Communication is via explicit messages; language has primitives for sending and receiving them.– Cooks working in separate kitchens, with telephones• Dataflow: Programmers write programs in terms of a DAG and a node executes after all of its predecessors in the graph– Cooks wait to be handed results of previous steps• Data parallelism: Have primitives for things like “apply function to every element of an array in parallel”•…Spring 2010 11CSE332: Data AbstractionsSome Java basics• Many languages/libraries provide primitives for creating threadsand synchronizing them• Will show you how Java does it– Many primitives will be delayed until we study concurrency– We will not use Java threads much in project 3 for reasons lecture will explain, but it’s still worth seeing them first• Steps to creating another thread:1. Define a subclass C of java.lang.Thread, overriding run2. Create an object of class C3. Call that object’s start method•Not run, which would just be a normal method callSpring 2010 12CSE332: Data AbstractionsParallelism idea• Example: Sum elements of an array (presumably large)• Use 4 threads, which each sum 1/4 of the