Physics
ComputerScience,1970-2008-Computer Science-2007.jsonl.gz.gz
Computer Science
b05a232326f66da8e5bea3cfb9b6d95d44a9bf95
Towards multi-GPU support for visualization

At the Institute for Ultrascale Visualization, we are tackling the broad problem of building visualization solutions for the petascale age and beyond. As computing transitions into a new age where scalar solutions no longer improve in performance, and parallel solutions are the vehicle for future performance gains, one key challenge in our effort is to harness the power of emerging commodity data-parallel processors. One of the most promising new parallel processors is the graphics processing unit (GPU), whose recent gains in programmability and enormous arithmetic and memory bandwidth substantially outpace its CPU counterpart. The GPU's performance and programmability, together with its graphics capabilities, make it particularly well suited for demanding next-generation visualization applications. We face a number of important challenges in making the GPU a first-class citizen for computation in these visualization applications. In this paper, we describe how we are addressing these challenges: mapping GPUs to general-purpose tasks, fundamental algorithms for GPUs, visualization applications that use the GPU for general-purpose computation, and extending our applications to support multiple GPUs. We also describe trends in upcoming GPU designs and how they will impact our research moving forward.


Introduction
Ten years ago, the conventional wisdom held that the scalar microprocessor was the future of computation. Driven by smaller, faster transistors, and increasing transistor counts, microprocessors doubled in performance every 18-20 months, with an annual performance growth increase of over 50% [1]. Even the Top500 list of supercomputers, traditionally the domain of specialized parallel processors, gradually shifted towards machines whose cores were commodity scalar microprocessors.
Today, the picture has changed. The future of computation is parallel processing. Future microprocessors, due to thermal and architectural constraints, will no longer demonstrate increases in the performance of a single thread of execution. Instead, future processors will increase performance solely by exploiting data-and thread-level parallelism. This monumental shift in focus-Intel CEO Paul Otellini called it a "sea change in computing"-fundamentally changes the way we must think about computation going forward.
At the SciDAC Institute for Ultrascale Visualization (IUSV), we are targeting two of the largest challenges in computing today. The first challenge is the "too much data" problem: the computational demands of science and engineering produces an ever-increasing flood of data that only sophisticated data analysis methods-such as large-scale visualization-can handle. With big data comes big computation, and the second challenge is restructuring that computation dual-core quadcore Figure 1. Because of the parallel nature of computer graphics, the GPU has always been a highly parallel machine. The most recent NVIDIA GPU, for instance, features 128 parallel processors. With this parallelism, modern GPUs feature substantially larger floating-point performance than their CPU counterparts. GPU memory systems also sustain bandwidths of over 80 GB/s, while CPU memory systems are closer to 10 GB/s. for this new parallel age. While scalar algorithms continue to evolve over time, only parallel algorithms that match the capabilities of emerging parallel computer systems can match the rate at which data is generated. It is this challenge of parallelism that is the focus of this paper. At IUSV, we are pursuing a research agenda to make the high-performance, highly parallel graphics processing unit (GPU) an integral part of our petascale visualization solutions.

GPU Computing
The commodity GPU is a youngster in the family tree of processors. GPUs only entered the computing mainstream around 1995. At first, the GPU was best described as a fixed-function processor, but in 2001, it began to feature stages that were directly programmable by the user. These programmable stages were initially fairly limited in functionality but, motivated by the need for more flexible shading and lighting in graphics applications, rapidly gained both features and performance. Today's GPU is no longer a fixed-function processor with programmable stages. It has instead transmuted into a programmable processor with several fixed-function components. The programmable parts of the GPU are now the most important components in GPU performance and functionality, and are the primary focus of continued architectural innovation by GPU vendors.
With these new programmable features, researchers in the field of general-purpose programmability of GPUs (GPGPU), also known as GPU computing, have successfully mapped a broad range of computationally demanding problems to the GPU [2]. How does the GPU, a processor designed for graphics, perform non-graphics, general-purpose computation? Historically this has been a convoluted task: researchers would specify geometry that covered a large portion of the screen, which would then invoke a programmable pixel program at each pixel, and the resulting image held the result (and could be used in future computation). (Harris describes this process in detail [3].) This process was awkward because it used graphics metaphors and APIs to perform non-graphics computation. However, the newest programming environments/APIs-NVIDIA's CUDA [4] ("compute unified device architecture") and AMD's CTM [5] ("close to the metal") allow developers to access the programmable units directly without the need to go through graphics APIs or special-purpose graphics hardware. CUDA provides a C-like language and a compute driver to access the programmable units; CTM exposes lower-level memory accesses and CPU-GPU transfer control operations; both greatly ease the difficulty of writing, debugging, and optimizing GPU programs for general-purpose use.
So why GPU computing? In a word, performance ( Figure 1). For problems well-suited to the GPU, researchers in GPU computing have found order-of-magnitude or greater increases in performance over CPU implementations. For instance, a GPU implementation of the NAMD molecular dynamics package achieves a 20-fold speedup over a highly tuned CPU implementation [6]. Large-scale visualization is an ideal fit for GPU computing for several reasons: • Visualization is a data-intensive application, particularly as the problem size increases into the petascale. GPUs are well-suited for data-intensive tasks. • Visualization computations exhibit substantial parallelism, typically both object parallelism (many objects or parts of objects can be computed/viewed in parallel) and image parallelism (visualizations produce large images and image parts can be computed/viewed in parallel). Parallel computations are necessary for GPUs to be effective. • Visualization tasks should be closely coupled to the graphics system; even though much of overall visualization computation may not be graphics-centric, the final stage typically is, and so moving computation closer to the graphics device offers potential benefits in terms of interactivity and computational steering. • Finally, GPUs can offload computation from CPUs, permitting the entire application to run faster when GPUs are involved.

Fundamental primitives for GPUs
In developing code for CPUs, programmers often have access to a wealth of abstractions, tools, and libraries. For instance, a developer may incorporate linear algebra packages (like BLAS or ATLAS), visualization toolkits (like vtk), and data structure and algorithm libraries (like STL or Boost) into a particular application. The developer is responsible for stitching these parts into an application, but in any given application, the developer only writes a small fraction of the code. This is a "horizontal" method of program development, with the lower layers of abstraction already present in most CPU codes.
One of the major difficulties in programming GPUs is the lack of these established abstractions, tools, and libraries. Consequently GPU programmers are forced to use a more "vertical" model of development, where the application programmer must write all levels of the application. Code reuse is rare and productivity is thus low.
One of our main goals at IUSV is to support large-scale visualization applications by creating libraries of fundamental primitives-algorithms and data structures-to enable modular programs and more productive programmers. We are fortunate to have experts on both low-level GPU programming (who can write efficient, portable parallel primitives) and visualization (who can guide the choice of primitives for best use by visualization).
We have begun our efforts in this area by concentrating on the lowest level of GPU primitives and will build layers and libraries of primitives over the course of the next few years. Our notable initial success is a successful implementation of the scan primitives on GPUs [7,8], which in turn has led to efficient and novel implementations of GPU sorting, sparse matrix operations, depth of field calculations, and fluid simulation.
To leverage our parallel primitive development, we are concurrently pursuing two major research goals. The first is the integration of GPU computation in visualization applications. The second is extending single-GPU applications to multiple GPUs.

Applications
The emergence of parallel hardware will force application developers of all kinds to rethink the way in which they structure their programs. While some of these changes are more evolutionary (threading in multicore machines), moving to the massive parallelism of the GPU implies more substantial changes. One of our primary research goals is to solve complex, compute-heavy visualization applications using GPU computing and with those lessons, better learn how to use the GPU as a computing engine in these future systems. One fertile area for research is migrating demanding general-purpose tasks to the GPU. For instance, sorting large datasets is a common operation in visualization applications. The GPU's superior memory bandwidth and arithmetic capability make it well-suited to large sorting tasks [9]. Robert Hero and Professor Kwan-Liu Ma at IUSV are using GPU-based sorts in CUDA to accelerate unstructured-grid visualizations, in which cells must be sorted by distance from the eye.
A second research thrust is leveraging the special-purpose hardware of the GPU for visualization tasks. At IUSV, Eric Lengyel and Professor Nelson Max are using floating-point compositing GPU hardware to blend partially transparent samples together for a final image.
Finally, a third focus for our research is directly building GPU implementations of visualization primitives, with a long-term goal of building a library of open-source, GPUaccelerated primitives. For instance, GPU primitives for compaction [10] are a key component of visualization primitives such as isosurface extraction. At IUSV, Yuan Hong, Liya Li, and Processor Han-Wei Shen are pursuing GPU implementations of both marching cubes and raycasting, both important primitives for a broad class of visualization applications.

Multi-GPU support
We also are pursuing a research program to extend our single-GPU primitives to multiple GPUs in a multi-node system. As our primary interest in IUSV is petascale visualization, clustered systems with many GPUs are a must.
Multi-node GPU computing is still in its infancy-with many open research problems with single-node GPUs, multi-node vendor support has been a tricky task. Successful multi-GPU applications have traditionally taken two forms. The first is parallelizable problems that can be partitioned between GPUs. In these problems, the input is divided into parts and each part is sent to a separate GPU. The second is a pipeline, where each GPU executes part of the pipeline and forwards its results to the next GPU in the pipeline.
While many interesting problems may be well suited for one of these communication patterns, neither allows fully general communication. Instead, the communication patterns for both are essentially fixed at the outset of the program. We see two potential more flexible models for computation in an ideal system.
In the first, the GPUs are the primary processors: GPUs can share memory dynamically, and any GPU can request arbitrary data from any other GPU at any time. We advocate, and have built, a distributed-shared memory abstraction across multiple GPUs [11]. With this abstraction, each GPU's memory is part of a global memory space, and any GPU can request memory from any part of that global memory space at any time without knowing the details of where that memory is located in the system. Such a system can be made scalable. Our current implementation assumes one GPU per CPU but can be extended to have multiple GPUs per CPU. It is functional but not suitable for performance-critical applications; however, the necessary vendor support for making such a system efficient, such as per-element demand paging and more fine-grained memory management, is on vendor roadmaps and will allow highperformance implementations over the next few years.
In the second, GPUs are treated as coprocessors and CPUs are primarily responsible for scheduling and distributing work with them. In conjunction with Brian Budge and Professor Ken Joy (VACET), we are pursuing a hybrid out-of-core rendering solution that efficiently distributes work across multiple nodes and processors on those nodes to render large complex scenes with sophisticated shading. The lessons learned-how to distribute work and what kind of work is best suited for GPUs-are directly applicable to complex visualization applications.
Regardless of the eventual model for arbitrary memory sharing across multiple GPUs, the broad research problem of the design of multi-node memory models-balancing generality with performance, programmer efficiency with runtime efficiency-is a vital one for not only GPUs but also emerging parallel CPUs and hybrid CPU-GPU clusters.

Looking Forward
Both GPU vendors and application developers with demanding computation needs are embracing GPU computing as a first-class computing resource in tomorrow's systems. Perhaps the most important challenge is the development of a programming ecosystem around the GPU; two important aspects of such an ecosystem are the development of fundamental primitives and an efficient, powerful programming abstraction built around multiple GPUs that we describe above. Beyond these components are a strong need for programming tools (compilers, emulators, debuggers, and profilers) and abstractions (programming models, libraries, and APIs). These problems are not unique to the GPU but instead are important to all aspects of parallel programming, whether coarse-grained thread-parallel systems (like a multicore CPU) or finegrained data-parallel systems (like a GPU). The development of vendor-supported general-purpose programming environments like CUDA and CTM are vital to the continued development of GPU computing. Over the next few years we will see further vendor improvements that will continue to improve the prospects of GPU computing. For instance, both AMD and NVIDIA have announced that their GPUs will support double-precision arithmetic by the end of 2007, eliminating a major obstacle to their adoption in scientific computing. The next generation of device drivers (Windows Driver Device Model 2.1) will add more fine-grained memory and exception control, which will lead to more efficient multi-GPU shared-memory implementations. And an increased vendor focus on GPU computing in general-evidenced by boards and products that are designed and built specifically for GPU computing-paints a bright picture.
As one of the most complex and demanding applications, visualization is perfectly positioned to take advantage of the power of GPU computing. Visualization is a critical step in the processing of data into knowledge, and the high computational demands of visualization applications coupled with their real-time requirements make it imperative that as we move into the petascale and beyond, we use GPU computing and other innovative computing approaches to best support these applications.