Advanced Architectures for Astrophysical Supercomputing
Benjamin Barsdell (bbarsdel@astro.swin.edu.au), David Barnes, Christopher Fluke
Swinburne Centre for Astrophysics & SupercomputingThis research is supported
under the Australian ResearchCouncil's Discovery
funding scheme (DP0665574).

Melbourne, Australia

Abstract

Astronomers have come to rely on the increasing performance of computers to reduce, analyse, simulate and visualise their data. The recent transition from increasing clock rate to increasing core countin CPUs has seen Moore’s Law maintained, but at the cost of a paradigm shift from serial to parallel processing. Current generation graphics processing units (GPUs) reflect the situation well: their massively
parallel architecture provides orders of magnitude more raw processing power than current CPUs, but present a new and foreign programming model. While efforts to port a number of astronomy
algorithms to GPUs have been successful in obtaining significant speed-ups (frequently 100x over CPUs), the approaches so far have been somewhat "ad-hoc" in nature.
Here we motivate an "algorithm analysis" approach to the use of GPUs and other advanced architectures in astronomy. Such an approach will identify the expected performance and scaling ofastronomy algorithms on new hardware architectures prior to implementation. The current direction of computer architecture development suggests that an understanding of our algorithms will be of great
importance to the future of computational astronomy.

The Future of Computing

Motivation: From Video Games to Science

Past

Modern astronomy has come to rely heavily
on high-performance computing (HPC).
However, all research areas are facing
significant challenges as data volumes
approach petabyte levels. The AustralianSquare Kilometre Array Pathfinder project for
instance will produce data at a rate thatmakes storage in raw form impractical,
necessitating on-the-fly reduction andanalysis to produce 4GB/s of products. On
the modeling front, there is an ongoing
desire for larger and more-detailed
simulations, and particle counts haveexceeded 1010 (e.g., the Millennium
simulation by Springel et al. 2005).
The HPC scene has recently witnessed the bold introduction of
the GPU as a viable and powerful general-purpose coprocessor to CPUs. GPUs were developed to off-load thecomputations involved in 3D graphics rendering from theCPU, primarily to the benefit of video-games. Their continued
development has been driven by the $60 billion/year videogames industry, the result of which is seen in Figure 1.
Along with rapidly-increasing performance, GPUs haveundergone a shift from containing special-function processors
to instead being composed of flexible general-purposeprocessors. This, combined with the availability of generalpurpose GPU programming tools, has opened up GPU
computation to a wide range of non-graphics-related tasks,
notably in the area of HPC.

The power of many-core architectures likeGPUs, if harnessed, could lead to significant
speed-ups in computational astronomy andpotentially to new science outcomes.

Present…

CPU:

GPU:

Future…

…

Figure 2. The direction of CPU architecture development and thecurrent state of GPU architecture. Boxes represent processor cores.

Figure1. Clock-rate versus core-count phase space of Moore’s Law. The
classical Moore’s Law trend is seen in the approximately equi-spaced black
dots at 1 on the vertical axis. The paradigm shift from increasing clock-rates
to increasing core-count is seen as a sharp turn at a clock-rate of around
3Ghz. This “multi-core corner” presents significant challenges to thecomputational astrophysics community. Recent GPUs appear beyond theturn, and represent a likely direction for future CPUs.

General-purpose GPU (GPGPU) computing brings a number ofsignificant benefits to HPC:
Monetary cost

CPUGPU$105/Tflop/s$104/Tflop/s

Environmental cost 0.5 Gflop/s/watt 4 Gflop/s/watt
Desktop supercomputing

10 Gflop/s

1000 Gflop/s

Note: flop/s = floating-point operations per second

Figure 2 depicts the recent evolution of CPU architectureand compares it to the current state of GPU architecture.
Prior to 2005, developments in CPU performance camelargely from increasing clock-speeds. Since then, hardware
issues have forced manufacturers to turn to multi-corearchitectures. We have thus seen a shift from single-coreprocessors to dual-core and then to quad-core CPUs (and8-core CPUs have recently been announced). Looking at it
this way, it becomes obvious that if CPU performance is tocontinue to increase, the number of cores must continue torise, and CPUs will almost inevitably move to a many-corearchitecture.
The significance of the GPU is that GPUs already havemany-core architectures. They thus present us with themotivation and opportunity to study how our astronomy
codes will perform and scale on many-core architecturesin the future.
Both the immediate performance boost provided by GPUs
and the expected future of CPU computing provide strong
motivation for a thorough analysis of the performance andscalability of our astrophysics algorithms in advanced
parallel processing environments.

GPU Use in Astronomy to Date
A small number of astronomy algorithms have been
implemented on GPUs to date, including:Rules of Thumb

The Algorithms of Astronomy

Here are some of the issues that are important when considering aGPU implementation of an algorithm (Barsdell et al., in prep):

Here we present an initial classification of astronomy algorithms
based on application of the “rules of thumb” and known GPUefficient algorithms (Barsdell et al., in prep):•Direct N-body simulations (e.g., Hamada & Iitaka 2007)•Simulation

Massive parallelism• Radio-telescope signal correlation (e.g., Harris, Haines &Staveley-Smith 2008)•The solution of Kepler’s equation (Ford 2008)•Having enough parallel granularity to use all of
the available hardware parallelism•Direct N-body simulations•Tree-code N-body simulations / SPH

High, O(100x)•Current GPUs hit peak at O(104) threads•Halo finding

Moderate, O(10x)•Fixed-resolution mesh simulations

Untested•Gravitational lensing ray-tracing (Thompson et al. 2010)•Phase-space study of post-Newtonian binary black holeinspirals (Herrmann et al. 2009)

Memory access locality and patterns•3D Cartesian shapelets (Fluke et al., in preparation)•Pulsar signal processing

All have reported speed-ups of O(100) over CPU
implementations. However, these algorithms are for the mostpart “embarrassingly parallel” “low-hanging fruits”, meaningthat they can be run on a parallel processing architecturewith little to no overhead. This makes them obvious
candidates for efficient GPU implementation. The questionthat remains is: Exactly which classes of astronomy
algorithms are likely to obtain significant speed-ups byrunning on advanced architectures?

2. Developing an algorithm analysis methodology relevant
to new hardware architectures
We believe that such an approach will minimise the effort
required to turn the “multi-core corner” for computational
astronomy and ensure that the solutions found will continue
to scale with future advances in technology.

•Adaptive mesh refinement•Read collisions are bad, write collisions arereally bad•Gravitational lensing ray-shooting•Semi-analytic modelling•Other Monte-Carlo methods•Data reduction•Should be minimised•Pulsar signal (coherent) dedispersion•At least aim for locality in branch paths•Radio-telescope signal correlation•Image processing

Computation / memory operation ratio•Arithmetic instructions generally much fasterthan memory operations•Increasing arithmetic intensity hides memory
latencies

We propose a generalised approach based around two keyideas:

1. Building and using a taxonomy of astronomy algorithms•Locality and alignment strongly impact
bandwidthBranching

Our Approach

CPUHostGPUPrecision

Efficiency, speed-up
on GPUs+-x÷I/ODevice memory transfers•Optical data reduction•Flat-fielding etc.

•Stacking / mosaicing (e.g., DRIZZLE)•Source extraction•Convolution and de-convolution•Bandwidth is O(10x) less than within device memory•CLEAN algorithm•Minimise transfers by implementing as much of thealgorithm as possible on the GPU•Gridding of visibilities and single-dish data
•Data analysis

3.1415926535897932...

•Data mining•Single-precision FLOPs can be (significantly) more than 2x fasterthan double-precision•Often worth the effort to assess whether and where doubleprecision is necessary
References
Springel, V. et al., 2005, Nature, 435, 629-636
Hamada, T., Iitaka, T. 2007, arXiv:astro-ph/0703100v1Harris, C., Haines, K., Staveley-Smith, L. 2008, ExA, 22, 129
Ford, E.B. 2008, NewA, 14, 406
Thompson, A.C., Fluke, C.J., Barnes, D.G., Barsdell, B.R. 2010, NewA, 15, 1, 16-23
Herrmann, F., Silberholz, J., Bellone, M., Guerberoff, G., Tiglio, M., 2009,arXiv:0908.3889v2 [gr-qc]•Selection based on criteria matching•Machine learning

We conclude that the data-richnature of computational astronomy•Fitting / optimisation
combined with the efficiency of data•Numerical integration parallel algorithms on current GPU
hardware make for a very promising•Volume rendering
relationship with current and future
massively-parallel architectures.
Processors are likely to become even more flexible in the future,potentially improving the efficiency of many astronomy algorithms
and opening up new avenues to significant speed-ups.

Conclusions
Modern astronomy relies heavily on HPC, and GPUs can provide both significant speed-ups over current CPUs and a glimpse of the probable future ofcommodity computing architectures. However, their more complex design means algorithms must be considered carefully if they are to run efficiently onthese advanced architectures. There is therefore strong motivation to thoroughly analyse and categorise the algorithms of astronomy in order to take fulladvantage of current and future advanced computing architectures and maximise our science outcomes.