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

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

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

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

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

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

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

1 引言

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

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

2 相關(guān)研究

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

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

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

3 問題描述

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

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

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

2) 業(yè)務(wù)中間狀態(tài)的管理。這里稱同一業(yè)務(wù)最后一個(gè)作業(yè)分組之前的運(yùn)算結(jié)果為中間狀態(tài)。在關(guān)聯(lián)業(yè)務(wù)的后序作業(yè)分組Pi(a+1)到來之前，Pia的運(yùn)算結(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ù)流對多種密碼算法模塊的隨機(jī)交叉訪問

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

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

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

上述的3個(gè)問題，實(shí)際上都可以歸結(jié)為調(diào)度問題，即作業(yè)分組在算法IP核的分配、分配的時(shí)機(jī)以及分配時(shí)數(shù)據(jù)分組的預(yù)處理。為了保證對業(yè)務(wù)流的快速處理，系統(tǒng)設(shè)計(jì)采用兩級調(diào)度機(jī)制，第一級調(diào)度完成作業(yè)分組與算法模塊處理節(jié)點(diǎn)間的映射，第二級調(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核入口隊(duì)列。IP為粗粒度實(shí)現(xiàn)的密碼算法運(yùn)算模塊，feedback為反饋模塊。每個(gè)模塊有自己的入口和出口隊(duì)列，其中，pre_queue為預(yù)處理隊(duì)列，IP_queue為IP核入口隊(duì)列，post_queue為處理后隊(duì)列。系統(tǒng)總的入口隊(duì)列接收隨機(jī)交叉流入的不同業(yè)務(wù)數(shù)據(jù)，入口隊(duì)列由所有的IP核共享，出口隊(duì)列的數(shù)據(jù)被分配至不同的CPU進(jìn)程。此架構(gòu)采用作業(yè)級并行JLP（job-level parallelism）的粗粒度并行方式[8]，各模塊間采用分段總線互連的方式。由于所有的數(shù)據(jù)處理模塊均有自己的本地緩沖隊(duì)列，可以獨(dú)立運(yùn)行，從而克服了存儲(chǔ)器間的競爭，實(shí)現(xiàn)了同一業(yè)務(wù)多個(gè)作業(yè)分組的同時(shí)處理，避免資源約束造成的作業(yè)流處理時(shí)滯和效率問題；同時(shí)增加算法IP核不會(huì)對其他操作造成影響，便于進(jìn)行系統(tǒng)的線性擴(kuò)展。

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

4.1 第一級調(diào)度

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

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

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

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

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

6) 返回步驟1)。

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

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

表1 簇索引查找真值

根據(jù)y值可以快速地將數(shù)據(jù)分轉(zhuǎn)至不同的簇隊(duì)列pre_queue中。分簇調(diào)度的方式，使調(diào)度時(shí)的對比位數(shù)有效減少，平均減少為原位數(shù)的，若系統(tǒng)共實(shí)現(xiàn)8種密碼算法，每種密碼算法有8個(gè)處理節(jié)點(diǎn)，共64個(gè)處理節(jié)點(diǎn)，若采用一級調(diào)度的方式，則索引項(xiàng)的位寬為6，而采用兩級調(diào)度的方式，在處理節(jié)點(diǎn)的分配上，每級索引項(xiàng)的位寬為3 bit，提高了以4輸入查找表為單元的FPGA布局的靈活性，同時(shí)，此種硬件檢索比較邏輯可以使索引表的時(shí)間復(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í)間順序，并獲得算法模塊的輸入數(shù)據(jù)。由于輸入隊(duì)列業(yè)務(wù)間的隨機(jī)交叉性和IP核間的異構(gòu)性，不能保證具有上下文相關(guān)的作業(yè)分組在進(jìn)行處理時(shí)，其前序作業(yè)分組已處理完。假設(shè)pre_queue的作業(yè)分組序列為{P11,P21,P31,P12,P22}，如表2所示，IP核內(nèi)密碼算法的處理采用流水線的方式。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) 關(guān)聯(lián)控制模塊對分組頭數(shù)據(jù)進(jìn)行解析，獲取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表進(jìn)行對比，若存在相同的ID號，則控制選擇開關(guān)s1將數(shù)據(jù)送relate_queue；否則，此作業(yè)分組為關(guān)聯(lián)任務(wù)的第一個(gè)作業(yè)分組，數(shù)據(jù)送data_reg，同時(shí)，將此作業(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模塊進(jìn)行運(yùn)算前的準(zhǔn)備；否則s2模塊根據(jù)請求的inter_ipid號，從relate_queue中選取具有相同taski的作業(yè)分組送入IP_CTRL模塊。

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

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

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

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

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

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

6 性能分析及原型測試

6.1 性能分析

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

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

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

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

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

6.2 實(shí)現(xiàn)及測試

為驗(yàn)證調(diào)度方法的正確性，本文采用Verilog語言在Xilinx XC7K325t FPGA上對上述調(diào)度算法進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)，并通過在FPGA上實(shí)現(xiàn)不同數(shù)量的算法IP核，對處理速度進(jìn)行了測試。圖8給出了2個(gè)SM2、2個(gè)SM3和1個(gè)SM4算法核情況下，業(yè)務(wù)數(shù)據(jù)以隨機(jī)交叉的方式進(jìn)入系統(tǒng)時(shí)的兩級調(diào)度仿真結(jié)果，其中，a_od2_fifo_wr、b_od2_fifo_wr為2個(gè)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可以看出此方案實(shí)現(xiàn)了對不同業(yè)務(wù)、不同長度作業(yè)分組的正確調(diào)度。

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

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

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

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

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

參考文獻(xiàn)：

[1]王蕾,崔慧敏,陳莉,等.任務(wù)并行編程模型研究與進(jìn)展[J].軟件學(xué)報(bào),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ān),沈晴霓,吳中海.一種超橢圓曲線密碼處理器并行結(jié)構(gòu)設(shè)計(jì)[J].計(jì)算機(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)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與系統(tǒng)安全、嵌入式系統(tǒng)安全應(yīng)用。

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

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

董秀剛（1976-），男，山東莒縣人，北京電子科技學(xué)院講師，主要研究方向?yàn)樾畔踩⒚艽a工程實(shí)現(xiàn)。

王璇（1991-），女，山東菏澤人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槎嗪苏{(diào)度。

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

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

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