基于并行算法的大数据阶乘算法的时间效率优化分析

高鑫， 王世杰， 许舒翔

(1.国家电网公司西北分部， 陕西 西安 710048；2.国电南瑞科技股份有限公司， 江苏 南京 211106)

0 引言

有学者最早在上世纪90年代定义了阶乘多项式并对其相关特性进行了分析[1-5]。之后又有文献进一步补充了阶乘的具体概念与运算特征。例如，有学者设计了一种可以对不同编号进行排列的阶乘数字处理系统，这在一定程度上促进了大数阶乘应用的发展。从实际应用层面分析，可以利用阶乘运算的方式将一些工业生产以及经济活动方面的内容通过不同形式进行组合优化。同时，在计算机处理系统中，近似处理泰勒多项式以及e自然对数的时候，也属于一种对整数n进行阶乘计算的过程[6-9]。另一方面，考虑到利用计算机来表达整数时受到天花板因素的限制，需要根据编译器来确定最大表示值，以64位编译器作为分析例子，可以获得的最大整数是264-1，因此只能将其用于表示20的阶乘。这就要求必须对整数类型进行新的设置，或引入更合适的算法，使计算机能够计算更大整数的阶乘[10]。

为了计算超过20的整数阶乘，可以引入动态数组与链表的方法，考虑到链表访问的速度通常慢于数组访问速度，同时还需要设置更大空间容量用于存储链表数据，这使得对较大的整数进行阶乘运算时，采用链表将无法满足运算速率与数据存储的要求[11-13]。

通过整数数组来创建一个数值尽量大的整数过程中，从理论层面考虑这受制于存储空间的限制，同时为了增强直观性，将数组内各元素都以十进制的形式进行表示[14]。该学者通过动态数组的方式完成大数阶乘的存储以及表达过程，并以不同位数来存储各数组所包含的元素。采用上述方法虽然可以对大数阶乘进行精确表达，但受到实际运算速率的明显限制，无法有效适应不同的问题规模，而如果设置过大静态存储空间则会引起存储资源发生浪费的情况；也可能遇到存储空间过小而出现在过大问题规模的情况下发生数据溢出的结果[15]。本文根据以上分析内容设计得到了一种基于并行算法的大数阶乘运算方法。该方法能够满足处于有限硬件资源的条件下，针对不同的问题规模，自主完成存储空间的优化分配过程；并且可以发挥FPGA并行处理的性能，对多核处理器进行模拟测试，实现计算速度的大幅提升。

1 算法

1.1 算法设计过程

本文算法的具体运行方式，如图1所示。

图1 基于FPGA的算法实现框架

在图1中列出了各项硬件测试的系统平台。该算法总共包含了以下3个运算阶段：第一阶段是预估问题的规模，得到阶乘n包含的位数Num，当n与Num增大后，将会获得更大规模的问题；之后再结合位数Num对数据存储空间实施优化处理；接着选择并行计算的模式计算出整数n的阶乘。以VHDL作为硬件描述语言，在FPGA平台上完成阶乘运算。具体包括了以下过程：在锁相环PLL上对全局时钟进行调节，同时管理所有Ala语句，达到并行计算的功能；利用在动态存储器(SDR)对各项计算参数进行保存；Fifo可以读取SDR中的计算结果，再将其显示于液晶屏上，加入Fifo之后可以更快读取计算结果。以下部分将会详细论述算法的不同组成部分。

1.2 存储空间优化

VHDL语言可以利用数组来表示十进制数，以a表示数组名，以M表示数组的规模，如式(1)。

a[M]=aM-1aM-2…a0

(1)

式中,ai与i∈(0，M-1)，各数组元素都是由w位十进制数组成;γ表示通过SDR方式进行数据存储的过程中跟数据对齐方法有关的一个参数，大部分情况下都取γ等于1。由于LCD只存在有限的硬件资源，在此假定问题规模取决于Nmax=20 000的上限值，n的取值范围介于0～20 000之间。在相同的w条件下，当问题规模增加后，计算时间也发生了快速增加,如图2所示。

图2 不同w下的计算时间

同时还应注意，处理同样规模的问题时，当w增大后所需的计算时间将会缩短。这主要是因为当w增大后将会提高数组内的各元素权重占比，可以更加高效装载数据并且不发生溢出的情况，同时还会引起数组内元素刷新频率的降低，由此获得更快的计算速率。但也需注意w无法实现持续增大的状态。并且数组内元素位数增加后，处理同等规模问题时，可以有效降低存储空间。因此，对于不同规模的问题可以自动调节存储空间，从而达到优化的效果。通过上述方式来确定存储空间与问题的规模,之后根据上述各项参数并通过并行计算的方式来求解得到n阶乘。

1.3 并行计算

VHDL通过并行语句的模式来构建Ala语句，各权重单元都实施阶乘运算，当权重单元发生溢出的情况时再迭代更新。所有子过程都可通过简化阶乘递推方式来实现，只有遇到溢出的情况时，对溢出值进行更新并将其存储到另一个空间中，并对现有存储空间实施求模，如图3所示。

图3 并行计算方法

2 结果分析

比较算法运行速度及计算结果的精度。通过VHDL时序以及计时器得到算法运行的总时间。对n=10 000条件下的所有算法运行效率进行了计算，如图4所示。

图4 不同复杂度下各算法的时间效率

可以明显发现，与现有阶乘算法相比，本文算法所需的用时最短。对不同复杂度情况的算法效率进行了统计，结果表明可以利用调整n值来获得不同的复杂度。图4给出了各复杂度条件下的算法效率。通过对比可知，在各复杂度下本文算法都相对于传统算法实现了效率的明显提升,如表1所示。

不同复杂度下各算法的精度位数,如图5所示。

图5 不同复杂度下各算法的精度位数

可以看出，迭代前期各算法几乎完全重合，表现出相似的计算精度。本文提出的算法精度位数达到2 500节点，表现出很低的计算误差。针对不同的应用领域进行处理时，采用大数阶乘来实现底层功能的过程中通常需要利用数组、堆或链表等多种存储方式，同时引起近似分析、傅里叶转变与并行分析的模式来共同实现；进行间接应用时，可以对大数阶乘实施求导与加权处理，这使其成为许多模型分析的重要方式，能够快速处理多种工程应用问题。

3 总结

本文设计得到了一种基于并行算法的大数阶乘运算方法，可以在有限的硬件资源条件下根据不同的问题规模为计算过程分配合适的存储空间，并且可以发挥FPGA所具备的并行处理功能，对多核处理器的并行处理过程进行模拟分析，实现计算速率的大幅提升。在此基础上，利用此算法开发得到了可以实现多种功能的阶乘计算器上位机，显著提升了时空效率，有效满足了大数阶乘运算的需求。