Slide 1Last Time, Lecture 16: GPUsUniprocessor Performance (SPECint)Parallel Processing: Déjà vu all over again?Symmetric MultiprocessorsSynchronizationA Producer-Consumer ExampleA Producer-Consumer Example continuedSequential Consistency A Memory ModelSequential ConsistencySequential ConsistencyMultiple Consumer ExampleLocks or Semaphores E. W. Dijkstra, 1965Implementation of SemaphoresCS152 AdministriviaMultiple Consumers Example using the Test&Set InstructionNonblocking SynchronizationLoad-reserve & Store-conditionalPerformance of LocksIssues in Implementing Sequential ConsistencyMemory Fences Instructions to sequentialize memory accessesUsing Memory FencesMutual Exclusion Using Load/StoreMutual Exclusion: second attemptA Protocol for Mutual Exclusion T. Dekker, 1966Analysis of Dekker’s AlgorithmN-process Mutual Exclusion Lamport’s Bakery AlgorithmAcknowledgementsApril 4, 2011 CS152, Spring 2011CS 152 Computer Architectureand Engineering Lecture 17: Synchronization and Sequential Consistency Krste AsanovicElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.cs.berkeley.edu/~cs152April 4, 2011 CS152, Spring 2011Last Time, Lecture 16: GPUs•Data-Level Parallelism the least flexible but cheapest form of machine parallelism, and matches application demands•Graphics processing units have developed general-purpose processing capability for use outside of traditional graphics functionality (GP-GPUs)•SIMT model presents programmer with illusion of many independent threads, but executes them in SIMD style on a vector-like multilane engine.•Complex control flow handled with hardware to turn branches into mask vectors and stack to remember µthreads on alternate path•No scalar processor, so µthreads do redundant work, unit-stride loads and stores recovered via hardware memory coalescing2April 4, 2011 CS152, Spring 20113CS152-Spring’091101001000100001978 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 Quantitative Approach, 4th edition, 20063XApril 4, 2011 CS152, Spring 2011Parallel Processing:Déjà vu all over again?•“… today’s processors … are nearing an impasse as technologies approach the speed 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 (2+ CPUs/2 yrs) Procrastination penalized: 2X sequential perf. / 5 yrs•Even handheld systems moving to multicore–Nintendo 3DS, iPad 2, (&iPhone5?) have two cores each–Next Playstation Portable NGP has four cores4April 4, 2011 CS152, Spring 20115symmetric• 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 busNetworksProcessorApril 4, 2011 CS152, Spring 20116SynchronizationThe need for synchronization arises whenever there are concurrent processes in a system(even in a uniprocessor system)Producer-Consumer: A consumer process must wait until the producer process has produced dataMutual Exclusion: Ensure that only one process uses a resource at a given timeproducerconsumerShared ResourceP1P2April 4, 2011 CS152, Spring 20117A Producer-Consumer ExampleThe program is written assuming instructions 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?April 4, 2011 CS152, Spring 20118A Producer-Consumer Example continuedProducer 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 4 happens after 1.Problem sequences are:2, 3, 4, 14, 1, 2, 31234April 4, 2011 CS152, Spring 20119Sequential 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 PApril 4, 2011 CS152, Spring 201110Sequential 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)} ?If y is 11 then x cannot be 0April 4, 2011 CS152, Spring 201111Sequential ConsistencySequential consistency imposes more memory ordering constraints than those imposed by uniprocessor program 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)additional SC requirementsDoes (can) a system with caches or out-of-order execution capability provide a sequentially consistent view of the memory ?more on this laterApril 4, 2011 CS152, Spring 201112Multiple 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 atomically by one consumer lockstail
View Full Document
Unlocking...