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

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

HighperformanceComputingandCommunication

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

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

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

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

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

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

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

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

工作站機(jī)群COW

*可擴(kuò)展并行計算機(jī)發(fā)展正趨于三種系統(tǒng)結(jié)構(gòu)：1、無共享體系結(jié)構(gòu)2、共享磁盤體系結(jié)構(gòu)3、共享存儲器體系結(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)存儲器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA無共享體系結(jié)構(gòu)（可以有多個p）

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

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

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

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

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

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

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

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

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