ch0并行算法的運(yùn)行與設(shè)計(jì)概論

1、Parallel Algorithms1 / Ch02021-10-12Parallel Algorithms Chapter 0 IntroductionParallel Algorithms2 / Ch02021-10-12主要內(nèi)容主要內(nèi)容n0.1 課程內(nèi)容介紹課程內(nèi)容介紹 課程目標(biāo)、內(nèi)容和授課方式課程目標(biāo)、內(nèi)容和授課方式教材和主要參考書目教材和主要參考書目課程在并行計(jì)算技術(shù)中的地位課程在并行計(jì)算技術(shù)中的地位n0.2 課程要求課程要求課程論文組織方式課程論文組織方式考核和評分要求考核和評分要求n0.3 并行計(jì)算介紹并行計(jì)算介紹什么是并行計(jì)算什么是并行計(jì)算?為什么需要并行計(jì)算為什么需要并行計(jì)

2、算?幾種實(shí)現(xiàn)方案幾種實(shí)現(xiàn)方案并行計(jì)算的粒度并行計(jì)算的粒度并行計(jì)算的研究領(lǐng)域并行計(jì)算的研究領(lǐng)域TOP500和和China TOP50Parallel Algorithms3 / Ch02021-10-12 0.1 課程內(nèi)容介紹課程內(nèi)容介紹: 課程目標(biāo)、內(nèi)容和授課方式課程目標(biāo)、內(nèi)容和授課方式n通過通過課程講授課程講授、課程論文課程論文和和課堂討論課堂討論的方式使同學(xué)們掌握的方式使同學(xué)們掌握各各種并行計(jì)算模型上常用的、基本的、典型的并行算法設(shè)計(jì)和種并行計(jì)算模型上常用的、基本的、典型的并行算法設(shè)計(jì)和分析，以及在各自研究領(lǐng)域中的應(yīng)用。分析，以及在各自研究領(lǐng)域中的應(yīng)用。 n具體內(nèi)容包括：具體內(nèi)容包括：并行

3、機(jī)結(jié)構(gòu)模型、并行計(jì)算模型、并行算法基本知識；并行機(jī)結(jié)構(gòu)模型、并行計(jì)算模型、并行算法基本知識；非數(shù)值并行算法：排序、選擇、組合搜索、串匹配、圖論算法等；非數(shù)值并行算法：排序、選擇、組合搜索、串匹配、圖論算法等；數(shù)值并行算法：矩陣運(yùn)算、線性方程組求解、數(shù)值并行算法：矩陣運(yùn)算、線性方程組求解、FFT算法等；算法等；并行計(jì)算理論初步和并行算法的應(yīng)用舉例。并行計(jì)算理論初步和并行算法的應(yīng)用舉例。n在教師的指導(dǎo)下，完成課程論文：在教師的指導(dǎo)下，完成課程論文：針對自己的研究領(lǐng)域中的問題，基于并行與分布式算法的思想和技術(shù)針對自己的研究領(lǐng)域中的問題，基于并行與分布式算法的思想和技術(shù)進(jìn)行求解和實(shí)現(xiàn)進(jìn)行求解和實(shí)現(xiàn)(或

4、模擬或模擬)，并對結(jié)果進(jìn)行總結(jié)提高完成一篇較高質(zhì)量，并對結(jié)果進(jìn)行總結(jié)提高完成一篇較高質(zhì)量的論文。的論文。(注：該類論文稱為原創(chuàng)論文注：該類論文稱為原創(chuàng)論文)。在閱讀最新文獻(xiàn)的基礎(chǔ)上，分析、總結(jié)和完成某個(gè)研究領(lǐng)域的綜述。在閱讀最新文獻(xiàn)的基礎(chǔ)上，分析、總結(jié)和完成某個(gè)研究領(lǐng)域的綜述。(注：該類論文稱為綜述論文注：該類論文稱為綜述論文)。Parallel Algorithms4 / Ch02021-10-120.1 課程內(nèi)容介紹課程內(nèi)容介紹:教材和主要參考書目教材和主要參考書目n教材：教材：陳國良陳國良, 并行算法的設(shè)計(jì)與分析并行算法的設(shè)計(jì)與分析（修訂版）（修訂版）, 高等教育出版社高等教育出版社,

5、2002.11 n主要參考書目：主要參考書目：Kai Hwang,Zhiwei Xu”,Scalable Parallel Computing”,McGraw-Hill,1998J.JaJa,”Introduction to Parallel Algorithms”, Addison Wesley,1992A.Gramma etal, ”Introduction to Parallel Computing”(Second Edition), 北京：機(jī)械工業(yè)出版社北京：機(jī)械工業(yè)出版社, 2003.7陳國良并行計(jì)算：結(jié)構(gòu)，算法，編程高等教育出陳國良并行計(jì)算：結(jié)構(gòu)，算法，編程高等教育出版社，版社，2

6、001.52001.5 Parallel Algorithms5 / Ch02021-10-120.1 課程內(nèi)容介紹課程內(nèi)容介紹: 課程在并行計(jì)算技術(shù)中的地位課程在并行計(jì)算技術(shù)中的地位Parallel Algorithms6 / Ch02021-10-12主要內(nèi)容主要內(nèi)容n0.1 課程內(nèi)容介紹課程內(nèi)容介紹 課程目標(biāo)、內(nèi)容和授課方式課程目標(biāo)、內(nèi)容和授課方式教材和主要參考書目教材和主要參考書目課程在并行計(jì)算技術(shù)中的地位課程在并行計(jì)算技術(shù)中的地位n0.2 課程要求課程要求課程論文組織方式課程論文組織方式考核和評分要求考核和評分要求n0.3 并行計(jì)算介紹并行計(jì)算介紹什么是并行計(jì)算什么是并行計(jì)算?為什么

7、需要并行計(jì)算為什么需要并行計(jì)算?幾種實(shí)現(xiàn)方案幾種實(shí)現(xiàn)方案并行計(jì)算的粒度并行計(jì)算的粒度并行計(jì)算的研究領(lǐng)域并行計(jì)算的研究領(lǐng)域TOP500和和China TOP50Parallel Algorithms7 / Ch02021-10-120.2 課程要求課程要求: 課程論文組織方式課程論文組織方式n在課程主頁的在課程主頁的“課程論文列表課程論文列表”中列出了上屆的課程論文，供大家參考和中列出了上屆的課程論文，供大家參考和選題，有些工作可以繼續(xù)做下去。選題，有些工作可以繼續(xù)做下去。n成立不超過成立不超過3人的課程論文小組，推舉出一名組長，確定選題（與教師商人的課程論文小組，推舉出一名組長，確定選題（與教

8、師商量確定），盡快報(bào)給老師和助教。可以個(gè)人單獨(dú)去完成課程論文。量確定），盡快報(bào)給老師和助教?？梢詡€(gè)人單獨(dú)去完成課程論文。n閱讀論文要求：閱讀論文要求：每人至少寫出三篇以上精讀論文的評論，評論字?jǐn)?shù)至少每人至少寫出三篇以上精讀論文的評論，評論字?jǐn)?shù)至少五百字五百字。評論主要著眼于論文的創(chuàng)新點(diǎn)和存在的問題，以及可能下一步的研究工作。評論主要著眼于論文的創(chuàng)新點(diǎn)和存在的問題，以及可能下一步的研究工作。要有自己的見解，不要簡單翻譯原文的摘要和結(jié)論。要有自己的見解，不要簡單翻譯原文的摘要和結(jié)論。評論應(yīng)注明原論文的出處、評論人，并發(fā)給助教。評論應(yīng)注明原論文的出處、評論人，并發(fā)給助教。n應(yīng)遵循：應(yīng)遵循：結(jié)合自己的

9、研究領(lǐng)域，廣泛查閱最新資料，確定選題；結(jié)合自己的研究領(lǐng)域，廣泛查閱最新資料，確定選題；認(rèn)真閱讀論文，完成閱讀評論；認(rèn)真閱讀論文，完成閱讀評論；積極組織組內(nèi)討論，可以邀請老師和助教參加；積極組織組內(nèi)討論，可以邀請老師和助教參加；勤于思考，勇于創(chuàng)新，實(shí)事求是。培養(yǎng)嚴(yán)謹(jǐn)?shù)目蒲凶黠L(fēng)，勤于思考，勇于創(chuàng)新，實(shí)事求是。培養(yǎng)嚴(yán)謹(jǐn)?shù)目蒲凶黠L(fēng)，嚴(yán)禁抄襲嚴(yán)禁抄襲。n課程論文成績評定：課程論文成績評定：論文閱讀和評論撰寫（論文閱讀和評論撰寫（30）最終課程論文和報(bào)告（最終課程論文和報(bào)告（70）Parallel Algorithms8 / Ch02021-10-120.2 課程要求課程要求:考核和評分要求考核和評分要求

10、nExamination and Grading -Lessons & Answer: 10% -Class-Paper: 40% -Final written exam: 50%Parallel Algorithms9 / Ch02021-10-12主要內(nèi)容主要內(nèi)容n0.1 課程內(nèi)容介紹課程內(nèi)容介紹 課程目標(biāo)、內(nèi)容和授課方式課程目標(biāo)、內(nèi)容和授課方式教材和主要參考書目教材和主要參考書目課程在并行計(jì)算技術(shù)中的地位課程在并行計(jì)算技術(shù)中的地位n0.2 課程要求課程要求課程論文組織方式課程論文組織方式考核和評分要求考核和評分要求n0.3 并行計(jì)算介紹并行計(jì)算介紹什么是并行計(jì)算什么是并行計(jì)算?為什么需要

11、并行計(jì)算為什么需要并行計(jì)算?幾種實(shí)現(xiàn)方案幾種實(shí)現(xiàn)方案并行計(jì)算的粒度并行計(jì)算的粒度并行計(jì)算的研究領(lǐng)域并行計(jì)算的研究領(lǐng)域TOP500和和China TOP50Parallel Algorithms10 / Ch02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹: 什么是并行計(jì)算？什么是并行計(jì)算？nA parallel computer is a “collection of processing elements that communicate and cooperate to solve large problem fast”. -David E. CullernOr all proces

12、sors cooperate to solve a single problemnDaily life examples:House construction / /綜合：并發(fā)、分布、流水綜合：并發(fā)、分布、流水Car manufacturing / /流水線流水線Grocery store operation / /分布分布Parallel Algorithms11 / Ch02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹:為什么需要并行計(jì)算？為什么需要并行計(jì)算？nInterest in parallelism since the very ancient era of computer

13、s(e.g. ILLIAC IV of 1967 had 64 processors)nParallel Processing is an effective answer for the tremendous future computing requirements.napplications impulses:Data-intensive applications: videoconferencing, virtual reality, large database and data mining, speech recognition, biology, image and signa

14、l processing, etcComputing-intensive applications: numerical simulation(e.g. forecasting, manufacturing, chemistry, aerodynamics) nGrand challenges:Science today: experimentation, theory, simulation(or computation)Simulation relies heavily on parallel processingnAmerica HPCC project, ASCI projectnIn

15、 one words: Parallel processing promises increase ofPerformance(e.g. large, fast, cost)ReliabilityLarge set of computational problems are inherently parallel in nature. But their existing applications are designed for uniprocessor systems. Their parallelization is required.Parallel Algorithms12 / Ch

16、02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹: 幾種實(shí)現(xiàn)方案幾種實(shí)現(xiàn)方案nCluster of workstations (lowest cost)nMultiprocessor workstations ($60,000)DEC Firefly, Apollo DN 10000, SUN SPARCstation 20nShared memory multiprocessors ($200,000-400,000)Sequent Symmetry, Encore Multimax, SGI Challenge, SUN SPARCserver 2000nDistributed me

17、mory multicomputers ($200,000-400,000)Intel iPSC/860, NCUBE/2, MeikonMassively parallel processors ($5,000,000)Intel Paragon, TMC CM-5, CRAY T3D, IBM SP-2Parallel Algorithms13 / Ch02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹: 并行計(jì)算的粒度并行計(jì)算的粒度nCoarse-grained(粗粒度粗粒度)：Level of jobsnMiddle-grained(中等粒度中等粒度)：Level of proce

18、ssesnFine-grained(細(xì)粒度細(xì)粒度)：Level of machine instructions(or lower)Parallel Algorithms14 / Ch02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹: 研究領(lǐng)域研究領(lǐng)域nDesign of parallel computers: How to the number of processors, communication throughput, data sharing, etc.nDesign of parallel algorithms: Parallel algorithms may be quite

19、 different from their sequential counterparts.nDesign of parallel software:Operating systemsCompilesLibrariesTools: debuggers, performance analyzersParallel Algorithms15 / Ch02021-10-120.3 并行計(jì)算介紹并行計(jì)算介紹: TOP500 RankSiteCountry/YearComputer / ProcessorsManufacturerRmaxRpeak1Earth Simulator CenterJapan

20、/2002Earth-Simulator / 5120NEC35860409602Los Alamos National LaboratoryUnited States/2002ASCI Q - AlphaServer SC45, 1.25 GHz / 8192Hirginia TechUnited States/2003X1100 Dual 2.0 GHz Apple G5/Mellanox Infiniband 4X/Cisco GigE / 2200Self-made10280176004NCSAUnited States/2003TungstenPowerEdge 1750, P4 Xeon 3.06 GHz, Myrinet / 2500Dell9819153005Pacific Northwest National LaboratoryUnited States/2003Mpp2Integrity rx2600 Itanium2 1.5 GHz, Quadrics / 1936HP86331161614Chinese Academy of S