網絡處理器任務調度
2007-12-31 00:00:00吳佳駿張兆慶
計算機應用研究 2007年8期
摘要：按照網絡應用及IXP處理器架構特點建立代價模型，并且以網絡應用需求為導向提出了基于時間和吞吐量的任務調度算法（LTTS）。該算法兼顧網絡程序的吞吐量和延遲需求自動完成網絡任務的調度工作，并且在這兩項評價網絡程序性能的重要指標上得到了滿意的結果。
關鍵詞：網絡處理器； 任務調度； 編譯器
中圖分類號：TP332文獻標志碼：A
文章編號：1001－3695(2007)08－0034－04
網絡發展初期，其應用的數據流量較小，對網絡的研究主要是在完善網絡協議和構建服務體系結構上。這個時期，網絡設備主要是使用通用處理器進行網絡數據處理。但是隨著各種傳輸技術的進步，網絡帶寬的增長速度逐漸超過了CPU處理能力的增長速度，而且這種差距有著進一步加大的趨勢。這時，網絡設備開始更多地采用ASIC技術；然而，ASIC缺乏靈活性，一旦指令或計算邏輯固化到硬件中，就很難修改升級。當前網絡的應用范圍在不斷擴大（從商用、教育到家庭和個人），新的業務不斷涌現（電子商務、多媒體應用和視頻會議等），網絡的發展也不僅僅是帶寬的不斷提高，而更多地表現為對靈活性、多樣化的要求。為了滿足網絡設備高性能和靈活多樣的處理方式的需求，一種針對網絡應用特性的新型網絡處理器[1~3]被提出來了。
但是由于網絡處理器的復雜結構，基于網絡處理器的應用程序編寫并不像針對傳統處理器的程序那么簡單。為了滿足各種不同的網絡應用，網絡處理器通常還含有不同的處理器內核，如Intel公司的IXP[1]系列處理器就集成了兩種不同的內核。早期大多數網絡應用程序是通過程序員手寫匯編代碼[4]完成的，這種方式工作量大而且容易出錯；異構的處理器結構還使得程序員要針對不同的處理器內核編寫不同的代碼。一些專門針對網絡處理的集成開發環境[5]也孕育而生，這些集成開發環境中程序員要針對不同的處理器內核編寫不同的代碼，并且需要程序員手工完成程序劃分工作。
1研究平臺
本文的目標平臺是Intel公司的IXP2400處理器。IXP￣2400是Intel公司IXA架構的網絡處理器產品。其中包含一個基于ARMV5TE的XScale內核（XScale是一個32位的通用RISC處理器）、八個RISC結構的ME（microengine）（每個ME有八個硬件支持的線程）。
編譯器平臺選取ShangriLa。它是Intel和中國科學院計算所合作開發的針對網絡處理器的高效易用的編程環境[6，7]。ShangriLa采用了專門針對網絡應用的編程語言Baker（它是在C語言子集上加入網絡應用特征的一個擴展）。Baker語言隱藏了復雜的異構多核處理器架構，展現在用戶面前的是一個常用的多線程單一處理器編程環境。ShangriLa的編譯架構是基于ORC(open research compiler)[8]開發的，原來ORC的前端被替換為Baker前端。
2復合式任務調度模型
網絡程序應用的多樣化使得單一模型并不能夠滿足如今網絡應用的需求。通常的文件傳輸應用，如電子郵件和視頻對延遲并不敏感。如果包的傳輸在這種應用情況下慢了幾秒，通常不會有太大影響；但是其他應用，如交互式應用和實時應用則對延遲非常敏感，如電話和視頻會議對延遲都有非常嚴格的要求。如果在電話通話過程中每句話都延遲了2 s，那么用戶將會認為這樣的連接是不能接受的；另外，從一臺服務器上播放音頻或視頻并不需要很低的延遲。可以用四個參數來描述每種網絡應用的需求，即可靠性、延遲、抖動、帶寬。這四個特征合起來就構成了決定一種網絡應用所要的服務質量[9]。
為了滿足服務質量的多樣化需求，本文提出了時間驅動模型和吞吐量驅動模型相結合的新型靜態任務調度算法LTTS（latency and throughput based task schedule）。對于要求實時應用的網絡程序，任務調度是使用處理時間驅動模型來減少程序對于每個分組的處理時間，達到降低延遲的目的。但是對于一些需要高帶寬的網絡應用程序，其網絡數據吞吐量往往比分組處理時間更重要，所以，任務調度算法也包含基于吞吐量驅動模型 (throughputdriven cost model，TDCM)。在這種模式下，它是為了獲取最大的吞吐量而不是減少分組處理時間。網絡應用的吞吐量是指在單位時間中多少分組被處理。使用吞吐量模型雖然在某些情況下單個分組的處理時間更長，但是分組的吞吐量應該大于處理時間驅動模型。
圖1展示了時間驅動模型和吞吐量驅動模型的各自特點。下面的例子是實際IXP系統的簡單描述，用來表述兩種模型的差異，僅包含了節點之間的通信開銷執行時間和代碼大小這些條件。
使用例子中給定的條件，在時間驅動模型和吞吐量驅動模型下會得到不同的結果。對于時間驅動模型，最好的解決方案是減少最大通信開銷。這種情況下，A和B就會被放在同一個處理器上，C因為代碼大小的限制會被放在另外的處理器上。調度結果展示在圖1中就是{(A， B)， C}。如果使用吞吐量驅動模型，那么B和C最好安放在同一個處理器。如果A和B放在同一個處理器上，那么執行時間會不平衡，降低了吞吐量。因此使用吞吐量驅動模型的調度結果是{(A)， (B， C)}。雖然第二種方法比第一種方法需要更多的時間處理一個包，但是第二種調度方法會讓吞吐量變大。
為了使得任務調度更好地區分網絡應用程序的行為，本文對編譯器的編譯選項進行修改，提供對網絡服務質量的語言支持。這樣任務調度就可以依靠編譯選項獲取的程序性能取向信息，用時間和吞吐量驅動模型進行復合調度。
3復合式任務調度算法
通過前面的討論已經初步了解網絡處理器上復合式任務調度的基本特點。但是在實際應用中影響程序的最終性能因素遠比抽象模型復雜，ShangriLa的調度算法必須考慮到這些因素。下面給出影響程序吞吐率與處理延遲的主要因素。
網絡應用中對分組的吞吐率取決于執行時間最長的處理階段。分組數據的處理延遲由任務調度長度決定，也就是從接收一個分組數據到發送出去所要的平均時間。在復合調度模型中可以近似地把吞吐量T(throughput)表示為T=N/K。對于吞吐量的基本抽象描述，其有助于指導調度獲得較高的吞吐量。其中：
a)N表示運行關鍵階段任務的處理器個數，與吞吐率成正比，所以在進行任務調度時可以通過復制關鍵節點來達到提高程序吞吐率的效果。但是這個復制個數受限于可得到的處理器個數，并且關鍵節點隨節點復制比率不停變化。
(2)K等于在關鍵階段處理一個分組所需要的時間。關鍵階段是指在一個流水線中執行時間最長的瓶頸階段。階段的劃分是以ME為單位，也就是一個ME作為一個階段。
其中：Wi表示第i個PPF處理一個分組數據的執行時間。影響執行時間的因素很多，其中包含PPF的指令條數、執行頻率、PPF分配到的處理器類型（同一個PPF在XScale上與ME的執行速度是不一樣的）以及PPF數據在存儲器上的分配類型等。因為延遲只是針對單個分組數據處理而言的，Wi并不考慮PPF被復制導致的平均數據處理時間的減少。
4網絡任務調度測試
4．1測試環境
本文在ENP2611上對異構編譯器生成的代碼進行了性能評估。ENP2611采用的是Intel公司的IXP2400處理器；板上含有8 MB SRAM、64 MB DRAM、三個千兆光纖網口；另外還有一個IXIA發包機和三塊千兆光纖網卡。這三個部分構建成一個完整的網絡測試平臺。
4．2測試例子
測試例子是使用Baker語言編寫的三個網絡應用程序：
a)L3switch[10]，包含對IP分組的轉發和路由功能，它最主要的是對IP提供路由功能。按照最長匹配法在路由表中查找對應IP分組的轉發地址，然后把分組轉發到目標網絡中。
b)MPLS[11]（multiprotocol label switching，多協議標簽交換），對每個接收到的分組，使用標簽來替換其目標IP地址。通過使用標簽的路由，減少路由對硬件的需求，并且相對傳統的IP路由方式提供更有效的網絡流量控制。
c)Firewall，用來隔離內部和外部網絡，對內部網絡提供安全防護。Firewall按照IP地址、網絡協議和端口號組合成的規則對收到的分組標上ID，然后按照ID扔掉不合乎要求的IP分組，防止危險數據流入內部網絡。
對于L3switch和MPLS，使用NPF[10，11]規定的分組集合作為程序測試輸入集合。除了對上面提到的三個程序進行性能測試，還使用了其他網絡應用例子進行正確性測試，如NAT(network address translation)、QoS、報頭壓縮程序以及MD5加/解密應用。
4．3測試結果
測試中的三個程序使用分組轉發率作為評估網絡程序性能的指標。優化選項時，-O3+peak所有優化選項被打開，各種優化是相互依賴的。其中包含基本的標量優化、inline優化、paket access combining（PAC）優化、packet caching(PC)等優化手段。圖2展示了使用最小為64 Byte分組時程序的分組轉發速率。因為網絡分組的收發模塊要各占一個ME，所以可以使用來調度的ME個數最多只有六個。調度算法按照使用一個ME逐步遞增到使用六個ME進行了測試。從性能測試結果可以看到，在ME個數低于四個時，增加ME處理器個數，對應程序性能也得到了線性提高。當ME個數超過四個時，帶寬利用率接近飽和，程序的性能增長變得平緩。這時，硬件的訪存帶寬成了限制程序性能提升的瓶頸。圖2中每條曲線都代表使用1~6個ME時獲取的性能。這三個程序都在2.5 Gbps時達到了100%的分組轉發率。其中MPLS更達到3 Gbps的ENP2611開發板極限轉發率。
測試結果表明，通過ShangriLa生成的代碼性能已經可以與專為IXP2400手工編寫的匯編代碼性能媲美。地址轉換很好地完成了在兩個不同架構處理器內核之間的地址協調工作，保證了兩個異構處理器之間數據的安全共享。LTTS算法的自動調度結果也滿足了網絡應用程序對高性能的需求。這種技術的使用使得建構一個整合的統一編譯平臺成為可能。基于整合編譯器開發平臺使得程序員面對與傳統類似的開發環境時，程序編寫的工作強度大大降低，并且取得了與手工編寫匯編代碼相近的性能。
5結束語
網絡程序不同于普通程序，網絡應用具有較高的并行性。但是網絡應用中的并行性是數據并行性，而且網絡程序評價性能指標的延遲時間和吞吐量也與普通任務調度追求的調度長度不同。本文提出了針對網絡應用特性的任務調度算法LTTS。在下一步的研究工作中，可以把靜態調度算法LTTS移植到動態調度系統中，實現自適應的網絡任務調度，針對變化的網絡狀況采用不同的調度策略，以期獲得更好的調度效果。
參考文獻：
［1］Intel IXP family of network processors[EB/OL].http://www.intel.com/design/network/products/npfamily/index.htm.
[2］The Motorola CPort family of network processors[EB/OL].http://www.motorola.com/webapp/sps/site/taxonomy.jsp?nodeId=01M￣994862703126.
[3］IBM PowerNP network processors[EB/OL].http://www3.ibm.com/chips/techlib/techlib.nsf/products/IBM_PowerNP_NP4GS3.
[4］JOHNSON E J， KUNZE A. IXP2400/2800 programming:the complete microengine coding guide[M].Hillsboro，OR:Intel Press，2003.
[5］TejaNP*: a software platform for network processors[EB/OL]. http://www.teja.com.
[6］CHEN M， JOHNSON E， JU R. Compilation system for throughputdriven multicore processors[C].//Proc of Micro－37.Oregon:[s.n.]， 2004.
[7］VIN H， MUDIGONDA J， JASON J，et al. A programming environment for packetprocessing systems: design considerations[C]//Proc of the 3rd Workshop on Network Processors Applications.Madrid:[s.n.]， 2004.
[8］中國科學院計算技術研究所.基于IA64開放源代碼編譯器ORC2.1[EB/OL].(2003－07－15).[2006－02－19]. http://ipforc.sourceforge.net/readmerelease－2.1.htm.
[9］TANENBAUM A S.Computer networks[M]. 4th ed. Amsterdam:Prentice Hall Press， 2002.
[10］Network Processing Forum. IP forwarding application level benchmark[EB/OL].http://www.npforum.org/benchmarking/ipforwarding_bm.shtml.
[11］Network Processing Forum. MPLS forwarding application level benchmark and annex[EB/OL]. (2003－02－24).[2006－02－19].http://www.npforum.org/techinfo/MPLSBenchmark.pdf.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
