RPRU：一種面向處理器的比特抽取與移位統(tǒng)一架構(gòu)

馬 超 戴紫彬 李 偉 南龍梅 金 羽

1(國(guó)家高性能集成電路(上海)設(shè)計(jì)中心 上海 201204)2(解放軍信息工程大學(xué) 鄭州 450001)3(集成電路國(guó)家重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)) 上海 200433)(wenlu_ma@163.com)

Fig. 1 8-bit Inverse Butterfly network圖1 8-bit Inverse Butterfly網(wǎng)絡(luò)

循環(huán)移位與比特抽取這2種操作被廣泛應(yīng)用于密碼編碼學(xué)、圖像處理、多媒體應(yīng)用以及生物統(tǒng)計(jì)學(xué)[1-4]等眾多領(lǐng)域.如在密碼學(xué)中，為了增加明文的“擴(kuò)散”程度，AES(advanced encryption standard)，LED(light encryption device)等大多數(shù)密碼算法均使用到了這2種細(xì)粒度位級(jí)操作，以提升密碼算法的安全性[5-6].然而，目前它們?cè)谕ㄓ锰幚砥髦械挠布O(shè)計(jì)策略大多采用孤立的方式，構(gòu)造各自專用的硬件單元[7].其中循環(huán)移位操作多基于桶型移位器、對(duì)數(shù)移位器實(shí)現(xiàn)[8]，比特抽取操作多基于組合排序網(wǎng)絡(luò)[9]、多級(jí)動(dòng)態(tài)互連網(wǎng)絡(luò)Inverse Butterfly實(shí)現(xiàn)[10].

然而循環(huán)移位與比特抽取操作都涉及到數(shù)據(jù)位置的重新排列，能夠利用位級(jí)置換實(shí)現(xiàn).若將它們彼此孤立設(shè)計(jì)，必將造成硬件資源的重復(fù)開銷[11].因此Hilewitz等人[12]提出了一種基于Inverse Butterfly網(wǎng)絡(luò)的移位-抽取單元，該單元首次將循環(huán)移位和復(fù)雜比特抽取這2種不同操作，統(tǒng)一在了同一網(wǎng)絡(luò)架構(gòu)下.其中比特抽取操作由于實(shí)際應(yīng)用的廣泛性，而被Intel在2013年發(fā)布的Haswell處理器指令集所支持[13].Chang等人[14]在Lee等人的基礎(chǔ)上對(duì)循環(huán)移位路由信息生成算法進(jìn)行了改進(jìn)，提出了具有高度并行化特征的路由信息生成算法，大幅提升了循環(huán)移位操作在Inverse Butterfly網(wǎng)絡(luò)中的實(shí)現(xiàn)性能.然而，盡管Hilewitz等人將循環(huán)移位和比特抽取操作統(tǒng)一在了一個(gè)架構(gòu)下，但針對(duì)這2種操作卻設(shè)計(jì)了各自獨(dú)立的路由算法.因此該單元在硬件實(shí)現(xiàn)時(shí)，就必須對(duì)應(yīng)2套完全不同的路由算法生成電路，這在一定程度上增加了硬件設(shè)計(jì)的復(fù)雜性，消耗了處理器中寶貴的硬件資源.Chang等人雖然在一定程度上提升了循環(huán)移位操作的處理性能，但其并行化的路由算法只針對(duì)循環(huán)移位操作，其實(shí)質(zhì)是對(duì)文獻(xiàn)[12]中循環(huán)移位路由算法的一種改進(jìn)，該單元若要支持比特抽取操作，則必須在硬件中增加相應(yīng)地路由算法電路，這仍然需要消耗額外的硬件資源.

因此，本文通過(guò)深入分析Inverse Butterfly網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及數(shù)據(jù)流特征，提出了一種能夠同時(shí)支持循環(huán)移位和比特抽取的統(tǒng)一路由信息生成算法.該算法不僅并行度高，硬件實(shí)現(xiàn)簡(jiǎn)潔，而且它還將這2種不同位級(jí)操作實(shí)現(xiàn)了從架構(gòu)統(tǒng)一到路由算法統(tǒng)一的跨越.

1 相關(guān)研究

圖1描述了一個(gè)8-bit位寬的Inverse Butterfly動(dòng)態(tài)互連網(wǎng)絡(luò)(N=8)，它可以通過(guò)改變各級(jí)開關(guān)狀態(tài)實(shí)現(xiàn)不同結(jié)點(diǎn)之間的連接，使系統(tǒng)具有自重構(gòu)能力，從而靈活地完成數(shù)據(jù)的重新排列[15].該網(wǎng)絡(luò)有l(wèi)gN級(jí)從上到下依次為第1級(jí)、第2級(jí)、第3級(jí)，每一級(jí)由N2個(gè)2輸入交叉開關(guān)構(gòu)成.每一個(gè)交叉開關(guān)由2個(gè)2選1數(shù)據(jù)選擇器組成，網(wǎng)絡(luò)一共有2N2×lg N種置換結(jié)果.數(shù)據(jù)在進(jìn)入Inverse Butterfly網(wǎng)絡(luò)各級(jí)前以2i-1-bit(i為級(jí)數(shù))為間距進(jìn)行兩兩分組，形成2-bit數(shù)據(jù)對(duì).然后將分組后的數(shù)據(jù)對(duì)輸入到2輸入交叉開關(guān)中，再通過(guò)適當(dāng)?shù)穆酚伤惴▉?lái)配置各交叉開關(guān)狀態(tài)，從而完成某些特定置換操作.從圖1左邊的數(shù)據(jù)流圖中還可以看出，網(wǎng)絡(luò)第i級(jí)有N/2i個(gè)位寬為2i-bit的子蝶網(wǎng)絡(luò)，從左至右依次為Subi-ibfly1～Subi-ibflyN/2i，且各子蝶網(wǎng)絡(luò)中數(shù)據(jù)不發(fā)生任何交互.例如當(dāng)i=1時(shí)，網(wǎng)絡(luò)第1級(jí)有4個(gè)位寬為2-bit的子蝶網(wǎng)絡(luò)，從左至右依次為Sub1-ibfly1～Sub1-ifbly4，各子蝶網(wǎng)絡(luò)中數(shù)據(jù)沒(méi)有交互通路.若把該網(wǎng)絡(luò)最后1級(jí)舍棄，剩下的部分可以看成2個(gè)獨(dú)立的以N/2-bit為位寬的Inverse Butterfly，它與N-bit位寬的Inverse Butterfly結(jié)構(gòu)相似只是規(guī)模較小，因此該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有迭代和遞歸特性.

比特抽取操作(parallel bit extract, PEX)是將控制序列R3中為“1”的控制位對(duì)應(yīng)在序列R2中的數(shù)據(jù)并行地抽取出來(lái)依次排在目的序列R1的最右側(cè)，同時(shí)將無(wú)關(guān)數(shù)據(jù)置“0”，從而并行地提取出后續(xù)操作所需的比特?cái)?shù)據(jù)，如圖2所示.由于控制序列R3(假設(shè)為N-bit)取值范圍廣泛，共有2N種，因此并行抽取操作硬件實(shí)現(xiàn)較為復(fù)雜.Lee等人[16]最早提出了基于組合邏輯實(shí)現(xiàn)比特抽取的方案，該方案硬件實(shí)現(xiàn)資源消耗極高，且電路延遲較大.Dimitrakopoulos等人[17]隨后又基于增強(qiáng)型歸并排序網(wǎng)絡(luò)提出了一種硬件資源消耗較低的比特抽取硬件單元，但該單元僅能夠?qū)崿F(xiàn)比特抽取操作，不具有功能擴(kuò)展性.Hilewitz等人[18]通過(guò)研究比特抽取在Inverse Butterfly網(wǎng)絡(luò)的實(shí)現(xiàn)原理，提出了基于該網(wǎng)絡(luò)的比特抽取路由信息生成算法，并構(gòu)建了基于該網(wǎng)絡(luò)的比特抽取硬件單元.該單元與ALU的延遲和面積相差無(wú)幾，且操作數(shù)類型為“2源1目的”形式，因此使其具備集成于通用處理器內(nèi)部的條件，如圖2中右半部分所示.

Fig. 2 Functions and implementation of PEX instruction圖2 PEX指令功能及硬件實(shí)現(xiàn)

Fig. 3 Evolution of traditional rotation shifter圖3 傳統(tǒng)移位器的發(fā)展趨勢(shì)

循環(huán)移位操作(rotation)主要基于對(duì)數(shù)移位器實(shí)現(xiàn)，其結(jié)構(gòu)如圖3(a)所示.一個(gè)N-bit輸入的數(shù)據(jù)，共有l(wèi)gN級(jí)每級(jí)有N個(gè)2選1數(shù)據(jù)器，數(shù)據(jù)在每一級(jí)可以按照2的冪指數(shù)進(jìn)行移位或保持不變.該結(jié)構(gòu)的優(yōu)點(diǎn)是移位位數(shù)S的二進(jìn)制數(shù)(slg N-1,slg N-2,…,s0)可直接作為lgN級(jí)開關(guān)的控制信號(hào)，電路面積小且移位處理速率高；缺點(diǎn)是移位模式單一，只能實(shí)現(xiàn)固定位寬的循環(huán)左移或右移操作.Hilewitz等人在文獻(xiàn)[12]中首次提出了基于Inverse Butterfly網(wǎng)絡(luò)的循環(huán)移位路由信息生成算法，將傳統(tǒng)移位操作與復(fù)雜比特抽取操作的硬件功能單元統(tǒng)一在了一個(gè)架構(gòu)下，為可重構(gòu)復(fù)雜移位器的發(fā)展提供一條新思路，如圖3(b)所示.

由上述分析可知，比特抽取和循環(huán)移位這2種不同位操作，已經(jīng)從以往孤立的設(shè)計(jì)方法過(guò)度到統(tǒng)一架構(gòu)下的可重構(gòu)實(shí)現(xiàn)方案，這種研究思路的轉(zhuǎn)變有效地降低了原架構(gòu)的資源消耗.然而，該方案在硬件設(shè)計(jì)時(shí)仍然需要2套不同的路由算法生成電路，硬件電路開銷具有可減少的可能.下面，本文將重點(diǎn)研究這2種操作在Inverse Butterfly網(wǎng)絡(luò)中數(shù)據(jù)在網(wǎng)絡(luò)各級(jí)的流動(dòng)特點(diǎn)，進(jìn)而提取出它們之間的共性邏輯.使這2種操作不僅能夠在一個(gè)架構(gòu)下實(shí)現(xiàn)，而且路由算法也能共享，以達(dá)到進(jìn)一步節(jié)省資源的目的.

Fig. 4 Shift rules of special pairs under switch state “through”圖4 直通狀態(tài)下特殊對(duì)移位規(guī)律

2 統(tǒng)一路由算法研究

2.1 循環(huán)移位與比特抽取操作實(shí)現(xiàn)原理

性質(zhì)1. 在Butterfly網(wǎng)絡(luò)的第i級(jí)，有2i-1個(gè)位寬為w=N/2i-1的子蝶網(wǎng)絡(luò)，若將各子蝶網(wǎng)絡(luò)中初始輸入數(shù)據(jù)(位寬為w=N/2i-1)循環(huán)左移S-bit，那么通過(guò)調(diào)整初始路由控制信息，其相應(yīng)的初始輸出數(shù)據(jù)能夠以左、右2個(gè)部分(位寬為w/2-bit)分別完成S-bit循環(huán)左移位.

證明. 選取任意一個(gè)在第i級(jí)的子蝶網(wǎng)絡(luò)為例，如圖4(a)所示.該子蝶網(wǎng)絡(luò)數(shù)據(jù)位寬為w-bit，且初始由信息為全“0”即所有開關(guān)為直通狀態(tài).當(dāng)初始輸入數(shù)據(jù)以w為位寬循環(huán)左移1位時(shí)，圖4(b)中左半部分的初始輸入數(shù)據(jù)(上層灰色方塊部分)中最高位(w-1)將被移位到右半部分的最低位，同時(shí)右半部分中的最高位數(shù)據(jù)(w2-1)將越過(guò)子蝶網(wǎng)絡(luò)的中線到左半部分的最低位，其余數(shù)據(jù)僅左移1位并沒(méi)有改變其初始所屬的部分.本文將左、右2部分中最高位bit數(shù)據(jù)組成1個(gè)特殊對(duì)，如圖4(b)中虛線圓框所示.它們不僅被同一個(gè)路由信息控制且在循環(huán)移位時(shí)它們都將跨越網(wǎng)絡(luò)邊界，到達(dá)對(duì)方初始所屬的部分中.若初始控制信息序列也隨著初始輸入數(shù)據(jù)循環(huán)左移1位從“00…00”→“0…000”，那么特殊對(duì)的輸出數(shù)據(jù)將對(duì)調(diào)彼此原屬的部分，如圖4(c)所示.與圖4(b)的初始輸出數(shù)據(jù)相比，僅有特殊對(duì)彼此調(diào)換了原有所屬的部分，其余的初始輸出數(shù)據(jù)僅僅是左移1位.處于i級(jí)的輸入數(shù)據(jù)對(duì)，能夠在相應(yīng)路由控制信息的作用下，完成彼此原有位置的互換或者保持原狀.若將圖4(b)中特殊對(duì)所對(duì)應(yīng)的路由控制信息取反即“0001”，那么該特殊對(duì)將重新回到原來(lái)所屬的部分中的最低位，且輸出序列相當(dāng)于初始輸出序列從中間分成左右2個(gè)部分，各部分內(nèi)數(shù)據(jù)循環(huán)左移1位的結(jié)果，如圖4(d)所示.

若該網(wǎng)絡(luò)再完成1次1-bit循環(huán)左移，初始輸入的下一對(duì)數(shù)據(jù)將成為特殊對(duì)即(w-2)與(w2-2).當(dāng)輸入數(shù)據(jù)序列循環(huán)左移S-bit時(shí)，特殊對(duì)依次向后傳遞.相應(yīng)地需要將初始路由控制序列循環(huán)移S位，同時(shí)保證每1次移位后末位路由控制信息取反，那么其輸出數(shù)據(jù)的結(jié)果相當(dāng)于初始輸出數(shù)據(jù)分別以左、右2個(gè)部分各自循環(huán)左移S位的結(jié)果.當(dāng)特殊對(duì)初始路由狀態(tài)為“1”時(shí)，與“0”情況相似，將其數(shù)值取反即可.

證畢.

性質(zhì)2. 若N-bit數(shù)據(jù)M={aN-1,aN-2,…,a0}1次通過(guò)Butterfly網(wǎng)絡(luò)實(shí)現(xiàn)了初始置換P：M→F，其中F={a0,aN-1,…,aN-2}，記

那么通過(guò)調(diào)整該網(wǎng)絡(luò)的初始路由控制信息，它還能夠?qū)崿F(xiàn)置換P′:M′→F，其中M′是數(shù)據(jù)序列M循環(huán)左移位S-bit(0≤S≤N)的結(jié)果.

證明. 根據(jù)性質(zhì)1可知，若將圖5(a)中N-bit初始輸入數(shù)據(jù)(initial inputs)循環(huán)左移S位，那么通過(guò)調(diào)整網(wǎng)絡(luò)第1級(jí)的初始路由信息，其初始輸出數(shù)據(jù)能夠分別以左、右2個(gè)部分(位寬為N2-bit)完成S-bit循環(huán)左移位，如圖5(b)中第1級(jí)輸出數(shù)據(jù)所示.Butterfly網(wǎng)絡(luò)是一種迭代遞歸網(wǎng)絡(luò)，若分別將初始置換網(wǎng)絡(luò)第2級(jí)的2個(gè)以N2-bit為位寬的子蝶網(wǎng)絡(luò)初始輸入數(shù)據(jù)(相當(dāng)于第1級(jí)的輸出數(shù)據(jù))循環(huán)左移S位.根據(jù)性質(zhì)1可知，其相應(yīng)的初始輸出數(shù)據(jù)則能夠以左、右2個(gè)部分(位寬為N4-bit)分別完成S-bit循環(huán)左移，如圖5(b)中第2級(jí)所示.依此類推，直到Butterfly網(wǎng)絡(luò)最后1級(jí)(第lgN級(jí))，該級(jí)共有N2個(gè)子蝶網(wǎng)絡(luò)(位寬為2-bit).當(dāng)初始輸入數(shù)據(jù)循環(huán)移位S-bit時(shí)，根據(jù)性質(zhì)1可知，其輸出數(shù)據(jù)將以1-bit為位寬進(jìn)行循環(huán)左移S位，這恒等于初始輸出數(shù)據(jù)，如圖5(b)中最后1級(jí)輸出所示.因此一個(gè)能夠基于Butterfly網(wǎng)絡(luò)實(shí)現(xiàn)初始置換P(M→F)的M序列，其循環(huán)移位S后所得的序列M′能夠?qū)崿F(xiàn)置換P′:M′→F.

證畢.

Fig. 5 Implementation principles of permutation-rotation operations圖5 置換-移位實(shí)現(xiàn)原理

1) 循環(huán)移位原理

Inverse Butterfly網(wǎng)絡(luò)是Butterfly網(wǎng)絡(luò)的逆結(jié)構(gòu)，若數(shù)據(jù)序列(input data)從圖5(b)中Butterfly網(wǎng)絡(luò)最后1級(jí)向第1級(jí)流動(dòng)，則可得出：

推論1. 若N-bit數(shù)據(jù)M={aN-1,aN-2,…,a0}1次通過(guò)Inverse Butterfly網(wǎng)絡(luò)實(shí)現(xiàn)置換P：M→F，其中F={a0,aN-1,…,aN-2}，記

那么通過(guò)調(diào)整初始路由信息該網(wǎng)絡(luò)還能夠?qū)崿F(xiàn)置換結(jié)果的移位操作記P′:M→F′，其中F′是數(shù)據(jù)序列F循環(huán)移位S-bit(0≤S≤N)的結(jié)果.

特別地，當(dāng)初始置換P為恒等置換時(shí)(各級(jí)初始控制信息全為0)，則初始輸入數(shù)據(jù)與初始輸出數(shù)據(jù)相等(M=F).且根據(jù)推論1可知，通過(guò)調(diào)整網(wǎng)絡(luò)初始路由控制信息，它還能夠?qū)崿F(xiàn)從M到M′的移位置換，其中M′是M循環(huán)移位S的結(jié)果.因此，Inverse Butterfly網(wǎng)絡(luò)能夠支持循環(huán)移位操作.

2) 比特抽取原理

比特抽取操作是根據(jù)序列R3中“1”的位置，完成對(duì)序列R2中比特?cái)?shù)據(jù)的并行抽取操作，本文將分析基于Inverse Butterfly網(wǎng)絡(luò)實(shí)現(xiàn)比特抽取操作的原理，并提取出與循環(huán)移位操作在該網(wǎng)絡(luò)實(shí)現(xiàn)時(shí)的共性環(huán)節(jié)，為統(tǒng)一路由算法的設(shè)計(jì)提供理論依據(jù).

推論2.N-bit數(shù)據(jù)的并行比特抽取操作能夠1次通過(guò)Inverse Butterfly網(wǎng)絡(luò)實(shí)現(xiàn).

證明. 本文以Inverse Butterfly網(wǎng)絡(luò)的拓?fù)涞Y(jié)構(gòu)作為研究基礎(chǔ)，采用數(shù)學(xué)歸納法對(duì)推論2進(jìn)行證明.

設(shè)i為N-bit Inverse Butterfly 網(wǎng)絡(luò)的級(jí)數(shù)(1≤i≤n，n=lgN).

① 當(dāng)i=1時(shí)，N-bit(N=8)數(shù)據(jù)被分成獨(dú)立的N2個(gè)以1-bit為間隔的數(shù)據(jù)對(duì)，如圖6所示.相鄰的2-bit數(shù)據(jù)對(duì)(A，B)進(jìn)行比特抽取操作時(shí)共有4種情況:圖6(a)表明2-bit數(shù)據(jù)A，B都需要被抽取，對(duì)應(yīng)的控制序列R3為“11”；圖6(b) 表明2-bit數(shù)據(jù)A，B僅高位數(shù)據(jù)需要被抽取，對(duì)應(yīng)的控制序列R3為“10”；圖6(c)表明2-bit數(shù)據(jù)A，B僅低位需要被抽取，對(duì)應(yīng)的控制序列R3為“01”；圖6(d)表明2-bit數(shù)據(jù)A，B都不需要被抽取，對(duì)應(yīng)的控制序列R3為“00”.從圖6各交叉開關(guān)中控制信息Sel可以看出，通過(guò)合理配置各開關(guān)的狀態(tài)，該級(jí)網(wǎng)絡(luò)即可完成比特抽取操作.因此，當(dāng)i=1時(shí)，N-bit Inverse Butterfly網(wǎng)絡(luò)的第1級(jí)能夠并行地完成N2個(gè)比特抽取操作；

Fig. 6 PEX operations map to stage 1圖6 PEX指令在網(wǎng)絡(luò)第1級(jí)的映射情況

② 假設(shè)當(dāng)i=lgN-1時(shí)，2個(gè)以N/2-bit為位寬的前l(fā)gN-1級(jí)子蝶網(wǎng)絡(luò)已經(jīng)完成了比特抽取操作;

③ 那么，需要證明當(dāng)i=lgN時(shí)，該網(wǎng)絡(luò)能夠完成以N-bit為位寬的比特抽取操作即可.

根據(jù)假設(shè)②，將圖7中左邊lgN-1級(jí)子蝶網(wǎng)絡(luò)最終輸出的抽取序列用X代替.同時(shí)，將右邊lgN-1級(jí)子蝶網(wǎng)絡(luò)輸出的抽取序列用Y代替.為了在網(wǎng)絡(luò)最后1級(jí)完成2個(gè)在第lgN-1級(jí)中被抽取序列X，Y的合并，并將合并后的序列置于輸出序列的末位.那么該網(wǎng)絡(luò)必須能夠同時(shí)完成2種操作：i)對(duì)左邊子蝶網(wǎng)絡(luò)的輸出序列X，進(jìn)行循環(huán)左移Y位的調(diào)整操作.這樣調(diào)整后左邊子蝶網(wǎng)絡(luò)的數(shù)據(jù)塊X，才能與右邊子蝶網(wǎng)絡(luò)被抽取的數(shù)據(jù)塊Y不處在同一個(gè)分組內(nèi)即不會(huì)出現(xiàn)路由控制信息沖突.因?yàn)樵谠摼W(wǎng)絡(luò)第lgN級(jí)，數(shù)據(jù)將以N/2-bit為間距構(gòu)成數(shù)據(jù)對(duì).ii)當(dāng)左邊子蝶網(wǎng)絡(luò)完成循環(huán)移位調(diào)整后，需要與右邊子蝶網(wǎng)絡(luò)中的無(wú)關(guān)數(shù)據(jù)塊I(位寬與X相等，且與Y相鄰)進(jìn)行交叉換位操作，以完成整個(gè)N-bit抽取操作.

下面，對(duì)這2種操作在Inverse Butterfly網(wǎng)絡(luò)實(shí)現(xiàn)的可行性進(jìn)行詳細(xì)分析：第1個(gè)操作中的移位位數(shù)Y可以根據(jù)右邊子蝶網(wǎng)絡(luò)中控制序列R3中“1”的個(gè)數(shù)確定.同時(shí)根據(jù)推論1可知，Inverse Butterfly網(wǎng)絡(luò)中對(duì)結(jié)果序列的循環(huán)移位操作，能夠通過(guò)調(diào)整各級(jí)初始控制信息實(shí)現(xiàn).也就是說(shuō)只要適當(dāng)調(diào)整左邊子蝶網(wǎng)絡(luò)(共lgN-1級(jí))的初始控制信息，那么第1個(gè)操作就能夠?qū)崿F(xiàn)，如圖7中第1步所示；第2個(gè)操作完成的是對(duì)第1個(gè)操作結(jié)果序列中的數(shù)據(jù)塊X與右邊子蝶網(wǎng)絡(luò)中無(wú)關(guān)數(shù)據(jù)塊I的交叉換位操作.該過(guò)程僅需要將第lgN級(jí)初始控制信息的最后Y部分置“0”，其余保持不變(假設(shè)默認(rèn)初始控制信息為“1”)即可完成，如圖7中第2步所示.因此，這2個(gè)操作能夠1次通過(guò)N-bit Inverse Butterfly網(wǎng)絡(luò)實(shí)現(xiàn).那么假設(shè)③成立.

Fig. 7 Implementation principles of N-bit PEX operation based on two N2-bit sub-networks圖7 N2-N2子蝶網(wǎng)絡(luò)完成N-bit抽取操作原理

證畢.

2.2 共性原理提取與統(tǒng)一路由算法設(shè)計(jì)

循環(huán)移位操作是推論1的一種特例，當(dāng)N-bit Inverse Butterfly網(wǎng)絡(luò)完成恒等置換時(shí)，輸入序列與輸出序列相等且各級(jí)初始控制信息全為“0”.該網(wǎng)絡(luò)若要完成循環(huán)移位S的操作，就需要將各級(jí)子蝶網(wǎng)絡(luò)中的初始控制信息2i-1-bit “0”進(jìn)行循環(huán)左移后末尾取反S次，其中i為級(jí)數(shù)，S為循環(huán)移位位數(shù).當(dāng)該網(wǎng)絡(luò)完成比特抽取操作時(shí)，則首先需要計(jì)算右邊子蝶網(wǎng)絡(luò)中控制序列R2中“1”的個(gè)數(shù)，記為Y.然后左邊子蝶網(wǎng)絡(luò)(共lgN-1級(jí))對(duì)應(yīng)的各級(jí)控制信息，按照各級(jí)子蝶網(wǎng)絡(luò)對(duì)應(yīng)的位寬(為2i-1-bit)進(jìn)行循環(huán)左移后末尾取反Y次，以完成該級(jí)輸出序列循環(huán)左移Y-bit的調(diào)整操作(圖7中的Step1).同時(shí)，最后1級(jí)網(wǎng)絡(luò)(第lgN級(jí))假設(shè)初始控制信息為“1”，也需要進(jìn)行循環(huán)左移后末位取反Y次，以完成與無(wú)關(guān)數(shù)據(jù)塊I(左相鄰于Y)的交叉換位操作(圖7中的Step2)，進(jìn)而完成比特抽取操作.因此，無(wú)論是循環(huán)移位操作還是比特抽取操作都用到了性質(zhì)1中的循環(huán)移位后末位取反操作.基于此，本文提出了針對(duì)循環(huán)移位和比特抽取2種不同操作的統(tǒng)一路由算法：

算法1. 循環(huán)移位與比特抽取操作統(tǒng)一路由算法.

輸入：C_pex，S_rot；

輸出：Control_bits. /*路由控制信息共有N×N/2-bit*/

① forl=1,2,…,N-2

②Sum_pc[l]=Popcnt(C_pex[l:0]);

/*統(tǒng)計(jì)C_pex中各比特位到0位的1的個(gè)數(shù)*/

③ end for

④ for (i=1,i≤lgN,i++)*/i表示級(jí)數(shù)*/

Fig. 8 Examples of the PEX and rotation operations圖8 比特抽取與循環(huán)移位操作示例

⑤k=2i-1； /*第i級(jí)子蝶網(wǎng)絡(luò)位寬*/

⑥ for (j=1,j≤N/2i-1-1,j=j+2)

⑦q=j×k-1；

⑧Control_bits(i)=RLTR(1k,Sum_pc[q]+S_rot)；

⑨ end for

⑩ end for

以8-bit Inverse Butterfly網(wǎng)絡(luò)為例，對(duì)算法1進(jìn)行詳細(xì)分析：

當(dāng)該網(wǎng)絡(luò)完成比特抽取操作時(shí)，S_rot必須為固定值0，設(shè)C_pex=1001_1011.根據(jù)算法1有：

若i=1時(shí)，k=1，j=1，3，5，7.因此q=0，2，4，6.且由于S_rot恒為0，第1級(jí)從右到左各子蝶網(wǎng)絡(luò)控制信息分別為：

Control_bit(1)=RLTR(11,Sum_pc[0]+0)=RLTR(1,1)=0； /*C_pex[0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[2]+0)=RLTR(1,2)=1； /*C_pex[2:0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[4]+0)=RLTR(1,4)=1； /*C_pex[4:0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[6]+0)=RLTR(1,2)=1. /*C_pex[6:0]中1的個(gè)數(shù)*/

若i=2時(shí)，k=2，j=1，3.因此q=1，5.且由于S_rot恒為0，第2級(jí)從右到左各子蝶網(wǎng)絡(luò)控制信息分別為：

Control_bit(2)=RLTR(12,Sum_pc[1]+0)=RLTR(11,2)=00； /*C_pex[1:0]中1的個(gè)數(shù)*/

Control_bit(2)=RLTR(12,Sum_pc[5]+0)=RLTR(11,4)=11. /*C_pex[4:0]中1的個(gè)數(shù)*/

若i=3時(shí)，k=4，j=1.因此q=3.且由于S_rot恒為0，第3級(jí)控制信息為：

Control_bit(3)=RLTR(14,Sum_pc[3]+0)=RLTR(1111,3)=1000. /*C_pex[3:0]中1的個(gè)數(shù)*/

比特抽取操作路由信息在網(wǎng)絡(luò)各級(jí)的適配情況，如圖8(a)所示.圖8(a)中第1級(jí)有4個(gè)子蝶網(wǎng)絡(luò)控制信息從左到右依次為“1”“1”“1”“0”；第2級(jí)有2個(gè)子蝶網(wǎng)絡(luò)，控制信息從左到右依次為“11”“00”；第3級(jí)僅有1個(gè)子蝶網(wǎng)絡(luò)，控制信息為“1000”.

當(dāng)該網(wǎng)絡(luò)完成循環(huán)移位操作時(shí)，C_pex必須為恒定值全1，設(shè)S_rot=5.根據(jù)算法1有：

若i=1時(shí)，k=1，j=1，3，5，7.因此q=0，2，4，6.且由于S_rot恒為5，第1級(jí)從右到左各子蝶網(wǎng)絡(luò)控制信息分別為：

Control_bit(1)=RLTR(11,Sum_pc[0]+5)=RLTR(1,6)=1； /*C_pex[0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[2]+5)=RLTR(1,8)=1； /*C_pex[2:0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[4]+5)=RLTR(1,10)=1； /*C_pex[4:0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(11,Sum_pc[6]+5)=RLTR(1,12)=1. /*C_pex[6:0]中1的個(gè)數(shù)*/

若i=2時(shí)，k=2，j=1，3.因此q=1，5.且由于S_rot恒為5，第2級(jí)從右到左各子蝶網(wǎng)絡(luò)控制信息分別為：

Control_bit(1)=RLTR(12,Sum_pc[1]+5)=RLTR(11,7)=01； /*C_pex[1:0]中1的個(gè)數(shù)*/

Control_bit(1)=RLTR(12,Sum_pc[5]+5)=RLTR(11,11)=01. /*C_pex[4:0]中1的個(gè)數(shù)*/

Fig. 9 Architecture of the RPRU圖9 可重構(gòu)比特抽取-移位單元架構(gòu)

若i=3時(shí)，k=4，j=1.因此q=3.且由于S_rot恒為0，第3級(jí)控制信息分別為：

Control_bit(1)=RLTR(14,Sum_pc[3]+5)=RLTR(1111,9)=1110. /*C_pex[3:0]中1的個(gè)數(shù)*/

循環(huán)移位操作路由信息在網(wǎng)絡(luò)各級(jí)的適配情況，如圖8(b)所示.圖8(b)中第1級(jí)有4個(gè)子蝶網(wǎng)絡(luò)控制信息從左到右依次為“1”“1”“1”“1”；第2級(jí)有2個(gè)子蝶網(wǎng)絡(luò)，控制信息從左到右依次為“01”“01”；第3級(jí)僅有1個(gè)子蝶網(wǎng)絡(luò)，控制信息為“1110”.

根據(jù)上述分析可知，當(dāng)該網(wǎng)絡(luò)完成比特抽取操作時(shí)，僅需將循環(huán)移位的參數(shù)S_rot設(shè)置為0.當(dāng)該網(wǎng)絡(luò)完成循環(huán)移位操作時(shí)，僅需要將抽取控制序列C_pex設(shè)置成全1.同時(shí)需要指出的是，當(dāng)網(wǎng)絡(luò)執(zhí)行循環(huán)移位操作時(shí)，處于同一級(jí)子蝶網(wǎng)絡(luò)的路由控制信息是相等的.如圖8(b)中，當(dāng)循環(huán)左移5位時(shí)，網(wǎng)絡(luò)第1級(jí)4個(gè)子蝶網(wǎng)絡(luò)中控制信息均為“1”，第2級(jí)2個(gè)子蝶網(wǎng)絡(luò)中的控制信息均為“01”.這是因?yàn)楫?dāng)Inverse Butterfly網(wǎng)絡(luò)完成循環(huán)移位時(shí)，各級(jí)子蝶網(wǎng)絡(luò)初始路由控制信息均為“0”.且根據(jù)性質(zhì)2可知，各子蝶網(wǎng)絡(luò)的初始路由控制信息的變化方式均相同，因此其最終路由信息也完全相同.

3 統(tǒng)一硬件架構(gòu)設(shè)計(jì)

本節(jié)根據(jù)算法1，設(shè)計(jì)了一種基于Inverse Butterfly網(wǎng)絡(luò)的可重構(gòu)比特抽取-移位單元 (recon-figurable parallel bit extraction-rotation hardware unit, RPRU)，如圖9所示.其中左邊為N-bit Inverse Butterfly網(wǎng)絡(luò)電路，由lgN級(jí)組成，各級(jí)有N2個(gè)2輸入交叉開關(guān)，需要N2-bit路由控制信息.右邊為可重構(gòu)路由信息生成電路，它是整個(gè)架構(gòu)的核心，共由2個(gè)部分構(gòu)成：可重構(gòu)比特連加電路(reconfigurable bit prefix population count circuit, RBPPC)和RLTR函數(shù)電路.RBPPC的作用是計(jì)算出控制序列C_pex從0位開始到各個(gè)位置的“1”的個(gè)數(shù)并記為Sum_pc[l],0≤l≤N-2.而后將每一個(gè)計(jì)算值與循環(huán)移位位數(shù)S_rot相加，從而得到用于各級(jí)子蝶網(wǎng)絡(luò)進(jìn)行RLTR函數(shù)運(yùn)算的操作數(shù)M.由Inverse Butterfly網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可知，第1級(jí)有N2個(gè)獨(dú)立的子蝶網(wǎng)絡(luò)，需要N2個(gè)1-bit位寬的RLTR函數(shù)電路.第i級(jí)有N2i個(gè)獨(dú)立的子蝶網(wǎng)絡(luò)，需要N2i個(gè)2i-1-bit位寬的RLTR函數(shù)電路.

由算法1的①～⑩步可知，控制序列C_pex中除了最高位以外的每一位都需要計(jì)算從0位開始到該位截止的加和值Sum_pc[l].若采用串行加法器的方式按位逐級(jí)相加，那么當(dāng)C_pex序列較長(zhǎng)時(shí)如32-bit或者64-bit，該電路的延遲開銷將非常巨大.因此，本文通過(guò)借鑒先行進(jìn)位加法器的設(shè)計(jì)思想[19]，提出了一種基于“樹”的并行連加結(jié)構(gòu)，如圖10所示.圖10中設(shè)計(jì)了(N=32)-bit的高速并行連加電路，其中上層數(shù)字(30～0)代表的是C_pex序列中各個(gè)比特的位置，下層數(shù)字(5～1)代表的是該比特位置對(duì)應(yīng)的加和值將被應(yīng)用的網(wǎng)絡(luò)級(jí)數(shù)i，黑色實(shí)心圓點(diǎn)代表的是全加電路，S_rot代表的是移位位數(shù).例如，當(dāng)上層數(shù)字為15時(shí)，其在下層輸出值是C_pex序列從0位到第15位的和再加上S_rot的值，且該位的輸出值將被用于網(wǎng)絡(luò)第i=5級(jí)的RLTR函數(shù)運(yùn)算，如圖10中粗虛線所示.經(jīng)過(guò)樹形壓縮后的連加電路最長(zhǎng)僅有6級(jí)加法器的延遲，與原先30級(jí)串行加法延遲相比大幅下降.

算法1中RLTR函數(shù)操作，根據(jù)連加電路各個(gè)位的加和值M=Sum_pc[q]+S_rot，進(jìn)行固定輸入為“1”的序列循環(huán)左移后末尾取反M次操作.通過(guò)研究發(fā)現(xiàn)一個(gè)長(zhǎng)度為L(zhǎng)(L=2i)個(gè)“1”的初始序列進(jìn)行RLTR操作時(shí)，周期為2L且結(jié)果序列為1x‖0y或?yàn)?x‖0y，x+y=2i.這與將該序列后拼接長(zhǎng)度為L(zhǎng)的“0”序列，并進(jìn)行聯(lián)合循環(huán)移M位，取其高L位輸出的結(jié)果相同.因此本文首先將RLTR函數(shù)用對(duì)數(shù)移位器進(jìn)行實(shí)現(xiàn)，如圖11(a)所示.而后，由于其初始輸入為恒定值“1”，因此再對(duì)其進(jìn)行布爾邏輯優(yōu)化以精簡(jiǎn)冗余邏輯，其優(yōu)化后結(jié)構(gòu)如圖11(b)所示.與傳統(tǒng)結(jié)構(gòu)相比，經(jīng)過(guò)優(yōu)化后的電路面積大幅減少且速度有所提升.

4 功能與性能分析

本文將設(shè)計(jì)的RPRU位寬設(shè)定為(N=64)-bit，進(jìn)行了硬件代碼編寫，并使用NC-Verilog對(duì)其功能進(jìn)行了覆蓋性測(cè)試，部分仿真結(jié)果如圖12所示.

圖12中前2行信號(hào)BP_LoacalA_Datain和BP_LoacalB_Datain一起組成64-bit輸入數(shù)據(jù).第3行為移位位數(shù)S_rot用6-bitBP_Shift表示.第4行為比特抽取控制序列C_Pex用64-bitBP_Mode_ibfly_config表示.第5行為RPRU的輸出結(jié)果用64-bitBP_DataOut表示.第6行為64-bittb_out是基準(zhǔn)測(cè)試程序生成的正確結(jié)果，它基于C語(yǔ)言編寫用來(lái)模擬RPRU的功能.最后1行error是64-bit判別信號(hào)，它是tb_out與BP_DataOut的“異或”值，該值為“0”說(shuō)明仿真數(shù)據(jù)與基準(zhǔn)測(cè)試結(jié)果一致，RPRU功能正確.

從圖12(a)中可以發(fā)現(xiàn)，當(dāng)BP_Mode_ibfly_config為64-bit全“1”時(shí)，移位位數(shù)BP_Shift從0到63依次改變，覆蓋所有移位可能.此時(shí)，error值恒為“0”，表明RPRU的循環(huán)移位功能正確.

從圖12(b)中可以發(fā)現(xiàn)，當(dāng)移位位數(shù)BP_Shift為恒定值“0”時(shí)，BP_Mode_ibfly_config為64-bit隨機(jī)值.此時(shí)，電路完成比特抽取操作，從error為“0”可以判定RPRU的比特抽取操作功能正確.

在功能正確的基礎(chǔ)上，基于CMOS 90 nm工藝對(duì)RPRU進(jìn)行了邏輯綜合，綜合時(shí)采用flatten的優(yōu)化策略(T=125℃,V=0.9V,P=slow)并設(shè)置時(shí)序優(yōu)先，其結(jié)果如表1所示:

Table 1 Comparison of Area and Latency of the RPRU表1 抽取-移位單元面積和延遲對(duì)比

表1中第1行描述的是Hilewitz等人設(shè)計(jì)的64-bit動(dòng)態(tài)比特抽取單元，該單元在TSMC 90 nm工藝下進(jìn)行綜合，其面積為8 500 gate，延遲為1.74 ns[18].第2行和第3行分別描述的是Hilewitz等人設(shè)計(jì)的64-bit靜態(tài)比特抽取單元和64-bit靜態(tài)比特抽取+循環(huán)移位單元[12].其中第3行的靜態(tài)抽取+移位單元的設(shè)計(jì)思想是首先將文獻(xiàn)[12]中提出的基于Inverse Butterfly網(wǎng)絡(luò)的循環(huán)移位算法進(jìn)行硬件設(shè)計(jì)，并與提前配置好的各級(jí)比特抽取路由控制信息進(jìn)行選擇，來(lái)實(shí)現(xiàn)同一架構(gòu)下的不同操作.若用第3行靜態(tài)比特抽取+移位單元的面積減去第2行靜態(tài)比特抽取單元的面積，剩余部分面積=8 200-3 600=4 600 gate為循環(huán)移位路由算法硬件實(shí)現(xiàn)所消耗的面積.當(dāng)該部分面積與第1行動(dòng)態(tài)比特抽取單元相加后的面積=4 600+8 500=13 100 gate則應(yīng)為Hilewitz等人的動(dòng)態(tài)比特抽取+移位單元的總面積.該單元的延遲應(yīng)仍然與動(dòng)態(tài)比特抽取單元延遲一致為1.74 ns，這是因?yàn)檠h(huán)移位算法實(shí)現(xiàn)的復(fù)雜度遠(yuǎn)低于比特抽取算法.第4行和第5行是本文設(shè)計(jì)的動(dòng)態(tài)比特抽取單元和動(dòng)態(tài)比特抽取+移位單元(RPRU)的面積和延遲值，它們基于CMOS 90 nm工藝綜合，不同之處在于前者將算法1的S_rot設(shè)定為恒定值0，而后者將S_rot設(shè)定為任意輸入數(shù)據(jù).

經(jīng)過(guò)上述分析可知，Lee等人設(shè)計(jì)的動(dòng)態(tài)比特抽取+循環(huán)移位單元的面積為13 100 gate，延遲為1.74 ns.本文設(shè)計(jì)的RPRU面積為9 300 gate，為前者面積的70%；延遲為1.4 ns，為前者延遲的80%.從絕對(duì)數(shù)值上看，無(wú)論是面積還是延遲本文設(shè)計(jì)的RPRU均有所降低.但是，這并不能有效衡量出循環(huán)移位與比特抽取算法的融合程度.因此，為了更加客觀地進(jìn)行性能對(duì)比，本文提出了相對(duì)面積比(percent of relative area,PRA)這一參數(shù)：

PRA越高，說(shuō)明動(dòng)態(tài)比特抽取單元面積占總面積(動(dòng)態(tài)比特抽取+移位單元)的比重就越大，同時(shí)循環(huán)移位路由算法硬件電路面積占總比重就越小(1-PRA).若循環(huán)移位路由算法硬件電路面積占總比重就越小，則表明其與比特抽取算法融合度就越高，那么該單元的結(jié)構(gòu)也更優(yōu).本文將該參數(shù)應(yīng)用于2個(gè)不同設(shè)計(jì)后有：Hilewitz的PRA=8 500/13 100=76.33%，本文的PRA=8 900/9 300=95.70%.從PRA的結(jié)果來(lái)看，Hilewitz等人設(shè)計(jì)的單元循環(huán)移位算法電路面積占總面積的近1-76.33%=34%.而本文設(shè)計(jì)的單元循環(huán)移位算法電路僅占總面積的4%左右.因此本文提出的算法能夠有效地將循環(huán)移位和比特抽取2種不同操作高度統(tǒng)一在一個(gè)算法架構(gòu)下，使它們能夠最大限度地共享硬件資源，從而大幅提升硬件資源的復(fù)用率.

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

本文深入研究了循環(huán)移位和比特抽取2種位級(jí)操作在Inverse Butterfly網(wǎng)絡(luò)中的實(shí)現(xiàn)原理，并提取出原理中所需的共性邏輯運(yùn)算，進(jìn)而提出了一種基于該網(wǎng)絡(luò)的統(tǒng)一路由算法.該算法的提出首次在理論層面證明了這2種操作在硬件路由算法實(shí)現(xiàn)策略上統(tǒng)一的可行性，為硬件融合架構(gòu)的設(shè)計(jì)提供理論支撐.同時(shí)，實(shí)驗(yàn)結(jié)果證明，利用本文算法設(shè)計(jì)的RPRU與同類設(shè)計(jì)相比，能夠大幅提升硬件復(fù)用率，從而有效降低資源消耗.同時(shí)，需要指出的是，比特抽取操作已經(jīng)集成于Intel處理器指令集中，若利用本文提出的統(tǒng)一路由算法，僅需增加不到4%的資源消耗即可實(shí)現(xiàn)傳統(tǒng)循環(huán)移位操作，而無(wú)需再設(shè)計(jì)專門硬件單元.因此，我們希望未來(lái)能將該路由算法進(jìn)行全定制設(shè)計(jì)，并與Intel處理器中的比特抽取操作充分融合.

[1]Bansod G, Raval N, Pisharoty N. Implementation of a new lightweight encryption design for embedded security[J]. IEEE Trans on Information Forensics and Security, 2015, 10(1): 142-151

[2]Jolfaei A, Wu Xinwen, Muthukkumarasamy V. On the security of permutation-only image encryption schemes[J]. IEEE Trans on Information Forensics & Security, 2015, 11(2): 235-246

[3]Zhang Jiyu, Liu Xianhua, Tan Mingxing, et al. Automatic instruction-set extension for bitwise operation-intensive applications[J]. Acta Electronica Sinica, 2012, 40(2): 209-214 (in Chinese)(張吉豫, 劉先華, 譚明星, 等. 一種針對(duì)位操作密集應(yīng)用的擴(kuò)展指令自動(dòng)選擇方法[J]. 電子學(xué)報(bào), 2012, 40(2): 209-214)

[4]Schwartz S, Kent J, Smit A, et al. Human-mouse alignments with BLASTZ[J]. Genome Research, 2003, 13(1): 103-107

[5]Bansod G, Gupta A, Ghosh A, et al. Experimental analysis and implementation of bit level permutation instructions for embedded security[J]. Wseas Trans on Information Science & Applications, 2013, 10(9): 303-312

[6]Guo Jian, Peyrin T, Poschmann A, et al. The LED block cipher[C] //Proc of Int Conf on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2011: 326-341

[7] Sayilar G, Chiou D. Cryptoraptor: High throughput reconfigurable cryptographic processor[C] //Proc of IEEE Int Conf on Computer-Aided Design. Piscataway, NJ: IEEE, 2014: 155-161

[8]Neto C, Vestias P. Architectural tradeoffs in the design of barrel shifters for reconfigurable computing[C] //Proc of IEEE Conf on Programmable Logic. Piscataway, NJ: IEEE, 2008: 31-36

[9]Dimitrakopoulos G, Mavrokefalidis C, Galanopoulos K, et al. Sorter based permutation units for media-enhanced microprocessors[J]. IEEE Trans on Very Large Scale Integration Systems, 2007, 15(6): 711-715

[10]Cardarilli C, Nunzio D, Fazzolari R, et al. Butterfly and inverse butterfly nets integration on altera NIOS-II embedded processor[C] //Proc of the 44th Int Symp on Signals, Systems and Computers. Piscataway, NJ: IEEE, 2010: 1279-128

[11]Hilewitz Y, Lee B. Performing advanced bit manipulations efficiently in general-purpose processors[C] //Proc of IEEE Symp on Computer Arithmetic. Piscataway, NJ: IEEE, 2007: 251-260

[12]Hilewitz Y, Lee B. A new basis for shifters in general-purpose processors for existing and advanced bit manipulations[J]. IEEE Trans on Computers, 2009, 58(8): 1035-1048

[13]Intel Corporation. Intel?64 and IA-32 Architectures Software Developer’s Manual[S/OL]. 2013 (2015-12-03) [2017-02-10]. http://www.intel.com/content/www/us/en/architecture-and-technology/64- ia-32-architectures-software-developer-manual-325462.html

[14]Chang Zhongxiang, Hu Jinshan, Ma Chao. Research on shifter based on ibutterfly network[C] //Proc of the 17th National Conf on Computer Engineering and Technology. Berlin: Springer, 2013: 92-100

[15]Jahanshahi M, Bistouni F. A new approach to improve reliability of the multistage interconnection networks[J]. Computers & Electrical Engineering, 2014, 40(8): 348-374

[16]Lee B, Shi J, Yin L, et al. On permutation operations in cipher design[C] //Proc of Int Conf on Information Technology: Coding and Computing. Piscataway, NJ: IEEE, 2004: 569-577

[17]Dimitrakopoulos G, Mavrokefalidis C, Galanopoulos K, et al. Sorter based permutation units for media-enhanced microprocessors[J]. IEEE Trans on Very Large Scale Integration Systems, 2007, 15(6): 711-715

[18]Hilewitz Y, Lee B. Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors[J]. Journal of Signal Processing Systems, 2008, 53(1/2): 145-169

[19]Johri R, Akashe S, Sharma S. High performance 8 bit cascaded carry look ahead adder with precise power consumption[J]. International Journal of Communication Systems, 2015, 28(8): 1475-1483