以FPGA實現基於部分距離搜尋法之競爭式學習系統

FPGA Implementation of Competitive Learning with Partial Distance Search

李惠雅(Hui-Ya Li)

指導教授 ： 黃文吉

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2007年)

摘要

本論文針對k贏家通吃競爭式學習法之場域可程式化閘陣列(FPGA)實作提出一新演算法。k個得以進行更新的獲勝神經元，為每一個輸入向量在小波域(wavelet domain)中執行部分距離搜尋(partial distance search)所找出的最近似者。在大多數的應用裡，PDS以軟體方式被用於神經元搜尋的加速。此章節將提出一個適於硬體實現的新PDS演算法。此演算法使用子空間搜尋(subspace search)、有限精度計算(finite precision calculation)、多係數累積(multiple-coefficient accumulation)、和查表式除法(lookup-table based division)等技巧來有效降低面積複雜度與運算延遲。也提出ㄧ個新的排序架構，用於PDS步驟後k個獲勝神經元的判定。
在此提出的硬體架構將以專用?輯區塊電?(custom logic block)的方式內嵌於Nios軟核心中央處?器的算術?輯單元(ALU)中。Nios處?器所提供的客製指?(custom instruction)?是用於存取專用?輯區塊電?的方式。我們已測?出，Nios軟核心中央處?器執?用於「k贏家通吃競爭式學習訓練」之部分距?搜尋程式客制指令所需的CPU時間。實驗結果顯示CPU時間低於未搭配部份距?搜尋硬體電?的Pentium IV處?器。

關鍵字

競爭式學習 ； FPGA

並列摘要

This paper presents a novel algorithm for the field programmable gate array (FPGA) realization of the competitive learning (CL) algorithm with k-winners-take-all activation. The k winning neurons for updating are those best matching the input vector in the wavelet domain with partial distance search (PDS). In most applications, the PDS is adopted as a software approach for attaining moderate codeword search acceleration. In this chapter, a novel PDS algorithm well-suited for hardware realization is proposed. The algorithm employs subspace search, finite precision calculation, multiple-coefficient accumulation, and lookup-table based division techniques for the effective reduction of the area complexity and computation latency. A novel sorting architecture is also proposed for identifying the k winning neurons after the PDS process.
The proposed implementation has been adopted as a custom logic block in the arithmetic logic unit (ALU) of the softcore NIOS processor. The custom instructions are also derived for accessing the custom logic block. The CPU time of the NIOS processor executing the PDS program with the custom instructions for k-winners-take-all CL training is measured. Experiment results show that the CPU time is lower than that of Pentium IV processors executing the PDS programs without the support of custom hardware.

並列關鍵字

competitive learning ； FPGA

參考文獻

[3] C.D. Bei and R.M. Gray, “An Improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization.“ IEEE Trans. Communication, Vol. COM-33, pp.1132-1133, Oct. 1985.

[4] Bondalapati K. and Prasanna V.K., “Reconfigurable computing systems,” Proceedings of the IEEE, Vol. 90, pp.1201-1217, 2002.

[6] Colavita A. A., Cicuttin A., Fratnik F., Capello G. SORTCHIP, “A VLSI Implementation of a Hardware Algorithm for Continuous Data Sorting,” IEEE Journal of Solid-State Circuits, Vol. 38, pp 1076-1079, 2003.

[7] Cole R. and Seigel A. R., “Optimal VLSI circuit for sorting,” Journal of ACM, Vol. 35, pp.777–809, 1998.

[8] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression. Kluwer, Norwood, Massachusetts, 1992.