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

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

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

0 引言

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

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

1 并行計(jì)算機(jī)

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

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

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

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

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

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

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

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

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

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

2.1.1定義與定理

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

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

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

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

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

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

2.1.2算法具體過程

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

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

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

2.1.3并行原理

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

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

(1)

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

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

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

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

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

(2)

證畢。

2.2 算法實(shí)現(xiàn)

2.2.1組成與功能

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

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

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

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

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

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

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

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

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

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

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

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

(6)銷毀與回收模塊

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

(7)工作線程模塊

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

2.2.2線程同步信息

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

2.2.3線程同步技術(shù)

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

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

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

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

2.3 算法推廣

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

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

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

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

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

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

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

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

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

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

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

3 測(cè)試與分析

3.1 測(cè)試環(huán)境

本文采用的測(cè)試平臺(tái)是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)化選項(xiàng)為O3。

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

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

線性反饋移位寄存器的參數(shù)包括反饋函數(shù)和初始狀態(tài)，其中反饋函數(shù)的次數(shù)、反饋函數(shù)的非0項(xiàng)數(shù)和初始狀態(tài)都影響隨機(jī)數(shù)生成算法的速度。本文采用常見的168次反饋函數(shù)。初始狀態(tài)需為非全0向量，本文采用常見的(0,…,0,1)。為考查不同反饋函數(shù)項(xiàng)數(shù)對(duì)測(cè)試結(jié)果的影響，本文使用2套參數(shù)。第1套參數(shù)，取項(xiàng)數(shù)最少的x168+x17+x15+x2+1作為反饋函數(shù)。通過采樣定理(取采樣間隔為5，5為最小的互素?cái)?shù))和Barlekamp Massey算法得到另一個(gè)項(xiàng)數(shù)為39的本原多項(xiàng)式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次/組測(cè)試，新算法并行相對(duì)串行加速比如圖2所示，當(dāng)工作線程個(gè)數(shù)為1時(shí)，相對(duì)于傳統(tǒng)的串行算法，本文提出的新算法的加速比接近1；當(dāng)工作線程個(gè)數(shù)為2時(shí)，加速比接近2；當(dāng)工作線程個(gè)數(shù)為4或64時(shí)，加速比接近4。

圖2 新算法并行相對(duì)串行加速比圖

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

4 結(jié)論

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