摘?? 要: 提出了一種硬件實現(xiàn)的優(yōu)先隊列算法,可以在常量時間內完成插入和解壓操作,達到OC3072線速要求,。

　　關鍵詞: 常量時間的優(yōu)先隊列? OC3072線速? QoS

?

　　隨著網(wǎng)絡的高速發(fā)展,用戶對網(wǎng)絡質量的需求也越來越高,調查顯示用戶對網(wǎng)絡的抱怨主要體現(xiàn)為速度慢,質量沒有保證,。要解決這個問題需要對網(wǎng)絡路由節(jié)點進行QoS(Quality of Service)改造,完善已有的QoS功能,用新的具有QoS能力的路由器逐步替代老一代產(chǎn)品。目前IETF等組織提出的QoS方案有2類,即路由器節(jié)點的QoS和路由器網(wǎng)絡的QoS(如MPLS和Traffic Engineering)。路由器節(jié)點的QoS還可以細分為公平的需求和不公平的需求,。前者主要包括各種公平調度算法,后者包括公平調度算法的不公平配置、BES,、RVSP,、IS和DS算法。節(jié)點QoS中的很多算法(如調度算法和DS算法)最終都歸結為傳統(tǒng)的優(yōu)先隊列算法,。由于純軟件實現(xiàn)的優(yōu)先隊列算法不能滿足高速路由器的需求,本文提出了一種硬件支持的常量時間的優(yōu)先隊列存取算法,能夠達到OC3072(即160Gbps)線速要求,。

1? 相關工作

　　目前有2類常量時間的優(yōu)先隊列算法:(1)基于通用內存的算法,如P-Heap算法。(2)基于專用內存的算法,這種算法起源于vEB(van Emde Boas)優(yōu)先隊列結構,一般被稱作STT(Split Tagged Tree)算法,。P-Heap算法提出了一種稱之為P-Heap的數(shù)據(jù)結構:每次插入和解壓至少經(jīng)過3次內存操作,而且它使用流水線隔行工作,相當于進行6次內存操作才能獲得1次結果,。這種機制是提高效率的主要瓶頸,最高支持OC192(即10Gbps)線速。STT算法得益于vEB提出的優(yōu)秀結構,它的速度足夠支持OC768(即40Gbps),但它必須采用專門定制的內存,這種內存因為產(chǎn)量很小而導致成本無法降低,。受到P-Heap的啟發(fā),提出一種B-Heap結構,單一隊列可以實現(xiàn)OC768線速,。如果把4個B-Heap優(yōu)先隊列組合起來,則可以滿足OC3072線速的要求。

2? B-Heap的工作原理

2.1 基本操作

　　硬件B-Heap的操作特點是在各個分層之間使用流水線工作,插入元素的同時也完成了解壓元素的操作,。這一點和P-Heap有所不同,雖然P-Heap也是流水線工作,但需要隔層操作,。假設插入的元素序列為{0,3,4,2,

6,8,1,9,1,7,5,3,2,8,0,-1,-1,-1,-1,2,-1,5,3,9},則初始階段的插入解壓過程如圖1所示,對應前8個元素;有空閑情況下的插入解壓過程如圖2所示,對應最后8個元素,說明流量減小時插入占位數(shù)據(jù)-1的過程;255是-1的一種表達方式,其中涉及到比較模式切換問題,中間8個元素的插入解壓類似于圖1的無空閑情況下的操作,。上述3個過程雖然各自代表實際操作中的各種情況,但是三者之間設計成連續(xù)的,便于觀察。元素從下向上流經(jīng)該結構,方框代表針對堆結構每一層的數(shù)據(jù)寄存器,最下端的寄存器為插入輸入,灰色寄存器為解壓輸出,。

?

?

　　主要的工作機制是每次操作選擇一條最小路徑,每一次操作按最小路徑進行,比較后進行流水線上移,。這里的最小路徑是指從上到下依次選擇上層入選節(jié)點的子節(jié)點中較小的元素所構成的路徑。其中有2種特殊情況:(1)最上面一層只有一個節(jié)點,因此入選,。(2)如果子節(jié)點中元素大小相等則左手子節(jié)點入選,。每一層所對應的寄存器作為該層的比較輸入,與該層最小路徑上的元素作比較,將較小者放入上一層寄存器的緩沖器。每層寄存器都包括一個寄存器的緩沖器,。寄存器讀取前打開,寫入前關閉,以滿足流水線操作時的同步要求,。規(guī)定當前沒有輸入時用-1模擬1個輸入,即所謂的空閑情況。對最下面一層的輸入寄存器為-1的狀態(tài)需要進行一次特殊的操作,即結構中所有比較器進行模式切換,將-1認為是與255進行比較,這樣有助于空閑情況下將原來元素按從小到大的順序解壓出來,。在具體實現(xiàn)中將-1認為是255的模式切換很容易辦到,因為對于一個有符號字節(jié)-1,如果用無符號字節(jié)對其進行識別就是255,。有了這種機制,在空閑情況下也可以保證空閑之前進入堆中的數(shù)據(jù)能夠正常流出。輸出結果顯示,圖中的B-Heap結構實現(xiàn)了排隊空間n=8的在線優(yōu)先隊列,。

2.2 最小路徑查找

　　通過觀察可以發(fā)現(xiàn),每次操作都需要查找最小路徑,這一環(huán)節(jié)是B-Heap算法進行高速處理的關鍵,。查找的最小路徑如圖3所示。結構中每一層節(jié)點的地址可以表示為從0開始的二進制數(shù),例如從上向下第4層的每一次操作的輸入地址可表示為000,001,010,011,100,101,110,111,。B-Heap的狀態(tài)可以表示為X|XX|XXXX|……,其中X為0或1,。0表示左手節(jié)點小于右手節(jié)點,1表示左手節(jié)點大于右手節(jié)點,|為層分隔符,區(qū)別從上到下每一層的狀態(tài)。則圖3中B-Heap的狀態(tài)可表示為,每次操作在每一層中最多修改1bit,。查找最小路徑即求出從狀態(tài)到每一層輸入地址的轉換結構,。下面介紹如何設計該轉換:由于每一層使用不同的內存,屬于并行操作,因此可以在上一次操作結束時得到所有的狀態(tài)位,而每次僅僅修改1bit,這樣不會造成較大的總線寬度硬件耗費。要從狀態(tài)中找出最小路徑可以通過一個以狀態(tài)為輸入,。多層地址為輸出的地址編碼器來完成,。如果采用ASIC,則可以使用足夠的寄存器存儲狀態(tài),從而完全在片內實現(xiàn)編碼器,對外只保留很小的總線寬度,能滿足每層只修改1bit即可。

?

?

　　內部邏輯類似于前綴樹,實際上是在前綴樹結構基礎上簡化了一半的狀態(tài)耗費,。定義每個二叉樹節(jié)點的左,、右子節(jié)點的比較結果為b,稱為路徑選擇變量。b是一個布爾量,為0表示左手子節(jié)點的值小于右手子節(jié)點的值,為1則恰好相反,。從二叉樹的根開始,判斷路徑選擇變量,如果為1,則選擇左子樹;如果為0,則選擇右子樹,。照此向下推進,直到葉節(jié)點為止,所形成的路徑就是需要尋找的最小路徑。路徑選擇變量存儲在寄存器中,每個變量占用1bit,。因為第一層并不需要該變量,所以路徑選擇變量總共占有n/2bit,使用m個寄存器,其中m=? ,。為了區(qū)別每一層的數(shù)據(jù)寄存器數(shù)組T,這m個寄存器稱為路徑選擇寄存器。

　　使用ASIC實現(xiàn)時,判斷路徑選擇變量并選擇一條分支的時間耗費t是門級,目前的硬件工藝可以做到十幾到幾十個皮秒(ps),。整條路徑選擇的時間耗費大約為t的倍。一般情況下<20,所以整條路徑選擇的時間實現(xiàn)不會超過1ns,。輸出的每一層的地址是可以復用的,如圖3的狀態(tài)字中最小路徑對應每一層節(jié)點地址為{0,0,01,011,0111,……},上層的地址是下層地址的前綴,。由此可知第一層不需要地址,因此所有輸出數(shù)據(jù)的地址位數(shù)= ,。

　　綜上所述,B-Heap算法的一次存取要完成以下步驟。

　　(1)根據(jù)每一層的比較地址找到比較節(jié)點,打開數(shù)據(jù)寄存器數(shù)組T中每個寄存器的緩存,刷新寄存器,。(2)取出比較節(jié)點的值和本層數(shù)據(jù)寄存器中的值相比較,其中較小值寫入上一層數(shù)據(jù)寄存器的緩存,較大值寫入該節(jié)點,。同時,輸入寄存器和輸出寄存器中都有了最新值。(3)將較大值和比較節(jié)點的兄弟節(jié)點進行比較,如果左節(jié)點大于右節(jié)點,則b=1;反之,b=0,。將結果寫入路徑選擇寄存器的相應位置,。(4)將路徑選擇寄存器的值輸入路徑選擇模塊以選擇一條最小路徑。這一步由ASIC實現(xiàn),輸入n/2位,輸出位,。輸出中含有所有層的下一次比較地址,。

3? 性能評估和合并隊列

　　由于路徑選擇的時間在總的時間耗費中不占很大比重,因此B-Heap插入和解壓的時間耗費約為P-Heap的1/4。其中逐行操作比隔行操作快一倍,插入和解壓的同步進行比分別進行快一倍,。所以按照P-Heap分析所依據(jù)的內存和ASIC工藝水平,B-Heap可以達到OC768線速,。同時,可以使用4片B-Heap擴展排隊長度和操作速度,對4片子優(yōu)先隊列進行RR(Round Robin)調度可以達到OC3072線速。

4? 結束語

　　本文提出了一種硬件輔助的優(yōu)先隊列算法B-Heap,通過特殊的結構和操作策略可以達到OC3072線速,在使用普通內存的方法中優(yōu)于P-Heap算法,。B-Heap算法的主要不足是排隊長度受到寄存器的限制,例如一個1024排隊長度的B-Heap需要16個寄存器,目前的工藝完全可以承受,。但是如果排隊長度按幾何比例增長,則B-Heap的實現(xiàn)依賴于能夠集成的寄存器數(shù)目。

?

參考文獻

1?? Xipeng X,Lionel M N.Internet QoS:A Big Picture.IEEE Network,1999;(4)

2?? Bhagwan R,Lin B.Fast and Scalable Priority Queue?Architecture for Highspeed Network Switches.IEEE?Infocom,2000;(3)

3?? Brodnik A.Worst Case Constant Time Priority Queue.WCCTPQ,2000;(3)