網(wǎng)絡(luò)處理器自適應(yīng)負(fù)載均衡調(diào)度機(jī)制

摘要：對TLDP結(jié)構(gòu)網(wǎng)絡(luò)處理器的線程調(diào)度問題展開討論，設(shè)計并用硬連線實現(xiàn)了TLPD結(jié)構(gòu)的微引擎間自適應(yīng)負(fù)載均衡線程調(diào)度機(jī)制。它根據(jù)TLDP結(jié)構(gòu)內(nèi)部各個微引擎的實時負(fù)載狀態(tài)和歷史信息自動調(diào)整活動微引擎的數(shù)量，然后在被選擇的活動微引擎集合上實現(xiàn)微引擎間的動態(tài)負(fù)載均衡，最大程度地提高了TLDP結(jié)構(gòu)網(wǎng)絡(luò)處理器的分組吞吐率。通過對TLDP結(jié)構(gòu)的RTL級模型仿真說明，該機(jī)制能有效地實現(xiàn)微引擎間的實時負(fù)載均衡。

關(guān)鍵詞：網(wǎng)絡(luò)處理器； 動態(tài)調(diào)度； 負(fù)載均衡

中圖分類號：TP303文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)04－1196－03

網(wǎng)絡(luò)處理器的出現(xiàn)改變了網(wǎng)絡(luò)設(shè)備的體系結(jié)構(gòu)，已成為第五代路由器與交換機(jī)的核心器件之一。目前全球已有30多個網(wǎng)絡(luò)處理器廠商共完成了超過500個網(wǎng)絡(luò)處理器的研發(fā)。西北工業(yè)大學(xué)航空微電子中心自主設(shè)計了一款基于線程級分布式處理（thread level distributed processing，TLDP）結(jié)構(gòu)的網(wǎng)絡(luò)處理器[1]。它融合了分布式多線程結(jié)構(gòu)[2]和指令級分布式處理結(jié)構(gòu)[3]（instruction level distributed processing，ILDP）的設(shè)計思想。對于具有八個協(xié)議處理微引擎（micro－engine），并采用流水方式執(zhí)行的TLDP結(jié)構(gòu)來說，如何設(shè)計并實現(xiàn)一個有效的線程調(diào)度機(jī)制，對于有效利用整個片上資源并提高分組吞吐率是至關(guān)重要的。這包括提高各個微引擎內(nèi)部以及微引擎間的并行性。其關(guān)鍵所在是在分組處理請求的分派過程中保持微引擎間的負(fù)載均衡，防止微引擎發(fā)生相關(guān)等待或者空閑的情況。雖然通過編譯或者系統(tǒng)開發(fā)平臺的方法，如文獻(xiàn)[4，5]等也可以隱藏網(wǎng)絡(luò)處理器的硬件并行細(xì)節(jié)，降低程序員的編程復(fù)雜度，并實現(xiàn)一種宏觀上的負(fù)載均衡。但它們均屬于靜態(tài)分派機(jī)制，無法及時、準(zhǔn)確地把握各個節(jié)點的動態(tài)負(fù)載狀態(tài)。文獻(xiàn)[6]提出在并行結(jié)構(gòu)的網(wǎng)絡(luò)處理器中采用hash散列調(diào)度方式，也是一種靜態(tài)調(diào)度方式，并且難以選擇一個合理hash函數(shù)，使所有的關(guān)鍵字經(jīng)過hash變換得到的結(jié)果在任何時候都能均勻地分布在處理單元上。本文采用硬連線實現(xiàn)的動態(tài)負(fù)載均衡調(diào)度機(jī)制，最大程度地提高了TLDP結(jié)構(gòu)的分組吞吐率，并實現(xiàn)了TLDP結(jié)構(gòu)內(nèi)部的多核、多線程結(jié)構(gòu)對系統(tǒng)程序員的透明性。

1TLDP結(jié)構(gòu)網(wǎng)絡(luò)處理器

從硬件結(jié)構(gòu)上看，TLDP結(jié)構(gòu)是一種動態(tài)多線程、多核結(jié)構(gòu)，主要用于數(shù)據(jù)平面上的高速協(xié)議處理。其基本邏輯結(jié)構(gòu)如圖1所示。可以看出，TLDP將原來ILDP中的多個執(zhí)行單元替換為多個協(xié)議處理微引擎，并且采用分布式系統(tǒng)的設(shè)計思想降低了硬件設(shè)計的復(fù)雜度和系統(tǒng)程序員的編程難度。TLDP中共集成了八個微引擎，共同構(gòu)成一個簇；簇內(nèi)共享硬件加速單元和片上的共享存儲資源；各個流的狀態(tài)信息對八個微引擎都是可見的。它屬于一種緊耦合的片上分布式結(jié)構(gòu)，各個節(jié)點物理位置相距很近，同步和通信開銷相對較小。設(shè)計中基本不會遇到在傳統(tǒng)并行處理器設(shè)計中所遇到的多個處理器間極其復(fù)雜的同步和通信問題[7]。

在TLDP結(jié)構(gòu)中，由I/O處理單元如上行接收MAC或者下行交換接口處的包組裝邏輯產(chǎn)生分組處理請求并存放到請求隊列中，稱為產(chǎn)生了一個線程，直接采用加權(quán)輪轉(zhuǎn)調(diào)度策略（WRR）選擇各個請求隊列中線程進(jìn)行分派。全局調(diào)度機(jī)制根據(jù)每個微引擎單元的實時負(fù)載狀態(tài)將線程分派到各個微引擎的線程站中。每個線程站能容納12個線程，分為3組，每組4個線程。為了降低線程切換開銷，微引擎給每個線程現(xiàn)場分配了物理上獨立的數(shù)據(jù)寄存器、線程狀態(tài)寄存器、程序計數(shù)器和標(biāo)志寄存器等，所以發(fā)生線程阻塞時，其內(nèi)部寄存器文件中的內(nèi)容不會被替換出來。微引擎內(nèi)部線程調(diào)度的關(guān)鍵不是提高cache命中率，而是最大程度地挖掘線程間的并行性。局部線程調(diào)度機(jī)制完成站內(nèi)線程的調(diào)度、對當(dāng)前運行線程的掛起狀態(tài)記錄、對等待線程的喚醒及線程站的狀態(tài)統(tǒng)計等。它在組間采用輪轉(zhuǎn)調(diào)度策略，微引擎每周期切換到下一組的一個線程中執(zhí)行。這種每周期切換的方式借鑒了細(xì)粒度多線程的設(shè)計思想，為了避免同一線程連續(xù)執(zhí)行發(fā)生控制相關(guān)時導(dǎo)致的流水線氣泡現(xiàn)象，而不是為了隱藏長延時的訪存操作。分組被處理完成后，若與之相鄰的前一個分組也已經(jīng)處理完成，則將該分組的處理結(jié)果存入相對應(yīng)的線程重排序緩沖區(qū)中。線程提交單元執(zhí)行命令緩沖中的命令完成分組的編輯處理或者將分組送給高層控制平面和高層安全協(xié)議處理的數(shù)據(jù)平面。從整體上看，這是一個宏觀流水線模式。為了平衡各級之間的速度差異，在線程執(zhí)行一級使用了八個并行的協(xié)議微引擎；每個微引擎內(nèi)部采用流水線與多線程技術(shù)相結(jié)合的方式提高處理速度。每個微引擎均有一個容量為32 KB的程序存儲器，若需要支持新的網(wǎng)絡(luò)協(xié)議處理，則只需控制平面的RISC處理器下載新的處理程序到程序存儲器即可。

2關(guān)鍵因素分析

在核心主干網(wǎng)絡(luò)中，分組到達(dá)的時間間隔很小，采用軟件調(diào)度機(jī)制難以滿足實時性要求。設(shè)獲取各個微引擎的負(fù)載信息所需時間為Tci(i=0，1，2，…，N)，執(zhí)行調(diào)度決策所需時間為Tsch，完成一個分組處理請求所需平均時間為Tpro，則通過一個負(fù)載均衡調(diào)度策略實現(xiàn)有效負(fù)載均衡的前提是

Tpro>>∑Ni=1Tci+Tsch(1)

即負(fù)載的處理時間必須遠(yuǎn)大于負(fù)載信息的收集時間∑Tci和均衡調(diào)度時間Tsch之和。否則調(diào)度器進(jìn)行負(fù)載信息的收集和調(diào)度決策后，各個微引擎的狀態(tài)已經(jīng)發(fā)生了較大的變化，此時的調(diào)度結(jié)果是無效的。

根據(jù)IEEE 802.3ae提出的萬兆以太網(wǎng)標(biāo)準(zhǔn)（OC—192），對于IPv4，每個分組最小長度為64 Byte，幀前導(dǎo)符為8 Byte，幀間最小間隔為96 bit。傳送一個最小幀的時間為傳送(64+8)×8+96=672 bit所需的時間，即在帶寬為OC—192的鏈路中，最壞情況下每67.2 ns就有一個分組到達(dá)。根據(jù)式（1），采用軟件方式很難在這么短的時間內(nèi)完成微引擎負(fù)載信息的收集和分組處理請求的調(diào)度決策，可能會得到過時的調(diào)度決策。

另外，在TLDP結(jié)構(gòu)中線程粒度小，執(zhí)行線程遷移需要暫停兩個相關(guān)微引擎的處理，每次遷移需要耗費近10個處理器周期，負(fù)載遷移代價較大。在10個處理器周期內(nèi)，外部新的分組處理請求的到達(dá)概率很大，與其進(jìn)行負(fù)載遷移，還不如將新的分組處理請求調(diào)度到輕載的微引擎上。因此，在TLDP結(jié)構(gòu)上執(zhí)行負(fù)載遷移不可取。

經(jīng)過上述分析，在TLDP結(jié)構(gòu)中采用了自適應(yīng)負(fù)載均衡機(jī)制，并用硬連線實現(xiàn)。調(diào)度需要綜合考慮各個微引擎的處理能力、負(fù)載均衡、分組保序、分組處理延時等因素。此外，需要降低調(diào)度機(jī)制本身的硬件實現(xiàn)復(fù)雜度，以提高調(diào)度的效率。

3全局自適應(yīng)負(fù)載均衡調(diào)度策略

全局自適應(yīng)負(fù)載均衡調(diào)度機(jī)制包含兩部分：a)微引擎集合的選擇調(diào)度機(jī)制。根據(jù)TLDP內(nèi)部負(fù)載的當(dāng)前狀態(tài)和歷史信息自動選擇調(diào)度若干個微引擎執(zhí)行分組處理。b)微引擎集合的動態(tài)負(fù)載均衡機(jī)制。在被選擇的微引擎集合中實現(xiàn)微引擎間的實時負(fù)載均衡，處于空閑狀態(tài)的微引擎一段時間后自動進(jìn)入休眠狀態(tài)，保證微引擎間的負(fù)載均衡的同時，降低了整個TLDP結(jié)構(gòu)的功耗。

3．1微引擎集合的選擇調(diào)度機(jī)制

選擇調(diào)度邏輯根據(jù)每個線程隊列的當(dāng)前負(fù)載狀態(tài)，分組處理請求FIFO中待處理的線程數(shù)以及在最近一段時間內(nèi)所處理的分組數(shù)大小，確定當(dāng)前TLDP的整體負(fù)載大小，在輕載狀況下將系統(tǒng)中的一部分微引擎轉(zhuǎn)入低功耗狀態(tài)，它們將已分派的線程處理完成后進(jìn)入空閑狀態(tài)。當(dāng)負(fù)載增加時，立即調(diào)度啟動一個當(dāng)前被屏蔽的微引擎執(zhí)行分組處理。

其中：L(k)表示引擎k的當(dāng)前負(fù)載大小；Lsum表示所有微引擎當(dāng)前的負(fù)載大小；Act_num表示當(dāng)前處于運行狀態(tài)的微引擎數(shù)；REQnum表示分組處理請求FIFO中待處理的線程數(shù)(當(dāng)其值小于REQ_tha時，表示TLDP當(dāng)前的待處理負(fù)載輕；當(dāng)值大于REQ_thb時，表示TLDP當(dāng)前的待處理負(fù)載重，立即調(diào)度一個當(dāng)前處于空閑狀態(tài)的微引擎進(jìn)入運行狀態(tài)）；Hm表示最近一段時間（即設(shè)定的臨界調(diào)度時間）內(nèi)TLDP所處理的分組數(shù)，其值小于Act_num×H_th時，表示TLDP在過去的一段時間內(nèi)處于輕載狀態(tài)；SLL(k)表示從當(dāng)前處于運行狀態(tài)的微引擎中選出的最小負(fù)載的微引擎的函數(shù)。在硬件實現(xiàn)中，權(quán)值復(fù)位邏輯先查找線程數(shù)小于6的微引擎，將其權(quán)值復(fù)位，若不存在則繼續(xù)查找小于9的，將其權(quán)值復(fù)位，近似實現(xiàn)了函數(shù)SLL(k)的功能。W(k)表示微引擎k的權(quán)值，為0表示該微引擎被關(guān)閉，為1表示該微引擎可調(diào)度，為-1表示該微引擎處于更新狀態(tài)。硬件實現(xiàn)時，通過生成一個分派掩碼實現(xiàn)微引擎的屏蔽功能。參數(shù)Tth、REQ_tha和REQ_thb均是可編程的，在仿真時REQ_tha和REQ_thb取經(jīng)驗值，分別為FIFO容量的20%和80%。

3．2微引擎集合的動態(tài)負(fù)載均衡機(jī)制

微引擎集合的負(fù)載均衡調(diào)度邏輯在選擇調(diào)度的結(jié)果上進(jìn)行負(fù)載均衡。每個微引擎的三個線程隊列間是相互獨立的，若線程分配不合理，會導(dǎo)致某個隊列中無可調(diào)度線程而發(fā)生空轉(zhuǎn)。這里直接比較同一個集合內(nèi)多個微引擎中各個隊列的負(fù)載大小，實現(xiàn)隊列間負(fù)載均衡。每個微引擎對應(yīng)的線程站實時地對各個隊列的空閑項和線程隊列的完成度進(jìn)行統(tǒng)計，由局部線程調(diào)度邏輯在每個處理器周期對各自線程站的狀態(tài)進(jìn)行一次統(tǒng)計并進(jìn)行反饋，空閑項的個數(shù)用一個4 bit的二進(jìn)制編碼表示。實際實現(xiàn)中，因線程在微引擎中的逗留時間僅為幾個微秒，對于兩個負(fù)載相同的線程隊列之間完成度的差別不會太大。為了簡化硬件實現(xiàn)復(fù)雜度并提高優(yōu)先級排隊邏輯的處理速度，線程隊列的完成度只劃分為兩個優(yōu)先級，用一個二進(jìn)制比特位表示。線程隊列集合的負(fù)載均衡調(diào)度流程如下：

其中：C(Si)為線程隊列Si中的當(dāng)前線程數(shù)，代表其負(fù)載狀況；HT(Si)為線程隊列Si中所有非空閑線程從被分派到當(dāng)前的時間和，代表隊列Si最近一段時間內(nèi)的完成進(jìn)度，各個線程隊列的C(Si)和HT(Si)由各個微引擎內(nèi)部的局部線程調(diào)度邏輯實時統(tǒng)計并反饋到全局線程調(diào)度器中；WT(Si)為線程隊列Si的權(quán)值，其值是根據(jù)對應(yīng)的微引擎權(quán)值W(k)確定的，WT(Si)為零表示該隊列不可分配。

4調(diào)度策略的評價

在傳統(tǒng)的分布式系統(tǒng)中，通常以任務(wù)的響應(yīng)時間和所有處理節(jié)點完成任務(wù)的處理性能或者吞吐量為依據(jù)來評價其動態(tài)負(fù)載均衡調(diào)度策略的優(yōu)劣，反映了一個調(diào)度機(jī)制的調(diào)度質(zhì)量。TLDP結(jié)構(gòu)位于網(wǎng)絡(luò)處理器的數(shù)據(jù)平面上，其功能是快速地完成每個分組的解析和轉(zhuǎn)發(fā)處理，分組吞吐率代表TLDP的分組處理性能或吞吐量。

本文建立了TLDP結(jié)構(gòu)的RTL級模型，對各個微引擎在運行時的利用率也進(jìn)行了統(tǒng)計分析，通過觀察每個微引擎利用率的差別大小變化可判斷其負(fù)載均衡調(diào)度策略的優(yōu)劣。其中：數(shù)據(jù)分組流采用NPF提供的數(shù)據(jù)包產(chǎn)生腳本程序生成；協(xié)議處理程序根據(jù)網(wǎng)絡(luò)處理器論壇提供的IPv4和IPv6的測試基準(zhǔn)要求以及RFC 894、RFC 2464、RFC 1812和RFC 2460的協(xié)議規(guī)范編寫。仿真過程中一共執(zhí)行了200萬個分組轉(zhuǎn)發(fā)，對各個微引擎的利用率每隔1 μs計算一次。

仿真得到如圖2所示的微引擎利用率最大差與均值之比的變化。分別為輕載情況和全負(fù)荷情況下各個微引擎利用率之差的最大值與均值的比值。兩種情況下的比值分別在0.15和0.048左右變化。最大值與最小值之所以存在一個相對穩(wěn)定的差別是因為各個微引擎一直在執(zhí)行分組轉(zhuǎn)發(fā)，每完成一個分組的處理就會導(dǎo)致負(fù)載發(fā)生變化。其中：大于穩(wěn)定值的情況是因為執(zhí)行路由表或分組分類表更新的延時較長且不固定，導(dǎo)致微引擎對分組處理延時的不確定，最后導(dǎo)致了各個微引擎負(fù)載的跳變。但在負(fù)載均衡機(jī)制的影響下，各個微引擎利用率的最大差與均值之比很快又回到了穩(wěn)定值附近。下跳的原因是在采樣時刻，此時剛執(zhí)行完負(fù)載均衡調(diào)度，各個微引擎的負(fù)載相差很小。從圖2可看出，在全負(fù)荷運行時，該比值一般情況下均小于0.05。可說明該全局自適應(yīng)負(fù)載均衡策略有效地實現(xiàn)了各個微引擎間的實時負(fù)載均衡。

5結(jié)束語

西北工業(yè)大學(xué)航空微電子中心自主設(shè)計了一款基于TLDP結(jié)構(gòu)的網(wǎng)絡(luò)處理器。如何設(shè)計和實現(xiàn)有效的線程調(diào)度機(jī)制來提高分組吞吐率是發(fā)揮和提高整個系統(tǒng)性能的關(guān)鍵。本文對TLDP結(jié)構(gòu)網(wǎng)絡(luò)處理器的全局線程調(diào)度機(jī)制進(jìn)行詳細(xì)的分析，提出了適合于TLDP結(jié)構(gòu)的全局自適應(yīng)負(fù)載均衡調(diào)度策略，不僅有利于降低TLDP結(jié)構(gòu)的功耗，而且實現(xiàn)了多個協(xié)議處理微引擎間的實時均衡。最后通過仿真對各個微引擎在運行時的利用率進(jìn)行了統(tǒng)計分析，說明該機(jī)制實現(xiàn)了微引擎間的實時負(fù)載均衡，最大化了系統(tǒng)分組處理能力。

參考文獻(xiàn)：

[1]周昔平. 多線程網(wǎng)絡(luò)處理器分布式內(nèi)核結(jié)構(gòu)研究[D].西安：西北工業(yè)大學(xué)， 2005.

[2]GUNTHER B K. Multithreading with distributed functional units[J]. IEEE Trans on Computers， 1997，46(4): 59－65.

[3]SMITH J E. Instruction level distributed processing[J]. IEEE Computer， 1997，34(4): 53－60.

[4]CHEN M K， LI Xiao－feng ， et al. Achieveing high performance from complied network applications while enabling ease of programming[C]//Proc of PLDI. 2005: 99－107.

[5]WAGNER J， LEUPERS R. Compiler design for an industrial network processor[C]//Proc ofACM SIGPLAN Workshop on Languages， Compilers and Tools for Embedded Systems.2001:77－84.

[6]BUX W，DENZEL W E， EUGBERSEN T，et al. Technologies and building blocks for fast packet forwarding[J]. IEEE Communications Magazine， 2001，39(1): 70－77.

[7]WOLF T， FRANKLIN M. Locality－aware predictive scheduling of network processors[C]//Proc ofISPASS. 2001: 152－159.

[8]BENINI I， BOGLIOLOZ A， MICHELIY de. A survey of design techniques for system level dynamic power management[J]. IEEE Trans on VLSI Systems， 2000，8(3):299－316.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”