進階搜尋


 
系統識別號 U0026-0812200915384556
論文名稱(中文) 使用GPU平行運算加速電腦象棋之走子產生器
論文名稱(英文) A GPU Based Move Generator for the Game of Chinese Chess
校院名稱 成功大學
系所名稱(中) 工程科學系碩博士班
系所名稱(英) Department of Engineering Science
學年度 97
學期 2
出版年 98
研究生(中文) 龔建銓
研究生(英文) Chien-Chuan Kung
電子信箱 jk@nc.es.ncku.edu.tw
學號 n9696411
學位類別 碩士
語文別 中文
論文頁數 38頁
口試委員 指導教授-侯廷偉
口試委員-許舜欽
口試委員-顏士淨
中文關鍵字 平行運算  顯示卡運算  電腦象棋 
英文關鍵字 Game of Chinese Chess  GPU Computing  Parallel Computing 
學科別分類
中文摘要 電腦象棋的能力主要取決於演算法的優劣與硬體的運算速度,現今大多數電腦象棋程式的運算工作都是由中央處理器(CPU)來負責運算。但是現今CPU的時脈提升已接近瓶頸,若還想要更大量的運算資源勢必要朝多執行緒平行化運算的方向來努力。近年來隨著圖形處理器(GPU)的進步,GPU已成為個人電腦中除了CPU之外第二強大的運算單元,為了針對圖形運算的特性,GPU有著大量的平行運算單元以計算圖形中各個頂點的光影變化和上色渲染。以往GPU只能透過DirectX或OpenGL等影像處理函式存取,因此很難被利用在處理影像之外的領域。
過去尚未有人提及應用GPU加速電腦象棋的運算,本論文使用GPU加速計算電腦象棋中走子產生器(Move Generator)的部份,同時本論文也將分析電腦象棋程式的架構與GPU運算特性之間的關係,以及比較電腦象棋程式中各部份可平行化的程度,並建立CPU與GPU之間分工的架構。
本實驗的實作與效能測量是在個人電腦上完成,設備等級為CPU Intel Core 2 Duo 6400 2.14 GHz + 2G RAM,GPU等級為9800GT 610MHz + 512MB RAM。實驗結果顯示走子產生器的部份相較本來CPU運算約有30~50%的提升,但是由於記憶體的傳輸時間延遲,整體的程式效率並沒有顯著提升,反而下降了43%。
英文摘要 Targeted for graphical computing, GPU has a large number of parallel computing units to execute graphic functions. In the past, GPU was difficult to be used in areas outside the image/graphic processing because it can only be accessed by some image processing libraries such as DirectX or OpenGL, etc. In addition, GPU has never been used in accelerating computer chess programs.
This thesis tries to explore if GPU is feasible for computer chess programs. We try to port the move generator of a Chinese chess program to the GPU. After carefully analyzing the chess program structure, the move generator is ported to the GPU of a personal computer. The analysis includes the relationship between the Chinese chess program's architecture and the GPU architecture, and the possible parallel candidate portions of the program. Experiments and fine-tuning of the move generator were performed. Currently, we find that the move generator's speedup, as compared with the CPU, is 47%; however, considering the delay of the copying of a large volume of shared data between GPU and CPU, the total performance is degraded 43%.The implementation and performance measurements are on the person computer, equipped with Intel Core 2 Duo 6400 2.14 GHz CPU, plus 2G RAM, and GPU is 9800GT 610MHz plus 512MB RAM.
論文目次 摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 背景 1
1.2 研究動機 4
1.3 電腦象棋結合GPU運算的優點 5
1.4 研究目的 5
1.5 研究流程 5
1.6 章節提要 6
第二章 背景與相關技術探討 7
2.1 電腦象棋 7
2.2 走子產生器(Move Generator) 8
2.3 平行運算與SIMD 8
2.4 GPU運算與CUDA 9
2.4.1 CUDA程式設計模型 11
2.4.2 執行緒、區塊與網格 12
2.4.3 記憶體 14
第三章 系統設計與實作 17
3.1 系統架構 17
3.2 記憶體規劃 23
3.3 程式碼平行化展開的部份 24
3.4 針對CUDA運算特性所做的改進 29
3.4.1 合併存取(coalesced I/O) 29
3.4.2 指令分支和warp對齊 30
3.4.3 材質快取 33
3.4.4 吃子與非吃子棋步產生合併 33
第四章 實驗結果 34
4.1 平行化展開程度 34
4.2 正確性檢驗 35
4.3 相對於未平行化前的效率分析 35
第五章 結論及未來工作 37
參考文獻 38
參考文獻 [1] Marc Boulé, and Zeljko Zilic, "FPGA Based Move Generator for the Game of Chess," Proceedings of the IEEE Custom Integrated Circuits Conference, pp. 71-74, 2002
[2] CUDA Zone -- The resource for CUDA developers , Available at: http://www.nvidia.com/cuda
[3] Chrilly Donninger, and Ulf Lorenz, "The Hydra Project," Xcell Journal, issue 53, pp. 94–97 , 2005
[4] Chrilly Donninger, Alex Kure, and Ulf Lorenz, "Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program," Proceeding of 18th Parallel and Distributed Processing, Santa Fe – NM USA,pp.44-52, April 2004
[5] Michael Garland, Scott Le Grand, John Nickolls, Joshua Anderson, and Jim Hardwick," Parallel Computing Experiences with CUDA," Micro, IEEE, vol. 28, no. 4,pp.13-27, July-Aug 2008
[6] Scott Hamilton, and Lee Garber, "Deep Blue's Hardware-Software Synergy," Computer ,vol. 30, no. 10, pp. 29 – 35, October 1997
[7] F.-H. Hsu, "IBM’s Deep Blue Chess Grandmaster Chips," IEEE Micro, vol. 19, no. 2, pp. 70-81, Apr 1999.
[8] Peter Messmer, Paul J. Mullowney, and Brian E. Granger, "GPULib: GPU Computing in High-level Languages," Computing in Science & Engineering, vol. 10, no. 5,pp. 70-73, Sept.-Oct 2008
[9] Larry Rosenblum, and Michael Macedonia, "Computation on Programmable Graphics Hardware," IEEE Computer Society ,vol. 25, no. 5,pp.12-15,Sept.-Oct. 2005
[10] John D. Owens, Mike Houston, David Luebke, Simon Green, John E. Stone, and James C. Phillips, "GPU Computing," Proceedings of the IEEE vol. 96, no. 5, pp. 879 – 899, May 2008
[11] Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu, "Computer Chinese Chess," ICGA Journal, vol. 27, no.1, pp. 3-18, ISSN 1389-6911, March 2004.
[12] 鄭明政,電腦象棋程式位置評分表之研究,國立成功大學工程學系論文,民國九十五年
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2011-08-29起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2011-08-29起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw