#第2章并行計算機體系結構內容提要：2.1并行機網絡互聯拓撲結構2.2并行機訪存模型與多級存儲結構2.3并行機分類2.4并行機舉例2.5并行計算機的發展史2.1并行機網絡互聯拓撲結構參考資料：文獻1：第1.2節；文獻2：詳細闡述；當代并行機拓撲結構：?并行機體系結構的幾個要素：結點：包含一個或多個CPU，這些CPU通過HUB或全互聯交叉開關相互聯接，并共享內存，也可以直接與外部進行I/O操作；路由器：聯接計算結點與互聯網絡，負責數據在結點間的路由尋址；互聯網絡：將所有路由器以某種拓撲結構相互聯接，保證它們之間可以自由地通信。?互聯網絡：拓撲結構：將并行機各結點之間物理上相互聯接的關系用圖來表示，其中圖中結點代表并行機的結點，圖中連線代表它所聯接的兩個結點的路由器之間存在物理上的直接聯接關系，我們稱該圖為并行機互聯網絡拓撲結構；拓撲結構的幾個重要定義：并行機規模：并行機包含的結點總數，或者包含的CPU總數；結點度：互聯網絡拓撲結構中聯入或聯出的一個結點的邊的條數，稱為該結點的度；結點距離：兩個結點之間跨越的圖的邊的條數；網絡直徑：網絡中任意兩個結點之間的最長距離；點對點帶寬：圖中邊對應的物理聯接的物理帶寬；點對點延遲：圖中任意兩個結點之間的一次零長度消息傳遞必須花費的時間。延遲與結點間距離相關，其中所有結點之間的最小延遲稱為網絡的最小延遲，所有結點之間的最大延遲稱為網絡的最大延遲；折半寬度：對分網絡成兩個部分（它們的結點個數至多相差1）所必須去掉的邊的網絡帶寬的總和；總通信帶寬：所有邊的帶寬之和；互聯網絡評價：大：結點度、點對點帶寬、折半寬度、總通信帶寬；小:網絡直徑、點對點延遲；互聯網絡的分類：靜態拓撲結構、動態拓撲結構、寬帶互聯網絡；靜態拓撲結構：結點之間存在固定的物理聯接方式，程序執行過程中，結點間的點對點聯接關系不變，例如：［文獻1：P10-P11，給出各類定義的具體值，文獻2詳細討論］；一維陣列（Array）、環（Ring）；多維網格（Mesh）、多維環（Torus）；樹（Tree）：二叉樹、X-樹、星樹、胖樹；超立方體（Hypercube）;動態拓撲結構：結點之間無固定的物理聯接關系，而是在聯接路徑的交叉點處用電子開關、路由器或仲裁器等提供動態聯接的特性，主要包含單一總線、多層總線、交叉開關、多級互聯網絡：A單一總線：聯接處理器、存儲模塊和I/O設備等的一組導線和插座，在主設備（處理器）和從設備（存儲器）之間傳遞數據，特征有：公用總線以分時工作為基礎，各處理器模塊分時共享總線帶寬，即在同一個時種周期，至多只有一個設備能占有總線；總線帶寬=總線主頻X總線寬度，例如ASUS主板的總線頻率=150MHz,總線寬度為64位，則該總線的帶寬=1.2GB/s；監聽協議與仲裁算法：選擇哪個設備占有總線；例如：微機主板外部數據總線、PCI總線、ASCIWhite每個結點包含16個CPU，CPU之間通過總線共享局部存儲器；多層總線：各設備內部存在本地總線（結點、存儲器、I/O設備），本地總線之間以系統總線相互聯接，系統總線一般在通信主板中實現，例如文獻1P14圖1.9。交叉開關（CrossbarSwitcher）：所有結點通過交叉開關陣列相互連接，每個交叉開關均為其中兩個結點之間提供一條專用聯接通路，同時，任意兩個結點之間也能找到一個交叉開關，在它們之間建立專用聯接通路。交叉開關的狀態可根據程序的要求動態地設置為“開”和“關”。例如4X4交叉開關聯接8個結點（黑板上畫圖說明）。交叉開關特征：結點之間聯接：交叉開關一般構成NxN陣列，但在每一行和每一列同時只能有一個交叉點開關處于“開”狀態，從而它同時只能接通N對結點；結點與存儲器之間的聯接：每個存儲器模塊同時只允許一個結點訪問，故每一列只能接通一個交叉點開關，但是為了支持并行存儲訪問，每一行同時可以接通多個交叉點開關。交叉開關的成本為N2,N為端口數，限制了它在大規模并行機中的應用，一般適合8-16個處理器的情形.多級互聯網絡（MIN：MultistageInterconnectionNetwork）：由多個單級交叉開關級聯接起來形成大型交叉開關網絡，相鄰交叉開關級之間存在固定的物理聯接拓撲。為了在輸入與輸出之間建立聯接，可以動態地設置開關狀態。例如：一般聯接圖：文獻1圖1.11，其中ISC為該級互聯網絡，主要有混洗、蝶網、縱橫交叉等；（詳細參考文獻2）蝶網、CCC網、Benes網：均為超立方體網絡的推廣，參考文獻2的P215-P225。0網：等價于蝶網，參考文獻1的P16圖1.12。寬帶互聯網絡：快速以太網（10Mbps（82年）、100Mbps（94年）、1Gbps（97年））：IEEE802.3國際標準，三代網絡性能比較參考文獻1的P18表1.6,特征類似于單一總線：分時共享、競爭仲裁：帶寬100Mbps，8臺處理機共享，每臺處理機的平均帶寬為12.5Mbps。FDDI:光纖分布式數據接口（FiberDistributedDataInterface）采用雙向光纖令牌環，所有結點聯接在該環中，提供100-200Mbps數據傳輸速度，雙向環提供冗余通路以提供可靠性，距離可達100米、2公里、60公里等，比快速以太網具有更好的可靠性、適應性；Switcher:交叉開關，可同時為N/2對端口提供100Mbps的直接聯接通路，其中N為端口總數。多個Switcher堆疊（不多于7個）可形成多級Switcher0Beowulf微機機群采用這種結構互聯所有結點。（參考張林波講義之圖）。ATM：異步傳輸模式（ATM：AsynchronousTransferMode）是在光纖通信基礎上建立起來的一種新的寬帶綜合業務數字網的交換技術。介質無關的信息傳輸協議，采用53字節的定長短數據單元（cell）進行傳輸。大的數據包進入ATM網絡時，分解成多個定長的單元，各個單元獨立傳輸，到達目的地址后,這些單元匯集成原來的數據包。ATM網絡適合高速度傳輸聲音、圖像、視頻和數據等的所有形式的媒體。Myrinet：專用機群互聯網絡，帶寬可達200MB/秒，延遲小于10us。Infiniband：專用機群互聯網絡，帶寬可達1.25GB/秒，延遲小于6us。Qudrics:專用機群互聯網絡，帶寬可達400MB/秒，延遲小于6us。HiPPI:高性能并行接口（HighPerformanceParallelInterface），1993年標準（ANSIX3T9.3）形成。單工點對點的數據傳輸界面，帶寬可達800Mb/s-1.6Gb/s。互聯網絡的路由選擇算法：定義：數據包（Packet:結點間數據在網絡中傳輸的最小單位，一般為幾十個、或者幾百個字節。路由選擇算法：網絡中數據包傳輸的路徑選擇。申請隊列長度：在某條邊上等待傳輸的數據包的個數。常用路由選擇算法：貪心法：每個數據包沿最短路徑傳輸（二維陣列舉例），該方法容易在某一條邊上形成通信阻塞。動態路由選擇算法:數據包根據當前邊的申請隊列長度，動態地改變傳輸路徑。蟲孔算法（Wormhole:數據包分解為長度更小的字節流，所有字節流在網絡中按動態路由選擇算法在網絡中傳輸，最后在目的地址合并還原成數據包。作業：作業2.1：假設網絡包含P=2n=M3個結點，請給出一維陣列（環）、二維網格（Torus）、三維網格（Torus）、超立方體、二叉樹（葉結點個數為P）、蝶網、Benes網的結點度、點對點延遲（以跨越的邊的條數為單位）、折半寬度（以邊的條數為單位）、網絡直徑。作業2.2：假設存在8個結點，分別聯接在1Gbps的快速以太網和100Mbps的24端口的Switcher上，請問任意兩個結點間的平均帶寬為多少，如果結點數增加一倍，則平均帶寬又為多少。2.2并行機存儲結構參考資料：文獻1：第1.3節;文獻8、文獻10；并行機存儲模塊■內存模塊與結點分離結點0結點P圖2.2.1■內存模塊局部于結點內部結點0結點P圖2.2.2并行機訪存模型均勻訪存模型（UMA：UniformMemoryAccess:內存模塊與結點分離，分別位于互聯網絡的兩側（圖2.2.1），互聯網絡一般采用系統總線、交叉開關和多級網絡，稱之為緊耦合系統（TightlyCoupledSystem）。具有如下特征：?物理存儲器被所有結點均勻共享；所有結點訪問任意存儲單元的時間相同；訪存競爭時，仲裁策略對每個結點均是機會等價的；各結點的CPU可帶有局部私有高速緩存（Cache）；外圍I/O設備也可以共享，且對各結點等價。非均勻訪存模型（NUMA：NonuniformMemoryAccess:內存模塊局部在各個結點內部（圖2.2.2），所有局部內存模塊構成并行機的全局內存模塊。具有如下特征：任意結點可以直接訪問任意內存模塊；結點訪問內存模塊的時間不一致：訪問本地存儲模塊的速度一般是訪問其他結點內存模塊的3倍以上；訪存競爭時，仲裁策略對結點可能是不等價的；各結點的CPU可帶有局部私有高速緩存（Cache）；外圍I/O設備也可以共享。Cache一致性非均勻訪存模型（CC-NUMA：Coherent-CacheNonuniformMemoryAccess：存在專用硬件設備保證在任意時刻，各結點Cache中數據與全局內存數據的一致性，具有特征：各CPU的局部Cache數據來源于全局內存，并保證所有結點中數據的一致性（畫圖簡單說明）；?大多數訪存可以局部在本地高速Cache；基于目錄的Cache一致性協議（Cache原理參考下章）。分布式訪存模型（DMA：DistributedMemoryAccess:各個結點的存儲模塊只能被局部CPU訪問，其他結點無法直接訪問局部存儲模塊，稱之為分布式存儲（圖2.2.2），具有特征：內存模塊分布局部于各個結點，每個結點只能直接訪問其局部存儲模塊，對其他結點的內存訪問只能通過消息傳遞程序設計來實現；每個結點均是一臺由處理器、存儲器、I/O設備組成的自洽計算機。?多級存儲結構:CPUchip；寄存器二級Cache一級Cache本地局部內存冠程內存(MPI消息傳遞500MHzPentium-IIIClusterCPUchip；寄存器二級Cache一級Cache本地局部內存冠程內存(MPI消息傳遞500MHzPentium-IIICluster容量(B)帶寬(MB/s)延遲(ns)2566000232K40006512K200080500M1200320海量100100,000處理機每位成本增加訪存延遲比例：微機機群1:3:40:160:50,000Origin20001:3:30:50:500一次消息傳遞延遲相當于峰值浮點運算的次數>微機機群：50,000次Origin2000:1000次通信與CPU計算速度不匹配：2.3并行機分類參考資料：文獻1：P21-P25；文獻6：第1章；文獻8、10、11；指令與數據流分類：■單指令多數據流(SIMD)：按同一條指令，并行機的各個不同的功能部件同時對不同的數據進行不同的處理，例如：傳統的向量機、80年代初期的陣列機CM-2,目前已經退出歷史舞臺；多指令多數據流(MIMD)：不同的處理器可同時對不同的數據執行不同的指令，目前所有并行機均屬于這一類；多指令單數據流(MISD)：至今沒出現當前流行的高性能并行機體系結構分類：(五類)對稱多處理共享存儲并行機(SMP：SymmetricMultiProcessing)；分布共享存儲并行機(DSM：DistributedSharedMemory)；大規模并行機(MPP：MassivelyParallelProcessors)；工作站(微機)機群(COW：ClusterOfWorkstation、BeowulfPC-Cluster)■并行向量多處理機(PVP：ParallelVectorProcessors)對稱多處理共享存儲并行機(SMP)：圖2.3.1SMP體系結構示意圖SMP具有如下特征：?對稱共享存儲:系統中任何處理器均可直接訪問任何存儲模塊中的存儲單元和I/O模塊聯接的I/O設備，且訪問的延遲、帶寬和訪問成功的概率是一致的。

所有內存地址單元統一編址。各個處理器之間的地位等價，不存在任何特權處理器。操作系統可在任意處理器上運行。?單一的操作系統映像：全系統只有一個操作系統駐留在共享存儲器中，它根據各個處理器的負載情況，動態地分配各個進程到各個處理器，并保持各處理器間的負載平衡。局部高速緩存Cache及其數據一致性：每個處理器均配備局部Cache，它們可以擁有獨立的局部數據，但是這些數據必須保持與存儲器中數據是一致的。低通信延遲：各個進程通過讀/寫操作系統提供的共享數據緩存區來完成處理器間的通信，其延遲通常小于網絡通信的延遲。共享總線帶寬：所有處理器共享總線的帶寬，完成對內存模塊和I/O模塊的訪問。支持消息傳遞、共享存儲并行程序設計。SMP具有如下缺點：欠可靠：總線、存儲器或操作系統失效可導致系統崩潰。可擴展性（scalability）較差：由于所有處理器共享總線帶寬，而總線帶寬每3年才增加2倍，跟不上處理器速度和內存容量的增加步伐，因此，SMP并行機的處理器個數一般少于32個，且只能提供每秒數百億次的浮點運算性能。SMP典型代表：SGIPOWERChallengeXL系列并行機（36個MIPSR1000微處理器）；COMPAQAlphaserver84005/440（12個Alpha21264個微處理器）；HP9000/T600（12個HPPA9000微處理器）；IBMRS6000/R40（8個RS6000微處理器）。分布共享存儲并行機（DSM）：結點PCPU0CPU111irCacheCache結點0二結點PCPU0CPU111irCacheCache結點0二M0OOOOOOOOOOCPU0CPU1ir11CacheCacher-SHUBRouterMP互聯網絡圖2.3.2DSM體系結構示意圖DSM較好地改善了SMP并行機的可擴展能力，具有如下特征：并行機以結點為單位，每個結點包含一個或多個CPU,每個CPU擁有自己的局部Cache，并共享局部存儲器和I/O設備，所有結點通過高性能互聯網絡相互聯接；物理上分布存儲：內存模塊局部在各結點中，并通過高性能互聯網絡相互聯接避免了SMP訪存總線的帶寬瓶頸，增強了并行機的可擴展能力。單一的內存地址空間：盡管內存模塊分布在各個結點，但是，所有這些內存模塊都由硬件進行了統一的編址，并通過互聯網絡聯接形成了并行機的共享存儲器。各個結點即可以直接訪問局部內存單元，又可以直接訪問其他結點的局部內存單元。非一致內存訪問（NUMA）模式：由于遠端訪問必須通過高性能互聯網絡，而本地訪問只需直接訪問局部內存模塊，因此，遠端訪問的延遲一般是本地訪問延遲的3倍以上。單一的操作系統映像：類似于SMP，在DSM并行機中，用戶只看到一個操作系統，它可以根據各結點的負載情況，動態地分配進程。基于Cache的數據一致性：通常采用基于目錄的Cache一致性協議來保證各結點的局部Cache數據與存儲器中數據的一致性。同時，我們也稱這種DSM并行機結構為CC-NUMA結構。低通信延遲與高通信帶寬：專用的高性能互聯網絡使得結點間的延遲很小，通信帶寬可以擴展。例如，目前最先進的DSM并行機SGIOrigin3000的雙向點對點通信帶寬可達3.2GB/秒，而延遲小于1個微秒。DSM并行機可擴展到上百個結點，能提供每秒數千億次的浮點運算性能。例如，SGIOrigin2000可以擴展到64個結點（128個CPU），而SGIOrigin3000可以擴展到256個結點（512個CPU）。但是，由于受Cache一致性要求和互聯網絡性能的限制，當結點數目進一步增加時，DSM并行機的性能也將大幅下降。支持消息傳遞、共享存儲并行程序設計。DSM典型代表：SGIOrigin2000；SGIOrigin3800。大規模并行機（MPP）：數百個乃至數千個處理器組成的大規模并行機。■典型代表：當前位于TOP500前列（參考第7章并行機性能測試）的并行機均屬于這一類，其中包括IBMASCIWhite（8192個處理器）、IntelASCIRed（9632個處理器）、IBMASCIBluePacific（5808個處理器）、SGIASCIBlueMountain（6144個處理器）、IBMSPPOWER3（1336個處理器）、CRAYT3E1200（1084個處理器）等。■典型體系結構:圖2.3.3MPP體系結構示意圖■MPP特征:由數百個乃至數千個計算結點和I/O結點組成，這些結點由局部網卡（NIC）通過高性能互聯網絡相互聯接。?每個結點相對獨立，并擁有一個或多個微處理器（P/C）。這些微處理器均配備有局部Cache，并通過局部總線或互聯網絡與局部內存模塊和I/O設備相聯接。MPP的各個結點均擁有不同的操作系統映像。一般情況下，用戶可以將作業提交給作業管理系統，由它負責調度當前最空閑、最有效的計算結點來執行該作業。但是，MPP也允許用戶登錄到某個特定的結點，或在某些特定的結點上運行作業。各個結點間的內存模塊相互獨立，且不存在全局內存單元的統一硬件編址。一般情形下，各個結點只能直接訪問自身的局部內存模塊，如果要求直接訪問其他結點的局部內存模塊，則必須有操作系統的特殊軟件支持。■按存儲結構的不同，MPP又可以分為兩類：分布式存儲大規模并行機（DM-MPP）、多臺SMP或DSM并行機通過高性能互聯網絡相互聯接的大規模機群（SMP-MPP或DSM-MPP）：DM-MPP:每個結點僅包含一個微處理器，早期的MPP均屬于這一類。例如CRAYT3D、CRAYT3E、IntelParagon、IBMSP-2、YH-3等。SMP-MPP:每個結點是一臺SMP并行機，例如當前位于Top500排名前列的多臺MPP并行機均屬于這一類，其中包括IBMASCIWhite、IntelASCIRed、IBMBluePacific等；DSM-MPP:每個結點是一臺DSM并行機，其典型代表為包含6144臺處理器的ASCIBlueMountainMPP并行機，它由48臺Origin2000構成，其中每臺含128個微處理器。

?微機機群(BeowulfPC-Cluster)：隨著商用微處理器性能的飛速發展，低延遲、高帶寬商用網絡父換機的出現，和LINUX操作系統等自由軟件的成熟，并行計算機不再是一個只有大型科研單位才能擁有的設備。例如，將128臺當前市場上最高性能的IntelPentium-III/800MHz的微機通過6個24端口的100Mbps的網絡交換機相互聯接，即可構成浮點峰值性能在1000億次左右的并行機，而其成本不超過200萬元人民幣，性能價格比遠遠高于以上提到的各類并行機(30倍以上)，國際上稱該類自行研制的并行機為Beowulf機群。盡管微機機群在通信性能、穩定性和使用方便等方面有待大幅度提高，但是，它們以其他并行機無法比擬的性能價格比，近年來已經成為了高性能并行計算中的一支不可忽視的重要力量。目前，在我國的各個大學和科研機構，例如中科院、北京大學、清華大學等，微機機群也得到了快速發展和推廣應用。特別地，在2000年底的Top500排名中，美國Sandi國家重點實驗室自行研制的機群Cplant排名第84位。圖2.3.4Beowulf微機機群示意圖(參考張林波講義之圖)Beowulf微機機群的體系結構如圖2.3.4所示，多臺高性能微機通過商用網絡交換機相互聯接，并擁有各自獨立的操作系統、主板、內存、硬盤和其他I/O設備，構成機群的計算結點。配置一臺或多臺文件服務器，一方面管理機群計算結點共享的所有軟件和用戶計算資源，另一方面充當機群與外部網絡的聯接橋梁，外部科研網的用戶只有通過文件服務器才能使用機群的計算資源。由于受商用交換機網絡性能和操作系統功能的影響，Beowulf微機機群的處理機規模一般限制在100臺左右。但是，如果將交換機替換成專用機群網絡，例如GigaNet、Myrinet等，則它們的規模可以進一步擴大。因此，在當前技術條件下，微機機群一般可提供千億次左右的浮點峰值性能。?并行向量多處理并行機(PVP)：體系結構類似于DM-MPP，但是每個CPU為向量多處理機。僅日本研制，應用不廣。2.4并行機舉例SMP并行機：SGIPowerChallengeXLR10000：多個（＜18）個SGIR10000微處理器、共享存儲模塊、I/O設備通過系統總線相互聯接。總線帶寬：2.4GB/秒。單一操作系統影像。DSM并行機：SGIOrigin2000、SGIOrigin3800：單一影像操作系統。Origin2000可擴展到8個機柜，每個機柜含8個結點，結點是構成Origin2000的基本單位，它包含：1-2個主頻為195MHz或250MHz的MIPSR10000CPU,每個CPU含4MB的二級Cache；內存512MB-4GB，分主存和目錄內存兩類，后者主要用于保持結點間的Cache數據一致性；集線器（HUB）含4個端口：CPU端口、內存端口、XIO端口和CrayLink互聯網絡端口，采用交叉開關實現兩個CPU、內存、輸入輸出和互聯網絡路由器（router）之間的全互聯，分別提供780MB/Sec、780MB/Sec、1.5GB/Sec、1.5GB/Sec的傳送速度。Origin2000的所有結點通過CrayLink高性能互聯網絡相互聯接,路由器是構成CrayLink的基本單位，它包含6個端口，內部采用交叉開關實現端口間的全互聯，具有9.3GB/Sec的峰值帶寬。每個路由器的兩個端口用于聯接結點，其余4個端口實現路由器間的互聯，形成互聯網絡拓撲結構。該CrayLink的半分帶寬與結點個數成線性遞增關系，對任意兩個結點,至少能提供兩條路徑，保證了結點間的高帶寬、低延遲聯接和互聯網絡的穩定性和容錯能力。圖3.2.5SGIOrigin2000并行機體系結構示意圖?SMP-MPP：ASCIWhite：512臺IBMSMPNH-2結點通過SP交換機相互聯接；每個結點為SMP并行機，含16個IBMPowerP3/375MHz微處理器，共享16GB內存；總計計算處理器8192個，內存4-6TB,峰值性能12.3TFLOPS，磁盤總容量150TB（可擴展到160TB）；總投資1.1億美元，美國能源部向IBM租借，年租金為8500萬美元；重106噸，兩個籃球場大；結點間支持消息傳遞并行程序設計，結點內部支持共享存儲、消息傳遞兩種并行編程模式，也支持消息傳遞和共享存儲混合編程模式。■微機機群：聯想深騰