基于LFSR具有并行與串行結(jié)果一致的隨機數(shù)生成算法

王 超，張秋艷，張 姍，王 龍

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京 100083)

0 引言

隨機數(shù)廣泛應(yīng)用于概率統(tǒng)計、模擬仿真、信息安全和數(shù)字通信等諸多領(lǐng)域。當(dāng)需要產(chǎn)生海量的隨機數(shù)時，傳統(tǒng)串行的隨機數(shù)生成算法(隨機數(shù)發(fā)生器，Random Number Generator)時間過長，難以達到實際需求。

本文在基于線性反饋移位寄存器(Linear Feedback Shift Register，LFSR)產(chǎn)生偽隨機數(shù)的基礎(chǔ)上，利用采樣定理，提出了一種基于多核處理器的新算法。在新算法中，將串行產(chǎn)生方式改為并行產(chǎn)生方式，提高了產(chǎn)生偽隨機數(shù)的效率，并且新算法具有并行與串行結(jié)果一致的特性，即新算法保持了通用性。本文首先證明了新算法的可計算性、確定性和結(jié)果一致性，然后給出了軟件實現(xiàn)流程和硬件推廣分析，最后在Intel(R) Core(TM) 四核CPU i7-6700上進行偽隨機數(shù)生成實驗，相對于傳統(tǒng)的串行算法，加速比已經(jīng)接近4。

1 并行計算機

并行計算機[1]是相對于串行計算機而言的，所謂串行計算機(順序計算機)就是單個處理單元順序執(zhí)行計算機程序的計算機。典型的并行計算機有多核處理器、現(xiàn)場可編程門陣列(Field-Programmable Gate Array，F(xiàn)PGA)芯片和圖形處理器(Graphics Processor Unit，GPU)。

多核處理器，又稱為單芯片多處理器(Chip Multiprocessors，CMP)，其各個處理器并行執(zhí)行不同的任務(wù)，通過線程并行性來取代越來越復(fù)雜的指令集并行，以此提高處理器的性能。

FPGA芯片是一種擁有高密度數(shù)字電路、高處理性能和可編程使用的信號處理器件，其通過消耗內(nèi)部邏輯資源塊實現(xiàn)并行處理。

以CUDA(Computer Unified Device Architecture)平臺為代表的圖形處理器，具有相當(dāng)高的內(nèi)存帶寬以及大量的浮點計算單元，其通過使用大量線程來充分利用多計算核心，從而實現(xiàn)高性能。

對于并行計算機，盡管它能夠提高多任務(wù)系統(tǒng)的性能，但是它不能提升串行系統(tǒng)的性能。因此，如果現(xiàn)有串行算法設(shè)計思想不加以改變，將無法充分利用并行計算機的計算能力。

2 偽隨機數(shù)生成算法

隨機數(shù)包括物理隨機數(shù)(真隨機數(shù))和偽隨機數(shù)兩類，若不特別說明，本文所涉及的隨機數(shù)都是指偽隨機數(shù)。

隨機數(shù)[2]可按均勻性劃分為均勻隨機數(shù)和非均勻隨機數(shù)。均勻隨機數(shù)是產(chǎn)生非均勻隨機數(shù)的基礎(chǔ)，如正態(tài)分布、指數(shù)分布等隨機數(shù)都可以用均勻隨機數(shù)經(jīng)過變換得到。當(dāng)今流行的均勻隨機數(shù)序列有：反饋移位寄存器(m序列、M序列)、二次剩余序列、霍爾(Hall)序列、孿生素數(shù)序列、混沌映射序列、進位加法和借位減法序列[3-4]等。其中反饋移位寄存器包括線性遞歸序列和非線性遞歸序列兩類，由于非線性遞歸序列的周期特性和統(tǒng)計特性還沒有成熟結(jié)論，分析這類序列密碼的安全性比較困難，因而LFSR是序列密碼設(shè)計中常用的一種初始亂源。

通過將種子密鑰作為LFSR的初態(tài)，按照遞推關(guān)系，產(chǎn)生一個周期長、統(tǒng)計特性好的初始亂源，從而為進一步利用非線性函數(shù)、有記憶變換等設(shè)計手段，產(chǎn)生抗破譯能力強的隨機數(shù)序列提供“原料”。

2.1 新隨機數(shù)生成算法及并行原理

2.1.1定義與定理

為證明本文的新隨機數(shù)生成算法(簡稱新算法)具有可計算性和確定性，以及并行與串行結(jié)果的一致性[5]，下面先引入幾個定義和定理，然后通過具體的算法過程來證明。

定義2：如果二元域上的n級線性遞歸序列的周期是2n-1，則稱該序列是二元域上的一條n級m序列，并稱其對應(yīng)的反饋多項式是本原多項式。

定理1：二元域上的n級m序列的游程特性：在一個周期內(nèi)，不存在長度大于n-1的0游程。

定理2：n級m序列的2i采樣(i=0,1,…,n-1)都與序列平移等價。

定理3：n級線性反饋移位寄存器由n個連續(xù)項(初始狀態(tài))和反饋多項式完全確定。

定理4：n次本原多項式的狀態(tài)圖由1個長度為1的圈(由零狀態(tài)構(gòu)成)和1個長度為2n-1的圈組成。

2.1.2算法具體過程

設(shè)f(x)是二元域上的n次本原多項式，S0是m序列的初始狀態(tài)(非全0向量，通常取值為(0,…,0,1)),并行線程個數(shù)記為2r。

步驟1：由f(x)和S0，通過基于乘法電路設(shè)計的線性反饋移位寄存器，生成長度為n×2r的輸出序列，記為序列a。

步驟3：將2r個線性反饋移位寄存器輸出進行拼接得到最終輸出。

2.1.3并行原理

(1)證明新算法具有可計算性

①步驟2中2r個初始狀態(tài)與步驟1中序列a的前n×2r項相同，如公式(1)所示：

(1)

綜上可知步驟2具有可計算性，于是新算法具有可計算性。

(2)證明新算法具有確定性

定理3保證2r個線性反饋移位寄存器都完全唯一確定，因此步驟2具有確定性，于是證明新算法具有確定性。

(3)證明新算法具有并行與串行結(jié)果一致性

序列a可以通過序列a,La,L2a,…,L2r-1a的2r采樣拼接而成，如公式(2)所示。

(2)

證畢。

2.2 算法實現(xiàn)

2.2.1組成與功能

新算法由主控線程和工作線程兩部分組成，總體架構(gòu)如圖1所示。

圖1 新算法總體架構(gòu)圖

(1)初始化與預(yù)計算模塊

該模塊主要完成：①工作線程個數(shù)2r的設(shè)置；②以下變量的初始化：用于索引的全局鏈表及保護它的線程互斥量，待分配任務(wù)計數(shù)、已運行任務(wù)計數(shù)和啟動線程結(jié)束標(biāo)志及保護三個變量的工作線程互斥量、工作線程條件變量；③反饋多項式的設(shè)置，預(yù)生成長度為n×2r的輸出序列，作為工作線程的輸入?yún)?shù)。

(2)工作線程創(chuàng)建模塊

該模塊完成創(chuàng)建2r個工作線程，其參數(shù)為反饋移位寄存器的初始狀態(tài)和工作線程序號。

(3)任務(wù)啟動與同步模塊

該模塊觸發(fā)工作線程遷移出等待階段，當(dāng)工作線程完成任務(wù)時，判定是否當(dāng)前批次任務(wù)都完成，若未完成則繼續(xù)等待。

(4)啟動工作線程結(jié)束模塊

該模塊觸發(fā)工作線程遷移出等待階段，允許工作線程結(jié)束。

(5)等待工作線程結(jié)束模塊

該模塊等待所有工作線程結(jié)束。

(6)銷毀與回收模塊

該模塊銷毀互斥量和條件變量，回收運行過程中申請的堆內(nèi)存。

(7)工作線程模塊

該模塊由等待階段、領(lǐng)取任務(wù)同步、執(zhí)行任務(wù)階段、完成任務(wù)同步和結(jié)束本線程組成。

2.2.2線程同步信息

圖1中以黑色實心箭頭形式標(biāo)出主線程與工作線程之間的同步信息：主控線程中“任務(wù)啟動與同步模塊”觸發(fā)工作線程中“等待階段”；主控線程中“啟動工作線程結(jié)束模塊”觸發(fā)工作線程中“等待階段”；工作線程中“完成任務(wù)同步”觸發(fā)主控線程中“任務(wù)啟動與同步模塊”。圖1中以空心箭頭形式標(biāo)出工作線程之間的同步信息：工作線程中領(lǐng)取任務(wù)同步觸發(fā)其他工作線程的等待階段。

2.2.3線程同步技術(shù)

考慮到各工作線程處理任務(wù)的相似性，得出各工作線程處理任務(wù)消耗的時間接近，于是減化同步控制，僅使用線程互斥量THREAD_MUTEX和工作線程條件THREAD_COND控制所有工作線程同步。本算法在實現(xiàn)中使用了最低數(shù)量的線程共享變量(待分配任務(wù)計數(shù)、已運行任務(wù)計數(shù)和啟動線程結(jié)束標(biāo)志)。全局鏈表與線程共享變量不存在資源競爭，為提高各工作線程效率，沒有使用THREAD_MUTEX保護全局鏈表，而是增加互斥量gPPHEAD_MUTEX來保護全局鏈表。

任務(wù)啟動與同步模塊通過設(shè)置待“分配任務(wù)計數(shù)”，觸發(fā)各工作線程開始執(zhí)行任務(wù)，然后直到“已運行任務(wù)計數(shù)”達到要求，再繼續(xù)執(zhí)行。

當(dāng)完成任務(wù)啟動與同步后，此時工作線程可能仍處于執(zhí)行任務(wù)階段，主控線程通過設(shè)置“啟動線程結(jié)束標(biāo)志”告知各工作線程后續(xù)沒有新任務(wù)，可以結(jié)束本工作線程。

各工作線程通過判斷“分配任務(wù)計數(shù)”決定是等待還是執(zhí)行任務(wù)；領(lǐng)取任務(wù)后“待分配任務(wù)計數(shù)”減一，并通知其他工作線程的等待階斷；完成任務(wù)后“已運行任務(wù)計數(shù)”加一，并通知主控線程的任務(wù)啟動與同步模塊，主控線程判斷“已運行任務(wù)計數(shù)”達到要求，決定是否繼續(xù)等待。

2.3 算法推廣

為了實現(xiàn)隨機數(shù)生成算法的并行與串行結(jié)果一致，傳統(tǒng)串行算法的流程如下：

(1)隨機數(shù)生成算法由n個模塊組成；

(2)第i(i=1,…,n)個模塊模擬運行i輪LFSR；

(3)內(nèi)部狀態(tài)步進n輪，轉(zhuǎn)至上一過程。

本文提出的新算法，對應(yīng)的流程如下：

(1)隨機數(shù)生成算法由n=2r個模塊組成；

(2)第i(i=1,…,n)個模塊模擬運行1輪LFSR；

(3)內(nèi)部狀態(tài)步進1輪，轉(zhuǎn)至上一過程。

在FPGA[6]上的傳統(tǒng)串行算法，當(dāng)n較大時，其第n個模塊相較第1個模塊復(fù)雜很多，使得FPGA的時鐘頻率無法很高。而新算法中，所有n個模塊的復(fù)雜度一樣，使得FPGA的時鐘頻率可以相對更高。

接下來考查GPU[7-9]，例如GeForce8800GTX擁有128個執(zhí)行單元，為充分利用，需要多線程。同時，由于CUDA平臺中對全局內(nèi)存的存取有較大延遲，線程會因為無法及時讀取或?qū)懭霐?shù)據(jù)而處于等待狀態(tài)，需通過使用超量的線程來隱藏全局內(nèi)存延遲，從而需要一個較高的計算和存取比率[10]。于是，為充分利用GPU，需要數(shù)千個線程。傳統(tǒng)串行算法中所有n個模塊的算法邏輯不同，而新算法中所有n個模塊的算法邏輯是一樣的，僅初始值不同，并且初始值為少量輸入，GPU恰好適合新算法的加速實現(xiàn)。

綜上所述，本文提出的新算法思想不僅適用于多核處理器，也同樣適用于FPGA和GPU。

3 測試與分析

3.1 測試環(huán)境

本文采用的測試平臺是Intel(R) Core(TM) 四核CPU i7-6700，主頻3.40 GHz，內(nèi)存8 GB，搭載Windows 7(Service Pack 1)旗艦版操作系統(tǒng)和GCC 4.6編譯環(huán)境，編譯優(yōu)化選項為O3。

本文采用中g(shù)ettimeofday函數(shù)計算CPU的執(zhí)行時間，精度單位為微秒，實測時驗證為毫秒。gettimeofday函數(shù)相比中time函數(shù)(精度為秒)精度更細(xì)致。雖然中clock函數(shù)精度為毫秒，但是其計算的是CPU的各個核累計的運行節(jié)拍對應(yīng)轉(zhuǎn)換成的時間，并不是真實的運行時間。

為了降低對時間的測量誤差，本文采用2 000作為單個測試的倍數(shù)。通過計算平均值獲取平均情況，采用8次單個測試作為1個測試組。為了消除內(nèi)存使用量對算法性能的影響，運行1組測試后，立即進行堆內(nèi)存釋放，然后再進行下一組測試，累計進行4組測試。對于1套給定參數(shù)，總計產(chǎn)生32個運行時間和1個平均值。

線性反饋移位寄存器的參數(shù)包括反饋函數(shù)和初始狀態(tài)，其中反饋函數(shù)的次數(shù)、反饋函數(shù)的非0項數(shù)和初始狀態(tài)都影響隨機數(shù)生成算法的速度。本文采用常見的168次反饋函數(shù)。初始狀態(tài)需為非全0向量，本文采用常見的(0,…,0,1)。為考查不同反饋函數(shù)項數(shù)對測試結(jié)果的影響，本文使用2套參數(shù)。第1套參數(shù)，取項數(shù)最少的x168+x17+x15+x2+1作為反饋函數(shù)。通過采樣定理(取采樣間隔為5，5為最小的互素數(shù))和Barlekamp Massey算法得到另一個項數(shù)為39的本原多項式x168+x111+x110+x109+x98+x93+x82+x80+x71+x70+x69+x64+x63+x62+x58+x53+x51+x46+x43+x41+x40+x39+x36+x35+x34+x32+x30+x29+x28+x25+x24+x23+x22+x21+x18+x16+x15+x2+1作為第2套參數(shù)。

3.2 加速效果分析

經(jīng)過4組×8次/組測試，新算法并行相對串行加速比如圖2所示，當(dāng)工作線程個數(shù)為1時，相對于傳統(tǒng)的串行算法，本文提出的新算法的加速比接近1；當(dāng)工作線程個數(shù)為2時，加速比接近2；當(dāng)工作線程個數(shù)為4或64時，加速比接近4。

圖2 新算法并行相對串行加速比圖

綜上所述，本文提出的新算法的加速比最大值與測試平臺CPU的物理核心個數(shù)一致，即在Intel(R) Core(TM) CPU i7-6700上新算法的加速比最大為4，此結(jié)論與理論推導(dǎo)一致。同時，驗證新算法對反饋函數(shù)的非0項個數(shù)不敏感，于是新算法適用于各種線性反饋移位寄存器參數(shù)。

4 結(jié)論

本文主要設(shè)計和實現(xiàn)了一種基于LFSR的適用于多核處理器的新偽隨機數(shù)生成算法。新算法在并行運行時與經(jīng)典串行算法產(chǎn)生一致的隨機數(shù)，相對于傳統(tǒng)的串行算法，加速比可以達到多核處理器的物理核心數(shù)，同時保持了通用性。下一步研究工作是將此算法向GPU與FPGA推廣。