片上網(wǎng)絡(luò)交換機(jī)制的研究

集成電路技術(shù)在過去的幾十年中得到了飛速的發(fā)展，在單一芯片上可集成的晶體管數(shù)目遵循著摩爾定律不斷增加，片上通信機(jī)制也經(jīng)歷了從點(diǎn)對點(diǎn)到總線結(jié)構(gòu)的轉(zhuǎn)變。但是在實(shí)際的操作中，總線結(jié)構(gòu)也暴露出了相當(dāng)多的技術(shù)問題，比如，可擴(kuò)展性差、定時(shí)困難、可重用性不佳等，并且也不具備并行通信能力。隨著片上器件數(shù)目的進(jìn)一步增加，為了使各部件之間更好的通信，總線結(jié)構(gòu)已經(jīng)不能勝任，芯片設(shè)計(jì)者需要尋求一種新的結(jié)構(gòu)來解決片上器件互連的問題。于是，人們紛紛將目光聚焦于運(yùn)用網(wǎng)絡(luò)技術(shù)來解決芯片中器件互連的問題上，從而使片上網(wǎng)絡(luò)成為了學(xué)術(shù)界新的研究熱點(diǎn)。

對開銷和能耗上的嚴(yán)格限制是片上網(wǎng)絡(luò)與并行計(jì)算機(jī)、互聯(lián)網(wǎng)絡(luò)及計(jì)算機(jī)網(wǎng)絡(luò)的最大不同?？偟恼f來，片上網(wǎng)絡(luò)具有芯片面積受限、低時(shí)延、高吞吐和低能耗等技術(shù)要求。交換機(jī)制是影響這些參數(shù)的一個(gè)重要因素，籠統(tǒng)的說，它定義了消息在片上網(wǎng)絡(luò)中傳遞的方式，并規(guī)定了沿輸出端口將消息轉(zhuǎn)發(fā)出去的時(shí)機(jī)，其中也包含了對所傳輸消息格式的規(guī)定。路由算法的制定和路由器結(jié)構(gòu)的設(shè)計(jì)，以及死鎖、活鎖、餓死等問題都在很大程度上依賴于所選用的交換機(jī)制。所以，對片上網(wǎng)絡(luò)交換機(jī)制的分析和研究相當(dāng)重要。

片上網(wǎng)絡(luò)節(jié)點(diǎn)的一般結(jié)構(gòu)如圖1所示，資源通過網(wǎng)絡(luò)接口(RNI)連接到本地路由器上，再由路由器連入網(wǎng)絡(luò)。網(wǎng)絡(luò)分界線在網(wǎng)絡(luò)接口與本地路由器之間，網(wǎng)絡(luò)部分采用統(tǒng)一的時(shí)鐘，而資源可以根據(jù)功能的不同而采用任意的時(shí)鐘，網(wǎng)絡(luò)接口實(shí)現(xiàn)兩種時(shí)鐘的協(xié)調(diào)工作。資源一般通過網(wǎng)絡(luò)接口以分組的形式將消息注入給網(wǎng)絡(luò)，在網(wǎng)絡(luò)中數(shù)據(jù)的傳遞形式則由所選用的交換機(jī)制而定。

片上網(wǎng)絡(luò)中運(yùn)用的交換機(jī)制主要可以分為兩類：面向連接的和無連接的。面向連接的交換機(jī)制主要有電路交換，無連接的機(jī)制主要有分組交換、虛切通和蟲孔交換。本文將分別對這幾種交換機(jī)制的工作原理進(jìn)行描述，并對各種交換機(jī)制在片上網(wǎng)絡(luò)中的優(yōu)缺點(diǎn)進(jìn)行分析與比較。

2．現(xiàn)有片上網(wǎng)絡(luò)交換機(jī)制

2.1 電路交換

電路交換最早產(chǎn)生于公共交換電話網(wǎng)(PSTN)，是一種面向連接的交換機(jī)制。在開始通信之前，一般要通過一個(gè)信息頭按照一定的路由規(guī)則選路，然后建立路徑，同時(shí)預(yù)定所經(jīng)過路徑的信道資源。收端在成功收到這個(gè)信息頭后將沿原路返回一個(gè)應(yīng)答，發(fā)端收到這個(gè)應(yīng)答后便開始傳輸數(shù)據(jù)。數(shù)據(jù)部分在網(wǎng)絡(luò)中傳輸時(shí)將獨(dú)占此路徑中各段鏈路的整個(gè)帶寬，并且不需要再做路由選擇。當(dāng)通信結(jié)束后，發(fā)端向收端發(fā)出終止通信的要求，并沿路拆鏈，釋放對各段鏈路的使用權(quán)。這就是電路交換的主要工作過程，如圖2所示，白色區(qū)域代表數(shù)據(jù)。

采用面向連接的方式可以保證片上網(wǎng)絡(luò)一些特定業(yè)務(wù)的服務(wù)質(zhì)量。在多媒體業(yè)務(wù)中，消息一般數(shù)量較少，但消息較長，所以采用電路交換方式較有優(yōu)勢。因?yàn)楫?dāng)消息較長時(shí)，數(shù)據(jù)部分的傳輸時(shí)間遠(yuǎn)大于路徑建立的時(shí)間，并且由于獨(dú)占整個(gè)物理帶寬，因此可以保證高吞吐和低時(shí)延。目前已經(jīng)提出的片上網(wǎng)絡(luò)模型，如AEthereal，NOSTRUM和MANGO等都用到了這種面向連接的思想來提供有保障的服務(wù)。采用電路交換的另一個(gè)好處是不需要在路由節(jié)點(diǎn)中添加緩存資源，這可以在很大程度上減小面積。傳統(tǒng)電路交換的一個(gè)缺點(diǎn)是一條鏈路只能被一個(gè)預(yù)留通道的應(yīng)用所使用，而采用時(shí)分復(fù)用的虛電路方式可以很好的解決這個(gè)問題。這種面向連接的交換機(jī)制采用異步通信，很好的解決了片上同步問題。然而對于盡力而為的業(yè)務(wù)而言，這種面向連接的電路交換并不適用，因?yàn)楸M力業(yè)務(wù)中的消息較短，且通信較頻繁，建立路徑的時(shí)間開銷將不可容忍，同時(shí)也會消耗過多的能量。

2.2 分組交換

分組交換是先將數(shù)據(jù)完全存儲，然后進(jìn)行路由決策，最后再轉(zhuǎn)發(fā)到下一節(jié)點(diǎn)的一種交換機(jī)制。它是在片上網(wǎng)絡(luò)中最早使用的一種交換機(jī)制，片上網(wǎng)絡(luò)中的分組交換主要以分組為流控單位，每個(gè)分組的大小可以不等，并且每個(gè)分組有一個(gè)分組頭，存有源節(jié)點(diǎn)地址，目的節(jié)點(diǎn)地址以及其它一些控制信息。路由節(jié)點(diǎn)接收到一個(gè)分組后，先將整個(gè)分組存儲在緩存器中，從分組頭中獲取所需的路由信息，由路由器的路由決策單元選擇一條輸出通道后，置位交叉矩陣中的內(nèi)部連接，如果下一路由節(jié)點(diǎn)中有足夠的空間存放此分組，就將此分組轉(zhuǎn)發(fā)到下一路由節(jié)點(diǎn)。其工作原理如圖3所示。

從圖3中可以看出，分組交換的時(shí)延與跳數(shù)成正比，因此它無法很好的適應(yīng)網(wǎng)絡(luò)規(guī)模的擴(kuò)展。并且在每個(gè)路由節(jié)點(diǎn)中要提供至少一個(gè)分組大小的緩存資源，因此會使芯片面積增加。而且每存儲轉(zhuǎn)發(fā)一個(gè)分組，路由節(jié)點(diǎn)中的所有緩存器都要參與工作并消耗能量。同時(shí)，如果兩節(jié)點(diǎn)間傳輸?shù)氖嵌嗝襟w業(yè)務(wù)，則一般希望分組之間的順序不發(fā)生變化，且要求較低的抖動范圍，而由于每個(gè)分組獨(dú)立路由，不同分組在網(wǎng)絡(luò)中可能經(jīng)歷不同的路徑，因此無法保證收端接收順序與發(fā)送順序相同，也就是所謂的亂序現(xiàn)象，又由于各分組到達(dá)時(shí)間無法預(yù)測，因此又會產(chǎn)生抖動。所以分組交換不能提供有保證的服務(wù)，而只能提供盡力而為的服務(wù)。

2.3 虛切通交換

虛切通交換將分組更進(jìn)一步劃分為更小的微片(flit)，大小通常為若干個(gè)比特，并將所有的微片按順序排好，將所需的路由信息放人第一個(gè)微片中(稱作頭微片，后續(xù)微片稱為數(shù)據(jù)微片)。由于路由信息只包含于頭微片中，所以路由節(jié)點(diǎn)沒有必要等整個(gè)分組都接收完以后再進(jìn)行轉(zhuǎn)發(fā)。在無阻塞的情況下，路由節(jié)點(diǎn)收到頭微片后，從中讀取路由信息，然后由路由決策單元負(fù)責(zé)選路，如果輸出通道空閑，則將頭微片轉(zhuǎn)發(fā)出去，后續(xù)微片緊隨頭微片向前路由，從而大大縮小了分組交換的時(shí)延。

當(dāng)頭微片所請求的輸出通道全忙時(shí)，頭微片就地緩存在中間節(jié)點(diǎn)，隨后的數(shù)據(jù)微片也依次前往并緩存在該節(jié)點(diǎn)中，如果阻塞的時(shí)間足夠長，則整個(gè)分組的微片都將存放在該中間節(jié)點(diǎn)中，因此像分組交換一樣，中間節(jié)點(diǎn)也要提供至少一個(gè)分組大小的緩存資源。

雖然運(yùn)用虛切通和分組交換的路由節(jié)點(diǎn)緩存器大小相同，但運(yùn)用虛切通交換機(jī)制的芯片面積要小于運(yùn)用分組交換的芯片面積。這是因?yàn)榉纸M交換需要“整存整取”，所以在路由器中需要加入一個(gè)復(fù)雜的分組結(jié)束探測裝置來接收變長度的分組。在沒有發(fā)生完全阻塞的情況下，虛切通交換只激活一個(gè)或幾個(gè)微片大小的緩存資源，而分組交換要激活全部的緩存資源，因此在吞吐量相同的情況下，虛切通機(jī)制的能耗低于分組交換。

2.4 蟲孔交換

蟲孔交換是當(dāng)今片上網(wǎng)絡(luò)中的主流交換機(jī)制。它和虛切通交換的基本思想大體相同，只是二者在發(fā)生阻塞時(shí)所表現(xiàn)出的行為不同。在蟲孔交換中，微片的種類分為頭微片，數(shù)據(jù)微片和尾片，并且允許一個(gè)分組只由一個(gè)微片組成。

當(dāng)頭微片發(fā)生阻塞時(shí)，分組中的所有微片都將停止前進(jìn)，也就是說發(fā)生阻塞時(shí)頭微片緩存在當(dāng)前節(jié)點(diǎn)，數(shù)據(jù)微片就地緩存在其后的若干個(gè)中間節(jié)點(diǎn)中。每個(gè)路由節(jié)點(diǎn)只需提供一個(gè)微片大小的緩存資源。在無競爭的情況下，蟲孔交換和虛切通交換的時(shí)延性能基本相同，并且可以通過在每個(gè)路由節(jié)點(diǎn)適當(dāng)增加緩存數(shù)量來進(jìn)一步提高吞吐量。優(yōu)良的時(shí)延性能、較小的緩存要求以及大吞吐量是蟲孔交換最突出的優(yōu)點(diǎn)。蟲孔交換也有自身的一些缺點(diǎn)，像分組交換一樣，蟲孔交換也是一種無連接的交換機(jī)制，不能運(yùn)用到消息較長的多媒體應(yīng)用當(dāng)中。當(dāng)發(fā)生阻塞時(shí)，蟲孔交換中的各個(gè)微片將會就地阻塞，從而使信道相關(guān)性擴(kuò)展到了多個(gè)相鄰的節(jié)點(diǎn)，并且將大大增加其它分組被阻塞的可能性，因此使死鎖問題變得更加復(fù)雜，并且在網(wǎng)絡(luò)負(fù)荷較重時(shí)，時(shí)延將變得不可預(yù)測。圖4示意了被阻微片導(dǎo)致其它分組無法前進(jìn)的例子。在圖中，分組A的頭微片被分組B的數(shù)據(jù)微片阻擋，導(dǎo)致A的所有微片就地阻塞，從而進(jìn)一步阻塞了請求2號路由器緩存資源的分組C?？梢赃\(yùn)用虛信道流控技術(shù)緩解上述阻塞問題，在一定程度上提高蟲孔交換機(jī)制的吞吐量。

為了更進(jìn)一步提高蟲孔交換的時(shí)延和吞吐性能，研究者針對片上網(wǎng)絡(luò)的特點(diǎn)又提出了一些改進(jìn)機(jī)制。其中一種較具代表性的方案是在頭微片和數(shù)據(jù)微片的傳輸期間使用不同的時(shí)鐘。由于在蟲孔交換機(jī)制中，只有頭微片通過中間節(jié)點(diǎn)時(shí)才需要進(jìn)行路由決策，而數(shù)據(jù)微片只需要簡單的跟隨前面的微片向前“蠕動”即可，也就是說這兩種動作的“節(jié)拍”是不相同的。因此可以考慮在頭微片傳輸時(shí)使用正常的時(shí)鐘，而在數(shù)據(jù)微片傳輸時(shí)使用較短的時(shí)鐘周期，其機(jī)理可用圖5加以簡單示意。

圖中上半部分是傳統(tǒng)的蟲孔交換，下半部分是使用不同時(shí)鐘的改進(jìn)的蟲孔交換。其中頭微片的大小為1，數(shù)據(jù)微片為4，共經(jīng)過4段鏈路，假設(shè)頭時(shí)鐘周期是數(shù)據(jù)時(shí)鐘的二倍，并在第三段鏈路時(shí)遇到了阻塞。從圖中可以看出，改進(jìn)型的蟲孔交換縮短了傳輸時(shí)間。

在這種機(jī)制中時(shí)延的縮短是以犧牲路由節(jié)點(diǎn)復(fù)雜度為代價(jià)的。運(yùn)用這種交換機(jī)制時(shí)，路由器需要同時(shí)提供兩個(gè)時(shí)鐘，并需要添加一個(gè)時(shí)鐘選擇器，所以在復(fù)雜度、面積和能耗性能方而都會帶來負(fù)面的影響。

還有很多研究者將面向連接的思想、虛信道和蟲孔交換結(jié)合使用。事實(shí)上在當(dāng)今提出的片上網(wǎng)絡(luò)模型中多采用這種類似于流水電路交換的綜合機(jī)制來支持有保證業(yè)務(wù)，并在多媒體業(yè)務(wù)中得到了廣泛的運(yùn)用。

3．總結(jié)

面向連接的電路交換可以很好的保證服務(wù)質(zhì)量，在傳輸消息較長的多媒體信息時(shí)可以獲得較高的吞吐和較低的時(shí)延?，F(xiàn)今提出的許多片上網(wǎng)絡(luò)模型都采用了這種面向連接的機(jī)制來提供有保證的服務(wù)。但對于盡力服務(wù)而言，普遍采用的無連接的交換方式。分組交換以分組為流控單位，在每個(gè)路由節(jié)點(diǎn)需要將分組完全存儲，做出路由判決后再進(jìn)行轉(zhuǎn)發(fā)。此種機(jī)制的缺點(diǎn)是所需的緩存器數(shù)量較多，影響了芯片的面積。為了進(jìn)一步提高時(shí)延性能，虛切通交換將分組劃分為更小的微片。在發(fā)生擁塞時(shí)，虛切通交換中的所有微片都向前存儲到頭微片被阻的中間節(jié)點(diǎn)中緩存起來。所以虛切通的路由器中也要提供和存儲轉(zhuǎn)發(fā)相同數(shù)量的緩存器。但仿真驗(yàn)證在實(shí)現(xiàn)相同吞吐量的情況下，虛切通路由器的面積和能耗性能都優(yōu)于分組交換。蟲孔交換與虛切通交換只在發(fā)生擁塞時(shí)才表現(xiàn)出不同。在沒有阻塞時(shí)，兩者都可以流水的通過網(wǎng)絡(luò)。在發(fā)生阻塞時(shí)，蟲孔交換分組中的各個(gè)微片均就地阻塞。在虛切通和蟲孔交換中，路由器之間傳遞的是微片，而路由器與網(wǎng)絡(luò)接口交換的是分組。所以路由節(jié)點(diǎn)要負(fù)責(zé)將分組分割成微片然后注入網(wǎng)絡(luò)，還要負(fù)責(zé)將微片從網(wǎng)絡(luò)中接收，并將微片組合成分組。這兩種機(jī)制都可以采用虛信道技術(shù)來進(jìn)一步提高喬吐，同時(shí)虛信道流控機(jī)制還能幫助蟲孔交換避免死鎖。通過觀察這兩種機(jī)制在阻塞時(shí)的行為可以發(fā)現(xiàn)，虛切通交換能夠更有效的利用網(wǎng)絡(luò)帶寬，因此比蟲孔交換具有更高的吞吐量，但是它需要較大的緩存資源。從性能的角度而言應(yīng)該選用虛切通交換，但是它所需要的緩存資源較大，并且也消耗更多的能量。

本文對片上網(wǎng)絡(luò)中常見的幾種交換機(jī)制的工作原理進(jìn)行了詳細(xì)的分析，并從片上網(wǎng)絡(luò)特有的限制的角度對這幾種交換機(jī)制進(jìn)行了分析與比較，最后對這幾種交換機(jī)制的優(yōu)缺點(diǎn)進(jìn)行了總結(jié)。