Developing and Deploying Advanced Algorithms to Novel Supercomputing Hardware

Róbert Brunner, Volodymyr Kindratenko, Adam D. MyersarXiv 2007 · DOI · arXiv

Abstract

As traditional CPU performance scaling faces physical limitations in power consumption and heat dissipation, high-performance computing (HPC) must look toward alternative architectures. This research demonstrates the practical application and significant performance gains achieved by porting complex scientific algorithms to reconfigurable hardware. By utilizing Field-Programmable Gate Arrays (FPGAs), we achieved nearly two orders of magnitude speedup for cosmological calculations. This work serves as both a performance benchmark and a guide for non-specialists to navigate the development barriers associated with novel hardware platforms.

Introduction

For decades, the scientific community relied on the steady advancement of Moore’s Law to meet increasing computational demands. However, the transition from faster raw clock speeds to multi-core designs has created a bottleneck for many legacy algorithms. Specialized hardware, such as FPGAs, Graphics Processing Units (GPUs), and the STI Cell BE platform, offers a potential solution. Despite their power, the primary barrier to widespread adoption remains a lack of accessible development tools and documented case studies. In partnership with the Innovative Systems Laboratory at the National Center for Supercomputing (NCSA), we explored the efficacy of several reconfigurable computing platforms, specifically the SRC-6 MAP-C/E and the SGI RASC RC100, to accelerate fundamental scientific computations.

The Computational Challenge: TPACF

Our research focuses on the Two-Point Angular Correlation Function (TPACF), a cornerstone of cosmology used to measure the clustering of galaxies and quasars. The TPACF is computationally intensive, scaling at $O(N^2)$. As modern datasets grow to include millions of objects, the time required for these calculations on traditional CPUs becomes prohibitive.

To evaluate performance, we utilized a dataset of 97,178 photometrically classified quasars. The algorithm compares this real-world data against 100 different "random" catalogs of equivalent size to determine the correlation across 30 logarithmic bins. This brute-force approach provides a rigorous test for the parallel processing capabilities of reconfigurable hardware.

Methodology and Hardware Implementation

Unlike standard CPUs that execute instructions sequentially, FPGAs allow researchers to "wire" an algorithm directly into the hardware circuitry. We employed several strategies to optimize the TPACF for these platforms:

  • High-Level Synthesis: To bridge the gap between scientific programming and hardware design, we used C-like languages (MAP C and Mitrion-C) rather than traditional hardware description languages like Verilog.
  • Loop Unrolling and Pipelining: Because FPGAs struggle with the branching logic of standard binary searches, we unrolled these searches into parallel "if-else" statements. This allowed the hardware to produce a new result on every clock cycle, maintaining a deep, uninterrupted pipeline.
  • Custom Numerical Precision: A key innovation was the move away from standard 64-bit double-precision floats. By determining that the science only required a custom 41-bit mantissa (12 decimal digits of precision), we reduced the physical space required on the FPGA by 27%, allowing for more compute engines to be placed on a single chip.
  • Hybrid Parallelism: We implemented a task-level approach where the host CPU managed data loading via OpenMP while coordinating multiple FPGA "tiles" simultaneously.

Results and Performance

The transition to reconfigurable hardware yielded dramatic performance improvements over traditional CPU architectures:

  1. SRC-6 Platform: The single-processor FPGA system achieved a 96x speedup compared to a 2.8 GHz Intel Xeon processor. By fitting four simultaneous distance-calculation cores per chip, the execution time was reduced proportionally to the number of cores.
  2. SGI RASC RC100: This platform achieved a 25x speedup over a 1.4 GHz Intel Itanium 2 processor.

While the FPGAs operated at significantly lower clock speeds (100–200 MHz) than their CPU counterparts, their architectural efficiency and massive parallelism allowed them to bypass the limitations of traditional serial processing.

Conclusion and Future Work

Our findings demonstrate that FPGAs can provide the necessary computational power to handle the next generation of astronomical datasets. However, the development barrier remains high; porting these algorithms requires a nuanced understanding of hardware architecture.

Future research will focus on expanding these implementations to NVIDIA GPUs and the STI Cell BE platform. Additionally, we aim to move beyond brute-force $O(N^2)$ calculations by implementing tree-based data structures to further optimize the correlation functions. Finally, we are exploring the application of these hardware acceleration techniques to other domains, including instance-based classifiers and power spectrum estimators, to provide a broader suite of tools for the scientific community.

Summary updated

Abstract

The objective of our research is to demonstrate the practical usage and orders of magnitude speedup of real-world applications by using alternative technologies to support high performance computing. Currently, the main barrier to the widespread adoption of this technology is the lack of development tools and case studies that typically impede non-specialists that might otherwise develop applications that could leverage these technologies. By partnering with the Innovative Systems Laboratory at the National Center for Supercomputing, we have obtained access to several novel technologies, including several Field-Programmable Gate Array (FPGA) systems, NVidia Graphics Processing Units (GPUs), and the STI Cell BE platform. Our goal is to not only demonstrate the capabilities of these systems, but to also serve as guides for others to follow in our path. To date, we have explored the efficacy of the SRC-6 MAP-C and MAP-E and SGI RASC Athena and RC100 reconfigurable computing platforms in supporting a two-point correlation function which is used in a number of different scientific domains. In a brute force test, the FPGA based single-processor system has achieved an almost two orders of magnitude speedup over a single-processor CPU system. We are now developing implementations of this algorithm on other platforms, including one using a GPU. Given the considerable efforts of the cosmology community in optimizing these classes of algorithms, we are currently working to implement an optimized version of the basic family of correlation functions by using tree-based data structures. Finally, we are also exploring other algorithms, such as instance-based classifiers, power spectrum estimators, and higher-order correlation functions that are also commonly used in a wide range of scientific disciplines.
BibTeX
@misc{brunner2007developing,
  author = {Róbert Brunner and Volodymyr Kindratenko and Adam D. Myers},
  title = {{Developing and Deploying Advanced Algorithms to Novel Supercomputing Hardware}},
  year = {2007},
  eprint = {0711.3414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0711.3414},
  howpublished = {arXiv},
}

Loading related content...

Figure