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

　　1．引言

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

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

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

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

　　2．現有片上網(wǎng)絡(luò )交換機制

　　2.1 電路交換

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

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

　　2.2 分組交換

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

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

　　2.3 虛切通交換

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

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

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

　　2.4 蟲(chóng)孔交換

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

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

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

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

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

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

　　3．總結

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

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