AstroGPU 2007 Notes (A. Shelton)

---

---

General Information

• Program Schedule (HTML, PDF)
• Slides for talks
• Group photo

---

Day One

General Purpose Computing on GPUs (Luebke)

a.k.a. Democratization of parallel computing

• GPUs are a cost effective data-parallel computing option as a developer kit costs ~$200
• Computers are no longer getting faster - just wider.
  • parallelization only way to gain performance
• data-parallel computing most scalable solution (as opposed to task-parallel, etc.)
• GPUs roughly give you 10x speed up over a CPU with no modification to parallel code - "out of the box"
• Specialized for math-intensive highly parallel computation
• Evolution in GPU computing - was GPGPU (trick GFU into general purpose computing) -> now GPU Computing (true general purpose - no tricks necessary)
• CUDA = Compute Unified Driver Architecture
• nVidia offers a new platform, Tesla, which is "graphics free" - no graphics capabilities at all - only computing
• nVidia thinks that general purpose computing is the future of GPUs - even more important than video games
• GPUs are the new massively parallel computers

Science on GPUs - Part I

GPU Acceleration of Scientific Applications Using CUDA (Stone)

• Amdahl's Law - Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved. It is often used in parallel computing to predict the theoretical maximum speedup using multiple processors.
• Parallel algorithms are the hard part, not the API (e.g. CUDA)
• CUDA is easy to mix with other parallel programming APIs (e.g. POSIX threads)
• Use algorithms that expose substantial parallelization
• Identify ideal GPU memory system to use for kernel data for best performance
• Minimize host/GPU DMA transfers, use pinned memory buffers when appropriate
• Development Tip: Use small examples to explore approaches to get best performance
• Choose algorithms wisely and understand the trade-offs between chosen algorithm and alternatives
• Seek to reduce memory references
• Avoid branching and divergent branches

GPU Applications at UMd (Dorland)

• UMd computer science department could be possible future collaborator? They work with large-scale visualization algorithms among other things.
• Using an NSF-funded GPU/CPU cluster and are upgrading it winter 07/08
• UMIACS - UMd Institute for Advanced Computer Studies, including physics and astrophysics
• Funding - NSF, DOE, NASA, DARPA
• UMd has middleware layer for programming GPUs (written in Fortran)
• Use custom algorithms
• Their software successfully being used by non-CUDA, non-computer science experts

Internals of CUNBODY-1 Library (Hamada)

High Performance Gravitational N-body Simulation on GPUs (Zwart)

Science on GPUs - Part II

Graphics Hardware-Accelerated Real-Time Processing Pipline for Radio Astronomy (Dale)

• Lincoln Greenhill at Harvard is involved in this
• Murchison Widefield Array (MWA) in Australian outback, operational by end of 2008
  • uses tiles, operates below 1.6 GHz
• Single GPU implementation -> scales to cluster
• data center co-located with array (16GB/s), upstream 1.7 GB/s
• Using CUDA, some OpenGL
• Major stages of the real time system 1 Array calibration - refraction, Faraday effect, ionispheric calibration, instrument calibration 1 Image formation - gridding, inverse Fourier transforms
• CPU -> GPU speedup * Calibration steps -> ~10x * Imaging -> ~20x * Gridding -> ~65x
• Single-precision ok for their purposes
• 1000 freq channels, 65 sources every 8 seconds, 1600^2 output image resolution
• GPUs consume much less power than the CPUs running equivalent code (14 kW vs. 151 kW)
• Still evaluating - GPUs are a promising platform, no final decision yet
• custom software for imaging and calibration

Real-Time Digital Signal Processing for Radio Astronomy Using GPUs (Brisken)

• Princeton might be interested in collaboration - telescope time for use of their clusters

Fast Summation of Potentials: the FMM on the GPU (Gumerov)

• FMM = Fast Multi-Pole Method
• Fortran & CUDA
• Kernels: LaPlace 3D, Helmhotz 3D
• Have own middleware library (see poster)

GRAPE-DR (Makino)

• Hardware targetted at N-body simulation (programming done in VHDL)
• Latest proposed design expanded to additional algorithms: new architecture, program in assembly
• Want to develop common software platform for various hardware (GRAPE, GPU, FPGA, etc.) because common programming paradigms for all

CUDA Tutorial - Parts I & II

• GPU threads are extremely lightweight - little creation overhead, context switching essentially free
• Goal -> same program, scalable performance
• Threads execute a kernel in blocks, blocks are organized in a grid
• Threads in a block share on-chip memory in PDC; barrier synchronization
• Blocks within a grid are independent - no global synchronization, no per-block mutex, blocks run to completion in unspecified order
• Single Instruction, Multiple Data (SIMD) - a technique employed to achieve data level parallelism, as in a vector processor. First made popular in large-scale supercomputers (contrary to MIMD parallelization), smaller-scale SIMD operations have now become widespread in personal computer hardware. Today the term is associated almost entirely with these smaller units.
• Warp -> unit of SIMD execution
• Each multiprocessor is a set of SIMD thread processors
• Memory architecture - 32-bit registers, on-chip shared memory, real-only constant cache, texture cache, device memory (global) [items in bold are most important, others are subtleties]
• Each thread block: split into warps, executed by only 1 multiprocessor
• A multiprocessor can execute several blocks concurrently
• CUDA programming in C: provide minimal set of extensions necessary to expose power
  • declaration specifiers to indicate where things live
  • extend function invocation syntax for parallel kernel launch
  • special variables for thread identification in kernels
  • intrinsics that expose specific operations in kernel code
• Features available to kernel
  • standard math functions: sin, cos, etc.
  • built-in vector types: float4, int4, etc. for dim 1 to 4
  • texture access
• Runtime support
  • memory allocation
  • memory copy, host <-> device, device <-> drivers
  • texture management
  • OpenGL and directK interoperability
• Can calculate theoretical performance and actual performance to get a feel for how much optimization can be done and if it might be worth the effort
• Partition data to operate in well-sized blocks
• Common scenarios - reduce, split, compact/expand
• Scan Algorithm (GPU Gems 2, 3) - very useful in parallel computing, not needed in serial computing
• Balanced trees - conceptual, not actual data structure, sweep to and from root
• Segmented scan - parallel quicksort, parallel matrix-vector multiply in compressed sparse row (CSR) format
• CUDA data-parallel primitives library - collaboration between nVidia and UC Davis, in beta release now at http://www.gpgpu.org/developer

---

Day Two

CUDA Tutorial - Part III

Overview

CUDA Optimization Strategies:

• Instruction precision, accuracy, and performance
• Memory Hierarchy performance
• avoiding SIMD divergence & bank conflicts
• coalescing memory operations
• Loop unrolling
• Using template parameters to write general-yet-optimized code
• Optimizing CPU-GPU transfers
• Algorithmic strategies
• Profiling tools

Notes

• General optimization guidance
  • coalescing memory operations - ~10x speedup - first thing to look for when optimizing CUDA code
    • coalescing - coordinated read by a half-warp, contiguous region of global memory, not all threads have to participate
      • use structure of arrays instead of arrays of structures
      • if not SoA, force structure alignment [__align(X) where X = 4, 8, or 16] use shared memory to achieve coalescing
      • greatly improves throughput
      • critical to small or memory-bound kernels
  • latency hiding
    • more threads/block = better memory latency hiding BUT more threads/block = fewer registers/thread
      • choose threads/block as multiple of warp size
      • min - 64 threads/block, 128-256 better choice, experiment!
    • register dependency - read after write dependency - more threads - at least 25% occupancy
    • synchronization (__syncthreads) - very lightweight, 1 clock cycle
  • shared memory bank conflicts - last thing to optimize
    • take advantage of shared memory - x100's faster than global, threads can cooperate through shared memory
    • parallel memory architecture
      • memory is divided into banks
      • bank can service one address/cycle
      • G80: 16 banks - same as the size of a half-warp
    • shared memory as fast as registers when no bank conflicts
    • simultaneous accesses to a bank result in a bank conflict - these are serialized
      • the more bank conflicts, the greater the return for optimization
• maximize: independent parallelism, arithmetic intensity, sometimes better to recompute than cache, avoid costly data transfers (do more computation on GPU)
• optimize memory coherence - coalesced Vs. non-coalesced, spatial locality (nearby pixels) in cached texture memory, avoid high-degree bank conflicts (shared memory)
  • global memory read/write - like to be performance bottleneck, can use coalescing to get ~10x speedup
• keep processors equally busy
• keep resource usage low enough to support multiple active thread per block
• data transfer
  • minimize transfers
  • group transfers - one large better than many small
  • page-locked memory transfers (cudaMallocHost, highest cudaMemcpy performance) - use with caution because allocating too much page-locked memory can reduce overall system performance
  • PCI Express slots - some motherboards have very difference performance between slots
• occupancy
  • number of warps running concurrently on a multiprocessor divided by max. number of warps than can run concurrently
  • keep hardware busy by executing other warps when busy
  • minimize occupancy requirements by minimizing latency
  • maximize occupancy by optimizing number of threads that run on each multiprocessor
  • register pressure, check .cubin file for # registers/kernel, can use -maxrregcount=N flag to NVCC, they are working on a visual profiler
  • .cubin file important for evaluating resource usage
  • CUDA Occupancy Calculator
  • occupancy = performance (necessarily)
• NVidia hardware compatible with things like OpenMP to facilitate multi-GPU applications
• grid/block size heuristics
  • e.g. # blocks/# multiprocessors > 1, all mp have at least one block to execute
  • many more
• you can make applications self-tuning (like fftw and atlas)
• relevant metrics - GFLOPS for compute-bound, Bandwidth for memory-bound

---

CUDA Tutorial - Part IV

Overview

Using CUDA Libraries:

• CuBLAS - Basic Linear Algebra Subprograms
• CuFFT - Fast Fourier Transforms (1D, 2D, 3D transforms of complex or real data sets)
• Calling CUDA from MATLAB, MEX plugin
• Example: Fast Poisson solver, CUDA accelerated MATLAB
• Graphics API interoperability

---

Notes

• Cuda 1.1
  • language improvements
    • Subset of C++ fully supported
    • volatile honored
    • loop unrolling with #pragma unroll
    • inlining control with __noinline__
  • asynchronous API
    • stream API - launch stream of commands to GPU which will run asynchronously
    • event API - insert events in the stream to query whether preceding operations have finished
  • visual profiler
    • prototype version for Linux and Windows
• Professor Partnership Program
  • support faculty research & teaching efforts - informal proposals
    • Easy
      • small equipment gifts -> 1-2 GPUs
      • discounts, cost-matching
    • Competitive
      • research contracts
      • small cash grants ~$25k
      • medium-scale equipment donations -> 10-30 GPUs

---

Round Table Discussion

• Activity within GPU community - http://gpgpu.org (more than just NVidia), CUDA GPU Forum
• Interest from Microsoft in running C# applications on GPUs, e.g. Excel
• Lots of interest in common middleware to hide CUDA from casual programmers, something like MPI

---

Late Breaking News

• http://ecommerce.pny.com, coupon "SC07" (40%-50% MSRP, Tesla Products)
• http://www.sun.com/ultra24, coupon "SC07_Ultra24" (20% off MSRP, Sun Ultra24)