x-數(shù)值-并行計(jì)算導(dǎo)論

(CIP)并行計(jì)算導(dǎo)論/張林波等編著.—： (高等院校信息與計(jì)算科學(xué)專業(yè)系列)ISBNI.并...II.張...III.并行算法–高等學(xué)校–IV.TP301.6館CIP(2006)第026693本書(shū)是并行計(jì)算，特別是分布式并行計(jì)算環(huán)境和消息傳遞并行編程的入門，目的是促進(jìn)并行計(jì)算技術(shù)在我國(guó)的應(yīng)用。書(shū)中介L(zhǎng)x/UNIXLx機(jī)PI消息傳遞并行編程的基本概念與方法。書(shū)中還提供了一批典型科學(xué)計(jì)算問(wèn)題的并行算法與程序設(shè)計(jì)實(shí)例，介紹了一些當(dāng)前國(guó)際上流行的科學(xué)計(jì)算軟件工知識(shí)，在逐步學(xué)習(xí)使用的過(guò)程中學(xué)會(huì)利用并行計(jì)算解決自己學(xué)習(xí)和工作中的問(wèn)題。本書(shū)側(cè)重介紹高性能計(jì)算的實(shí)用技術(shù)，可作為與計(jì)算專業(yè)的專業(yè)基礎(chǔ)課，也可作為其他理工科非計(jì)算機(jī)專業(yè)的并行算程。外，書(shū)可作有關(guān)Lx機(jī)群建、I息傳遞并行算法設(shè)計(jì)與編程及常用高性能科學(xué)計(jì)算軟件的參考書(shū)使用。 隨著高性能并行計(jì)算機(jī)，尤其是Linux微機(jī)機(jī)群在我國(guó)應(yīng)用部成科學(xué)計(jì)算軟件工具箱、庫(kù)等的普及教育和推廣應(yīng)用還明顯不夠，入門。它側(cè)重于介紹利用現(xiàn)有的微機(jī)條件建立并行計(jì)算的軟硬件 消息傳遞并行編程的基本概念與方全書(shū)分為三部分，共包括九章和兩個(gè)附錄1141章講述并行計(jì)算機(jī)的發(fā)展歷史、并行計(jì)算機(jī)體系結(jié)構(gòu)以及2Linux操3章講述標(biāo)準(zhǔn)消息傳遞并行編程接口MPI，并介紹如何利用目前流行的免費(fèi)MPI軟件MPICH和Linux并鑒于國(guó)內(nèi)已有一些專門關(guān)于MPI編程的書(shū)，本書(shū)中關(guān)于MPI編程的部分僅限于講述MPI編程的基本概念和介紹一些MPI的重要函數(shù)，同時(shí)在附錄B中提供MPI變量和函數(shù)的完整參考方便讀者查詢。第4章講述程序性能評(píng)價(jià)與優(yōu)化方面的有關(guān)知識(shí)。第2部分包括第5章至第9章。在這部分中，通過(guò)一些典行算法設(shè)計(jì)及并行程序?qū)崿F(xiàn)的實(shí)例，介紹并行算法設(shè)計(jì)的基本思想與PI5章介紹一個(gè)自適應(yīng)數(shù)值積分算法的并行算法設(shè)計(jì)與PI并行程序?qū)崿F(xiàn)。第6章介紹矩陣計(jì)算行與序第7章介紹快速變換(FFT)的并行算法及在消息傳遞并行環(huán)境中的實(shí)現(xiàn)方法。第8章以二維isson方程5點(diǎn)差分格式的點(diǎn)Jacobi9章通過(guò)二維熱傳導(dǎo)方程的DI格式介紹基于流水線方法的并行算法設(shè)計(jì)的基本思想及實(shí)現(xiàn)方法。第3部分由兩個(gè)附錄構(gòu)成。附錄A介紹一些重要的高性能計(jì)BLAS，LAPACK，ScaLAPACK，F(xiàn)FTWPETScB是一個(gè)為方便讀者速查而整理的較完整的MPI參考手冊(cè)。建立的實(shí)際操作及Linux系統(tǒng)的管理和使用，與自己的工作領(lǐng)域相結(jié)合編寫具體模型問(wèn)題的例子程序舉一反三通過(guò)本書(shū) 在本書(shū)的作者中，張林波(中國(guó)數(shù)學(xué)與系統(tǒng)科學(xué))編寫了3章、5章、9章和B，以及第2章、4章和附錄A中的部分內(nèi)容；遲學(xué)斌(中國(guó)計(jì)算機(jī)網(wǎng)絡(luò)信息中心)編寫了第6章、第7章，以及附錄A中的部分內(nèi)容；莫?jiǎng)t堯(應(yīng)用京大學(xué)數(shù)學(xué)科學(xué)學(xué)院)編寫了第2章。本程序?qū)嵗梢詮南旅娴?(A.3)、(A.2)、(A.4)，在此一并致謝。作2006717日于 第1部分基礎(chǔ)知 第1章預(yù)備知 并行計(jì)算的主要研究目標(biāo)和內(nèi) 什么是并行計(jì) 并行計(jì)算的主要研究目標(biāo)和內(nèi) 推動(dòng)并行計(jì)算發(fā)展的主要?jiǎng)?并行計(jì)算機(jī)發(fā)展歷 應(yīng)用需求的推動(dòng)作 70年 80年代早 80年代中 80年代后 90年代早 90年代中后 2000年到當(dāng) 并行機(jī)體系結(jié) 1.4.2并行編程環(huán)境....................并行算法..........................1.5.1并行算法的分類..................1.5.2并行算法的發(fā)展階段................習(xí)...............................2LinuxLinux安裝與使用入門..................2.1.1Linux系統(tǒng)的安裝.................2.1.2基本使用與管理..................Linux基本命令和概念..................2.2.1一些基本命令....................2.2.2 ........................2.2.3文本文件處理....................程序開(kāi)發(fā)環(huán)境.......................2.3.1第一個(gè)程序(C程序)...............2.3.2Fortran程序的開(kāi)發(fā)................2.3.3軟件開(kāi)發(fā)......................第3章消息傳遞編程接口 單機(jī)環(huán)境下MPICH的安裝.. 機(jī)群環(huán)境下MPICH的安裝.. MPI編程................ MPI編程的基本概 程序基本結(jié) MPI的原始數(shù)據(jù)類 點(diǎn)對(duì)點(diǎn)通信函數(shù)與通信模 聚合通信與同步..................自定義數(shù)據(jù)類型..................進(jìn)程組與通信器..................進(jìn)程拓?fù)浣Y(jié)構(gòu)....................文件輸入/輸出...................程序主要結(jié)構(gòu)....................習(xí) 4程序性能評(píng)價(jià)并行程序執(zhí)行時(shí)間.....................并行加速比與效率.....................并行程序性能評(píng)價(jià)方法..................4.3.1浮點(diǎn)峰值性能與實(shí)際浮點(diǎn)..........4.3.2數(shù)值效率和并行效率................可擴(kuò)展分析.........................程序性能優(yōu)化........................4.5.1串行程序性能.................4.5.2并行程序性能.................習(xí)...............................第2部分并行算法設(shè)計(jì)與實(shí)現(xiàn)實(shí) 第5章自適應(yīng)數(shù)值積 梯形積分公 局部二分自適應(yīng)區(qū)間加 串行程 基于簡(jiǎn)單區(qū)域分解的并行算 基于主從模式的并行算 基于非阻塞通信的并行程 基于動(dòng)態(tài)負(fù)載調(diào)度的并行算法基于動(dòng)態(tài)負(fù)載調(diào)度的并行算法..............習(xí)...............................第6章矩陣并行計(jì) 并行矩陣乘 串行矩陣乘 行列劃分算 行行劃分算 列列劃分算 列行劃分算 Cannon算 線性代數(shù)方程組并行求解方 分布式系統(tǒng)的并行LU分解算 三角方程組的并行解 對(duì)稱正定線性方程組的并行解 Cholesky分解列格式的并行計(jì) 雙曲變換Cholesky分 修正的雙曲變換Cholesky分 三對(duì)角方程組的并行解 經(jīng)典迭代算法的并行 Jacobi迭代 Gauss-Seidel迭代 異步并行迭代 異步并行迭代法基 線性迭代的一般收斂性結(jié) 代數(shù)特征值問(wèn)題的并行求 對(duì)稱三對(duì)角矩陣特征值問(wèn) Householder變 化對(duì)稱矩陣為三對(duì)角矩 習(xí) 第7章FFT算法與應(yīng) 一維串行FFT算 二維串行FFT算 并行FFT算 FFT應(yīng)用示 多項(xiàng)式相 循環(huán)矩陣方程組的求 第8章二維Poisson方 并行算法設(shè) MPI并行程序設(shè) 并行效率分 MPI并行程序的改 習(xí) 第9章二維熱傳導(dǎo)方 空間離散與區(qū)域劃 時(shí)間離散：顯式格 時(shí)間離散：隱式/半隱式格 時(shí)間離散：ADI方 分塊流水線方 模型問(wèn) 模型問(wèn)題的并行效率分 習(xí) 第3部分 附錄 并行程序開(kāi)發(fā)工具與高性能程序 Level1 Level2 Level3 LAPACK軟件包組 LAPACK程序文 LAPACK參數(shù)設(shè) LAPACK使用示 ScaLAPACK體系結(jié) ScaLAPACK程序介 ScaLAPACK安 ScaLAPACK編程指 復(fù)型變 實(shí)型變 并行 FFTW計(jì)算實(shí) PETSc的系統(tǒng)結(jié) PETSc的基本特 PETSc的基本功 PETSc計(jì)算實(shí) PETSc小 MPI參考手MPI函數(shù)、變量速查表..................MPI預(yù)定義的變量及類型................B.2.1C語(yǔ)言MPI原始數(shù)據(jù)類型............B.2.2Fortran77語(yǔ)言MPI原始數(shù)據(jù)類型.......B.2.3預(yù)定義的通信器與進(jìn)程組.............B.2.4用于歸約函數(shù)的預(yù)定義的二目運(yùn)算.......B.2.5C變量類型及預(yù)定義.............B.2.6空對(duì)象.......................B.2.7MPI常量......................B.2.8進(jìn)程拓?fù)浣Y(jié)構(gòu)...................B.2.9通信狀態(tài)信息...................B.2.10錯(cuò)誤碼.......................B.2.11MPI–2...初始化、退出與錯(cuò)誤處理函數(shù)..............點(diǎn)對(duì)點(diǎn)通信......................B.4.1阻塞型通信函數(shù)..................B.4.2非阻塞型通信函數(shù).................B.4.3持久通信函數(shù)...................數(shù)據(jù)類型與打包函數(shù)...................同步與聚合通信函數(shù)...................進(jìn)程組與通信器操作...................B.7.1進(jìn)程組操作.....................B.7.2域內(nèi)通信器操作..................進(jìn)程拓?fù)浣Y(jié) 域間通信器操 時(shí)間函 參考文 名詞索 表三種并行編程環(huán)境主要特征一覽 Linux常用的分 Linux文件的特 Linux常用信 常用環(huán)境變 Bash的環(huán)境變量字符串過(guò) Bash的文件檢測(cè)操 Bash比較兩個(gè)文件的操 Bash的算術(shù)比較及字符串檢測(cè)操 Bash的算術(shù)表達(dá) gdb的基本命 GNUMake常用自動(dòng)變量及含 MPI原始數(shù)據(jù)類 MPI點(diǎn)對(duì)點(diǎn)通信類型及模式匯 MPI–2文件讀寫函數(shù)匯 代碼5.4在4結(jié)點(diǎn)微機(jī)機(jī)群上的運(yùn)行時(shí)間統(tǒng) 按位倒置變 遞推關(guān)系式的流水線計(jì)算流 插Origin–2000結(jié)構(gòu) 并行機(jī)體系結(jié)構(gòu)示意圖：內(nèi)存模塊與結(jié)點(diǎn)分 并行機(jī)體系結(jié)構(gòu)示意圖：內(nèi)存模塊位于結(jié)點(diǎn)內(nèi) 含4個(gè)結(jié)點(diǎn)的一維陣列和環(huán)的拓?fù)浣Y(jié) 含44個(gè)結(jié)點(diǎn)的二維網(wǎng)格和網(wǎng)格環(huán)的拓?fù)浣Y(jié) 含8個(gè)結(jié)點(diǎn)的二叉樹(shù)和X–樹(shù)的拓?fù)浣Y(jié) 超立方體拓?fù)浣Y(jié) 動(dòng)態(tài)拓?fù)浣Y(jié) 多級(jí)結(jié)構(gòu)示意 Cache讀操作工作流程示意 SMP體系結(jié)構(gòu)典型示意 MPP體系結(jié)構(gòu)典型示意 單進(jìn)程多線程執(zhí)行示意 消息傳遞進(jìn)程拓?fù)浣Y(jié)構(gòu)和并行機(jī)模 top命令抓 Emacs屏幕截 Doxygen生成的LATEX文 Doxygen生成的HTML文 自適應(yīng)梯形公式計(jì)算定積 使用3個(gè)處理機(jī)求解下三角線性代數(shù)方程 FFT數(shù)據(jù)依賴關(guān) DIFFFT計(jì)算過(guò) 兩種區(qū)域分解策 3的二維塊區(qū)域分 輔助網(wǎng)格單元示意 流水線方法計(jì)算流程示意 分塊流水線方法計(jì)算時(shí)間變化曲 LAPACK軟件 結(jié) ScaLAPACK軟件的層次結(jié) ScaLAPACK軟件 PETSc實(shí)現(xiàn)的層次結(jié) 稀疏矩陣結(jié)構(gòu)：二維拉斯方 非線性求解器(SNES)的主要計(jì)算流 TS的主要計(jì)算流程：隱式Euler方 第1部分1并行計(jì)算是伴隨并行機(jī)的出現(xiàn)，在近30年來(lái)迅速發(fā)展的一同，并行地執(zhí)行而達(dá)到加速求解速度，或者求解應(yīng)用問(wèn)題規(guī)模的目的由此，為了成功開(kāi)展并行計(jì)算，必須具備三個(gè)基本條件：應(yīng)用問(wèn)題必須具有并行度。也就是說(shuō)，應(yīng)用可以分解為多個(gè)子2個(gè)星期（14天），這個(gè)速度對(duì)一般的應(yīng)用而言，是無(wú)法100臺(tái)處理器，加速50倍，將執(zhí)行時(shí)間縮短為6.72個(gè)小時(shí)提高求解問(wèn)題的規(guī)模。例如，在單處理器上，受內(nèi)存資源的限制，只能計(jì)算10萬(wàn)個(gè)網(wǎng)格，但是，當(dāng)前數(shù)值模擬要求計(jì)算千萬(wàn)個(gè)網(wǎng)格。于是，也可以借助并行計(jì)算，使用100個(gè)處理將問(wèn)題求解規(guī)模線性地?cái)U(kuò)大100倍并行計(jì)算之所以必需，主要在于，當(dāng)前的單處理器性能不可能滿足大規(guī)?？茖W(xué)與工程計(jì)算及商業(yè)應(yīng)用的需求，并行計(jì)算是目前唯一能滿足實(shí)際大規(guī)模計(jì)算需求的支撐技術(shù)。例如，即使是當(dāng)前較為先進(jìn)的微處理器（Itanium–II1.5GHz、POWER41.5GHz等值性能也僅為60億次/秒。近2年內(nèi)，微處理器的峰值性能也不會(huì)超過(guò)100億次/秒。并行計(jì)算之所以可行，主要在于，并發(fā)性是物質(zhì)并行機(jī)的高性能特征抽取。主要任務(wù)在于，充分理解和抽取當(dāng)前并行機(jī)體系結(jié)構(gòu)的高性能特征，提出實(shí)用的并行計(jì)算模型和并行算法設(shè)計(jì)與分析。針對(duì)應(yīng)用領(lǐng)域?qū)＜仪蠼飧黝悜?yīng)用問(wèn)題的MPI[20或者并行算法和并行程序。一個(gè)沒(méi)有經(jīng)過(guò)實(shí)際應(yīng)用驗(yàn)證和確認(rèn)的算的基礎(chǔ)，第2、3部分是并行計(jì)算研究的，也是在并行機(jī)上高效求解應(yīng)用問(wèn)題的基本保證，第4部分是并行計(jì)算研究的目也是驗(yàn)證和確認(rèn)并行計(jì)算研究成果的最有效的途徑。第4部分將為第2、3需要說(shuō)明的是，并行計(jì)算不同于分布式計(jì)算（distributedcom-下面給出并行計(jì)算和分布式計(jì)算的幾個(gè)例子，以示區(qū)別例1.1:（并行計(jì)算）N個(gè)數(shù)被分布在P臺(tái)處理器，P臺(tái)處理1.2:（并行計(jì)算Dirichlet問(wèn)題?uf，5NNxNy個(gè)網(wǎng)格單PPxPyJacobi迭Dirichlet問(wèn)題，從而達(dá)到縮短求解問(wèn)題的時(shí)間，或者擴(kuò)大網(wǎng)格規(guī)模N的目的。，例1.3:（分布式計(jì)算）觀眾點(diǎn)播駕馭式可視化，電視會(huì)議等，大規(guī)?？茖W(xué)與工程計(jì)算應(yīng)用對(duì)并行計(jì)算的需求是推動(dòng)的。全球氣象預(yù)報(bào)中期天氣預(yù)報(bào)模式要求在24小時(shí)內(nèi)完48小時(shí)天氣預(yù)測(cè)數(shù)值模擬，此時(shí)，至少需要計(jì)算635 存需求大于1TB，計(jì)算性能要求高達(dá)25 億次、30萬(wàn)億次和100萬(wàn)億次的大規(guī)模并行數(shù)值模擬，實(shí)現(xiàn)全三維、全物理過(guò)程、高分辨率的核數(shù)值模擬。除此之外，在天體物理、，近10年來(lái)在大規(guī)模科學(xué)與工程計(jì)算應(yīng)用領(lǐng)域啟動(dòng)了三，第一次是在1983年，配合星球大戰(zhàn)防御計(jì)劃而開(kāi)展的計(jì)算機(jī)計(jì)劃（SCP），研制了每秒十億次CRAY并行機(jī)。第二次是在993年，由科學(xué)、工程、技術(shù)協(xié)調(diào)委員會(huì)向國(guó)會(huì)倡議的“重大性項(xiàng)目：高性能計(jì)算與通信（HC計(jì)T（1Tops1TB內(nèi)存容量和TB/s的I/OT1012學(xué)與工程計(jì)算中的重大性課題，保持其在高性能計(jì)算和計(jì)算機(jī)通信領(lǐng)域中的世界領(lǐng)先地位，利用高性能計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)刺激生高性能計(jì)算機(jī)系統(tǒng)（PC（AA（NREN（BRHR對(duì)一大批重要應(yīng)用問(wèn)題，計(jì)算性能要達(dá)到每秒萬(wàn)億次運(yùn)2發(fā)展相關(guān)的系統(tǒng)軟件，對(duì)一大批問(wèn)題改進(jìn)算法；3國(guó)家研究網(wǎng)能力要達(dá)到每秒十億位；4充分保證計(jì)算機(jī)科學(xué)與工程領(lǐng)域的科研人員的需求。HPCC計(jì)劃背景是一大批巨大性問(wèn)題需要解決，其空氣污染，蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)，金星圖象分析和破譯技術(shù)。世界上第一臺(tái)峰值速度超過(guò)1T?ops的高性能計(jì)算機(jī)由In公司于1996年12月成功研制。我國(guó)863高科技計(jì)劃也將并行計(jì)算機(jī)的研制列為關(guān)鍵攻關(guān)技術(shù)。第三次在1996年，能源部聯(lián)合三大核 Alamos國(guó)家、LawrenceLivermore國(guó)家和Sandia國(guó)力。為此，三大分別向三大公司（In 、IBM和SGI）預(yù)定了峰值速度超過(guò)1T?ops的并行機(jī)計(jì)劃分四個(gè)階段分別實(shí)現(xiàn)萬(wàn)以TOP500[9]中第1的峰值性能為185萬(wàn)億次的IBMBlueGene/L為標(biāo)志，四個(gè)階段的并行機(jī)研制已經(jīng)初步實(shí)現(xiàn)。目前，整個(gè)ASCI計(jì)劃發(fā)展到第2個(gè)階段改名為“先進(jìn)模擬計(jì)算計(jì)劃(ASC)”。對(duì)應(yīng)于的ASCI計(jì)劃，和歐洲也提出了相應(yīng)對(duì)策。尤其是，以2002年研制的EarthSimulator[9]及其在大氣海洋環(huán)流除了大規(guī)模科學(xué)與工程計(jì)算應(yīng)用外，微電子技術(shù)與大規(guī)模集成電路LI的發(fā)展是推進(jìn)并行計(jì)算發(fā)展的另一個(gè)主要?jiǎng)恿?。?dāng)前，ooe定律仍在延續(xù)，計(jì)算機(jī)微處理器的速度每3年翻兩番，內(nèi)存容量每?jī)赡攴C4連技飛展行絡(luò)延遲可低于1個(gè)微秒，帶寬可達(dá)GB/s，并行機(jī)網(wǎng)絡(luò)延遲可低于6.2GB/s行編程模式帶來(lái)新的。當(dāng)前，如何快速地開(kāi)發(fā)并行應(yīng)用程序，高效率地發(fā)揮當(dāng)前并行機(jī)的峰值性能，已經(jīng)成為當(dāng)前并行計(jì)算研究的一個(gè)性問(wèn)題。7080年代蓬勃發(fā)展和百家爭(zhēng)鳴，90年代體系結(jié)構(gòu)框架趨于統(tǒng)一，近5年來(lái)機(jī)群技術(shù)的快速發(fā)展，市場(chǎng)需求一直是推動(dòng)并行計(jì)算機(jī)發(fā)展的主要?jiǎng)恿?，大量?shí)際應(yīng)高性能并行計(jì)算機(jī)的研制與應(yīng)用水平，一直是以和為首的各個(gè)發(fā)達(dá)國(guó)家共同追逐的目標(biāo)，是衡量一個(gè)國(guó)家科技、經(jīng)濟(jì)和HC計(jì)劃701972ILLIACIV32型機(jī)器。對(duì)大量流體力學(xué)程序，ILLIACIV2–6倍于當(dāng)時(shí)性能最高的CDC7600機(jī)器的速度。0年代誕生的并行機(jī)還有陣列機(jī)ICLPGooerPP及向量機(jī)CY–1-00ID量機(jī)CY–170年代的并行計(jì)算機(jī)引起了人們的極大，吸引了大量的專家學(xué)者從事于并行計(jì)算機(jī)研80年代并行計(jì)算機(jī)的蓬勃發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)。8080年代早期，以MIMD并行機(jī)的研制為主。首先誕生的是DenelcorHEP，含16臺(tái)處理機(jī)，共享，能同時(shí)支持細(xì)粒度和其次，誕生了共享向量多處理機(jī)CRAYX–MP/22（2個(gè)向量機(jī)能。同時(shí)，以超立方體結(jié)構(gòu)連接的分布式MIMD結(jié)構(gòu)原型機(jī)開(kāi)80功的機(jī)器為Sequent（20個(gè)結(jié)點(diǎn)、Encore（16-32個(gè)結(jié)點(diǎn)它們提列串行機(jī)構(gòu)成了嚴(yán)重的。同時(shí)，還誕生了8個(gè)結(jié)點(diǎn)的向量多處理機(jī)Alliant，它提供了非常好的自量并行編譯技術(shù)；誕生了4CRAY–2。這些向量多處理機(jī)系統(tǒng)在實(shí)際應(yīng)用此期間還誕生了可擴(kuò)展的分布IDPE機(jī)器含04個(gè)點(diǎn)CPU和單元均分布包含在結(jié)點(diǎn)，所有結(jié)點(diǎn)通過(guò)超立方體網(wǎng)絡(luò)相互連接，支持消息傳遞并行編程環(huán)境，并真正投入實(shí)際使用。由于該機(jī)對(duì)流體力學(xué)中的幾個(gè)實(shí)際應(yīng)用問(wèn)題獲得了超過(guò)100的加速比，引起了計(jì)算機(jī)界的轟動(dòng)，改變了人們對(duì)hl當(dāng)時(shí)，在分布式體系結(jié)構(gòu)中，處理機(jī)間的消息傳遞與消息長(zhǎng)度、處理機(jī)間的距離有較大的關(guān)系。因此互連網(wǎng)絡(luò)最優(yōu)拓?fù)溥B接和數(shù)據(jù)包路由選擇算法的研究引起了人們的大量注意，目的在于減少處理機(jī)遠(yuǎn)端的花費(fèi)。8080年代后期，真正具有強(qiáng)大計(jì)算能力的并行機(jī)開(kāi)始出現(xiàn)。例如，Meiko系統(tǒng)，由400個(gè)T800Transputer通過(guò)二維Mesh相互連和DAP，其中CM–2對(duì)Linpack測(cè)試獲得了5.2G?ops的性能；超立方體連接的分布MIMD并行機(jī)nCUBE–2與In 分別可擴(kuò)展到8K個(gè)結(jié)點(diǎn)和128個(gè)結(jié)點(diǎn)，峰值性能達(dá)27G?ops和7G?ops；由硬件支持共享機(jī)制的BBNTC2000，用Butter?y多級(jí)互連網(wǎng)連接處理機(jī)和模塊，可擴(kuò)展到500臺(tái)處理機(jī)，本地cache內(nèi)存和遠(yuǎn)端內(nèi)存的延遲時(shí)間為1:3:7；共享向量多處理機(jī)系統(tǒng)CRAYY–MP，能獲得很好的實(shí)際運(yùn)算性能。90的微處理的性能幾乎以每18個(gè)月增長(zhǎng)1倍、內(nèi)存容量每年幾為了滿足HPCC計(jì)劃中高性能計(jì)算要求考慮到共享存布式MPP系統(tǒng)，使得MPP的硬件和軟件系統(tǒng)得到了長(zhǎng)足的發(fā)Fortran（HPF）這一時(shí)期，MIMD類型占據(jù)絕對(duì)主導(dǎo)位置。用于科學(xué)與工程計(jì)SIMD類型并行機(jī)和單純的向量機(jī)已逐漸退出歷史舞臺(tái)，但以單個(gè)向量機(jī)為結(jié)點(diǎn)構(gòu)成的MIMD并行機(jī)仍然在實(shí)際應(yīng)用中發(fā)揮重這段時(shí)間出現(xiàn)的分布式MPP并行機(jī)主要有CM–5E16–1KRISCSPARC處理器（含四個(gè)向量部 ParagonXP/S，含24–3K個(gè)i860/XP微處理（主CRAYT3D，16–1K2個(gè)處理器（64RISCDECchip21064150M?ops）64MB，最大128GBTorusSP21616個(gè)處理器（POWER–2芯關(guān)HPS連接，機(jī)柜之間采用信息傳遞光纖網(wǎng)絡(luò)連接。在共享方面由向量機(jī)構(gòu)成的并行機(jī)CRAYY-MPC90(1616G?ops)YH-24臺(tái)向量機(jī)，峰值性能1G?ops)也誕生了，在應(yīng)用問(wèn)題中發(fā)揮了重要作用。思想已經(jīng)們接受。這方面的代表機(jī)型為1991生產(chǎn)的Kendall為15G?ops。90SUNUltraSPARC250MHz1G?ops第一，以高性能微處理和互連網(wǎng)絡(luò)通信技術(shù)為基礎(chǔ)，共享存儲(chǔ)對(duì)稱多處理機(jī)SP系統(tǒng)得到了迅速發(fā)展。它們大多以高性能服務(wù)器的面目出現(xiàn)，能提供每秒幾百億次的浮點(diǎn)運(yùn)算能力、幾十個(gè)GB的內(nèi)存和超過(guò)GBcI/O64UltraSPARC處理器（250MB，2MBcache），12.8GB/Sec，I/O帶寬為64GB/Sec。它采用標(biāo)準(zhǔn)UNIX操作系統(tǒng)，支持共享、消息傳遞并行程序設(shè)計(jì)。類似的SMP系統(tǒng)還有SGIPowerChallengeR10000，HPC–240，DECAlphaserver400C等，這第二，以微處理為的工作站能提供近1G?ops的計(jì)算MB的內(nèi)存，能單獨(dú)承擔(dān)一定的計(jì)算任務(wù)。并且，將多備一定的并行支撐軟件，形成一個(gè)松散耦合的并行計(jì)算環(huán)境，協(xié)同地并行求解同一個(gè)問(wèn)題，稱之為工作站機(jī)群（NOWs：NetworkOfPVM、MPI消息傳遞并行程序設(shè)計(jì)軟件支撐環(huán)境，序設(shè)計(jì)難等許多亟待解決的問(wèn)題，吸引了大量國(guó)內(nèi)外專家學(xué)者的注意力。易被用戶接受的缺點(diǎn)，單純的分布式并行機(jī)已經(jīng)朝分布共享方向發(fā)展。它們都采用最先進(jìn)的微處理作為處理單元，單元內(nèi)配備有較大的局部cache 所有結(jié)點(diǎn)通過(guò)高性能網(wǎng)絡(luò)相互連接，從而用戶可以采用共享或數(shù)據(jù)并行的并行程序設(shè)計(jì)方式，并且自由地申請(qǐng)結(jié)點(diǎn)個(gè)數(shù)和內(nèi)存大小。DSMCC–NUMA結(jié)構(gòu)具有比SMPSMP的共能。但是，它并不能完全避免SMP結(jié)構(gòu)中出現(xiàn)的內(nèi)存瓶頸問(wèn)SMP的折衷機(jī)型。CC-NUMASGIOrigin系列超級(jí)服務(wù)器，它是基于directory）CC-NUMA1.1Origin–20008個(gè)機(jī)柜，每個(gè)8個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)是構(gòu)成Origin–2000的基本單位，它包含：1–2195MHzR10000CPUCPU4MB的二級(jí)cache；512MB–4GB，分主存（mainmemory）和內(nèi)存（direc-torymemory，用于保持結(jié)點(diǎn)間的cache一致性）；集線器（HUB）4個(gè)端口（interface）：CPU端口、內(nèi)存端口、XIO端口、CrayLink互連網(wǎng)絡(luò)端口，采用交叉開(kāi)關(guān)實(shí)現(xiàn)兩個(gè)CPU、內(nèi)存、輸入輸出和互連網(wǎng)絡(luò)路由器（router）之間的1.5GB/sOrigin–2000CrayLink網(wǎng)絡(luò)相互連接。路由器是構(gòu)9.3GB/s的現(xiàn)路由器間的互連，形成互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。CrayLink的半分帶寬能，512GB的內(nèi)存，已近千億次并行計(jì)算的要求。Origin–2000采用標(biāo)準(zhǔn)UNIX操作系統(tǒng)，支持共享、數(shù)據(jù)并1.1Origin–2000結(jié)構(gòu)NUA即原分式機(jī)基上，局部?jī)?nèi)存的全局共享功能，提供共享并行編程環(huán)境。它們能繼持分布式并行機(jī)的可擴(kuò)展性，但當(dāng)處理機(jī)臺(tái)數(shù)較多時(shí)，也只有息傳遞并行程序設(shè)計(jì)方式才能發(fā)揮它們的潛在并行計(jì)算性能。這方面的典型代表為CyT3E和CyT-100個(gè)CP（主頻00H值性能達(dá)到.T?op。20002000年以來(lái)，受重大計(jì)算需求的牽引和微處理器及高速展。至2005年底，國(guó)內(nèi)陸續(xù)安裝到位的萬(wàn)億次并行機(jī)將近20臺(tái)用型的并行機(jī)系統(tǒng)，以微機(jī)機(jī)群為典型代表，它們具有優(yōu)良的性能應(yīng)用問(wèn)題而定制的MPP 系統(tǒng)，通常為國(guó)家的應(yīng)用而特殊定制。從體系結(jié)構(gòu)的角度，當(dāng)前并行機(jī)的體系結(jié)構(gòu)可分為如下三類[10]：機(jī)群(cluster)系統(tǒng)由結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)包含2-4個(gè)微處理器，采用機(jī)換機(jī)連接結(jié)點(diǎn)，結(jié)點(diǎn)間分布目前機(jī)群采用的典型64位微處理器代表為IBMPPC、2.2GHz，InItanium–II1.5GHz，AMDOpteron2.2GHz，峰值1.25GB/s)128個(gè)目前，2005年6月TOP500第5位的IBMJS20機(jī)群（巴塞羅拉超級(jí)計(jì)算機(jī)中心、4800IBMPPC9702.2GHz、Myrinet互連、峰值性能每秒42萬(wàn)億次）第7位的CDCThunder(LLNL4096InItanium–IITiger41.4GHz、Quadrics互連、峰值性能每中心、2560AMDOpteron2.2GHz、Myrinet互連、峰值性能、機(jī)群系統(tǒng)占據(jù)了304臺(tái)套，占絕對(duì)優(yōu)勢(shì)星群(conslation)。它們也有三個(gè)明顯的特征系統(tǒng)由結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)是一臺(tái)共享或者分布共享采用機(jī)換機(jī)連接結(jié)點(diǎn)，結(jié)點(diǎn)間分布在各個(gè)結(jié)點(diǎn)上，運(yùn)行的結(jié)點(diǎn)操作系統(tǒng)、編譯系統(tǒng)和作業(yè)管理系統(tǒng)。星群的典型代表為TOP500第3位的SGIColumbia系統(tǒng)（NASA/Ames/NAS、20個(gè)結(jié)點(diǎn)通過(guò)VoltaireIn?niBandSGIAltix3700系統(tǒng)（含由SGINUMAlink512Itanium–II1.5GHz處理器SGILinux61萬(wàn)億次。20056月的TOP500中，星群占據(jù)79臺(tái)套。大規(guī)模并行機(jī)系統(tǒng)（MPP：MassivelyParallelProcessing）。它系統(tǒng)由結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)含10個(gè)左右處理器，共享。處理器采用或者CPU。采用高性能網(wǎng)絡(luò)互連，結(jié)點(diǎn)間分布系統(tǒng)運(yùn)行操作系統(tǒng)、編譯系統(tǒng)和作業(yè)管理系統(tǒng)此類系統(tǒng)是傳統(tǒng)意義的大規(guī)模并行處理系統(tǒng)。它區(qū)別于其他兩種體系結(jié)構(gòu)的一個(gè)特征就是，它的處理器或者結(jié)點(diǎn)間的互連網(wǎng)絡(luò)是針對(duì)應(yīng)用需求而特殊定制的，在某種程度上，帶有并理器個(gè)數(shù)可擴(kuò)展到數(shù)十萬(wàn)個(gè)。MPP的典型代表為第1位的IBMBlueGene/L(DOE/NNSA/LLNL、65536顆IBMPowerPC440700MHz處理器、IBMProprietary互連網(wǎng)、峰值性能每秒184萬(wàn)億次)，另一個(gè)典型代表是第4位的NECEarth-Simulator(地球模擬中心、640個(gè)結(jié)點(diǎn)通過(guò)Multi-satge交叉開(kāi)關(guān)互連、每個(gè)結(jié)點(diǎn)含8顆向量處理表是第10位的CRAYRedStorm（Sandia國(guó)家實(shí)驗(yàn)室、1250個(gè)結(jié)點(diǎn)通過(guò)CRAYXT3互連網(wǎng)絡(luò)連接、每個(gè)結(jié)點(diǎn)4AMDOpteron2GHz20萬(wàn)億次。20056TOP500中，MPP117臺(tái)套。以上僅簡(jiǎn)單地討論了并行機(jī)的發(fā)展。如果讀者希望詳細(xì)了解當(dāng)考TP00[9]內(nèi)TOP00[]。當(dāng)前，如圖1.2和圖1.3所示，組成并行機(jī)的三個(gè)要素結(jié)點(diǎn)（node）互聯(lián)網(wǎng)絡(luò)（iterconnectnetwrk）。所有結(jié)點(diǎn)通過(guò)互聯(lián)網(wǎng)絡(luò)相互1.2所示所示，位于各個(gè)結(jié)點(diǎn)的內(nèi)部結(jié)結(jié)點(diǎn)是構(gòu)成并行機(jī)的最基本單位。以圖1.3為例結(jié)點(diǎn)個(gè)進(jìn)程將并行地運(yùn)行在結(jié)點(diǎn)的各個(gè)微處理器上。每個(gè)微處理器擁有 局部的二級(jí)高速緩存（L2cache）。L2cache是現(xiàn)代高性能微處理器用于彌補(bǔ)日益增長(zhǎng)的CPU執(zhí)行速度和內(nèi)存速度差距（訪存墻）而采取的關(guān)鍵部件。它按cache映射策略緩存內(nèi)存的數(shù)據(jù)，同CPUcache提供計(jì)算數(shù)據(jù)。CPUcache些內(nèi)容。有者請(qǐng)參考專著[12]。當(dāng)前，集線器可以提供給微處理器每秒數(shù)十GB的訪存帶寬和百個(gè)納秒之內(nèi)的訪存延遲，以及最快每秒6.4GB的互聯(lián)網(wǎng)絡(luò)帶寬。當(dāng)處理器個(gè)數(shù)較少時(shí)，例如8–16個(gè)以內(nèi)，集線器一般采用高速傳統(tǒng)地，11小。例如，10.4個(gè)字節(jié)的內(nèi)存單元。如果604個(gè)處理器的單結(jié)2408GB以上。于是，64首先，介紹互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的幾個(gè)重要定義結(jié)點(diǎn)距離：兩個(gè)結(jié)點(diǎn)之間的圖的邊的最少條數(shù)網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)距離延遲稱為網(wǎng)絡(luò)的最小延遲，所有結(jié)點(diǎn)之間的最大延遲稱為網(wǎng)絡(luò)的最大延遲；折半寬度對(duì)分帶寬（它們的結(jié)點(diǎn)數(shù)相等，或者至多相差1）時(shí)，必須去掉的邊的最少條數(shù)，或1.1:L與它們之間的距離m有一個(gè)簡(jiǎn)單的關(guān)系式 其中，L0為相鄰兩個(gè)結(jié)點(diǎn)之間的延遲，δ表示消息一個(gè)結(jié)點(diǎn)所需的開(kāi)銷。一般的，δ!L0。因此，當(dāng)并行機(jī)包含的結(jié)點(diǎn)個(gè)數(shù)較少控制在2個(gè)微秒差之內(nèi)1.2:點(diǎn)對(duì)點(diǎn)帶寬是指連接兩個(gè)結(jié)點(diǎn)之間的物理通道在單位時(shí)間內(nèi)可傳輸?shù)淖止?jié)總數(shù)。通常這種傳輸是即沿兩個(gè)不同的:BN的消息傳遞的時(shí)間可近似寫為：TpNq N 結(jié)構(gòu)中，如果兩個(gè)結(jié)點(diǎn)之間存在直接物理連接，則稱之互為相鄰結(jié)點(diǎn)。論著[2]詳細(xì)地討論了當(dāng)前并行機(jī)采用的各類靜態(tài)拓?fù)浣Y(jié)構(gòu)，包括陣(array)(ring)、網(wǎng)格(mesh)、網(wǎng)格環(huán)(torus，也叫環(huán)面)、樹(shù)1.4(a)PP個(gè)pijij0P1，相互連接的充要條 1i, 0,..., 1.4(b)PPpi和結(jié)點(diǎn)pj相互連接的充要條件是： 1mod 0,..., 高到2，網(wǎng)絡(luò)直徑從P1減少rP2s1，是對(duì)一維陣列的有效改(a)一維陣 (b)1.44網(wǎng)格和網(wǎng)格環(huán)如圖1.5(a)所示，d(d?2)維網(wǎng)格包含PP0P1 Pd1個(gè)結(jié)點(diǎn)，所有結(jié)點(diǎn)排列成d維陣列，結(jié)點(diǎn)0,i1,,id1q和結(jié)點(diǎn)0,j1,,jd1q相互連接的充要條件是

1

?如圖1.5(b)所示，d(d?2)維網(wǎng)格環(huán)包含PP0P1 Pd1個(gè)結(jié)點(diǎn)，所有結(jié)點(diǎn)排列成d維陣列，結(jié)點(diǎn)0,i1,,id1q和結(jié)點(diǎn)0,j1,,jd1q相互連接的充要條件是?容易容易看出，網(wǎng)格和網(wǎng)格環(huán)的結(jié)點(diǎn)的度均為2d，網(wǎng)格的網(wǎng)絡(luò)直

1: jk 1mod

d1 1q，而網(wǎng)格環(huán)的網(wǎng)絡(luò)直徑等 d1prPks1q有關(guān)網(wǎng)k k 和網(wǎng)格環(huán)的折半寬度，請(qǐng)讀者自己計(jì)算(作業(yè)3)樹(shù)如圖1.6(a)所示，標(biāo)準(zhǔn)二叉樹(shù)拓?fù)浣Y(jié)構(gòu)包含P 2N個(gè)葉結(jié)二維網(wǎng)圖1.5含 4個(gè)結(jié)點(diǎn)的二維網(wǎng)格和網(wǎng)格環(huán)的拓?fù)浣Y(jié)2logP，非據(jù)等，但是，它的折半寬度只為1，不利于結(jié)點(diǎn)之間的大數(shù)據(jù)量通信X–1.68個(gè)結(jié)點(diǎn)的二叉樹(shù)和X–樹(shù)的拓?fù)浣Y(jié)是將每層結(jié)點(diǎn)形成環(huán)；或者也就是多叉?zhèn)€內(nèi)結(jié)點(diǎn)的超立1.7(a)和圖1.7(b)所示，d維超立(d包含 2d個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)i的二進(jìn)制編號(hào) id 0, 結(jié)點(diǎn) id1和結(jié)點(diǎn) jd1相互連接的充要條件 1 Dp?

2d1d，隨并行機(jī)規(guī)模的增加而增不超過(guò)5維。例如，SGIOrigin系列并行計(jì)算機(jī)的SuperLinker網(wǎng)絡(luò)，采用5維的嵌套超立方體拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)高效的通信。動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)是指，結(jié)點(diǎn)之間無(wú)固定的物理連接，而是在連接路徑的交叉點(diǎn)處用電子開(kāi)關(guān)、路由器或仲裁器等提供動(dòng)態(tài)連接，主要單總線接理模塊和/O備座，在主設(shè)備（處理器）和從設(shè)備（器）之間傳遞數(shù)據(jù)，其特征(a)三維超立方1.7超立方體拓?fù)浣Y(jié)150MHz，總線寬度為64位，則該總線的帶寬為采用公平的協(xié)議與仲裁算法，以確定在某個(gè)時(shí)刻選擇哪個(gè)例如，SGIPowerChallengeXL系列共享服務(wù)器，多個(gè)CPU共享總線，在處理器和模塊之間傳遞數(shù)據(jù)。又如，IBM并行機(jī)ASCIWhite16IBMPowerPC處理器，結(jié)點(diǎn)內(nèi)大多數(shù)用于充當(dāng)并行機(jī)單個(gè)結(jié)點(diǎn)內(nèi)部多個(gè)CPU之間的連接通道。多層總線在并行機(jī)的結(jié)點(diǎn)內(nèi)部，多個(gè)處理器共享本地總線，而單一可擴(kuò)展能力。圖1.8(a)給交叉開(kāi)關(guān)(crossbarswitch)所有結(jié)點(diǎn)通過(guò)交叉開(kāi)關(guān)陣列相互和“閉”兩種狀態(tài)。圖1.8(b)給出了一個(gè)4 4的交叉開(kāi)關(guān)拓?fù)浣Y(jié)兩級(jí)總441.8NN陣列，但在每一行時(shí)只能接通N對(duì)結(jié)點(diǎn)。結(jié)構(gòu)為NN的交叉開(kāi)關(guān)只能提供2N在大規(guī)模并行機(jī)中的應(yīng)用。交叉開(kāi)關(guān)一般僅適合數(shù)個(gè)處理器的情形，或者，在結(jié)點(diǎn)內(nèi)部為處理器和器之間提供快速高效通道。多級(jí)互聯(lián)網(wǎng)絡(luò)(IN:lisageIcocion)連接，可以動(dòng)態(tài)地設(shè)置開(kāi)關(guān)狀態(tài)。多級(jí)互聯(lián)網(wǎng)絡(luò)的典型代表為蝶網(wǎng)、CC網(wǎng)和ees紹，有者請(qǐng)參考[][]。，寬帶互聯(lián)網(wǎng)絡(luò)隨著網(wǎng)絡(luò)技術(shù)的成熟寬帶互聯(lián)網(wǎng)絡(luò)逐步成為連接微機(jī)而構(gòu)成簡(jiǎn)易并行機(jī)的互聯(lián)網(wǎng)絡(luò)，并且，相繼推出了除了MPP系統(tǒng)采用靜態(tài)的拓?fù)浣Y(jié)構(gòu)外，微機(jī)機(jī)群均采用寬帶，(1)以太 (Ethernet)。以太網(wǎng)絡(luò)是早期網(wǎng)絡(luò)連接最常用的802.3國(guó)際標(biāo)準(zhǔn)相繼推出了三代網(wǎng)絡(luò)，性能分別為10Mbps（82為100Mbps，連接8臺(tái)處理機(jī)，則每臺(tái)處理機(jī)的平均帶寬僅為12.5Mbps(2)交換機(jī)（switch）。交換機(jī)內(nèi)部采用全互聯(lián)方式，可同時(shí)(3)微機(jī)機(jī)群互聯(lián)網(wǎng)絡(luò)，它們的功能類似于交換機(jī)，但是，10μs。請(qǐng)參考[13]。6μs。請(qǐng)參考[14]。于6μs。請(qǐng)參考[15]。多級(jí)體系結(jié)得益于主頻和量指令級(jí)流水線技術(shù)的發(fā)展，現(xiàn)代微處理器的發(fā)展仍然遵循ooe定律，峰值運(yùn)算速度每18速度卻沒(méi)有得到平衡的發(fā)展。相比較而言，內(nèi)存的速度要比處理器執(zhí)行速度慢很多，難以發(fā)揮微處理器的峰值速度，這就...(memorywall)為了盡量克服內(nèi)存墻對(duì)性能的影響，一個(gè)簡(jiǎn)捷的方法是，在內(nèi)存和處理器之間增加一個(gè)高速緩沖區(qū)，稱為cache緩存內(nèi)存模塊的部分?jǐn)?shù)據(jù)，盡量將內(nèi)存的轉(zhuǎn)換為對(duì)cache的，cache稱為二cache(L2cache)。在處理器內(nèi)部，還存在一，cachecache(L1cache)。L1cache連接CPUL2cacheL2cache中的數(shù)據(jù)到寄存器中。位于最頂層的是CPU，它從寄存器中數(shù)據(jù)；寄存器從L1cache中數(shù)據(jù)。CPU寄存器和L1cache構(gòu)成微處理器(chip)L1微處理器和L2cache通?？梢暈槲⑻幚砥?。多個(gè)微處理器和它還存在其他結(jié)點(diǎn)的局部?jī)?nèi)存模塊稱之為內(nèi)存空間。顯然，是，訪存速度越來(lái)越快，即訪存延遲越來(lái)越小，帶寬越來(lái)越高。以圖1.9多級(jí)結(jié)構(gòu)示意500MHzIn Pentium–III為處理器的微機(jī)機(jī)群為例假設(shè)處理器之 包括兩個(gè)方面，一個(gè)是cae的映射策略，即ce是如何從內(nèi)存中下面主要從這兩個(gè)方面來(lái)介紹并行機(jī)的多級(jí)體系結(jié)構(gòu)。這些內(nèi)在當(dāng)Cachecache(line)cache線包L8個(gè)字節(jié)。例如，L4cache線包4832個(gè)字節(jié)；L8cache8864個(gè)字個(gè)字cachecache線為基本單位，即數(shù)據(jù)從內(nèi)存調(diào)入cache時(shí)，不是以該單個(gè)數(shù)據(jù)字為單位，而是以Lcache，cachecache線中的位置。因此，通過(guò)cache線的一次調(diào)入，隨后的數(shù)據(jù)可能就落在Fortran循環(huán)。DODOI=1,A(I)=A(I)+5.0*B(I)假設(shè)沒(méi)有cache，則內(nèi)存讀次數(shù)為2M次。如果有cache，則內(nèi)存次數(shù)下降為2M{L次。從而，由前面的多級(jí)結(jié)構(gòu)性能分析數(shù)據(jù)可知，cache的使用必定加快程序的執(zhí)行速度。一次內(nèi)存操作，如果操作數(shù)存在于cache中，則稱該次問(wèn)是cache..的，否則，稱該次cache..的。為了衡量cachecache為，程序執(zhí)行過(guò)程中，cache命Cachecache容量、cache線大小、cache個(gè)數(shù)、cache的映射策略、cache線的置換策略、cache數(shù)Cache中，大量數(shù)據(jù)表明，超大容量cache并不能顯著提高性能，反而顯著容量一般為1MB–16MB，且只程序的數(shù)據(jù)；L1cache的容量比L2cache的容量小幾個(gè)數(shù)量級(jí)，一般為數(shù)KB到數(shù)十KB。CacheCache大小也應(yīng)該有一個(gè)合適的長(zhǎng)度。當(dāng)前，cache4–8Cachecache一般還分為兩個(gè)一個(gè)指令，另一個(gè)數(shù)據(jù)。二級(jí)cacheCachecache線之間建立相互映射關(guān)系，是具體實(shí)現(xiàn)只能到被映射的cache線中，而cache線中的數(shù)據(jù)也能夠且只能被映射到對(duì)應(yīng)的內(nèi)存塊中。當(dāng)前，cache的映射策略可分為.....、K–...............所謂直接映射策略，指每個(gè)內(nèi)存塊只能被唯一地映射到一條cae線中。cacheM2rcache(每條線的長(zhǎng)度L2w個(gè)字)j塊內(nèi)存將被映射到第i條cache線中，其中 mod 假設(shè)內(nèi)存地址空間（以字為單位）總共可用 psrqrw位表示cache線之間的映射關(guān)系條cache線對(duì)應(yīng)2sr個(gè)內(nèi)存塊。例如，假D20r8w表示，內(nèi)存總共包含220個(gè)字，cache包含 28條線cache線的422個(gè)字。則內(nèi)存中地址為aa0a1a19a20的字將被唯一地映射到第ba11a18條cache線的ca19a20個(gè)字節(jié)處。每cache線對(duì)應(yīng)1024個(gè)連續(xù)的數(shù)據(jù)單元位于不同的內(nèi)存塊中，而這些塊被映射到同一條cache線中，連續(xù)的數(shù)據(jù)將引起頻繁的cache線置cacheMcache線，M2r，cache線L2wNML2rw，假設(shè)程序有四個(gè)數(shù)COMMONCOMMON/XXX/A(N),B(N),C(N),則下面的循環(huán)將發(fā)生嚴(yán)重的cacheDODOI=1,A(I)=A(I)+B(I)+C(I)+D(I)I的同一個(gè)元素被映射到換，cache對(duì)程序的性能沒(méi)有任何改進(jìn)。為了改進(jìn)上面的cache，從程序設(shè)計(jì)的角度，通常采用“補(bǔ)邊法(padding)”，在COMMON塊的設(shè)計(jì)中，每個(gè)數(shù)組的長(zhǎng)數(shù)組之間增加一些輔助數(shù)組，使得各個(gè)數(shù)組至少錯(cuò)開(kāi)一條cachecache線。例COMMONCOMMON/XXX/A(N),X1(K),B(N),X2(K),C(N),X3(K),其實(shí)，在某些編譯器中，有自動(dòng)補(bǔ)邊的優(yōu)化功能K–路組關(guān)聯(lián)映射策略(K–waysetassociationmapCacheVKcache線組成，內(nèi)存塊按直接映射策略映射到某個(gè)組，但是在該組中，內(nèi)存塊可到cache中的K條cache線的任何一條。具體算法為： 址之間的自然cache線長(zhǎng)度2w個(gè)字，cache包含V2dK2rcache線，內(nèi)存空間包含2sw2sdr個(gè)字的內(nèi)存塊被映射到同一個(gè)cache組中。例如，對(duì)前面的例子，如果K4，則cache就可被消除。cache映射策略是2–路或4–路組關(guān)全關(guān)聯(lián)映射策略(fullassociationmap內(nèi)存塊可以被映射到ce中的任意一條e映射策略的實(shí)現(xiàn)比較復(fù)雜，通常只有理論上存在的價(jià)值，在實(shí)際中并不多見(jiàn)。Cache線FIFO(FirstInputFirstOutput)線LFULeastFrequentlyUsed)線隨機(jī)算法：隨機(jī)選擇一條cache線置換Cache顯然，為了保持計(jì)算結(jié)果的正確性，必須設(shè)計(jì)某種策略，保持cache數(shù)據(jù)和內(nèi)存數(shù)據(jù)的一致性。通常有兩Write–through策略：cache線中的數(shù)據(jù)一旦被修改，則立即寫Write–backcache線置換時(shí)，或者有外部請(qǐng)求內(nèi)存塊時(shí)，將cache線的數(shù)據(jù)寫入內(nèi)存。綜上所述，以讀操作為例，cache的工作流程可用圖1.10示意訪存型(UMA：UniformMemoryAccessmodel)(NUMA：Non-UniformMemoryAccessmodel)(DMA：Distri-butedMemoryAccessmodel)及混合訪存模(HMA：HybridMem-oryAccessmodel)四類。本小節(jié)只是簡(jiǎn)單地介紹這些模型的主要特均勻訪存模型。如圖1.2所示，內(nèi)存模塊與結(jié)點(diǎn)分離，分別位1.10Cache讀操作工作流程示意物理器被所有結(jié)點(diǎn)共享所有結(jié)點(diǎn)任意單元的時(shí)間相同CPU可帶有局部私有高速緩存I/O 當(dāng)前對(duì)稱多處理共享并行機(jī)P:SmmeicMti-Processing均采用這種模型。在并行機(jī)的分類中將再討論此類并行機(jī)的主要特征。非均勻訪存模型。如圖.3訪存模型也可稱為分布共享訪存模型。該模型具有如下典型特征：物理器被所有結(jié)點(diǎn)共享，任意結(jié)點(diǎn)可以直接任意結(jié)點(diǎn)內(nèi)存模塊的速度不同：本地模塊的速度一般是其他結(jié)點(diǎn)內(nèi)存模塊的3倍以上；CPU可帶有局部私有高速緩存非均勻訪存模型的典型例子為SGIOrigin系列并行機(jī)，它們采用基于cache Cache–CoherentNonuniformMemoryAccess），設(shè)計(jì)了專門的硬致性。限于篇幅，這里不介紹并行機(jī)各個(gè)結(jié)點(diǎn)之間的cache一1.3所示，并行機(jī)分類單指令多數(shù)據(jù)流（ID：按同一條指令，并行機(jī)的各個(gè)不同的功能部件同時(shí)對(duì)不同的數(shù)據(jù)進(jìn)行不同的處理，例如：傳統(tǒng)的0年代初期的陣列機(jī)CM–行機(jī)可分為對(duì)稱多處理共享并行機(jī)（SMP：SymmetricMulti-Processing）分布共享并行機(jī)（DSM：DistributedSharedMem-MassivelyParallelProcessing）等五類。對(duì)稱多處理共享并行機(jī)（SMP。如圖.11模塊和處理器對(duì)稱地分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)，內(nèi)存屬典型的型SP并行機(jī)有如下主要特征：對(duì)稱共享：系統(tǒng)中任何處理器均可直接任何模塊中的單元和I/O問(wèn)成功的概率是一致的。所有內(nèi)存單元統(tǒng)一編址。各個(gè)處理器之間的地位等價(jià)，不存在任何處理器。操作系統(tǒng)可在任意處理器上運(yùn)行。單一的操作系統(tǒng)映像：全系統(tǒng)只有一個(gè)操作系統(tǒng)駐留在共享器中，它據(jù)各個(gè)處理器的負(fù)載情況，動(dòng)態(tài)分配個(gè)進(jìn)程到各個(gè)處理器，并保持各處理器間的負(fù)載平衡。ace局部cce，它們可以擁有獨(dú)立的局部數(shù)據(jù)，但是這些數(shù)據(jù)必中據(jù)一。/寫操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來(lái)完成處理器間的通信，其延遲通常小于網(wǎng)絡(luò)通信的延遲。共享總線帶寬：所有處理器共享總線的帶寬，完成對(duì)內(nèi)存模塊和I/O模塊的。支持消息傳遞、共享并行程序設(shè)計(jì)SMP欠可靠：總線、器或操作系統(tǒng)失效可導(dǎo)致系統(tǒng)32倍，跟不上處理器速度和內(nèi)存容量的增加步伐，因此，SMP并行機(jī)的處理器個(gè)數(shù)一SMP1.11SMPSGIPOWERChallengeXL系列并行機(jī)（36MIPSR10000微處理器COMPAQAlphaserver84005/440（12Alpha微處理器HP9000/T600（12HPPA9000微處理器IBMRS6000/R40（8RS6000微處理器多處理共享并行機(jī)的可擴(kuò)展能力。DSM并行機(jī)具有如下主個(gè)CPU擁有自己的局部cache，并共享局部器和I/O物理上分布：內(nèi)存模塊分布在各結(jié)點(diǎn)中，并通過(guò)高SMP訪存總線的帶寬瓶頸，單一的內(nèi)存地址空間：盡管內(nèi)存模塊分布在各個(gè)結(jié)點(diǎn)，但網(wǎng)絡(luò)連接形成了并行機(jī)的共享器。各個(gè)結(jié)點(diǎn)既可以直接本地局部?jī)?nèi)存單元，又可以直接其他結(jié)點(diǎn)的局部?jī)?nèi)存單元。非一致內(nèi)存（NUMA）模式：由于遠(yuǎn)端必須通過(guò)高遠(yuǎn)端的延遲一般是本地延遲的3倍以上。單一的操作系統(tǒng)映像：類似于SMP，在DSM并行機(jī)中，cache的數(shù)據(jù)一致性：通常采用基于的cache一致性協(xié)議來(lái)保證各結(jié)點(diǎn)的局部cache數(shù)據(jù)與器中數(shù)據(jù)DSMCC–NUMA低通信延遲與高通信帶寬：的高性能互聯(lián)網(wǎng)絡(luò)使得結(jié)點(diǎn)間的延遲很小，通信帶寬可以擴(kuò)展。例如，SGIOrigin3000的雙向點(diǎn)對(duì)點(diǎn)通信帶寬可達(dá)3.2GB/s1μs。浮點(diǎn)運(yùn)算性能。例如，SGIOrigin–200064個(gè)結(jié)點(diǎn)（512CPU），SGIAltix512個(gè)結(jié)支持消息傳遞、共享并行程序設(shè)計(jì)分布共享并行機(jī)的典型代表為GIOii0（圖.GIOigin300和GIAixGIAix供給用戶的是一個(gè)單一操作系統(tǒng)的用戶交互式界面，可以象工作站一樣被用戶使用。同時(shí)，由于它實(shí)現(xiàn)了全局硬件編址的分布共享，進(jìn)程間消息傳遞的延遲低于1個(gè)微秒，帶寬高達(dá)/機(jī)群系統(tǒng)。請(qǐng)參考第1.2.8節(jié)(第18頁(yè))星群系統(tǒng)。請(qǐng)參考第1.2.8節(jié)(第19頁(yè))儲(chǔ)系統(tǒng)，其體系結(jié)構(gòu)如圖1.12所示。其典型特I/O結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)局部cache，并通過(guò)局部總線或互聯(lián)網(wǎng)絡(luò)與局部?jī)?nèi)存模塊和這些結(jié)點(diǎn)由局部高性能網(wǎng)卡NIC)通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相靜態(tài)拓?fù)浣Y(jié)構(gòu)耦合而成的混合拓?fù)浣Y(jié)構(gòu)，其通信延遲和通信帶寬均明顯優(yōu)于機(jī)群互聯(lián)網(wǎng)絡(luò)。PP的各個(gè)結(jié)點(diǎn)均擁有不同的操作系統(tǒng)映像。一般情況下，用戶可以將作業(yè)提交給作業(yè)管理系統(tǒng)，由它負(fù)責(zé)調(diào)度當(dāng)PP也允許用戶登錄到某個(gè)特定的結(jié)點(diǎn)，或在某些特定的結(jié)點(diǎn)上運(yùn)行作業(yè)。各個(gè)結(jié)點(diǎn)間的內(nèi)存模塊相互獨(dú)立，且不存在全局內(nèi)存單元的統(tǒng)一硬件編址。一般情形下，各個(gè)結(jié)點(diǎn)只能直接自身的局部?jī)?nèi)存模塊，如果要求直接其他結(jié)點(diǎn)的局部?jī)?nèi)Fortran并行程序設(shè)計(jì)，不支持全局共享的OpenMP并行程序設(shè)計(jì)模式。1.12MPP體系結(jié)構(gòu)典型示意當(dāng)前，TOP500中第一的BlueGene/L就是典型MPPMPP1.2.8(19頁(yè))基本概念，重點(diǎn)在于學(xué)習(xí)消息傳遞或者共享并行編程所必須了解UNIX操作系統(tǒng)幾乎是當(dāng)前所有高性能并行機(jī)（SMP、DSM、 lation、MPP）采用的標(biāo)準(zhǔn)操作系統(tǒng)，其中包括SGI公司的IRIX，COMPAQ公司的True64，HP公司的HPUX，IBM公司的AIXSUN公司的Solaris和自由軟件Linux等。雖然各并行機(jī)廠商研制的UNIX操作系統(tǒng)的實(shí)現(xiàn)原理不盡相同，但是，它們給用戶提供的基本UNIX操作系統(tǒng)界面是大體一致的。因此，用戶只要對(duì)UNIX操作系統(tǒng)有一定的了解，就可以方便地使用以上介紹的各在程序設(shè)計(jì)語(yǔ)言方面，SMP、DSMMPP并行機(jī)一般均提供符合國(guó)際標(biāo)準(zhǔn)的Fortran77/90、C/C++、HPF等語(yǔ)言，而機(jī)群系GNUFortran77/95、GNUC/C++等語(yǔ)言。特別地，1.4.2將介紹各類并行機(jī)支持的并行程序設(shè)計(jì)平臺(tái)。現(xiàn)代NX一個(gè)重要概念便是進(jìn)程(prcess)。正是由于多個(gè)進(jìn)程之間的相互通信，進(jìn)任何進(jìn)程總和程序聯(lián)系在一起，程序一旦在具體操作系統(tǒng)環(huán)境中投入運(yùn)行，就變成了進(jìn)程。各個(gè)進(jìn)程擁有獨(dú)立的執(zhí)行環(huán)境，其中包括內(nèi)I/O進(jìn)程具有兩個(gè)明顯的特征：一個(gè)是資源特征，包括那些程序執(zhí)I/O設(shè)進(jìn)程執(zhí)行過(guò)程中動(dòng)態(tài)改變的特征，例如（即進(jìn)程執(zhí)行的指令序列、進(jìn)程的控制與執(zhí)行狀態(tài)等。進(jìn)程的資源特征反映了進(jìn)任何進(jìn)程，在執(zhí)行過(guò)程中，均涉及如下幾種狀態(tài)：非存在狀態(tài)就緒狀態(tài)：進(jìn)程由其父進(jìn)程（例如，操作系統(tǒng)的內(nèi)核進(jìn)程或進(jìn)程，或其他應(yīng)用程序進(jìn)程）調(diào)入并準(zhǔn)運(yùn)行狀態(tài)CPU和其他必需的計(jì)算資源，并執(zhí)行指掛起狀態(tài)CPU或其他必需的計(jì)算資源被其他進(jìn)程占有，退出狀態(tài)：進(jìn)程正常結(jié)束或因異常退出而被廢棄只對(duì)消息傳遞并行程序設(shè)計(jì)感的讀者，了解以上的進(jìn)程概進(jìn)程間通信無(wú)論位于同一臺(tái)處理機(jī)，還是位于不同處理機(jī)，進(jìn)程始終是操作系統(tǒng)資源調(diào)度的基本單位，且各個(gè)進(jìn)程不能直接其他進(jìn)程的于同一臺(tái)處理機(jī)或不同處理機(jī)的多個(gè)進(jìn)程之間相互交流信息，具體。個(gè)進(jìn)程之間傳遞的數(shù)據(jù)為..，稱這種操作為....。顯然，..：同步是使位于相同或不同處理機(jī)中的多個(gè)進(jìn)程之間相互態(tài)之后才進(jìn)行。其實(shí)，同步也是進(jìn)程之間相互通信的式。..(..)：將位于相同或不同處理機(jī)中的多個(gè)進(jìn)程的局部結(jié)果綜合起來(lái)，通過(guò)某種操作，例如求最大值、最小值、累同步和，統(tǒng)稱為.....，而操作的具體數(shù)據(jù)對(duì)象為..，具體操作為....。進(jìn)程間通信的具體實(shí)現(xiàn)大體可以分為兩類（在共享環(huán)中，通過(guò)讀/寫操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來(lái)實(shí)現(xiàn)（2在分布現(xiàn)的具體細(xì)節(jié)對(duì)并行編程的用戶都是的，用戶看到的均是統(tǒng)一的（PI。MPI線由于管理重量級(jí)進(jìn)程的高開(kāi)銷較大地影響了并行機(jī)性能的發(fā)揮，解兩個(gè)一部分由其資源特稱之為進(jìn)....... 所示，進(jìn)程的指令路徑可以分解為并行的互不相關(guān)的多條子路CPU，對(duì)不同的數(shù)據(jù)進(jìn)行處理，從而達(dá)到提高進(jìn)程執(zhí)行速度圖 開(kāi)銷也遠(yuǎn)遠(yuǎn)小于進(jìn)程間的切換開(kāi)銷。因此，線程的管理開(kāi)銷遠(yuǎn)遠(yuǎn)小于進(jìn)程的管理開(kāi)銷，比較適合細(xì)粒度的共享的并行程序設(shè)計(jì)。共享并行編程基于線程級(jí)細(xì)粒度并行，僅被SP和M支持?jǐn)?shù)據(jù)的共享，所以并行編程的難度較小，但一般情形展性。但是，消息傳遞并行編程只能支持進(jìn)程間的分布模式，內(nèi)存空間的只能通過(guò)消息傳遞來(lái)實(shí)現(xiàn)。因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享和數(shù)據(jù)并行兩種編程由于當(dāng)前流行的各類SMP、DSM、MPP和微機(jī)機(jī)群等并行機(jī)傳遞并行程序從而簡(jiǎn)化并行程序設(shè)增強(qiáng)程序的可移植性。1.1特消息傳典型代可移植并行粒異異數(shù)據(jù)模共共顯隱較容偏可擴(kuò)展好較一MPI表示每個(gè)進(jìn)程的局部?jī)?nèi)存空間，多個(gè)“P/M”1.14P/M模塊替換成處理器，且規(guī)定每個(gè)處并行機(jī)模型實(shí)際上屬于典型的分布式并行機(jī)，且每臺(tái)處理器只1.14這里，有必要說(shuō)明的是，消息傳遞分布式并行機(jī)模型和具體（SPDMclsercosaionPP，用戶面對(duì)的都是該模型隱含的進(jìn)程拓?fù)浣Y(jié)構(gòu)，只是各類具體并行機(jī)實(shí)現(xiàn)的消息傳遞函數(shù)庫(kù)的方式不同，但用戶無(wú)須知道這些細(xì)節(jié)。例如，在共享PDSM在PPPDM并行機(jī)內(nèi)部是通過(guò)共享數(shù)據(jù)緩存SPDM圖14所示的分布式并行機(jī)模型。標(biāo)準(zhǔn)消息傳遞界面1994年6月，全球工業(yè)、和科研應(yīng)用部門聯(lián)合推出消息傳遞并行編程環(huán)境的標(biāo)準(zhǔn)用戶界面（MPI），它將消息傳遞并行編程環(huán)境分解為兩個(gè)部分，第一是構(gòu)成該環(huán)境的所有消息傳遞函數(shù)的標(biāo)準(zhǔn)接口說(shuō)明，它們是根據(jù)并行應(yīng)用程序?qū)ο鬟f功能的不同要求而制定的，不考慮該函數(shù)能否具體實(shí)現(xiàn)；第二是各并行機(jī)廠商提供的對(duì)這PI庫(kù)函數(shù)的標(biāo)準(zhǔn)接口，PI并行程序，便可在支持PIPI系統(tǒng)就是指所有這些具有標(biāo)準(zhǔn)接口說(shuō)明的消息傳遞函數(shù)所構(gòu)成的函數(shù)庫(kù)。入實(shí)現(xiàn)進(jìn)程MPI消息傳遞庫(kù)函數(shù)，就構(gòu)成了MPI并行程序設(shè)計(jì)所依賴的并行編程環(huán)境。MPI吸收了眾多消息傳遞系統(tǒng)的優(yōu)點(diǎn)，例P4、PVM、Express、PARMACS等，是目前國(guó)內(nèi)外最流行象、石油、、空氣動(dòng)力學(xué)、核物理等）的科研與工程軟件已經(jīng)移植到MPI平臺(tái)。有精確的定義，從而為并行軟件的發(fā)展提供了必要的條件了如下的消息傳遞功能I/O：允許多個(gè)進(jìn)程同時(shí)讀/寫同（與penP的混合并行編程（動(dòng)態(tài)進(jìn)程管理：允許并行應(yīng)用程序在執(zhí)行過(guò)程中，動(dòng)態(tài)地增加和刪除進(jìn)程個(gè)數(shù)（4單邊通信：允許某個(gè)進(jìn)程對(duì)其他進(jìn)程的局部?jī)?nèi)存單元直接執(zhí)行讀/寫，而不要對(duì)方進(jìn)程的顯式干預(yù)（5并行應(yīng)用程序之間的動(dòng)態(tài)互操作：允許各個(gè)PI并行應(yīng)用程序之間動(dòng)態(tài)地建立和刪除消息傳遞通信通道。并行算法....是適合在并行機(jī)上實(shí)現(xiàn)的算法，一個(gè)好的并行算法應(yīng)計(jì)算方法數(shù)值離散后，剩下的問(wèn)題就是如何設(shè)計(jì)并行算法，編制并目前，并行算法根據(jù)運(yùn)算基本對(duì)象的不同可分為：數(shù)值并行算 主要為數(shù)值計(jì)算方法而設(shè)計(jì)的并行算法主要為符號(hào)運(yùn)算而設(shè)計(jì)的并行算法，如圖論算根據(jù)并行進(jìn)程間相互執(zhí)行順序關(guān)系的不同可分為：同步并行算法進(jìn)程間由于運(yùn)算執(zhí)行順序而必須相互等待的并行異步并行算法進(jìn)程間執(zhí)行相對(duì)獨(dú)立，不需要相互等待的一種算法，通常針對(duì)消息傳遞ID算的整個(gè)過(guò)程中均不需要等待，而是根據(jù)消息決定進(jìn)程的繼續(xù)或終止；獨(dú)立并行算法進(jìn)程間執(zhí)行是完全獨(dú)立的，計(jì)算的整個(gè)過(guò)程不需要根據(jù)各進(jìn)程承擔(dān)的計(jì)算任務(wù)粒度的不同，可分為：細(xì)粒度并行算 通常指基于向量和循環(huán)級(jí)并行的算法中粒度并行算法通常指基于子任務(wù)級(jí)并行的算法，例如通常的并行算法的幾個(gè)重要發(fā)展階段可分為基于向量運(yùn)算的并行算法該類算法是隨著向量機(jī)(如CRY–1YH–1等)的出現(xiàn)而出現(xiàn)0年代末和80名的成果為遞歸問(wèn)題的向量化。我國(guó)在這方面有很好的研究和[]?；诙嘞蛄刻幚頇C(jī)的并行算法設(shè)計(jì)階如CRYYPY的出現(xiàn)而出現(xiàn)的，其特點(diǎn)是既要考慮到多處理機(jī)間的任務(wù)級(jí)大粒度并行，又要考慮到單處理機(jī)上的向量級(jí)細(xì)粒度并行。該類算法在0年代初期和中期比較流行，目前一直持在這方面SIMDCM-2、Systolic陣列、Transputer等類并行機(jī)上的并行算法。該類并行算法研究在80年代中期比較熱門，但由于缺少一般性，過(guò)分MIMD該類并行機(jī)的顯著特點(diǎn)是處理器功能比較強(qiáng)大，能獨(dú)立處理各求解同一問(wèn)題。并且，處理器間單位數(shù)據(jù)的通信開(kāi)銷通常遠(yuǎn)遠(yuǎn)高于處理器的單位運(yùn)算開(kāi)銷。因此，該類并行機(jī)通常需要任務(wù)級(jí)并行機(jī)。興起于80現(xiàn)代并行算法設(shè)計(jì)展性和可移植性。但隨著微處理器和互聯(lián)網(wǎng)絡(luò)速度的發(fā)展，可擴(kuò)展高性能的獲取必須要求并行算法設(shè)計(jì)兼顧兩個(gè)發(fā)展方向：第一， 0，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，在最短的時(shí)間內(nèi)完成這N個(gè)數(shù)相加P2NM3個(gè)結(jié)點(diǎn)，請(qǐng)給出一維陣列（環(huán)、點(diǎn)個(gè)數(shù)為P）的結(jié)點(diǎn)度、點(diǎn)對(duì)點(diǎn)延遲（以的邊的條數(shù)為單假設(shè)8個(gè)結(jié)點(diǎn)，分別連接在1Gbps100Mbps24switch上，請(qǐng)問(wèn)任意兩個(gè)結(jié)點(diǎn)間的平均帶寬為多簡(jiǎn)單闡述當(dāng)前并行計(jì)算機(jī)的多級(jí)結(jié)構(gòu)，以及在程序設(shè)計(jì)中如何適應(yīng)這種結(jié)構(gòu)。闡述當(dāng)前流行的并行計(jì)算機(jī)的分類，以及各類并行機(jī)體系結(jié)構(gòu)的主要特征。2章LinuxLinux操作系統(tǒng)PCClusterLinux操作系統(tǒng)的一些基本知識(shí)有Linux的安裝和基本使用，以及在2.3節(jié)。如果對(duì)于該系統(tǒng)下的程序設(shè)計(jì)也已Linux操作系統(tǒng)進(jìn)行工作可以認(rèn)為，LinuxUNIX操Windows1操作系統(tǒng)完成日常工作，并且具有程本章將在此基礎(chǔ)上講述Linux操作系統(tǒng)的安裝、使用以及在LinuxLinuxLinuxLinux系統(tǒng)，需要進(jìn)行一些硬件以避免出現(xiàn)一些硬件支持方面的問(wèn)題。Linux系統(tǒng)對(duì)太過(guò)時(shí)的硬件1Windows 公司的商標(biāo)WindowsLinux操作系統(tǒng)時(shí)可以保留已有的操作系統(tǒng)，但必須在硬盤上留出安裝Linux所Windows中的某個(gè)非系統(tǒng)分區(qū)，或是借助一些工具，如PartitionMagic，調(diào)Windows分區(qū)的大小來(lái)達(dá)到這一目的。建議至少保留5GB的空間給Linux系統(tǒng)用，其中4.5GBLinux的文件系統(tǒng)，0.51GB另外一個(gè)備是一套ix系統(tǒng)的安裝光。光盤裝是目前最簡(jiǎn)單的裝方Lix系統(tǒng)可以通許多其式安裝軟U網(wǎng)卡至直接貝硬盤區(qū)或文系統(tǒng)可以等熟了Lix裝ix系統(tǒng)的安光盤可以過(guò)商網(wǎng)可己前上或上供的Lix有很版本們被稱不同的版(isii)，這樣局面出現(xiàn)是為ix是一個(gè)開(kāi)放碼的操系統(tǒng)，任人都以將Lx核些軟合起一。te它有都方如使計(jì)沒(méi)么別的硬件，該裝iws操作系沒(méi)有什顯差別，過(guò)非常單也好只跟裝的行就以鑒于本章后介紹主基由eat(紅帽)司支持的Fea，建最好安裝eaCe(htp/ /)，以本閱練。安裝時(shí)將第一張光盤放入光驅(qū)，接通計(jì)算機(jī)的電源，設(shè)置計(jì)算經(jīng)驗(yàn)的人或者在網(wǎng)絡(luò)上尋求幫助。另外，市場(chǎng)上大量關(guān)于Lx系統(tǒng)安裝的入門資料亦可參考。超級(jí)用戶，用戶名為root，它是計(jì)算機(jī)的管理員帳戶，在安裝過(guò)程中也要為超級(jí)用戶設(shè)置一個(gè)口令。一般來(lái)說(shuō)，在使用Linux系統(tǒng)工每個(gè)版都帶有豐富的軟件。如果為L(zhǎng)inux系統(tǒng)留出的硬盤Linux操作系統(tǒng)Linux的各種發(fā)LinuxLILOGrub。新引導(dǎo)程序允許用等。選擇啟動(dòng)Linux，便可以進(jìn)入到剛剛安裝的Linux系統(tǒng)中。Lix系統(tǒng)默的文件統(tǒng)格式是ex2，它的后繼ex3。其他操作系統(tǒng)一樣，Linux 的文件系統(tǒng)采用的也是樹(shù)形結(jié)構(gòu)樹(shù)的根就...(tiec)，用個(gè)正斜杠“”表，樹(shù)的子是文件，中間結(jié)點(diǎn)則是 。要注意的是，Liux的路徑名中用正斜杠“/”分隔 名，而Windows中用的則是反斜杠“\”。Linux系統(tǒng)的 /usr/home：普通用戶的家所在的位置，可以選擇將它放在一個(gè)不/procLinux內(nèi) /sbin/bin/boot/initrd：系統(tǒng)啟動(dòng)用的文件/lib：庫(kù)文 其他：/opt，/misc，/var：這些普通用戶基本上不用；需要的是系統(tǒng)日志文件在/var/log下面。/usr是所有中最復(fù)雜的一為除了最基本的系統(tǒng)軟件裝在/opt/usr/local下面)。其中包含的主要有：這個(gè)中；裝在/opt；等。XLinux/UNIX的圖形界面軟件，圖形用戶界面的軟件通常都在該中；share/man和share/doc家。通常，普通用戶的家/home下，名字和用戶名相同。普通用戶能夠修改的主要內(nèi)容局限在自己的家例如，作者的用戶名是rli，家的位置就是/home/rli。Linux系統(tǒng)后，首先看到的是一個(gè)登錄界面，通常是Linux系統(tǒng)時(shí)為自己創(chuàng)建的用戶名，緊接著根據(jù)提雖然Linux系統(tǒng)提供了與Windows操作系統(tǒng)類似的圖形界面，但對(duì)于編程者來(lái)說(shuō)，學(xué)會(huì)直接使用Linux令行操作依然十分重 錄的，則需要首先啟動(dòng)一個(gè)s..，例如點(diǎn)擊系統(tǒng)菜單中的“系統(tǒng)工具—終端”，然后才能在窗口中輸入命令。S字面上的令，并將命令執(zhí)行結(jié)果返回給用戶。S本身也是一個(gè)應(yīng)用程序，有很多不同類型的s可供選擇，比較常用的有Bournes、Cs、Korns、TCs和Zshs等。在Linux中，最常用的是Bash，其全稱是Bourne–AgainS，它是Bournes的一個(gè)擴(kuò)展版本。S窗口也叫....，其中運(yùn)行著一個(gè)交互式s[rli@arenatmp]$出一個(gè)提示符，等待用戶輸入命令。S提示符的形式是可以配置[rli@arenatmp]$命令名[可選項(xiàng)1可選項(xiàng)2...]參數(shù)1參數(shù)2$s提示符前輸入一條命令，命令名[可選項(xiàng)1可選項(xiàng)2...]參數(shù)1參數(shù)2[rli@arenatmp]$su-su轉(zhuǎn)換成為超級(jí)用戶，為此，只需在s提示符前輸入命令[rli@arenatmp]$su-[root@arena[root@arena系統(tǒng)會(huì)提示要求輸。輸入超級(jí)用戶的口令后，系統(tǒng)提示符會(huì)“$”“#”，su命令后面加“-”的主要作用是為了得到超級(jí)用戶的路徑，以便直接使用/sbin和/usr/sbin中令。帳號(hào)Linux系統(tǒng)最重要的配置文件之一是/etc/passwd，它記載著系統(tǒng)中所有用戶的信息。在傳統(tǒng)的UNIX系統(tǒng)中，該文件用戶的單獨(dú)在另外一個(gè)文件/etc/shadow中，所以/etc/passwd中實(shí)容在命令執(zhí)行前后的變化來(lái)了解命令的確切作用。Linux中添加新用戶令為useradd，它的簡(jiǎn)單語(yǔ)法為useradd[-d][-g組名][-s用戶由于后續(xù)介紹中將采用上面的格式來(lái)介紹許多Linux命令的語(yǔ)法，這里稍稍做些解釋。在上面的格式中命令名為useradd，寫在方括 (默認(rèn)值為/home/用戶名)，組名指定新用戶所屬的用戶組(稍后解釋)，s指定用戶的默認(rèn) ，即用戶登錄時(shí)自動(dòng)獲得的s(默認(rèn)值為/bin/bash)。例如， [root@arena[root@arenatmp]#useradd-gusers-s/bin/bash添加一個(gè)名為aaa的新用戶，該用戶屬于用戶組users，s/bin/bash。上述命令的執(zhí)行會(huì)使得/etc/passwd文件中增加下面文件/etc/passwd中每行定義一個(gè)用戶，由用冒號(hào)分割開(kāi)的幾是一個(gè)x，真實(shí)的口令在文件/etc/shadow中)、用戶號(hào)(uid)、 和s。刪除一個(gè)用戶令userdeluserdel[-r]用戶“-r”[root@arena[root@arenatmp]#passwd[用戶名[root@arenatmp]#[root@arenatmp]#usermod-s/bin/csh會(huì)將用戶aaa的默認(rèn)s改成Cs(/bin/csh)個(gè)用戶可以同時(shí)屬于多個(gè)用戶組，/etc/passwd中給出的用戶組是組的信息在文件/etc/group中。對(duì)于用戶組的管理也有相應(yīng)令，如groupadd、groupdel等。為了將一個(gè)用戶加入某個(gè)組或者從某個(gè)組去掉，可以使用命令gpasswd[root@arenatmp]#groupaddvisitor[root@arenatmp]#groupaddvisitor[root@arenatmp]#gpasswd-daaavisitor[root@arenatmp]#groupdelvisitor上述命令中，首先創(chuàng)建了一個(gè)叫做visitor的用戶組，然后將用戶aaa加入到該組。這樣，用戶aaausersvisitorvisitor/etc/group(gname)(grouppassword)，組號(hào)(gid)，最后是屬于該用戶組的用戶名列表。Linux