網絡處理器自適應負載均衡調度機制

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

關鍵詞：網絡處理器； 動態調度； 負載均衡

中圖分類號：TP303文獻標志碼：A

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

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

1TLDP結構網絡處理器

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

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

2關鍵因素分析

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

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

即負載的處理時間必須遠大于負載信息的收集時間∑Tci和均衡調度時間Tsch之和。否則調度器進行負載信息的收集和調度決策后，各個微引擎的狀態已經發生了較大的變化，此時的調度結果是無效的。

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

另外，在TLDP結構中線程粒度小，執行線程遷移需要暫停兩個相關微引擎的處理，每次遷移需要耗費近10個處理器周期，負載遷移代價較大。在10個處理器周期內，外部新的分組處理請求的到達概率很大，與其進行負載遷移，還不如將新的分組處理請求調度到輕載的微引擎上。因此，在TLDP結構上執行負載遷移不可取。

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

3全局自適應負載均衡調度策略

全局自適應負載均衡調度機制包含兩部分：a)微引擎集合的選擇調度機制。根據TLDP內部負載的當前狀態和歷史信息自動選擇調度若干個微引擎執行分組處理。b)微引擎集合的動態負載均衡機制。在被選擇的微引擎集合中實現微引擎間的實時負載均衡，處于空閑狀態的微引擎一段時間后自動進入休眠狀態，保證微引擎間的負載均衡的同時，降低了整個TLDP結構的功耗。

3．1微引擎集合的選擇調度機制

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

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

3．2微引擎集合的動態負載均衡機制

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

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

4調度策略的評價

在傳統的分布式系統中，通常以任務的響應時間和所有處理節點完成任務的處理性能或者吞吐量為依據來評價其動態負載均衡調度策略的優劣，反映了一個調度機制的調度質量。TLDP結構位于網絡處理器的數據平面上，其功能是快速地完成每個分組的解析和轉發處理，分組吞吐率代表TLDP的分組處理性能或吞吐量。

本文建立了TLDP結構的RTL級模型，對各個微引擎在運行時的利用率也進行了統計分析，通過觀察每個微引擎利用率的差別大小變化可判斷其負載均衡調度策略的優劣。其中：數據分組流采用NPF提供的數據包產生腳本程序生成；協議處理程序根據網絡處理器論壇提供的IPv4和IPv6的測試基準要求以及RFC 894、RFC 2464、RFC 1812和RFC 2460的協議規范編寫。仿真過程中一共執行了200萬個分組轉發，對各個微引擎的利用率每隔1 μs計算一次。

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

5結束語

西北工業大學航空微電子中心自主設計了一款基于TLDP結構的網絡處理器。如何設計和實現有效的線程調度機制來提高分組吞吐率是發揮和提高整個系統性能的關鍵。本文對TLDP結構網絡處理器的全局線程調度機制進行詳細的分析，提出了適合于TLDP結構的全局自適應負載均衡調度策略，不僅有利于降低TLDP結構的功耗，而且實現了多個協議處理微引擎間的實時均衡。最后通過仿真對各個微引擎在運行時的利用率進行了統計分析，說明該機制實現了微引擎間的實時負載均衡，最大化了系統分組處理能力。

參考文獻：

[1]周昔平. 多線程網絡處理器分布式內核結構研究[D].西安：西北工業大學， 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.

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