GPU

Home * Hardware * GPU

GeForce 6600GT (NV43) GPU

GPU (Graphics Processing Unit),
a specialized processor primarily intended for graphic cards to rapidly manipulate and alter memory for fast image processing, usually but not necessarily mapped to a framebuffer of a display. GPUs have more raw computing power than general purpose CPUs but need a limited, specialized and massive parallelized way of programming, not that conform with the serial nature of alpha-beta if it is about a massive parallel search in chess. Instead, Best-first Monte-Carlo Tree Search (MCTS) approaches in conjunction with deep learning proved a successful way to go on GPU architectures.

GPGPU

There are various frameworks for GPGPU, General Purpose computing on Graphics Processing Unit. Despite language wrappers and mobile devices with special APIs, there are in main three ways to make use of GPGPU.

Mapping to an API

• BrookGPU (translates to OpenGL and DirectX)
• C++ AMP (Open standard by Microsoft that extends C++)
• DirectCompute (GPGPU API by Microsoft)

Native Compilers

• CUDA (GPGPU framework by Nvidia)
• OpenCL (Open Compute Language specified by Khronos Group)

Intermediate Languages

• HSAIL
• PTX
• SPIR

Inside

Modern GPUs consist of up to hundreds of SIMD or Vector units, coupled to compute units. Each compute unit processes multiple Warps (Nvidia term) resp. Wavefronts (AMD term) in SIMT fashion. Each Warp resp. Wavefront runs n (32 or 64) threads simultaneously.

The Nvidia GeForce GTX 580, for example, is able to run 32 threads in one Warp, in total of 24576 threads, spread on 16 compute units with a total of 512 cores. The AMD Radeon HD 7970 is able to run 64 threads in one Wavefront, in total of 81920 threads, spread on 32 compute units with a total of 2048 cores. . In real life the register and shared memory size limits the amount of total threads.

Memory

The memory hierarchy of an GPU consists in main of private memory (registers accessed by an single thread resp. work-item), local memory (shared by threads of an block resp. work-items of an work-group ), constant memory, different types of cache and global memory. Size, latency and bandwidth vary between vendors and architectures.

Here the data for the Nvidia GeForce GTX 580 (Fermi) as an example:

• 128 KiB private memory per compute unit
• 48 KiB (16 KiB) local memory per compute unit (configurable)
• 64 KiB constant memory
• 8 KiB constant cache per compute unit
• 16 KiB (48 KiB) L1 cache per compute unit (configurable)
• 768 KiB L2 cache
• 1.5 GiB to 3 GiB global memory

Here the data for the AMD Radeon HD 7970 (GCN) as an example:

• 256 KiB private memory per compute unit
• 64 KiB local memory per compute unit
• 64 KiB constant memory
• 16 KiB constant cache per four compute units
• 16 KiB L1 cache per compute unit
• 768 KiB L2 cache
• 3 GiB to 6 GiB global memory

Instruction Throughput

GPUs are used in HPC environments because of their good FLOP/Watt ratio. The instruction throughput in general depends on the architecture (like Nvidia's Tesla, Fermi, Kepler, Maxwell or AMD's Terascale, GCN), the brand (like Nvidia GeForce, Quadro, Tesla or AMD Radeon, Radeon Pro, Radeon Instinct) and the specific model.

• 32 bit Integer Performance

The 32 bit integer performance can be architecture and operation depended less than 32 bit FLOP or 24 bit integer performance.

• 64 bit Integer Performance

Current GPU registers and Vector-ALUs are 32 bit wide and have to emulate 64 bit integer operations.

• Mixed Precision Support

Newer architectures like Nvidia Turing and AMD Vega have mixed precision support. Vega doubles the FP16 and quadruples the INT8 throughput.Turing doubles the FP16 throughput of its FPUs.

• TensorCores

With Nvidia Volta series TensorCores were introduced. They offer fp16*fp16+fp32, matrix-multiplication-accumulate-units, used to accelerate neural networks. Turings 2nd gen TensorCores add FP16, INT8, INT4 optimized computation.

Throughput Examples

Nvidia GeForce GTX 580 (Fermi, CC 2.0) - 32 bit integer operations/clock cycle per compute unit

   MAD 16
   MUL 16
   ADD 32
   Bit-shift 16
   Bitwise XOR 32

Max theoretic ADD operation throughput: 32 Ops * 16 CUs * 1544 MHz = 790.528 GigaOps/sec

AMD Radeon HD 7970 (GCN 1.0) - 32 bit integer operations/clock cycle per processing element

   MAD 1/4
   MUL 1/4
   ADD 1
   Bit-shift 1
   Bitwise XOR 1

Max theoretic ADD operation throughput: 1 Op * 2048 PEs * 925 MHz = 1894.4 GigaOps/sec

Host-Device Latencies

One reason GPUs are not used as accelerators for chess engines is the host-device latency, aka. kernel-launch-overhead. Nvidia and AMD have not published official numbers, but in practice there is an measurable latency for null-kernels of 5 microseconds up to 100s of microseconds . One solution to overcome this limitation is to couple tasks to batches to be executed in one run .

Deep Learning

GPUs are much more suited than CPUs to implement and train Convolutional Neural Networks (CNN), and were therefore also responsible for the deep learning boom, also affecting game playing programs combining CNN with MCTS, as pioneered by Google DeepMind's AlphaGo and AlphaZero entities in Go, Shogi and Chess using TPUs, and the open source projects Leela Zero headed by Gian-Carlo Pascutto for Go and its Leela Chess Zero adaption.

See also

• Deep Learning
  • AlphaGo
  • AlphaZero
  • Convolutional Neural Networks
  • Leela Zero
  • Leela Chess Zero
• FPGA
• Graphics Programming
• Monte-Carlo Tree Search
  • MCαβ
  • UCT
• Parallel Search
• Perft(15)
• SIMD and SWAR Techniques
• Thread
• Zeta

Publications

2009

• Ren Wu, Bin Zhang, Meichun Hsu (2009). Clustering billions of data points using GPUs. ACM International Conference on Computing Frontiers
• Mark Govett, Craig Tierney, Jacques Middlecoff, Tom Henderson (2009). Using Graphical Processing Units (GPUs) for Next Generation Weather and Climate Prediction Models. CAS2K9 Workshop, pdf

2010...

• Avi Bleiweiss (2010). Playing Zero-Sum Games on the GPU. NVIDIA Corporation, GPU Technology Conference 2010, slides as pdf
• Mark Govett, Jacques Middlecoff, Tom Henderson (2010). Running the NIM Next-Generation Weather Model on GPUs. CCGRID 2010

2011

• Mark Govett, Jacques Middlecoff, Tom Henderson, Jim Rosinski, Craig Tierney (2011). Parallelization of the NIM Dynamical Core for GPUs. slides as pdf
• Ľubomír Lackovič (2011). Parallel Game Tree Search Using GPU. Institute of Informatics and Software Engineering, Faculty of Informatics and Information Technologies, Slovak University of Technology in Bratislava, pdf
• Dan Anthony Feliciano Alcantara (2011). Efficient Hash Tables on the GPU. Ph. D. thesis, University of California, Davis, pdf » Hash Table
• Damian Sulewski (2011). Large-Scale Parallel State Space Search Utilizing Graphics Processing Units and Solid State Disks. Ph.D. thesis, University of Dortmund, pdf
• Damjan Strnad, Nikola Guid (2011). Parallel Alpha-Beta Algorithm on the GPU. CIT. Journal of Computing and Information Technology, Vol. 19, No. 4 » Parallel Search, Reversi

2012

• Liang Li, Hong Liu, Peiyu Liu, Taoying Liu, Wei Li, Hao Wang (2012). A Node-based Parallel Game Tree Algorithm Using GPUs. CLUSTER 2012 » Parallel Search

2013

• S. Ali Mirsoleimani, Ali Karami Ali Karami, Farshad Khunjush (2013). A parallel memetic algorithm on GPU to solve the task scheduling problem in heterogeneous environments. GECCO '13
• Ali Karami, S. Ali Mirsoleimani, Farshad Khunjush (2013). A statistical performance prediction model for OpenCL kernels on NVIDIA GPUs. CADS 2013
• Diego Rodríguez-Losada, Pablo San Segundo, Miguel Hernando, Paloma de la Puente, Alberto Valero-Gomez (2013). GPU-Mapping: Robotic Map Building with Graphical Multiprocessors. IEEE Robotics & Automation Magazine, Vol. 20, No. 2, pdf

2014

• Qingqing Dang, Shengen Yan, Ren Wu (2014). A fast integral image generation algorithm on GPUs. ICPADS 2014
• S. Ali Mirsoleimani, Ali Karami Ali Karami, Farshad Khunjush (2014). A Two-Tier Design Space Exploration Algorithm to Construct a GPU Performance Predictor. ARCS 2014, Lecture Notes in Computer Science, Vol. 8350, Springer

2015 ...

• Peter H. Jin, Kurt Keutzer (2015). Convolutional Monte Carlo Rollouts in Go. arXiv:1512.03375 » Deep Learning, Go, MCTS
• Liang Li, Hong Liu, Hao Wang, Taoying Liu, Wei Li (2015). A Parallel Algorithm for Game Tree Search Using GPGPU. IEEE Transactions on Parallel and Distributed Systems, Vol. 26, No. 8 » Parallel Search

2016

• Sean Sheen (2016). Astro - A Low-Cost, Low-Power Cluster for CPU-GPU Hybrid Computing using the Jetson TK1. Master's thesis, California Polytechnic State University, pdf
• Jingyue Wu, Artem Belevich, Eli Bendersky, Mark Heffernan, Chris Leary, Jacques Pienaar, Bjarke Roune, Rob Springer, Xuetian Weng, Robert Hundt (2016). gpucc: an open-source GPGPU compiler. CGO 2016
• David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, Demis Hassabis (2016). Mastering the game of Go with deep neural networks and tree search. Nature, Vol. 529 » AlphaGo

2017

• David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815 » AlphaZero
• Tristan Cazenave (2017). Residual Networks for Computer Go. IEEE Transactions on Computational Intelligence and AI in Games, Vol. PP, No. 99, pdf

2018

• David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, Vol. 362, No. 6419

Forum Posts

2005 ...

• Hardware assist by Nicolai Czempin, Winboard Forum, August 27, 2006
• Monte carlo on a NVIDIA GPU ? by Marco Costalba, CCC, August 01, 2008

2010 ...

• Using the GPU by Louis Zulli, CCC, February 19, 2010

2011

• GPGPU and computer chess by Wim Sjoho, CCC, February 09, 2011
• Possible Board Presentation and Move Generation for GPUs? by Srdja Matovic, CCC, March 19, 2011

Re: Possible Board Presentation and Move Generation for GPUs by Steffan Westcott, CCC, March 20, 2011

• Zeta plays chess on a gpu by Srdja Matovic, CCC, June 23, 2011 » Zeta
• GPU Search Methods by Joshua Haglund, CCC, July 04, 2011

2012

• Possible Search Algorithms for GPUs? by Srdja Matovic, CCC, January 07, 2012
• uct on gpu by Daniel Shawul, CCC, February 24, 2012 » UCT
• Is there such a thing as branchless move generation? by John Hamlen, CCC, June 07, 2012 » Move Generation
• Choosing a GPU platform: AMD and Nvidia by John Hamlen, CCC, June 10, 2012
• Nvidias K20 with Recursion by Srdja Matovic, CCC, December 04, 2012

2013

• Kogge Stone, Vector Based by Srdja Matovic, CCC, January 22, 2013 » Kogge-Stone Algorithm
• GPU chess engine by Samuel Siltanen, CCC, February 27, 2013
• Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013 » Perft, Kogge-Stone Algorithm

2015 ...

• GPU chess update, local memory... by Srdja Matovic, CCC, June 06, 2016
• Jetson GPU architecture by Dann Corbit, CCC, October 18, 2016 » Astro
• Pigeon is now running on the GPU by Stuart Riffle, CCC, November 02, 2016 » Pigeon

2017

• Back to the basics, generating moves on gpu in parallel... by Srdja Matovic, CCC, March 05, 2017 » Move Generation
• Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017 » Perft(15)
• Chess Engine and GPU by Fishpov , Rybka Forum, October 09, 2017
• To TPU or not to TPU... by Srdja Matovic, CCC, December 16, 2017 » Deep Learning

2018

• Announcing lczero by Gary, CCC, January 09, 2018 » Leela Chess Zero
• GPU ANN, how to deal with host-device latencies? by Srdja Matovic, CCC, May 06, 2018 » Neural Networks
• How good is the RTX 2080 Ti for Leela? by Hai, September 15, 2018 » Leela Chess Zero

Re: How good is the RTX 2080 Ti for Leela? by Ankan Banerjee, CCC, September 16, 2018

• My non-OC RTX 2070 is very fast with Lc0 by Kai Laskos, CCC, November 19, 2018 » Leela Chess Zero
• LC0 using 4 x 2080 Ti GPU's on Chess.com tourney? by M. Ansari, CCC, December 28, 2018 » Leela Chess Zero

2019

• Generate EGTB with graphics cards? by Nguyen Pham, CCC, January 01, 2019 » Endgame Tablebases
• LCZero FAQ is missing one important fact by Jouni Uski, CCC, January 01, 2019 » Leela Chess Zero

External Links

• Graphics processing unit from Wikipedia
• Video card from Wikipedia
• Heterogeneous System Architecture from Wikipedia
• Tensor processing unit from Wikipedia
• General-purpose computing on graphics processing units (GPGPU) from Wikipedia
• List of AMD graphics processing units from Wikipedia
• List of Nvidia graphics processing units from Wikipedia
• NVIDIA Developer
• NVIDIA GPU Programming Guide

OpenCL

• OpenCL from Wikipedia
• Part 1: OpenCL™ – Portable Parallelism - CodeProject
• Part 2: OpenCL™ – Memory Spaces - CodeProject

CUDA

• CUDA from Wikipedia
• CUDA Zone | NVIDIA Developer
• Nvidia CUDA Compiler (NVCC) from Wikipedia
• Compiling CUDA with clang — LLVM Clang documentation
• CppCon 2016: “Bringing Clang and C++ to GPUs: An Open-Source, CUDA-Compatible GPU C++ Compiler" by Justin Lebar, YouTube Video

 :

Deep Learning

• Deep Learning | NVIDIA Developer » Deep Learning
• NVIDIA cuDNN | NVIDIA Developer
• Efficient mapping of the training of Convolutional Neural Networks to a CUDA-based cluster
• Deep Learning in a Nutshell: Core Concepts by Tim Dettmers, Parallel Forall, November 3, 2015
• Deep Learning in a Nutshell: History and Training by Tim Dettmers, Parallel Forall, December 16, 2015
• Deep Learning in a Nutshell: Sequence Learning by Tim Dettmers, Parallel Forall, March 7, 2016
• Deep Learning in a Nutshell: Reinforcement Learning by Tim Dettmers, Parallel Forall, September 8, 2016
• Faster deep learning with GPUs and Theano
• Theano (software) from Wikipedia
• TensorFlow from Wikipedia

Game Programming

• Advanced game programming | Session 5 - GPGPU programming by Andy Thomason
• Leela Zero by Gian-Carlo Pascutto » Leela Zero

GitHub - gcp/leela-zero: Go engine with no human-provided knowledge, modeled after the AlphaGo Zero paper

Chess Programming

• GPU Chess Blog
• Chess on a GPGPU
• Zeta OpenCL Chess
• ankan-ban/perft_gpu · GitHub  » Perft
• LCZero · GitHub » Leela Chess Zero

References

Up one Level