基于并行算法的大數據階乘算法的時間效率優化分析

高鑫， 王世杰， 許舒翔

(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所具備的并行處理功能，對多核處理器的并行處理過程進行模擬分析，實現計算速率的大幅提升。在此基礎上，利用此算法開發得到了可以實現多種功能的階乘計算器上位機，顯著提升了時空效率，有效滿足了大數階乘運算的需求。