Principles Of Concurrency And Parallelism
Principles of Concurrency andParallelismSuresh uresh/CS390Cwww.piazza.com (CS390PCP)CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 121
Course Overview Introduction to Concurrency and Parallelism Basic Concepts Interaction Models for Concurrent Tasks Elements of Concurrency Threads, Co-routines, EventsCorrectness Shared Memory, Message-Passing, Data ParallelData races, linearizability, deadlocks, livelocks, serializabilityPerformance Measures Cost models, latency, throughput, speedup, efficiencyCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Course Overview Abstractions Shared memory, message-passing, data parallel Erlang, MPI, Concurrent ML, CudaPosix, Cilk, OpenMPSynchronous vs. asynchronous communication Data Structures and Algorithms Queues, Heaps, Trees, Lists Sorting, Graph AlgorithmsProcessor Architectures Relaxed memory models GPGPUCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Grading and Evaluation Scribe Four to five small programming projects Transcribe and expand lecture notes to a cohesivenarrative. Provide additional examples and bibliography.Programming exercises will be in different languages anduse different tools.One midterm and final examCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
IntroductionWhat is Concurrency?Traditionally, the expression of a task in the form ofmultiple, possibly interacting subtasks, that maypotentially be executed at the same time.CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
IntroductionWhat is Concurrency? Concurrency is a programming concept. It says nothing about how the subtasks are actuallyexecuted. Concurrent tasks may be executed serially or in paralleldepending upon the underlying physical resourcesavailable.CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Concurrency?Concurrency plays a critical role in sequential as wellas parallel/distributed computing environments.It provides a way to think and reason aboutcomputations, rather than necessarily a way ofimproving overall performance.CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Concurrency? In a serial environment, consider the followingsimple example of a server, serving requests fromclients (e.g., a web server and web clients)request 2Non-concurrentserial serverrequest 1t 0CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Let us process requests seriallyrequest 2request 2request 1t 0request 1t 6t 8request 2request 1Total completion time 8 units, Average service time (6 8)/2 7 unitsCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Try a concurrent server now!request 1request 2t 0request 1request 2t 1request 1request 2t 2CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
We reduced mean service time!t 3t 4t 8Total completion time 8 units, Average service time (4 8)/2 6 unitsCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Concurrency? The lesson from the example is quite simple: Not knowing anything about execution times, we canreduce average service time for requests by processingthem concurrently!But what if I knew the service time for eachrequest? Would “shortest job first” not minimize average servicetime anyway? Aha! But what about the poor guy standing at the backnever getting any service (starvation/ fairness)?CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Concurrency? Notions of service time, starvation, and fairnessmotivate the use of concurrency in virtually allaspects of computing: Operating systems are multitasking Web/database services handle multiple concurrentrequests Browsers are concurrent Virtually all user interfaces are concurrentCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Concurrency? In a parallel context, the motivations forconcurrency are more obvious: Concurrency parallel execution performanceCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
What is Parallelism? Traditionally, the execution of concurrent tasks onplatforms capable of executing more than one taskat a time is referred to as “parallelism”Parallelism integrates elements of execution -- andassociated overheadsFor this reason, we typically examine thecorrectness of concurrent programs andperformance of parallel programs.CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Parallelism? We can broadly view the resources of a computerto include the processor, the data-path, the memorysubsystem, the disk, and the network.Contrary to popular belief, each of these resourcesrepresents a major bottleneck.Parallelism alleviates all of these bottlenecks.CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Parallelism? Starting from the least obvious: I/O (disks) represent major bottlenecks in terms of theirbandwidth and latency Parallelism enables us to extract data from multiple disks atthe same time, effectively scaling the throughput of the I/Osubsystem An excellent example is the large server farms (severalthousand computers) that ISPs maintain for serving content(html, movies, music, mail).CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Parallelism? Most programs are memory bound – i.e., they operate at a smallfraction of peak CPU performance (10 – 20%)They are, for the most part, waiting for data to come from thememory.Parallelism provides multiple pathways to memory – effectivelyscaling memory throughput as well!CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Why Parallelism? The process itself is the most obvious bottleneck.Moore's law states that the component count on a die doublesevery 18 months.Contrary to popular belief, Moore's law says nothing aboutprocessor speed.What does one do with all of the available “components” on thedie?CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Parallelism in Processors Processors increasingly pack multiple cores into a single die.Why?CS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Parallelism in Processors The primary motivation for multicore processors, contrary tobelief is not speed, it is power.Power consumption scales quadratically in supply voltage.Reduce voltage, simplify cores, and have more of them – this isthe philosophy of multicore processorsCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
Architecture TrendsCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 1222
UtilizationCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 1223
Circa 2001IBM Power 4First non-embedded processor withmultiple coresUnified L2 cache, 1.3 GHz24Tuesday, January 10, 12
Circa 2010Tilera100 cores32 MB aggregate cachedistributed coherency25Tuesday, January 10, 12
Circa 2010No cache coherencyacross multiple cores26Tuesday, January 10, 12
Circa 2010Azul864 cores16 x 54 coresFull cache coherenceBut, slower processors(roughly 1/3 speed of Core2 duo)27Tuesday, January 10, 12
Why Parallel? Sometimes, we just do not have a choice – the data associatedwith the computations is distributed, and it is not feasible tocollect it all. What are common buying patterns at Walmart across thecountry?In such scenarios, we must perform computations in adistributed environment. Distributed programming shares many of the same issues asparallel programming, but there are important differences latency and throughput scalesfailure modelsCS390C: Principles of Concurrency and ParallelismTuesday, January 10, 12
CS390C: Principles of Concurrency and Parallelism Course Overview Introduction to Concurrency and Parallelism Basic Concepts Interaction Models for Concurrent Tasks Shared Memory, Message-Passing, Data Parallel Elements of Concurrency Threads, Co-routines, Events Correctness Data races, linearizability, deadlocks, livelocks, serializability
Parallelism within the Gradient Computation Try to compute the gradient samples themselvesin parallel Problems: We run this so many times, we will need to synchronize a lot Typical place to use: instruction level parallelism, SIMD parallelism And distributed parallelism when using model/pipeline parallelism x t 1 x t rf (x t .
CS378 TYPES OF PARALLELISM Task parallelism Distributes multiple tasks (jobs) across cores to be performed in parallel Data parallelism Distributes data across cores to have sub-operations performed on that data to facilitate parallelism of a single task Note: Parallelism is frequently accompanied by concurrency (i.e. multiple cores still have multiple threads operating on the data)
Concurrency, Parallelism and Coroutines Parallelism in C 17 The Coroutines TS The Concurrency TS Coroutines and Parallel algorithms Executors Anthony WilliamsJust Softw
Query Parallelism and the Explain Facility TBSCAN, IXSCAN (row-organized processing only) Optimizer determines these options for row-organized parallelism Determined at runtime for column-organized parallelism SCANGRAN (n): (Intra-Partition Parallelism Scan Granularity) SCANTYPE: (Intra-Partition Parallelism Scan Type)
GPU parallelism Will Landau A review of GPU parallelism Examples of parallelism Vector addition Pairwise summation Matrix multiplication K-means clustering Markov chain Monte Carlo A review of GPU parallelism The single instruction, multiple data (SIMD) paradigm I SIMD: apply the same command to multiple places in a dataset. for( i 0; i 1e6 .
devoted to designing concurrency control methods for RTDBS and to evaluating their performance. Most of these algorithms use serializability as correctness criteria and are based on one of the two basic concurrency control mechanisms: Pessimistic Concurrency Control [3, 12] or Optimistic Concurrency Control [2, 4, 5, 6, 11]. However, 2PL
Concurrency control Concurrency control in DBS methods for scheduling the operations of database transactions in a way which guarantees serializability of all transactions ("between system start and shutdown") Primary concurrency control methods – Locking (most important) – Optimistic concurrency control – Time stamps
Reading music from scratch; Easy, effective finger exercises which require minimal reading ability; Important musical symbols; Your first tunes; Audio links for all tunes and exercises; Key signatures and transposition; Pre scale exercises; Major and minor scales in keyboard and notation view; Chord construction; Chord fingering; Chord charts in keyboard view; Arpeggios in keyboard and .
