基于負載均衡的隨機作業(yè)流密碼服務調度算法

李莉，史國振，耿魁，董秀則，李鳳華,,5

（1. 西安電子科技大學通信工程學院，陜西 西安 710071；2. 北京電子科技學院電子信息工程系，北京 100070；3. 北京電子科技學院信息安全系，北京 100070；4. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；5. 中國科學院大學網(wǎng)絡空間安全學院，北京100049）

1 引言

天地一體化網(wǎng)絡作為無處不在的網(wǎng)絡服務的基礎支撐，是國家信息化的關鍵。在安全形勢日益嚴峻的今天，天地一體化網(wǎng)絡的安全對于實現(xiàn)國家安全戰(zhàn)略目標具有重要的意義。天地一體化網(wǎng)絡的安全保障離不開相應的密碼防護，通過配備高性能的密碼服務器，采用密碼計算資源的虛擬化、密碼服務的高并發(fā)調度運行來保障數(shù)據(jù)安全。天地一體化信息網(wǎng)絡由于跨陸、海、空、天多域及天基網(wǎng)絡的特殊性，拓撲結構具有動態(tài)變化的特點，且傳輸鏈路具有高延時、大方差、間歇性的特點，異構互聯(lián)也致使網(wǎng)絡設備類型多、密碼資源多、業(yè)務需求量大[1]。因此服務于天地一體化網(wǎng)絡的密碼服務器存在接收業(yè)務海量高并發(fā)且不同業(yè)務隨機交叉的現(xiàn)象，如何保證來自不同網(wǎng)絡應用端的不同密碼服務請求得到有效、快速的解決，防止業(yè)務流阻塞，業(yè)務流的調度及并發(fā)運算起著至關重要的作用。文獻[2]針對安全領域中海量業(yè)務安全需求多樣性導致的多種密碼算法運算隨機交叉的現(xiàn)象，提出了具有關聯(lián)判斷的基于業(yè)務標識的分層硬件調度方法——HHS-ACDID，通過兩級調度完成業(yè)務流與密碼算法IP核間的映射以及隨機交叉業(yè)務流中關聯(lián)作業(yè)包的正確有序處理，從而實現(xiàn)了高速數(shù)據(jù)流下多對多通信中多密碼算法、多數(shù)據(jù)流的隨機交叉加解密問題。

由于多算法密碼服務器屬于典型的異構多核系統(tǒng)，各密碼算法處理節(jié)點的處理能力和存儲容量不同，業(yè)務流到達各處理節(jié)點的時間不一致，如果不能進行合理的作業(yè)包與處理節(jié)點間的映射，則可能導致處理節(jié)點負載輕重不一，影響整個處理系統(tǒng)的吞吐率。本文針對多算法密碼服務器的特點，考慮實際處理需求，在文獻[2]的基礎上，抽象出與實際密切吻合的任務模型，在充分考慮處理節(jié)點運算速率和節(jié)點存儲容量的基礎上，以負載均衡為調度目標，將處理節(jié)點的實際處理能力作為靜態(tài)參數(shù)，處理節(jié)點任務隊列的剩余容量作為動態(tài)參數(shù)，采用靜態(tài)參數(shù)和動態(tài)參數(shù)相結合的方法，設計了一種支持非關聯(lián)任務和關聯(lián)任務的兩級負載均衡動態(tài)調度算法，在不額外增加系統(tǒng)硬件成本的條件下，實現(xiàn)了高速的密碼處理吞吐率。

2 相關研究

多處理器任務調度問題是一種NP-hard問題，其最優(yōu)解往往與具體應用有關，需要針對實際問題進行建模，很多文獻從不同角度（如負載均衡、吞吐量最大化、資源利用率最大化、減少功耗等方面）對其進行了研究。為獲得資源的最大利用率和并行任務的最短執(zhí)行時間，Liu等[3]根據(jù)歷史調度信息，采用Apriori分類數(shù)據(jù)挖掘算法，通過建立任務和處理器之間的關聯(lián)規(guī)則來進行多核處理器調度。該算法提高了內核利用率，但是沒有考慮決定系統(tǒng)調度成敗的歷史調度信息的產(chǎn)生；另外，由于該算法必須考慮關聯(lián)規(guī)則外任務的調度，使該算法實現(xiàn)復雜。文獻[4]提出一種基于異構多核處理器的 PIE（performance impact estimated）調度算法，該算法以進程在各個內核上能夠獲得性能的評估結果作為任務調度的參考依據(jù)，以求充分利用處理器資源，提高任務執(zhí)行率。其中，性能采集模塊以及評估參數(shù)寄存器的使用在一定程度上降低了該算法的易用性。

針對多處理器平臺中公平調度問題，Li等[5]基于時間片輪轉（RR，round robin）調度算法，分別提出了面向同構的多核處理器（DWRR，distributed weighted round robin）調度算法和面向異構的多核處理器（ADWRR，asymmetric distributed weighted round robin）調度算法[6]，實現(xiàn)核間的負載均衡，并保證了全局調度公平性。但并未考慮關聯(lián)任務的調度問題。針對多核處理器平臺上關聯(lián)任務的調度問題，楊茂林等[7]提出一種資源敏感的實時任務調度算法。該算法采用任務分組策略將存在共享資源敏感的任務劃分為若干個相關任務子集，將同一相關任務子集上的任務盡量分配到同一內核上；對于無法分配在內核上的相關任務子集采用任務拆分策略進行拆分。該算法可以減少核間任務阻塞。但是，當系統(tǒng)中任務數(shù)較少或較多時，可能會因為任務相關度評價耗時過長，造成任務的等待，降低系統(tǒng)吞吐率。文獻[8]考慮到云計算環(huán)境處理節(jié)點的安全性和可用性以及任務之間的相互依賴關系，采用有向無環(huán)圖（DAG）描述一個應用中相互依賴的任務，提出一種云計算環(huán)境下融合安全與可用性的 DAG任務調度策略。文獻[9]提出一種包含優(yōu)先級和條件邊的集成控制流信息，擴展并行有向無環(huán)圖任務模型，提高對條件任務的解決效率，減少傳統(tǒng)的零星DAG任務系統(tǒng)的調度分析時間。

在異構系統(tǒng)中，基于負載均衡的調度使用最多的是 RR算法和啟發(fā)式算法[10]。RR算法采用處理節(jié)點輪詢的方式，對任務進行調度，算法簡單、快速，比較適用于硬件實現(xiàn)，但是沒有考慮不同任務間的差異以及關聯(lián)任務的執(zhí)行?？紤]QoS需求，已有不少學者基于多目標約束，對經(jīng)典的啟發(fā)式算法，如遺傳算法[11]、蟻群算法[12-14]、Sufferage[15]等進行改進并提出新的調度方案。文獻[16]提出一種雙目標優(yōu)化粒子群算法（DPSO, discrete particle swarm optimization），在滿足任務安全需求的前提下，縮短系統(tǒng)對任務的響應時間。文獻[17]基于完成時間最快和用戶支出費用最少2個目標，面向商業(yè)云提出一種基于完成時間和支付費用權重函數(shù)的動態(tài)工作流調度算法，為任務選取合適的處理節(jié)點。文獻[18]針對多核異構分布式系統(tǒng)中流程序的執(zhí)行，提出了 2種新的啟發(fā)式分區(qū)算法：KLA（Kernighan-Linadapted）算法和CA（congestion avoidance）算法來解決空間圖分割流程序的劃分問題，以提高系統(tǒng)的吞吐率。文獻[19]提出采用統(tǒng)計的方法來進行線程的分配，給每個線程分配一個隨機樣本，通過減少需要測量的候選解決方案數(shù)量的統(tǒng)計方法來降低線程分配時間，獲得最佳性能。文獻[20]采用多目標優(yōu)化為約束條件，提出了一種基于混沌蟻群的遺傳算法（GA-CAS），獲得了優(yōu)于其他啟發(fā)式算法的收斂速度。

由于在實際應用中具有許多時刻變化的因素，通過靜態(tài)調度找出最優(yōu)調度方案幾乎不可能，容易造成調度和過程優(yōu)化控制相互脫節(jié)，因此，大規(guī)模動態(tài)復雜調度始終是研究中的熱點與難點。本文基于海量高并發(fā)隨機交叉密碼服務的應用場景，建立一個與實際應用更接近的任務模型，在文獻[2]提出的兩級調度的基礎上，通過對不同運算需求業(yè)務流的感知，實現(xiàn)作業(yè)包在處理節(jié)點上的合理分配，充分發(fā)揮異構多核的優(yōu)勢，實現(xiàn)快速的業(yè)務流處理。

3 任務模型

3.1 任務集

在流數(shù)據(jù)處理系統(tǒng)中，數(shù)據(jù)需要以包的形式進行傳輸和處理。根據(jù)作業(yè)包的大小不同，一個作業(yè)需要拆分為若干個作業(yè)包。假設系統(tǒng)中有n個作業(yè)，作業(yè)集合記為 J = { J1, J2,… ,Ji, … ,Jn}，作業(yè) Ji劃分為m個作業(yè)包，可以表示為 Ji= { Ji1, Ji2,… ,Jid,… ,Jim}。根據(jù)文獻[2]中的描述，作業(yè)Ji的第a個作業(yè)包Pia表示為

其中，taski為作業(yè)包所屬業(yè)務的編號，同一作業(yè)的不同作業(yè)包該字段相同，是作業(yè)的唯一標識，同時保證處理完作業(yè)包的正確返回。cmdi為處理命令，決定對數(shù)據(jù)的具體操作，如加密、解密、簽名、驗簽等。cypi為密碼算法模塊id號，決定數(shù)據(jù)的處理節(jié)點，c y pi={c luster _ i d | |i p _ i d }，其中，高位表示簇號，低位表示簇內的算法處理節(jié)點號，即在流數(shù)據(jù)打包的軟件層就確定了作業(yè)包與算法 IP核間的映射關系。modei為密碼算法工作模式，決定對密碼算法處理節(jié)點入口數(shù)據(jù)的處理，如對于ECB模式可以將數(shù)據(jù)直接送入算法處理節(jié)點，而對于CBC模式，則需要將數(shù)據(jù)與同一個業(yè)務的前一組數(shù)據(jù)的運算結果進行異或后，再送入算法處理節(jié)點。Noi為作業(yè)包的序號，long為作業(yè)包中運算數(shù)據(jù)的長度，dia為運算數(shù)據(jù)。由于不同業(yè)務作業(yè)包的大小不盡相同，且不同的工作模式、不同算法的運算速度不同，因此在軟件層無法精確地預知處理節(jié)點的負載狀況，從而導致處理節(jié)點負載不均衡，影響系統(tǒng)的整體吞吐率。為此，本文將 cypi修改為cypi={c luster _ i d }，即在軟件調度層僅確定作業(yè)包所需送至的算法處理節(jié)點簇，相同的算法實現(xiàn)處于相同的算法節(jié)點簇中。作業(yè)包與算法IP核間的具體映射關系由硬件調度模塊根據(jù)處理節(jié)點的工作能力和負載情況實時確定。

流數(shù)據(jù)處理系統(tǒng)如圖1所示，來自不同應用線程的業(yè)務通過作業(yè)提交模塊將作業(yè)包發(fā)送至流數(shù)據(jù)處理系統(tǒng)的作業(yè)接收模塊，作業(yè)接收模塊按照時間順序依次接收到各作業(yè)包。

圖1 流數(shù)據(jù)處理系統(tǒng)

用i表示時間戳，則該時間戳的作業(yè)包為Ti。多任務環(huán)境下，由于數(shù)據(jù)傳輸路徑、速度等不同，不同業(yè)務請求的作業(yè)包到達作業(yè)調度系統(tǒng)的作業(yè)接收模塊時間不同。所以對于同一個業(yè)務來說，雖然各作業(yè)提交模塊按序提交各業(yè)務作業(yè)包，但是在作業(yè)接收模塊中的作業(yè)包是亂序的，即存在不同業(yè)務間的交叉接收。因此定義作業(yè)接收模塊中的任務集為

其中，nmax為一個作業(yè)窗口中作業(yè)接收模塊能夠接收的最大作業(yè)包的個數(shù)。

通過有向無環(huán)圖（DAG，directed acyclic graph）對流數(shù)據(jù)任務集進行描述，可以清晰地表示流數(shù)據(jù)作業(yè)包的傳遞及作業(yè)包間的數(shù)據(jù)相關關系。圖 2為流數(shù)據(jù)任務集 DAG，共有 4個任務： J OB1={T1, T2}， J OB2= { T3,T5,T9}， J OB3={T4,T7,T8,T11}，JOB4= {T6,T10}。

圖2 流數(shù)據(jù)任務集DAG

其中，JOB1、JOB2、JOB4為依賴任務，JOB3為非依賴任務。以 CBC加密模式為例介紹密碼運算中的依賴任務：假設2.JOBmode CBC= ，首先將明文分成3種固定長度的作業(yè)包，選取初始向量IV，對第一個作業(yè)包T3進行加密，得到密文T3′；然后，將密文T3′與下一個作業(yè)包T5異或后作為初始向量加密，得到密文T5′；最后，將密文T5′與下一個作業(yè)包T9異或后加密，得到密文T9′。加密過程如圖3所示。

圖3 JOB2 CBC加密

圖2 中TS為任務集的入口節(jié)點，TE為任務集的出口節(jié)點，實線箭頭為數(shù)據(jù)關聯(lián)線有序邊。前序節(jié)點：數(shù)據(jù)關聯(lián)線有序邊的起點處的節(jié)點為終點處節(jié)點的前序節(jié)點。由圖3可知，T3是T5的前序節(jié)點，T5是T9的前序節(jié)點。后繼節(jié)點：數(shù)據(jù)關聯(lián)線有序邊的終點處的節(jié)點為起點處節(jié)點的后繼節(jié)點。由圖 3可知，T5是T3的后繼節(jié)點，T9是T5的后繼節(jié)點。虛線箭頭為數(shù)據(jù)非關聯(lián)線有序邊，其有序僅表現(xiàn)為時間傳遞上的有序性，并沒有數(shù)據(jù)相關性。

通過流數(shù)據(jù)任務集的DAG模型可以看出，任務集有以下2種特點：同一業(yè)務的作業(yè)包在任務集中的排列是有序的；同一業(yè)務的作業(yè)包序列中穿插有其他業(yè)務的作業(yè)包。

3.2 作業(yè)窗口

作業(yè)調度系統(tǒng)根據(jù)作業(yè)接收模塊中的任務集，對作業(yè)包進行調度。假設作業(yè)接收模塊的存儲容量為m，數(shù)據(jù)流的傳輸速率為s bit/s，作業(yè)包大小為p，則作業(yè)窗口時間t必須滿足

且在t作業(yè)窗口時間內，作業(yè)接收模塊能夠接收到的作業(yè)包的個數(shù)最大為

作業(yè)包的大小是可變的，由規(guī)則化數(shù)據(jù)結構中的數(shù)據(jù)長度決定，作業(yè)窗口的大小必須保證作業(yè)接收模塊能夠完整地接收作業(yè)提交系統(tǒng)傳遞過來的作業(yè)包。

4 作業(yè)調度算法

4.1 作業(yè)調度模型

作業(yè)調度模型如圖4所示，包括7個部分：作業(yè)接收隊列、作業(yè)分轉模塊、簇任務隊列、負載均衡控制模塊、處理節(jié)點任務隊列、中間狀態(tài)存儲模塊和等待任務隊列。

作業(yè)接收隊列接收輸入的任務集；作業(yè)分轉模塊進行作業(yè)的第一級調度，按照cypi將作業(yè)包送至相應的簇任務隊列；負載均衡控制模塊進行作業(yè)的第二級調度，按照負載均衡策略，將作業(yè)包送至相應的處理節(jié)點任務隊列；處理節(jié)點任務隊列按照先來先服務的原則，將作業(yè)包送至處理節(jié)點進行算法處理；中間狀態(tài)存儲模塊用于暫存依賴作業(yè)前序作業(yè)包的中間結果，為后繼作業(yè)包提供中間數(shù)據(jù)；等待任務隊列是為了保證數(shù)據(jù)流的連續(xù)性，防止由于某個簇任務隊列滿導致的數(shù)據(jù)流阻塞，用于暫存已滿簇任務隊列的作業(yè)包。

4.2 計算資源

處 理 節(jié) 點 集 I P = { I Pi1, I Pi2, … ,I Pim, … ,I Pp1,… ,IPpn}為任務所能獲得的計算資源，每個處理節(jié)點具有各自的適用領域 field、運算速度 s和存儲容量cap。其中，適用領域描述該處理節(jié)點的功能，與任務屬性中的cypi對應；運算速度取決于處理節(jié)點本身的設計，以密碼算法IP核為例，包括密碼算法設計中的信號流水線處理、密鑰擴展的同步處理以及算法實現(xiàn)的工作頻率。存儲容量取決于處理節(jié)點任務隊列的大小，存儲容量必須為單元作業(yè)包的整數(shù)倍，否則會造成數(shù)據(jù)丟失。即

圖4 作業(yè)調度模型

4.3 作業(yè)調度策略

本文所研究的基于負載均衡的動態(tài)作業(yè)調度算法采用了靜態(tài)參數(shù)與動態(tài)參數(shù)結合的方法。以處理節(jié)點的實際處理能力為靜態(tài)參數(shù)，處理節(jié)點任務隊列的剩余容量為動態(tài)參數(shù)；按照可調節(jié)的比例得到一個權重來決定作業(yè)包的優(yōu)先級。

1) 處理節(jié)點狀態(tài)表

每個算法簇的負載均衡控制模塊維護一個處理節(jié)點狀態(tài)表： Sip={tunit,c ap,n}。負載均衡調度算法根據(jù)此狀態(tài)表進行處理節(jié)點權重的計算，進行作業(yè)包調度的動態(tài)調整。其中，tunit為單元作業(yè)包Punit的處理時間，cap為處理節(jié)點的任務隊列存儲容量，n為任務隊列中已有的作業(yè)包的個數(shù)。處理節(jié)點任務隊列中每接收一個作業(yè)包，則n+1，每輸出一個作業(yè)包，則n-1。

由于每個處理節(jié)點上可以執(zhí)行的操作類型不同，如加密、解密、簽名、驗簽，而不同的操作消耗的時間不同，因此單元作業(yè)包在不同處理節(jié)點上的處理時間為

其中，ti1表示第i個處理節(jié)點加密單元作業(yè)包的時間，ti2表示第i個處理節(jié)點解密單元作業(yè)包的時間，ti3表示第i個處理節(jié)點對單元作業(yè)包簽名需要的時間，ti4表示第i個處理節(jié)點對單元作業(yè)包驗簽需要的時間。因此，具有m個算法IP的算法i的處理節(jié)點狀態(tài)矩陣為

2) 處理節(jié)點權重

處理節(jié)點的權重與處理節(jié)點的剩余容量以及處理速度有關。由于處理節(jié)點的速度和容量的數(shù)量級不同，數(shù)據(jù)尺度的不統(tǒng)一對處理節(jié)點的選擇影響很大，必須進行調整。將節(jié)點的處理速度歸一化至[0,1]區(qū)間。

其中，mint 為簇上運算最快的節(jié)點處理單位作業(yè)包所需的時間，maxt 為簇上運算最慢的節(jié)點處理單位作業(yè)包所需的時間。以具有 m個算法 IP的算法 i的簇為例，有

因此，對于每一個處理節(jié)點來說，其速度權重為一固定向量。處理節(jié)點的剩余容量歸一化至[0, 1]區(qū)間。

其中，cap為處理節(jié)點的任務隊列容量，rcap為處理節(jié)點的任務隊列剩余容量，可通過隊列的容量減去已經(jīng)使用的存儲偏移量獲得，p為作業(yè)包的大小，n表示任務隊列中已有n個作業(yè)包，n可以通過處理節(jié)點任務隊列計數(shù)器實現(xiàn)。則處理節(jié)點的權重函數(shù)為

其中，α為速度權重系數(shù)，β為剩余容量權重系數(shù)。為便于后期處理節(jié)點權重的計算，將處理節(jié)點狀態(tài)矩陣替換為

3) 選擇關系表

選擇關系表用于描述進入處理節(jié)點任務隊列的依賴任務ID和處理節(jié)點ID間的對應關系，為一個二元表： c hoose_ l ist = {t a ski,ip _ i d }。選擇關系表的長度choose_list.length取決于算法簇處理節(jié)點的個數(shù)，每個算法簇維護一個選擇關系表。若某算法簇中的處理節(jié)點為n個，則

4.4 調度算法

1) 第一級分轉調度

根據(jù)cypi進行調度，按照先來先服務的原則將不同算法處理需求的作業(yè)包放入對應算法簇任務隊列中；當任務集中某一算法處理需求的作業(yè)包大量流入導致相應的簇任務隊列滿時，將當前作業(yè)包放入等待任務隊列中，并置mask為1，標識此單元被占用，繼續(xù)進行下一個作業(yè)包的調度；當簇任務隊列有數(shù)據(jù)移出時，則查詢等待任務隊列，將先進入的同一算法需求的作業(yè)包取出放入簇任務隊列中，如圖5所示。

圖5 第一級分轉調度模型

等待任務隊列能夠使任務集中的作業(yè)包不斷地流入，避免了因某個算法簇的任務執(zhí)行速度慢導致隊列滿，進而導致數(shù)據(jù)流的停滯。

2）第二級負載均衡調度

策略 1 為保證信號的快速處理，優(yōu)先考慮算法的存儲容量，當存儲容量不能滿足時，就沒有必要再考慮運算速度。當存儲容量滿足時，選取權重大的處理節(jié)點進行作業(yè)包的處理。

策略 2 當某依賴任務的前序作業(yè)包在處理節(jié)點i上運算時，其后繼作業(yè)包也必須在此處理節(jié)點上運算。此策略可以免除數(shù)據(jù)遷移帶來的傳輸時延，獲得較好的數(shù)據(jù)本地化。

具體作業(yè)調度算法步驟如下所示。

Step1 根據(jù)工作模式modei，判斷依賴性。

若modei為CBC|OFB|CFB，則此作業(yè)屬于依賴作業(yè)。首先查詢選擇關系表，若選擇關系表中存在此作業(yè)包的itask表項，則將此作業(yè)包放置于此表項對應的處理節(jié)點ip_id的任務隊列中，進入Step7；若選擇關系表中不存在此作業(yè)包的itask表項，則將此itask加入選擇關系表中，進入Step2。

若作業(yè)為非依賴作業(yè)，進入Step2。

Step2 根據(jù)處理節(jié)點狀態(tài)表，獲取本簇處理節(jié)點的剩余容量 c apr= c ap ? n p 。

Step3 根據(jù)處理節(jié)點狀態(tài)表和處理算法類型，獲取剩余容量非空處理節(jié)點的速度權重。

Step4 計算剩余容量非空處理節(jié)點的權重，選取權重最大的處理節(jié)點。

Step5 若作業(yè)包屬于依賴作業(yè)，將此處理節(jié)點ip_id加入itask對應的表項；否則，進入Step6。

Step6 將作業(yè)包放入處理節(jié)點ip_id的任務隊列中。

Step7 若作業(yè)包為依賴作業(yè)包，在作業(yè)包處理完成時，判斷此作業(yè)包是否為作業(yè)的最后一個分片，若是則從選擇關系表中將此作業(yè)包itask對應的表項刪除，并將運算結果直接返回業(yè)務請求端；否則將此作業(yè)包的運算結果作為中間狀態(tài)保存至中間狀態(tài)存儲模塊。若作業(yè)包不屬于依賴作業(yè)包，則將運算結果直接返回業(yè)務請求端。

5 分析及驗證

本文對任務調度負載均衡性和執(zhí)行效率進行了仿真，并與基于業(yè)務標識的分層硬件調度方法HHS-ACDID進行對比分析。仿真在Windows環(huán)境下，通過C++語言實現(xiàn)算法。由于每一個簇的調度過程是相似的，選取一個簇下的調度進行仿真。

任務集信息參數(shù)設置如表1所示。其中，itask為作業(yè)編號；Noi為不同作業(yè)包編號；flag為依賴作業(yè)標識；arrivalTime為作業(yè)包進入作業(yè)調度模塊的時刻；long為作業(yè)包大小。

表1 任務集的參數(shù)設置

仿真實驗1 權重系數(shù)α、β對完成時間的影響。假設當α=αi時，系統(tǒng)獲得最小完成時間。IP核數(shù)=4，隨機生成 4組處理速度 ti meij∈[16,36],i, j ∈ [1 ,4]。改變處理節(jié)點隊列存儲容量初始值CAP，觀察CAP與αi之間的關系如圖6(a)所示，可見在其他參數(shù)相同的情況下，取得最小完成時間的αi的取值隨CAP的增大而減小。IP核數(shù)=4，單位作業(yè)包完成時間分別為 t ime1∈ ( 8,28)， t ime2∈ ( 16,36)，time3∈ ( 32,52)，t i me4∈ ( 64,84)，C AP= 2 00，仿真結果如圖6(b)所示，取得最小完成時間的αi的變化趨勢與圖6(a)基本一致。

圖6 α、β與完成時間關系

仿真實驗 2 權重系數(shù)對負載均衡性和執(zhí)行效率的影響。采用相同的任務集，作業(yè)包總數(shù)=600，IP核數(shù)=4， ti meij∈[16,36],i, j ∈ [1 ,4]，改變α∈[0,1]，β∈[0,1]的取值，負載分布和完成時間如圖7所示。

圖7 α、β對調度結果的影響

從圖7可以看出，隨著處理節(jié)點速度權重系數(shù)α增大，IP核負載分布趨向于不均衡；系統(tǒng)完成時間先減小后增大，最后趨于不變。其中，當α=0.05時，完成時間取得最小值，負載分布較均衡。由此可知，α、β的取值影響任務調度過程中 IP核的負載分布和完成時間，以下實驗都將在完成時間最小的前提下討論。

仿真實驗 3 算法的負載均衡性。處理節(jié)點性能不變， ti meij∈[16,36],i, j ∈ [1 ,4]，IP核數(shù)=4，作業(yè)包總數(shù)分別為100、200、300、400、500、600、700，負載分布情況如圖8所示。

圖8 4個IP核的負載分布

IP核數(shù)為10，作業(yè)包數(shù)分別為500、700、1000、1100、1300、1500，負載分布情況如圖9所示。

圖9 10個IP核的負載分布

當處理節(jié)點數(shù)分別為4和10時，反映出相同的規(guī)律：隨著作業(yè)包數(shù)的增加，調度結果保持良好的負載均衡性。

仿真實驗4 從2個方面比較本文算法與分層硬件調度方法 HHS-ACDID的執(zhí)行效率：固定 IP核數(shù)，改變作業(yè)包數(shù)；固定作業(yè)包數(shù)，改變IP核數(shù)。

1) 固定 IP核數(shù)為 4，作業(yè)包總數(shù)變化（100～700）；固定 IP核數(shù)為 10，作業(yè)包數(shù)變化（500～1500），本文算法與HHS-ACDID算法的執(zhí)行時間比較分別如圖10和圖11所示。

圖10 4個IP核的完成時間

圖11 10個IP核的完成時間

由圖10和圖11可知，在相同的實驗環(huán)境下，本文算法的執(zhí)行效率明顯優(yōu)于HHS-ACDID算法，執(zhí)行時間比HHS-ACDID算法減少約10.6%～15.3%，并且隨著作業(yè)包數(shù)的增多，其優(yōu)勢更加明顯。這主要是因為與HHS-ACDID算法相比，本文算法同時考慮不同處理節(jié)點的處理性能和當前負載情況，保證了處理節(jié)點的負載均衡和任務的處理速度，使高性能的處理節(jié)點得到更多的使用率。

2) 固定任務數(shù)=1 000，IP核數(shù)變化（4～10個IP核）時，本文算法與HHS-ACDID算法執(zhí)行時間如圖12所示。

圖12 不同IP核下的任務完成時間對比

由圖 12可知，對于相同的任務集，本文算法的執(zhí)行時間比HHS-ACDID算法少10.3%～15.3%。IP核數(shù)量較少時優(yōu)勢明顯；隨著IP數(shù)量的增加，其優(yōu)勢有所降低。

可見，通過硬件實時監(jiān)控處理節(jié)點任務隊列的剩余容量，在任務數(shù)較大時，提高速度權重系數(shù)，減小剩余容量權重系數(shù)；任務數(shù)較小時，提高剩余容量權重系數(shù)，減小速度權重系數(shù)，能獲得較佳的負載均衡效果。根據(jù)測試結果，在作業(yè)量增大的趨勢下，本文算法展現(xiàn)出更大的優(yōu)勢。

6 結束語

本文針對多算法密碼流系統(tǒng)模型，提出了一種基于負載均衡的兩級作業(yè)調度算法，首先根據(jù)作業(yè)包的算法標識cypi把任務遞交到相應的簇；然后根據(jù)作業(yè)包的工作模式 modei以及處理節(jié)點狀態(tài)表進行二級均衡調度。該算法適用于關聯(lián)任務和非關聯(lián)任務以及混合情況，實現(xiàn)上采用三級存儲層次的流水架構，通過作業(yè)分轉模塊、負載均衡控制模塊以及等待任務隊列，保證了數(shù)據(jù)流傳輸?shù)倪B續(xù)性，不存在作業(yè)的重分配以及因作業(yè)需求類型不同導致的某個作業(yè)長期占用計算資源，而其他作業(yè)得不到響應的情況，也起到了隱藏傳輸時延、改善帶寬效應的作用。仿真結果表明，該算法在保證系統(tǒng)負載均衡的基礎上，執(zhí)行效率比 HHS-ACDID算法高12%左右。