哈工大-并行處理-第一章緒論

并行處理技術(shù)第一章緒論計(jì)算機(jī)種類低端計(jì)算機(jī)（pc機(jī)、工作站）——一般計(jì)算機(jī)用戶高端計(jì)算機(jī)（超級(jí)計(jì)算機(jī)、并行機(jī)）——復(fù)雜科學(xué)計(jì)算、大型工程應(yīng)用、大存儲(chǔ)容量和高RAS商務(wù)處理1、科學(xué)和工程計(jì)算、應(yīng)用主流的科學(xué)計(jì)算有：物理、化學(xué)、材料學(xué)、生物學(xué)、天文學(xué)、地球科學(xué)工程應(yīng)用：能源勘探、油藏模擬、藥物分析、汽車碰撞模擬、氣流分析為此，美國(guó)制定HPCC計(jì)劃和ASCI計(jì)劃HPCC——高性能計(jì)算和通信

HighperformanceComputingandCommunication

HPCC計(jì)劃分布的重大挑戰(zhàn)應(yīng)用課題有：磁記錄技術(shù)、新藥設(shè)計(jì)、高速民航、催化作用、燃料燃燒、海洋建模、臭氧耗損、數(shù)字解析、大氣污染、蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)、圖象處理、密碼破譯HPCC對(duì)計(jì)算機(jī)突出3T要求：1Tflop/s計(jì)算能力1TB主存1TB/sI/O帶寬超級(jí)機(jī)、并行機(jī)的應(yīng)用：化學(xué)（催化劑研究、化學(xué)工廠模擬）物理學(xué)（新材料研究、基本粒子研究、聚變系統(tǒng)……）天文學(xué)（宇宙論、太陽(yáng)動(dòng)力學(xué)、黑洞碰撞……）氣候（中、長(zhǎng)期預(yù)報(bào)……）環(huán)境（生態(tài)系統(tǒng)、地球觀察系統(tǒng)、空氣和水質(zhì)建模）地理物理學(xué)（地震數(shù)據(jù)分析、水庫(kù)建模、地震預(yù)報(bào)……）工程（交通工具、建筑及橋梁設(shè)計(jì)、芯片模擬、發(fā)動(dòng)機(jī)電路設(shè)計(jì)）圖象和信號(hào)處理(合成孔徑雷達(dá)、虛擬現(xiàn)實(shí)、空時(shí)自適應(yīng)系統(tǒng)）統(tǒng)）商業(yè)應(yīng)用（數(shù)據(jù)庫(kù)查詢、數(shù)據(jù)倉(cāng)庫(kù)、決策支持系統(tǒng)、在線事務(wù)處理）計(jì)算機(jī)應(yīng)用可歸納為逐步升級(jí)的：數(shù)據(jù)處理（Dataprocessing）信息處理（Informationprocessing）知識(shí)處理（Knowledgeprocessing）智能處理（Intelligenceprocessing）都隱含有能同時(shí)進(jìn)行運(yùn)算或操作的特性，稱之為并行性ASCI計(jì)劃——加速戰(zhàn)略計(jì)算創(chuàng)新

（AcceleratedStrategicComputingInitiative）通過(guò)數(shù)值模擬，評(píng)估核武器的性能：安全性、可靠性、更新等。要求數(shù)值模擬達(dá)到高分辨率、高逼真度、三維、全物理、全系統(tǒng)……美能源部目前使用的計(jì)算機(jī)：100Tflop/s50TB

目前ASCI計(jì)劃正把各項(xiàng)應(yīng)用要求與計(jì)算機(jī)平臺(tái)推進(jìn)到萬(wàn)億級(jí)規(guī)模的體系中去（美目前最快的計(jì)算機(jī)是70萬(wàn)億次，3.3萬(wàn)個(gè)CPU）商務(wù)應(yīng)用數(shù)據(jù)庫(kù)管理和查詢、在線事物處理、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘、決策支持系統(tǒng),數(shù)據(jù)庫(kù),硬件和軟件供應(yīng)商,多處理機(jī)系統(tǒng)。以上應(yīng)用可用TPM表示:將計(jì)算機(jī)系統(tǒng)的速度容量換算成每秒鐘事務(wù)處理數(shù)。

網(wǎng)絡(luò)計(jì)算應(yīng)用：應(yīng)用主要要求有效的通信、協(xié)同和互動(dòng)操作、良好的安全性等。應(yīng)用有：WWW服務(wù)、多媒體處理、視頻點(diǎn)播、電子商務(wù)、數(shù)字圖書館、遠(yuǎn)程學(xué)習(xí)、醫(yī)療診斷。因特網(wǎng)的網(wǎng)格計(jì)算研究，個(gè)人互聯(lián)網(wǎng)的研究等

2004年美快閃族聯(lián)網(wǎng)完成1800億次運(yùn)算，沖擊500強(qiáng)。國(guó)計(jì)民生方面的應(yīng)用：醫(yī)療保健、教育、能源管理、環(huán)境保護(hù)、文化娛樂(lè)、國(guó)防安全……都涉及到了高性能并行機(jī)的使用

1995世界第一部全計(jì)算機(jī)動(dòng)畫片<玩具總動(dòng)員>是由上百臺(tái)SUN工作站并行完成的。以上的應(yīng)用涉及并行機(jī)和機(jī)群。1.2并行性的概念1、并行性（parallelism）——在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成兩種以上性質(zhì)相同或不相同的工作，只要時(shí)間上相互重疊，均存在并行性。2、并行性含義同時(shí)性（Simultaneity）——兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生并發(fā)性（Concurency）——兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生3、并行性分類粗粒度并行——在多處理機(jī)上分別運(yùn)行多個(gè)進(jìn)程，由多臺(tái)處理機(jī)合作完成一個(gè)程序。細(xì)粒度并行——指在一個(gè)進(jìn)程中，進(jìn)行操作一級(jí)或指令一級(jí)的并行處理當(dāng)代并行機(jī)系統(tǒng)大型并行計(jì)算機(jī)（scalable-parallelComputer）可分為:單指令多數(shù)據(jù)流機(jī)SIMD并行向量處理機(jī)PVP對(duì)稱多處理機(jī)SMP

大規(guī)模并行處理機(jī)MPP

分布式共享存儲(chǔ)DSM多處理機(jī)

工作站機(jī)群COW

*可擴(kuò)展并行計(jì)算機(jī)發(fā)展正趨于三種系統(tǒng)結(jié)構(gòu)：1、無(wú)共享體系結(jié)構(gòu)2、共享磁盤體系結(jié)構(gòu)3、共享存儲(chǔ)器體系結(jié)構(gòu)屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD互聯(lián)網(wǎng)絡(luò)交叉開關(guān)交叉開關(guān)，總線定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商業(yè)化網(wǎng)絡(luò)通信機(jī)制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲(chǔ)器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA無(wú)共享體系結(jié)構(gòu)（可以有多個(gè)p）

CMDNIC互連網(wǎng)絡(luò)

CMDNIC…PP共享磁盤體系結(jié)構(gòu)

CMDNIC互連網(wǎng)絡(luò)

CMDNIC…共享磁盤PP互連網(wǎng)絡(luò)…共享磁盤共享存儲(chǔ)器CPCP共享存儲(chǔ)器體系結(jié)構(gòu)規(guī)?？缮炜s性——增加機(jī)器規(guī)模，即處理機(jī)數(shù)。用可擴(kuò)展性衡量一個(gè)系統(tǒng)能容納的最大處理機(jī)數(shù)。資源擴(kuò)展——可保持cpu數(shù)不變，增加存儲(chǔ)容量，更大的高速緩存、磁盤……軟件可擴(kuò)展性——①操作系統(tǒng)用一個(gè)新版本，多線程，多用戶…②更大的地址空間，以及高效的內(nèi)核功能③更有效的數(shù)學(xué)和工程庫(kù)④更有效和易于使用的應(yīng)用軟件⑤對(duì)用戶更友好的編程環(huán)境應(yīng)用可擴(kuò)展性——①機(jī)器規(guī)模可擴(kuò)展性（增加機(jī)器數(shù)，系統(tǒng)性能有多大改進(jìn)）②問(wèn)題規(guī)模可擴(kuò)展性（例：并行雷達(dá)程序256cpu,100雷達(dá)）技術(shù)可擴(kuò)展性代（時(shí)間）可擴(kuò)展性——一個(gè)系統(tǒng)通過(guò)使用下一代的部件，一個(gè)新的OS，更強(qiáng)的編譯器，計(jì)算能力增加?？臻g可擴(kuò)展性——Internet具有最好的空間可擴(kuò)展性異構(gòu)可擴(kuò)展性——系統(tǒng)集成不同廠商提供的軟件和硬件而擴(kuò)展的能力，具有開放系統(tǒng)結(jié)構(gòu)，在軟件領(lǐng)域有可移植性并行處理所涉及的問(wèn)題系統(tǒng)規(guī)模——處理單元有多少（小規(guī)模、中規(guī)模、大規(guī)模）系統(tǒng)的組織策略——處理單元的功能有多強(qiáng)蟻軍法象群法系統(tǒng)的互連問(wèn)題——各處理單元之間按什么樣的拓?fù)浣Y(jié)構(gòu)彼此相連系統(tǒng)的通信方式——處理單元的數(shù)據(jù)如何運(yùn)輸共享變量方式消息傳遞方式同步互斥問(wèn)題——保證多處理單元操作的順序性數(shù)據(jù)一致性——不同存儲(chǔ)層次中的共享數(shù)據(jù)的完整性并行算法的研究——對(duì)串行應(yīng)用找出能利用多機(jī)并行的新算法并行編譯技術(shù)——并行語(yǔ)言的研究、自動(dòng)并行識(shí)別器、編譯程序本身的并行化、并行程序開發(fā)工具、調(diào)試工具、分析工具并行操作系統(tǒng)——支持多處理機(jī)并行；自動(dòng)調(diào)度和負(fù)載平衡并行程序設(shè)計(jì)支持機(jī)制；Unix并行化…并行處理系統(tǒng)的三個(gè)主要優(yōu)點(diǎn)1、有很高的運(yùn)算速度，處理能力2、良好的性能價(jià)格比。3、系統(tǒng)規(guī)模的可伸縮性好。并行程序的設(shè)計(jì)方法隱式并行性——用傳統(tǒng)cFORTRAN編；并行編譯器。顯式并行性——用并行語(yǔ)言編源程序并行計(jì)算機(jī)定義——由多個(gè)處理器組成的計(jì)算機(jī)系統(tǒng)，這些處理單元相互通信和協(xié)作，快速高效求解復(fù)雜問(wèn)題。6、從標(biāo)量處理計(jì)算機(jī)到并行計(jì)算機(jī)的演變標(biāo)量順序的先行I/E重疊功能并行多功能部件流水線隱式向量顯式向量存儲(chǔ)器到存儲(chǔ)器寄存器到存儲(chǔ)器SIMDMIMD多處理機(jī)多計(jì)算機(jī)處理機(jī)陣列關(guān)聯(lián)處理器1.3并行處理機(jī)的發(fā)展1、提高并行性的三種主要技術(shù)途徑1）時(shí)間重疊（Time-interleaving）即多個(gè)處理過(guò)程在時(shí)間上相互錯(cuò)開，輪流重疊使用同一套硬件的各個(gè)部件，以加強(qiáng)部件的周轉(zhuǎn)而提高速度。2）資源重復(fù)（resource-replication）根據(jù)以數(shù)量取勝原則，重復(fù)設(shè)置硬件資源以大幅度提高系統(tǒng)的性能。3）資源共享（resource-sharing）利用軟件方法，使多個(gè)用戶分時(shí)使用同一個(gè)計(jì)算機(jī)系統(tǒng)。2、計(jì)算機(jī)系統(tǒng)并行處理的發(fā)展1）按照指令流和數(shù)據(jù)流的多倍性概念將計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類指令流——指機(jī)器所執(zhí)行的指令序列數(shù)據(jù)流——指指令所調(diào)用的數(shù)據(jù)序列多倍性——指機(jī)器的瓶頸部件上所可能并行執(zhí)行的最大指令或數(shù)據(jù)的個(gè)數(shù)。單機(jī)系統(tǒng)多道程序分時(shí)系統(tǒng)多終端遠(yuǎn)程系統(tǒng)智能終端分布處理系統(tǒng)局部計(jì)算機(jī)網(wǎng)通信處理機(jī)遠(yuǎn)程網(wǎng)絡(luò)部件冗余多操作部件多存儲(chǔ)體并行處理機(jī)聯(lián)想處理機(jī)同構(gòu)型多處理機(jī)可重構(gòu)多處理機(jī)容錯(cuò)處理機(jī)緊密偶合系統(tǒng)重疊方式先行控制指令流水?dāng)?shù)據(jù)流水向量處理機(jī)異構(gòu)型多處理機(jī)高級(jí)語(yǔ)言處理機(jī)數(shù)據(jù)庫(kù)處理機(jī)松散耦合系統(tǒng)多機(jī)系統(tǒng)資源共享資源重復(fù)時(shí)間重疊網(wǎng)絡(luò)化機(jī)間互聯(lián)功能專用2）計(jì)算機(jī)并行處理的發(fā)展1.4并行性的等級(jí)1）從計(jì)算機(jī)系統(tǒng)中執(zhí)行程序的角度分級(jí)指令內(nèi)部的并行——一條指令內(nèi)部各個(gè)微操作之間的并行。指令之間的并行——多指令的并行執(zhí)行。任務(wù)或進(jìn)程的并行——多個(gè)任務(wù)或程序段的并行執(zhí)行。作業(yè)或程序之間的并行——多個(gè)任務(wù)或多道程序的并行。2）從計(jì)算機(jī)系統(tǒng)中處理數(shù)據(jù)的并行性分級(jí)位串字串——同時(shí)只對(duì)一個(gè)字的一位進(jìn)行處理，沒(méi)有并行。位并字串——同時(shí)對(duì)一個(gè)字的全方位進(jìn)行處理，開始出現(xiàn)并行。位片串字并——同時(shí)對(duì)許多字的同一位（位片）進(jìn)行處理，顯示出開始進(jìn)入并行處理領(lǐng)域。全并行——同時(shí)對(duì)許多字的全部或部位組進(jìn)行處理。3）從計(jì)算機(jī)對(duì)信息加工的步驟和階段來(lái)分級(jí)：存儲(chǔ)器操作并行——采用單體多字，多體單字，多體多字方式在同一周期內(nèi)訪多字。處理器操作步驟并行——將操作步驟或具體執(zhí)行步驟在時(shí)間上重疊流水。處理器操作并行——讓多個(gè)處理器在同一控制器下按照同一條指令的要求對(duì)多個(gè)數(shù)據(jù)同時(shí)操作。指令、任務(wù)、作業(yè)并行——多個(gè)處理機(jī)同時(shí)對(duì)多條指令及有關(guān)數(shù)據(jù)組操作。Flynn將計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類如下：

單指令單數(shù)據(jù)流（SISD）

單指令多數(shù)據(jù)流（SIMD）

多指令單數(shù)據(jù)流（MISD）

多指令多數(shù)據(jù)流（MIMD）

CUPUMMISISISSISD計(jì)算機(jī)CUPU1PU2PUnMM1MM2MMnDS1DS2DSn....ISISSIMD計(jì)算機(jī)PU1PU2PUnDS..MM2MM1MMn…MM1MM1MM1IS1IS2ISnIS1IS2ISnISnIS2IS1DSMISD計(jì)算機(jī)…PU1PU2PUnMM1MM2MMnDS1DS2DSn....CU1CU2CUn..IS1IS2ISnIS1IS2ISn..MIMD計(jì)算機(jī)3）多處理機(jī)系統(tǒng)比較項(xiàng)目同構(gòu)型多處理機(jī)異構(gòu)型多處理機(jī)分布處理系統(tǒng)目的提高系統(tǒng)性能（可靠性、速度）提高系統(tǒng)的使用效率兼顧效率與性能技術(shù)途徑資源重復(fù)（機(jī)間互聯(lián)）時(shí)間重疊（功能專用化）資源共享（網(wǎng)絡(luò)化）組成同類型（同等功能）不同類型（不同功能）不限制分工方式任務(wù)分布功能分布硬、軟件、數(shù)據(jù)等資源的分布工作方式一個(gè)作業(yè)由多機(jī)協(xié)同并行地完成一個(gè)作業(yè)由多機(jī)協(xié)同串行地完成一個(gè)作業(yè)由一臺(tái)處理機(jī)完成，必要時(shí)才請(qǐng)求他機(jī)協(xié)作控制方式常采用浮動(dòng)控制方式采用專用控制方式分布控制方式耦合度緊密耦合緊密、松散耦合松散、緊密耦合對(duì)互聯(lián)網(wǎng)的要求快速、靈活、可重構(gòu)性專用性快速、簡(jiǎn)單、靈活、通用同構(gòu)型——對(duì)稱型異構(gòu)型——非對(duì)稱型浮動(dòng)控制方式——即整個(gè)系統(tǒng)的管理由一臺(tái)處理機(jī)管理控制