中共湖南省委黨校湖南行政學(xué)院彭勁杰 (原名彭孟良)
1引言
通過(guò)高性能互連系統(tǒng)將多個(gè)CPU構(gòu)成并行計(jì)算機(jī)集群系統(tǒng)，是獲得高性能計(jì)算的有效途徑。為了提高互連系統(tǒng)的性能，人們從許多方面進(jìn)行了大量研究，如互連硬件設(shè)備性能、并行系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由算法等等。由于硬件性能受限于當(dāng)前的工藝水平，且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究非常成熟，路由算法就成了研究熱點(diǎn)。
在路由的實(shí)現(xiàn)過(guò)程中，互連網(wǎng)絡(luò)所采用的信息交換技術(shù)決定了信息可以沿著路徑傳輸?shù)难訒r(shí)和帶寬。因此信息交換技術(shù)是反映互聯(lián)網(wǎng)性能的一個(gè)重要因素。最基本的信息交換技術(shù)有電路交換（CircuitSwitch）和報(bào)文交換（PacketSwitch）兩種，其他許多改進(jìn)方法都是針對(duì)這兩種技術(shù)的性能改善方法，比如蟲(chóng)孔交換（WormholeSwitch）是對(duì)報(bào)文交換中有的路徑上信息單元不足一個(gè)報(bào)文；虛跨步交換（Virtual Cut-through Switch）是鑒于電路交換與報(bào)文交換之間的技術(shù)。這些技術(shù)的改進(jìn)是針對(duì)物理鏈路的要求而來(lái)的，而不是針對(duì)應(yīng)用特點(diǎn)的延時(shí)與帶寬需求進(jìn)行的。
從應(yīng)用的角度來(lái)看，一個(gè)集群系統(tǒng)上往往運(yùn)行了多種應(yīng)用程序。不同應(yīng)用的數(shù)據(jù)有不同的特點(diǎn)，對(duì)信息交換的性能有不同的要求，比如有的要求是低延時(shí)，而有的要求高帶寬，這就要求有與之相適應(yīng)的信息交換技術(shù)。電路交換與報(bào)文交換二者有不同的特點(diǎn)，任何一種方法都不能同時(shí)滿(mǎn)足所有應(yīng)用。為此，需要研究與多種應(yīng)用需求相適應(yīng)的信息交換技術(shù)。
為了提高信息交換對(duì)應(yīng)用需求的適應(yīng)性，文獻(xiàn)[2]提出了一種基于高性能輸入隊(duì)列的交換技術(shù)。該技術(shù)通過(guò)改進(jìn)鏈路上設(shè)備的緩沖區(qū)來(lái)提高系統(tǒng)的交換性能，其優(yōu)點(diǎn)是能適應(yīng)一定范圍內(nèi)的信息提供高帶寬低延時(shí)的服務(wù)，其缺點(diǎn)是需要增設(shè)緩沖區(qū)，對(duì)底層進(jìn)行修改。但是不同應(yīng)用的QoS標(biāo)準(zhǔn)不同，其方法只能針對(duì)應(yīng)用的低延時(shí)或高帶寬的多種要求同時(shí)進(jìn)行優(yōu)化。本文提出自適應(yīng)信息交換技術(shù)的思想，是為了提高網(wǎng)絡(luò)的信息交換性能并且可以滿(mǎn)足不同應(yīng)用的多種需求。
2傳統(tǒng)的信息交換技術(shù)
2.1電路交換
在數(shù)據(jù)傳輸前要在源和目的之間首先建立一條物理路徑，然后在這條路徑上一次將數(shù)據(jù)傳送完，再釋放該物理路徑。
其中物理路徑的建立是通過(guò)向網(wǎng)絡(luò)注入路由頭微片來(lái)實(shí)現(xiàn)的（這個(gè)路由頭微片包括目的地址和其他控制信息，路由探測(cè)頭向目的前進(jìn)，在通過(guò)中間路由器傳輸?shù)耐瑫r(shí)保留物理鏈路。當(dāng)探測(cè)頭到達(dá)目的時(shí)，就建立了一條完整的路徑，并向源結(jié)點(diǎn)返回應(yīng)答）。路徑建立后，消息內(nèi)容就可以以硬件路徑的整個(gè)帶寬傳送。
電路交換的優(yōu)點(diǎn)是：①簡(jiǎn)單，就類(lèi)似于源與目的之間建立一條物理專(zhuān)線；②傳送帶寬高，因?yàn)槠鋫魉涂梢哉碱I(lǐng)整個(gè)帶寬性能。當(dāng)應(yīng)用中需要傳送的消息很長(zhǎng)時(shí)（消息傳輸時(shí)間遠(yuǎn)遠(yuǎn)大于路徑建立時(shí)間），這種交換技術(shù)非常有效。
電路交換的缺點(diǎn)是：①路徑建立延時(shí)很長(zhǎng)。路徑的建立要求路徑的每個(gè)器件都空閑；②整個(gè)消息發(fā)送期間都要占領(lǐng)該物理路徑，有可能阻塞其他的消息，影響網(wǎng)絡(luò)的整體利用率。
2.2報(bào)文交換
針對(duì)電路交換要占用整個(gè)路徑的缺點(diǎn)，是將消息劃分成固定長(zhǎng)度的許多報(bào)文，每個(gè)報(bào)文從源結(jié)點(diǎn)到目的結(jié)點(diǎn)獨(dú)立路由，報(bào)文在向下一個(gè)結(jié)點(diǎn)轉(zhuǎn)發(fā)之前完全緩沖在每個(gè)中間結(jié)點(diǎn)，不需要占領(lǐng)獨(dú)立的物理通道。為了便于控制，每個(gè)報(bào)文的前幾個(gè)字節(jié)包含路由和控制信息，稱(chēng)作報(bào)文頭。中間路由器析取頭信息，確定報(bào)文轉(zhuǎn)發(fā)的輸出鏈路。
報(bào)文交換的優(yōu)點(diǎn)是：①不需要建立物理路徑，消息傳送的延時(shí)小，對(duì)消息較短和延時(shí)受限的應(yīng)用來(lái)說(shuō)很有意義；②在報(bào)文交換中，只要某段預(yù)留路徑空閑有效的時(shí)間段，有數(shù)據(jù)需要傳輸時(shí)通信鏈路就可以充分利用，器件的并行性較好，網(wǎng)絡(luò)的利用率高。
報(bào)文交換的缺點(diǎn)是：①消息需要進(jìn)行分片，會(huì)帶來(lái)額外開(kāi)銷(xiāo)；②由于每個(gè)消息片獨(dú)立路由，一條消息的多個(gè)報(bào)文會(huì)出現(xiàn)亂序等現(xiàn)象，整個(gè)傳送的完成需要等待傳送最慢的消息片；③消息傳送需要有超時(shí)機(jī)制對(duì)是否傳送完成進(jìn)行判斷，和報(bào)文重復(fù)丟棄等復(fù)雜情況進(jìn)行管理。
3.自適應(yīng)信息交換
不同的應(yīng)用對(duì)消息交換有不同的要求。比如在集群系統(tǒng)上運(yùn)行科學(xué)計(jì)算中的障礙同步操作（Barrie），消息較短，操作的延時(shí)直接決定了多機(jī)并發(fā)工作的性能。這種情況就是延時(shí)受限。而對(duì)于數(shù)據(jù)挖掘應(yīng)用，數(shù)據(jù)庫(kù)服務(wù)器需要將某一維的所有數(shù)據(jù)進(jìn)行傳送，數(shù)據(jù)量大，傳送的及時(shí)完成對(duì)應(yīng)用服務(wù)性能有直接影響。這種需要高帶寬的應(yīng)用就是帶寬受限。一個(gè)集群系統(tǒng)同時(shí)運(yùn)行這些應(yīng)用，就要求網(wǎng)絡(luò)交換技術(shù)具有一定的適應(yīng)性。
3.1兩種交換方式的互補(bǔ)性
經(jīng)分析，電路交換的優(yōu)點(diǎn)是帶寬高，但是建立鏈路時(shí)間太長(zhǎng)時(shí)，同樣會(huì)影響數(shù)據(jù)傳遞的效果；在報(bào)文交換機(jī)制中，每個(gè)片會(huì)帶來(lái)額外的數(shù)據(jù)包處理開(kāi)銷(xiāo)等，如果這些開(kāi)銷(xiāo)太大，同樣會(huì)引起系統(tǒng)的整體性能。二者結(jié)合起來(lái)，則有較理想的效果。
電路交換與報(bào)文交換相互補(bǔ)的方法是指對(duì)于一個(gè)消息，如果能很快建立一條物理鏈路，則可以選擇進(jìn)行電路交換；如果在鏈路上的某幾個(gè)結(jié)點(diǎn)之間能很快建立一條物理鏈路，則這些結(jié)點(diǎn)間能進(jìn)行電路交換，而路徑上的其余結(jié)點(diǎn)間采用報(bào)文交換。
互補(bǔ)交換是自適應(yīng)交換中的一種交換方式。在互補(bǔ)交換中，只需要少量的鏈路建立時(shí)間。
3.2自適應(yīng)信息交換思想
所謂自適應(yīng)信息交換技術(shù)就是根據(jù)實(shí)際應(yīng)用的需要，自適應(yīng)地選擇數(shù)據(jù)交換方法，如算法一所示。算法一中，對(duì)有延時(shí)要求的短消息，自適應(yīng)信息交換會(huì)選擇報(bào)文交換機(jī)制進(jìn)行數(shù)據(jù)傳遞；而對(duì)有帶寬要求的長(zhǎng)消息且比較易于建立鏈路，自適應(yīng)信息交換會(huì)選擇電路交換；對(duì)鏈路建立時(shí)間很長(zhǎng)的，自適應(yīng)信息交換會(huì)選擇電路交換與報(bào)文交換互補(bǔ)的方式。
輸入：目的結(jié)點(diǎn)T、源結(jié)點(diǎn)S、數(shù)據(jù)信息M、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、各結(jié)點(diǎn)間鏈路建立的統(tǒng)計(jì)時(shí)間信息交換的延時(shí)
輸出：信息交換方法
算法開(kāi)始：如果M短且有 要求延時(shí)短， 則輸出 報(bào)文交換 如果 T與S間的鏈路建立時(shí)間 ≤ 閾值， 則 輸出 電路交換 輸出 互補(bǔ)交換
算法結(jié)束
算法一信息交換機(jī)制的選擇算法
在算法一中，需要直到各結(jié)點(diǎn)之間路由鏈路的建立時(shí)間統(tǒng)計(jì)情況。這些統(tǒng)計(jì)情況是一些歷史信息，并且根據(jù)每次鏈路的建立情況進(jìn)行修改。
3.3自適應(yīng)信息交換機(jī)制
分別設(shè)置數(shù)據(jù)信息量的信息交換下閥值x1和上閥值x2；
分別設(shè)置數(shù)據(jù)信息量的信息交換下閥值y1和上閥值y2。
設(shè)置數(shù)據(jù)記憶長(zhǎng)度N。
近期歷史記錄中采用電路交換的N個(gè)數(shù)據(jù)信息，記為n1i(i=1,2,…,N)，其信息量大小為s1i，完成信息交換的延時(shí)為t1i。
近期歷史記錄中提取采用電路交換的N個(gè)數(shù)據(jù)信息，記為n2j(j=1,2,…,N)，其信息量大小為s2j，完成信息交換的延時(shí)為t2j。
具體算法實(shí)現(xiàn)方式如下：
如果數(shù)據(jù)信息位于灰色區(qū)域，采用電路交換；
否則，
如果數(shù)據(jù)信息位于綠色區(qū)域，采用報(bào)文交換
否則，
如果可接受延時(shí)/數(shù)據(jù)信息量，采用報(bào)文交換
否則，采用電路交換
具體算法計(jì)算公式：(略)
4結(jié)束語(yǔ)
針對(duì)當(dāng)今信息交換不能滿(mǎn)足集群中多種應(yīng)用需求，本文研究提出了自適應(yīng)交換的思想。在研究中提出了互補(bǔ)交換的思想，并給出了自適應(yīng)交換選擇的算法。今后的工作需要將該思想進(jìn)行工程實(shí)現(xiàn)和驗(yàn)證。
