Introduction

Not all applications are suitable for an RCM. Applications that involve extensive recursion, for example, are a poor match because the synthesized "hardware" must be of fixed size. But with many applications, including image and signal processing and biological sequence comparison, orders of magnitude speedup can be obtained. This is because hardware execution is inherently parallel, because the overhead of the fetch-decode-execute cycle is eliminated, and because the "CPU" can be custom-designed to accommodate computations not normally supported by instruction set architectures.

There are presently two primary problems in reconfigurable computing. The first is to demonstrate that there is a sufficient range of problems on which one can get a factor of 50 to 100 speedup by using a reconfigurable machine and thus to justify the development of reconfigurable hardware instead of simply following existing technology curves. The second problem is to demonstrate that this speedup can be obtained by a process that can be described as "programming" and not as "hardware design."

Previous funded work at USC included attempts to implement relevant complete algorithms on hardware from Star Bridge Systems. Following the conclusion of that phase of the work, our attention was shifted to the SRC-6 manufactured and sold by SRC Computers, Inc.. These two represent the only extant systems of significant size that are currently available from commercial vendors, although. SGI and Cray are in the process of releasing hardware.

Our current focus is on the DARPA HPCS Discrete Mathematics Benchmarks, most of which are highly amenable to a solution on an RCM. In addition, we are looking at bioinformatics, molecular dynamics, and error-correcting codes as secondary topic areas.

News

Related courses in VLSI

• CSCE 611 -- VLSI Systems Architecture & Design
• CSCE 612 -- HDL-based Design for VLSI Systems
• CSCE 613 -- Fundamentals of CMOS VLSI Design
• CSCE 818 -- Low-Power VLSI Design
• CSCE 819 -- Hardware-Software Co-design for Embedded Systems

DARPA HPCS Discrete Math Benchmarks

The research team, Fall 2004.

FCCM 2005

High-Performance Secure Computing

The HC-36m® RCM platform.

Some of the problems associated with this endeavor include the following: (1) algorithm analysis - to determine the most appropriate architecture to place the computationally-intensive portions of the application on the reconfigurable platform; (2) architecture development - to assess and empirically evaluate different architecture alternatives, which generally involves trading-off the computational throughput of the portion of the architecture executing on the reconfigurable custom computing engine with the communications overhead associated with a given partitioning scheme.

The HC-36m® RCM platform.

See this link for a description of the research results to date, and check out the latest publications we're working on relative to the architecture modeling for realizing elliptic curve cryptography on reconfigurable platforms.

Bioinformatics

Current projects underway include the re-architecting and re-implementation of Phylogenetics algorithms onto RCM platforms.  One such project involves the development of an accelerated version of the UPGMA algorithm for determining the taxa distance in Phylogenetic trees.  Software algorithms exist for this technique, and these have been highly optimized in software for execution on a conventional computer.  However, as the number of species taxa grows large, meaning that the corresponding data sets grow large as well, existing techniques don't scale well.  

Therefore, we are investigating methods for improving the data throughput for large amounts of data collected through genetic analysis of species, so that the overall computation time can be by one to two orders of magnitude.  This means Biologists and Statisticians involved in the analysis of species' genomic data sets can get processing results much faster than would ordinarily be possible.  In addition to the UPGMA approach, other techniques, such as Least Squares and Parsimony, are being explored and will be exploited for high-performance execution on a parallel processing RCM platform.

Reconfigurable Computing for Wireless Mobile Applications

Whereas most of the problems we are looking at in Scientific computing have a large data path component, the problem of RCM in wireless mobile computing is one that is more control dominated--requiring many parallel state machines that share data paths and communicate, synchronize and coordinate with one another.  These are very useful for design of protocols and control-oriented algorithms.  We seek to manage complexity of these protocols and algorithms by adopting architectures that use a lot of smaller, concurrent state machines.  We see the use of RCM techniques, employing a much higher degree of custom logic content in wireless systems solution, as an alternative to the predominant embedded systems and SoC methods of delivering feature content in appropriate mobile device "footprints".  Issues such as energy management, performance throughput and cost will provide the catalyst for realizing tetherless products on a custom logic substrate.  The use of the RCM paradigm will enable such applications to be created that better exploit the power of VLSI custom logic, while also gaining the advantages of dynamic reconfigurability of the VLSI platform for multiple applications--a benefit of software-based systems that is now available to VLSI hardware.

As wireless networks become large, there are a number of scaling problems which need to be addressed.  Wireless LANs are becoming a means for communities of users to set up ad-hoc networks, to offer commercial services (such as access to the Internet for wireless laptops and PDAs) or provide support for military operations (such as through wireless sensor networks).  Operating using unregulated frequencies in the 2.5 GHZ and 5 GHZ frequency bands, wireless LANs using the IEEE 802.11 protocol family are deceptively easy to set up and manage.  However, there are a number of security, traffic congestion management and resource management issues that need to be addressed if wireless networks based in 802.11 protocol are to become and integral part of the Internet fabric and infrastructure.

We are looking to apply principles of adaptive, self-organizing systems to this problem.  Wireless  LAN nodes constitute a population of individuals that exhibit behaviors defined by a rigid protocol.  What if this protocol were not so rigid, but adaptive, where each wireless station (namely, the MAC layer that manages the resources and resource access of the wireless medium) were able to learn and adapt to changing conditions in its environment?  What if WLAN stations were able to share more than frame information, but meta-level information governing their internal state and what they have learned from their environment?  Would it be possible to create behaviors in individual wireless nodes such that the behavior of the wireless network as a whole were capable of "intelligence"?  These are the questions we want to answer in this research, and we believe that RCM techniques provide an appropriate vehicle for realizing such adaptive systems on a compact and cost effective VLSI hardware platform.  See this ASOWN abstract and Research Quad Chart (PDF) for more information on this project.

Design and Architecture of Reconfigurable Computing Applications

MAPLD 2003, Washington, DC.  

High-performance RCM platforms provide a wide-range of architectures and circuit realization possibilities.  The primary problem being investigated is how to formalize the analysis, architecture and implementation of applications that are specially formulated for the reconfigurable computing paradigm that make the most of the resources that RCM platforms have to offer.  In general, we are looking to explore different mappings of applications--in terms of their algorithms and data structures--onto various reconfigurable computing platforms in an efficient manner.  Such RCM platforms have resources at our disposal--in terms of logic "slices" (the primitive unit of resource allocation on a Xilinx® FPGA) and CLBs on a given FPGA device, and interconnect resources (signals paths and bus structures) available for communicating logic functions that span multiple FPGA devices configured in the RCM platform.

The problem of identifying the "best fit" of a given application starts with exploring how best to map the application

Working hard.

architecture to this set of available resources so as to provide the most efficient use of these resources while delivering the most application performance.  However, we are also interested in the relationship between the algorithms and data structures that may be in prevalent use for a given application domain, and how to assess and select the most optimal VLSI architecture among many candidate architectures for subsequent mapping onto the RCM platform.  In general, we are looking at this for problem domains where computation consists of very-wide data paths, resulting in operations that span multiple FPGA devices. 

Team members working with the SBS HAL-15(R).

Therefore, the analysis, architecture selection, and platform mapping tasks are interrelated and iterative.  For instance, we might identify a number of different ways to construct a large, 256-bit multiplier architecture for use in a high-performance application, but we must consider the selection of the architecture not just on the general efficiency and throughput of the architecture, but also on the quality of the resultant design partitioning and mapping to the fixed resources according to resource and  timing "budgets" available to us for the RCM platform being used.  We are currently pursuing this investigation using the Star Bridge Systems® HC-36m® platform.

Publications

• L. Cordova, D. Buell, and S. Akella, "The DARPA dynamic programming benchmark on a reconfigurable computer," FCCM poster session, 18-20 April 2005. (ppt).

Faculty contacts

Some Industry links