Butterfly網絡的置換理論研究*

吳朋庭，李 軍，何衛國，王明東

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

0 引 言

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

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

1 Butterfly網絡的數學理論

圖1為一個Butterfly置換網絡結構，N（N=2n）比特數據對應的Butterfly置換網絡的寬度為N，路由深度為n。

為了描述它的結構特征，需要引入一些定義。

原始數據從右到左第jn比特稱為起點s(jn)，目標數據從右到左第j0比特稱為終點e(j0)，中間第i層數據從右到左第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)在橫坐標上投影的最大距離稱為路由權重w(i)，且w(i)=2i。

以權重w(i)為寬度，第i層數據被劃分的2n-i個區間稱為路由區間 b(i,k)=[(k+1)×2i-1,k×2i]，(0≤k≤2n-i-1)。當k為奇數時，b(i,k)為奇區間ob(i,k)；當k為偶數時，b(i,k)為偶區間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)出發，途經各層路由點r(i,ji)并最終到達終點e(j0)劃過的所有路由線l(i,ji+1→ji)的首尾相連的組合稱為s(jn)到r(i,ji)的路由路徑p(jn,j0)。將路由路徑經過的所有路由點對應的路由方向剝離符號后得到的元素d[i]組成路由向量d={d[n-1],d[n-2],…,d[1],d[0]}。

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

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

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

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

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

假設交點存在于第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。

因此，有：

等式的左側為偶數，等式的右側為奇數，產生矛盾，定理1得證。

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

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

根據式（2），有：

根據定理1，有：

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

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

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

因此，定理2得證。

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

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

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

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

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

（1）根據已知條件求解數據的起始地址；

（2）根據已知條件求解數據的目標地址；

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

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

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

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

2 Butterfly網絡數學理論的應用

2.1 PDEP運算

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

Lee等人發表的論文證明了PDEP運算可以采用Butterfly置換網絡結構實現，并提出了置換遞歸算法來對置換參數進行求解。

整個求解過程在硬件實現時被分解為3個步驟：

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

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

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

作為對比，本文采用第一章提出的Butterfly網絡的置換數學理論對PDEP運算的置換參數求解過程進行推導。

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

根據Butterfly置換網絡數學理論求解置換參數的標準流程如下。

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

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

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

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

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

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

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

從步驟（1）化簡后的PDEP運算結果可以發現，第i層奇區間eb(i,2k+1)和偶區間ob(i,2k)中的對應路由點的起始位置js1和js2相差小于等于2i，因此兩個起始位置的二進制展開式在第i層的組合(js1[i],js2[i])可能有 4種情況——(0,0)、(0,1)、(1,0)和(1,1)。同時，它的對應目標位置的二進制展開式在第i層互為相反數，且其組合(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層以上的路由元素，相應對應著4種不同的修正可能性，其中(0,0)對應位置保持，(0,1)對應左側位置保持，(1,0)對應右側位置保持，(1,1)對應位置交換。至此，路由向量修正算法可以簡化為：當jd1[i]＆jd2[i]=1時執行位置交換，否則執行位置保持。

進一步分析發現，當(jd1[i],jd2[i])為(1,0)、(0,0)、(0,1)這3種組合時，對應的起始位置組合(js1[i],js2[i])分別為 (0,0)、(1,0)、(1,1)。由于 js1和 js2相差小于等于2i，因此這3種組合對應的兩個起始位置的二進制展開式在第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層相同的路由區間，其對應的目標位置二進制展開式在第i+1層到第n-1層有：

由此可得：

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

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

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

表1 32 bit PDEP運算置換參數產生模塊對比

2.2 ROT運算

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

Lee等人發表的論文證明了RROT運算也可以采用Butterfly置換網絡結構實現，同時提出了置換遞歸算法來對置換參數進行求解。

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

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

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

作為對比，本文采用第一章提出的Butterfly網絡的置換數學理論對RROT運算的置換參數求解過程進行推導。

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

根據Butterfly置換網絡數學理論求解置換參數的標準流程如下。

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

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

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

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

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

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

令A=je、B=m，則可將原算法轉化為：

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

得到：

代入進位產生函數和進位傳遞函數：

當je[i]=0時，有：

當je[i]=1時，有：

因此，得到遞歸函數：

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

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

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

最終得到：

由此可見，利用Butterfly網絡的數學理論直接推導的結果與Lee提出的遞歸算法相同，因此兩種算法實現的置換參數產生模塊的優化程度一致，如圖16所示。

3 結 語

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