簡易檢索 / 詳目顯示

回結果列表
研究生： 潘璟德
Pan, Jin-De
論文名稱： 應用支援列舉法在圖形處理器上計算二元矩陣賽局之納許平衡點
Using Support Enumeration Method on GPU to Find Nash Equilibria in Bimatrix Games
指導教授： 朱治平
Chu, Chih-Ping
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2011
畢業學年度： 99
語文別： 英文
論文頁數： 47
中文關鍵詞： CUDA 、圖形處理器 、納許平衡點 、二元矩陣賽局
外文關鍵詞： CUDA, GPU, Nash equilibria, Bimatrix game
相關次數： 點閱：121  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在本論文中,我們提出了一個在圖形處理器(Graphics Processing Unit, GPU)上使用支援列舉法計算二元矩陣賽局之納許平衡點的演算法。圖形處理器是一個擁有多核心運算多重處理器的硬體單元。在最近幾年,因為圖形處理器的多核心多重處理器硬體架構特性,使得它能夠被廣泛的使用在各種不同的領域。而計算賽局理論之納許平衡點是一個非常耗時且繁複的工作,如果我們只應用單核的中央處理器去作運算,將會耗費相當大的時間成本。因此我們將計算賽局理論之納許平衡點的工作交由圖形處理器去作高速運算,以減少耗費的時間。我們實做出在圖形處理器上使用CUDA語言計算納許平衡點。實驗結果顯示,在圖形處理器上計算賽局理論之納許平衡點能夠執行得很有效率。

    In our research, we propose an algorithm that achieves the computation of support enumeration method to nd all Nash equilibria in bimatrix games on graphics processing unit (GPU). Recently, GPU has been widly used in many di erent applications because of its tremendous computing capability. Computing all Nash equilibria in large bimatrix game is a time-consuming work using single-processor computers. Based on the sequential support enumeration algorithm, we design and implement a parallel support enumeration algorithm on GPU for nding all Nash equilibria in bimatrix games. We performed experiments using CUDA enabled GPU and showed the performance of the parallel algorithm. Finally, we conclude this research and give suggestions for furture work.

    Contents 論文口試委員審定書(中) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 論文口試委員審定書(英) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Abstract(in Chinese) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract(in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 CUDA Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 CUDA Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 CUDA Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 CUDA Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Nash Equilibrium of Bimatrix Game . . . . . . . . . . . . . . . . . . . 16 3.3 Support Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Computing Nash equilibria on CUDA . . . . . . . . . . . . . . . . . . . . . . 24 4.1 Computing Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Computing on Multi-GPU . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Experimental Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

    References
    [1] NVIDIA, Nvidia cuda c programming guide 3.2."
    CUDA C Programming Guide.pdf, Oct 2010.
    [2] W.-M. W.Hwu, Nvidia cuda 大量平行處理器程式設計," 2008.
    [3] NVIDIA, Nvidia cuda best practices guide 3.2."
    CUDA C Best Practices Guide.pdf, Aug 2010.
    [4] NVIDIA, Nvidia cuda toolkit reference manual."
    CUDA Toolkit Reference Manual.pdf, Aug 2010.
    [5] NVIDIA, Cuda forum."
    [6] J. Sanders and E. Kandrot, CUDA by Example: An Introduction to General- Purpose GPU Programming. Addison Wesley, 2010.
    [7] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, Coalitional game theory for communication networks," Signal Processing Magazine, IEEE, vol. 26, pp. 77-97, september 2009.
    [8] Z. Ma and A. Krings, Dynamic hybrid fault modeling and extended evolutionary game theory for reliability, survivability and fault tolerance analyses," Reliability,
    IEEE Transactions on, vol. 60, pp. 180-196, march 2011.
    [9] L. Zhao, J. Zhang, and H. Zhang, Using incompletely cooperative game theory in wireless mesh networks," Network, IEEE, vol. 22, pp. 39 {44, jan.-feb. 2008.
    [10] C. E. Lemke and J. T. Howson, Equilibrium points of bimatrix games," Journal of the Society for Industrial and Applied Mathematics, vol. 12, no. 2, pp. 413-423, 1964.
    [11] R. Porter, E. Nudelman, and Y. Shoham, Simple search methods for finding a nash equilibrium," Games and Economic Behavior, vol. 63, pp. 642-662, July 2008.
    [12] B. Von Stengel, Computing equilibria for two-person games," in Handbook of Game Theory with Economic Applications (R. Aumann and S. Hart, eds.), vol. 3 of Handbook of Game Theory with Economic Applications, ch. 45, pp. 1723-1759, Elsevier, May 2002.
    [13] B. von Stengel, Equilibrium computation for two-player games in strategic and extensive form," Algorithmic Game Theory, vol. chapter 3, (eds. N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani), Combridge Univ. Press, pp. 53-78,
    2007.
    [14] R. Datta, Finding all nash equilibria of a nite game using polynomial algebra," Economic Theory, vol. 42, pp. 55-96, January 2010.
    [15] J. Widger and D. Grosu, Computing equilibria in bimatrix games by parallel sup- port enumeration," Parallel and Distributed Computing, International Symposium on, vol. 0, pp. 250-256, 2008.
    [16] Z. Yang, Y. Zhu, and Y. Pu, Parallel image processing based on cuda," in Computer Science and Software Engineering, 2008 International Conference on, vol. 3, pp. 198-201, dec. 2008.
    [17] L. A. Dugatkin and H. K. Reeve, Game Theory and Animal Behavior. Oxford Univ Pr on Demand, 2000.
    [18] J. F. Nash, Non-cooperative games," annals of Math, vol. 54(2), pp. 286-295, 1951.
    [19] K. Li, F. Karray, K. Hipel, and D. Kilgour, Fuzzy approaches to the game of chicken," Fuzzy Systems, IEEE Transactions on, vol. 9, pp. 608-623, aug 2001.
    [20] S. Chong and X. Yao, Behavioral diversity, choices and noise in the iterated prisoner's dilemma," Evolutionary Computation, IEEE Transactions on, vol. 9, pp. 540-551, dec. 2005.
    [21] M. Nokleby, W. Stirling, and A. Swindlehurst, Satis cing learning dynamics in the stag hunt," in Adaptive and Learning Systems, 2006 IEEE Mountain Workshop on, pp. 219-224, july 2006.
    [22] G. Rabow, The social implications of nonzero-sum games," Technology and Society Magazine, IEEE, vol. 7, pp. 12-18, mar 1988.
    [23] N. Hanchate and N. Ranganathan, Simultaneous interconnect delay and crosstalk noise optimization through gate sizing using game theory," Computers, IEEE Transactions on, vol. 55, pp. 1011-1023, aug. 2006.
    [24] NVIDIA, Nvidia cuda toolkit 3.2 rc2," Jan 2004.
    [25] NVIDIA, Nvidia cuda sdk 3.2," Apr 2010.
    [26] E. Nudelman, J. Wortman, Y. Shoham, and K. Leyton-Brown, Run the gamut: a comprehensive approach to evaluating game-theoretic algorithms," in Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004. Proceedings of the Third International Joint Conference on, pp. 880-887, 2004.
    [27] R. D. McKelvey, A. M. McLennan, and T. L. Turocy, Gambit: Software tools for game theory, version 0.2010.09.01.," 2010.
    [28] NVIDIA, Nvidia cuda occupancy calculator." CUDA Occupancy calculator.xls.
    [29] Video card benchmarks."

    下載圖示 校內：2021-12-31公開
    校外：2021-12-31公開
    QR CODE