CS 152 Computer Architectureand Engineering Lecture 19: Synchronization andSequential ConsistencyKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.cs.berkeley.edu/~cs1524/17/20082CS152-Spring!08Summary: Multithreaded CategoriesTime (processor cycle)Superscalar Fine-Grained Coarse-GrainedMultiprocessingSimultaneousMultithreadingThread 1Thread 2Thread 3Thread 4Thread 5Idle slot4/17/20083CS152-Spring!081101001000100001978 1980 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 2006Performance (vs. VAX-11/780) 25%/year52%/year??%/yearUniprocessor Performance (SPECint)• VAX : 25%/year 1978 to 1986• RISC + x86: 52%/year 1986 to 2002• RISC + x86: ??%/year 2002 to presentFrom Hennessy and Patterson,Computer Architecture: A QuantitativeApproach, 4th edition, 20063X4/17/20084CS152-Spring!08Déjà vu all over again?“… today’s processors … are nearing an impasse as technologies approach thespeed of light..”David Mitchell, The Transputer: The Time Is Now (1989)• Transputer had bad timing (Uniprocessor performance!)" Procrastination rewarded: 2X seq. perf. / 1.5 years• “We are dedicating all of our future product development to multicore designs.… This is a sea change in computing”Paul Otellini, President, Intel (2005)• All microprocessor companies switch to MP (2X CPUs / 2 yrs)" Procrastination penalized: 2X sequential perf. / 5 yrs64424Threads/chip8211Threads/Processor8224Processors/chipSun/’07IBM/’07Intel/’07AMD/’07Manufacturer/Year4/17/20085CS152-Spring!08symmetric• All memory is equally far away from all processors• Any processor can do any I/O (set up a DMA transfer)Symmetric MultiprocessorsMemoryI/O controllerGraphicsoutputCPU-Memory busbridgeProcessorI/O controller I/O controllerI/O busNetworksProcessor 4/17/20086CS152-Spring!08SynchronizationThe need for synchronization arises whenever there are concurrent processes in a system(even in a uniprocessor system)Forks and Joins: In parallel programming, a parallel process may want to wait until several events have occurredProducer-Consumer: A consumer process must wait until the producer process has produced dataExclusive use of a resource: Operating system has to ensure that only one process uses a resource at a given timeproducerconsumerforkjoinP1P24/17/20087CS152-Spring!08A Producer-Consumer ExampleThe program is written assuminginstructions are executed in order.Producer posting Item x:Load Rtail, (tail)Store (Rtail), xRtail=Rtail+1Store (tail), RtailConsumer:Load Rhead, (head)spin: Load Rtail, (tail)if Rhead==Rtail goto spinLoad R, (Rhead)Rhead=Rhead+1Store (head), Rheadprocess(R)ProducerConsumertail head RtailRtailRheadRProblems?4/17/20088CS152-Spring!08A Producer-Consumer ExamplecontinuedProducer posting Item x:Load Rtail, (tail)Store (Rtail), xRtail=Rtail+1Store (tail), RtailConsumer:Load Rhead, (head)spin: Load Rtail, (tail)if Rhead==Rtail goto spinLoad R, (Rhead)Rhead=Rhead+1Store (head), Rheadprocess(R)Can the tail pointer get updatedbefore the item x is stored?Programmer assumes that if 3 happens after 2, then 4happens after 1.Problem sequences are:2, 3, 4, 14, 1, 2, 312344/17/20089CS152-Spring!08Sequential ConsistencyA Memory Model“ A system is sequentially consistent if the result ofany execution is the same as if the operations of allthe processors were executed in some sequential order, and the operations of each individual processorappear in the order specified by the program” Leslie LamportSequential Consistency = arbitrary order-preserving interleavingof memory references of sequential programsMP P P P P P4/17/200810CS152-Spring!08Sequential ConsistencySequential concurrent tasks: T1, T2Shared variables: X, Y (initially X = 0, Y = 10)T1: T2:Store (X), 1 (X = 1) Load R1, (Y) Store (Y), 11 (Y = 11) Store (Y’), R1 (Y’= Y) Load R2, (X) Store (X’), R2 (X’= X)what are the legitimate answers for X’ and Y’ ?(X’,Y’) # {(1,11), (0,10), (1,10), (0,11)} ?4/17/200811CS152-Spring!08Sequential ConsistencySequential consistency imposes more memory orderingconstraints than those imposed by uniprocessorprogram dependencies ( ) What are these in our example ?T1: T2:Store (X), 1 (X = 1) Load R1, (Y) Store (Y), 11 (Y = 11) Store (Y’), R1 (Y’= Y) Load R2, (X) Store (X’), R2 (X’= X)Does (can) a system with caches or out-of-orderexecution capability provide a sequentially consistentview of the memory ?more on this later4/17/200812CS152-Spring!08Multiple Consumer ExampleProducer posting Item x:Load Rtail, (tail)Store (Rtail), xRtail=Rtail+1Store (tail), RtailConsumer:Load Rhead, (head)spin: Load Rtail, (tail)if Rhead==Rtail goto spinLoad R, (Rhead)Rhead=Rhead+1Store (head), Rheadprocess(R)What is wrong with this code?Critical section:Needs to be executed atomicallyby one consumer ! lockstail headProducer RtailConsumer1 R RheadRtailConsumer2 R RheadRtail4/17/200813CS152-Spring!08Locks or SemaphoresE. W. Dijkstra, 1965A semaphore is a non-negative integer, with thefollowing operations:P(s): if s>0, decrement s by 1, otherwise waitV(s): increment s by 1 and wake up one of the waiting processesP’s and V’s must be executed atomically, i.e., without• interruptions or• interleaved accesses to s by other processorsinitial value of s determines the maximum no. of processesin the critical sectionProcess iP(s) <critical section>V(s)4/17/200814CS152-Spring!08Implementation of SemaphoresSemaphores (mutual exclusion) can be implemented using ordinary Load and Store instructions in the Sequential Consistency memory model. However, protocols for mutual exclusion are difficult to design...Simpler solution:atomic read-modify-write instructionsTest&Set (m), R: R $ M[m];if R==0 then M[m] $ 1;Swap (m), R:Rt $ M[m];M[m] $ R;R $ Rt;Fetch&Add (m), RV, R:R $ M[m];M[m] $ R + RV;Examples: m is a memory location, R is a register4/17/200815CS152-Spring!08CS152 Administrivia• CS194-6 class description• Quiz results• Quiz common mistakes4/17/200816CS152-Spring!08CS194-6 Digital Systems ProjectLaboratory•Prerequisites: EECS 150•Units/Credit: 4, may be taken for a grade.•Meeting times: M 10:30-12 (lecture), F 10-12 (lab)•Instructor: TBA•Fall 2008CS 194 is a capstone digital design project course. The projects are teamprojects, with 2-4 students per team. Teams propose a project in adetailed design
View Full Document
Unlocking...