[数学]算法导论-sch5 Parallel Algorithms.pdf

算法设计与分析算法设计与分析算法设计与分析算法设计与分析 Design and Analysis of AlgorithmsDesign and Analysis of AlgorithmsDesign and Analysis of AlgorithmsDesign and Analysis of Algorithms 主讲人主讲人主讲人主讲人 徐徐徐徐 云云云云 FallFall 2012,2012, USTCUSTC 第第55章章((补充补充)) 并行算法并行算法 5.15.1 概述概述 5.2 并行算法基础知识并行算法基础知识并行算法基础知识并行算法基础知识 5.5.33 并行程序设计并行程序设计 5555..4444 一一般设计方法和过程般设计方法和过程般设计方法和过程般设计方法和过程 5.5.55 算法设计示例算法设计示例 5.65.6 Intel MultiIntel Multi--core Architecture Programmingcore Architecture Programming 5.1 概述  什什么是并行计算是并行计算  为什么要并行计算  并行计算算的实实现方案案  并行计算的研究领域并行计算的研究领域  Top500 China Top100  并行机体系结构 2012/10/31 算法设计与分析 3 什么是并行计算  A parallel computer is a “collection of processing elements that communicate andprocessing elements that communicate and cooperate to solve large problem fast”. – David EDavid E. Culler Culler  Or all processors cooperate to solve a single problblem  Daily life examples: - House construction - Car manufacturing - Grocery store operation 2012/10/31 算法设计与分析 4 为什么要并行计算（1）  Interest in parallelism since the very ancient era of compputers(e.gg. ILLIAC IV of 1967 had 6464 processors ))  Parallel Processing is an effective answer for the tremendous future computingthe tremendous future computing requirements. - ii.ee. MutiMuti-core CPU and Processorcore CPU and Processor  applications impulses: - Data-intensive apppplications: videoconferencing,g, virtual reality, large database and data mining, speech recognition, biology, image and signal pprocessing,g, etc - Computing-intensive applications: numerical simulation(e.g. fo