第 7 章 并行處理技術(shù)

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

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

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

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

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

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

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

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

F=(C,R)描述了互連網(wǎng)絡(luò)及參數(shù)這種描述模型為評(píng)價(jià)不同的陣列機(jī)結(jié)構(gòu)提供了比較基礎(chǔ)。2/2/202320計(jì)算機(jī)的操作特性描述如MasParMP-1計(jì)算機(jī)：(1)PE數(shù)N＝1024至16384。PE數(shù)目與機(jī)器配置有關(guān)。

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

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

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

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

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

2/2/2023242/2/202325LDAALPHA

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

ADRN

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

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

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

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

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

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

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

2/2/202334技術(shù)特點(diǎn)

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

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

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

2/2/202336主要技術(shù)指標(biāo)

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

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

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

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

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

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

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

，字長(zhǎng)64位，單精度浮點(diǎn)運(yùn)算速度為80Mflops，雙精度為60Mflops，標(biāo)量計(jì)算速度為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)處理器。在所有的計(jì)算節(jié)點(diǎn)上運(yùn)行OS與用戶程序。

2/2/202342（3）服務(wù)節(jié)點(diǎn)：服務(wù)節(jié)點(diǎn)用于管理系統(tǒng)資源，它是一臺(tái)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個(gè)服務(wù)節(jié)點(diǎn)，兩者可使用共享系統(tǒng)資源表的方法協(xié)同工作。

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

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

2/2/202345（6）前端機(jī)：曙光-1000用戶工作平臺(tái)是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)的計(jì)算服務(wù)器，在前端機(jī)上用戶程序被編輯、編譯（使用C和Fortran77i860交叉編譯器）、鏈接和查錯(cuò)，當(dāng)編譯成功后，應(yīng)用程序的目標(biāo)代碼通過(guò)以太網(wǎng)傳到服務(wù)節(jié)點(diǎn)；然后由服務(wù)節(jié)點(diǎn)發(fā)往計(jì)算節(jié)點(diǎn)；最終的計(jì)算結(jié)果由前端機(jī)顯示輸出。

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

（1）操作系統(tǒng)：曙光-1000的操作系統(tǒng)是基于Unix的分布操作系統(tǒng)。在計(jì)算節(jié)點(diǎn)上運(yùn)行微核操作系統(tǒng)，支持虛擬存儲(chǔ)管理、自陷處理、作業(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)與計(jì)算節(jié)點(diǎn)具有相同的消息傳遞接口。系統(tǒng)執(zhí)行帶有流控的消息傳遞協(xié)議。

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

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

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

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

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

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

2/2/202352設(shè)計(jì)準(zhǔn)則

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

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

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

2/2/202355體系結(jié)構(gòu)

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

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

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

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

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

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

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

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

2/2/202364（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)是否正常，包括偵測(cè)和交換心跳信息；資源組服務(wù)就是定義節(jié)點(diǎn)和應(yīng)用程序、系統(tǒng)資源（如IP）屬于一個(gè)故障切換資源組，通常該組包括那些相關(guān)的應(yīng)用服務(wù)員；通知服務(wù)就是在組的結(jié)構(gòu)和節(jié)點(diǎn)狀態(tài)發(fā)生了變化時(shí)通知組內(nèi)成員；恢復(fù)服務(wù)提供了當(dāng)組內(nèi)結(jié)構(gòu)和節(jié)點(diǎn)狀態(tài)發(fā)生變化時(shí)，當(dāng)前組中備份節(jié)點(diǎn)恢復(fù)進(jìn)程的啟動(dòng)機(jī)制，即故障切換（Takeover）。這些服務(wù)是由運(yùn)行在節(jié)點(diǎn)上的HA守護(hù)進(jìn)程（Daemon）所實(shí)現(xiàn)的。

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

2/2/202367（5）系統(tǒng)管理：訪問(wèn)曙光-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)控制臺(tái)上進(jìn)行，它是一臺(tái)獨(dú)立的天演系列工作站，與系統(tǒng)中每一機(jī)柜相連，用戶可從網(wǎng)絡(luò)的任何一個(gè)地方登錄到控制臺(tái)；系統(tǒng)管理軟件使用基于SNMP協(xié)議的客戶/服務(wù)方式來(lái)從控制臺(tái)啟動(dòng)系統(tǒng)管理命令，基于JAVA的圖形化界面用于確定在哪一個(gè)節(jié)點(diǎn)上進(jìn)行操作、修改和收集節(jié)點(diǎn)應(yīng)答；硬件監(jiān)控軟件使得系統(tǒng)員可以監(jiān)控曙光-2000系統(tǒng)的硬件狀態(tài)。

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

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

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

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)網(wǎng)，而高維二元n-立方體則稱為超立方體。用網(wǎng)絡(luò)折疊的方法可避免環(huán)網(wǎng)中長(zhǎng)的端繞連接，如圖所示。2/2/2023105靜態(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值很大時(shí)其結(jié)點(diǎn)度也太高。

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

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

2/2/20231112/2/2023112由于使用切通選路技術(shù)，時(shí)延可減少到20微秒。使用2或4端口線卡可構(gòu)造22端口的交叉開(kāi)關(guān)?？傊д组_(kāi)關(guān)/FDDI能提供高達(dá)3.6Gbps的帶寬（是以太網(wǎng)的360倍），它已用在Digital的TruCluster中。千兆開(kāi)關(guān)/FDDI是一種通用的網(wǎng)絡(luò)產(chǎn)品，可用于任意以FDDI環(huán)連接的系統(tǒng)中，它是基于交叉開(kāi)關(guān)設(shè)計(jì)的實(shí)現(xiàn)節(jié)點(diǎn)間通信的一個(gè)很好例子。2/2/2023113常用的單級(jí)互連網(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位變反就可得到對(duì)應(yīng)的輸出排列。也寫成2/2/2023114交換互連網(wǎng)絡(luò)共有n＝log2N種互連函數(shù)。在單級(jí)交換互連網(wǎng)絡(luò)中，從一個(gè)結(jié)點(diǎn)到任何另一個(gè)結(jié)點(diǎn)所需的最短距離(即網(wǎng)絡(luò)直徑)為n。當(dāng)N＝8，n＝log28＝3時(shí)，交換互連網(wǎng)絡(luò)就是常用的立方體互連網(wǎng)絡(luò)。立方體中的每一個(gè)頂點(diǎn)代表一個(gè)處理單元。8個(gè)PE的坐標(biāo)地址可用3位二進(jìn)制代碼表示。它的三個(gè)互連函數(shù)為：2/2/2023115

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

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

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

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

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

＝(b0bn－2…

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

子蝶式(subbutterfly)B(k)

最低k位的高低位互換

超蝶式(superbutterfly)B(k)

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

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

0≤x≤N例：N＝8，m＝2的移數(shù)互連01234567012345672/2/20231276.PM2I互連網(wǎng)絡(luò)PM2I互連網(wǎng)絡(luò)是“加減2i”單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱，又稱循環(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個(gè)互連函數(shù)。2/2/2023128例：N＝8時(shí)，PM2＋0，PM2＋1和PM2＋2互連網(wǎng)絡(luò)2/2/202312901234567PM2＋001234567PM2＋101234567PM2±22/2/2023130只需將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相連。2/2/20231317.混洗交換互連網(wǎng)絡(luò)混洗交換互連網(wǎng)絡(luò)由全混洗Shuffle(x)和交換網(wǎng)絡(luò)Exchange0(x)復(fù)合而成。也寫成2/2/20231327例：N＝8時(shí)的混洗交換互連網(wǎng)絡(luò)01234560000010100111001011101110000010100111001011101112/2/2023133N＝8時(shí)的混洗交換互連網(wǎng)絡(luò)可以看作由Cube0交換函數(shù)和全混洗函數(shù)復(fù)合得到。其中最遠(yuǎn)的全“0”和全“1”兩個(gè)PE間的連接需要n次交換和n－1次混洗才能實(shí)現(xiàn)，所以的最大距離為2n－1。2/2/2023134三種基本單級(jí)網(wǎng)絡(luò)的比較互連函數(shù)個(gè)數(shù)網(wǎng)絡(luò)最大距離（網(wǎng)絡(luò)直徑）PM2I2n－1交換nn混洗交換22n－12/2/2023135互連函數(shù)舉例假設(shè)16個(gè)處理機(jī)的編號(hào)分別為0、1、…、15，采用單級(jí)互連網(wǎng)絡(luò)?；ミB函數(shù)分別為：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第12號(hào)處理機(jī)分別與哪一個(gè)處理機(jī)相連？2/2/2023136解：16個(gè)處理器，需4位二進(jìn)制表示，故：(12)10=(1100)2

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

4號(hào)處理機(jī)

(2)PM2+3，

(12+8)MOD16=4，

4號(hào)處理機(jī)

(3)PM2-0，

12–1=11，

11號(hào)處理機(jī)

(4)Shuffle，

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

9號(hào)處理機(jī)

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

(6)Reversal，

1100的位序反過(guò)來(lái)為0011,

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

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

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

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

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

2/2/2023161（a）遞歸構(gòu)成

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

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

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

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

2/2/20231652/2/2023166

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

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

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

二.四種尋徑方式

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

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

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

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

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

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

其通信時(shí)延用公式表示為T=(Lh/B)×D+L/B=(Lh×D+L)/B，Lh是消息的尋徑頭部的長(zhǎng)度。一般來(lái)說(shuō)，L>>Lh×D，所以公式可以近似為T＝L/B，可以看到此時(shí)通信時(shí)延與結(jié)點(diǎn)數(shù)無(wú)關(guān)，這相對(duì)于存儲(chǔ)轉(zhuǎn)發(fā)的尋徑方式來(lái)說(shuō)是一個(gè)非常大的改進(jìn)。2/2/2023173

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

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

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

用頭片直接開(kāi)辟一條以輸入鏈路到輸出鏈路的路徑的方法來(lái)進(jìn)行操作。每個(gè)消息中的片以流水方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”。每個(gè)片相當(dāng)于蟲(chóng)的一個(gè)節(jié)，“蠕動(dòng)”是以節(jié)為單位順序地向前爬行。

當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片的尋徑消息立即做出路由選擇：

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

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

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

其中，Lf是片的長(zhǎng)度，Tf是片經(jīng)過(guò)一個(gè)結(jié)點(diǎn)所需時(shí)間。

一般來(lái)說(shuō)，L>>Lf×D，所以公式可以近似為：T＝L/B，可以看到此時(shí)通信時(shí)延也與結(jié)點(diǎn)數(shù)無(wú)關(guān)。

(5)蟲(chóng)蝕尋徑的優(yōu)點(diǎn)：

(a)每個(gè)結(jié)點(diǎn)的緩沖區(qū)較小，易于VLSI實(shí)現(xiàn)。2/2/2023180

(b)較低的網(wǎng)絡(luò)傳輸時(shí)延。所有的片以流水方式向前傳輸，采用了時(shí)間并行性。而存儲(chǔ)轉(zhuǎn)發(fā)方式的消息包整個(gè)地從一個(gè)結(jié)點(diǎn)“跳”到另一個(gè)結(jié)點(diǎn)，通道的使用是串行的，所以它的傳輸時(shí)延基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x。蟲(chóng)蝕尋徑方式的網(wǎng)絡(luò)傳輸時(shí)延正比于消息包的長(zhǎng)度，傳輸距離對(duì)它的影響很小。

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

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