臺灣博碩士論文加值系統

隨著圖型處理器(GPU)的問世，例如NVIDIA GeForce系列，繪圖硬體逐漸變得更強大且可編程。由於GPU內大量的平行架構，GPU做浮點數運算的能力超越了通用的CPU。而最新的GPU實際上也擁有足夠的編程自由去做除了圖形處理以外之其他計算。此篇論文會利用GPU的優點進而提高資料分群演算法的效能。本篇論文我們將在GPU上實作一個資料分群的演算法－使用m個最近群中心的廣義模糊k均值分群法(GFKM)。我們將會比較GFKM在CPU和GPU運算後的加速程度，同時也會分析使用GPU運算此分群法的利與弊。從我們的實驗結果可以得知我們提出的方法比CPU的最佳版本速度加快約三到十八倍。

The graphics hardware is becoming increasingly more powerful and programmable with the introduction of Graphics Processing Units (GPU) like the NVidia GeForce series. The GPU’s exceed the ordinary general purpose CPU’s ability to do floating point operations due to the massively parallel architecture in the GPU’s. With the newest GPU’s one actually have enough programmable freedom to do other computations than computer graphics processing. This project will take advantage of this in order to get high performance implementations of data clustering algorithms. In this project we will implement a data clustering algorithm, which is Generalized Fuzzy k-Means Clustering Using m nearest Cluster Centers (GFKM) [1], on a GPU. We also make comparisons with CPU based implementations and analysis the pros and cons of using GPU’s. Our experimental results show that our GPU-based GFKM algorithms are about three to eighteen times faster than the optimized CPU code-based GFKM algorithms.

摘要
ABSTRACT
致謝
目錄
List of Table
List of Figs
List of Algorithms
Chapter 1 Introduction
1.1 Background
1.2 Motivation
1.3 Organization
Chapter 2 Related Works
2.1 Introduction to GPU Architecture
2.2 GFKM Algorithm
Chapter 3 Proposed Method
3.1 Introduction to the Proposed Method
3.2 Updating Membership
3.3 Calculating new Centroids
3.3 Checking Convergence
Chapter 4 Experimental Results
4.1 Performance Measure
4.2 The First Test
4.3 The Second Test
4.4 The Third Test
4.5 The Fourth Test
Chapter 5 Conclusion and Future Work
5.1 Conclusion
5.2 Future Work
REFERENCES

[1] Franklin J. C. Lai, Eric Y. T. Juan, and Jim Z. C. Lai, Generalized Fuzzy k-Means Clustering Using m Nearest Cluster Centers, 2013.
[2] You Li, Kaiyong Zhao, Xiaowen Chu, and Jiming Liu, Speeding up K-Means Algorithm by GPUs, 2010.
[3] Mark Harris, Optimizing Parallel Reduction in CUDA, NVIDIA Developer Technology, 2007.
[4] CUDA Programming Guide Version 7.0, Technical report, NVIDIA Corporation, 2015.
[5] https://en.wikipedia.org/wiki/CUDA.
[6] V. Schwammle and O. N. Jensen, “A simple and fast method to determine k-means cluster analysis,” Bioinformatics, vol. 26, no. 3, September 2010, pp. 2841-2848.