Butterfly網(wǎng)絡(luò)的置換理論研究*

吳朋庭，李 軍，何衛(wèi)國，王明東

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引 言

Butterfly網(wǎng)絡(luò)廣泛應(yīng)用于比特擴散、比特循環(huán)移位等動態(tài)比特置換運算模塊的硬件實現(xiàn)。以往的研究主要集中于挖掘其數(shù)據(jù)通路的遞歸特性[1-6]。例如，比特擴散運算。在每一層置換參數(shù)求解的過程中，Lee發(fā)現(xiàn)了一些Butterfly置換網(wǎng)絡(luò)的遞歸特性，并利用這些特性對部分運算過程進行了簡化[1]。簡化的過程非常精妙甚至有些偶然，然而在數(shù)學的世界里面，偶然現(xiàn)象一定存在其必然的數(shù)學理論。所以，無論研究人員歸納出的Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)的遞歸特性多么精妙，都是建立在它的數(shù)學理論基礎(chǔ)之上的衍生特征。只要充分利用其數(shù)學理論對運算進行推導(dǎo)，就可能獲得優(yōu)化程度不低于現(xiàn)有遞歸算法的方案。

本文旨在研究Butterfly網(wǎng)絡(luò)的置換數(shù)學理論及其應(yīng)用。首先采用數(shù)字與符號對Butterfly網(wǎng)絡(luò)結(jié)構(gòu)進行定義，其次利用這些定義總結(jié)歸納Butterfly網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)學理論并予以證明，最后利用Butterfly網(wǎng)絡(luò)的數(shù)學理論重新分析比特擴散和循環(huán)移位等特殊的置換運算，以期得到優(yōu)化程度更好的硬件實現(xiàn)方案或者更加簡單的置換參數(shù)求解過程，為研究人員進一步分析其他置換運算提供新的思路。

1 Butterfly網(wǎng)絡(luò)的數(shù)學理論

圖1為一個Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)，N（N=2n）比特數(shù)據(jù)對應(yīng)的Butterfly置換網(wǎng)絡(luò)的寬度為N，路由深度為n。

為了描述它的結(jié)構(gòu)特征，需要引入一些定義。

原始數(shù)據(jù)從右到左第jn比特稱為起點s(jn)，目標數(shù)據(jù)從右到左第j0比特稱為終點e(j0)，中間第i層數(shù)據(jù)從右到左第ji比特稱為路由點r(i,ji)，第i+1層路由點r(i+1,ji+1)到第i層路由點r(i,ji)之間的路線稱為路由線l(i,ji+1→ji)，路由線l(i,ji+1→ji)在橫坐標上投影的最大距離稱為路由權(quán)重w(i)，且w(i)=2i。

以權(quán)重w(i)為寬度，第i層數(shù)據(jù)被劃分的2n-i個區(qū)間稱為路由區(qū)間 b(i,k)=[(k+1)×2i-1,k×2i]，(0≤k≤2n-i-1)。當k為奇數(shù)時，b(i,k)為奇區(qū)間ob(i,k)；當k為偶數(shù)時，b(i,k)為偶區(qū)間eb(i,k)。路由線l(i,ji+1→ji)從上而下劃過的方向在橫坐標上的投影稱為路由方向d(i,ji+1→ji)，且當ji∈ob(i,k)時 d(i,ji+1→ji)∈ {0,1}，當 ji∈ eb(i,k)時 d(i,ji+1→ji)∈{-1,0}，其中“1”“-1”“0”分別表示向左、向右和保持。

從起點s(jn)出發(fā)，途經(jīng)各層路由點r(i,ji)并最終到達終點e(j0)劃過的所有路由線l(i,ji+1→ji)的首尾相連的組合稱為s(jn)到r(i,ji)的路由路徑p(jn,j0)。將路由路徑經(jīng)過的所有路由點對應(yīng)的路由方向剝離符號后得到的元素d[i]組成路由向量d={d[n-1],d[n-2],…,d[1],d[0]}。

綜上所述，存在以下路由等式：

由于位移主要發(fā)生在橫坐標上，僅考慮橫坐標上的投影，則有：

定理1從任一起點s(jn)出發(fā)到任一終點e(j0)的路由路徑僅有一條。

證明：假設(shè)從起點s(jn)出發(fā)到任一終點e(j0)的路由路徑有兩條，則有：

由于兩條路由路徑的終點相等，那么這兩條路徑在終點或者終點之前必定存在一個交點，且在此之后匯聚成一條路徑。

假設(shè)交點存在于第t層，則有：

由于兩條路徑在路由點r(t,jt)處匯聚，因此d2(t)≠ d1(t)。

當 r(t,jt)∈ ob(i,k)時，d2(t)、d1(t)∈ {0,1}， 則|d2(t)-d1(t)|=1。

當 r(t,jt)∈ eb(i,k)時，d2(t)、d1(t)∈ {-1,0}，則|d2(t)-d1(t)|=1。

因此，有：

等式的左側(cè)為偶數(shù)，等式的右側(cè)為奇數(shù)，產(chǎn)生矛盾，定理1得證。

定理2任一起點s(jn)出發(fā)到任一終點e(j0)的路由傳遞過程是兩點橫坐標的異或運算。

證明：將起點s(jn)和終點e(j0)的橫坐標做二進制數(shù)展開，得：

根據(jù)式（2），有：

根據(jù)定理1，有：

當j0[i]=1時，表示路由點落在第i層的奇區(qū)間，d(i)的符號為“+”，有：

當j0[i]=0時，表示路由點落在第i層的偶區(qū)間，d(i)的符號為“-”，有：

對于不含進位的單比特加減法，有：

因此，定理2得證。

由于Butterfly置換網(wǎng)絡(luò)的數(shù)學理論本質(zhì)就是初始坐標與目標坐標的二進制展開式的按位異或運算。因此，只要知道輸入數(shù)據(jù)的初始坐標和目標坐標，就能通過異或運算快速得到該數(shù)據(jù)的路由向量d，從而為求解Butterfly置換參數(shù)做好準備。

如圖2所示，初始坐標為“5”和“3”的數(shù)據(jù)需要通過Butterfly網(wǎng)絡(luò)分別置換到“2”和“5”的目標位置。它的各層置換參數(shù)與路由向量元素的數(shù)值相等，位置正好處于各層的路由點r(i,ji)上。

因此，求出路由路徑各層路由點的橫坐標就能快速得到Butterfly網(wǎng)絡(luò)的置換參數(shù)。根據(jù)路由路徑的定義和異或運算的交換特性，可得遞歸算法：

由于已知終點e(j0)，因此可以選擇從終點橫坐標j0出發(fā)逐層推導(dǎo)出路徑上各路由點的橫坐標ji，然后將各層的路由元素放置到該位置，得到置換參數(shù)。

綜上所述，如圖3所示，求解某置換運算的Butterfly置換參數(shù)的算法步驟可以分解為：

（1）根據(jù)已知條件求解數(shù)據(jù)的起始地址；

（2）根據(jù)已知條件求解數(shù)據(jù)的目標地址；

（3）初始地址和目標地址異或得到路由向量集合，設(shè)置i=0；

（4）使用路由向量第i層元素d[i],，修正其上所有層路由向量元素d[i+1]～d[n-1]的位置，i++；

（5）重復(fù)步驟（4）直到i=n-1，即得到Butterfly置換參數(shù)。

可以選擇目標地址為參照坐標系，由此合并步驟（1）和步驟（2），調(diào)整為根據(jù)已知條件求解目標地址上數(shù)據(jù)來源的起始地址。

2 Butterfly網(wǎng)絡(luò)數(shù)學理論的應(yīng)用

2.1 PDEP運算

如圖4所示，PDEP運算是一種比特擴散運算。它根據(jù)置換掩碼數(shù)據(jù)中“1”的數(shù)量m，選中輸入數(shù)據(jù)最低m比特數(shù)據(jù)，然后將選中的這些數(shù)據(jù)從右至左第j比特移位到掩碼數(shù)據(jù)中從右至左第j個“1”對應(yīng)的位置上，0≤j≤m-1。

Lee等人發(fā)表的論文證明了PDEP運算可以采用Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)實現(xiàn)，并提出了置換遞歸算法來對置換參數(shù)進行求解。

整個求解過程在硬件實現(xiàn)時被分解為3個步驟：

（1）計算置換掩碼mask在位置區(qū)間[j,0]，(0≤j≤N-1）中“1”的數(shù)量 POPCNT(mask[ j:0])；

（2）在第i行，對k(i)=2i個“1”執(zhí)行LROT C(1k(i),POPCNT[mask[(2t+1)×k(i)-1:0])]運 算 ，其 中0 ≤ i≤ log2N-1，0 ≤t≤ 2n-i-1；

（3）將（2）中計算的結(jié)果按照左對齊的方式放在第i行第(2t+1)×k(i)-1列的位置，從而得到完整的置換參數(shù)[1]。

作為對比，本文采用第一章提出的Butterfly網(wǎng)絡(luò)的置換數(shù)學理論對PDEP運算的置換參數(shù)求解過程進行推導(dǎo)。

為了方便描述，以下采用8 bit PDEP運算進行分析，如圖5所示。

根據(jù)Butterfly置換網(wǎng)絡(luò)數(shù)學理論求解置換參數(shù)的標準流程如下。

（1）根據(jù)已知條件求解各目標位置上數(shù)據(jù)的起始位置。該運算的已知條件包括置換掩碼和輸入數(shù)據(jù)，輸入數(shù)據(jù)作為被置換的對象，本身并不包含任何位置信息，因此可以利用的已知條件只有置換掩碼。

PDEP運算的定義是將輸入數(shù)據(jù)從右至左的第js比特din[js]置換到輸出數(shù)據(jù)中對應(yīng)置換掩碼從右至左的第js個“1”的位置上。把定義反向推導(dǎo)即可得知，置換到輸出數(shù)據(jù)第je比特dout[je]的數(shù)據(jù)來源是置換掩碼mask[je]對應(yīng)位置的“1”是其從右至左的第幾個“1”，也就是mask[je]對應(yīng)位置的“1”在整個置換掩碼中的編號。

如圖6所示，置換掩碼從右至左第1個“1”編號為0，因此其je位置上的“1”的編號是je位置右邊所有“1”的數(shù)量和，即POPCNT(mask[ je:0])。所以，比特擴散的輸出有效位，對應(yīng)的數(shù)據(jù)來源位置即為POPCNT(mask[ je:0])。由于其他非擴散有效位的數(shù)據(jù)在輸出時將統(tǒng)一被置換掩碼過濾為“0”，其運算中間結(jié)果是多少并不重要。為了簡化運算，可以與有效位的數(shù)據(jù)來源算法保持一致。

綜上所述，目標位置je上數(shù)據(jù)的起始位置求解算法為POPCNT(mask[ je:0])。

（2）初始排序和目標排序異或得到路由向量集合。根據(jù)（1）中的算法，可以計算得到N比特PDEP運算輸出數(shù)據(jù)的初始排序為：

只需將其與目標排序{N-1,N-2,…,2,1,0}做異或操作，就可以得到Butterfly網(wǎng)絡(luò)的路由向量集合，如圖7所示。

（3）對路由向量集合進行修正得到置換參數(shù)。該步驟的一般處理辦法是利用路由向量集合中第i層的元素，對第i+1層到第n-1層的元素進行置換修正，然而將額外引入一個Butterfly網(wǎng)絡(luò)的硬件開銷，也沒有進一步優(yōu)化運算復(fù)雜度，不符合利用Butterfly置換網(wǎng)絡(luò)數(shù)學理論求解問題的預(yù)期。正確的做法是進一步挖掘置換的本質(zhì)就是異或帶來的運算特性，如圖8所示。

從步驟（1）化簡后的PDEP運算結(jié)果可以發(fā)現(xiàn)，第i層奇區(qū)間eb(i,2k+1)和偶區(qū)間ob(i,2k)中的對應(yīng)路由點的起始位置js1和js2相差小于等于2i，因此兩個起始位置的二進制展開式在第i層的組合(js1[i],js2[i])可能有 4種情況——(0,0)、(0,1)、(1,0)和(1,1)。同時，它的對應(yīng)目標位置的二進制展開式在第i層互為相反數(shù)，且其組合(je1[i],je2[i])只有一種情況(1,0)。因此，兩者異或運算后得到的路由向量在第i層的組合(jd1[i],jd2[i])也有(1,0)、(1,1)、(0,0)和(0,1)這4種情況。

(jd1[i],jd2[i])的4種組合決定了路由向量在第i層以上的路由元素，相應(yīng)對應(yīng)著4種不同的修正可能性，其中(0,0)對應(yīng)位置保持，(0,1)對應(yīng)左側(cè)位置保持，(1,0)對應(yīng)右側(cè)位置保持，(1,1)對應(yīng)位置交換。至此，路由向量修正算法可以簡化為：當jd1[i]＆jd2[i]=1時執(zhí)行位置交換，否則執(zhí)行位置保持。

進一步分析發(fā)現(xiàn)，當(jd1[i],jd2[i])為(1,0)、(0,0)、(0,1)這3種組合時，對應(yīng)的起始位置組合(js1[i],js2[i])分別為 (0,0)、(1,0)、(1,1)。由于 js1和 js2相差小于等于2i，因此這3種組合對應(yīng)的兩個起始位置的二進制展開式在第i+1層到第n-1層的組合(js1[n-1:i+1],js2[n-1:i+1])只有 (0n-i-2,0n-i-2)和 (1n-i-2,1n-i-2)兩種，即js1[n-1:i+1]=js2[n-1:i+1]。同時，由于(jd1[i],jd2[i])來源于第i+1層到第n-1層相同的路由區(qū)間，其對應(yīng)的目標位置二進制展開式在第i+1層到第n-1層有：

由此可得：

這意味著當 (jd1[i],jd2[i])為(1,0)、(0,0)、(0,1)這3種組合時，其i+1層到n-1層的待修正路由向量是相等的，因此執(zhí)行“位置交換”還是執(zhí)行“位置保持”并不影響結(jié)果。此時，路由向量修正算法可以進一步簡化為：無論(jd1[i],jd2[i])是什么值，都對第i+1層到n-1層的路由向量執(zhí)行奇偶區(qū)間對應(yīng)位置的交換修正，如圖9所示。

由于本步驟的修正運算是固定的，對于硬件實現(xiàn)來說無需引入額外的運算模塊，只需要將步驟2中計算結(jié)果的相應(yīng)比特位利用拼接符“{}”指定固定的硬連線就可以實現(xiàn)。相對于Lee提出的遞歸算法，將POPCNT+LROTC運算轉(zhuǎn)化為POPCNT+XOR運算，存在優(yōu)化的可能性。

采用synopsys_design compiler-2018.06-SP1工具，結(jié)合UMC28nm工藝12track混合標準單元庫(sc12mcpp140z_l28hpc_hpk_lvt_c30_ssg_cworst_max_0p81v_125c.db)，對兩種算法實現(xiàn)的32 bit PDEP運算的置換參數(shù)產(chǎn)生模塊進行綜合對比。結(jié)果在時序約束為0.5 ns的情況下，獲得了15%的面積優(yōu)化，如表1所示。

表1 32 bit PDEP運算置換參數(shù)產(chǎn)生模塊對比

2.2 ROT運算

ROT運算是一種特殊的移位運算，根據(jù)移位方向d和移位位數(shù)m，選中輸入數(shù)據(jù)的最低/最高n比特數(shù)據(jù)，然后將選中的這些數(shù)據(jù)移位到剩余數(shù)據(jù)的左側(cè)/右側(cè)，d∈{-1,1}，0≤m≤N-1。為了方便描述和推導(dǎo)，本文主要考慮RROT運算，如圖10所示。

Lee等人發(fā)表的論文證明了RROT運算也可以采用Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)實現(xiàn)，同時提出了置換遞歸算法來對置換參數(shù)進行求解。

整個求解過程在硬件實現(xiàn)的時候被分解為兩個步驟：

（1）對第 i行執(zhí)行LROTC(0k(i),(m)mod2i+1)運算，其中k(i)=2i，0≤i≤log2N-1；

（2）將2n-i-1個LROTC(0m(i),(m)mod2i+1)拼接在一起得到第i層置換參數(shù)[1]。

作為對比，本文采用第一章提出的Butterfly網(wǎng)絡(luò)的置換數(shù)學理論對RROT運算的置換參數(shù)求解過程進行推導(dǎo)。

為了方便描述，以下采用8 bit RROT運算進行分析。圖11為一個8 bit的RROT置換運算。

根據(jù)Butterfly置換網(wǎng)絡(luò)數(shù)學理論求解置換參數(shù)的標準流程如下。

（1）根據(jù)已知條件求解各目標位置上數(shù)據(jù)的起始位置。RROT運算的定義是根據(jù)移位位數(shù)m把輸入數(shù)據(jù)最右側(cè)m比特din[m-1:0]置換到輸出數(shù)據(jù)中最左側(cè)的m比特dout[N-1:m]的位置上，把輸入數(shù)據(jù)最左側(cè)N-m比特din[N-1:m]置換到輸出數(shù)據(jù)中最右側(cè)的m比特dout[N-m-1:0]的位置上。因此，有dout={din[m-1:0],din[N-1:m]}，輸出數(shù)據(jù)各比特對應(yīng)的起始位置為：

綜上所述，目標位置je上數(shù)據(jù)的起始位置求解算法為(je+m)mod2n，如圖12所示。

（2）初始排序和目標排序異或得到路由向量集合。根據(jù)（1）中的算法，可以得到N比特RROT運算輸出數(shù)據(jù)的初始排序為：

只需將其與目標排序{N-1,N-2,…,2,1,0}做異或操作，就可以得到Butterfly網(wǎng)絡(luò)的路由向量集合，如圖13所示。

至此，N（N=2n）比特RROT運算置換參數(shù)的求解算法轉(zhuǎn)化為N路并行“n比特加法+異或”運算。雖然邏輯深度由2n降為n，但是N個n比特加法器消耗的硬件資源不容忽視。值得注意的是，第j路n比特加法的其中一個輸入是常數(shù)je，因此n比特加法邏輯可以進一步化簡。

根據(jù)路由向量d(je)的求解算法[(je+m)⊕je]mod2n，由于mod2n屬于硬件運算模塊的附加屬性，為了簡化，在后續(xù)推導(dǎo)過程將其省略。

令A(yù)=je、B=m，則可將原算法轉(zhuǎn)化為：

代入全加器的邏輯表達式：

得到：

代入進位產(chǎn)生函數(shù)和進位傳遞函數(shù)：

當je[i]=0時，有：

當je[i]=1時，有：

因此，得到遞歸函數(shù)：

（3）對路由向量集合進行修正得到置換參數(shù)。從步驟（1）化簡后的RROT運算結(jié)果可以發(fā)現(xiàn)，第i層奇區(qū)間eb(i,2k+1)和偶區(qū)間ob(i,2k)中的對應(yīng)路由點的起始位置js1和js2相差始終等于2i，因此兩個起始位置的二進制展開式在第i層的組合(js1[i],js2[i])可能有兩種情況(1,0)和(0,1)。同時，它的對應(yīng)目標位置的二進制展開式在第i層互為相反數(shù)，且其組合(je1[i],je2[i])只有一種情況(1,0)。因此，兩者異或運算后得到的路由向量在第i層的組合(jd1[i],jd2[i])只有(0,0)和(1,1)兩種情況，如圖14所示。

(jd1[i],jd2[i])的兩種組合決定了路由向量在第i層以上的路由元素，相應(yīng)的對應(yīng)著兩種不同的修正可能性，其中(0,0)對應(yīng)位置保持，(1,1)對應(yīng)位置交換。至此，路由向量修正算法可以簡化為：當jd1[i]＆jd2[i]=1時執(zhí)行位置交換，否則執(zhí)行位置保持。

這意味著當(jd1[i],jd2[i])為(0,0)組合時，其i+1層到n-1層的待修正路由向量是相等的，因此執(zhí)行“位置交換”還是執(zhí)行“位置保持”并不影響結(jié)果。此時，路由向量修正算法可以進一步簡化為：無論(jd1[i],jd2[i])是什么組合，都對第i+1層到n-1層的路由向量執(zhí)行奇偶區(qū)間對應(yīng)位置的交換修正，如圖15所示。

最終得到：

由此可見，利用Butterfly網(wǎng)絡(luò)的數(shù)學理論直接推導(dǎo)的結(jié)果與Lee提出的遞歸算法相同，因此兩種算法實現(xiàn)的置換參數(shù)產(chǎn)生模塊的優(yōu)化程度一致，如圖16所示。

3 結(jié) 語

本文通過數(shù)字表示的方法定義了Butterfly網(wǎng)絡(luò)結(jié)構(gòu)，通過數(shù)學方法深入研究網(wǎng)絡(luò)結(jié)構(gòu)的性質(zhì)和特征，歸納總結(jié)出Butterfly網(wǎng)絡(luò)的置換數(shù)學理論。此外，利用該數(shù)學理論重新分析了PDEP運算和RROT運算。對于32 bit PDEP運算，在時序約束同為0.5 ns的情況下，置換參數(shù)產(chǎn)生模塊的硬件實現(xiàn)方案獲得了15%的面積優(yōu)化。對于RROT運算，獲得了更加直觀的置換參數(shù)推算過程。研究可為研究人員進一步分析開發(fā)Butterfly網(wǎng)絡(luò)在其他比特置換運算中的應(yīng)用提供了新思路。