電子科大盧老師-并行算法ppt2資料.ppt

1、并行算法及其應(yīng)用,計算機學(xué)院 盧光輝 Email:* Tel:* 主樓B1-*,教學(xué)安排：20學(xué)時 教材： 孫世新，盧光輝等，并行算法及其應(yīng)用 參考書： 黃鎧、徐志偉著，陸鑫達等譯.可擴展并行計算技術(shù)、結(jié)構(gòu)與編程.機器工業(yè)出版社，2000. 李曉梅、蔣增榮等著.并行算法,湖南科學(xué)技術(shù)出版社，1992. 陳國良.并行算法的設(shè)計與分析.高等教育出版社，2002.11.,序言,1.什么叫并行算法？ 一些可同時執(zhí)行的諸進程的集合，這些進程相互作用和相互協(xié)調(diào)。,2.并行算法與串行算法的關(guān)系：,P1,P2,P3,3. 并行與并發(fā)的關(guān)系：并行并發(fā) 并發(fā)是指兩個或者多個事件在同一時間間隔內(nèi)發(fā)生。在單處理機系統(tǒng)

2、中，每一時刻僅能有一道程序執(zhí)行，宏觀上多道程序在同時運行，微觀上這些程序是分時交替執(zhí)行。 4. 并行與分布式的關(guān)系： 網(wǎng)絡(luò)；并行更注重性能，而分布式更注重透明共享。,5.并行與網(wǎng)格計算（普適計算）的關(guān)系： 網(wǎng)格通過網(wǎng)絡(luò)連接地理上分布的各類計算資源、存儲資源、通信資源、軟件資源、信息資源、知識資源等，形成對用戶相對透明的虛擬的高性能計算環(huán)境，讓人們透明地使用這些資源和功能。它們與并行計算存在規(guī)模上的差異。 6 .并行與云計算的關(guān)系： 云計算以開放的標(biāo)準(zhǔn)和服務(wù)為基礎(chǔ)，以互聯(lián)網(wǎng)為中心，提供安全、快速、便捷的數(shù)據(jù)存儲和網(wǎng)絡(luò)計算服務(wù)，讓互聯(lián)網(wǎng)這片“云”上的各種計算機共同組成數(shù)個龐大的數(shù)據(jù)中心及計算中心。

3、云計算把計算及存儲以服務(wù)的形式提供給互聯(lián)網(wǎng)用戶，用戶所使用的數(shù)據(jù)、服務(wù)器、應(yīng)用軟件、開發(fā)平臺等資源都來自互聯(lián)網(wǎng)上的虛擬化計算中心，該數(shù)據(jù)中心負(fù)責(zé)對分布在互聯(lián)網(wǎng)上的各種資源進行分配、負(fù)載的均衡、軟件的部署、安全的控制等。,7. 為什么要研究并行算法？ （1）CPU的發(fā)展速度：Moore Law。 （2）深藍與國際象棋大師：1996年2月，國際象棋世界冠軍卡斯帕羅夫與IBM開發(fā)的“深藍”計算機對奕，卡斯帕羅夫最終四比二戰(zhàn)勝 “深藍”（IBM，它帶有256個處理器 ）。 1997年5月， “深藍”計算機以3.5:2.5戰(zhàn)勝卡斯帕羅夫。 （3）需求：快速（天氣預(yù)報），提高計算精度，與理論、實驗并重的科

4、學(xué)方法（代替核武器實驗）,8.國內(nèi)外發(fā)展現(xiàn)狀 （1）國內(nèi)發(fā)展情況：2010年11月中國國防科學(xué)技術(shù)大學(xué)研制的“天河1A” 運算速度達每秒2570萬億次,有186，368個核，在第三十六期全球超級計算機TOP500中曾排名第一，2012年6月排名第5。 “863”計劃、“973”計劃、國家自然科學(xué)基金都對并行計算十分重視。 （2）國外發(fā)展情況 2012年6月， Rank 1: 美國IBM的“BlueGene/Q”，1,572,864個核，運算速度已達16,324萬億次。 最新見附表（附表中計算速度單位為Gflops/s）。,美國HPCC、ASCI計劃； 早在20世紀(jì)80年代末期，美國政府就制定了

5、一項高性能計算計劃（Federal High Performance Computing Program）。旨在發(fā)展美國的的高性能計算機并將其用于解決一些有關(guān)國民經(jīng)濟與國家安全的重大問題，后來，隨著通信技術(shù)的發(fā)展，這個計劃被修改為高性能計算與通信計劃（HPCC）。 后來，美國政府為了把HPCC計劃向更高、更深入的層次發(fā)展，又提出了三個計劃：,推動戰(zhàn)略計算計劃（Accelerated Strategic Computing Initiative, ASCI） 其目的是為模擬核試驗和核武器儲備管理提供足夠的計算能力。 高性能計算現(xiàn)代化計劃（HPC Modernization Program）。 其

6、目的是為了改善國防研究的計算，降低武器設(shè)計、測試費用，保持美國在軍事上的優(yōu)勢。其任務(wù)是建立16個由高速網(wǎng)絡(luò)連接的高性能計算中心。 每秒千萬億次浮點計算計劃（Petaflops Computing） 這是美國的前瞻性研究計劃。,日本真實世界計算計劃: 日本早在20世紀(jì)90年代初就制定了這一項雄心勃勃的計劃。這項計劃的目的在于超越信息處理的原有框架，研制超并行、超分布的光計算機系統(tǒng)，并在神經(jīng)科學(xué)和認(rèn)知科學(xué)等方面取得重大進展。真實世界內(nèi)的信息包括圖像、聲音、觸覺、符號型知識數(shù)據(jù)等，種類極為繁雜、信息量非常龐大。 另外，日本1997年計劃開發(fā)的“地球模擬器”已于2002年研發(fā)成功，成為一度領(lǐng)先的世界最

7、快的超級計算機。 （3）并行算法的發(fā)展?fàn)顩r：,（4）并行計算模型發(fā)展?fàn)顩r：LogP，LogGP，BSP （5）并行開發(fā)環(huán)境發(fā)展?fàn)顩r：PVM、MPI、HPF、OpenMP（利用超線程技術(shù)，針對共享內(nèi)存多處理器體系結(jié)構(gòu)并行計算機）、OpenCL（支持多核、GPU、DSP等硬件平臺，【目前主要建立在CUDA架構(gòu)上】 ）,全書共分為三個部分： 1.基礎(chǔ)理論:主要介紹并行計算平臺、并行算法概述、并行程序開發(fā)環(huán)境等； 2.基礎(chǔ)應(yīng)用：主要包含矩陣運算、快速傅立葉變換、卷積運算、數(shù)字濾波、離散余弦變換、哈達瑪變換、2D離散小波變換、數(shù)字圖像處理等方面的并行算法設(shè)計、分析與測試； 3.實際應(yīng)用:主要介紹并行算法

8、在電磁散射中的應(yīng)用和無線電波參數(shù)聯(lián)合估計中的應(yīng)用。,第一章 并行計算平臺,并行計算機分類,1. SISD,Single Instruction Stream |82| | MPYU .M2 m1_6,qp_tab,m2_6$1 ; |101| | SHR .S2 m1_4,0 x13,m1_4 ; |94| | SHR .S1 m1_3,0 x13,m1_3 ; |95| ADD .D2 qp_constb,m2_7,m2_7 ; |109| | SHR .S2 m2_6,0 xf,m3_6 ; |119| | ADD .L1 qp_consta,m2_3,m2_3 ; |113| | SHR

9、 .S1 m1_2,0 x13,m1_2 ; |96| | MPYU .M1X m1_1,qp_tab,m2_1 ; |106| | OR .L2 val_1,sign5,sign5 ; |144| | MPY2 .M2 x2_54,val_2B1b,x5:x4 ; |69| | LDDW .D1T1 *-scaleM(8),sm3:sm2 ; |61| PACK2 .L2 m4_7,m4_6,m76 ; |170| | PACK2 .L1 m4_3,m4_2,m32 ; |172| | OR .D1X val_1,sign2,sign2 ; |147| | MPYU .M2X x6,sm2,

10、m0_6 ; |74| | SHL .S2 x76,0 x10,sign6 ; |132| | SHL .S1 x10,0 x10,sign0 ; |135| | MPY2 .M1 x2_10,val_2B1a,x1:x0 ; |71| ,執(zhí)行時的最小單位是 thread；數(shù)個 thread 可以組成一個 block；一個 block 中的 thread 能存取同一塊共享的內(nèi)存，而且可以快速進行同步的動作；不同 block 中的 thread 無法存取同一個共享的內(nèi)存，因此無法直接互通或進行同步；執(zhí)行相同程序的 block，可以組成 grid。,GPU并行:CUDA(Compute Unifi

11、ed Device Architecture ),SIMD/SMP,nVIDIA GTX200核心,Tesla GPGPU可以看作之前的Nvidia Quadro專業(yè)卡的通用計算版本 GTX200的240個流處理器被分為10組并行的材質(zhì)處理簇TPC（ Texture Processing Cluster ） 每個TPC由3個流處理器單元SM（ Streaming Multiprocessors ）組成 每個SM由8個流處理器SP（Stream Processor）；每個TPC內(nèi)的24個流處理器共享L1緩存（TPC的核內(nèi)內(nèi)存） 每個SM可以支持1024個并行線程 整個GTX200核心可以支持30720個線程,定義： network diameter: bisection width：,并行計算機的處理器連接方式,一.總線結(jié)構(gòu),二.一維陣列結(jié)構(gòu),三. 網(wǎng)格結(jié)構(gòu),四.超立方體結(jié)構(gòu),五.