Ronald Reagan Building and International Trade Center
Washington, D.C.
September 9-11, 2003
Seminars
Reconfigurable Computing: FPGA-Based, General Purpose, High Performance Systems. (6 hours, full day).
Extended Abstract
Introduction
Reconfigurable computing exploits high degrees of parallelism and bit-level optimizations found in custom hardware implementations to achieve high processing speeds. Yet, it retains the aspects of a general-purpose programmable computer because applications can be downloaded into FPGA devices on the order of tens of milliseconds. Although many early reconfigurable computers were expensive complicated monolithic FPGA arrays, most modern commercial and research systems have evolved into relatively less expensive PCI workstation accelerators. Furthermore, FPGA based components have been moving into the mainstream of supercomputing. In recent efforts, high-performance computing vendors have been either considering the use of FPGA based hardware to establish their fixed point arithmetic units or for establishing stand alone parallel computers of reconfigurable and conventional computing units. Research efforts in academic institutions have been also been considering the establishment and management of parallel reconfigurable computing clusters and high-throughput networks of reconfigurable computers (NORCs). All these individual efforts are creating a new direction, namely reconfigurable supercomputing, which should be recognized and treated as such. This tutorial contributes to that direction, by bringing together a group of experts that have researched and contributed to the different sides of this technology revolution to provide an integrated view to this new area. We will start our coverage with reconfigurable computing technology and systems. Then we will overview reconfigurable compiling technology which can allow the linkage between programs and this new class of hardware. We will complete the picture with a discussion of tools that can hide engineering details from reconfigurable applications developers. WE then proceed to examine applications that can excel on such systems with special attention to cryptography and image processing.
Technology and Systems
In the technology and systems area, we start by presenting the structural and operational characteristics of FPGAs that make them different from conventional hardware. We do this at a high-level suited to students and IT professionals who are not specialized in engineering. We proceed to derive the challenges for this technology and set the stage for the rest of the segments of our coverage. We next cover the architecture of a number of reconfigurable accelerator boards, with emphasis on PCI based boards. This will include generic board architecture and operations as well as example boards such as the SLAAC-1v, from USC/ISI, and WildeFORCE and Firebird from Annapolis MicroSystems. Networks of Reconfigurable Computers systems (NORCs), such as the extended LSF system, from GWU/GMU in collaboration with platform computing, will be covered. Parallel reconfigurable clusters efforts will be surveyed. In addition complete systems and research efforts towards the development of reconfigurable supercomputers will be overviewed specially those from SRC, Starbridge, and research consortia.
Compiler Technology
Reconfigurable systems present a formidable challenge in terms of algorithm design tools. Design tools for FPGA devices, the building blocks of reconfigurable hardware, are oriented towards ASIC development environments, in which digital design engineers create large (multi-million gate), complex designs that once created and validated, do not change. In contrast, reconfigurable supercomputers require a more software-centric development environment, in which algorithms are constantly revised and tested. In response to the need for software-oriented tools, vendors and researchers have developed compilers for software programming languages that synthesize hardware. Compilers for several C variants, Java, and Matlab have become available in the past couple of years. In this section of the tutorial, we will review both commercially available compilers as well as research efforts. We will compare the language variants supported (all of these compilers define synthesizable subsets of the language), the design tool flow, and the target reconfigurable hardware. We will discuss trade-offs between compiler-based and "native" approaches for reconfigurable supercomputing.
Tools
It is natural to wish to program reconfigurable elements in a traditional style and indeed the previous section updates on traditional (and not so traditional) compiler techniques for FPGA based systems. However, flexible hardware enables flexible problem specification that may not best be represented in a Von Neumann oriented programming style. Here we familiarize supercomputing practitioners with high-level, dataflow programming languages that include a visual programming interface and library suites enabling rapid program development targeting reconfigurable resources such as FPGAs. Vivaä is a high-level graphical language that allows FPGAs to be programmed very easily. We start with an introduction to the look, feel, and capabilities of Vivaä . Then learn how to construct Vivaä objects, construct CONSTRUCTING_VIVA_OBJECTSbehavior sheets, convert behavior sheets to objects and construct polymorphic types. We go on to consider input and output (sometimes the trickiest part as well as the performance bottleneck for FPGA devices). Then learn how to construct system object trees, vectors and dynamic data sets. Finally complete the picture to consider FPGA implementations including system polymorphism, forcing GateWare allocation, obtaining information rates, and implementing control nodes. CoreFireä is a tool similar to Vivaä allowing users to program FPGA-based boards by drawing dataflow diagrams. CoreFireä completely replaces a VHDL-based design flow that previously included simulation and synthesis. We will learn how to build designs for FPGAs using CoreFireä by working from high level, data flow concepts of the design. We will see how to combine GUI design entry and debug tools with CoreFireä cores.
Applications
Reconfigurable computers are known to excel in many applications. Among those are cryptography, image processing, and computational biology. In this tutorial, we demonstrate via several examples the suitability of these applications for reconfigurable computing as well as how to develop efficient solutions for such applications on recofigurable platforms.
Computations in cryptography are generally ill suited to conventional computers. NIST has proposed standard curves for elliptic curve cryptography as well as the new Advanced Encryption Standard (AES). At the heart of elliptic curve cryptography, for example, are arithmetic operations either with multiprecise integer arithmetic or with binary finite field arithmetic several hundred bits in length. We will begin in this section by describing the operations underlying these computations--the Instruction Set Architecture, as it were, that would permit these computations to be executed efficiently. We will then describe a library framework for supporting these kernel operations on reconfigurable hardware. Libraries such as those for linear algebra have been a fundamental part of the use of high performance computers for many years. In the case of these particular cryptographic applications, the functions to be encapsulated into libraries are well understood, and the analogy with Linpack is very apt. We will illustrate the general library framework with a particular example, using the Star Bridge Systems reconfigurable computing platform as an example. We will also discuss some of the work done in applying reconfigurable computing to image processing problems. At the heart of any particular application is the balance between "CPU" usage and data movement. Using this application as a motivating example, we will describe methods for balancing these two parts of the computational process. Finally, we will extrapolate from known needs and current extant hardware to describe the intellectual path that must be traveled to make reconfigurable computing part of the normal means for achieving high performance on critical compute-intensive applications. In addition to cryptography, some computational biology problems are considered. At least two standard problems in computational biology are amenable to an attack using reconfigurable hardware. Many computations in statistical phylogenetics consist of tree searches with an objective function to be optimized. Under suitable versions of these problems, the tree enumeration can be done much as with a Gray code, the computation is inherently parallel (albeit with some synchronization necessary of the current best value of the objective function), and the computations are sufficiently simple to be computable on a reconfigurable platform.
A second problem of this type is in the processing of microarray data. This kind of image processing, clustering, and classification problem is also inherently parallel and has been attacked with neural nets and similar methods. Once again, the problem is parallel and amenable to hardware implementation on reconfigurable systems as we will be showing.
Home - NASA Office of Logic Design
Last Revised: March 06, 2003
Digital Engineering Institute
Web Grunt: Richard Katz
