徐金甫 章宇雷 李 偉 陳 韜

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

1 引言

粗粒度可重構(gòu)密碼邏輯陣列(Coarse -grained Reconfigurable Cipher Logical Array， CRCLA)是一種基于數(shù)據(jù)流的高效運(yùn)算結(jié)構(gòu)，它結(jié)合了專用集成電路高性能與通用處理器高靈活性的特點(diǎn)[1]，具有豐富的計(jì)算資源和互連資源，能夠?qū)崿F(xiàn)密碼算法的高能效實(shí)現(xiàn)及靈活性切換。但由于其復(fù)雜的硬件結(jié)構(gòu)，在映射密碼算法時(shí)，也帶來(lái)了一定的難度。不同的映射方式將直接影響算法的實(shí)現(xiàn)性能及功耗，因此合理的映射方式是充分發(fā)揮粗粒度可重構(gòu)陣列結(jié)構(gòu)優(yōu)勢(shì)的關(guān)鍵[2]。

將密碼算法映射到CRCLA上，從數(shù)據(jù)流圖的角度出發(fā)，映射問題實(shí)際上就是布局和布線兩個(gè)子問題的組合。目前，國(guó)內(nèi)外針對(duì)布局布線算法的研究主要是基于現(xiàn)場(chǎng)可編程邏輯門陣列(Field Programmable Gate Array， FPGA)進(jìn)行的，而該項(xiàng)研究上均是將布局布線過程拆分成兩個(gè)階段進(jìn)行的，按照先布局后布線的順序[3，4]，采用了模擬退火算法及路徑搜索算法。與傳統(tǒng)的FPGA的布局布線算法不同的是，在CRCLA的映射問題上，布局和布線兩個(gè)子問題存在著很大的關(guān)聯(lián)性，若將其獨(dú)立分開，將不能達(dá)到較好的映射效果，且映射失敗往往發(fā)生在布線的過程中，因此需要將兩者結(jié)合。文獻(xiàn)[5]提出了一種基于圖映射的算法SPKM啟發(fā)式映射算法，通過“分裂-推送”的方式將循環(huán)部分映射至粗粒度可重構(gòu)陣列上，減少了映射的陣列行數(shù)，但其流水性能較差；文獻(xiàn)[6]提出了一種存儲(chǔ)感知映射方法RAMP，在調(diào)度步驟之前，智能地探索各種路由資源，提高了映射的效率和質(zhì)量；文獻(xiàn)[7]提出了一種基于傳輸感知的有效循環(huán)映射方法TAEM，該方法可以有效利用CGRA上的異構(gòu)資源，顯著提高了編譯速度；文獻(xiàn)[8]對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)劃分后利用模調(diào)度的方式進(jìn)行映射，并采用了路徑重用進(jìn)一步優(yōu)化路由資源，但其依賴可重構(gòu)單元進(jìn)行路由，并未討論存在互連資源的可重構(gòu)陣列結(jié)構(gòu)；文獻(xiàn)[9]提出了一種以邊為中心的模調(diào)度(Edge-centric Modulo Scheduling， EMS)映射算法，在時(shí)間維度上的模調(diào)度采用了邊的映射為中心，節(jié)點(diǎn)為邊放置過程中的產(chǎn)物的方式，縮短了算法的搜索空間，減少了編譯時(shí)間的同時(shí)，也能夠達(dá)到較好的映射性能，但其搜索空間可能存在局部最優(yōu)解；文獻(xiàn)[10]針對(duì)流水氣泡問題進(jìn)行了優(yōu)化，通過直通算子共享的方式減少了算法的啟動(dòng)間隔，提升了算法映射的性能等。

上述算法主要基于通用型可重構(gòu)陣列的結(jié)構(gòu)下進(jìn)行討論的，而密碼算法的運(yùn)算具有特殊性，且CRCLA內(nèi)部由專為密碼處理而設(shè)計(jì)的運(yùn)算單元排列而成，通過配置信息來(lái)形成特定的數(shù)據(jù)通路[11]，因此上述映射算法均不適用基于CRCLA的密碼算法映射問題。本文通過結(jié)合密碼算法的運(yùn)算特征及CRCLA的硬件結(jié)構(gòu)，提出了一種映射過程中的建模方式，對(duì)映射過程具有更加清晰地描述；并提出了一種以邊來(lái)指導(dǎo)節(jié)點(diǎn)的空間映射算法，通過確定根節(jié)點(diǎn)的映射后，按照關(guān)鍵路徑優(yōu)先的原則構(gòu)造搜索步，并制定了路徑搜索的方案使得映射路徑最短，為避免映射失敗，引入了回溯機(jī)制，提升了映射的能效及效率。

2 粗粒度可重構(gòu)密碼邏輯陣列映射模型

2.1 CRCLA基本結(jié)構(gòu)

本文基于課題組前期設(shè)計(jì)的一款粗粒度可重構(gòu)密碼邏輯陣列開展映射算法驗(yàn)證，該陣列結(jié)構(gòu)已在55 nm工藝下流片并驗(yàn)證。圖1所示為課題組設(shè)計(jì)的4×4規(guī)模陣列，該陣列結(jié)構(gòu)中，4×4個(gè)同構(gòu)的運(yùn)算單元(Processing Element， PE)構(gòu)成了PE的計(jì)算資源，運(yùn)算位寬為32 bit，其內(nèi)部包含了多個(gè)運(yùn)算功能單元(Functional Unit， FU)，如比特置換單元、邏輯運(yùn)算單元、非線性運(yùn)算單元等，能夠滿足密碼算法運(yùn)算的基本需求，并且各個(gè)FU單元之間存在互連網(wǎng)絡(luò)，能夠?qū)崿F(xiàn)數(shù)據(jù)的互通。為消除密碼運(yùn)算過程中的流水氣泡以及滿足部分算法數(shù)據(jù)的寄存需求，在各個(gè)FU單元后添加了寄存器傳輸網(wǎng)絡(luò)，可以通過配置來(lái)實(shí)現(xiàn)數(shù)據(jù)的寄存。同時(shí)，每一行的PE之間存在級(jí)聯(lián)網(wǎng)絡(luò)，能夠滿足部分密碼算法大位寬數(shù)據(jù)的處理需求。

連接盒(Connect Box， CB)和開關(guān)盒(Switch Box， SB)構(gòu)成了CRCLA的互連資源，CB分布在各個(gè)PE的4個(gè)方向上，能夠?qū)崿F(xiàn)PE與PE之間的互連以及PE與SB之間的互連；SB位于4個(gè)CB的中心，能夠?qū)崿F(xiàn)各個(gè)CB之間的互連。各個(gè)單元之間采用雙向數(shù)據(jù)傳輸?shù)姆绞?，同一個(gè)方向上不能同時(shí)存在兩個(gè)輸出或輸入，否則即為錯(cuò)誤映射方式。

圖1 CRCLA整體硬件結(jié)構(gòu)

2.2 CRCLA映射描述形式

基于以上分析，密碼算法的映射問題實(shí)際上就是將密碼算法轉(zhuǎn)換成CRCLA的配置數(shù)據(jù)的過程?？紤]到密碼算法表示的多樣性，結(jié)合粗粒度可重構(gòu)密碼邏輯陣列的結(jié)構(gòu)，采用密碼算法的數(shù)據(jù)流圖作為密碼算法映射問題的輸入。

在進(jìn)行數(shù)據(jù)流圖的映射之前，由于CRCLA的一個(gè)PE中含有多種運(yùn)算功能單元，能夠同時(shí)實(shí)現(xiàn)多個(gè)節(jié)點(diǎn)的運(yùn)算，為充分利用PE內(nèi)部資源以及降低映射難度，需要對(duì)初始的密碼算法數(shù)據(jù)流圖進(jìn)行任務(wù)劃分，任務(wù)劃分過程參照文獻(xiàn)[12]，本文不再贅述。

在經(jīng)過任務(wù)劃分后，同樣可以得到一個(gè)新的數(shù)據(jù)流圖，但該數(shù)據(jù)流圖中的節(jié)點(diǎn)不再表示單一的運(yùn)算節(jié)點(diǎn)，而是由多個(gè)運(yùn)算節(jié)點(diǎn)形成的節(jié)點(diǎn)簇，在后文中，如無(wú)特殊說明，均稱為節(jié)點(diǎn)，且本文中的密碼算法數(shù)據(jù)流圖均為經(jīng)過了任務(wù)劃分后的數(shù)據(jù)流圖。因此，各節(jié)點(diǎn)之間可能存在多條互連關(guān)系。

下面將舉例說明此種表示方式。如圖2(a)所示為一個(gè)初始的數(shù)據(jù)流圖，此時(shí)，一個(gè)節(jié)點(diǎn)表示一個(gè)運(yùn)算操作；在經(jīng)過任務(wù)劃分后，得到如圖2(b)所示的數(shù)據(jù)流圖，此時(shí)一個(gè)節(jié)點(diǎn)中包含多個(gè)運(yùn)算操作；圖2(c)即為該數(shù)據(jù)流圖的矩陣表示方法。

圖2 數(shù)據(jù)流圖的矩陣表示過程

同樣地，對(duì)粗粒度可重構(gòu)密碼邏輯陣列的計(jì)算及互連資源參數(shù)化模型進(jìn)行表示。圖3所示為對(duì)PE的資源占用情況采用鏈表式描述。

Tag_row(PE)表示當(dāng)前PE所在行數(shù)，Tag_line(PE)表示當(dāng)前PE所在列數(shù)，Occupied(PE)表示當(dāng)前PE是否被占用，其值可取0或1，值為1表示被占用。當(dāng)陣列規(guī)模較小時(shí)，可能無(wú)法容納一個(gè)數(shù)據(jù)流圖，需要多個(gè)配置頁(yè)面來(lái)進(jìn)行配置，因此添加一個(gè)Page(PE)來(lái)表示當(dāng)前PE的配置頁(yè)面。

圖3 PE資源占用情況表示

對(duì)于互連資源，由2.1節(jié)可知，每一個(gè)PE周圍均有8個(gè)互連開關(guān)盒，為便于描述，將一個(gè)PE左邊及上邊的兩個(gè)CB、左上角的一個(gè)SB作為一個(gè)集合，如圖4(a)所示。

SB及CB的位置用該P(yáng)E所在的行列進(jìn)行表示，同時(shí)需要有對(duì)應(yīng)的標(biāo)量對(duì)其進(jìn)行區(qū)分，其表示方法如圖4(b)所示。

Tag(Con)表示當(dāng)前鏈表指向的互連單元，其值可取0， 1， 2，分別代表SB， CB0， CB1。E_in，E_out， N_in， N_out， S_in， S_out， W_in，W_out分別表示東南西北4個(gè)方向的輸入和輸出占用情況，其值可取0或1，值為1表示已被占用，即表示不能從此方向輸入(輸出)。

綜上，本小節(jié)對(duì)密碼算法的數(shù)據(jù)流圖和CRCLA的計(jì)算資源及互連資源進(jìn)行了描述，使得在映射過程中能夠更清晰地表示資源占用情況及映射的輸入輸出，為后續(xù)的算法映射奠定了一定的基礎(chǔ)。

圖4 一個(gè)包含互連及運(yùn)算單元的集合及其表示方式

3 密碼算法映射分析及問題定義

3.1 映射分析

由2.2節(jié)分析可知，密碼算法映射問題面向的是一個(gè)經(jīng)過劃分后的能夠滿足CRCLA的各種約束的數(shù)據(jù)流圖。由于劃分后的數(shù)據(jù)流圖中的每個(gè)節(jié)點(diǎn)在映射時(shí)直接對(duì)應(yīng)于一個(gè)PE，且PE內(nèi)部各個(gè)FU均可通過全互連網(wǎng)絡(luò)實(shí)現(xiàn)數(shù)據(jù)之間的交互，因此無(wú)需考慮節(jié)點(diǎn)內(nèi)部算子的連接關(guān)系。受限于面積限制，CRCLA各個(gè)PE之間無(wú)法采用全互連網(wǎng)絡(luò)，因此，其互連資源較為匱乏。通常，傳統(tǒng)的映射方法都是以節(jié)點(diǎn)為中心的，其重點(diǎn)在于如何將節(jié)點(diǎn)分配給各個(gè)PE，然而當(dāng)密碼算法映射時(shí)，隨著映射的推進(jìn)，即使還存在有大量的空閑狀態(tài)下的PE，也不可避免地由于互連資源限制導(dǎo)致映射失敗。

密碼算法的映射性能取決于映射到陣列上的關(guān)鍵路徑的延遲，而關(guān)鍵路徑上的延遲同時(shí)取決于計(jì)算單元PE的關(guān)鍵路徑延遲以及互連資源的關(guān)鍵路徑延遲。假設(shè)一個(gè)密碼算法映射到陣列上，則其關(guān)鍵路徑的延遲可以表示為

由式(3)可知，在布局布線可以通過盡量減少x，y的值來(lái)降低關(guān)鍵路徑上的延遲，即減少CB， SB的個(gè)數(shù)。因此各個(gè)節(jié)點(diǎn)映射的PE應(yīng)盡可能的緊湊，且各PE之間的連線應(yīng)盡可能短。

結(jié)合以上所有分析，互連資源的映射直接決定了密碼算法的映射性能及映射的成功與否。另外，對(duì)于密碼算法的映射問題，經(jīng)過大量研究可知，其布局及布線有著十分緊湊的聯(lián)系，不能將兩者單獨(dú)分開進(jìn)行討論。

3.2 問題描述

定義7 密碼算法映射問題：給定一個(gè)經(jīng)過劃分后的密碼算法數(shù)據(jù)流圖G={V，E}和陣列C ={P，L}，在滿足路徑存在約束、方向一致性約束及資源約束的前提下，找到一個(gè)最少使用互連資源的映射f(G)。

4 算法設(shè)計(jì)

4.1 EMS算法概述

EMS(Edge-centric Modulo Scheduling)算法，是一種以邊為中心的模調(diào)度算法，它摒棄了傳統(tǒng)的先布局后布線以節(jié)點(diǎn)為中心的模擬退火映射算法，采用顯示的方法來(lái)取代模擬退火的隱式管理，傳統(tǒng)的模擬退火算法在映射時(shí)編譯時(shí)間過長(zhǎng)，而EMS算法則采用了以數(shù)據(jù)流圖中的邊為中心的映射方式，首先考慮的是布線的資源利用率問題，在路由邊的過程中尋找可以映射節(jié)點(diǎn)的單元。因此，只要邊映射成功了，節(jié)點(diǎn)的映射也隨之成功，這一方法將布局布線兩個(gè)過程結(jié)合起來(lái)，搜索空間大大縮小，提高了編譯的效率。在映射過程中，遵循以下幾個(gè)準(zhǔn)則：(1)最小化布線資源；(2)主動(dòng)避免布線失敗；(3)對(duì)邊的映射進(jìn)行優(yōu)先級(jí)度量。

EMS算法是一種時(shí)域映射模調(diào)度算法，而本文所研究的密碼算法具有強(qiáng)烈的數(shù)據(jù)相關(guān)性，在映射上通常為空間映射，即不存在子圖之間的時(shí)序問題，且面向的對(duì)象為互連及計(jì)算資源較為豐富的粗粒度密碼邏輯陣列，模調(diào)度將不適用于密碼算法的映射。因此，該算法難以適用于本文的映射問題，本文在此基礎(chǔ)上，針對(duì)密碼算法在CRCLA上的映射問題，提出一種以邊為中心的空間映射算法(Edge-centric Cipher Logical array Mapping，ECLMap)。

4.2 ECLMap算法策略

在總體映射策略上，假設(shè)陣列資源能夠滿足密碼算法的映射需求，采用空間映射的手段，結(jié)合上述分析，密碼算法的映射問題更貼切于EMS算法中的以邊為中心指導(dǎo)節(jié)點(diǎn)進(jìn)行映射的思想。因此在映射過程中，同樣遵循4.1節(jié)提到的EMS算法的3個(gè)準(zhǔn)則。

在映射一個(gè)密碼算法數(shù)據(jù)流圖時(shí)，按照優(yōu)先級(jí)順序?qū)⑵洳鸱殖芍鸺?jí)遞進(jìn)的遞增子圖，以邊為引導(dǎo)，按照遞增子圖的順序依次進(jìn)行映射。圖5所示為對(duì)一個(gè)數(shù)據(jù)流圖拆分的過程。

如圖5所示，在映射由A， B， C， D4個(gè)節(jié)點(diǎn)組成的數(shù)據(jù)流圖時(shí)，按照遞增子圖的順序進(jìn)行映射，對(duì)圖1而言，假設(shè)首先映射節(jié)點(diǎn)A至某個(gè)PE后，從該P(yáng)E出發(fā)沿著陣列對(duì)邊1進(jìn)行搜索，當(dāng)尋找到未被占用的PE時(shí)，停止本次搜索，此條路徑即為邊1對(duì)應(yīng)的映射對(duì)象，而該P(yáng)E為節(jié)點(diǎn)B的映射對(duì)象，即同時(shí)完成了該子圖的布局布線。依次按照遞增子圖的順序進(jìn)行搜索。此圖相應(yīng)的搜索路徑順序?yàn)锳1B→B2C→C4D→D3A。結(jié)合密碼算法的映射特征及CRCLA的硬件結(jié)構(gòu)，采用以下策略來(lái)完成整個(gè)映射過程：

圖5 數(shù)據(jù)流圖拆分映射過程

策略1 起始節(jié)點(diǎn)的映射。就緒隊(duì)列中包含節(jié)點(diǎn)及節(jié)點(diǎn)之間的邊，在進(jìn)行邊的映射之前，首先需要確定一個(gè)起始位PE，然后從這個(gè)PE出發(fā)，對(duì)邊進(jìn)行映射。由于目標(biāo)陣列的第1行PE為輸入行PE，外部數(shù)據(jù)只能通過第1行PE輸入而進(jìn)行運(yùn)算，因此，第1行PE作為起始節(jié)點(diǎn)的映射對(duì)象。由于本文的研究?jī)?nèi)容為空間映射，無(wú)需考慮各個(gè)節(jié)點(diǎn)的時(shí)間上的先后順序，因此，從所有入度為0的起始節(jié)點(diǎn)中，按照扇出邊的值從大到小的順序，選擇扇出邊的值最大的起始節(jié)點(diǎn)進(jìn)行映射。這是因?yàn)樯瘸鲞叺闹递^大的節(jié)點(diǎn)對(duì)互連資源的需求較大，隨著不斷進(jìn)行映射，可用的互連資源和PE個(gè)數(shù)不斷減少，易受其他已經(jīng)映射的節(jié)點(diǎn)占用的資源影響，可能難以找到有效的映射。

策略2 搜索步的構(gòu)造。在確認(rèn)了起始節(jié)點(diǎn)后，需要明確搜索路徑的順序，即構(gòu)造一個(gè)搜索步。為貼合密碼算法的運(yùn)算特性，一個(gè)已映射的節(jié)點(diǎn)可能存在多個(gè)依賴關(guān)系，也就存在多條有向邊，從該節(jié)點(diǎn)出發(fā)，優(yōu)先選擇關(guān)鍵路徑上的邊進(jìn)行映射。而如果優(yōu)先映射非關(guān)鍵路徑的邊，可能會(huì)造成在映射關(guān)鍵路徑的邊時(shí)，由于部分互連資源被占用，需要繞線從而使用了更多的互連資源，不僅影響其他節(jié)點(diǎn)及邊的映射，還可能使得關(guān)鍵路徑的延遲變大從而導(dǎo)致最終的映射性能不佳，甚至?xí)?dǎo)致之后的邊映射失敗。

因此，本文在深度優(yōu)先搜索的基礎(chǔ)上，按照關(guān)鍵路徑優(yōu)先級(jí)最大的方式構(gòu)造搜索步。該過程可以描述為如下步驟：

步驟 1 輸入為算法的數(shù)據(jù)流圖 G，輸出為搜索路徑SE={e1，e2，···，en}。從根節(jié)點(diǎn)v開始，將該節(jié)點(diǎn)標(biāo)記為已訪問；

步驟 2 將關(guān)鍵路徑優(yōu)先納入集合S E中，并將這條關(guān)鍵路徑上的節(jié)點(diǎn)均標(biāo)記為已訪問；

步驟 3 搜索與根節(jié)點(diǎn) v相連的所有的邊e=＜v，u ＞，若節(jié)點(diǎn)u 未被訪問，則將邊e 納入SE中，然后以節(jié)點(diǎn)u為起點(diǎn)，循環(huán)步驟3至與v相連的所有的邊均已被訪問。

步驟 4 若圖中仍然存在未被訪問的節(jié)點(diǎn)，則以該節(jié)點(diǎn)為起始節(jié)點(diǎn)，跳至步驟3，直到所有節(jié)點(diǎn)均被標(biāo)記為已訪問。

步驟 5 得到一條搜索路徑SE={e1，e2，···，en}。之后的映射則按照該搜索路徑進(jìn)行。

策略3 路徑選擇。一個(gè)PE周圍存在著東南西北4個(gè)方向的互連資源，即連接盒CB，當(dāng)確定一條就緒隊(duì)列中待映射的邊e后，通過查找鏈表來(lái)確定哪個(gè)方向的CB沒有被占用；在映射前期，當(dāng)存在多個(gè)方向的CB未被占用時(shí)，有多個(gè)CB可以進(jìn)行選擇。此時(shí)，從已映射的節(jié)點(diǎn)對(duì)應(yīng)的PE進(jìn)行多條路徑搜索。對(duì)于單條路徑搜索，當(dāng)首次搜索到某個(gè)CB周圍存在未映射的PE時(shí)，作為本次路徑的終點(diǎn)，停止本次路徑搜索，并記錄該條路徑所經(jīng)過的CB， SB以及未映射的PE的編號(hào)。定義一條路徑搜索(邊e=＜u，v ＞ 的映射)為

在進(jìn)行路徑搜索時(shí)，為避免大量無(wú)意義的解而造成編譯時(shí)間的浪費(fèi)，算法并不窮舉有向邊的所有可能的映射子圖。當(dāng)搜索到某個(gè)未映射的PE時(shí)，對(duì)路徑的終點(diǎn)PE進(jìn)行分析，定義一個(gè)PE的親和度為通過與該P(yáng)E可進(jìn)行數(shù)據(jù)交互的其他PE的個(gè)數(shù)和數(shù)據(jù)流圖中與待映射節(jié)點(diǎn)u存在直接連接關(guān)系的節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系。通過計(jì)算該P(yáng)E與待映射節(jié)點(diǎn)的親和度來(lái)進(jìn)行取舍，其計(jì)算公式為

式(4)為親和度計(jì)算公式，其中，Conu為除去已映射的節(jié)點(diǎn)，與節(jié)點(diǎn) u有著直接連接關(guān)系的節(jié)點(diǎn)的個(gè)數(shù)；ConPE表示與路徑終點(diǎn)PE能夠進(jìn)行數(shù)據(jù)交互的未映射的PE的個(gè)數(shù)。由公式可知，若Conu＞ConPE，則在后續(xù)的映射過程中會(huì)導(dǎo)致與節(jié)點(diǎn)u 有直接連接關(guān)系的部分節(jié)點(diǎn)映射失敗，因此其親和度值為0；若Conu≤ConPE，則該條路徑的后續(xù)映射能夠滿足其映射需求，此時(shí)，若Conu越接近于ConPE，則該P(yáng)E越符合該節(jié)點(diǎn)u 的映射需求，則其親和度的值越高，其最大值為1。這樣既能夠保證節(jié)點(diǎn) u的直接相鄰節(jié)點(diǎn)被成功映射，又不會(huì)造成資源的浪費(fèi)，保留了其他具有更多可進(jìn)行數(shù)據(jù)交互的PE個(gè)數(shù)的PE，可供后續(xù)節(jié)點(diǎn)的映射。因此，若該P(yáng)E的親和度值為0，則刪除該條搜索路徑。

為使其互連資源盡可能少，在經(jīng)過算法搜索后得到的所有路徑中，篩選出最短的路徑，即所經(jīng)過的CB， SB個(gè)數(shù)最少，從最短的路徑中，選出親和度值最高的路徑，作為最佳路徑，為本次映射的最終方案。若存在多個(gè)最佳路徑，則進(jìn)行記錄，并隨機(jī)挑選一個(gè)路徑作為本次映射的最終方案。

策略4 回溯機(jī)制。該算法采用的搜索方式是啟發(fā)式的，在后續(xù)的節(jié)點(diǎn)的映射過程中，隨著映射的推進(jìn)，由于可用的資源越來(lái)越緊張，可能會(huì)出現(xiàn)映射失敗的情況。因此，采用一種反向回溯機(jī)制，該機(jī)制基于一種稱為回溯表(Failure Table，F(xiàn)T)的數(shù)據(jù)結(jié)構(gòu)[14]。在前向映射某個(gè)節(jié)點(diǎn) vi時(shí)，每次挑選出最佳路徑時(shí)，對(duì)剩下的路徑依照親和度值及路徑大小按照從小到大進(jìn)行排序，因此，回溯表可以表示為FTi=(vi，{Road1，Road2，···，Roadn})， 其中，Roadi則表示從vi的前向節(jié)點(diǎn)對(duì)應(yīng)映射的PE出發(fā)，進(jìn)行搜索得到的路徑，包含經(jīng)過的CB， SB的位置信息及終點(diǎn)PE的位置信息。

若在映射過程中，從某個(gè)節(jié)點(diǎn) vi映射對(duì)應(yīng)的PE出發(fā)的路徑在搜索的過程中，當(dāng)出現(xiàn)以下情況時(shí)：(1)無(wú)法搜索到未映射的PE；(2)所有路徑中的親和度的值均為0；(3)沒有可以進(jìn)行映射的路徑；則進(jìn)行反向回溯，回到在映射節(jié)點(diǎn)vj時(shí)的路徑搜索過程中，在回溯表中刪除所有到達(dá)該P(yáng)E的路徑。之后查找回溯表中的信息，選擇親和度值最大的最短路徑Roadj進(jìn)行映射，并將Roadj從回溯表中刪除，然后進(jìn)行后續(xù)的邊及節(jié)點(diǎn)的映射。當(dāng)出現(xiàn) vj的回溯表為空時(shí)，說明vj及前向路徑僅存在當(dāng)前的一種映射方案，則往前回溯到 vj的前向節(jié)點(diǎn)vi的回溯表中繼續(xù)尋找其他映射方案，并依此類推，直到找到回溯的節(jié)點(diǎn)的回溯表不為空。

4.3 ECLMap完整算法描述

如表1所示，為ECLMap的完整過程的偽代碼。算法的輸入為經(jīng)過任務(wù)劃分后的密碼算法數(shù)據(jù)流圖及CRCLA的資源集合，輸出為最終的映射結(jié)果。

首先，對(duì)算法映射結(jié)果以及回溯表進(jìn)行初始化(行(1) —行(2))；接著依據(jù)策略1對(duì)起始節(jié)點(diǎn)進(jìn)行選取，并依據(jù)策略2構(gòu)造相應(yīng)的搜索步(行(3)—行(5))。然后對(duì)搜索步中的起始節(jié)點(diǎn)進(jìn)行映射，再?gòu)囊延成涞墓?jié)點(diǎn)對(duì)應(yīng)的PE出發(fā)，按照搜索步的順序依次對(duì)每一條邊的映射路徑依據(jù)策略3進(jìn)行搜索，并通過親和度值來(lái)篩選可選路徑，在所有可選路徑中確定最短路徑即為該邊的最終映射方案，該路徑的終點(diǎn)為節(jié)點(diǎn)對(duì)應(yīng)的映射PE，并在回溯表中記錄其他候選方案(行(6)—行(15))。若映射過程中某一條邊沒有可選路徑，映射失敗，則進(jìn)行反向回溯，從而進(jìn)行新的映射(行(16) —行(26))。直到所有的節(jié)點(diǎn)及邊映射完畢后，輸出最終映射結(jié)果。

5 實(shí)驗(yàn)驗(yàn)證與分析

為驗(yàn)證本文提出的ECLMap算法相較于其他算法在密碼算法映射問題上的有效性及優(yōu)勢(shì)，本節(jié)在實(shí)驗(yàn)室前期研制的粗粒度可重構(gòu)密碼邏輯陣列上進(jìn)行測(cè)試，該陣列結(jié)構(gòu)已完成相關(guān)功能驗(yàn)證，在仿真平臺(tái)下使用Verilog HDL進(jìn)行了相應(yīng)的模塊化描述，本文選取了典型的密碼算法AES， DES， A5-1，ZUC和SM3等密碼算法進(jìn)行映射實(shí)驗(yàn)，并利用了綜合仿真驗(yàn)證工具進(jìn)行了功能驗(yàn)證及相關(guān)性能測(cè)試。

采用Intel Core i5- 6300HQ@ 2. 30 GHz CPU及16 GB內(nèi)存環(huán)境進(jìn)行算法映射及仿真測(cè)試。首先，對(duì)算法自身的回溯機(jī)制進(jìn)行了驗(yàn)證，主要體現(xiàn)在對(duì)有無(wú)回溯時(shí)算法映射的成功率進(jìn)行了統(tǒng)計(jì)與分析，其結(jié)果如圖6所示。從圖6可以看出，由于引入了回溯機(jī)制，使得算法在某一步映射失敗時(shí)，可以通過查詢回溯表返回至上一步，選擇其他候選方案進(jìn)行重新映射，一定程度上避免了映射失敗，提高了映射成功率。

表1 ECLMap算法描述

為驗(yàn)證ECLMap算法的高效性，對(duì)算法的編譯時(shí)間進(jìn)行了測(cè)試，并將其與SA[4]， SPKM[5]，EPIMap[15]和2-StepACO[16]等幾種通用的映射算法進(jìn)行了對(duì)比，結(jié)果如圖7所示。從圖中可以看出，本文提出的ECLMap算法對(duì)密碼算法的數(shù)據(jù)流圖與CRCLA的硬件結(jié)構(gòu)之間緊密的聯(lián)系進(jìn)行了充分的考慮，并對(duì)初始的密碼算法的數(shù)據(jù)流圖進(jìn)行了任務(wù)劃分的優(yōu)化，因此在編譯時(shí)間上相較于其他算法有著一定的優(yōu)勢(shì)，平均減少了約25%。

圖6 ECLMap算法映射成功率對(duì)比

圖7 CRCLA密碼算法映射編譯時(shí)間對(duì)比結(jié)果

對(duì)于密碼算法，其更為重要的是映射在CRCLA硬件結(jié)構(gòu)上實(shí)現(xiàn)的性能及功耗。因此，經(jīng)過不同算法運(yùn)行后得到的不同配置方案下的配置信息，在CRCLA仿真平臺(tái)下進(jìn)行映射實(shí)驗(yàn)。表2和表3分別展示了幾種通用的映射算法和本文的ECLMap算法下的映射的性能及1.2 V工作電壓下的功耗結(jié)果對(duì)比。圖8進(jìn)一步直觀地顯示了幾種密碼算法在不同的映射算法下實(shí)現(xiàn)的能效。從圖8可以看出，在編譯時(shí)間優(yōu)于其他算法的同時(shí)，ECLMap算法在映射能效上同樣比其他算法要高，平均提升了約20%，這是因?yàn)镋CLMap算法的設(shè)計(jì)對(duì)于密碼算法更具針對(duì)性，從而能夠滿足密碼算法的高能效映射。

表2 不同映射算法下的密碼算法映射性能(Mbps)

表3 不同映射算法下的密碼算法映射功耗(mW)

圖8 CRCLA密碼算法映射能效對(duì)比結(jié)果

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

為實(shí)現(xiàn)密碼算法在粗粒度密碼邏輯陣列上的高能效映射，對(duì)密碼算法的映射問題進(jìn)行了分析。本文對(duì)密碼算法的數(shù)據(jù)流圖及粗粒度可重構(gòu)密碼邏輯陣列的資源進(jìn)行了相應(yīng)的描述，分析了影響密碼算法映射性能的關(guān)鍵因素及可進(jìn)行提高的方面，并提出了一種以邊為中心的密碼邏輯陣列映射算法ECLMap，算法引入了回溯機(jī)制來(lái)進(jìn)一步確保映射的成功率。實(shí)驗(yàn)表明，在4×4陣列規(guī)模下，該算法無(wú)論是編譯時(shí)間還是映射性能上，相較于其他算法，均具有一定的優(yōu)勢(shì)。下一步將結(jié)合可變的陣列規(guī)模對(duì)算法進(jìn)行改進(jìn)。