Parallel ProcessingThe single processor problemPowerPoint PresentationSlide 4Slide 5Types of Parallel ProcessorsSlide 7Slide 8Parallel Processing ProblemsNetwork TopologiesRingTreeMeshHypercubeComplete ConnectivitySlide 16Parallel ProcessingParallel ProcessingPresented by: Presented by: Wanki HoWanki HoCS147, Section 1CS147, Section 1The single processor problemThe single processor problemQuestion: Why is parallel processing necessary?Question: Why is parallel processing necessary?Reasons for needing computational powerReasons for needing computational powerLonger time to completionLonger time to completionHigher complexityHigher complexityMore detailMore detailSolutions must be found within a Solutions must be found within a reasonable time by human standardsreasonable time by human standardsExamples of computational problemsExamples of computational problemsWeather predictionWeather predictionAir traffic simulationsAir traffic simulationsDNA mappingDNA mappingBig challengesBig challengesComputer AIsComputer AIsUnderlying problem: Need more memory Underlying problem: Need more memory and speedand speedThe solution: Parallel processingThe solution: Parallel processingConnect a lot of computers together using Connect a lot of computers together using an interconnection network so that they act an interconnection network so that they act togethertogetherTypes of Parallel ProcessorsTypes of Parallel ProcessorsVarious types depending on how the Various types depending on how the processors interact with memoryprocessors interact with memoryFlynn’s TaxonomyFlynn’s TaxonomySISD Single Instruction Single Data StreamSISD Single Instruction Single Data StreamSIMD Single Instruction Multiple Data StreamSIMD Single Instruction Multiple Data StreamMISD Multiple Instruction Single Data StreamMISD Multiple Instruction Single Data StreamMIMD Multiple Instruction Multiple Data MIMD Multiple Instruction Multiple Data StreamStreamSISDSISDVon Neumann architecture. Your typical Von Neumann architecture. Your typical everyday computereveryday computerMISDMISDWierd stuff. Noone uses.Wierd stuff. Noone uses.SIMDSIMDComputers with special instructions for Computers with special instructions for handling large data in parallel (ex. Array handling large data in parallel (ex. Array processor in Intel’s MMX chip)processor in Intel’s MMX chip)MIMDMIMDMany processors performing operations on Many processors performing operations on many datamany dataMultiprocessorsMultiprocessorsNetworks of interconnected computersNetworks of interconnected computersParallel Processing ProblemsParallel Processing Problems Multiple processors accessing the same Multiple processors accessing the same memory.memory.What happens if one processor reads and What happens if one processor reads and another processor writes to the same another processor writes to the same block of memory?block of memory?How do two processors maintain separate How do two processors maintain separate caches concurrently?caches concurrently?Network TopologiesNetwork TopologiesBus NetworkBus NetworkRingRingTreeTreeMeshMeshHypercubeHypercubeComplete ConnectivityComplete ConnectivityRingRingEvery computer has two branches connecting it Every computer has two branches connecting it to another computer or outside the ringto another computer or outside the ringTreeTreeComputers are connected to each other in a tree Computers are connected to each other in a tree structurestructureMeshMeshEach computer is connected to the computer Each computer is connected to the computer below and above and to the left and right of itbelow and above and to the left and right of itHypercubeHypercubeEach computer is connected to 4 other Each computer is connected to 4 other computerscomputersConsistent distance between two computers. Consistent distance between two computers. Useful for weight balancingUseful for weight balancingComplete ConnectivityComplete ConnectivityEach computer is connected to every other Each computer is connected to every other computer in the network computer in the network Optimal connectivityOptimal connectivityComplexity grows geometricallyComplexity grows geometricallyThe EndThe
View Full Document