基于可分負(fù)載理論的多核密碼處理器調(diào)度研究

郎俊豪，李偉，陳韜，南龍梅

（戰(zhàn)略支援部隊(duì)信息工程大學(xué)，鄭州 450000）

0 概述

隨著5G 技術(shù)、云計(jì)算、物聯(lián)網(wǎng)等迅速發(fā)展，海量邊緣設(shè)備的增加使網(wǎng)絡(luò)數(shù)據(jù)量劇增，數(shù)據(jù)算力需求越來(lái)越高。邊緣計(jì)算是緩解數(shù)據(jù)中心壓力，滿足算力需求的重要方式，但由于靠近用戶端，其安全問(wèn)題成為網(wǎng)絡(luò)安全的關(guān)鍵。密碼算法是網(wǎng)絡(luò)安全的基石，由于邊緣設(shè)備異構(gòu)性、實(shí)時(shí)性等要求［1］，以及密碼算法的計(jì)算密集性，因此設(shè)計(jì)高能效且同時(shí)滿足性能與能耗兩方面需求的多核密碼處理器越來(lái)越受到人們的關(guān)注。任務(wù)調(diào)度機(jī)制通過(guò)分配待處理數(shù)據(jù)給各個(gè)密碼處理器核，進(jìn)而挖掘處理器并行性能潛力，提升計(jì)算效能，是高能效多核密碼處理器設(shè)計(jì)的關(guān)鍵。

可分負(fù)載理論（Divisible Load Theory，DLT）在過(guò)去幾十年被廣泛應(yīng)用于并行計(jì)算領(lǐng)域［2］，提升多核處理器平臺(tái)的調(diào)度性能。DLT 指總?cè)蝿?wù)數(shù)據(jù)（或稱任務(wù)負(fù)載），可被劃分成任意尺寸，且各劃分部分?jǐn)?shù)據(jù)無(wú)依賴關(guān)系，可被同時(shí)處理，其目標(biāo)是最小化負(fù)載處理時(shí)間。視頻編解碼［3］、大數(shù)據(jù)科學(xué)計(jì)算［4］等并行應(yīng)用中常會(huì)基于可分負(fù)載理論調(diào)度任務(wù)數(shù)據(jù)。對(duì)于多核密碼處理器，單密碼算法的數(shù)據(jù)相關(guān)性較強(qiáng)，為提升多核并行度，大多采用單核實(shí)現(xiàn)單算法及大數(shù)據(jù)量的密碼任務(wù)處理模式，任務(wù)數(shù)據(jù)可以被任意劃分（最小為密碼算法單次處理長(zhǎng)度）。因此，可分負(fù)載理論可應(yīng)用于多核密碼處理器的調(diào)度機(jī)制研究，基于DLT 分析，確定任務(wù)負(fù)載傳輸?shù)臅r(shí)間、數(shù)據(jù)量大小，實(shí)現(xiàn)高能效調(diào)度目的。

本文根據(jù)多核密碼處理器任務(wù)負(fù)載特征，在給定任務(wù)量下以設(shè)計(jì)高能效的調(diào)度機(jī)制為目標(biāo)，利用可分負(fù)載理論的分析方法，建立多核密碼處理器調(diào)度的數(shù)學(xué)模型。通過(guò)分析數(shù)學(xué)模型，提出多輪與單輪混合任務(wù)調(diào)度方式，得到優(yōu)化的任務(wù)數(shù)據(jù)分配輪數(shù)、處理器分配任務(wù)量等影響多核密碼處理器調(diào)度效率的關(guān)鍵參數(shù)，縮短多核密碼處理器總?cè)蝿?wù)調(diào)度運(yùn)算時(shí)間，提升負(fù)載調(diào)度的能效。此外，通過(guò)板級(jí)測(cè)試，驗(yàn)證本文模型的有效性。

1 相關(guān)工作

多核處理器負(fù)載調(diào)度根據(jù)負(fù)載數(shù)據(jù)的特征，主要分為基于圖的調(diào)度和基于可分負(fù)載理論的調(diào)度?；趫D的調(diào)度針對(duì)任務(wù)負(fù)載有較強(qiáng)的數(shù)據(jù)依賴性，將任務(wù)表示成任務(wù)依賴圖（Task Dependency Graphs，TDG）［5-6］以及有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG）［7-8］等圖形式，通過(guò)分析圖來(lái)研究多核處理器的調(diào)度?；诳煞重?fù)載理論的調(diào)度針對(duì)任務(wù)數(shù)據(jù)可任意劃分成小單元，劃分后數(shù)據(jù)間無(wú)依賴關(guān)系，可任意分配到各處理器上。根據(jù)多核處理器間通信拓?fù)潢P(guān)系不同，有研究鏈?zhǔn)?、總線式、單層樹(shù)狀、2D-mesh［9-10］等拓?fù)浣Y(jié)構(gòu)的調(diào)度。根據(jù)考慮因素不同，有考慮帶前端處理、帶結(jié)果反饋等因素的調(diào)度。

文獻(xiàn)［11］以最小化任務(wù)處理時(shí)間為目標(biāo)，首次提出可分負(fù)載的分析方法，同時(shí)考慮通信與計(jì)算，研究調(diào)度問(wèn)題，并在形式上給出可分負(fù)載理論的最優(yōu)條件，即所有處理器同時(shí)停止運(yùn)算，但文獻(xiàn)只考慮了線性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，且僅針對(duì)傳感器網(wǎng)絡(luò)。文獻(xiàn)［12］對(duì)可分負(fù)載單輪調(diào)度方式，在數(shù)學(xué)上嚴(yán)格證明所有處理器同時(shí)停止運(yùn)算，是可分負(fù)載理論達(dá)最優(yōu)處理時(shí)間的條件，并給出調(diào)度的數(shù)學(xué)最優(yōu)解，但研究仍只考慮線性網(wǎng)絡(luò)拓?fù)?，且單輪調(diào)度存在負(fù)載不均衡問(wèn)題。文獻(xiàn)［13］基于可分負(fù)載理論分析單層樹(shù)狀拓?fù)浣Y(jié)構(gòu)的多處理器任務(wù)調(diào)度，并給出各處理器同構(gòu)情況下的任務(wù)負(fù)載分配的數(shù)學(xué)解析解。不同于上述理論研究，文獻(xiàn)［14］將可分負(fù)載理論應(yīng)用到并行視頻解碼中，結(jié)果顯示采用可分負(fù)載理論能有效縮短多核處理器上并行視頻解碼任務(wù)的完成時(shí)間。為優(yōu)化可分負(fù)載理論的負(fù)載任務(wù)完成時(shí)間，文獻(xiàn)［15］在處理器網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)未知情況下，提出采用自適應(yīng)負(fù)載分配方式，通過(guò)探測(cè)網(wǎng)絡(luò)結(jié)構(gòu)分配負(fù)載；文獻(xiàn)［16］基于可分負(fù)載理論分析了當(dāng)有兩個(gè)根節(jié)點(diǎn)同時(shí)調(diào)度任務(wù)時(shí)，多核處理器任務(wù)完成時(shí)間的變化；文獻(xiàn)［17］提出多輪周期調(diào)度任務(wù)方式，縮短了處理器等待任務(wù)傳輸?shù)臅r(shí)間。文獻(xiàn)［18-20］基于可分負(fù)載理論分別研究了異構(gòu)多核處理器實(shí)時(shí)系統(tǒng)、負(fù)載非線性、異構(gòu)星形拓?fù)浣Y(jié)構(gòu)上的圖像處理任務(wù)、雷達(dá)圖像數(shù)據(jù)并行處理等不同應(yīng)用下的負(fù)載調(diào)度［21］。

針對(duì)可分負(fù)載理論在單輪調(diào)度上存在負(fù)載平衡不均、采用多輪調(diào)度優(yōu)化后難以得到解析解、多核處理器研究多為線性拓?fù)浠蛲瑯?gòu)處理器結(jié)構(gòu)、缺乏對(duì)異構(gòu)處理器的分析以及缺乏應(yīng)用于多核密碼處理器調(diào)度方面的研究等問(wèn)題，本文對(duì)多核密碼處理器的負(fù)載調(diào)度進(jìn)行研究，在調(diào)度方式上采用多輪與單輪混合方式，多核拓?fù)浣Y(jié)構(gòu)為單層樹(shù)狀結(jié)構(gòu)，考慮同構(gòu)、異構(gòu)情況下的負(fù)載調(diào)度，建立基于可分負(fù)載理論的多核密碼處理器調(diào)度數(shù)學(xué)模型，提出高能效的負(fù)載調(diào)度機(jī)制，從數(shù)學(xué)模型仿真、實(shí)際芯片測(cè)試兩方面對(duì)提出的調(diào)度策略進(jìn)行實(shí)驗(yàn)分析與評(píng)估。

2 多核密碼處理器可分負(fù)載調(diào)度模型

本節(jié)基于可分負(fù)載理論對(duì)單層樹(shù)狀拓?fù)浣Y(jié)構(gòu)的多核密碼處理器進(jìn)行負(fù)載調(diào)度研究，建立了單輪調(diào)度方式的數(shù)學(xué)模型，提出多輪與單輪混合調(diào)度方式。

2.1 多核密碼處理器拓?fù)浣Y(jié)構(gòu)

調(diào)度模型研究的多核密碼處理器采用單層樹(shù)狀拓?fù)浣Y(jié)構(gòu)，如圖1 所示。圖中負(fù)載數(shù)據(jù)進(jìn)入調(diào)度控制器H0，H0對(duì)數(shù)據(jù)進(jìn)行調(diào)度，依次分配數(shù)據(jù)到各處理器P1至Pn中，待處理器完成運(yùn)算后，將結(jié)果送到輸出控制器H1中輸出。在整個(gè)多核密碼處理器系統(tǒng)中，H0是調(diào)度的核心?；诳煞重?fù)載理論，調(diào)度的本質(zhì)是確定什么時(shí)間，輸送多少數(shù)據(jù)量，到哪個(gè)處理器Pi（1≤i≤n）。

圖1 多核密碼處理器的單層樹(shù)狀拓?fù)浣Y(jié)構(gòu)Fig.1 Single layer tree topology structure of multi-core cryptographic processors

高能效的調(diào)度方式主要從功耗盡可能低、性能盡可能提高兩方面考慮。功耗可以分成靜態(tài)功耗與動(dòng)態(tài)功耗。對(duì)于任務(wù)級(jí)密碼數(shù)據(jù)處理，一方面，給定任務(wù)量條件下，無(wú)論采用何種調(diào)度方式，需要調(diào)度傳輸?shù)臄?shù)據(jù)量、處理器計(jì)算數(shù)據(jù)量是一定的，因此動(dòng)態(tài)功耗是固定的，而靜態(tài)功耗與整體數(shù)據(jù)處理完成時(shí)間成正比；另一方面，性能提高要求盡可能減少負(fù)載調(diào)度、處理完成時(shí)間。因此，高能效的調(diào)度機(jī)制意味著盡可能地減少整個(gè)數(shù)據(jù)的調(diào)度計(jì)算時(shí)間，這與可分負(fù)載理論的優(yōu)化目標(biāo)，即最小化完成時(shí)間是一致的。

2.2 多核密碼處理器單輪調(diào)度模型

為便于說(shuō)明，先建立最簡(jiǎn)單的單輪同構(gòu)多核密碼處理器調(diào)度模型。相關(guān)參數(shù)表示及模型假設(shè)如下：

1）處理器拓?fù)浣Y(jié)構(gòu)為單層樹(shù)狀結(jié)構(gòu)，向量H=（H0，H1）表示輸入調(diào)度控制器和輸出控制器，向量P=（P1，P2，…，Pn）表示各密碼處理器核；

2）多核處理器為同構(gòu)結(jié)構(gòu)，且每個(gè)處理器必須接收完全部數(shù)據(jù)后才開(kāi)始計(jì)算；

3）s表示處理器核運(yùn)算速度的倒數(shù)，c表示數(shù)據(jù)傳輸通信速度的倒數(shù)；

4）Ts表示單位數(shù)據(jù)量，是s=1 時(shí)的計(jì)算時(shí)間；Tc表示單位數(shù)據(jù)量，是c=1 時(shí)的通信時(shí)間，用于將模型中各變量參數(shù)量綱統(tǒng)一到完成時(shí)間上；

5）總?cè)蝿?wù)數(shù)據(jù)量為V，對(duì)應(yīng)占比為1，ai表示分配到處理器Pi的任務(wù)占比，有，且0≤ai≤1；

6）Ti表示第i個(gè)處理器完成任務(wù)負(fù)載時(shí)間，Tf表示最終任務(wù)負(fù)載時(shí)間。

根據(jù)可分負(fù)載理論最優(yōu)條件，當(dāng)所有密碼處理器同時(shí)停止運(yùn)算時(shí)，任務(wù)負(fù)載完成時(shí)間最短。若處理器不是在同一時(shí)間結(jié)束運(yùn)算，則空閑處理器核可以處理任務(wù)，以減少時(shí)間，同時(shí)之前的研究也給出了最優(yōu)條件嚴(yán)格的數(shù)學(xué)證明［12］。根據(jù)處理器同時(shí)停止的條件，整個(gè)調(diào)度過(guò)程可表示為圖2 所示，圖中a1×c×Tc表示任務(wù)負(fù)載a1傳輸給P1所消耗的時(shí)間，a1×s×Ts表示任務(wù)負(fù)載a1在P1中運(yùn)算消耗的時(shí)間。調(diào)度控制器H0給P1傳輸完負(fù)載a1后，P1開(kāi)始計(jì)算，同時(shí)H0開(kāi)始給P2傳輸負(fù)載，依此類推，最終當(dāng)所有處理器同時(shí)停止計(jì)算時(shí)，整個(gè)處理時(shí)間最短。

圖2 單輪可分負(fù)載任務(wù)調(diào)度Fig.2 Single-round divisible load tasks scheduling

基于已有對(duì)可分負(fù)載理論分析［13］的研究，當(dāng)處理器同時(shí)停止時(shí)達(dá)到最優(yōu)調(diào)度，各處理器完成時(shí)間如式（1）所示：

又因?yàn)橥瑫r(shí)停止，所以有式（2）：

由T1=T2可得a1與a2的關(guān)系如式（3）所示：

所以由式（5）及等比數(shù)列求和公式，可得式（6）：

由式（4）、式（6）可以得到各個(gè)處理器調(diào)度分配的任務(wù)占比如式（7）所示：

其中：當(dāng)多核處理器結(jié)構(gòu)確定后，r為固定參數(shù)，由此可得調(diào)度控制器H0的任務(wù)調(diào)度分配方式，使得當(dāng)前假設(shè)下整個(gè)負(fù)載處理的完成時(shí)間最短，最短時(shí)間Tf表達(dá)式如式（8）所示：

2.3 多核密碼處理器多輪與單輪混合調(diào)度模型

第2.2 節(jié)基于可分負(fù)載理論，在H0的調(diào)度控制下得到了數(shù)學(xué)上的解析最優(yōu)解，明確給每個(gè)密碼處理器分配任務(wù)負(fù)載ai，并得到最優(yōu)完成時(shí)間Tf。但由于假設(shè)簡(jiǎn)單，因此仍存在一些不足，主要有：一是對(duì)于處理器Pi來(lái)說(shuō)，i越大（傳輸數(shù)據(jù)順序越靠后），表示需要等待負(fù)載的時(shí)間越長(zhǎng)，這期間存在較多空閑時(shí)間；二是單輪分配使得各處理器任務(wù)負(fù)載不均衡，越靠后的處理器分配到的任務(wù)越少；三是第2.2 節(jié)的模型是只針對(duì)同構(gòu)情況下的多核處理器；四是未考慮實(shí)際情況數(shù)據(jù)輸出的時(shí)間消耗。

為進(jìn)一步優(yōu)化基于可分負(fù)載理論的多核密碼處理器調(diào)度機(jī)制，提升模型的適用性、準(zhǔn)確性，減少調(diào)度處理時(shí)間，在第2 節(jié)的基礎(chǔ)上優(yōu)化模型，主要的優(yōu)化措施有：一是采用多輪與單輪混合調(diào)度方式，即第1 階段采用多輪等量分配方式，以減少處理器空閑等待時(shí)間，減少調(diào)度處理時(shí)間，第2 階段采用單輪方式，保證所有處理器在相等時(shí)間內(nèi)結(jié)束運(yùn)行；二是考慮異構(gòu)多核密碼處理器情況，引入實(shí)際中結(jié)果輸出耗時(shí)參數(shù)，精確模型。

為建立優(yōu)化后的新模型，進(jìn)一步補(bǔ)充假設(shè)如下：

1）總?cè)蝿?wù)分成m輪次，前m－1輪，各不同輪次之間，同一輪調(diào)度各密碼處理器之間，分配的任務(wù)占比相同，即等量，第m輪采用單輪調(diào)度分配方式；

2）aij（1≤i≤n，1≤j≤m）表示第j個(gè)輪次分配給處理器Pi的任務(wù)量

3）si、ci（1≤i≤n）分別表示Pi處理器計(jì)算速度、通信速度的倒數(shù)；Ts、Tc仍表示單位數(shù)據(jù)量，當(dāng)si=1，ci=1時(shí)的計(jì)算時(shí)間、通信時(shí)間，為簡(jiǎn)化模型，Ts、Tc仍為固定值；

4）結(jié)果輸出時(shí)間固定表示為aij×Tout（1≤i≤n，1≤j≤m）；

5）處理器Pi輸出結(jié)果的時(shí)間消耗為T(mén)oi（1≤i≤n），采用單輪調(diào)度的處理器Pi消耗的時(shí)間為T(mén)im（1≤i≤n）。

對(duì)于多輪任務(wù)負(fù)載調(diào)度，不同輪次、同一輪次內(nèi)不同處理器調(diào)度分配任務(wù)的等量或不等量，沒(méi)有本質(zhì)上的區(qū)別，目的都是為縮短各個(gè)處理器等待數(shù)據(jù)通信時(shí)間，盡快進(jìn)入計(jì)算階段，以得到最佳的傳輸、計(jì)算總時(shí)間。在理想情況下，對(duì)多核密碼處理器，最優(yōu)的情況是所有處理器能同時(shí)處于計(jì)算狀態(tài)。但因運(yùn)算數(shù)據(jù)需要傳輸時(shí)間，因此最佳情況變成每個(gè)處理器只需要等待自身任務(wù)數(shù)據(jù)傳輸時(shí)間，不受其他處理器影響，且應(yīng)盡早開(kāi)始進(jìn)行運(yùn)算。因此為便于模型分析，且不失一般性，本文采用不同輪次、同輪次內(nèi)不同處理器等量任務(wù)數(shù)據(jù)調(diào)度方式，且最后一輪次采用單輪非等量調(diào)度方式，保證可分負(fù)載理論的最優(yōu)條件，即各處理器同時(shí)結(jié)束運(yùn)算。

多輪加單輪混合調(diào)度方式過(guò)程如圖3 所示。整個(gè)調(diào)度分配分成多輪等量調(diào)度、單輪調(diào)度兩個(gè)階段。對(duì)于單輪調(diào)度，可用第2.2 節(jié)的模型進(jìn)行分析，得到具體每個(gè)處理器需要的任務(wù)量。對(duì)于多輪等量調(diào)度，不失一般性地分析第1 輪次，由于各處理器任務(wù)量相等，關(guān)鍵在于分配任務(wù)量ai1（1≤i≤n），即最后一個(gè)處理器Pn何時(shí)開(kāi)始計(jì)算。在圖3中，Pn在P1剛好計(jì)算完成后開(kāi)始計(jì)算，記該時(shí)刻為tp。若實(shí)際Pn在tp時(shí)刻后，則會(huì)增加傳輸通信消耗時(shí)間，Tf無(wú)法達(dá)到最優(yōu)；若實(shí)際Pn在tp時(shí)刻前，則任務(wù)傳輸通信時(shí)間較短，但下一輪次仍要等P1運(yùn)算結(jié)果后才能進(jìn)行運(yùn)算，對(duì)Tf無(wú)更多的增益。因此，在多輪等量調(diào)度階段，使Pn在P1剛好計(jì)算完成后開(kāi)始計(jì)算，即滿足等式，這也便于模型的分析。由可分負(fù)載理論的處理器同時(shí)結(jié)束條件，多輪加單輪混合調(diào)度方式完成時(shí)間如式（9）所示：

其中：Tim和Toi（1≤i≤n）可表示如式（10）、式（11）所示，分析結(jié)果輸出消耗時(shí)間Toi，從圖3 中可以看到，在多輪等量調(diào)度階段，只要結(jié)果輸出時(shí)間小于任務(wù)數(shù)據(jù)調(diào)度時(shí)間，就可以不考慮，實(shí)際上對(duì)于密碼處理器，結(jié)果輸出時(shí)間不會(huì)超過(guò)任務(wù)數(shù)據(jù)調(diào)度時(shí)間，因此可以忽略，所以式（10）只計(jì)算了最后單輪階段的結(jié)果輸出時(shí)間。

根據(jù)可分負(fù)載的處理器同時(shí)停止運(yùn)算時(shí)為最優(yōu)條件，式（2）的遞推等式對(duì)多輪等量加單輪混合調(diào)度方式依舊適用。等量分配m個(gè)輪次，類似的有這兩個(gè)等式成立。對(duì)于異構(gòu)多核處理器平臺(tái)，由于si、ci不同，要想直接求解每個(gè)任務(wù)數(shù)據(jù)占比aij（1≤i≤n，1≤j≤m）已經(jīng)被證明是一個(gè)NP 困難問(wèn)題［22-24］。

為分析多輪等量加單輪混合調(diào)度的情況，首先考慮當(dāng)多核密碼處理器為同構(gòu)平臺(tái)，即計(jì)算速度與通信速度均相等時(shí)，可得到式（12）～式（14）：

其中：式（12）表示考慮同構(gòu)情況下各處理器核計(jì)算、通信速度相等；式（13）表示在多輪等量調(diào)度階段，任務(wù)數(shù)據(jù)占比主要與分配輪次m和處理器數(shù)n相關(guān)；式（14）則表示第m輪采用單輪調(diào)度時(shí)，各處理器分配得到的任務(wù)量，與式（7）結(jié)果類似，只是此處不是對(duì)全體任務(wù)分配，而是對(duì)1/m的任務(wù)調(diào)度分配。

由式（2）和式（9）～式（14）可得到最終調(diào)度，計(jì)算完成總時(shí)間Tf如式（15）所示：

從式（15）中可以看到，總消耗時(shí)間Tf與電路固定參數(shù)、處理器核數(shù)n、多輪分輪數(shù)m有關(guān)，在一個(gè)固定多核密碼處理器平臺(tái)上，分輪數(shù)m是一個(gè)變化量，也是調(diào)度中的關(guān)鍵。因?yàn)閞×s×Ts=c×Tc+s×Ts，對(duì)式（15）中的項(xiàng)，由于實(shí)際結(jié)果輸出時(shí)間要遠(yuǎn)小于通信加運(yùn)算時(shí)間，因此該項(xiàng)可近似為1，由此對(duì)式（15），固定n，對(duì)m求偏導(dǎo)數(shù)可得式（16）：

易證，當(dāng)n≥1、r≥1時(shí)恒成立，則小于0，即Tf對(duì)于m單調(diào)遞減，分的輪次越大，消耗總時(shí)間Tf越小。而對(duì)于密碼算法，由于單個(gè)核心處理數(shù)據(jù)量有最小限制，因此當(dāng)多輪調(diào)度采用每輪次分配最小限制量時(shí)，m最大，此時(shí)Tf最小，調(diào)度方式對(duì)多核密碼處理器平臺(tái)為能效最優(yōu)。

當(dāng)多核密碼處理器平臺(tái)為異構(gòu)時(shí)，假設(shè)通信速度相等，在不同輪次仍采用等量分配方式，在同一輪次中根據(jù)不同處理器的計(jì)算能力進(jìn)行比例分配，即，由此可以進(jìn)行與同構(gòu)情況下相同的分析。對(duì)于第m輪次，即采用單輪方式階段，代入不同計(jì)算速度si，通過(guò)解線性方程的方式可以得到相應(yīng)的調(diào)度任務(wù)數(shù)據(jù)負(fù)載aim（1≤i≤n）的解。

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文提出的多核密碼處理器調(diào)度機(jī)制的可行性，分別進(jìn)行MATLAB 軟件仿真實(shí)驗(yàn)、多核密碼處理器芯片板級(jí)任務(wù)調(diào)度測(cè)試并分析結(jié)果。

3.1 結(jié)果分析

3.1.1 單輪調(diào)度仿真分析

通過(guò)MATLAB 仿真，使r取不同值，得到如圖4所示的多核密碼處理器單輪調(diào)度時(shí)處理器核數(shù)與最終完成時(shí)間之間的關(guān)系。由圖4 可以看到，以r=1.1時(shí)為例，整個(gè)曲線最開(kāi)始快速下降，之后下降趨勢(shì)逐漸緩慢，最終趨于不變。這是因?yàn)閷?duì)于多核密碼處理器，當(dāng)任務(wù)量固定時(shí)，初始提升核心數(shù)能有效提升任務(wù)處理的并行性，從而完成時(shí)間迅速減小；但當(dāng)處理器核數(shù)過(guò)多時(shí)，并行度提升達(dá)到極限，同時(shí)核心數(shù)增多導(dǎo)致任務(wù)傳輸通信時(shí)間增加，即處理器等待任務(wù)時(shí)間增加，因此完成時(shí)間Tf減小的斜率將逐漸放緩，直至趨于不變。

當(dāng)變化r值時(shí)，從圖4 中可以看到隨著r的增大，各曲線達(dá)到極限Tf值時(shí)對(duì)應(yīng)的n值越來(lái)越小，且趨于不變時(shí)的Tf值越來(lái)越大。這是因?yàn)榧创矶嗪嗣艽a處理器通信時(shí)間與計(jì)算時(shí)間的占比，當(dāng)r趨近于1時(shí)，表示計(jì)算時(shí)間占比更大，通信時(shí)間幾乎可以忽略，因此隨處理器核數(shù)n增大導(dǎo)致的通信時(shí)間消耗影響會(huì)更小，即完成時(shí)間Tf所能達(dá)到的極限值會(huì)更??；當(dāng)r越大，即通信時(shí)間占比增加（如r=2時(shí)，表示完成任務(wù)需要的數(shù)據(jù)通信傳輸時(shí)間與計(jì)算時(shí)間各占總時(shí)間的50%），處理器核數(shù)n增大導(dǎo)致的通信時(shí)間消耗影響加劇，完成時(shí)間Tf能達(dá)到的最小值增大，即有更多時(shí)間浪費(fèi)在數(shù)據(jù)傳輸通信上，需要更長(zhǎng)的Tf完成時(shí)間。這說(shuō)明對(duì)于單輪調(diào)度，處理密碼任務(wù)的處理器核數(shù)、任務(wù)本身通信/計(jì)算比例兩個(gè)因素會(huì)影響整個(gè)調(diào)度過(guò)程。

除分析調(diào)度完成時(shí)間Tf的變化趨勢(shì)及指導(dǎo)調(diào)度方式設(shè)計(jì)外，基于可分負(fù)載理論模型還能給出具體的調(diào)度策略。以n=4，r=1.1 為例，這表明多核密碼處理器有4 個(gè)核心，總?cè)蝿?wù)負(fù)載的通信/計(jì)算占比r=1.1，可得調(diào)度方式如表1 所示，最佳調(diào)度為分別給處理器P1、P2、P3、P4按序分配如表1 所示比例的任務(wù)數(shù)據(jù)，能達(dá)到最優(yōu)的總完成時(shí)間，即達(dá)到高能效的調(diào)度。

表1 基于可分負(fù)載理論的單輪調(diào)度示例Table 1 Example of single round scheduling based on divisible load theory %

3.1.2 多輪與單輪混合調(diào)度仿真分析

利用MATLAB 對(duì)建立的基于可分負(fù)載理論多輪與單輪混合調(diào)度的模型進(jìn)行仿真。分別固定m，改變參數(shù)r、n；固定n，改變參數(shù)r、m；固定r，改變參數(shù)m、n；固定m、n、r，變化結(jié)果輸出因子Tout4種不同情況仿真，從多個(gè)維度對(duì)多輪與單輪混合調(diào)度機(jī)制進(jìn)行分析。

當(dāng)固定混合調(diào)度的輪次m=4時(shí)，完成時(shí)間Tf隨處理器核數(shù)增加的變化趨勢(shì)如圖5 所示。對(duì)比圖4可知，圖5 的5 種不同r取值下的完成時(shí)間Tf均要小于圖4，這表明提出的多輪加單輪混合調(diào)度機(jī)制在理論上要優(yōu)于單輪調(diào)度方式，即能使得整個(gè)任務(wù)完成時(shí)間更短。這是因?yàn)橥ㄟ^(guò)劃分多輪，能讓各個(gè)處理器更早地開(kāi)始運(yùn)算，減小了負(fù)載傳輸?shù)却龝r(shí)間。從圖5 中可以看到，相較于圖4、圖5 的5 條曲線，當(dāng)Tf達(dá)到極限最小值且趨于平滑時(shí)，5 條曲線之間的差值要遠(yuǎn)小于圖4 中該情況下5 條曲線的差值。這是因?yàn)椴捎没旌险{(diào)度方式，分輪次會(huì)使得單次傳輸?shù)娜蝿?wù)量減小，即使傳輸通信速度差異較大，但由于單次傳輸?shù)娜蝿?wù)量小，體現(xiàn)出來(lái)的時(shí)間差異也相應(yīng)減小，相當(dāng)于削弱了通信計(jì)算比例參數(shù)r的影響。這也側(cè)面說(shuō)明多輪與單輪混合調(diào)度能通過(guò)削弱任務(wù)傳輸通信時(shí)間消耗影響，提高整個(gè)調(diào)度的能效。

圖5 固定輪次條件下混合調(diào)度完成時(shí)間的變化趨勢(shì)Fig.5 Changing trend of completion time of mixed scheduling under fixed turns condition

除分析趨勢(shì)外，建立的模型仍可以得到具體的調(diào)度分配方式，以n=4，m=4，r=1.1 為例，為達(dá)到最佳總完成時(shí)間，調(diào)度方式如表2 所示。

表2 基于可分負(fù)載理論的混合調(diào)度示例Table 2 Mixed scheduling example based on divisible load theory %

當(dāng)固定混合調(diào)度的處理器數(shù)n=4時(shí)，完成時(shí)間Tf隨處理器核數(shù)增加的變化趨勢(shì)如圖6 所示。由圖6可知，當(dāng)參數(shù)r取值不同時(shí)，Tf在m=1 處的值也不同，且r越大，Tf值越小。這是因?yàn)閙=1 表示單輪調(diào)度，不劃分輪次，因此任務(wù)總完成時(shí)間Tf值受r影響，這個(gè)結(jié)論也與圖4 的結(jié)果相一致。同時(shí)可以看到，當(dāng)m越大時(shí)，Tf值越小，且最終趨于相同。這是因?yàn)槔碚撋希鬽值無(wú)限增大，即任務(wù)負(fù)載可被無(wú)限分割小，此時(shí)任務(wù)傳輸通信時(shí)間就可以忽略，即表現(xiàn)為即使r值差距很大，但圖6 中的Tf值最終也趨于相同。當(dāng)然，在實(shí)際中，對(duì)于多核密碼處理器，每個(gè)核有最小處理數(shù)據(jù)位寬（如AES 算法，其最小處理位寬為128 bit），因此m不可能無(wú)限增大，但模型仿真結(jié)果暗示了，當(dāng)m達(dá)到單個(gè)核可以處理的最小位寬時(shí)，本文提出的多輪與單輪混合策略能達(dá)到最優(yōu)的Tf值，這也驗(yàn)證了前述數(shù)學(xué)求導(dǎo)證明的正確性。

圖6 固定處理器數(shù)條件下混合調(diào)度完成時(shí)間的變化趨勢(shì)Fig.6 Changing trend of completion time of mixed scheduling under fixed number of processors condition

當(dāng)固定混合調(diào)度的通信計(jì)算占比參數(shù)r=1.1時(shí)，完成時(shí)間Tf隨處理器核數(shù)增加的變化趨勢(shì)如圖7 所示。圖7 的變化趨勢(shì)表明，當(dāng)m、n同時(shí)變化時(shí)，其與Tf組成的二元函數(shù)Tf（m，n）的變化趨勢(shì)是圖5、圖6變化趨勢(shì)的線性結(jié)合，即使m、n同時(shí)變化，前述的變化規(guī)律也仍舊適應(yīng)，即m越大，n越大，在一定范圍內(nèi)Tf值會(huì)迅速減小，但減小的速度會(huì)逐漸降低，直至趨于平緩。

圖7 固定參數(shù)r 條件下混合調(diào)度完成時(shí)間的變化趨勢(shì)Fig.7 Changing trend of completion time of mixed scheduling under fixed parameter r condition

為研究本文模型中結(jié)果輸出參數(shù)Tout對(duì)總完成時(shí)間Tf的影響，改變Tout的取值，通過(guò)MATLAB 仿真得到如圖8 所示的變化趨勢(shì)圖。圖8 為取處理器核數(shù)n=4，輪次m=4，通信計(jì)算占比r=1.1 情況下，對(duì)應(yīng)不同Tout值的變化曲線。從圖8 中可以看到，隨著Tout值的增大，最終完成時(shí)間Tf也會(huì)增大，但增大的幅度較小。這表明輸出Tout值會(huì)影響任務(wù)總完成時(shí)間，同時(shí)也說(shuō)明，結(jié)果輸出時(shí)間的影響占比不大，不是整個(gè)混合調(diào)度完成時(shí)間Tf的主要影響因素，通過(guò)調(diào)節(jié)通信計(jì)算占比及合理選擇輪次m，可以有效減小結(jié)果輸出消耗時(shí)間的影響。

圖8 處理器核數(shù)與混合調(diào)度完成時(shí)間的關(guān)系Fig.8 Relationshtp between the number of processor cores and completion time of mixed scheduling

3.2 板級(jí)測(cè)試結(jié)果與分析

在現(xiàn)有多核密碼處理器芯片的基礎(chǔ)上，通過(guò)控制輸入微控制器采用提出的混合調(diào)度方式進(jìn)行任務(wù)負(fù)載的調(diào)度，驗(yàn)證基于可分負(fù)載理論的多輪與單輪混合調(diào)度方式的實(shí)際有效性。

多核密碼處理器芯片的示意結(jié)構(gòu)如圖9 所示，處理器由輸入微控制器、輸出微控制器及4 個(gè)密碼處理器核組成，4 個(gè)密碼處理器可以獨(dú)立工作，也可相互通信。輸入微控制器可以進(jìn)行微代碼編程，控制任務(wù)負(fù)載送到各個(gè)密碼處理器核心的數(shù)量與順序。多核密碼處理器芯片板級(jí)測(cè)試平臺(tái)如圖10 所示，測(cè)試板與ZYNQ 系列FPGA 連接，負(fù)責(zé)發(fā)送數(shù)據(jù)給多核密碼處理器芯片，多核密碼處理器中的輸入微控制器再進(jìn)行接收數(shù)據(jù)的調(diào)度，本文考慮的調(diào)度是指進(jìn)入多核密碼處理器芯片內(nèi)任務(wù)負(fù)載分配給各個(gè)核心的調(diào)度。

圖9 多核密碼處理器芯片的結(jié)構(gòu)Fig.9 Structure of multi-core cryptoprocessor chip

圖10 多核密碼處理器芯片板級(jí)測(cè)試平臺(tái)Fig.10 Chip board testing platform for multi-core cryptoprocessor chips

在多核密碼處理器板級(jí)測(cè)試平臺(tái)上，對(duì)密碼算法1、算法2、算法3 分別采取任務(wù)負(fù)載均衡分配調(diào)度［25］（簡(jiǎn)稱平均調(diào)度）、單輪分配調(diào)度［10］（簡(jiǎn)稱單輪調(diào)度）、多輪與單輪混合分配調(diào)度（m=1，簡(jiǎn)稱混合調(diào)度），3 種方式進(jìn)行測(cè)試，得到任務(wù)完成時(shí)間Tf的實(shí)驗(yàn)結(jié)果如圖11 所示。算法1、算法2、算法3 的負(fù)載任務(wù)量均為768×32 Byte，芯片工作頻率為256 MHz。由圖11 可知，在相同任務(wù)量下，算法1、算法2、算法3采用多輪與單輪混合調(diào)度方式對(duì)比平均調(diào)度方式完成時(shí)間分別縮短了10.1%、19.1%、48.2%，這說(shuō)明本文所提出的混合調(diào)度方式的有效性。不同算法完成時(shí)間的縮短程度不同，與其算法的通信計(jì)算時(shí)間比有關(guān)。注意到平均調(diào)度與單輪調(diào)度方式差距不大，一方面是因?yàn)樘幚碡?fù)載任務(wù)量不夠大，另一方面是因?yàn)? 個(gè)算法整體來(lái)說(shuō)通信時(shí)間占比較小，所以體現(xiàn)不出基于可分負(fù)載理論的單輪調(diào)度的優(yōu)勢(shì)。

圖11 不同調(diào)度方式下完成時(shí)間的對(duì)比Fig.11 Comparison of completion time under different scheduling patterns

圖12 為算法2 在板級(jí)測(cè)試時(shí)采用不同的輪次m得到的吞吐率變化趨勢(shì)，當(dāng)m分別為1、4、8、16時(shí)，得到的吞吐率分別為682、812、838、839 Mb/s。可以看到在數(shù)據(jù)量一定的條件下，隨著m值的增大，完成時(shí)間Tf不斷減少，進(jìn)而吞吐率增大，但當(dāng)m足夠大時(shí)，曲線趨于平緩，這與圖6 的仿真結(jié)果相一致。

圖12 算法2 在不同輪次條件下的吞吐率Fig.12 Throughput rate of algorithm 2 under different turns condition

實(shí)際上，當(dāng)處理數(shù)據(jù)量固定時(shí)，隨著m變化，能耗不增加，性能提升，即能效值會(huì)相應(yīng)增大。表3 為在多核密碼處理器上使用不同調(diào)度方式時(shí)得到的板級(jí)測(cè)試能效值。從表3 可以看到，對(duì)于不同算法，對(duì)比平均調(diào)度和單輪調(diào)度方式，本文提出的混合調(diào)度方式在能效值上的提升分別為9.8%、18.7%、48.1%，由于不同算法在多核密碼處理器上調(diào)度時(shí)的通信計(jì)算比不同，因此提升幅度也有差異。

表3 不同算法的能效值比較Table 3 Comparison for energy-efficiency of different algorithms 單位：(Mb·s-1·mW-1)

4 結(jié)束語(yǔ)

針對(duì)5G、物聯(lián)網(wǎng)等背景下邊緣設(shè)備面臨的安全與資源受限等問(wèn)題對(duì)高能效多核密碼處理器設(shè)計(jì)提出的需求，本文提出基于可分負(fù)載理論的高能效調(diào)度機(jī)制。利用可分負(fù)載理論的分析方法，建立多核密碼處理器上任務(wù)負(fù)載調(diào)度處理數(shù)學(xué)模型，并提出多輪與單輪混合調(diào)度方式。通過(guò)MATLAB 仿真分析得到處理器核數(shù)、多輪分配輪次、結(jié)果輸出消耗等因素對(duì)多核密碼處理器任務(wù)完成時(shí)間的影響。多核密碼處理器芯片板級(jí)測(cè)試結(jié)果表明，本文提出的多輪與單輪混合調(diào)度方式能夠有效縮短密碼任務(wù)處理完成的時(shí)間，提升多核密碼處理器的能效。下一步將繼續(xù)利用可分負(fù)載理論，研究面向異構(gòu)多核密碼處理器平臺(tái)的高能效負(fù)載調(diào)度機(jī)制，并將單層樹(shù)狀拓?fù)浣Y(jié)構(gòu)擴(kuò)展到多層樹(shù)狀拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)更多處理器核數(shù)場(chǎng)景下的高能效異構(gòu)多核密碼處理器負(fù)載調(diào)度。