在科學計算領域，經常會涉及到大規模大復雜度的計算，比如氣象計算，物理粒子模擬等。石油勘探采用的PSDM算法，作為科學計算的一種，其運行過程也是復雜度高，計算量大。不同于其他領域的科學計算，比如物理粒子模擬，有著很高的數據并行度，PSDM算法的并行性不強，數據相關性太大，迭代次數過多，IO吞吐較為分散。以上特點注定了PSDM算法使用集群的實現方式并不能很好得實現加速，反而會造成各個主機間為了協同數據造成的通信帶寬過大的局面。

正是由于以上的特性，使得在通用處理器上，很難尋求到算法加速的突破點，因為通用處理器的訪存-計算-訪存模型會使得處理器在處理IO和數學運算之間來回切換，很難行成流水。所以我們自然得想到能否自己定制一種專用的處理器，專門針對此算法的運算特性，有的放矢得構建出合適的系統構架。

定制專用的處理器，傳統的方式是使用專用集成電路的方法，雖然專用集成電路的方法有著速度快，功耗低等優點，但其成本高，結構不夠靈活^[2]。隨著VLSI的發展，FPGA向高速度，高集成度的方向發展，價格也越來越低，同時又具有開發時間較短，內部結構修改靈活的特點。這就為在FPGA上實現PSDM算法奠定了基礎。

目前國內外對PSDM算法的硬件實現有過一些研究，但是大部分只是針對算法中的一小部分（比如帶權疊加或者計算旅行時表）。即使有一些是大范圍的移植，也沒有給出訪存模型的設計以及實現，只是停留在理想階段。最重要的是，PSDM算法中有很多的N次方運算，現存的研究都是把這部分留在主機來進行，這就造成了效率低下，吞吐量和計算量的比例增大等諸多因素，不適宜加速。另一方面，目前在FPGA中還沒有任何關于計算N次方的方法，僅存的一些都是只在精度要求有限（可以采用查表的方法），或者冪指數是常量的計算的情況（只能實現固定冪指數的運算）。

本論文將給出在FPGA中實現N次方運算的設計，并將其設計集成到PSDM算法的移植當中，預計實現整個算法的全方位移植。整個論文結構如下：首先，給出了浮點數計算的弊端，并尋找了一種轉向整數計算的捷徑，使得浮點數計算的次數盡可能的少但是還不改變計算效果；其次，分析了整數N次方運算的數學模型，找到了一種高效的算法，給出了軟件實現的偽代碼；下一步，論文針對N次方算法給出了電路的設計，考慮了并行等因素；最后，給出了結果仿真以及本論文的研究結論。

1 將問題轉換成整數的運算

32位計算機中整數的表示是一個連續的位，這種格式的存儲很自然得加快了運算速度，只要每一個位依次運算然后進位就可以了，無論是加減法還是乘除法基本都可以做到一個時鐘周期就可以計算完畢。

浮點數則有所不同，他有著自己的固定格式，不能直觀得進行位運算，所以運算速度自然慢了很多，資源消耗也相對偏大。最理想的方式是把浮點數的N次方轉換成整數的N次方運算，然后把浮點計算的部分盡量降到最低。

1.1 浮點數N次方到整數N次方的轉換

浮點運算在硬件芯片中實現起來，有如下弊端：

1）資源消耗相對整數運算偏大，速度偏慢；

2）浮點數不容易實現過程控制，比如循環控制；

3）浮點數的位移運算沒有意義，浪費了硬件的天生優勢。

綜上所述，我們考慮把浮點數的N次方運算轉換成整數的運算。

任何一個浮點數，都可以表示成一個分數的形式，比如1.3可以表示成13/10；0.375可以表示成3/8等。不妨設：M是浮點數，A,B,N均為整數：

（1）

所以任何一個浮點數的N次方運算，都可以轉換成2次整數的N次方運算，1次除法運算�？梢钥闯�，整數的N次方運算是整個運算的關鍵。

1.2 數據的表示以及溢出考慮

眾所周知：一個32位寬的信號如果表示整數，上限是2³²-1。也就是說A,B如果大于等于2，N如

果大于32，則肯定會發生溢出，反之，也并不能保證不會發生溢出。針對以上情況，我們自然想到依舊采用浮點數格式表示整數。

IEEE 754 標準規定了三種浮點數格式：單精度、雙精度、擴展精度^[4]，我們采用單精度表示：按位域可劃分為：符號位、階碼位與尾數位，如下：

表1 單精度浮點數格式

符號位取 0 表示正數，取 1 表示負數。階碼位是 8 位，這里有一點需要注意，那就是的指數e并不能直接當作階碼來處理，需要將其與127相加才能得到真正的階碼。尾數的位域長度在圖示中是 23 位，但實際上卻是 24 位，這個位是“不可見”的，其值固定為 1，這也就是說 IEEE 754 標準所定義的浮點數，其有效數字是介于 1 與 2 之間的小數。

2 M^N算法模塊設計

2.1 算法的軟件描述及優化

經典的N次方運算，運算流程如下：將結果值初始化為M值，然后令循環控制變量從一至N，每次迭代過程中將結果值與M值進行相乘運算，最后得到的結果即是最終結果。此算法的時間復雜度為O(N)，空間復雜度為O(1)。

然而，仔細考慮N次方運算的數學模型不難得到：

（2）

用二進制的方法表示N：

（3）

如果能得到的值，就可以經過次乘法得到。這顯然可以通過遞推得到：

（4）

舉例說明：

（5）

綜上所述，M的N次方運算的流程如下：

1）初始化結果值為1，臨時變量tmp 為m；

2）如果n為0，則退出，否則繼續；

3）如果n的最低位是1，結果值(reault)更新為結果值乘以臨時變量(tmp)；

4）臨時變量(tmp)更新為自己的平方；

5）重復第二步。

如此推導，算法的時間復雜度可以減小到，這對于N迅速增大的情況（比如64位位寬），性能改善10倍。

2.2 算法的硬件實現

2.2.1 采用的FPGA平臺

目前，可重構部件種類繁多，而FPGA（Field Programmable Gate Array）相對其他器件，則被更廣使用。Xilinx公司是目前主要的FPGA生產商之一，有兩大類FPGA產品：Spartan類和Virtex類，前者主要面向低成本的中低端應用，是目前業界成本最低的一類FPGA；后者主要面向高端應用，屬于業界的頂級產品。這兩個系列的差異僅限于芯片的規模和專用模塊上，都采用了先進的0.13 、90 甚至65 制造工藝。

PSDM算法的特點是運算密集型，所以需要大量的運算資源（DSP48E）。Virtex-5系列是Xilinx最新一代的FPGA產品，計劃提供了4種新型平臺，每種平臺都在高性能邏輯、串行連接功能、信號處理和嵌入式處理性能方面實現了最佳平衡�，F有的3款平臺為LX、LXT以及SXT。LX針對高性能邏輯進行了優化，LXT針對具有低功耗串行連接功能的高性能邏輯進行了優化，SXT針對具有低功耗串行連接功能的 DSP 和存儲器密集型應用進行了優化�？紤]到工程的需要最終選擇SXT系列。

2.2.2 IP-CORE以及開發工具

整個算法涉及到乘法運算，移位運算等，xilinx公司提供了浮點運算核，可以配置成多種工作模式，比如加減法、乘除法。我們使用其中的乘法模式，加入自己的條件控制，封裝成我們自己的乘法器：條件乘法器（參見圖二）。

開發工具的選擇上，xilinx本身自帶的ISE由于綜合速度過慢^[6]，且優化功能偏少，所以我們只用它做布局布線，在代碼的綜合上，采用Synplify作為綜合器，代碼的仿真采用ModelSim作為仿真器，形成了工具鏈的使用。

2.2.3 整形運算芯片設計

硬件與軟件的最大區別在于硬件功能的單一性與專業性，相比與軟件的靈活性，多樣性而言，硬件實現某些功能需要更復雜的設計，得到高性能的同時，喪失了靈活性。還有一個最大的區別在于硬件是并行處理的，不同于軟件的逐句執行�？紤]到之前的運算流程，設計出如下陣列：

圖1 計算陣列框架圖

初始化時，平方器的輸入為M，條件乘法器的輸入為1，M。而條件乘法器的條件輸入則始終是N的最低位。每一次時鐘上沿，將并行發生如下運算：1）平方器計算輸出，并把輸出重新賦值給輸入；2）條件乘法器的條件輸入如果是高電平，則計算乘法，并把輸出重新賦值到一端輸入，如果條件端是低電平，則什么也不錯；3）FIFO向右右移一位。整個運算直到FIFO中的數為0，然后FINISH變成高電平結束運算。以上整個運算都是并行進行的，在Verilog中注意使用非阻塞賦值^[5]。

3 結果仿真和資源占用

最終實現的運算陣列如圖二所示，switch_3組件是一個選擇器，當選擇短是高電平的時候，輸出值等于A輸入，否則是B輸入。Nfifo組件是一個并入串出的設備，每次輸入一個32位值，可以使用32個節拍，每一個節拍這個值要進行右移操作。當nfifo里全是0的時候，會把finish電平拉高，預示著計算結束，結果值就是最終結果了。

圖2 陣列實現圖

在modelsim中對電路進行后仿真，時鐘可以跑到125MHz，計算結果正確。下圖是整形運算的仿真截圖：

圖3 后仿真截圖

資源占用方面，每個浮點運算芯片使用了DEP48E 68個，查找表1078個，不到整個FPGA資源的5%。相對于使用查找表方法的實現，幾乎沒有使用內存資源。而相對于N為常量的運算，性能下降50%左右。

4結論

本文通過將浮點運算先轉換成整數運算，然后針對整數運算設計了專門的運算芯片的方法，完成了浮點數N次方的運算，在整個設計中，外部提供A,B,N三項輸入，運算芯片就可以輸出結果值。在PSDM算法的硬件移植過程中，本設計成功解決了N次方運算的瓶頸問題，PSDM算法大規模提升速度5倍以上，實現了硬件加速的目的。不僅如此，對FPGA的資源占用，也減少了35%。由于N次方運算的數學通用性，所以本設計同時也可以作為其他科學計算的數學資源庫。