片上網絡交換機制的研究

　　1．引言

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

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

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

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

　　2．現有片上網絡交換機制

　　2.1 電路交換

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

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

　　2.2 分組交換

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

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

　　2.3 虛切通交換

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

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

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

　　2.4 蟲孔交換

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

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

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

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

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

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

　　3．總結

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

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