© University of Colorado, 2010Eight Simple Rules for Designing Concurrent SystemsKenneth M. AndersonUniversity of Colorado, BoulderCSCI 5828 — Lecture 10 — 02/11/20101Lecture GoalsReview of material in Chapter 4 of BreshearsEight Simple Rules…2An Art Not a Science…In the chapter, Breshears presents eight guidelines for designing concurrent applicationsWe make use of guidelines as designing multithreaded applications is still more of an art than a scienceThat is not to say that we don’t have methodologies or techniques to draw uponwe just covered the main approaches in the prior lecturesBut, for any particular program, there are multiple ways to make it concurrent and it may not be clear which way to go3Rule 1Identify Truly Independent ComputationsIf you can’t identify (in a single threaded application)computations that can be done in parallel, you’re out of luckAnd, in last lecture, we looked at situations that indeed can’t be made parallelBut opportunities will be there if you’re willing to look hard enough: from the real world, DVD rental fulfillmentpulling discs, packing them, shipping them: all independentConsider: File Browsers: what might be independent?4Rule 2Implement Concurrency at the Highest Level PossibleWhen discussing “What’s Not Parallel” a common refrain was “you can’t make this parallel, so see if its part of a larger computation that CAN be made parallel”This is such good advice, it was promoted to being a guideline!Two approaches: bottom up, top down5Rule 2: Bottom UpOur methodology says to create a concurrent programstart with a tuned, single-threaded programand use a profiler to find out where it spends most of its timeIn the bottom-up approach, you start at those “hot spots” and work up; typically, a hotspot will be a loop of some sortSee if you can thread the loopIf not, move up the call chain, looking for the next loop and see if it can be made parallel…If so, still look up the call chain for other opportunities, first.Why? Granularity! You want coarse-grained tasks for your threads6Rule 2: Top DownWith knowledge of the location of the hot spotstart by looking at the whole application and see if there are parallelization opportunities on the large-scale structure that contains the hot spotif so, you’ve probably found a nice coarse-grained task to assign to your threadsIf not, move lower in the code towards the hot spot, looking for the first opportunity to make the code concurrent7Rule 3Plan Early for ScalabilityThe number of cores will keep increasingYou should design your system to take advantage of more cores as they become availableMake the number of cores an input variable and design from thereIn particular, designing systems via data decomposition techniques will provide more scalable systemshumans are always finding more data to process!More data, more tasks; if more cores arrive, you’re ready8Rule 4Make use of Thread-Safe Libraries Wherever PossibleFirst, software reuse!Don’t fall prey to Not Invented Here Syndromeif code already exists to do what you need, use it!Second, more libraries are becoming multithread awareThat is, they are being built to perform operations concurrentlyThird, if you make use of libraries, ensure they are thread-safe; if not, you’ll need to synchronize calls to the libraryGlobal variables hiding in the library may prevent even this, if the code is not reentrant ; if so, you may need to abandon it9Rule 5Use the Right Threading ModelAvoid the use of explicit threads if you can get away with itThey are hard to get right, as we’ve seenLook at libraries that abstract away the need for explicit threadsWe’ll be looking at OpenMP and Intel Threading Building Blocks in Chapter 5And, I’ll be discussing Scala’s agent model, Go’s goroutines and Clojure’s concurrency primitivesall of these models hide explicit threads from the programmer10Rule 6Never Assume a Particular Order of ExecutionWith multiple threads, as we’ve seen, the scheduling of atomic statements is nondeterministicIf you care about the ordering of one thread’s execution with respect to another, you have to impose synchronizationBut, to get the best performance, you want to avoid synchronization as much as possiblein particular, you want high granularity tasks that don’t require synchronization; this allows your cores to run as fast as possible on each task they’re given11Rule 7Use Thread-Local Storage Whenever Possible or Associate Locks with specific dataRelated to Rule 6; the more your threads can use thread-local storage, the less you will need synchronizationOtherwise, associate a single lock with a single data itemin which a data item might be a huge data structureThis makes it easier for the developer to understand the system; “if I need to update data item A, then I need to acquire lock A first”12Rule 8Dare to Change the Algorithm for a Better Chance of ConcurrencySometimes a tuned, single-threaded program makes use of an algorithm which is not amenable to parallelizationThey might have picked that algorithm for performance reasonsStrassen’s Algorithm O(n2.81) vs. the triple-nested loop algorithm to perform matrix multiplication O(n3)Change the algorithm used by the single-threaded program to see if you can then make that new algorithm concurrentBUT: when measuring speedup, compare to the original!!13Coming Up NextLecture 11: Good Enough DesignChapter 5 of Pilone & MilesLecture 12: Model-Based Approach to ConcurrencyMaterial will come from optional
View Full Document
Unlocking...