Parallel ComputingLimits on single-processor performanceParallelismDrawbacks to ParallelismAmdahl’s LawSlide 6History of Parallel Computing – ExamplesHistory of Parallel Computing –Overview of EvolutionMultiprocessor ArchitecturesSuperscalarVLIWVector ProcessorsMIMD ArchitecturesInterconnection NetworksNetwork TopologiesStatic TopologiesSlide 17Dynamic TopologySwitchesSlide 202x2 SwitchesShared Memory MultiprocessorsUMA Shared MemoryNUMA Shared MemoryDistributed ComputingGrid ComputingQuestions?Parallel ComputingParallel ComputingErik RobbinsErik RobbinsLimits on single-processor Limits on single-processor performanceperformanceOver time, computers have become better Over time, computers have become better and faster, but there are constraints to and faster, but there are constraints to further improvementfurther improvementPhysical barriersPhysical barriersHeat and electromagnetic interference limit chip Heat and electromagnetic interference limit chip transistor densitytransistor densityProcessor speeds constrained by speed of lightProcessor speeds constrained by speed of lightEconomic barriersEconomic barriersCost will eventually increase beyond price Cost will eventually increase beyond price anybody will be willing to payanybody will be willing to payParallelismParallelismImprovement of processor performance by Improvement of processor performance by distributing the computational load among distributing the computational load among several processors.several processors.The processing elements can be diverseThe processing elements can be diverseSingle computer with multiple processorsSingle computer with multiple processorsSeveral networked computersSeveral networked computersDrawbacks to ParallelismDrawbacks to ParallelismAdds costAdds costImperfect speed-up.Imperfect speed-up.Given n processors, perfect speed-up would Given n processors, perfect speed-up would imply a n-fold increase in power.imply a n-fold increase in power.A small portion of a program which cannot be A small portion of a program which cannot be parallelized will limit overall speed-up.parallelized will limit overall speed-up.““The bearing of a child takes nine months, no The bearing of a child takes nine months, no matter how many women are assigned.”matter how many women are assigned.”Amdahl’s LawAmdahl’s LawThis relationship is given by the equation:This relationship is given by the equation:S = 1 / (1 – P)S = 1 / (1 – P)S is the speed-up of the program (as a S is the speed-up of the program (as a factor of its original sequential runtime)factor of its original sequential runtime)P is the fraction that is parallelizableP is the fraction that is parallelizableWeb Applet –Web Applet –http://www.cs.iastate.edu/~prabhu/Tutorial/CACHE/amdahl.htmlhttp://www.cs.iastate.edu/~prabhu/Tutorial/CACHE/amdahl.htmlAmdahl’s LawAmdahl’s LawHistory of Parallel Computing – History of Parallel Computing – ExamplesExamples1954 – IBM 704 1954 – IBM 704 Gene Amdahl was a principle architectGene Amdahl was a principle architectuses fully automatic floating point arithmetic commands.uses fully automatic floating point arithmetic commands.1962 – Burroughs Corporation D8251962 – Burroughs Corporation D825Four-processor computerFour-processor computer1967 – Amdahl and Daniel Slotnick publish debate about 1967 – Amdahl and Daniel Slotnick publish debate about parallel computing feasibilityparallel computing feasibilityAmdahl’s Law coinedAmdahl’s Law coined1969 – Honeywell Multics system1969 – Honeywell Multics systemCapable of running up to eight processors in parallelCapable of running up to eight processors in parallel1970s – Cray supercomputers (SIMD architecture)1970s – Cray supercomputers (SIMD architecture)1984 – Synapse N+11984 – Synapse N+1First bus-connected multi-processor with snooping cachesFirst bus-connected multi-processor with snooping cachesHistory of Parallel Computing –History of Parallel Computing –Overview of EvolutionOverview of Evolution1950’s - Interest in parallel computing began.1950’s - Interest in parallel computing began.1960’s & 70’s - Advancements surfaced in the form of 1960’s & 70’s - Advancements surfaced in the form of supercomputers.supercomputers.Mid-1980’s – Massively parallel processors (MPPs) Mid-1980’s – Massively parallel processors (MPPs) came to dominate top end of computing.came to dominate top end of computing.Late-1980’s – Clusters (type of parallel computer built Late-1980’s – Clusters (type of parallel computer built from large numbers of computers connected by network) from large numbers of computers connected by network) competed with & eventually displaced MPPs.competed with & eventually displaced MPPs.Today – Parallel computing has become mainstream Today – Parallel computing has become mainstream based on multi-core processors in home computers. based on multi-core processors in home computers. Scaling of Moore’s Law predicts a transition from a few Scaling of Moore’s Law predicts a transition from a few cores to many.cores to many.Multiprocessor ArchitecturesMultiprocessor ArchitecturesInstruction Level Parallelism (ILP)Instruction Level Parallelism (ILP)Superscalar and VLIWSuperscalar and VLIWSIMD Architectures SIMD Architectures (single instruction streams, multiple data streams)(single instruction streams, multiple data streams)Vector ProcessorsVector ProcessorsMIMD Architectures (multiple instruction, multiple data)MIMD Architectures (multiple instruction, multiple data)Interconnection NetworksInterconnection NetworksShared Memory MultiprocessorsShared Memory MultiprocessorsDistributed ComputingDistributed ComputingAlternative Parallel Processing ApproachesAlternative Parallel Processing ApproachesDataflow ComputingDataflow ComputingNeural Networks (SIMD)Neural Networks (SIMD)Systolic Arrays (SIMD)Systolic Arrays (SIMD)Quantum ComputingQuantum ComputingSuperscalarSuperscalarA design methodology that allows multiple A design methodology that allows multiple instructions to be executed simultaneously in instructions to be executed simultaneously in each clock cycle.each clock cycle.Analogous to adding another lane to a highway. Analogous to adding another lane to a highway. The “additional lanes” are called
View Full Document