KawPow演算法硬體架構實現於FPGA

Abstract

本論文中所提及的KawPow演算法為Ravencoin的演算法，Ravencoin是一種區塊鏈，主要目的是提供轉帳功能，為維持這個機制，必須實際操作KawPow演算法並得到小於特定值的答案，符合的答案可以使區塊鏈產生新的區塊。因區塊鏈演算法的特性，需經過多次計算才可得出答案，在單位時間內的計算次數則稱為算力(hash rate)，而論文內容則針對如何提升算力來討論及實作。 KawPow演算法為一種區塊鏈演算法，其特性為memory-bound以及memory-hard，也就是會對memory進行大量資料讀取以及寫入，因此對於記憶體頻寬以及記憶體容量要求較高。除此之外，相比於其他相同特性的區塊鏈演算法如Ethash的演算法，KawPow演算法為了要防止ASIC以及FPGA利用硬體高運算效率的特性主宰算力，提升了用來計算的資料寬度，而這也導致ASIC及FPGA面積的使用大大提升，成本也隨之上升，使ASIC及FPGA無法完美發揮其運算快速之優勢，也達成防止算力被主宰的目的。雖然如此，本論文仍將利用現有FPGA的有限資源，針對KawPow演算法運算資料寬度大幅提升的問題進行分析及實作。 本論文將KawPow演算法實作於Xilinx FPGA VU35P晶片上並使用Xilinx的開發軟體Vivado進行synthesis、placement和routing，藉由分析實驗室舊版KawPow演算法硬體架構之優缺點，善用FPGA上的資源並將舊版架構加以改良，達到超越舊版架構的效能(Performance)。論文中詳細描述了從舊版硬體架構缺點之分析、KawPow演算法分析、FPGA硬體資源整理並分配、演算法硬體架構設計、FPGA資源使用量之估算、到最後實作、面積優化以及在FPGA進行emulation的過程。 論文最後整理出了新版及舊版架構的算力差距、資源使用，以及新版emulation的結果。從simulation可以看出，新版所能達到的算力為舊版的四倍，且在相同頻率的情況下使用Xilinx的開發軟體Vivado進行P&R及timing分析，新版的timing result比舊版更好，而新版架構於FPGA進行emulation時，則可操作在360MHz，約可達到5.6M Hash/s的算力。

KawPow algorithm discussed in the thesis is the algorithm for Ravencoin. Ravencoin is a blockchain and platform optimized for transferring assets. To sustain the mechanism, the valid hash values which are smaller than specific values are derived by calculating the KawPow algorithm. The valid hash values make the blockchain generate a new block. Because of the characteristic of blockchain, the valid hash values are derived after lots of attempts and computations. The number of computations in unit time is called hash rate. This thesis focuses on how to increase the hash rate and implement the algorithm. KawPow algorithm which the thesis implements is one kind of algorithm of blockchain. The features of the algorithm are memory-bound and memory-hard. That is to say, it has a high requirement of memory bandwidth and does memory access lots of time. Besides, compared to the other algorithm which features are also memory-bound and memory-hard such as Ethash, to avoid the ASIC and FPGA dominating the hash rate by high computing efficiency, the KawPow algorithm increases the data width for computing. As a result, not only the area utilization increases significantly, but also the cost of ASIC and FPGA increases as well. This makes the ASIC and FPGA not able to make use of their advantage of high computing efficiency. However, the thesis still uses limited resources and focuses on the problem of high data width to analyze and implement on FPGA. The thesis shows how to implement the hardware architecture of KawPow on Xilinx FPGA VU35P and run the synthesis and implementation on Vivado, which is a Xilinx developing software. Besides, by analyzing the original hardware architecture of KawPow in laboratory, the author makes the good use of FPGA resources to improve the shortcomings and surpasses the performance (hash rate) of the original architecture. The thesis presents the flow of implementation in detail. 1. Analysis of the original architecture 2. Analysis of KawPow algorithm 3. Reallocation of FPGA resources 4. Design the hardware architecture 5. Estimation of the utilization of FPGA resources 6. Implementation, area reduction, and emulation. At the end of the thesis, the difference of hash rate between the original architecture and improved architecture will be presented. Besides, the emulation result of improved architecture will be presented too. When executing the simulation, the hash rate of the improved architecture is four times better than the original architecture. Besides, when we execute the implementation using Xilinx developing software “Vivado”, the timing result of the improved architecture is better than the original architecture. The improved architecture can be executed at 366MHz when executing emulation. The hash rate achieves 5.6MH/s.