第 7 章 并行處理技術

第7章并行處理技術2/2/20231本章學習內容并行處理技術的基本概念SIMD并行計算機基礎知識計算機互連網絡及互連算法多處理機2/2/202327.1并行處理技術的基本概念(簡述)并行性在同一時刻或是同一時間間隔內完成兩種或兩種以上性質相同或不相同的工作。并行性包括并發(fā)性和同時性。并行性的粒度Tw：所有處理器的計算時間的總和。Tc：所有處理器的通信時間的總和2/2/20233并行性的等級2/2/20234（1）指令級：并行性發(fā)生在指令內部微操作之間或指令之間。取決于程序的具體情況。可借助于優(yōu)化編譯器開發(fā)細粒度并行性，它能自動檢測并行性并將源代碼換成運行時系統(tǒng)能識別的并行形式。（2）循環(huán)級：相當于迭代循環(huán)操作，典型循環(huán)包含的指令大約幾百條，循環(huán)級并行性是并行機或向量計算機上運行的最優(yōu)程序結構，并行處理主要由編譯器在循環(huán)級中進行開發(fā)。2/2/20235（3）子任務級：屬于中粒度。子程序是在單處理機或多處理機的多道程序設計這一級進行的。這一級并行性由算法設計者或程序員開發(fā)而非用編譯器開發(fā)。（4）任務級：這是與任務、過程、程序段、協(xié)同程序級相對應的中粒度或粗粒度規(guī)模。典型粒度包含的指令幾千條，檢測本級的并行性比細粒度級困難得多，需要更多地涉及過程間的相關性分析。需編譯器支持。（5）作業(yè)（程序）級：對于少量幾臺高性能處理機構成的超級計算機開發(fā)這種粗粒度并行性切實可行。2/2/20236并行性的開發(fā)策略時間重疊資源重復資源共享并行性的開發(fā)方式粗粒度開發(fā)方式：主要采用軟件手段開發(fā)并行性。細粒度開發(fā)方式：主要采用硬件手段開發(fā)并行性。粒度與Flynn的關系粗粒度-MIMD方式（G↗）細粒度-SIMD方式（G↘）2/2/202377.2陣列處理機（SIMD并行計算機）并行計算機的定義并行計算機就是由多個處理單元PE(以下也稱為處理器，或簡稱為CPU)組成的計算機系統(tǒng)，這些處理單元相互通信和協(xié)作能快速、高效的求解大型復雜問題。

下圖給出了從標量到向量和并行計算機的演變。2/2/202382/2/20239陣列機以SIMD方式工作、采用資源重復技術實現數據處理時的高度并行的陣列處理機。陣列機主要用于處理向量和陣列型數據。它在同一個控制部件管理下，有多個處理單元。所有處理單元均收到從控制部件廣播來的同一條指令，但操作對象是不同的數據。H.J.Siegel提出了SIMD計算機的操作模型。2/2/2023107.2.1陣列機的基本結構1.陣列機的結構陣列機通常由一個控制器（CU）、N個處理器單元（PE）、M個存儲器模塊（M）以及一個互連網絡部件（IN）所組成?；ミB網絡（IN）有時也稱為對準網絡或排列網絡。2/2/202311H.J.Siegel提出的并行處理機模型

2/2/2023122.陣列機的工作方式陣列機工作時，由控制器CU控制將指令廣播給系統(tǒng)中的各個PE，所有活躍的PE將以同步方式執(zhí)行相同的指令（單指令流）。PE從相應的存儲模塊中取得自己所需的數據對象（多數據流）進行處理?；ミB網絡IN用來使各個PE之間或是PE和M之間實現方便的通信連接。2/2/2023133.陣列機的兩種基本結構⑴分布式存儲器陣列機2/2/202314①N個相同的處理單元PE由處理器Pi和局部存儲器Mi組成。各個Pi主要將從自己的局部存儲器Mi中獲取數據進行操作。各個PE通過IN實現相互間必要的數據交換，因此IN是單向的。②CU具有自己的存儲器，用于存放系統(tǒng)程序、用戶程序以及各個PE所需的共享數據。CU的主要功能是對指令譯碼和判別指令應在何處執(zhí)行。對于標量或控制類指令，CU利用本身的運算部件直接執(zhí)行；若是向量指令，它就將指令廣播到各個PE去執(zhí)行。分布式存儲器陣列機的特點2/2/202315③各個PE同步執(zhí)行來自CU的操作命令。但是并不一定每個操作非得所有PE都參加，CU將對PE實行屏蔽控制，只有那些未被屏蔽的活躍PE才可參加操作。CU控制互連網絡IN，使各個PE之間通過IN實現相互之間必要的數據交換。當相互需要交換數據的兩個PE不直接相連時，就需要經過它們之間的中間PE來完成連接。2/2/202316⑵共享存儲器的陣列機2/2/202317①每個PE沒有自己的局部存儲器。存儲器模塊以集中形式為所有PE（通過IN）共享。②互連網絡受CU控制，用來構成PE和M之間的數據交換通路。要求互連網絡具有同時連接PE到M和M到PE的雙向性。③系統(tǒng)中的一個PE可以與任何另一個PE實現數據交換（只要有任何一個存儲模塊同時與這兩個PE相連接）。當兩個需交換數據的PE之間沒有共享的存儲模塊時，可能需要經過多次的傳送之后，方可實現交換。④互連網絡比較復雜。共享存儲器陣列機的特點2/2/202318SIMD計算機的操作模型可用五元組表示：C＝<N，C，I，M，R>式中：

(1)N為機器的處理單元(PE)數。

例如，IlliacIV有64個PE。而連接機(ConnectionMachine)CM-2采用65536個PE。

(2)C為由控制部件(CU)直接執(zhí)行的指令集，包括標量和程序流控制指令。

陣列機特征的形式化表示2/2/202319(3)I為由CU廣播至所有PE進行并行執(zhí)行的指令集，它包括算術運算、邏輯運算、數據尋徑、屏蔽以及其它由每個活動的PE對它的數據所執(zhí)行的局部操作。(4)M為屏蔽方案集，其中每種屏蔽將PE集劃分為允許操作和禁止操作兩種子集。

(5)R是數據尋徑功能集，說明互連網絡中PE間通信所需要的各種設置模式。

F=(C,R)描述了互連網絡及參數這種描述模型為評價不同的陣列機結構提供了比較基礎。2/2/202320計算機的操作特性描述如MasParMP-1計算機：(1)PE數N＝1024至16384。PE數目與機器配置有關。

(2)CU執(zhí)行標量指令，將譯碼后的向量指令廣播到PE陣列，并控制PE間的通信。

(3)每個PE都是基于寄存器的加載/存儲RISC處理機，能執(zhí)行不同數據量的整數運算和標準浮點運算。PE從CU接受指令。

(4)屏蔽方案設在每個PE中，并由CU連續(xù)監(jiān)控，它能在運行時動態(tài)地使每個PE處于置位或復位狀態(tài)。

(5)MP-1有一個X-Net網格網絡和一個全局多級交叉開關尋徑器，以實現CU-PE之間、X-Net的8個近鄰之間和全局尋徑器的通信。2/2/2023212/2/2023227.2.2陣列機的主要特點(1)陣列機采用資源重復的策略，利用并行性中的同時性提高處理速度。(2)陣列機中通常都采用簡單、規(guī)整的互連網絡實現處理單元PE間的連接操作。(3)陣列機的研究必須與并行算法研究密切結合。(4)增加PE可提高陣列機的性能，因此陣列機具有較好的可擴展性。(5)由于處理單元PE都是相同的，因此可將陣列機看成是一個同構型并行機。但實際的陣列機系統(tǒng)是由控制器、PE、前端機三部分構成的一個異構型多處理機系統(tǒng)。2/2/2023237.2.3陣列機的并行算法以矩陣加為例

在陣列處理機上解決矩陣加法問題是最簡單的一維情形。假定兩個8×8的矩陣A和B相加，則只需把A和B居于相似位置的一對分量存放在同一PEM內，且令A的分量在全部64個PEM中存放的單元地址均為a,B的分量單元地址碼均為a+1，而C＝A＋B的結果分量均放在地址碼為a+2的單元內，如圖所示。于是，只需用下列3條IlliacIV的匯編指令就可一次實現矩陣相加。

2/2/2023242/2/202325LDAALPHA

；全部(a)由PEM送PE的累加器RGA

ADRN

ALPHA＋1；全部(a+1)與(RGA)進行浮點規(guī)舍加，結果送PGA

STAALPHA＋2；全部(RGA)由PE送PEM的a+2單元。

由于全部64個處理單元并行操作，故速度可提高為順序處理的64倍。2/2/2023267.2.4典型SIMD計算機舉例一、Illiac-IVSIMD陣列機

它是由Burroughs公司和Illinois大學1965年開始制、并于1972年完成的。Illiac-IV是SIMD陣列處理機的典型代表,其結構框圖如下圖所示，共有64個PE，統(tǒng)一由CU控制。B6500作為前端機進行系統(tǒng)管理。每個PE有自己的局存PEM，容量為2K字，字長64位，同時每個PE擁有4個64位的寄存器，分別用作累加器、操作數寄存器、數據路由寄存器和通用寄存器。此外，尚有1個16位變址器和1個8位的方式寄存器，用于存放PE的屏蔽信息。

2/2/2023272/2/202328下圖示出了Illiac-IV帶環(huán)繞的2維網孔互連網絡，這是一種4近鄰的互連網絡，從一個PE發(fā)送數據到另一個PE，在最壞情況下，須要經過步（n為PE數）。這種互連拓樸形式很適合于求解偏微分方程和矩陣運算之類的問題。當64個PE并行工作時，系統(tǒng)峰值速度可達每秒2億次運算，它主要應用于氣象預報和核工程研究等領域。2/2/202329IlliacIV處理陣列的連接由８８＝64個PU組成。每個PU由處理部件PE和它的局部存儲器PEM組成。每一個PUi只和它的東、西、南、北四個近鄰： PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64直接連接。南北方向同一列PU連成一個環(huán)， 東西方向構成一個閉合螺線。閉合螺線網絡直徑為7步， 環(huán)形網格的直徑為8步。2/2/2023302/2/202331陣列控制器CU陣列控制器CU實際上是一臺小型計算機。

對陣列處理單元實行控制和完成標量操作。 標量操作與各PE的數組操作可以重疊執(zhí)行?？刂破鞯墓δ苡幸韵挛鍌€方面： (1)對指令進行譯碼，并執(zhí)行標量指令； (2)向各PE發(fā)出執(zhí)行數組操作指令的控制信號； (3)產生并向所有處理單元廣播公共的地址； (4)產生并向所有處理單元廣播公共的數據； (5)接收和處理PE、I/O操作以及B6700產生的陷阱中斷信號。2/2/202332二、國產曙光系列并行機系統(tǒng)介紹我國的高性能計算機的發(fā)展起步并不晚：早在20世紀60年代后期到70年代，我國就自行研制了大型計算機（MainframeComputer），其典型代表機器有150、905、718和DJS260等，它們采用單/雙CPU，其峰值速度約為1MOPS（MillionOperationsPerSecond），即俗稱的百萬次機器；20世紀70年代后期到80年代，我國研制了向量機和多處理機，其典型代表機器有757、銀河1號和2號等，它們采用1~4個CPU，其峰值速度達10~100MOPS，即俗稱的億次機器。2/2/20233320世紀80年代后期到現在，我國研制了對稱多處理機（SMP）、大規(guī)模并行機（MPP）和工作站群（COW），其典型代表機器有曙光1號、曙光-1000/1000A、YH-3和曙光-2000等，它們采用4~128個CPU，其峰值速度達1Gflops~幾十Gflops，即俗稱百億次機器，我國1999年正式推出了千億次高性能計算機。

以下簡介我國的大規(guī)模并行處理系統(tǒng)：曙光-1000

2/2/202334技術特點

曙光-1000是一臺分布存儲的大規(guī)模并行處理MPP（MassivelyParallelProcessing）系統(tǒng)，它突破了MPP中一些技術關鍵，采用20世紀90年代大量先進技術，其峰值速度達25億次，可廣泛應用于科學工程計算、氣象預報、石油勘探、地震數據處理和銀行等商務處理中。其技術特點是：

①良好的可擴放性，包括硬件和軟件兩個方面；2/2/202335②大量的節(jié)點、強大的計算能力和大容量存儲器；③自行設計的穩(wěn)定可靠的蟲蝕通信芯片；④使用帶流控的消息傳遞協(xié)議；⑤優(yōu)良的優(yōu)化并行編譯器；

⑥先進的并行編程環(huán)境、并行查錯工具、自動并行化工具和包括PVM、MPI、Express、NX等的編程工具。

2/2/202336主要技術指標

曙光-1000整體性能達到20世紀90年代初期世界先進水平，其主要技術指標是：

①使用6×6的二維網孔連接、共36個節(jié)點，其中計算節(jié)點32個，服務節(jié)點2個和I/O節(jié)點2個；②峰值速度單精度達2.56Gflops，雙精度1.92Gflops，實際速度為1.58Gflops；③存儲容量為每個節(jié)點32MB，共1GB；④硬盤容量可超過5GB；⑤二維網孔連接、蟲蝕選路，總通信容量為4.8GB/s；

2/2/202337⑥計算節(jié)點和通信網絡間帶寬為2.8GB/s；⑦支持并行C、C++和Fortran，提供并行優(yōu)化重構工具Port和自動并行化工具Autopar、動態(tài)監(jiān)視和分析工具ParaVision以及單計算節(jié)點上源代碼與目標代碼的優(yōu)化工具；⑧基于Unix的分布式并行操作系統(tǒng)；⑨提供并行程序查錯環(huán)境NDB；⑩提供并行程序設計和運行環(huán)境PVM、MPI、Express、NX和P4等。

2/2/202338硬件系統(tǒng)

曙光-1000是一臺分布存儲、消息傳遞的MPP系統(tǒng)，如下圖所示，在6×6二維網孔的每個格點上有一個蟲蝕路由芯片WRC（WormholeRoutingChip）和一個計算節(jié)點（或服務節(jié)點或I/O節(jié)點），系統(tǒng)監(jiān)視器（Monitor）負責系統(tǒng)初始化和硬件故障診斷，用戶工作平臺可以是工作站SUNSparc-Ⅱ(或其它工作站)也可以是終端（它們都稱為前端機），它們通過10Mb/s的以太網連向服務節(jié)點。

2/2/2023392/2/202340（1）二維網孔和WRC：二維網孔是一種擴展的互連網絡。格點上的計算節(jié)點（或服務節(jié)點或I/O節(jié)點）都連向WRC。節(jié)點編號（物理地址）由X方向編號和Y方向編號兩部分組成，節(jié)點間相對地址包含在消息中。一個WRC有10條輸入/輸出通道，每個通道包含8條數據線，一條指明消息結束的尾信號線、一條發(fā)送請求線REQ和一條應答ACK。當一條消息自源發(fā)往目的時，它只穿過途中的WRC，并不進入與WRC相連的節(jié)點處理器。消息選路采用X-Y選路算法。

2/2/202341（2）計算節(jié)點：它是一塊插入板，其核心是一個i860xr芯片，其主頻為40MHz

，字長64位，單精度浮點運算速度為80Mflops，雙精度為60Mflops，標量計算速度為40MIPS；它有帶奇偶校驗的32MBDRAM、8KBEPROM和2KBNVRAM；節(jié)點與網孔的接口模塊包含16KBFIFO，網孔與各節(jié)點間的通信帶寬為33MB/s，消息具有CRC校驗，RS-232接口直接連向監(jiān)視器上的多用戶卡，以便監(jiān)視器能診斷所有的節(jié)點處理器。在所有的計算節(jié)點上運行OS與用戶程序。

2/2/202342（3）服務節(jié)點：服務節(jié)點用于管理系統(tǒng)資源，它是一臺50MHz的具有EISA總線的486PC機。EISA總線與網孔之間有一接口模塊EMI，在EMI卡上有DMA機制；在數據通路FIFO-網孔-FIFO上使用CRC校驗；EMI卡和網孔之間的通信速度是16MB/s。如果較多的用戶和圖形顯示設備，則可使用2個服務節(jié)點，兩者可使用共享系統(tǒng)資源表的方法協(xié)同工作。

2/2/202343（4）I/O節(jié)點：和服務節(jié)點一樣，I/O節(jié)點也是一臺帶有EISA總線、具有EMI插卡的486PC機。一個I/O節(jié)點使用插在EISA總線上的SCSI卡可接入4GB硬盤。系統(tǒng)可提供一個或兩個I/O節(jié)點，當用戶要求大的I/O吞吐率時可使用更多的I/O節(jié)點，但計算節(jié)點則須相應減少。I/O節(jié)點和網孔之間的數據傳輸速度為16MB/s。每個I/O節(jié)點上運行并行文件系統(tǒng)，執(zhí)行并行文件操作。

2/2/202344（5）系統(tǒng)控制臺：也就是監(jiān)視器，它運行SCOUNIX，其中有一塊多用戶卡，連向32個RS-232串行口?？刂婆_與計算節(jié)點可執(zhí)行點到點通信，也可向所有計算節(jié)點同時播送消息。其主要功能是初始化系統(tǒng)、監(jiān)視計算節(jié)點上操作系統(tǒng)和用戶程序的運行、動態(tài)地查看節(jié)點處理器資源組態(tài)表和診斷失效的計算節(jié)點。

2/2/202345（6）前端機：曙光-1000用戶工作平臺是SUNSparc-Ⅱ或SGI圖形工作站或終端，所有這些設備均經由LAN（如以太網）連向系統(tǒng)服務節(jié)點。LAN遵從TCP/IP協(xié)議，其速率為10Mb/s。事實上，網孔系統(tǒng)可視為前端系統(tǒng)的計算服務器，在前端機上用戶程序被編輯、編譯（使用C和Fortran77i860交叉編譯器）、鏈接和查錯，當編譯成功后，應用程序的目標代碼通過以太網傳到服務節(jié)點；然后由服務節(jié)點發(fā)往計算節(jié)點；最終的計算結果由前端機顯示輸出。

2/2/202346系統(tǒng)軟件

（1）操作系統(tǒng)：曙光-1000的操作系統(tǒng)是基于Unix的分布操作系統(tǒng)。在計算節(jié)點上運行微核操作系統(tǒng)，支持虛擬存儲管理、自陷處理、作業(yè)管理和消息傳遞；在服務節(jié)點上運行基于Mach2.6操作系統(tǒng)，支持多線程，其主要功能是系統(tǒng)管理，特別是節(jié)點處理器的分配與去分配；在I/O節(jié)點上運行并行文件服務器PFS。服務節(jié)點和I/O節(jié)點與計算節(jié)點具有相同的消息傳遞接口。系統(tǒng)執(zhí)行帶有流控的消息傳遞協(xié)議。

2/2/202347（2）并行優(yōu)化編譯和工具：節(jié)點程序編譯優(yōu)化包括源碼級優(yōu)化和目標碼級優(yōu)化，前者使用循環(huán)（Loop）交換、循環(huán)合并和循環(huán)分離的辦法開拓并行性；后者采用充分利用流水線、雙指令模式和雙操作指令（由i860所提供的）和浮點加載指令以向量化循環(huán)的方式開拓并行性。Autopar是自行開發(fā)的自動并行化工具，它能識別并行循環(huán)、執(zhí)行數據劃分和產生并行的Fortran源代碼。Paravision是曙光-1000并行系統(tǒng)的可視化工具，它能夠移植到其它MPP系統(tǒng)上，用戶使用它能觀察程序動態(tài)運行過程，包括消息傳遞條件、負載平衡情況和是否出現死鎖等。

2/2/202348（3）并行編程環(huán)境和并行查錯工具：為了便利用戶編程和運行并行程序，曙光-1000移植了4種成熟的界面環(huán)境，即NX、Express、PVM和MPI。其中NX原是Paragon系統(tǒng)上的用戶并行編程界面，而Express、PVM和MPI均是世界上廣泛使用的并行編程和運行環(huán)境。并行程序查錯器包括源代碼查錯程序NDB和匯編代碼查錯程序ADB，它們的主要功能是顯示、設置和取消指令斷點、讀/寫存儲器、逐步或連續(xù)運行程序或發(fā)送和接收現行進程狀態(tài)。它們能夠查錯運行在多個節(jié)點上的程序。

2/2/202349與某些著名MPP系統(tǒng)的性能比較一覽表

下表列出了曙光-1000與某些著名MPP系統(tǒng)的性能比較，性能指標是利用求解標準線性方程組測得的，其中R（max）是機器能夠達到的最高速度，系統(tǒng)N（max）是速度達到R（max）時線性方程組的階，N（1/2）是速度達到1/2R（max）時線性方程組的階。

2/2/2023502/2/202351超級并行計算機系統(tǒng)：曙光-2000

曙光天潮系列“曙光-2000”是基于分布存儲和消息傳遞體系結構的通用可擴放并行計算機系統(tǒng)，其節(jié)點數為4~128個，節(jié)點CPU采用先進的PowerPC604e微處理器，通過高速以太網和蟲蝕路由器芯片組成的二維孔互連。每個節(jié)點上運行完整的IBMAIX操作系統(tǒng)，系統(tǒng)與IBMRS/6000二進制兼容?？蓮V泛應用于科技計算和商業(yè)計算的多種領域中。

2/2/202352設計準則

為了將曙光-2000設計成一種通用、靈活的可擴放并行機系統(tǒng)，設計者們在廣泛分析和深入理解當前硬件、軟件技術發(fā)展趨勢，不同應用領域的需求和用戶環(huán)境要求的基礎上，遵循了一系列設計準則：①一個高性能的可擴放并行系統(tǒng)必須采用標準的微處理器、軟件構件（Component）和操作系統(tǒng)，只應在標準技術無法滿足可擴放并行系統(tǒng)某些特殊要求（如通信延遲）時，才采用定制的硬件和軟件；2/2/202353②采用最新的技術，保證性能價格比的領先優(yōu)勢。為此必須盡可能少地依賴于技術供應商，低層的體系結構必須足夠靈活，在OS級上對各節(jié)點采用松散耦合方式；

③對低延遲的高帶寬的要求使得在今后幾年內可擴放并行計算機系統(tǒng)仍然依賴于定制的內部網絡和通信子系統(tǒng)；④系統(tǒng)的編程和執(zhí)行環(huán)境應與標準的、開放的、分布式Unix環(huán)境一致；⑤系統(tǒng)應當有選擇地在下列領域提供高性能服務：通信系統(tǒng)、高性能文件系統(tǒng)、并行庫、并行數據庫、高速I/O，以利于高效地進行超級計算、并行查詢和高性能事務處理；

2/2/202354⑥消除造成系統(tǒng)崩潰的單一故障點和從失效中快速恢復，可獲得系統(tǒng)高可用性。為此必須有足夠的硬件和軟件備份（Replication），同時提供支持可用性的基礎軟件（故障檢測、診斷、系統(tǒng)重配置和恢復等）；⑦對于單一系統(tǒng)映像進行有選擇地支持，只進行重要資源（如文件、目錄服務）和命令的全局化以及提供對系統(tǒng)管理的單點控制。

2/2/202355體系結構

曙光-2000體系結構

如圖所示。曙光-2000系統(tǒng)可由4~128個處理節(jié)點組成。每個節(jié)點包括可靠的高效的RISC微處理器Power-PC，運行完整的IBMAIX操作系統(tǒng)。諸節(jié)點由高速以太網和二維網孔互連；通信網卡通過PCI總線與節(jié)點相連，外圍子系統(tǒng)通過I/O接口與節(jié)點相連；系統(tǒng)管理員通過控制臺管理系統(tǒng)；用戶工作站或終端通過外部以太網訪問節(jié)點。曙光-2000系統(tǒng)的節(jié)點可分為計算節(jié)點和I/O與登錄服務節(jié)點：前者用于執(zhí)行用戶提交的任務；后者用于支持用戶作業(yè)在計算節(jié)點上運行。

2/2/2023562/2/202357（1）節(jié)點處理器：PowerPC微處理器采用超標量技術（即每個周期同時執(zhí)行多條指令）和很多復雜結構技術來獲得高性能。它擁有6個處理單元（浮點單元FPU、轉移處理單元BPU、存/取單元LSU、2個單周期整數單元SCIU和多周期整數單元MCIU），可同時執(zhí)行4條指令，300MHz主頻的處理器可達到每秒6億次浮點運算。每個處理器的一級高速緩存容量為32KB數據/32KB指令，二級高速緩存容量為1MB；內存容量為128~52MB；內置硬盤容量為4.3GB；I/O總線速率為133MB/s。

2/2/202358（2）通信子系統(tǒng)：曙光-2000采用二維網孔互連，使用“蟲蝕”選路，從而具有可擴放性、低延遲、高帶寬、低處理器開銷和可靠靈活之特性。在二維網孔中，點與點之間采用基于消息包的固定路由、無緩沖的傳輸機制，點與點之間的通信帶寬保持常數，不依賴于拓樸中兩節(jié)點的物理位置。WRC芯片有10個通道，如圖所示，每個通道16位數據寬度，50MHz頻率，數據帶寬100MB/s。芯片內部有X、Y兩個路選擇控制器和4級16位數據緩沖器。曙光-2000節(jié)點通過一塊PCI網絡接口板與底板相連，其中PMI-16接口板由PCI的DMA引擎控制數據傳輸，PMI-960接口板由一個Intel960協(xié)處理器負責DMA傳輸和協(xié)議控制。接口板和節(jié)點內存之間采用DMA方式傳輸，減少了消息傳遞中處理器的開銷。

2/2/2023592/2/202360軟件系統(tǒng)

曙光-2000軟件邏輯結構如下圖所示。其中，每個節(jié)點均由一個完整的AIX4.2以上操作系統(tǒng)管理，它提供了大量的多用戶通信和系統(tǒng)管理技術、編譯器等，符合主要的工業(yè)標準；在低層它提供了用于消息傳遞的基本通信庫BCL、PVM和MPI；在高層提供集成并行程序設計環(huán)境IPPE、并行可視化工具ParaVT、并行調試器DCDB、KISS（KeepItSimpleandScalable）、基于Web的用戶界面、自動并行化工具AutoPAR、可擴放文件系統(tǒng)COSMOS、批作業(yè)管理JOSS、資源管理RMS和曙光服務器聚集軟件DSC；此外，曙光-2000系統(tǒng)還提供了一系列廣泛的IBMRS/6000兼容的開放軟件工具來支持管理和操作，包括IBM的C和Fortran編譯器、數學和工程庫ESSL、數據庫DB2等。

2/2/2023612/2/202362（1）并行環(huán)境：它由BCI、IPPE、ParaVT和DCDB組成，用戶可用來開發(fā)、調試和修改并行Fortran和C程序，并且可啟動、監(jiān)視和控制程序的運行。其中，BCL支持Fortran和C顯式消息傳遞模型，提供大量的函數集和子程序以支持進程間點到點通信和用戶非阻塞通信，并支持多用戶方式用戶空間通信；IPPE提供啟動、監(jiān)視、控制并行應用的用戶環(huán)境，主要功能包括編譯、鏈接并行代碼和通信庫，并行任務分區(qū)、并行作業(yè)加載和監(jiān)視作業(yè)的運行，傻瓜界面KISS提供基于Web的查詢和使用界面；ParaVT提供并行應用的性能監(jiān)視和跟蹤可視化，前者在程序運行時實時地顯示系統(tǒng)的活動狀態(tài)；后者用戶可設置跟蹤點以觀察并行進程間的通信情況、識別死鎖、負載變化和性能瓶頸等；DCDB是一個源代碼級的調試器，支持圖形化使用界面，是在Unix串行調試器dbx或gdb基礎上附加了一些專用的并行程序調試功能。

2/2/202363（2）可擴放文件系統(tǒng)：COSMOS可有效解決超級計算應用對單個文件的可擴展高帶寬的要求，并能提高網絡文件系統(tǒng)吞吐量的可擴放性。它支持對條帶化（Stripe）方式分布存儲的文件的并行訪問；它允許一個并行程序的多個進程對同一文件進行訪問；可支持異步的I/O和規(guī)模大于2GB的文件；COSMOS支持標準Unix文件系統(tǒng)調用，用戶通過UNIXioctl操作可獲得其它的功能。由于每個計算節(jié)點上運行一個ClientDaemon、每個COSMOS服務節(jié)點上運行一個StorageDaemon（或有選擇地運行ManagerDaemon），所以這些服務進程相互通信形成一個可擴放服務器來滿足用戶請求。

2/2/202364（3）可用性服務：曙光-2000所提供的可用性服務包括系統(tǒng)管理軟件中的系統(tǒng)監(jiān)控和NCIC-HA高可用軟件包。目前曙光-2000系統(tǒng)可用性服務的主要功能包括心跳服務、資源組服務、通知服務和恢復協(xié)調服務。其中心跳服務就是監(jiān)視系統(tǒng)的狀態(tài)是否正常，包括偵測和交換心跳信息；資源組服務就是定義節(jié)點和應用程序、系統(tǒng)資源（如IP）屬于一個故障切換資源組，通常該組包括那些相關的應用服務員；通知服務就是在組的結構和節(jié)點狀態(tài)發(fā)生了變化時通知組內成員；恢復服務提供了當組內結構和節(jié)點狀態(tài)發(fā)生變化時，當前組中備份節(jié)點恢復進程的啟動機制，即故障切換（Takeover）。這些服務是由運行在節(jié)點上的HA守護進程（Daemon）所實現的。

2/2/202365（4）全局服務：對于曙光-2000來說，一個全面的單一系統(tǒng)映像并不是迫切需要的，它只是對特殊資源（包括磁盤、文件和通信網絡等）提供單一系統(tǒng)映像。在曙光-2000中，通過網絡文件系統(tǒng)NFS來提供對文件的全局訪問，全局網絡訪問是通過網絡路由機制和TCP/IP及UDP/IP對互連網絡的支持來進行的。在此方式下，可使曙光-2000上的應用以單一的IP地址對外提供服務；曙光-2000還打算使用虛擬共享磁盤VSD提供對磁盤的全局訪問，使用VSD，運行在任何節(jié)點上的應用程序可以透明地訪問任一其它節(jié)點上的磁盤，就像該磁盤是連接在自身節(jié)點上的一樣；2/2/202366另一個全局服務是系統(tǒng)存儲庫SDR，它提供曙光-2000系統(tǒng)中各節(jié)點和控制工作站上的數據存儲和檢索，這包括各個節(jié)點和互連網絡的配置的全局信息以及系統(tǒng)中資源和作業(yè)的信息，這些重要的系統(tǒng)數據不僅要儲存在實現這些系統(tǒng)功能的服務節(jié)點上，而且也應被保存在這些節(jié)點以外的全局儲存庫SDR上。當重要的系統(tǒng)服務發(fā)生故障時，故障節(jié)點可以通過查詢SDR來重新恢復正常工作，在此期間，對服務的請求只是被延遲，但不會引起其它的故障發(fā)生。

2/2/202367（5）系統(tǒng)管理：訪問曙光-2000系統(tǒng)管理和監(jiān)控軟件是建立在大量的AIX工作站環(huán)境中已有的系統(tǒng)管理工具和命令的界面上的，它使得在多節(jié)點上可以運行傳統(tǒng)的系統(tǒng)管理命令，這些命令的功能包括系統(tǒng)安裝、重啟/關機、系統(tǒng)操作、用戶管理、安全管理、作業(yè)記帳、硬件監(jiān)控、打印和郵件服務等；曙光-2000的單點控制在系統(tǒng)控制臺上進行，它是一臺獨立的天演系列工作站，與系統(tǒng)中每一機柜相連，用戶可從網絡的任何一個地方登錄到控制臺；系統(tǒng)管理軟件使用基于SNMP協(xié)議的客戶/服務方式來從控制臺啟動系統(tǒng)管理命令，基于JAVA的圖形化界面用于確定在哪一個節(jié)點上進行操作、修改和收集節(jié)點應答；硬件監(jiān)控軟件使得系統(tǒng)員可以監(jiān)控曙光-2000系統(tǒng)的硬件狀態(tài)。

2/2/202368（6）作業(yè)管理：用戶可以使用批處理或交互方式使用曙光-2000：在批處理方式中，作業(yè)是通過網絡作業(yè)調度程序提交的；在交互方式中，用戶使用Unixrlogin/telnet命令登錄到曙光-2000系統(tǒng)上，通過相應的網絡地址就可直接訪問某個特定的節(jié)點。曙光-2000的資源管理器的主控服務運行在控制臺上，它將相應的節(jié)點分配給并行作業(yè)，當并行作業(yè)被提交時，用戶通過函數或命令向資源管理器申請作業(yè)所需的節(jié)點，如果有相應數量的可用節(jié)點，資源管理器就返回一個可用節(jié)點表，這些節(jié)點就構成了該并行作業(yè)的節(jié)點分區(qū)；當節(jié)點分區(qū)確定后，分區(qū)管理進程就在分區(qū)內的每個節(jié)點上加載一份作業(yè)的可執(zhí)行代碼，并通知該節(jié)點上的守護進程啟動代碼的執(zhí)行；當作業(yè)完成后，分區(qū)管理進程負責清除和終止工作，并交回分區(qū)內所有節(jié)點。

2/2/2023697.3計算機互連網絡1.地位與作用隨著各個領域對高性能計算的要求越來越高，多處理機和多計算機系統(tǒng)的規(guī)模越來越大，處理機之間或處理單元和存儲模塊之間的通信要求和難度也越來越突出。所以互連網絡已成為并行處理系統(tǒng)的核心組成部分，它對整個計算機系統(tǒng)的性能價格比有著決定性的影響?；ミB網絡在多處理機系統(tǒng)中位置和作用如圖所示。2/2/2023702/2/2023712.互連網絡互連網絡是一種由開關元件按照一定的拓撲結構和控制方式構成的網絡，用來實現計算機系統(tǒng)內部多個處理機或多個功能部件之間的相互連接。下圖是具有本地存儲器、私有高速緩存、共享存儲器和共享外圍設備的多處理機系統(tǒng)互連結構。每臺處理機Pi與自己的本地存儲器(LM)和私有高速緩存(Ci)相連，多處理機－存儲器互連網絡IPMN與共享存儲器模塊(SM)相連。處理機通過處理機－I/O網絡PION訪問共享的I/O和外圍設備。處理機之間通過處理機間通信網絡IPCN進行通信。2/2/2023722/2/202373其中：IPMN（處理機－存儲器網絡）PION（處理機－I/O網絡）IPCN（處理機之間通信網絡）P（處理機）C（高速緩沖存儲器）SM（共享存儲器）LM（本地存儲器）2/2/2023743.互連網絡信息的交互發(fā)送方的步驟如下：(1)用戶程序把要發(fā)送的數據拷貝到系統(tǒng)緩沖區(qū)。(2)緩沖區(qū)中的數據打包并發(fā)送到網絡接口部件。(3)網絡接口硬件開始發(fā)送消息。數據包的接收步驟如下：(1)把數據包從網絡接口部件拷貝到系統(tǒng)緩沖區(qū)。(2)檢查收到的數據包，如果正確，發(fā)回答信號。(3)把接收到的數據拷貝到用戶地址空間。發(fā)送方接收到回答信號后釋放系統(tǒng)緩沖區(qū)2/2/2023754.互連網絡的主要時延(1)頻帶寬度(Bandwidth)：傳輸信息的最大速率(2)傳輸時間(Transmissiontime)：等于消息長度除以頻寬。(3)飛行時間(Timeofflight)：第一位信息到達接收方所花費的時間。(4)傳輸時延(Transportlatency)：等于飛行時間與傳輸時間之和。(5)發(fā)送方開銷(Senderoverhead)：處理器把消息放到互連網絡的時間。(6)接收方開銷(Receiveroverhead)：處理器把消息從網絡取出來的時間。2/2/202376一個消息的總時延可以用下面公式表示：

總時延＝發(fā)送方開銷＋飛行時間＋消息長度/頻寬＋接收方開銷2/2/202377例1：假設一個網絡的頻寬為10Mb/S，發(fā)送方開銷為230us，接收方開銷分別為270us。如果兩臺機器相距100米，現在要發(fā)送一個1000字節(jié)的消息給另一臺機器，試計算總時延。如果兩臺機器相距1000公里，那么總時延為多大？（設光的速度為299792.5km/s，信號在導體中傳遞速度大約是光速的50％。）2/2/202378解：相距100米時總時延為：相距1000公里時的總時延為：2/2/2023795.互連網絡的種類靜態(tài)互連網絡：連接通路是固定的，一般不能實現任意結點到結點之間的互連。循環(huán)互連網絡：通過多次重復使用同一個單級互連網絡以實現任意結點到結點之間的互連。多級互連網絡：將多套相同的單級互連網絡連接起來，實現任意結點到結點之間的互連。全排列互連網絡：能夠同時實現任意結點到結點之間的互連。全交叉開關網絡：能夠同時實現任意結點到結點之間的互連，還能夠實現廣播和多播。2/2/2023807.3.1互連網絡的設計準則及互連函數若把處理單元PE或存儲模塊M看成結點，則互連網絡實際為輸入和輸出兩組結點之間提供了數據通路或映像。對于N個輸入和M個輸出來講，由于不允許有多對一的映像（因為會造成訪問沖突），由輸入到輸出映象共有NM種，如果限定為一對一映像，則只有N!種映像。NMICN2/2/2023811.互連網絡的性能參數⑴網絡規(guī)模網絡中的結點數。用于表示網絡中所能連接的部件的多少。⑵連接度（結點度）網絡中與結點相連接的邊的數目。用于表示結點所需要的I/O端口數。入度：進入結點的通道數。出度：從結點出來的通道數。結點度＝入度＋出度。結點度也反映了一個結點與其他結點的連接程度。2/2/202382⑶連接數網絡中所有結點之間連接的數量，即通路（邊數）的總和。⑷距離網絡中兩結點之間相連的最少邊數。⑸網絡直徑網絡中任意兩結點之間距離的最大值。網絡直徑反映了從一個結點傳送信息到任何另一個結點所需的時間，即網絡的延時性。另外，帶寬、可靠性和成本也是反映網絡性能的重要指標。2/2/202383⑴通信工作方式（定時方式）①同步方式用統(tǒng)一的時鐘同步各PE的并行操作以及控制器向處理單元廣播命令的操作。SIMD并行機都采用同步方式。同步方式的控制比較簡單。②異步方式不用統(tǒng)一時鐘同步操作，各個處理單元根據需要相互建立動態(tài)連接。異步方式的控制比較復雜。2.互連網絡設計時應考慮的因素2/2/202384⑵控制策略①集中式控制由一個統(tǒng)一控制器對各個互連開關狀態(tài)加以控制。一般的SIMD并行機都采用集中控制。②分散式控制由各個互連開關自身實行管理。2/2/202385⑶交換方式①線路交換在整個交換過程中，在源和目標結點之間建立固定的物理通路。線路交換適用于成批數據傳送。②分組交換把要傳送的一個信息分成多個分組，分別送入互連網絡。這些分組可通過不同的路由到達目標結點。分組交換適合于短數據報文的傳送。SIMD并行機一般采用線路交換，因為處理單元間的聯(lián)接比較緊密。MIMD多機系統(tǒng)多采用分組交換方式。2/2/202386⑷網絡拓撲拓撲：互連網絡中的各個結點間連接關系，通常用圖來描述。①靜態(tài)拓撲在各結點間有專用的連接通路，且在運行中不能改變。靜態(tài)拓撲一維的有線性陣列結構，二維的有環(huán)形、星形、樹形、網格形等，三維的有立方體等，三維以上的有超立方體等。2/2/2023872/2/202388②動態(tài)拓撲各結點之間的連接通路中設置有源開關，可根據需要利用控制信號對連接通路加以重新組合。動態(tài)拓撲主要有單級循環(huán)網絡和各種多級互連網絡等。2/2/202389每種互連網絡可用一組互連函數來定義，互連函數反映了不同互連網絡的連接特性。若將互連網絡的N個輸入端和N個輸出端分別用整數0，1，…，N－1表示，則互連函數表示互相連接的輸出端號與輸入端號的一一對應關系。或者說，存在互連函數f，輸入i與輸出f(i)相連，0≤i≤N－1。當用互連網絡實現PE與PE之間的數據變換時，互連函數也反映了輸入數組與輸出數組間對應的置換或排列關系，因此互連函數也稱為置換函數或排列函數。3.互連函數2/2/202390互連函數的表示方法⑴輸入輸出對應表示法例：2/2/202391⑵函數表示法用x表示輸入端變量，f(x)表示互連函數。通常把N個輸入端x用N位二進制形式表示為：互連函數對應表示為例：設所以即，127號輸入與254號輸出關聯(lián)。2/2/2023924.拓撲結構圖例（1）線形和環(huán)形2/2/2023932/2/2023942/2/202395（2）樹形和星形2/2/2023962/2/202397（3）網格形和環(huán)網形

2/2/2023982/2/202399（4）超立方體和帶環(huán)立方體2/2/20231002/2/20231012/2/20231022/2/2023103（5）k元n--立方體（k=4,n=3）2/2/2023104按照慣例，低維k元n-立方體稱為環(huán)網，而高維二元n-立方體則稱為超立方體。用網絡折疊的方法可避免環(huán)網中長的端繞連接，如圖所示。2/2/2023105靜態(tài)網絡特性一覽表下表匯總了靜態(tài)互連網絡的重要特性。大多數網絡的結點度都小于4，這是比較理想的。全連接網絡和星形網絡的結點度都太高。超立方體的結點度隨log2N值增大而增大，當N值很大時其結點度也太高。

網絡直徑的變化范圍很大。但隨著硬件尋徑技術不斷革新(蟲蝕尋徑)，直徑已不是一個嚴重問題，因為任意兩結點間的通信延遲在高度流水線操作下幾乎是固定不變的。鏈路數會影響網絡價格，等分寬度將影響網絡的帶寬。

2/2/20231062/2/20231077.3.2單級互連網絡具有N個輸入分配器和N個輸出選擇器的開關網絡。通常只實現有限的幾種基本連接。2/2/2023108在單級互連網絡中，IS和OS分別為一對多和多選一的多路分配和多路選擇器。所有的IS和OS根據互連函數在控制器控制下，在處理單元之間建立起所需要的連接通路。全交叉開關網絡是單級互連網絡中的例外。在全交叉互連網絡中，任何一個結點都有與其他結點的直接通路，所以只需經過一步就可使源結點中的數據傳送到網絡中任一目標結點。全交叉互連網絡具有最好的連接性。2/2/2023109全交叉開關網絡2/2/2023110下圖示出了Digital公司的千兆開關/FDDI中所設計的交叉開關。該交叉開關是為Alpha工作站和服務器的多個FDDI環(huán)之間計算機群互連而設計的。使用FDDI全雙工技術（FFDT），能夠連接多至22個FDDI端口，每路速度為100Mbps。

2/2/20231112/2/2023112由于使用切通選路技術，時延可減少到20微秒。使用2或4端口線卡可構造22端口的交叉開關?？傊?，千兆開關/FDDI能提供高達3.6Gbps的帶寬（是以太網的360倍），它已用在Digital的TruCluster中。千兆開關/FDDI是一種通用的網絡產品，可用于任意以FDDI環(huán)連接的系統(tǒng)中，它是基于交叉開關設計的實現節(jié)點間通信的一個很好例子。2/2/2023113常用的單級互連網絡1．交換互連網絡（Exchange）在網絡規(guī)模為N的互連網絡中，交換互連網絡的互連函數為：E(x)k＝(bn－1…bk…b0)其中：0≤k≤n－1，n＝log2N即把輸入端x的二進制編碼的第k位變反就可得到對應的輸出排列。也寫成2/2/2023114交換互連網絡共有n＝log2N種互連函數。在單級交換互連網絡中，從一個結點到任何另一個結點所需的最短距離(即網絡直徑)為n。當N＝8，n＝log28＝3時，交換互連網絡就是常用的立方體互連網絡。立方體中的每一個頂點代表一個處理單元。8個PE的坐標地址可用3位二進制代碼表示。它的三個互連函數為：2/2/2023115

(a)E0方體置換(b)E1方體置換(c)E2方體置換

2/2/2023116立方體互連網絡2/2/20231172.混洗互連網絡（Shuffle）⑴全混洗Shuffle(bn－1bn－2…b1b0)

＝(bn－2…b0bn－1)即將輸入端x的二進制編碼循環(huán)左移一次就可得到輸出端的二進制編碼。也寫成2/2/2023118子混洗(subshuffle)S(k),最低k位循環(huán)左移一位

超混洗(supershuffle)S(k),最高k位循環(huán)左移一位

顯然成立：逆混洗函數：2/2/2023119例：N＝8時的混洗互連2/2/2023120Σ是x的一次全混洗，若再進行一次混洗，則得到新的函數：即每全混洗一次，輸出端的二進制編碼就是輸入端x的二進制編碼循環(huán)左移一次得到的編碼。當全混洗次數為n時，全部N個輸入對應的輸出又恢復到最初的排列次序。全混洗互連網絡的特點是編號為全“0”和全“1”的輸入端PE無法與網絡中的其他PE相連。2/2/20231213.蝶式互連網絡（Butterfly）Butterfly(bn－1bn－2…b1b0)

＝(b0bn－2…

b1bn－1)即將輸入端x的二進制編碼的最高位與最低位互相交換位置就可得到輸出端的二進制編碼。也寫成2/2/2023122

子蝶式(subbutterfly)B(k)

最低k位的高低位互換

超蝶式(superbutterfly)B(k)

最高k位的高低位互換 顯然成立：2/2/20231234.反位序互連網絡(BitReversalpermutation)

即將輸入x的二進制編碼的位序顛倒就可得到輸出端的二進制編碼。子反位序函數，最低k位的位序反過來;超反位序函數，最高k位的位序反過來.對于N=8,n＝3的情況，正好有：R＝B，R(2)＝B(2)，R(2)＝B(2)。2/2/20231242/2/20231255.移數互連網絡(shiftpurmutation)α(x)＝(x＋1)mod2n0≤x≤N移數互連函數相當于把N個輸入端的二進制編碼同時移動一個位置。即把x的n位二進制編碼的末位上加上“1”再取模2n，就是輸出端的二進制編碼。例：N＝8＝23時的移數互連α(x)。0000010100111001011101110000010100111001011101112/2/2023126移數互連函數用x的十進制編碼更容易表示。一般地，如果需要把N個輸入端同時移動m個位置傳到輸出端，則移數互連函數可寫為：α(x)＝(x＋m)modN

0≤x≤N例：N＝8，m＝2的移數互連01234567012345672/2/20231276.PM2I互連網絡PM2I互連網絡是“加減2i”單級網絡的簡稱，又稱循環(huán)移數網。它的互連函數為移數互連網絡的特例：PM2±i（j）＝（j±2i）modN式中：0≤i≤n－1，0≤j≤N－1，n＝log2N，N是網絡中的結點數。這種互連網絡中共有2n個互連函數。2/2/2023128例：N＝8時，PM2＋0，PM2＋1和PM2＋2互連網絡2/2/202312901234567PM2＋001234567PM2＋101234567PM2±22/2/2023130只需將PM2＋0和PM2＋1中相應的箭頭反向即可實現PM2－0和PM2－1的連接，且PM2＋2＝PM2－2在通用情況下：PM2＋(n－1)＝PM2－(n－1)在N相同的情況下，PM2I網絡比立方體網絡具有更好的連接性。例如，在PM2I網絡處理單元0可直接與處理單元1，2，4，6，7相連，而立方體網絡中0只能與1，2，4相連。2/2/20231317.混洗交換互連網絡混洗交換互連網絡由全混洗Shuffle(x)和交換網絡Exchange0(x)復合而成。也寫成2/2/20231327例：N＝8時的混洗交換互連網絡01234560000010100111001011101110000010100111001011101112/2/2023133N＝8時的混洗交換互連網絡可以看作由Cube0交換函數和全混洗函數復合得到。其中最遠的全“0”和全“1”兩個PE間的連接需要n次交換和n－1次混洗才能實現，所以的最大距離為2n－1。2/2/2023134三種基本單級網絡的比較互連函數個數網絡最大距離（網絡直徑）PM2I2n－1交換nn混洗交換22n－12/2/2023135互連函數舉例假設16個處理機的編號分別為0、1、…、15，采用單級互連網絡。互連函數分別為：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第12號處理機分別與哪一個處理機相連？2/2/2023136解：16個處理器，需4位二進制表示，故：(12)10=(1100)2

(1)Cube3，1100最高位取反得0100，

4號處理機

(2)PM2+3，

(12+8)MOD16=4，

4號處理機

(3)PM2-0，

12–1=11，

11號處理機

(4)Shuffle，

1100循環(huán)左移1位得到1001,

9號處理機

(5)Butterfly，1100的最高最低位交換0101,5號處理機

(6)Reversal，

1100的位序反過來為0011,

3號處理機2/2/20231377.3.3多級互連網絡單級互連網絡通常只能實現有限幾種基本連接，不能實現任意處理單元之間連接。為實現任意處理器間的互連，可采用的方法有：①利用時間重復性，將同一套單級互連網絡循環(huán)使用。特點：節(jié)省器材，但由于輸入、輸出控制部分較為復雜，因此工作速度較慢，一般不采用。②采用空間重復性，將多套單級互連網絡串接使用。特點：縮短了通過時間，提高了速度，可將多種單級互連網絡進行靈活組合以適應多種算法的需要，但增加了成本。2/2/2023138ISC1，ISC2，……，ISCn構成的通用多級互連網絡結構2/2/20231391.決定多級互連網絡特性的主要因素(1)交換開關交換開關是組成互連網絡的基本單元。一個a×b開關模塊中有a個輸入和b個輸出。在理論上a和b不一定要相等，但實際上常選擇使

a＝b＝2k，k≥1。如：常用的開關模塊的大?。?×2，4×4，8×8在交換開關的作用下，每一個輸入可與一個或多個輸出相連，但在輸出端必須避免發(fā)生沖突。即輸入與輸出允許一對一或一對多的映射，但不允許多對一的映射。2/2/2023140只允許一對一映射的開關稱為交叉開關。例：2×2交換開關的功能：直通、交換、上播、下播。四功能開關：具有直通、交換、上播、下播功能。二功能開關（交叉開關）：具有直通、交換功能。2/2/20231412/2/2023142(2)拓撲結構用于表示網絡間各級輸入端與輸出端相互連接的規(guī)則或連接模式。將各種單級互連網絡進行不同組合，可構成各種具有不同連接特性的多級互連網絡。(3)控制方式控制方式是指對各交換開關進行控制的方式①級控同一級的所有交換開關都受同一控制信號控制，對一個n級網絡就需要n個控制信號。2/2/2023143②單元控制每一個交換開關都有一個單獨的控制信號，各自處于不同的狀態(tài)。單元控制的控制電路較為復雜，但靈活性較高。③部分級控對不同的級采用不同數量的控制信號。例如，第0級采用1個控制信號，第1級采用2個控制信號，而第2級采用3個控制信號等，即用i＋1個控制信號控制第i級，0≤i≤n－1，n為級數。為了方便，規(guī)定用寫在交換單元中的文字代表控制信號。若不同框中是同一文字，則表示它們所用的控制信號相同。2/2/20231442.常用的多級互連網絡下面討論的多級互連網絡均為具有N個輸入端、N個輸出端，且級數等于n＝log2N的條件下的基本多級互連網絡。⑴多級立方體網絡由n個Cubei網絡串連構成，其中0≤i≤n－1。因為在單級立方體網絡中，網絡的最大距離為n。所以重復n次使用單級互連網絡，就可以實現任意兩個結點的連接。在多級立方體網絡中將n個單級立方體網絡串連，讓每一級實現一種互連函數E(x)kk＝0，1，…，n－1，就可以實現任意兩個結點的連接。2/2/2023145多級立方體網絡通常采用二功能交換開關構成，根據控制方式的不同分為STARAN網絡和間接二進制n方體網絡等。STARAN網絡采用級控制和部分級控制。間接二進制n方體網絡采用單元控制方式。2/2/2023146例：將具有Cube0，Cube1和Cube2三種互連函數的三個單級立方體網串接起來構成多級立方體STARAN網絡。2/2/2023147①對0～2級采用級控方式，“1”控制開關為交換方式，“0”控制開關為直通方式。當級控信號為“101”時，輸出與輸入的對應關系為：0—5，1—4，2—7，3—6，4—1，5—0，6—3，7—2。采用不同的級控信號，可實現不同的交換功能。2/2/2023148②對各級開關采用部分級控方式。例如，0級級控信號為“0”，1級級控信號為“1”，2級中I、J級控信號為“1”，K、L級控信號為“0”時，輸出與輸入的對應關系為：0—2，1—3，2—4，3—5，4—6，5—7，6—0，7—1。實現了移2（mod8）功能2/2/2023149(2)多級混洗交換網絡多級混洗交換網絡又稱OMEGA網絡，由n級相同的網絡組成，每一級都包含一個全混洗拓撲和隨后一列N/2個四功能交換單元，采用單元控制方式。n級混洗交換網絡的互連函數可以表示成：PSE(n)＝(σ(n)ε(0))n四功能交換單元根據控制信號可分別完成恒等、交換、上播和下播功能。2/2/2023150三級混洗交換網絡2/2/2023151在OMEGA網絡中，各級的編號順序與多級立方體網絡正好相反。當采用級控方式時，OMEGA網絡成為STARAN網絡的逆網絡。當采用單元控制方式時，OMEGA網絡成為間接二進制N方體網絡的逆網絡。OMEGA網絡與多級立方體網絡之間的差別：①前者的數據流向與后者的數據流向正好相反。②前者采用四功能交換開關，而后者采用二功能交換單元。由于OMEGA網絡采用四功能交換開關，因此允許同時實現一個入端到多個出端的連接，具有更多的靈活性。2/2/2023152例：將輸入端2連接到所有輸出端的控制信號為：C、I、J、K、L采用上播，E、F采用下播。2/2/2023153例：實現置換（0，7，6，4，2）（1，3）（5）的控制信號為：2/2/2023154分析：實現置換（06473）（15）（2）的控制信號怎么安排？阻塞出現：A、D、G、I、L==〉阻塞網絡2/2/20231552/2/2023156

一般說來，一個n輸入的Ω網絡需要log2n級2×2開關，每級要用n/2個開關模塊，網絡共需(nlog2n)/2個開關。每個開關模塊采用單元控制方式。

不同的開關狀態(tài)組合可實現各種置換、廣播或從輸入到輸出的其它連接。2/2/2023157(3)多級PM2I互連網絡多級PM2I互連網絡又稱為數據交換網絡。各級中的處理單元按PM2I互連函數進行連接。該網絡由log2N+1列開關單元和log2N級互連網絡構成。例：N＝8，n＝log28＝3，各級處理單元按PM2I互連函數連接起來，其中：第0級：完成PM2I±0。第1級：完成PM2I±1。第2級：完成PM2I±2。第i級的每個輸入端j都有三根連接線分別連到輸出端j、(j＋2i)modN和(j－2i)modN。2/2/20231582/2/2023159在第2級中，因為(x＋22)mod8＝(x－22)mod8，為到同一處理單元提供了冗余通路，有利于提高可靠性。進一步，因為單級PM2I網絡的網絡直徑為，但組成多級PM2I互連網絡時用了n級，所以在網絡中提供了冗余通路，有利于提高可靠性。2/2/2023160(4)基準網絡基準網絡可如下圖(a)所示遞歸生成。

第1級為一個N×N模塊，第2級為兩個(N/2)×(N/2)子模塊，以C0和C1表示。以上構成方法可遞歸用于子模塊，直至得到2×2的N/2子模塊為止。各小框和最終的子模塊構件是2×2開關，每個有兩個合法連接狀態(tài)：兩個輸入和兩個輸出間的直送和交叉連接。16×16基準網絡如下圖(b)所示。

2/2/2023161（a）遞歸構成

2/2/2023162（b）16×16基準網絡

2/2/20231637.3.4消息尋徑方式(略)消息傳遞機制的研究在互連網絡的研究中占有非常重要的地位。

一.消息格式1.消息、包和片等術語消息（Message）：是在多計算機系統(tǒng)的處理接點之間傳遞包含數據和同步消息的信息包。它是一種邏輯單位，可由任意數量的包構成。包（Packet）：包的長度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位。片（Flit）：片的長度固定，一般為8位。2/2/20231642.格式

消息尋徑中的信息單位如圖所示。消息是結點間通信的邏輯單位，它常常由任意數目的長度固定的包組成，因此它的長度是可變的。

2/2/20231652/2/2023166

包是包含尋徑目的地址的基本單位。由于不同的包可能異步地到達目的結點，因此每個包需要一個序號，以便把傳遞的消息重新裝配起來。

可以進一步把包分成一些固定長度的數據片。尋徑信息(目的地址)和序號形成頭片，其余的片是數據片。

在采用存儲轉發(fā)尋徑方式的多計算機系統(tǒng)中，包是信息傳送的最小單位。在采用蟲蝕尋徑網絡的多計算機中，包可以進一步分成片。片的長度往往受網絡大小的影響。256個結點的網絡需要片長為8位。2/2/2023167包的長度取決于尋徑方式和網絡的實現方法。典型的包的長度為64～512位。序號可能占用1～2個片，取決于消息的長度。包和片的大小還與通道頻寬、尋徑器設計以及網絡流量密度等有關。

二.四種尋徑方式

消息尋徑方式可以分為兩大類：線路交換和包交換。其中包交換又包括：存儲轉發(fā)尋徑、虛擬直通尋徑和蟲蝕尋徑等。2/2/2023168(1)線路交換(circuitswitch)：在線路交換這種尋徑方式下，在傳遞一個消息之前，先建立一條從源結點到目的結點的物理通路，然后再傳遞消息，如圖所示。

其傳輸時延用公式表示為T＝(Lt/B)×D+L/B，Lt為建立路徑所需的小信息包的長度，L為信息包的長度，D為經過的結點數，B為帶寬(以下同)。

在并行計算機中的頻繁的小信息包通信的這種方式下，由于在傳遞一個消息之前，需要頻繁地建立從源結點到目的結點的物理通路，開銷將會很大，這種尋徑方式與以下的幾種包交換(packetswitch)的尋徑方式相比這是一個很大的缺點。包交換的尋徑方式以其較高的傳輸帶寬和較低的平均傳輸時延，更適合于具有動態(tài)和突發(fā)特性的MPP數據傳送。2/2/20231692/2/2023170

(2)存儲轉發(fā)尋徑(storeandforward)：在存儲轉發(fā)網絡中包是信息流的基本單位。每個結點有一個包緩沖區(qū)。包從源結點經過一系列中間結點到達目的結點。

當一個包到達一個中間結點時，它首先被存入緩沖區(qū)。當所要求的輸出通道和接收結點的包緩沖區(qū)可使用時，然后再將它傳送給下一個結點。如圖7.26(b)所示。

存儲轉發(fā)網絡的時延與源和目的地之間的距離(段數)成正比。第一代多計算機系統(tǒng)采用這種尋徑方式。其時延用公式表示為T＝(L/B)×D+L/B=(D+1)×L/B。2/2/20231712/2/2023172(3)虛擬直通(virtualcutthrough)：目前有一些多計算機系統(tǒng)采用的是虛擬直通的尋徑方式。虛擬直通的尋徑方式的思想是，為了減少時延，沒有必要等到整個消息全部緩沖后再作路由選擇，只要接收到用作尋徑的消息頭部即可判斷。

其通信時延用公式表示為T=(Lh/B)×D+L/B=(Lh×D+L)/B，Lh是消息的尋徑頭部的長度。一般來說，L>>Lh×D，所以公式可以近似為T＝L/B，可以看到此時通信時延與結點數無關，這相對于存儲轉發(fā)的尋徑方式來說是一個非常大的改進。2/2/2023173

然而，當出現尋徑阻塞時，虛擬直通方式只有將整個消息全部存儲在尋徑結點中，直到尋徑通道不阻塞時才能將消息發(fā)出，這就需要每個尋徑結點都有足夠的緩沖區(qū)來存儲可能出現的最大的信息包，在這一點上，虛擬直通方式與存儲轉發(fā)的尋徑方式是一樣的，同樣不利于VLSI的實現。因此，虛擬直通方式在最壞的情況下與存儲轉發(fā)方式的通信時延是一樣的。由此出現了下面將要討論的新的尋徑方式蟲蝕尋徑方式，它改進了以上提到的缺點。2/2/2023174(4)蟲蝕尋徑(wormhole)：新型的多計算機系統(tǒng)很多采用的是蟲蝕尋徑方式，把包進一步分成更小的片。與結點相連的硬件尋徑器中有片緩沖區(qū)。消息從源結點傳送到目的結點要經過一系列尋徑器，如圖所示。該尋徑由Dally于1986年提出。

同一個包中所有的片象不可分離的同伴一樣以流水方式順序地傳送。包可以看作是一列火車，由火車(頭片)和被牽引的車廂(數據片)組成。

只有頭片知道包將發(fā)往何處。所有的數據片必須跟著頭片。不同的包可以交替地傳送，但不同包的片不能交叉，否則它們可能被送到錯誤的目的地。2/2/20231752/2/2023176

用頭片直接開辟一條以輸入鏈路到輸出鏈路的路徑的方法來進行操作。每個消息中的片以流水方式在網絡中向前“蠕動”。每個片相當于蟲的一個節(jié)，“蠕動”是以節(jié)為單位順序地向前爬行。

當消息的頭片到達一個結點A的尋徑器后，尋徑器根據頭片的尋徑消息立即做出路由選擇：

如果所選擇的通道空閑且所選擇的結點B的片緩沖區(qū)可用，那么這個頭片就不必等待，直接通過結點A傳向下一個結點B。隨后的其它數據片跟著相應地向前“蠕動”一步。當消息的尾片向前“蠕動”一步之后，它剛才所占有的結點就被放棄了。2/2/2023177

為了實現上述的一個包內相繼片的異步流水操作，采用如圖所示的握手協(xié)議。(a)沿著路徑，相鄰尋徑器之間有一根一位的就緒/請求(R/A)線。當接收尋徑器(D)就緒時，就可以接收一片，即片緩沖區(qū)可用了，R/A線的電平變低。(b)當發(fā)送的尋徑器(S)就緒時，R/A線的電平變高并通過通道傳送片I。當D正在接收片時，R/A線保持高電平。(c)當片i從D的緩沖區(qū)移走后(即傳送到下一個結點)，重復上述操作過程以便傳送片i+1，直到整個包都被接收。2/2/20231782/2/2023179蟲蝕尋徑的通信時延用公式表示為：

T=Tf×D+L/B=(Lf/B)×D＋L/B=(Lf×D＋L)/B

其中，Lf是片的長度，Tf是片經過一個結點所需時間。

一般來說，L>>Lf×D，所以公式可以近似為：T＝L/B，可以看到此時通信時延也與結點數無關。

(5)蟲蝕尋徑的優(yōu)點：

(a)每個結點的緩沖區(qū)較小，易于VLSI實現。2/2/2023180

(b)較低的網絡傳輸時延。所有的片以流水方式向前傳輸，采用了時間并行性。而存儲轉發(fā)方式的消息包整個地從一個結點“跳”到另一個結點，通道的使用是串行的，所以它的傳輸時延基本上正比于消息在網絡中傳輸的距離。蟲蝕尋徑方式的網絡傳輸時延正比于消息包的長度，傳輸距離對它的影響很小。

(c)通道共享性好，利用率高，對通道的預約和釋放是結合在一起的一個完整的過程，有一段新的通道后將立即放棄用過的一段舊通道。

(d)易于實現選播和廣播通信方式。允許尋徑器復制消息包的片并把它們從其多個輸出通道輸出。2/2/20231817.4多處理機多處理機結構由若干臺獨立的計算機組成，每臺計算機能夠獨立執(zhí)行自己的程序，屬于MIMD系統(tǒng)。多處理機系統(tǒng)的目的是開發(fā)粗粒度的并行性，即作業(yè)或任務級的并行性。在多處理機系統(tǒng)中存在有多個指令控制流，每個指令控制流分別獨立地對共享主存中數據進行加工或是對自己私有局部存儲器中的數據對象進行加工。處理器之間按某種形式互連，實現程序之間的數據交換和同步。多處理機系統(tǒng)中處理器之間通過適當的通信，可以協(xié)同求解