基于LFSR具有并行与串行结果一致的随机数生成算法

2018-10-22张秋艳

网络安全与数据管理 2018年10期

王超，张秋艳，张姗，王龙

(中国电子信息产业集团有限公司第六研究所，北京 100083)

0 引言

随机数广泛应用于概率统计、模拟仿真、信息安全和数字通信等诸多领域。当需要产生海量的随机数时，传统串行的随机数生成算法(随机数发生器，Random Number Generator)时间过长，难以达到实际需求。

本文在基于线性反馈移位寄存器(Linear Feedback Shift Register，LFSR)产生伪随机数的基础上，利用采样定理，提出了一种基于多核处理器的新算法。在新算法中，将串行产生方式改为并行产生方式，提高了产生伪随机数的效率，并且新算法具有并行与串行结果一致的特性，即新算法保持了通用性。本文首先证明了新算法的可计算性、确定性和结果一致性，然后给出了软件实现流程和硬件推广分析，最后在Intel(R) Core(TM) 四核CPU i7-6700上进行伪随机数生成实验，相对于传统的串行算法，加速比已经接近4。

1 并行计算机

并行计算机[1]是相对于串行计算机而言的，所谓串行计算机(顺序计算机)就是单个处理单元顺序执行计算机程序的计算机。典型的并行计算机有多核处理器、现场可编程门阵列(Field-Programmable Gate Array，FPGA)芯片和图形处理器(Graphics Processor Unit，GPU)。

多核处理器，又称为单芯片多处理器(Chip Multiprocessors，CMP)，其各个处理器并行执行不同的任务，通过线程并行性来取代越来越复杂的指令集并行，以此提高处理器的性能。

FPGA芯片是一种拥有高密度数字电路、高处理性能和可编程使用的信号处理器件，其通过消耗内部逻辑资源块实现并行处理。

以CUDA(Computer Unified Device Architecture)平台为代表的图形处理器，具有相当高的内存带宽以及大量的浮点计算单元，其通过使用大量线程来充分利用多计算核心，从而实现高性能。

对于并行计算机，尽管它能够提高多任务系统的性能，但是它不能提升串行系统的性能。因此，如果现有串行算法设计思想不加以改变，将无法充分利用并行计算机的计算能力。

2 伪随机数生成算法

随机数包括物理随机数(真随机数)和伪随机数两类，若不特别说明，本文所涉及的随机数都是指伪随机数。

随机数[2]可按均匀性划分为均匀随机数和非均匀随机数。均匀随机数是产生非均匀随机数的基础，如正态分布、指数分布等随机数都可以用均匀随机数经过变换得到。当今流行的均匀随机数序列有：反馈移位寄存器(m序列、M序列)、二次剩余序列、霍尔(Hall)序列、孪生素数序列、混沌映射序列、进位加法和借位减法序列[3-4]等。其中反馈移位寄存器包括线性递归序列和非线性递归序列两类，由于非线性递归序列的周期特性和统计特性还没有成熟结论，分析这类序列密码的安全性比较困难，因而LFSR是序列密码设计中常用的一种初始乱源。

通过将种子密钥作为LFSR的初态，按照递推关系，产生一个周期长、统计特性好的初始乱源，从而为进一步利用非线性函数、有记忆变换等设计手段，产生抗破译能力强的随机数序列提供“原料”。

2.1 新随机数生成算法及并行原理

2.1.1定义与定理

为证明本文的新随机数生成算法(简称新算法)具有可计算性和确定性，以及并行与串行结果的一致性[5]，下面先引入几个定义和定理，然后通过具体的算法过程来证明。

定义2：如果二元域上的n级线性递归序列的周期是2n-1，则称该序列是二元域上的一条n级m序列，并称其对应的反馈多项式是本原多项式。

定理1：二元域上的n级m序列的游程特性：在一个周期内，不存在长度大于n-1的0游程。

定理2：n级m序列的2i采样(i=0,1,…,n-1)都与序列平移等价。

定理3：n级线性反馈移位寄存器由n个连续项(初始状态)和反馈多项式完全确定。

定理4：n次本原多项式的状态图由1个长度为1的圈(由零状态构成)和1个长度为2n-1的圈组成。

2.1.2算法具体过程

设f(x)是二元域上的n次本原多项式，S0是m序列的初始状态(非全0向量，通常取值为(0,…,0,1)),并行线程个数记为2r。

步骤1：由f(x)和S0，通过基于乘法电路设计的线性反馈移位寄存器，生成长度为n×2r的输出序列，记为序列a。

步骤3：将2r个线性反馈移位寄存器输出进行拼接得到最终输出。

2.1.3并行原理

(1)证明新算法具有可计算性

①步骤2中2r个初始状态与步骤1中序列a的前n×2r项相同，如公式(1)所示：

(1)

综上可知步骤2具有可计算性，于是新算法具有可计算性。

(2)证明新算法具有确定性

定理3保证2r个线性反馈移位寄存器都完全唯一确定，因此步骤2具有确定性，于是证明新算法具有确定性。

(3)证明新算法具有并行与串行结果一致性

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

(2)

证毕。

2.2 算法实现

2.2.1组成与功能

新算法由主控线程和工作线程两部分组成，总体架构如图1所示。

图1 新算法总体架构图

(1)初始化与预计算模块

该模块主要完成：①工作线程个数2r的设置；②以下变量的初始化：用于索引的全局链表及保护它的线程互斥量，待分配任务计数、已运行任务计数和启动线程结束标志及保护三个变量的工作线程互斥量、工作线程条件变量；③反馈多项式的设置，预生成长度为n×2r的输出序列，作为工作线程的输入参数。

(2)工作线程创建模块

该模块完成创建2r个工作线程，其参数为反馈移位寄存器的初始状态和工作线程序号。

(3)任务启动与同步模块

该模块触发工作线程迁移出等待阶段，当工作线程完成任务时，判定是否当前批次任务都完成，若未完成则继续等待。

(4)启动工作线程结束模块

该模块触发工作线程迁移出等待阶段，允许工作线程结束。

(5)等待工作线程结束模块

该模块等待所有工作线程结束。

(6)销毁与回收模块

该模块销毁互斥量和条件变量，回收运行过程中申请的堆内存。

(7)工作线程模块

该模块由等待阶段、领取任务同步、执行任务阶段、完成任务同步和结束本线程组成。

2.2.2线程同步信息

图1中以黑色实心箭头形式标出主线程与工作线程之间的同步信息：主控线程中“任务启动与同步模块”触发工作线程中“等待阶段”；主控线程中“启动工作线程结束模块”触发工作线程中“等待阶段”；工作线程中“完成任务同步”触发主控线程中“任务启动与同步模块”。图1中以空心箭头形式标出工作线程之间的同步信息：工作线程中领取任务同步触发其他工作线程的等待阶段。

2.2.3线程同步技术

考虑到各工作线程处理任务的相似性，得出各工作线程处理任务消耗的时间接近，于是减化同步控制，仅使用线程互斥量THREAD_MUTEX和工作线程条件THREAD_COND控制所有工作线程同步。本算法在实现中使用了最低数量的线程共享变量(待分配任务计数、已运行任务计数和启动线程结束标志)。全局链表与线程共享变量不存在资源竞争，为提高各工作线程效率，没有使用THREAD_MUTEX保护全局链表，而是增加互斥量gPPHEAD_MUTEX来保护全局链表。

任务启动与同步模块通过设置待“分配任务计数”，触发各工作线程开始执行任务，然后直到“已运行任务计数”达到要求，再继续执行。

当完成任务启动与同步后，此时工作线程可能仍处于执行任务阶段，主控线程通过设置“启动线程结束标志”告知各工作线程后续没有新任务，可以结束本工作线程。

各工作线程通过判断“分配任务计数”决定是等待还是执行任务；领取任务后“待分配任务计数”减一，并通知其他工作线程的等待阶断；完成任务后“已运行任务计数”加一，并通知主控线程的任务启动与同步模块，主控线程判断“已运行任务计数”达到要求，决定是否继续等待。

2.3 算法推广

为了实现随机数生成算法的并行与串行结果一致，传统串行算法的流程如下：

(1)随机数生成算法由n个模块组成；

(2)第i(i=1,…,n)个模块模拟运行i轮LFSR；

(3)内部状态步进n轮，转至上一过程。

本文提出的新算法，对应的流程如下：

(1)随机数生成算法由n=2r个模块组成；

(2)第i(i=1,…,n)个模块模拟运行1轮LFSR；

(3)内部状态步进1轮，转至上一过程。

在FPGA[6]上的传统串行算法，当n较大时，其第n个模块相较第1个模块复杂很多，使得FPGA的时钟频率无法很高。而新算法中，所有n个模块的复杂度一样，使得FPGA的时钟频率可以相对更高。

接下来考查GPU[7-9]，例如GeForce8800GTX拥有128个执行单元，为充分利用，需要多线程。同时，由于CUDA平台中对全局内存的存取有较大延迟，线程会因为无法及时读取或写入数据而处于等待状态，需通过使用超量的线程来隐藏全局内存延迟，从而需要一个较高的计算和存取比率[10]。于是，为充分利用GPU，需要数千个线程。传统串行算法中所有n个模块的算法逻辑不同，而新算法中所有n个模块的算法逻辑是一样的，仅初始值不同，并且初始值为少量输入，GPU恰好适合新算法的加速实现。

综上所述，本文提出的新算法思想不仅适用于多核处理器，也同样适用于FPGA和GPU。

3 测试与分析

3.1 测试环境

本文采用的测试平台是Intel(R) Core(TM) 四核CPU i7-6700，主频3.40 GHz，内存8 GB，搭载Windows 7(Service Pack 1)旗舰版操作系统和GCC 4.6编译环境，编译优化选项为O3。

本文采用中gettimeofday函数计算CPU的执行时间，精度单位为微秒，实测时验证为毫秒。gettimeofday函数相比中time函数(精度为秒)精度更细致。虽然中clock函数精度为毫秒，但是其计算的是CPU的各个核累计的运行节拍对应转换成的时间，并不是真实的运行时间。

为了降低对时间的测量误差，本文采用2 000作为单个测试的倍数。通过计算平均值获取平均情况，采用8次单个测试作为1个测试组。为了消除内存使用量对算法性能的影响，运行1组测试后，立即进行堆内存释放，然后再进行下一组测试，累计进行4组测试。对于1套给定参数，总计产生32个运行时间和1个平均值。

线性反馈移位寄存器的参数包括反馈函数和初始状态，其中反馈函数的次数、反馈函数的非0项数和初始状态都影响随机数生成算法的速度。本文采用常见的168次反馈函数。初始状态需为非全0向量，本文采用常见的(0,…,0,1)。为考查不同反馈函数项数对测试结果的影响，本文使用2套参数。第1套参数，取项数最少的x168+x17+x15+x2+1作为反馈函数。通过采样定理(取采样间隔为5，5为最小的互素数)和Barlekamp Massey算法得到另一个项数为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套参数。