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

下圖給出了從標(biāo)量到向量和并行計算機(jī)的演變。3/4/202483/4/20249陣列機(jī)以SIMD方式工作、采用資源重復(fù)技術(shù)實(shí)現(xiàn)數(shù)據(jù)處理時的高度并行的陣列處理機(jī)。陣列機(jī)主要用于處理向量和陣列型數(shù)據(jù)。它在同一個控制部件管理下，有多個處理單元。所有處理單元均收到從控制部件廣播來的同一條指令，但操作對象是不同的數(shù)據(jù)。H.J.Siegel提出了SIMD計算機(jī)的操作模型。3/4/2024107.2.1陣列機(jī)的基本結(jié)構(gòu)1.陣列機(jī)的結(jié)構(gòu)陣列機(jī)通常由一個控制器（CU）、N個處理器單元（PE）、M個存儲器模塊（M）以及一個互連網(wǎng)絡(luò)部件（IN）所組成?；ミB網(wǎng)絡(luò)（IN）有時也稱為對準(zhǔn)網(wǎng)絡(luò)或排列網(wǎng)絡(luò)。3/4/202411H.J.Siegel提出的并行處理機(jī)模型

3/4/2024122.陣列機(jī)的工作方式陣列機(jī)工作時，由控制器CU控制將指令廣播給系統(tǒng)中的各個PE，所有活躍的PE將以同步方式執(zhí)行相同的指令（單指令流）。PE從相應(yīng)的存儲模塊中取得自己所需的數(shù)據(jù)對象（多數(shù)據(jù)流）進(jìn)行處理。互連網(wǎng)絡(luò)IN用來使各個PE之間或是PE和M之間實(shí)現(xiàn)方便的通信連接。3/4/2024133.陣列機(jī)的兩種基本結(jié)構(gòu)⑴分布式存儲器陣列機(jī)3/4/202414①N個相同的處理單元PE由處理器Pi和局部存儲器Mi組成。各個Pi主要將從自己的局部存儲器

Mi中獲取數(shù)據(jù)進(jìn)行操作。各個PE通過IN實(shí)現(xiàn)相互間必要的數(shù)據(jù)交換，因此IN是單向的。②CU具有自己的存儲器，用于存放系統(tǒng)程序、用戶程序以及各個PE所需的共享數(shù)據(jù)。CU的主要功能是對指令譯碼和判別指令應(yīng)在何處執(zhí)行。對于標(biāo)量或控制類指令，CU利用本身的運(yùn)算部件直接執(zhí)行；若是向量指令，它就將指令廣播到各個PE去執(zhí)行。分布式存儲器陣列機(jī)的特點(diǎn)3/4/202415③各個PE同步執(zhí)行來自CU的操作命令。但是并不一定每個操作非得所有PE都參加，CU將對PE實(shí)行屏蔽控制，只有那些未被屏蔽的活躍PE才可參加操作。CU控制互連網(wǎng)絡(luò)IN，使各個PE之間通過IN實(shí)現(xiàn)相互之間必要的數(shù)據(jù)交換。當(dāng)相互需要交換數(shù)據(jù)的兩個PE不直接相連時，就需要經(jīng)過它們之間的中間PE來完成連接。3/4/202416⑵共享存儲器的陣列機(jī)3/4/202417①每個PE沒有自己的局部存儲器。存儲器模塊以集中形式為所有PE（通過IN）共享。②互連網(wǎng)絡(luò)受CU控制，用來構(gòu)成PE和M之間的數(shù)據(jù)交換通路。要求互連網(wǎng)絡(luò)具有同時連接PE到M和M到PE的雙向性。③系統(tǒng)中的一個PE可以與任何另一個PE實(shí)現(xiàn)數(shù)據(jù)交換（只要有任何一個存儲模塊同時與這兩個PE相連接）。當(dāng)兩個需交換數(shù)據(jù)的PE之間沒有共享的存儲模塊時，可能需要經(jīng)過多次的傳送之后，方可實(shí)現(xiàn)交換。④互連網(wǎng)絡(luò)比較復(fù)雜。共享存儲器陣列機(jī)的特點(diǎn)3/4/202418SIMD計算機(jī)的操作模型可用五元組表示：

C＝<N，C，I，M，R>式中：

(1)N為機(jī)器的處理單元(PE)數(shù)。

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

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

陣列機(jī)特征的形式化表示3/4/202419

(3)I為由CU廣播至所有PE進(jìn)行并行執(zhí)行的指令集，它包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其它由每個活動的PE對它的數(shù)據(jù)所執(zhí)行的局部操作。

(4)M為屏蔽方案集，其中每種屏蔽將PE集劃分為允許操作和禁止操作兩種子集。

(5)R是數(shù)據(jù)尋徑功能集，說明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。

F=(C,R)

描述了互連網(wǎng)絡(luò)及參數(shù)這種描述模型為評價不同的陣列機(jī)結(jié)構(gòu)提供了比較基礎(chǔ)。3/4/202420計算機(jī)的操作特性描述如MasParMP-1計算機(jī)：

(1)PE數(shù)N＝1024至16384。PE數(shù)目與機(jī)器配置有關(guān)。

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

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

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

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

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

3/4/2024243/4/202425LDA

ALPHA

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

ADRN

ALPHA＋1；全部(a+1)與(RGA)進(jìn)行浮點(diǎn)規(guī)舍加，結(jié)果送PGA

STA

ALPHA＋2；全部(RGA)由PE送

PEM的a+2單元。

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

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

3/4/2024273/4/202428下圖示出了Illiac-IV帶環(huán)繞的2維網(wǎng)孔互連網(wǎng)絡(luò)，這是一種4近鄰的互連網(wǎng)絡(luò)，從一個PE發(fā)送數(shù)據(jù)到另一個PE，在最壞情況下，須要經(jīng)過步（n為PE數(shù)）。這種互連拓樸形式很適合于求解偏微分方程和矩陣運(yùn)算之類的問題。當(dāng)64個PE并行工作時，系統(tǒng)峰值速度可達(dá)每秒2億次運(yùn)算，它主要應(yīng)用于氣象預(yù)報和核工程研究等領(lǐng)域。3/4/202429IlliacIV處理陣列的連接由８

８＝64個PU組成。每個PU由處理部件PE和它的局部存儲器PEM組成。每一個PUi只和它的東、西、南、北四個近鄰：

PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64直接連接。南北方向同一列PU連成一個環(huán)， 東西方向構(gòu)成一個閉合螺線。閉合螺線網(wǎng)絡(luò)直徑為7步， 環(huán)形網(wǎng)格的直徑為8步。3/4/2024303/4/202431陣列控制器CU陣列控制器CU實(shí)際上是一臺小型計算機(jī)。

對陣列處理單元實(shí)行控制和完成標(biāo)量操作。 標(biāo)量操作與各PE的數(shù)組操作可以重疊執(zhí)行。控制器的功能有以下五個方面：

(1)對指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令；

(2)向各PE發(fā)出執(zhí)行數(shù)組操作指令的控制信號；

(3)產(chǎn)生并向所有處理單元廣播公共的地址；

(4)產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；

(5)接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號。3/4/202432二、國產(chǎn)曙光系列并行機(jī)系統(tǒng)介紹

我國的高性能計算機(jī)的發(fā)展起步并不晚：早在20世紀(jì)60年代后期到70年代，我國就自行研制了大型計算機(jī)（MainframeComputer），其典型代表機(jī)器有150、905、718和DJS260等，它們采用單/雙CPU，其峰值速度約為1MOPS（MillionOperationsPerSecond），即俗稱的百萬次機(jī)器；20世紀(jì)70年代后期到80年代，我國研制了向量機(jī)和多處理機(jī)，其典型代表機(jī)器有757、銀河1號和2號等，它們采用1~4個CPU，其峰值速度達(dá)10~100MOPS，即俗稱的億次機(jī)器。3/4/20243320世紀(jì)80年代后期到現(xiàn)在，我國研制了對稱多處理機(jī)（SMP）、大規(guī)模并行機(jī)（MPP）和工作站群（COW），其典型代表機(jī)器有曙光1號、曙光-1000/1000A、YH-3和曙光-2000等，它們采用4~128個CPU，其峰值速度達(dá)1Gflops~幾十Gflops，即俗稱百億次機(jī)器，我國1999年正式推出了千億次高性能計算機(jī)。

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

3/4/202434技術(shù)特點(diǎn)

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

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

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

3/4/202436主要技術(shù)指標(biāo)

曙光-1000整體性能達(dá)到20世紀(jì)90年代初期世界先進(jìn)水平，其主要技術(shù)指標(biāo)是：

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

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

3/4/202438硬件系統(tǒng)

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

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

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

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

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

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

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

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

3/4/202446系統(tǒng)軟件

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

3/4/202447（2）并行優(yōu)化編譯和工具：節(jié)點(diǎn)程序編譯優(yōu)化包括源碼級優(yōu)化和目標(biāo)碼級優(yōu)化，前者使用循環(huán)（Loop）交換、循環(huán)合并和循環(huán)分離的辦法開拓并行性；后者采用充分利用流水線、雙指令模式和雙操作指令（由i860所提供的）和浮點(diǎn)加載指令以向量化循環(huán)的方式開拓并行性。Autopar

是自行開發(fā)的自動并行化工具，它能識別并行循環(huán)、執(zhí)行數(shù)據(jù)劃分和產(chǎn)生并行的Fortran源代碼。Paravision是曙光-1000并行系統(tǒng)的可視化工具，它能夠移植到其它MPP系統(tǒng)上，用戶使用它能觀察程序動態(tài)運(yùn)行過程，包括消息傳遞條件、負(fù)載平衡情況和是否出現(xiàn)死鎖等。

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

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

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

3/4/2024503/4/202451超級并行計算機(jī)系統(tǒng)：曙光-2000

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

3/4/202452設(shè)計準(zhǔn)則

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

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

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

3/4/202455體系結(jié)構(gòu)

曙光-2000體系結(jié)構(gòu)

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

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

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

DMA引擎控制數(shù)據(jù)傳輸，PMI-960接口板由一個Intel960協(xié)處理器負(fù)責(zé)DMA傳輸和協(xié)議控制。接口板和節(jié)點(diǎn)內(nèi)存之間采用DMA方式傳輸，減少了消息傳遞中處理器的開銷。

3/4/2024593/4/202460軟件系統(tǒng)

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

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

3/4/202463（2）可擴(kuò)放文件系統(tǒng)：COSMOS可有效解決超級計算應(yīng)用對單個文件的可擴(kuò)展高帶寬的要求，并能提高網(wǎng)絡(luò)文件系統(tǒng)吞吐量的可擴(kuò)放性。它支持對條帶化（Stripe）方式分布存儲的文件的并行訪問；它允許一個并行程序的多個進(jìn)程對同一文件進(jìn)行訪問；可支持異步的I/O和規(guī)模大于2GB的文件；COSMOS支持標(biāo)準(zhǔn)Unix文件系統(tǒng)調(diào)用，用戶通過UNIXioctl操作可獲得其它的功能。由于每個計算節(jié)點(diǎn)上運(yùn)行一個ClientDaemon、每個COSMOS服務(wù)節(jié)點(diǎn)上運(yùn)行一個

StorageDaemon（或有選擇地運(yùn)行ManagerDaemon），所以這些服務(wù)進(jìn)程相互通信形成一個可擴(kuò)放服務(wù)器來滿足用戶請求。

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

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

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

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

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

總時延＝發(fā)送方開銷＋飛行時間＋消息長度/頻寬＋接收方開銷3/4/202477例1：假設(shè)一個網(wǎng)絡(luò)的頻寬為10Mb/S，發(fā)送方開銷為230us，接收方開銷分別為270us。如果兩臺機(jī)器相距100米，現(xiàn)在要發(fā)送一個1000字節(jié)的消息給另一臺機(jī)器，試計算總時延。如果兩臺機(jī)器相距1000公里，那么總時延為多大？（設(shè)光的速度為299792.5km/s，信號在導(dǎo)體中傳遞速度大約是光速的50％。）3/4/202478解：相距100米時總時延為：相距1000公里時的總時延為：3/4/2024795.互連網(wǎng)絡(luò)的種類靜態(tài)互連網(wǎng)絡(luò)：連接通路是固定的，一般不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。循環(huán)互連網(wǎng)絡(luò)：通過多次重復(fù)使用同一個單級互連網(wǎng)絡(luò)以實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。多級互連網(wǎng)絡(luò)：將多套相同的單級互連網(wǎng)絡(luò)連接起來，實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。全排列互連網(wǎng)絡(luò)：能夠同時實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。全交叉開關(guān)網(wǎng)絡(luò)：能夠同時實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連，還能夠?qū)崿F(xiàn)廣播和多播。3/4/2024807.3.1互連網(wǎng)絡(luò)的設(shè)計準(zhǔn)則及互連函數(shù)若把處理單元PE或存儲模塊M看成結(jié)點(diǎn)，則互連網(wǎng)絡(luò)實(shí)際為輸入和輸出兩組結(jié)點(diǎn)之間提供了數(shù)據(jù)通路或映像。對于N個輸入和M個輸出來講，由于不允許有多對一的映像（因?yàn)闀斐稍L問沖突），由輸入到輸出映象共有NM種，如果限定為一對一映像，則只有N!種映像。NMICN3/4/2024811.互連網(wǎng)絡(luò)的性能參數(shù)⑴網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)。用于表示網(wǎng)絡(luò)中所能連接的部件的多少。⑵連接度（結(jié)點(diǎn)度）網(wǎng)絡(luò)中與結(jié)點(diǎn)相連接的邊的數(shù)目。用于表示結(jié)點(diǎn)所需要的I/O端口數(shù)。入度：進(jìn)入結(jié)點(diǎn)的通道數(shù)。出度：從結(jié)點(diǎn)出來的通道數(shù)。結(jié)點(diǎn)度＝入度＋出度。結(jié)點(diǎn)度也反映了一個結(jié)點(diǎn)與其他結(jié)點(diǎn)的連接程度。3/4/202482⑶連接數(shù)網(wǎng)絡(luò)中所有結(jié)點(diǎn)之間連接的數(shù)量，即通路（邊數(shù)）的總和。⑷

距離網(wǎng)絡(luò)中兩結(jié)點(diǎn)之間相連的最少邊數(shù)。⑸網(wǎng)絡(luò)直徑網(wǎng)絡(luò)中任意兩結(jié)點(diǎn)之間距離的最大值。網(wǎng)絡(luò)直徑反映了從一個結(jié)點(diǎn)傳送信息到任何另一個結(jié)點(diǎn)所需的時間，即網(wǎng)絡(luò)的延時性。另外，帶寬、可靠性和成本也是反映網(wǎng)絡(luò)性能的重要指標(biāo)。3/4/202483⑴通信工作方式（定時方式）①同步方式用統(tǒng)一的時鐘同步各PE的并行操作以及控制器向處理單元廣播命令的操作。SIMD并行機(jī)都采用同步方式。同步方式的控制比較簡單。②異步方式不用統(tǒng)一時鐘同步操作，各個處理單元根據(jù)需要相互建立動態(tài)連接。異步方式的控制比較復(fù)雜。2.互連網(wǎng)絡(luò)設(shè)計時應(yīng)考慮的因素3/4/202484⑵控制策略①集中式控制由一個統(tǒng)一控制器對各個互連開關(guān)狀態(tài)加以控制。一般的SIMD并行機(jī)都采用集中控制。②分散式控制由各個互連開關(guān)自身實(shí)行管理。3/4/202485⑶交換方式①線路交換在整個交換過程中，在源和目標(biāo)結(jié)點(diǎn)之間建立固定的物理通路。線路交換適用于成批數(shù)據(jù)傳送。②分組交換把要傳送的一個信息分成多個分組，分別送入互連網(wǎng)絡(luò)。這些分組可通過不同的路由到達(dá)目標(biāo)結(jié)點(diǎn)。分組交換適合于短數(shù)據(jù)報文的傳送。SIMD并行機(jī)一般采用線路交換，因?yàn)樘幚韱卧g的聯(lián)接比較緊密。MIMD多機(jī)系統(tǒng)多采用分組交換方式。3/4/202486⑷網(wǎng)絡(luò)拓?fù)渫負(fù)洌夯ミB網(wǎng)絡(luò)中的各個結(jié)點(diǎn)間連接關(guān)系，通常用圖來描述。①靜態(tài)拓?fù)湓诟鹘Y(jié)點(diǎn)間有專用的連接通路，且在運(yùn)行中不能改變。靜態(tài)拓?fù)湟痪S的有線性陣列結(jié)構(gòu)，二維的有環(huán)形、星形、樹形、網(wǎng)格形等，三維的有立方體等，三維以上的有超立方體等。3/4/2024873/4/202488②動態(tài)拓?fù)涓鹘Y(jié)點(diǎn)之間的連接通路中設(shè)置有源開關(guān)，可根據(jù)需要利用控制信號對連接通路加以重新組合。動態(tài)拓?fù)渲饕袉渭壯h(huán)網(wǎng)絡(luò)和各種多級互連網(wǎng)絡(luò)等。3/4/202489每種互連網(wǎng)絡(luò)可用一組互連函數(shù)來定義，互連函數(shù)反映了不同互連網(wǎng)絡(luò)的連接特性。若將互連網(wǎng)絡(luò)的N個輸入端和N個輸出端分別用整數(shù)0，1，…，N－1表示，則互連函數(shù)表示互相連接的輸出端號與輸入端號的一一對應(yīng)關(guān)系。或者說，存在互連函數(shù)f，輸入i與輸出f(i)相連，0≤i≤N－1。當(dāng)用互連網(wǎng)絡(luò)實(shí)現(xiàn)PE與PE之間的數(shù)據(jù)變換時，互連函數(shù)也反映了輸入數(shù)組與輸出數(shù)組間對應(yīng)的置換或排列關(guān)系，因此互連函數(shù)也稱為置換函數(shù)或排列函數(shù)。3.互連函數(shù)3/4/202490互連函數(shù)的表示方法⑴輸入輸出對應(yīng)表示法例：3/4/202491⑵函數(shù)表示法用x表示輸入端變量，f(x)表示互連函數(shù)。通常把N個輸入端x用N位二進(jìn)制形式表示為：互連函數(shù)對應(yīng)表示為例：設(shè)所以即，127號輸入與254號輸出關(guān)聯(lián)。3/4/2024924.拓?fù)浣Y(jié)構(gòu)圖例（1）線形和環(huán)形3/4/2024933/4/2024943/4/202495（2）樹形和星形3/4/2024963/4/202497（3）網(wǎng)格形和環(huán)網(wǎng)形

3/4/2024983/4/202499（4）超立方體和帶環(huán)立方體3/4/20241003/4/20241013/4/20241023/4/2024103（5）k元n--立方體（k=4,n=3）3/4/2024104按照慣例，低維k元n-立方體稱為環(huán)網(wǎng)，而高維二元n-立方體則稱為超立方體。用網(wǎng)絡(luò)折疊的方法可避免環(huán)網(wǎng)中長的端繞連接，如圖所示。3/4/2024105靜態(tài)網(wǎng)絡(luò)特性一覽表下表匯總了靜態(tài)互連網(wǎng)絡(luò)的重要特性。大多數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度都小于4，這是比較理想的。全連接網(wǎng)絡(luò)和星形網(wǎng)絡(luò)的結(jié)點(diǎn)度都太高。超立方體的結(jié)點(diǎn)度隨log2N值增大而增大，當(dāng)N值很大時其結(jié)點(diǎn)度也太高。

網(wǎng)絡(luò)直徑的變化范圍很大。但隨著硬件尋徑技術(shù)不斷革新(蟲蝕尋徑)，直徑已不是一個嚴(yán)重問題，因?yàn)槿我鈨山Y(jié)點(diǎn)間的通信延遲在高度流水線操作下幾乎是固定不變的。鏈路數(shù)會影響網(wǎng)絡(luò)價格，等分寬度將影響網(wǎng)絡(luò)的帶寬。

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

3/4/20241113/4/2024112由于使用切通選路技術(shù)，時延可減少到20微秒。使用2或4端口線卡可構(gòu)造22端口的交叉開關(guān)?？傊?，千兆開關(guān)/FDDI能提供高達(dá)3.6Gbps的帶寬（是以太網(wǎng)的360倍），它已用在Digital的TruCluster中。千兆開關(guān)/FDDI是一種通用的網(wǎng)絡(luò)產(chǎn)品，可用于任意以FDDI環(huán)連接的系統(tǒng)中，它是基于交叉開關(guān)設(shè)計的實(shí)現(xiàn)節(jié)點(diǎn)間通信的一個很好例子。3/4/2024113常用的單級互連網(wǎng)絡(luò)1．交換互連網(wǎng)絡(luò)（Exchange）在網(wǎng)絡(luò)規(guī)模為N的互連網(wǎng)絡(luò)中，交換互連網(wǎng)絡(luò)的互連函數(shù)為：

E(x)k＝(bn－1…bk…b0)其中：0≤k≤n－1，n＝log2N即把輸入端x的二進(jìn)制編碼的第k位變反就可得到對應(yīng)的輸出排列。也寫成3/4/2024114交換互連網(wǎng)絡(luò)共有n＝log2N種互連函數(shù)。在單級交換互連網(wǎng)絡(luò)中，從一個結(jié)點(diǎn)到任何另一個結(jié)點(diǎn)所需的最短距離(即網(wǎng)絡(luò)直徑)為n。當(dāng)N＝8，n＝log28＝3時，交換互連網(wǎng)絡(luò)就是常用的立方體互連網(wǎng)絡(luò)。立方體中的每一個頂點(diǎn)代表一個處理單元。8個PE的坐標(biāo)地址可用3位二進(jìn)制代碼表示。它的三個互連函數(shù)為：3/4/2024115

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

3/4/2024116立方體互連網(wǎng)絡(luò)3/4/20241172.混洗互連網(wǎng)絡(luò)（Shuffle）⑴全混洗Shuffle(bn－1bn－2…b1b0)

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

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

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

＝(b0

bn－2…

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

子蝶式(subbutterfly)B(k)

最低k位的高低位互換

超蝶式(superbutterfly)B(k)

最高k位的高低位互換 顯然成立：3/4/20241234.反位序互連網(wǎng)絡(luò)(BitReversalpermutation)

即將輸入x的二進(jìn)制編碼的位序顛倒就可得到輸出端的二進(jìn)制編碼。子反位序函數(shù)，最低k位的位序反過來;超反位序函數(shù)，最高k位的位序反過來.對于N=8,n＝3的情況，正好有：

R＝B，R(2)＝B(2)，R(2)＝B(2)。3/4/20241243/4/20241255.移數(shù)互連網(wǎng)絡(luò)(shiftpurmutation)

α(x)＝(x＋1)mod2n0≤x≤N移數(shù)互連函數(shù)相當(dāng)于把N個輸入端的二進(jìn)制編碼同時移動一個位置。即把x的n位二進(jìn)制編碼的末位上加上“1”再取模2n，就是輸出端的二進(jìn)制編碼。例：N＝8＝23時的移數(shù)互連α(x)。0000010100111001011101110000010100111001011101113/4/2024126移數(shù)互連函數(shù)用x的十進(jìn)制編碼更容易表示。一般地，如果需要把N個輸入端同時移動m個位置傳到輸出端，則移數(shù)互連函數(shù)可寫為：

α(x)＝(x＋m)modN

0≤x≤N例：N＝8，m＝2的移數(shù)互連01234567012345673/4/20241276.PM2I互連網(wǎng)絡(luò)PM2I互連網(wǎng)絡(luò)是“加減2i”單級網(wǎng)絡(luò)的簡稱，又稱循環(huán)移數(shù)網(wǎng)。它的互連函數(shù)為移數(shù)互連網(wǎng)絡(luò)的特例：

PM2±i（j）＝（j±2i）modN式中：0≤i≤n－1，0≤j≤N－1，n＝log2N，N是網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)。這種互連網(wǎng)絡(luò)中共有2n個互連函數(shù)。3/4/2024128例：N＝8時，PM2＋0，PM2＋1和PM2＋2互連網(wǎng)絡(luò)3/4/202412901234567PM2＋001234567PM2＋101234567PM2±23/4/2024130只需將PM2＋0和PM2＋1中相應(yīng)的箭頭反向即可實(shí)現(xiàn)PM2－0和PM2－1的連接，且PM2＋2＝PM2－2在通用情況下：PM2＋(n－1)＝PM2－(n－1)在N相同的情況下，PM2I網(wǎng)絡(luò)比立方體網(wǎng)絡(luò)具有更好的連接性。例如，在PM2I網(wǎng)絡(luò)處理單元0可直接與處理單元1，2，4，6，7相連，而立方體網(wǎng)絡(luò)中0只能與1，2，4相連。3/4/20241317.混洗交換互連網(wǎng)絡(luò)混洗交換互連網(wǎng)絡(luò)由全混洗Shuffle(x)和交換網(wǎng)絡(luò)Exchange0(x)復(fù)合而成。也寫成3/4/20241327例：N＝8時的混洗交換互連網(wǎng)絡(luò)01234560000010100111001011101110000010100111001011101113/4/2024133

N＝8時的混洗交換互連網(wǎng)絡(luò)可以看作由Cube0交換函數(shù)和全混洗函數(shù)復(fù)合得到。其中最遠(yuǎn)的全“0”和全“1”兩個PE間的連接需要n次交換和n－1次混洗才能實(shí)現(xiàn)，所以的最大距離為2n－1。3/4/2024134三種基本單級網(wǎng)絡(luò)的比較互連函數(shù)個數(shù)網(wǎng)絡(luò)最大距離（網(wǎng)絡(luò)直徑）PM2I2n－1交換nn混洗交換22n－13/4/2024135互連函數(shù)舉例假設(shè)16個處理機(jī)的編號分別為0、1、…、15，采用單級互連網(wǎng)絡(luò)?；ミB函數(shù)分別為：

(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal

第12號處理機(jī)分別與哪一個處理機(jī)相連？3/4/2024136解：

16個處理器，需4位二進(jìn)制表示，故：

(12)10=(1100)2

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

4號處理機(jī)

(2)PM2+3，

(12+8)MOD16=4，

4號處理機(jī)

(3)PM2-0，

12–1=11，

11號處理機(jī)

(4)Shuffle，

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

9號處理機(jī)

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

(6)Reversal，

1100的位序反過來為0011,

3號處理機(jī)3/4/20241377.3.3多級互連網(wǎng)絡(luò)單級互連網(wǎng)絡(luò)通常只能實(shí)現(xiàn)有限幾種基本連接，不能實(shí)現(xiàn)任意處理單元之間連接。為實(shí)現(xiàn)任意處理器間的互連，可采用的方法有：①利用時間重復(fù)性，將同一套單級互連網(wǎng)絡(luò)循環(huán)使用。特點(diǎn)：節(jié)省器材，但由于輸入、輸出控制部分較為復(fù)雜，因此工作速度較慢，一般不采用。②采用空間重復(fù)性，將多套單級互連網(wǎng)絡(luò)串接使用。特點(diǎn)：縮短了通過時間，提高了速度，可將多種單級互連網(wǎng)絡(luò)進(jìn)行靈活組合以適應(yīng)多種算法的需要，但增加了成本。3/4/2024138ISC1，ISC2，……，ISCn構(gòu)成的通用多級互連網(wǎng)絡(luò)結(jié)構(gòu)3/4/20241391.決定多級互連網(wǎng)絡(luò)特性的主要因素

(1)交換開關(guān)交換開關(guān)是組成互連網(wǎng)絡(luò)的基本單元。一個a×b開關(guān)模塊中有a個輸入和b個輸出。在理論上a和b不一定要相等，但實(shí)際上常選擇使

a＝b＝2k，k≥1。如：常用的開關(guān)模塊的大?。?×2，4×4，8×8在交換開關(guān)的作用下，每一個輸入可與一個或多個輸出相連，但在輸出端必須避免發(fā)生沖突。即輸入與輸出允許一對一或一對多的映射，但不允許多對一的映射。3/4/2024140只允許一對一映射的開關(guān)稱為交叉開關(guān)。例：2×2交換開關(guān)的功能：直通、交換、上播、下播。四功能開關(guān)：具有直通、交換、上播、下播功能。二功能開關(guān)（交叉開關(guān)）：具有直通、交換功能。3/4/20241413/4/2024142(2)拓?fù)浣Y(jié)構(gòu)用于表示網(wǎng)絡(luò)間各級輸入端與輸出端相互連接的規(guī)則或連接模式。將各種單級互連網(wǎng)絡(luò)進(jìn)行不同組合，可構(gòu)成各種具有不同連接特性的多級互連網(wǎng)絡(luò)。(3)控制方式控制方式是指對各交換開關(guān)進(jìn)行控制的方式①級控同一級的所有交換開關(guān)都受同一控制信號控制，對一個n級網(wǎng)絡(luò)就需要n個控制信號。3/4/2024143②單元控制每一個交換開關(guān)都有一個單獨(dú)的控制信號，各自處于不同的狀態(tài)。單元控制的控制電路較為復(fù)雜，但靈活性較高。③部分級控對不同的級采用不同數(shù)量的控制信號。例如，第0級采用1個控制信號，第1級采用2個控制信號，而第2級采用3個控制信號等，即用i＋1個控制信號控制第i級，0≤i≤n－1，n為級數(shù)。為了方便，規(guī)定用寫在交換單元中的文字代表控制信號。若不同框中是同一文字，則表示它們所用的控制信號相同。3/4/20241442.常用的多級互連網(wǎng)絡(luò)下面討論的多級互連網(wǎng)絡(luò)均為具有N個輸入端、N個輸出端，且級數(shù)等于n＝log2N的條件下的基本多級互連網(wǎng)絡(luò)。⑴多級立方體網(wǎng)絡(luò)由n個Cubei

網(wǎng)絡(luò)串連構(gòu)成，其中0≤i≤n－1。因?yàn)樵趩渭壛⒎襟w網(wǎng)絡(luò)中，網(wǎng)絡(luò)的最大距離為n。所以重復(fù)

n次使用單級互連網(wǎng)絡(luò)，就可以實(shí)現(xiàn)任意兩個結(jié)點(diǎn)的連接。在多級立方體網(wǎng)絡(luò)中將

n個單級立方體網(wǎng)絡(luò)串連，讓每一級實(shí)現(xiàn)一種互連函數(shù)E(x)kk＝0，1，…，n－1，就可以實(shí)現(xiàn)任意兩個結(jié)點(diǎn)的連接。3/4/2024145多級立方體網(wǎng)絡(luò)通常采用二功能交換開關(guān)構(gòu)成，根據(jù)控制方式的不同分為STARAN網(wǎng)絡(luò)和間接二進(jìn)制n方體網(wǎng)絡(luò)等。STARAN網(wǎng)絡(luò)采用級控制和部分級控制。間接二進(jìn)制n方體網(wǎng)絡(luò)采用單元控制方式。3/4/2024146例：將具有Cube0，Cube1和Cube2三種互連函數(shù)的三個單級立方體網(wǎng)串接起來構(gòu)成多級立方體STARAN網(wǎng)絡(luò)。3/4/2024147①對0～2級采用級控方式，“1”控制開關(guān)為交換方式，“0”控制開關(guān)為直通方式。當(dāng)級控信號為“101”時，輸出與輸入的對應(yīng)關(guān)系為：0—5，1—4，2—7，3—6，4—1，5—0，6—3，7—2。采用不同的級控信號，可實(shí)現(xiàn)不同的交換功能。3/4/2024148②對各級開關(guān)采用部分級控方式。例如，0級級控信號為“0”，1級級控信號為“1”，2級中I、J級控信號為“1”，K、L級控信號為“0”時，輸出與輸入的對應(yīng)關(guān)系為：0—2，1—3，2—4，3—5，4—6，5—7，6—0，7—1。實(shí)現(xiàn)了移2（mod8）功能3/4/2024149(2)多級混洗交換網(wǎng)絡(luò)多級混洗交換網(wǎng)絡(luò)又稱OMEGA網(wǎng)絡(luò)，由n級相同的網(wǎng)絡(luò)組成，每一級都包含一個全混洗拓?fù)浜碗S后一列N/2個四功能交換單元，采用單元控制方式。n級混洗交換網(wǎng)絡(luò)的互連函數(shù)可以表示成：PSE(n)＝(σ(n)ε(0))n四功能交換單元根據(jù)控制信號可分別完成恒等、交換、上播和下播功能。3/4/2024150三級混洗交換網(wǎng)絡(luò)3/4/2024151在OMEGA網(wǎng)絡(luò)中，各級的編號順序與多級立方體網(wǎng)絡(luò)正好相反。當(dāng)采用級控方式時，OMEGA網(wǎng)絡(luò)成為STARAN網(wǎng)絡(luò)的逆網(wǎng)絡(luò)。當(dāng)采用單元控制方式時，OMEGA網(wǎng)絡(luò)成為間接二進(jìn)制N方體網(wǎng)絡(luò)的逆網(wǎng)絡(luò)。OMEGA網(wǎng)絡(luò)與多級立方體網(wǎng)絡(luò)之間的差別：①前者的數(shù)據(jù)流向與后者的數(shù)據(jù)流向正好相反。②前者采用四功能交換開關(guān)，而后者采用二功能交換單元。由于OMEGA網(wǎng)絡(luò)采用四功能交換開關(guān)，因此允許同時實(shí)現(xiàn)一個入端到多個出端的連接，具有更多的靈活性。3/4/2024152例：將輸入端2連接到所有輸出端的控制信號為：C、I、J、K、L采用上播，E、F采用下播。3/4/2024153例：實(shí)現(xiàn)置換（0，7，6，4，2）（1，3）（5）的控制信號為：3/4/2024154分析：實(shí)現(xiàn)置換（06473）（15）（2）的控制信號怎么安排？阻塞出現(xiàn)：A、D、G、I、L==〉阻塞網(wǎng)絡(luò)3/4/20241553/4/2024156

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

不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其它連接。3/4/2024157(3)多級PM2I互連網(wǎng)絡(luò)多級PM2I互連網(wǎng)絡(luò)又稱為數(shù)據(jù)交換網(wǎng)絡(luò)。各級中的處理單元按PM2I互連函數(shù)進(jìn)行連接。該網(wǎng)絡(luò)由log2N+1列開關(guān)單元和log2N級互連網(wǎng)絡(luò)構(gòu)成。例：N＝8，n＝log28＝3，各級處理單元按PM2I互連函數(shù)連接起來，其中：第0級：完成PM2I±0。第1級：完成PM2I±1。第2級：完成PM2I±2。第i級的每個輸入端j都有三根連接線分別連到輸出端

j、(j＋2i)modN和(j－2i)modN。3/4/20241583/4/2024159在第2級中，因?yàn)?x＋22)mod8＝(x－22)mod8，為到同一處理單元提供了冗余通路，有利于提高可靠性。進(jìn)一步，因?yàn)閱渭塒M2I網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑為，但組成多級PM2I互連網(wǎng)絡(luò)時用了n級，所以在網(wǎng)絡(luò)中提供了冗余通路，有利于提高可靠性。3/4/2024160(4)基準(zhǔn)網(wǎng)絡(luò)基準(zhǔn)網(wǎng)絡(luò)可如下圖(a)所示遞歸生成。

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

3/4/2024161（a）遞歸構(gòu)成

3/4/2024162（b）16×16基準(zhǔn)網(wǎng)絡(luò)

3/4/20241637.3.4消息尋徑方式(略)消息傳遞機(jī)制的研究在互連網(wǎng)絡(luò)的研究中占有非常重要的地位。

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

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

3/4/20241653/4/2024166

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

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

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

二.四種尋徑方式

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

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

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

(2)存儲轉(zhuǎn)發(fā)尋徑(storeandforward)：在存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)中包是信息流的基本單位。每個結(jié)點(diǎn)有一個包緩沖區(qū)。包從源結(jié)點(diǎn)經(jīng)過一系列中間結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)。

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

存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)的時延與源和目的地之間的距離(段數(shù))成正比。第一代多計算機(jī)系統(tǒng)采用這種尋徑方式。其時延用公式表示為

T＝(L/B)×D+L/B=(D+1)×L/B。3/4/20241713/4/2024172(3)虛擬直通(virtualcutthrough)：目前有一些多計算機(jī)系統(tǒng)采用的是虛擬直通的尋徑方式。虛擬直通的尋徑方式的思想是，為了減少時延，沒有必要等到整個消息全部緩沖后再作路由選擇，只要接收到用作尋徑的消息頭部即可判斷。

其通信時延用公式表示為T=(Lh/B)×D+L/B=(Lh×D+L)/B，L