李莉，史國振，耿魁，董秀則，王璇，李鳳華

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

密碼芯片的多算法隨機作業(yè)流調(diào)度方法

李莉1,2，史國振3，耿魁4，董秀則2，王璇1，李鳳華4

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

針對安全領(lǐng)域中海量業(yè)務(wù)安全需求多樣性導(dǎo)致的多種密碼算法運算隨機交叉的現(xiàn)象，提出了具有關(guān)聯(lián)判斷控制的基于業(yè)務(wù)標識的分層硬件調(diào)度方法(HHS-ACDID)。第一級調(diào)度完成業(yè)務(wù)在不同算法簇上的分配，通過優(yōu)化檢索邏輯，實現(xiàn)數(shù)據(jù)的快速分配；第二級調(diào)度通過增設(shè)關(guān)聯(lián)控制模塊和關(guān)聯(lián)隊列的方式，完成上下文相關(guān)作業(yè)分組調(diào)度順序的處理。采用中間狀態(tài)存儲模塊，以業(yè)務(wù)號為索引完成串行密碼算法工作模式下中間狀態(tài)的存儲，并通過預(yù)處理模塊完成對后序關(guān)聯(lián)作業(yè)分組輸入數(shù)據(jù)的處理。實驗驗證所提調(diào)度方法有效解決了高速數(shù)據(jù)流下多對多通信中多密碼算法、多數(shù)據(jù)流的隨機交叉加解密問題。

交叉加解密；作業(yè)調(diào)度；多算法；密碼處理芯片；硬件調(diào)度

1 引言

計算機網(wǎng)絡(luò)的發(fā)展以及互聯(lián)網(wǎng)應(yīng)用、移動通信的普及，加快了全球經(jīng)濟一體化的進程，促使社會經(jīng)濟及網(wǎng)絡(luò)經(jīng)濟快速發(fā)展。云服務(wù)、電子商務(wù)、網(wǎng)上銀行、電子支付等新型服務(wù)模式的不斷涌現(xiàn)，使云安全進入了高速發(fā)展期，云加密服務(wù)成為云安全市場新的增長熱點。在數(shù)據(jù)大集中處理方式下，數(shù)據(jù)加解密以及數(shù)字簽名、驗簽的業(yè)務(wù)請求數(shù)量非常巨大，加密服務(wù)終端必然存在著不同業(yè)務(wù)數(shù)據(jù)的高度融合和密碼服務(wù)請求的交叉訪問，即多個不同業(yè)務(wù)的不同密碼服務(wù)請求間的交叉融合。這些業(yè)務(wù)請求的不同可能表現(xiàn)在處理算法上，如加密郵件請求的DES算法、簽名請求的散列算法，以及數(shù)據(jù)庫加密請求的AES算法等；也可能表現(xiàn)在密鑰上，不同客戶的業(yè)務(wù)請求具有不同的公、私鑰；或表現(xiàn)在不同的密碼算法工作模式上，如對于安全性要求不高或強調(diào)處理速度的ECB、CTR工作模式，或?qū)Π踩砸筝^高的CBC、OFB、CFB模式等。如何對這些隨機交叉的安全服務(wù)請求進行正確且快速的處理，是海量數(shù)據(jù)安全服務(wù)請求必須要解決的問題。

目前，對于多算法交叉加解密的調(diào)度研究，多是在軟件或算法層面解決，通過軟件層面的調(diào)度實現(xiàn)業(yè)務(wù)數(shù)據(jù)在多算法核上的分配，且以非關(guān)聯(lián)數(shù)據(jù)的處理為主。軟件實現(xiàn)的調(diào)度方法具有處理靈活的優(yōu)點，但是速度提升有限，不能很好地滿足海量數(shù)據(jù)的快速、有效處理，影響用戶體驗。本文以云安全應(yīng)用下高性能密碼處理芯片的設(shè)計為研究背景，探討了在多算法交叉加解密服務(wù)需求下，采用帶有中間狀態(tài)管理的基于數(shù)據(jù)標識的分層硬件調(diào)度方法（HHS-ACDID）實現(xiàn)交叉業(yè)務(wù)請求下多算法、多密鑰、多IP核的隨機交叉加解密服務(wù)，實現(xiàn)數(shù)據(jù)大集中處理場景下業(yè)務(wù)的快速處理。

2 相關(guān)研究

目前，對于海量數(shù)據(jù)密碼應(yīng)用的研究和處理主要集中在多核并行處理架構(gòu)和密碼算法本身的高速并行實現(xiàn)上。并行處理架構(gòu)又分為以GPU為主的通用多核CPU架構(gòu)[1,2]和以密碼算法處理IP核為主的專用多核架構(gòu)。算法本身的并行高速實現(xiàn)主要集中在挖掘算法本身的并行性和算法的流水線實現(xiàn)2個方面，將算法的處理分為多個階段[3]，部分功能采用并行化的實現(xiàn)方式[4,5]，如模冪運算[6]或點乘算法[7]的并行化，以及對密鑰擴展模塊采用并行化的實現(xiàn)方式[8]。文獻[9]建立了以GPU為中心的流水線架構(gòu)模型，通過對GPU核的周期性調(diào)度，獲得可預(yù)期的GPU處理時間，但是并未考慮對交叉作業(yè)分組的處理，每個GPU核流水線處理的是同一業(yè)務(wù)的順序作業(yè)分組，其中，GPU的調(diào)度周期受限于最大作業(yè)分組的處理時間，且沒有涉及異構(gòu)核和關(guān)聯(lián)任務(wù)處理的問題。文獻[10]基于數(shù)據(jù)密態(tài)檢索采用的Gentry全同態(tài)加密，提出建立數(shù)據(jù)依賴圖解決上下文相關(guān)業(yè)務(wù)并行處理的方法。文獻[11]探討了一種虛擬化的軟件架構(gòu)，通過Dispatcher將數(shù)據(jù)送至不同的處理器實現(xiàn)對全同態(tài)加密算法的并行化處理。這些處理都是軟件層面的解決方案，調(diào)度的處理相對滯后，不能根據(jù)處理模塊的運行情況進行業(yè)務(wù)調(diào)度的實時處理。文獻[12]針對業(yè)務(wù)數(shù)據(jù)交叉加解密的思想，提出了在典型密碼處理器體系結(jié)構(gòu)上增設(shè)專用易失性存儲器、專用易失性存儲器控制器和索引寄存器的多線程密碼芯片的體系結(jié)構(gòu)，但并未對其進行實現(xiàn)與驗證。以密碼算法處理IP核為主的專用多核架構(gòu)采用一個系統(tǒng)內(nèi)部掛接多個密碼算法處理IP核[13]，通過指令級和數(shù)據(jù)級并行，最大化數(shù)據(jù)疊加流水處理，提高系統(tǒng)的吞吐率，加速算法數(shù)據(jù)處理速度，實現(xiàn)單一鏈接下的不同任務(wù)在不同工作模式下的多種密碼算法的并行處理[14～17]。這些研究成果雖然涉及了多密鑰多數(shù)據(jù)加解密以及單一密鑰多數(shù)據(jù)流加解密操作的技術(shù)，但是均未涉及不同業(yè)務(wù)作業(yè)流間存在隨機交叉加解密請求狀況的處理，且未考慮依賴數(shù)據(jù)的處理。

許多研究者在操作系統(tǒng)層面對異構(gòu)多核處理器下的任務(wù)調(diào)度算法進行了研究[18,19]，文獻[20]通過對嵌入式流媒體中數(shù)據(jù)相關(guān)任務(wù)建模，采用無環(huán)靜態(tài)數(shù)據(jù)流（CSDF）模型，實現(xiàn)了周期性任務(wù)的硬件調(diào)度。還有一些研究采用多任務(wù)調(diào)度算法實現(xiàn)任務(wù)在FPGA平臺上的分配，通過FPGA的可重構(gòu)特性，實現(xiàn)對FPGA資源的有效利用，從而達到計算靈活性和高速性的目的[21]。文獻[22]針對重構(gòu)時出現(xiàn)的開銷問題，提出混合映射的調(diào)度技術(shù)，利用應(yīng)用程序之間的關(guān)系來減少重構(gòu)產(chǎn)生的開銷。由于在多處理器上進行任務(wù)的分配是一個典型的NP問題，無法在多項式時間內(nèi)找到一個最優(yōu)的任務(wù)分配方案，因此，一些研究者采用啟發(fā)式算法或全局優(yōu)化技術(shù)，來尋找近似最優(yōu)解。文獻[23]提出了一種可搶占式調(diào)度的硬件實現(xiàn)方法，通過掃描路徑上的寄存器結(jié)構(gòu)，來暫停低優(yōu)先級任務(wù)，啟動高優(yōu)先級任務(wù)，設(shè)計實現(xiàn)了不影響其他任務(wù)執(zhí)行的低優(yōu)先級任務(wù)上下文保存和恢復(fù)電路。這些調(diào)度機制都是停留在理論仿真階段，并未提出與硬件架構(gòu)相配合的調(diào)度算法。硬件調(diào)度算法不僅具有運算速度快的特點，而且可以大大降低軟件調(diào)度算法設(shè)計的復(fù)雜度。

因此，根據(jù)高并發(fā)數(shù)據(jù)的處理特點，本文提出了基于數(shù)據(jù)標識的分層硬件調(diào)度機制，通過構(gòu)造具有特定標識的作業(yè)分組，采用專門的調(diào)度解析模塊進行作業(yè)分組的轉(zhuǎn)發(fā)，實現(xiàn)多個算法模塊間的并行運算，完成高并發(fā)多密鑰隨機交叉的密碼運算操作，提高了加解密效率。

3 問題描述

本文所研究的密碼系統(tǒng)包含有多種密碼算法，這里將不同的算法按簇進行劃分，每種算法對應(yīng)一個或多個能并行處理的IP核，稱為一個算法簇。若系統(tǒng)可以實現(xiàn)p種算法處理，ipik表示實現(xiàn)算法sj(1≤j≤p)的第k個處理單元，mj表示算法簇sj中的IP核數(shù)，即

不同的算法核對分組數(shù)據(jù)的處理速度可能不同。業(yè)務(wù)以作業(yè)分組的形式進入此多核密碼處理系統(tǒng)，密碼處理系統(tǒng)需要按照不同業(yè)務(wù)的不同處理需求將作業(yè)分組快速地分配至能進行對應(yīng)密碼運算的處理節(jié)點上。由于來自不同應(yīng)用請求的數(shù)據(jù)傳輸速度不同，因此，進入密碼處理系統(tǒng)的作業(yè)分組的先后順序不同，存在不同業(yè)務(wù)不同數(shù)據(jù)分組間的交叉現(xiàn)象。如圖1所示，Pia表示業(yè)務(wù)i的第a個作業(yè)分組，同一業(yè)務(wù)的2個連續(xù)作業(yè)分組Pia、Pi(a+1)間可能穿插有其他業(yè)務(wù)的作業(yè)分組。因此，在進行業(yè)務(wù)處理時，需要解決3個方面的問題。

1) 作業(yè)分組Pia的處理需求是什么，即要解決作業(yè)分組與處理節(jié)點間的映射關(guān)系。

2) 業(yè)務(wù)中間狀態(tài)的管理。這里稱同一業(yè)務(wù)最后一個作業(yè)分組之前的運算結(jié)果為中間狀態(tài)。在關(guān)聯(lián)業(yè)務(wù)的后序作業(yè)分組Pi(a+1)到來之前，Pia的運算結(jié)果Cia作為后續(xù)作業(yè)分組的中間狀態(tài)如何保存以及在后序作業(yè)分組Pi(a+1)到來之后，如何獲取中間狀態(tài)值Cia。

3) 若同一業(yè)務(wù)的作業(yè)分組間存在迭代關(guān)系，在前序作業(yè)分組未處理完之前，為保證系統(tǒng)處理的速度和系統(tǒng)入口作業(yè)流的不間斷，流水到來的后序作業(yè)分組如何處理。

圖1 不同業(yè)務(wù)流對多種密碼算法模塊的隨機交叉訪問

因此，為便于系統(tǒng)的正確處理，需要對進入系統(tǒng)的作業(yè)分組進行歸一化處理，使作業(yè)分組帶有算法、運算類型、算法工作模式等數(shù)據(jù)標識，此處將作業(yè)分組設(shè)定為

其中，taski表示業(yè)務(wù)號，用來標識數(shù)據(jù)的來源，對數(shù)據(jù)的處理沒有影響，但是決定著數(shù)據(jù)的正確返回；cmdi為處理命令，決定對數(shù)據(jù)的具體操作，如加密、解密、簽名、驗簽等；cypi為密碼算法模塊ID號，決定數(shù)據(jù)的處理節(jié)點；modei為密碼算法工作模式，決定對密碼算法處理節(jié)點入口數(shù)據(jù)的處理。對于ECB模式，可以將數(shù)據(jù)直接送入算法處理節(jié)點，而對于CBC模式，則需要將數(shù)據(jù)與同一個業(yè)務(wù)的前一組數(shù)據(jù)的運算結(jié)果進行異或后，再送入算法處理節(jié)點。No.為作業(yè)分組的序號，long為作業(yè)分組中運算數(shù)據(jù)的長度；dia為運算數(shù)據(jù)。

4 分層調(diào)度機制

上述的3個問題，實際上都可以歸結(jié)為調(diào)度問題，即作業(yè)分組在算法IP核的分配、分配的時機以及分配時數(shù)據(jù)分組的預(yù)處理。為了保證對業(yè)務(wù)流的快速處理，系統(tǒng)設(shè)計采用兩級調(diào)度機制，第一級調(diào)度完成作業(yè)分組與算法模塊處理節(jié)點間的映射，第二級調(diào)度根據(jù)作業(yè)分組間的依賴關(guān)系決定作業(yè)分組的調(diào)度順序，并獲取正確的密碼算法模塊入口數(shù)據(jù)。

調(diào)度模型如圖2所示，其中，schedule1為第一級調(diào)度模塊，根據(jù)cypi完成作業(yè)分組數(shù)據(jù)送入對應(yīng)的算法模塊簇；schedule2為第二級調(diào)度模塊，根據(jù)modei獲取正確的算法入口數(shù)據(jù)，送入IP核入口隊列。IP為粗粒度實現(xiàn)的密碼算法運算模塊，feedback為反饋模塊。每個模塊有自己的入口和出口隊列，其中，pre_queue為預(yù)處理隊列，IP_queue為IP核入口隊列，post_queue為處理后隊列。系統(tǒng)總的入口隊列接收隨機交叉流入的不同業(yè)務(wù)數(shù)據(jù)，入口隊列由所有的IP核共享，出口隊列的數(shù)據(jù)被分配至不同的CPU進程。此架構(gòu)采用作業(yè)級并行JLP（job-level parallelism）的粗粒度并行方式[8]，各模塊間采用分段總線互連的方式。由于所有的數(shù)據(jù)處理模塊均有自己的本地緩沖隊列，可以獨立運行，從而克服了存儲器間的競爭，實現(xiàn)了同一業(yè)務(wù)多個作業(yè)分組的同時處理，避免資源約束造成的作業(yè)流處理時滯和效率問題；同時增加算法IP核不會對其他操作造成影響，便于進行系統(tǒng)的線性擴展。

在這種調(diào)度方式下，cypi的設(shè)計如圖2所示，其中，高m位表示簇號，低n位表示簇內(nèi)的算法處理節(jié)點號。

4.1 第一級調(diào)度

第一級調(diào)度由schedule1模塊完成，算法調(diào)度模塊schedule1提取input_queue中的數(shù)據(jù)，通過對作業(yè)分組cypi的解析，獲取算法類型，將數(shù)據(jù)分發(fā)至相應(yīng)算法的預(yù)處理隊列實現(xiàn)數(shù)據(jù)的分流，保證作業(yè)分組與算法間映射的正確性。若作業(yè)分組中表示運算數(shù)據(jù)長度的標識long以字節(jié)為單位，系統(tǒng)中的分段總線寬度為wbit，則除分組頭外，運算數(shù)據(jù)的讀取至少需要個時鐘。調(diào)度算法如下。

1) 若input_queue隊列非空，則從input_queue中讀取作業(yè)分組頭數(shù)據(jù)。

2) 對分組頭數(shù)據(jù)進行解析，獲取處理節(jié)點簇號cluster_id和作業(yè)分組長度數(shù)據(jù)。

3) 根據(jù)cluster_id檢索預(yù)處理隊列索引表，并將分組頭數(shù)據(jù)送對應(yīng)的預(yù)處理隊列；否則，cluster_id為非法的算法簇號，數(shù)據(jù)送ERROR_FIFO。

4) 若長度計數(shù)器中的值與長度寄存器中的值不同，則input_queue中的數(shù)據(jù)送pre_queue；否則，進入步驟6)。

6) 返回步驟1)。

在此調(diào)度算法中，除步驟3)外，其余的步驟都可在單個時鐘完成。而步驟3)根據(jù)抽取的cluster_id進行數(shù)據(jù)的分轉(zhuǎn)，若系統(tǒng)中的算法類型共有n種，則預(yù)處理隊列索引表的長度為n，軟件遍歷的方式最多需要耗費n個時鐘，大大影響數(shù)據(jù)傳輸?shù)男省；谏⒘械臋z索方式，由于存在沖突碰撞現(xiàn)象，也存在效率不高的問題。這里考慮硬件解決方案，由于作業(yè)分組對密碼算法的請求具有唯一性，因此，cluster_id至多只能與pre_queue索引表中的一個表項一致，多于一個表項相同的現(xiàn)象是不可能存在的，可以將其作為無關(guān)項對邏輯操作進行優(yōu)化。假設(shè)cluster_id=x，pre_queue索引表中共有3個索引項a、b、c，“^”表示異或操作，“|”表示邏輯或操作，y表示x與哪個索引項匹配，則x與a、b、c之間的關(guān)系只能有如表1所示的4種情況。

圖2 多核并行流水線密碼處理調(diào)度模型

表1 簇索引查找真值

根據(jù)y值可以快速地將數(shù)據(jù)分轉(zhuǎn)至不同的簇隊列pre_queue中。分簇調(diào)度的方式，使調(diào)度時的對比位數(shù)有效減少，平均減少為原位數(shù)的，若系統(tǒng)共實現(xiàn)8種密碼算法，每種密碼算法有8個處理節(jié)點，共64個處理節(jié)點，若采用一級調(diào)度的方式，則索引項的位寬為6，而采用兩級調(diào)度的方式，在處理節(jié)點的分配上，每級索引項的位寬為3 bit，提高了以4輸入查找表為單元的FPGA布局的靈活性，同時，此種硬件檢索比較邏輯可以使索引表的時間復(fù)雜度降為O(1)，沒有碰撞沖突，且不影響系統(tǒng)的工作頻率，很好地解決了數(shù)據(jù)分轉(zhuǎn)調(diào)度效率低的問題。

4.2 第二級調(diào)度

第二級調(diào)度是保證交叉訪問正確性的關(guān)鍵環(huán)節(jié)，由pre_process模塊完成，通過對作業(yè)分組工作狀態(tài)的判斷，確定作業(yè)分組調(diào)度的時間順序，并獲得算法模塊的輸入數(shù)據(jù)。由于輸入隊列業(yè)務(wù)間的隨機交叉性和IP核間的異構(gòu)性，不能保證具有上下文相關(guān)的作業(yè)分組在進行處理時，其前序作業(yè)分組已處理完。假設(shè)pre_queue的作業(yè)分組序列為{P11,P21,P31,P12,P22}，如表2所示，IP核內(nèi)密碼算法的處理采用流水線的方式。

表2 預(yù)處理隊列作業(yè)分組序列

如圖3所示，在圖3(a)中，由于不同業(yè)務(wù)的作業(yè)分組間相互獨立，節(jié)點對數(shù)據(jù)的處理采用流水線的方式，P11、P21、P31這3個業(yè)務(wù)流的第一個作業(yè)分組依次從pre_queue中輸出，進入對應(yīng)的處理節(jié)點。由于P11的工作模式為CBC，作業(yè)分組間存在迭代關(guān)系，后序作業(yè)分組P12的處理必須等到P11運算結(jié)果輸出的時刻才能進行，從而阻滯了P22的讀取。如果能將P12旁路掉，在P11運算完成后再取出，則可以在保證正確性的前提下，加速后序其他業(yè)務(wù)作業(yè)分組的處理，如圖3(b)所示。因此，本系統(tǒng)在架構(gòu)中針對每一個算法簇在預(yù)處理模塊前端增加關(guān)聯(lián)控制模塊和關(guān)聯(lián)隊列（relate_queue），如圖4所示。

圖3 作業(yè)分組在處理節(jié)點上的分配

1) 關(guān)聯(lián)控制模塊

關(guān)聯(lián)控制模塊通過維護關(guān)聯(lián)ID表，實現(xiàn)對關(guān)聯(lián)作業(yè)分組調(diào)度次序的控制。關(guān)聯(lián)ID表為正在進行處理的關(guān)聯(lián)任務(wù)作業(yè)分組的索引表，這里以關(guān)聯(lián)作業(yè)分組的ID號taski為索引項。

① 關(guān)聯(lián)ID表項的追加：任何一個進入預(yù)處理模塊（IP_CTRL）的關(guān)聯(lián)作業(yè)分組，都要將其ID號存入關(guān)聯(lián)ID表。

② 關(guān)聯(lián)ID表項的刪除：任何一個從算法運算模塊輸出的關(guān)聯(lián)作業(yè)分組，都要通過req信號通知關(guān)聯(lián)控制模塊，關(guān)聯(lián)控制模塊通過提取此作業(yè)分組的taski，并與關(guān)聯(lián)ID表中的ID號進行對比，若相同，則將此ID號從關(guān)聯(lián)ID表中刪除。

2) 關(guān)聯(lián)隊列

關(guān)聯(lián)隊列用于保存正在進行運算的關(guān)聯(lián)作業(yè)分組的后續(xù)作業(yè)分組，保證后續(xù)作業(yè)分組的正常讀取。

① 關(guān)聯(lián)隊列的輸入：當預(yù)處理隊列非空時，關(guān)聯(lián)控制模塊從預(yù)處理隊列中提取作業(yè)分組頭，首先根據(jù)modei是否為CBC|OFB|CFB，判斷此作業(yè)是否為依賴作業(yè)；其次，提取依賴作業(yè)的ID號taski，與關(guān)聯(lián)ID表中的ID號進行對比，若相同，則啟動關(guān)聯(lián)控制開關(guān)s1，將此作業(yè)分組放入關(guān)聯(lián)隊列中；否則，將此作業(yè)分組送入預(yù)處理模塊。

圖4 第二級調(diào)度模塊內(nèi)部邏輯

② 關(guān)聯(lián)隊列的輸出：每個IP模塊在運算完一個關(guān)聯(lián)作業(yè)分組后，都會向關(guān)聯(lián)控制模塊輸出一個req信號以及作業(yè)分組的ID號。關(guān)聯(lián)控制模塊接收此ID號，并對關(guān)聯(lián)ID表進行遍歷查詢，若存在相同的ID號，控制關(guān)聯(lián)選擇開關(guān)s2將此ID號對應(yīng)的作業(yè)分組從關(guān)聯(lián)隊列送入cypi指定的預(yù)處理模塊；否則，丟棄此ID號。

第二級調(diào)度算法如下。

1) 若pre_queue非空，則關(guān)聯(lián)控制模塊從pre_queue中讀取作業(yè)分組頭數(shù)據(jù)。

2) 關(guān)聯(lián)控制模塊對分組頭數(shù)據(jù)進行解析，獲取inter_ipid號、作業(yè)分組長度和算法工作模式。若modei=ECB，則同一業(yè)務(wù)不同作業(yè)分組間沒有關(guān)聯(lián)關(guān)系，控制選擇開關(guān)s1將數(shù)據(jù)送data_reg；若modei為CBC|OFB|CFB，則此作業(yè)分組為關(guān)聯(lián)作業(yè)分組，將taski與關(guān)聯(lián)ID表進行對比，若存在相同的ID號，則控制選擇開關(guān)s1將數(shù)據(jù)送relate_queue；否則，此作業(yè)分組為關(guān)聯(lián)任務(wù)的第一個作業(yè)分組，數(shù)據(jù)送data_reg，同時，將此作業(yè)分組的taski追加至關(guān)聯(lián)ID表中。

3) 若關(guān)聯(lián)控制模塊沒有收到req請求，則選擇開關(guān)s2根據(jù)請求的inter_ipid號將data_reg中的數(shù)據(jù)送入IP_CTRL模塊進行運算前的準備；否則s2模塊根據(jù)請求的inter_ipid號，從relate_queue中選取具有相同taski的作業(yè)分組送入IP_CTRL模塊。

4) 預(yù)處理模塊為算法的運算做準備，用于獲取IP核運算需要的數(shù)據(jù)，包括key和IV，并將數(shù)據(jù)送密碼算法入口隊列。

兩級調(diào)度算法保證了具有上下文相關(guān)的作業(yè)分組處理時的正確性，同時，其他業(yè)務(wù)的作業(yè)分組可以在某個關(guān)聯(lián)業(yè)務(wù)作業(yè)分組的流水處理過程中，進入流水處理階段，實現(xiàn)了數(shù)據(jù)處理的不斷線。

5 中間狀態(tài)管理

在不同業(yè)務(wù)流的作業(yè)分組隨機交叉下傳的過程中，不能保證同一業(yè)務(wù)作業(yè)分組的連續(xù)性，也不能保證關(guān)聯(lián)業(yè)務(wù)的后序作業(yè)分組Pi(a+1)恰好出現(xiàn)在Pia運算完成時，因此，必須將其運算結(jié)果Cia暫存起來，以備后序作業(yè)分組到來時使用?？紤]到數(shù)據(jù)傳輸?shù)目煽啃?，這里，對所有業(yè)務(wù)的中間狀態(tài)均進行保存，在系統(tǒng)中增加密鑰和中間狀態(tài)寄存器KSM，用于保存各作業(yè)分組的密鑰以及不同作業(yè)分組運算過程中生成的中間狀態(tài)數(shù)據(jù)。如圖5所示，為了保證密鑰、中間狀態(tài)與作業(yè)分組間的對應(yīng)關(guān)系，以業(yè)務(wù)唯一標識號taski為指針，進行密鑰、中間狀態(tài)的存儲與獲取。算法處理模塊IP在輸出運算結(jié)果的同時，將運算結(jié)果連同其密鑰key一起以taski為存儲地址存入KSM中，即每個業(yè)務(wù)流有唯一的KSM地址，從而保證中間狀態(tài)數(shù)據(jù)提取的正確性。作業(yè)分組在進入算法處理隊列IP_queue前，算法預(yù)處理模塊首先根據(jù)作業(yè)分組頭中的taski獲取本作業(yè)分組需要的key和中間狀態(tài)，并根據(jù)運算模式modei獲得正確的算法模塊入口數(shù)據(jù)。

在這種處理方式下，由于數(shù)據(jù)的調(diào)度順序，入口數(shù)據(jù)與初始向量間的運算都已在數(shù)據(jù)進入算法模塊入口隊列之前完成，所以算法模塊的功能相對單一，僅僅專注于密碼運算，所以可以方便地進行模塊的線性擴展。同時，這種設(shè)置降低了傳輸過程中因意外或出錯導(dǎo)致的上下文相關(guān)的數(shù)據(jù)運算的重傳量。如若某業(yè)務(wù)的第i分組數(shù)據(jù)在傳輸時發(fā)生了錯誤，由于第i–1分組數(shù)據(jù)已正確傳輸，且運算結(jié)果保存在KSM中，所以不需要對整個業(yè)務(wù)作業(yè)流進行重傳，只需要從第i分組開始重傳即可。每個作業(yè)分組根據(jù)其ID號，即可獲知運算的密鑰，并自動切換至其前序作業(yè)分組的加解密狀態(tài)，保證了上下文相關(guān)的作業(yè)分組間數(shù)據(jù)的正確性，避免數(shù)據(jù)傳輸延遲，實現(xiàn)數(shù)據(jù)、密鑰、中間狀態(tài)間的同步，提高了業(yè)務(wù)處理的快速性。

圖5 算法中間狀態(tài)的處理

6 性能分析及原型測試

6.1 性能分析

第一級調(diào)度通過cluster_id與簇索引表的對比獲得作業(yè)分組與處理節(jié)點間的映射關(guān)系，采用硬件的實現(xiàn)方式，可以實現(xiàn)時間復(fù)雜度為O(1)的檢索速度，用t1表示第一級的調(diào)度時間。第二級調(diào)度的預(yù)處理包括2個環(huán)節(jié)，關(guān)聯(lián)判斷、入口數(shù)據(jù)獲取，其處理時間分別用t21、t22表示。若系統(tǒng)中共包含4種密碼算法，共8個算法IP核，其中，每種密碼算法實現(xiàn)有2個IP核，每種算法的處理時間依次用t31、t32、t33、t34表示，反饋時間用t4表示。若t1=1,t21=1,t22=2,t31=18,t32=32,t33=16,t34=64,t4=3，請求密碼處理的業(yè)務(wù)固定為100個，隨機生成分屬于100個業(yè)務(wù)的不同個數(shù)的作業(yè)分組，對作業(yè)流的調(diào)度時間與輪詢調(diào)度(RR,round-robin)進行對比分析，結(jié)果如圖6所示。

圖6 4×2算法IP核下調(diào)度算法性能對比

由圖6可知，隨著隨機交叉進入系統(tǒng)的作業(yè)分組的數(shù)量增多，調(diào)度時間的減少呈增大趨勢，圖7所示為4種共16個算法IP核在同樣的作業(yè)流條件下與8個算法性能比較的仿真測試結(jié)果，可見隨著處理節(jié)點的增多，總的調(diào)度時間呈倍數(shù)減少。

圖7 4×4與4×2算法IP核下調(diào)度算法性能對比

圖8 兩級調(diào)度仿真結(jié)果

6.2 實現(xiàn)及測試

為驗證調(diào)度方法的正確性，本文采用Verilog語言在Xilinx XC7K325t FPGA上對上述調(diào)度算法進行了設(shè)計實現(xiàn)，并通過在FPGA上實現(xiàn)不同數(shù)量的算法IP核，對處理速度進行了測試。圖8給出了2個SM2、2個SM3和1個SM4算法核情況下，業(yè)務(wù)數(shù)據(jù)以隨機交叉的方式進入系統(tǒng)時的兩級調(diào)度仿真結(jié)果，其中，a_od2_fifo_wr、b_od2_fifo_wr為2個SM2算法模塊的入口FIFO寫信號，a_od2_stb_en、b_od2_stb_en為作業(yè)分組寫完成信號，od3_fifo_wr、od4_fifo_wr分別為SM3、SM4算法模塊的入口FIFO寫信號，od3_stb_en、od4_stb_en為對應(yīng)算法模塊作業(yè)分組寫完成信號，從圖8可以看出此方案實現(xiàn)了對不同業(yè)務(wù)、不同長度作業(yè)分組的正確調(diào)度。

在原型系統(tǒng)下對系統(tǒng)處理數(shù)據(jù)的速度進行測試，圖9所示為采用2個和3個SM2核，線程數(shù)分別為32、64、128和256時簽名、驗簽的速度。

圖9 算法核和線程數(shù)量不同時SM2簽名、驗簽速率

測試證明當采用2個SM2核時，SM2的簽名速度可以到達每秒14 000次以上。Safenet公司的高性能硬件安全模塊（HSM）：Luna PCI-E 7 000每秒可執(zhí)行7 000次RSA 1 024位交易，本設(shè)計下的簽名達到其2倍以上的運算速度，并且在某一算法處理節(jié)點數(shù)量不變的情況下，改變處理線程數(shù)，作業(yè)流的處理速度不受影響。當增加算法的處理節(jié)點數(shù)量時，業(yè)務(wù)流的處理速度近似線性增加。

圖10為采用不同的線程數(shù)下發(fā)相同數(shù)據(jù)量的作業(yè)流進行SM4加密處理時吞吐率，可以看出隨著線程數(shù)的增加，SM4算法的處理速度有所增長，由于在相同數(shù)據(jù)量的前提下，線程數(shù)的增多，意味著相互獨立的任務(wù)數(shù)增多，關(guān)聯(lián)檢索操作相應(yīng)減少，從而提高了數(shù)據(jù)處理的吞吐率。文獻[18]采用6個IP核在FPGA上實現(xiàn)AES算法，時鐘頻率為177.9 MHz，處理速度為5.6 Gbit/s。本文在作業(yè)流隨機交叉加解密的情況下SM4算法的實現(xiàn)速度是其1.2倍以上。

當在FPGA上實現(xiàn)的算法核的種類和個數(shù)分別為3SM2+2SM3+SM4時，LUT的占用率為43%，Registers的占用率為24%，Logic Distribution的占用率為66%，RAM的占用率為78%，系統(tǒng)能夠?qū)崿F(xiàn)的最高工作頻率為175 MHz，總功耗為4.927 W。

圖10 相同數(shù)據(jù)量、不同線程數(shù)下SM4加密處理速度

7 結(jié)束語

本文設(shè)計的多密碼算法隨機作業(yè)流硬件調(diào)度方法相對于軟件調(diào)度算法具有調(diào)度速度快的優(yōu)勢，能夠?qū)崟r地根據(jù)底層密碼模塊的運算速度進行作業(yè)流的調(diào)度，保證了密碼模塊服務(wù)的高效性，同時簡化了上層應(yīng)用程序的處理。根據(jù)特定的作業(yè)分組業(yè)務(wù)標識，兩級調(diào)度機制以流水線的方式保證了密碼服務(wù)設(shè)備入口數(shù)據(jù)流的高速不阻塞輸入。關(guān)聯(lián)控制和中間狀態(tài)管理模塊的引入保證了入口數(shù)據(jù)流高速接收前提下不同工作模式數(shù)據(jù)的正確調(diào)度，從而滿足了多算法、多IP核、多作業(yè)流隨機交叉情況下的密碼服務(wù)需求，解決了單一芯片支持多算法、多IP核的并行運算的高并發(fā)處理問題。采用此調(diào)度方法實現(xiàn)面向云計算的高性能綜合密碼系統(tǒng)，其中，多核加解密的實現(xiàn)采用Xilinx XC7K325t FPGA，在單芯片的情況下，可以支持4 900萬個密碼線程和35億個并發(fā)應(yīng)用，SM4加解密性能達到6.4 Gbit/s、SM3雜湊性能達到1.1 Gbit/s、SM2簽名速率達到10 000次/秒以上、SM2驗簽速率達到2 700次/秒。

參考文獻：

[1]王蕾,崔慧敏,陳莉,等.任務(wù)并行編程模型研究與進展[J].軟件學(xué)報,2013,24(1):77-90.WANG L,CUI H M,CHEN L,et al.Research on task parallel programming model[J].Journal of Software,2013,24(1):77-90.

[2]SEOG C S,JUNG H P,DONG H L,et al.An efficient implementation of KCDSA on graphic processing units[C]//2011 Fifth FTRA International Conference on Multimedia and Ubiquitous Engineering.2011:167-172.

[3]QIU C,LU Y Q,GAO P D,et al.A parallel bulk loading algorithm for m-tree on multi-core CPU[C]//2010 Third International Joint Conference on Computational Science and Optimization.2010:300-303.

[4]SATOH A.High-speed parallel hardware architecture for galois counter mode[C]//2007 IEEE International Symposium on Circuits and Systems.2007:1863-1866.

[5]WU F,WANG L,WAN J G.A low cost and inner-round pipelined design of ECB-AES-256 crypto engine for solid state disk[C]//2010 IEEE Fifth International Conference on Networking,Architecture,and Storage.2010:485-491.

[6]LARA P,BORGES F,PORTUGAL R,et al.Parallel modular exponentiation using load balancing without precomputation[J].Journal of Computer &System Sciences,2012,78(2):575-582.

[7]AMINI E,JEDDI Z,BAYAYOUMI M.A high-throughput ECC architecture[C]//2012 19th IEEE International Conference on Electronics,Circuits,and Systems.2012:901-904.

[8]MOZAFFARI K M,REYHANI M A.Efficient and high-performance parallel hardware architectures for the AES-GCM[J].IEEE Transactions on Computers,2012,61(8):1165-1178.

[9]ZHANG K,HU J Y,HUA B.A holistic approach to build real-time stream processing system with GPU[J].Journal of Parallel and Distributed Computing,2015,83:44-57.

[10]HAYWARD R,CHIANG C C.Parallelizing fully homomorphic encryption[C]//2014 International Symposium on Computer,Consumer and Control.2014:721-724.

[11]HAYWARD R,CHIANG C C.An architecture for parallelizing fully homomorphic cryptography on cloud[C]//2013 Seventh International Conference on Complex,Intelligent,and Software Intensive Systems.2013:72-77.

[12]李鳳華.分布式信息系統(tǒng)安全的理論與關(guān)鍵技術(shù)研究[D].西安電子科技大學(xué),2009.LI F H.Theory and key technologies for the security in distributed information systems[D].Xidian University,2009.

[13]HUANG W,HAN J,WANG S A,et al.A low-complexity heterogeneous multi-core platform for security soc[C]//2010 IEEE Asian Solid-State Circuits Conference.2010:1-4.

[14]LIU Q,XU Z,YUAN Y.High throughput and secure advanced encryption standard on field programmable gate array with fine pipelining and enhanced key expansion[J].IET Computers &Digital Techniques,2015,9(3):175-184.

[15]WANG M Y,SU C P,HORNG C L,et al.Single- and multi-core configurable AES architectures for flexible security[J].IEEE Transactions on Very Large Scale Integration Systems,2010,18(4):541-552.

[16]XIAO L,LI Y,RUAN L,et al.High performance implementation of aria encryption algorithm on graphics processing units[C]//IEEE International Conference on High Performance Computing &Communications &IEEE International Conference on Embedded &Ubiquitous Computing.2013:504 - 510.

[17]方躍堅,沈晴霓,吳中海.一種超橢圓曲線密碼處理器并行結(jié)構(gòu)設(shè)計[J].計算機研究與發(fā)展,2013,11:2383-2388.FANG Y J,SHEN Q N,WU Z H.A parallel architecture for FPGA based hyperelliptic curve cryptoprocessor[J].Journal of Computer Research and Development,2013,50(11):2383-2388.

[18]XUAN K D,LOUISE S,COHEN A.Managing the latency of data-dependent tasks in embedded streaming applications[C]//2015 IEEE 9th International Symposium on Embedded Multicore/Many-core Systems-on-Chip.2015:9-16.

[19]CHEN W,FEKETE K,YOUNG C L.Exploiting deadline flexibility in Grid workflow rescheduling[C]//2010 11th IEEE/ACM International Conference on Grid Computing.2010:105-112.

[20]SPASIC J,LIU D,CANELLA E,et al.Improved hard real-time scheduling of CSDF-modeled streaming applications[C]//2015 International Conference on Hardware/Software Codesign and System Synthesis.2015:65-74.

[21]BAMAKHRAMA M,STEFANOY T.Hard-real-time scheduling of data-dependent tasks in embedded streaming applications[C]//The Ninth ACM International Conference on Embedded Software.2011:195-204.

[22]CLEMENTE J A,RANA V,SCIUTO D,et al.A hybrid mapping-scheduling technique for dynamically reconfigurable hardware[C]//2011 21st International Conference on Field Programmable Logic and Applications.2011:177-180.

[23]JOVANOVIC S,TANOUGAST C,WEBER S.A hardware preemptive multitasking mechanism based on scan-path register structure for FPGA-based reconfigurable systems[C]//Second NASA/ESA Conference on Adaptive Hardware and Systems.2007:358-364.

李莉（1974-），女，山東青島人，西安電子科技大學(xué)博士生，北京電子科技學(xué)院副教授、碩士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)與系統(tǒng)安全、嵌入式系統(tǒng)安全應(yīng)用。

史國振（1974-），男，河南濟源人，博士，北京電子科技學(xué)院副教授、碩士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)與系統(tǒng)安全、嵌入式安全。

耿魁（1989-），男，湖北紅安人，博士，中國科學(xué)院信息工程研究所助理研究員，主要研究方向為網(wǎng)絡(luò)安全。

董秀剛（1976-），男，山東莒縣人，北京電子科技學(xué)院講師，主要研究方向為信息安全、密碼工程實現(xiàn)。

王璇（1991-），女，山東菏澤人，西安電子科技大學(xué)碩士生，主要研究方向為多核調(diào)度。

李鳳華（1966-），男，湖北浠水人，博士，中國科學(xué)院信息工程研究所副總工程師、研究員、博士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)與系統(tǒng)安全、隱私計算、可信計算。

Stochastic job stream scheduling method for cipher chip with multi-cryptography

LI Li1,2,SHI Guo-zhen3,GENG Kui4,DONG Xiu-ze2,WANG Xuan1,LI Feng-hua4
(1.College of Communication Engineering,Xidian University,Xi'an 710071,China;2.Department of Electronic and Information Engineering,Beijing Electronics Science and Technology Institute,Beijing 100070,China;3.Department of Information Security,Beijing Electronic Science and Technology Institute,Beijing 100070,China;4.State Key Laboratory of Information Security,Institute of Information Engineering,CAS,Beijing 100093,China)

Aiming at the rich of safety requirements of tasks which resulting in random cross access to multi cipher algorithms,a hierarchical hardware scheduling method was presented with associated control based on data identification.The first level was responsible for distributing tasks to different cipher clusters,and by optimizing the search logic to achieve rapid distribution of data.The second level was responsible for completing the context-related tasks in scheduling order by adding an association control module and association queues.Intermediate state storage module realized the saving of the intermediate state in serial cipher algorithm modes,which was indexed by task ID.Pre-processing module process data inputted by the succeeding tasks.It is proved that the proposed scheduling algorithm solves the problem of random cross encryption and decryption in many-to-many communication model of high-speed data stream.

cross encryption and decryption,job stream scheduling,multi-cryptography,cipher chip,hardware scheduling

s:The National Key Research and Development Project (No.2016YFB0800304),The Natural Science Foundation of Beijing (No.4152048),The Major Science and Technology Project of Press and Publication (No.1681300000119)

TP393.2

A

10.11959/j.issn.1000-436x.2016275

2016-08-29；

2016-10-25

李鳳華，lfh@iie.ac.cn

國家重點研發(fā)計劃基金資助項目（No.2016YFB0800304）；北京市自然科學(xué)基金資助項目（No.4152048）；新聞出版重大科技工程基金資助項目（No.1681300000119）