Architectures, Compilers, and Configuration Management for Mass-Market Adaptive Computing

Scott Hauck, Prithviraj Banerjee, Majid Sarrafzadeh

This DARPA-sponsored research project seeks to develop a complete adaptive computing solution for general-purpose computation. It includes efforts on adaptive computer architectures, configuration management, high-level compilation, template-based physical design, and military applications of adaptive computing technology.

Adaptive Computing Architectures

In order to demonstrate the advantages of single-chip integration of reconfigurable logic with a host processor, as well as the speculative execution model proposed, we will develop the Chimaera hardware system. We will develop a VLSI implementation of the Chimaera Reconfigurable Logic Array, and demonstrate the achievable performance of this array. We will also investigate high-performance carry chains, and create VLSI implementations of our proposed logic structures. Finally, we will create the architecture for the rest of the system, and demonstrate the complete system architecture operating on complex applications.

Configuration Management for Adaptive Computing

We have proposed numerous techniques for configuration management for adaptive computing. New techniques proposed here include high-performance configuration buses and configuration compression and decompression algorithms. We will develop a high-performance bus structure optimized for carrying configuration data for adaptive computers, leveraging current techniques in high-performance sequential memory bus structures. We will also create compression algorithms appropriate for adaptive computing, allowing configuration size to be reduced while allowing for efficient decompression during reconfiguration. To demonstrate these techniques we will develop a VLSI implementation of the decompression algorithms for inclusion in our adaptive computing system.

Eliminating reconfiguration overhead requires more than just compression and fast bus structures. To remove this bottleneck we will develop an integrated configuration management system. This system will include the high-performance configuration bus and compression algorithms described earlier, as well as the integration of prefetching, configuration caching, multi-level caching, dynamic contexts, and partial run-time reconfiguration. We will develop a prototype system including all of these optimizations, and demonstrate their performance on the applications investigated in this proposal.

High-level Compilation for Adaptive Computing

Adaptive computing systems require not just efficient hardware, but also software sophisticated enough to achieve high-performance implementations of user algorithms. To achieve this goal we will develop high-level compilation support to translate source programs in a high-level language into assembly language and reconfigurable logic implementations for adaptive computers. These tools will create implementations automatically in approximately the same time as a standard software compiler.

Our compiler for adaptive computers will include several advanced optimizations. In order to reduce the complexity of the logic mapped to the reconfigurable logic, and create the fastest implementation, we will apply strength reduction transformations to replace difficult to implement instructions with simpler alternatives. To increase the benefit of an RFUOP, we will develop techniques (similar to cache blocking) which can group operations together that can take advantage of the same RFUOP. Parallelism in the code will also be considered, and we will extract parallelism from the program to allow multi-threaded operation which can help hide reconfiguration latency. We will also develop code motion techniques, which can increase the regions of the code that can be mapped to reconfigurable logic. Finally, we will investigate support for variable-precision arithmetic, and create compiler optimizations that can automatically take advantage of this unique opportunity in reconfigurable logic. Each of these optimizations will be implemented in software, and merged into a complete compiler for adaptive computers.

Template Based Physical Design

Once the high-level compiler has transformed a program into assembly language, with some regions of the code identified for migration to reconfigurable logic, it is necessary to create an implementation of these code regions. In order to provide high quality implementations, while maintaining compile times similar to standard software compilers, we are developing a template-based compilation methodology. We will develop algorithms to take regions of assembly language and replace them with logic templates, and then floorplan the reconfigurable logic. This will create an initial layout for the circuit. Then, we will investigate techniques for merging connected templates and remove extraneous logic elements. From there, we will develop template-based placement and routing tools, physical design algorithms optimized to take advantage of the structure of the templates while allowing enough flexibility to create high-quality implementations. We will develop each of these algorithms, and create a complete back-end compiler for the reconfigurable logic in an adaptive computer system. Once this system is operational, we will investigate methods for run-time constant propagation, which will reoptimize a configuration to take advantage of knowledge about parameters only obtainable at runtime.

Military Applications for Adaptive Computing

In order to demonstrate our techniques, and guide the development of the hardware and software constructs contained in this proposal, we will develop implementations of important classes of military-relevant algorithms on adaptive computers. These applications will include Automatic Target Recognition, Data Encryption and Compression, Image and Signal Processing, Variable Precision Arithmetic, Emulation of Legacy Computing Systems, and BDD-based VLSI/CAD algorithms. These implementations will include both hand-optimized, automatically generated, and library-based solutions.