Parallel Processing I 15-319, spring 2010 7th Lecture, Feb 2nd Lecture Motivation Lecture OutlineWhat is Parallel Computing?Parallel Computing ResourcesHistory of Parallel ComputingWhen can a computation be Parallelized? (1/3)When can a computation be Parallelized? (2/3)When can a computation be Parallelized? (3/3)Lecture OutlineUses of Parallel Computing (1/2)Uses of Parallel Computing (2/2)Why Parallel Computing? (1/2)Why Parallel Computing? (2/2)How much faster can CPUs get?Solution : More chips in Parallel!Multicore CPUsGraphics Processing Units (GPUs)Lecture OutlineTermsProgram Execution LevelsParallelization levels (1/8)Parallelization levels (2/8)Parallelization levels (3/8)Parallelization levels (4/8)Parallelization levels (5/8)Parallelization levels (6/8)Slide Number 28Parallelization levels (8/8)Lecture OutlineParallel Computers Classification (1/5)Parallel Computers Classification (2/5)Parallel Computers Classification (3/5)Parallel Computers Classification (4/5)Parallel Computers Classification (5/5)Lecture OutlineParallel Computing Memory Architecture (1/9)Parallel Computing Memory Architecture (2/9)Parallel Computing Memory Architecture (3/9)Parallel Computing Memory Architecture (4/9)Parallel Computing Memory Architecture (5/9)Parallel Computing Memory Architecture (6/9)Parallel Computing Memory Architecture (7/9)Parallel Computing Memory Architecture (8/9)Parallel Computing Memory Architecture (9/9)Lecture OutlineParallel Programming Models (1/12)Parallel Programming Models (2/12)Parallel Programming Models (3/12)Parallel Programming Models (4/12)Parallel Programming Models (5/12)Parallel Programming Models (6/12)Parallel Programming Models (7/12)Parallel Programming Models (8/12)Parallel Programming Models (9/12)Parallel Programming Models (10/12)Parallel Programming Models (11/12)Parallel Programming Models (12/12)Lecture OutlineNext LectureReferencesCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingIntroduction to Cloud ComputingMajd F. SakrParallel Processing I 15‐319, spring 2010 7th Lecture, Feb 2ndCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingLecture Motivation  Concurrency and why? Different flavors of parallel computing Get the basic idea of the benefits of concurrency and the challenges in achieving concurrent execution.Carnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingLecture Outline What is Parallel Computing? Motivation for Parallel Computing Parallelization Levels ‐ granularities Parallel Computers Classification  Parallel Computing Memory Architecture Parallel Programming ModelsCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingWhat is Parallel Computing?4CPU..…instructionsProblemtimeProblem..…instructionsCPUCPUCPU..…..…timeCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingParallel Computing Resources Multiple processors on the same computer Multiple computers connected by a network Combination of bothProblem..…instructionsCPUCPUCPU..…..…timeCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingHistory of Parallel Computing195019601980 1990 2000 2004TodayInterest Started1970shared memory & multiprocessors working on shared data1981:Cosmic Cube constructed ( 64 Intel Microprocessor )Clusters & Companies began selling Parallel ComputersParallel Systems made of off the shelf processors(e.g. Beowulf Clusters)1997: 1st supercomputer(ASCI Red) (1 trillion operations/second)1998: 2nd Supercomputer (ASCI Blue Pacific)(by IBM, 3 trillion operations/s)3rd supercomputer(ASCI While) (by IBM, 10 trillion operations/second)100 trillion Operations/secondParallel Computing based on multi-core processorsCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingWhen can a computation be Parallelized? (1/3) When using multiple compute resources to solve the problem saves it more time than using single resource At any moment, we can execute multiple program chunks DependenciesCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud Computingadd a, b, cWhen can a computation be Parallelized? (2/3)a=1 b=3 c=-1 e=2d=???Initial values:add a, b, cmult d, a, eTo Do:timeSequential Parallelb=3 c=-1+a=2mult d, a, ea=2 e=2xd=4add a, b, cmult d, a, eb=3 c=-1+a=1 e=2xa=2d=2 Problem’s ability to be broken into discrete pieces to be solved simultaneously Check data dependenciesCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud Computingadd a, b, cWhen can a computation be Parallelized? (3/3)a=??? b=3 c=-1 e=2d=???Initial values:add a, b, cmult d, e, fTo Do:timeSequential Parallelb=3 c=-1+a=2mult d, e, fe=2xd=0add a, b, cb=3 c=-1+a=2 Problem’s ability to be broken into discrete pieces to be solved simultaneously Check data dependenciesf=0f=0mult d, e, fe=2xd=0f=0Carnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingLecture Outline What is Parallel Computing? Motivation for Parallel Computing Parallelization Levels Parallel Computers Classification  Parallel Computing Memory Architecture Parallel Programming ModelsCarnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingUses of Parallel Computing (1/2) Modeling difficult scientific and engineering problems Physics: applied, nuclear, particle, condensed matter, high pressure, fusion, photonics Geology Molecular sciences Electrical Engineering: circuit design, condense matter, high pressure … Commercial applications Databases, Datamining Network video and multi‐national corporations Financial and economic modeling …11Carnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingUses of Parallel Computing (2/2) User Applications Image and Video Editing Entertainment Applications Games & Real‐time Graphics High Definition Video Playback  3‐D Animation12Carnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingWhy Parallel Computing? (1/2) Why not simply build faster serial computer?? The speed at which data can move through hardware determines the speed of a serial computer. So we need to increase proximity of data. Limits to miniaturization: even though  Economic Limitations: cheaper to use multiple commodity processors to achieve fast performance than to build a single fast processor. Carnegie MellonSpring 2010 ©15-319 Introduction to Cloud ComputingWhy Parallel Computing? (2/2) Saving