Parallel ProcessingTypes of Parallel ProcessingSlide 3Slide 4Stages of Parallel ComputationExamplesParallel Processing•Parallel Processing occurs when more than one processor works together to solve a single problem.•Your lab has a lot of PC's but that doesnt mean parallel processing is going on. Each separate PC is working on solving separate problems. •Parallel processing speeds up solution times in two ways:–Multiple computers simply add "horsepower" to an existing algorithm–New algorithms can be designed to actually lower the cost of the problem solution.•Two kinds of parallelism:–Data parallelism: when the data is divided up among processors–Task parallelism: When the parts of an algorithm are divided up.Types of Parallel Processing•Pipelining (not usually considered true parallelism)–This occurs when separate processers, each with a specific job, work on a phase of a problems solution.–Most common example is your PC. The "single" processor is actually made up of many smaller special purpose processors.Phase 1Phase 2Phase 3Phase 1Phase 2Phase 3Data 2Data 3Data 4Data 5Result 1Result 1Data 2Data 4Data 5Data 3Normal processingrequires 3 steps to produce each result.Pipelining allows aresult to appear at each step.Types of Parallel Processing•Parallel Processing–Separate processors, usually identical work with one memory.–Usually requires special purpose machines. These machines may contain thousands of simple processors (usually in a multiple of 2, like 4096 or 8192, etc)MEMORYP01P02 P03P04 P05P06 P07Types of Parallel Processing•Distributed Processing–Separate processors of any type each with their own memory.–Networks or the internet. This is the most general and flexible type of processing, but communication costs between processors may be high.P01P02 P03P04 P05P06 P07M02 M03 M04 M05 M06 M07M01COMMUNICATION NETWORKStages of Parallel Computation•Everything has a benefit and a cost - parallel processing has an overhead cost. •The goal is to let the benefit of multiple processors working on a single problem outweigh the cost of keeping track of them. •Stages of a parallel computation:–(cost) Division of problem/data and distribution to processors–(cost) Start up of remote processes–(benefit) Parallel Computation–(cost) Transfer local results to a common processor–(cost) Collate results and presentExamples•Assume problem size = n and number of processors = p.•Image processing: Cost goes from O(n) to O(n/p).•FindMax: Cost goes from O(n) to O(log n).•Matrix squaring: Cost goes from O(n4) to O(n2).•Sorting: cost goes from O(n logn) to