Slide 1Changing a major assumptionA simplified view of historyWhat to do with multiple processors?Parallelism vs. ConcurrencyParallelism ExampleConcurrency ExampleAn analogyShared memory with ThreadsShared memory with ThreadsOther modelsJava Threads (at a high level)Parallelism idea: First approachPartial Code for first attempt (with Threads)Join: Our ‘wait’ method for ThreadsProblems with our current approachImprovementsNaïve algorithm that doesn’t workA better idea… look familiar?Divide-and-conquer really worksCode would look something like this (still using Java Threads)Being realisticHalf the threads createdThat library, finallyDifferent terms, same basic ideaExample: final version (minus imports)Getting good results in practiceCSE332: Data AbstractionsLecture 19: Introduction to Multithreading and Fork-Join ParallelismTyler RobisonSummer 20101Changing a major assumption2So 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 & opportunitiesProgramming: Divide work among threads of execution and coordinate (synchronize) among themAlgorithms: 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)Writing correct and efficient multithreaded code is often much more difficult than for single-threaded (i.e., sequential) codeA simplified view of history3From roughly 1980-2005, desktop computers got exponentially faster at running sequential programsAbout twice as fast every couple yearsBut nobody knows how to continue thisIncreasing clock rate generates too much heatRelative cost of memory access is too highBut we can keep making “wires exponentially smaller” (Moore’s “Law”), so put multiple processors on the same chip (“multicore”)What to do with multiple processors?4Next computer you buy will likely have 4 processorsWait 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 timeAlready do that? Yes, but with time-slicingDo multiple things at once in one programOur focus – more difficultRequires rethinking everything from asymptotic complexity to how to implement data-structure operationsParallelism vs. Concurrency5Note: These terms are not yet standard, but the difference in perspective is essentialMany programmers confuse themRemember that Parallelism != ConcurrencyParallelism: Use more resources for a faster answerConcurrency: Correctly and efficiently allow simultaneous access to something (memory, printer, etc.)There is some connection:Many programmers use threads for bothIf parallel computations need access to shared resources, then something needs to manage the concurrencyCSE332: Next few lectures on parallelism, then a few on concurrencyParallelism Example6Parallelism: Increasing throughput by using additional computational resources (code running simultaneously on different processors)Ex: We have a huge array of numbers to add up; split between 4 peopleExample in pseudocode (not Java, yet) below: sum elements of an arrayNo such ‘FORALL’ construct, but we’ll see something similarIf you had 4 processors, might get roughly 4x speedupint sum(int[] arr){ res = new int[4]; len = arr.length; FORALL(i=0; i < 4; i++) { //parallel iterations res[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 Example7Concurrency: Allowing simultaneous or interleaved access to shared resources from multiple clientsEx: Multiple threads accessing a hash-table, but not getting in each others’ waysExample in pseudo-code (not Java, yet): chaining hash-tableEssential correctness issue is preventing bad inter-leavingsEssential performance issue not preventing good concurrencyOne ‘solution’ to preventing bad inter-leavings is to do it all sequentiallyclass 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 insertion re-enable access to arr[bucket]; } V lookup(K key) {(like insert, but can allow concurrent lookups to same bucket) }}An analogy8CSE142 idea: Writing a program is like writing a recipe for a cookOne step at a timeParallelism:Have lots of potatoes to slice? Hire helpers, hand out potatoes and knivesBut we can go too far: if we had 1 helper per potato, we’d spend too much time coordinatingConcurrency:Lots of cooks making different things, but only 2 stove burnersWant to allow simultaneous access to both burners, but not cause spills or incorrect burner settingsShared memory with Threads9The model we will assume is shared memory with explicit threadsOld story: A running program hasOne call stack (with each stack frame holding local variables) One program counter (current statement executing)Static fieldsObjects (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 counterNo access to another thread’s local variablesThreads can (implicitly) share static fields / objectsTo communicate, write somewhere another thread readsShared memory with Threads 10…Heap for all objects and static fieldsThreads, each with own unshared call stack and current statement (pc for “program counter”)– local variables are numbers/null or heap referencespc=0x……pc=0x……pc=0x……Other models11We will focus on shared memory, but you should know several other models existMessage-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 telephonesDataflow: Programmers write programs in terms of a DAG and a node executes after all of its predecessors in the graphCooks wait to be handed results of previous stepsData parallelism: Have primitives for things like “apply function to every element of an array in parallel”…Java Threads (at
View Full Document