Algorithm Analysis and Mapping Environment for Adaptive Computing Systems

ABSTRACT

Our approach to building a design environment for ACS has been to focus on three areas of capability critical to the success of adaptive computing and to integrate these capabilities into an open, extensible software framework. The development of the three areas, algorithm analysis, algorithm mapping, and smart generators, are taking advantage of the special characteristics of signal processing algorithms to make progress. These capabilities are being implemented on top of the Ptolemy signal processing algorithm and implementation environment from the University of California, Berkeley (see http://ptolemy.eecs.berkeley.edu).

Algorithm implementation on Adaptive Computing Systems requires careful consideration of the costs of operations as well as significant work to determine the appropriate signal representation. The algorithm analysis capabilities that are being developed on this program will reduce the effort required to find good algorithms for implementation on ACS. The environment will eventually provide mathematicians with information about operation counts, including adds, multiplies, and memory accesses, and with analyses of numerical issues relating to implementation in Adaptive Computing Systems. Our capabilities will include analysis of algorithms at the bit level to determine appropriate finite precision implementations, statistical analysis, symmetry detection, and error propagation. With these capabilities an algorithm designer will be able to quickly determine the appropriate number of bits for signal representation and to quantify the performance of various implementation choices.

Signal processing algorithm mapping for ACS involves the assignment of functions to different processing elements. Current systems either require hand mapping or use general logic partitioning methods that do not take advantage of the structure of signal processing algorithms. On this program we are developing mapping techniques for ACS tailored to signal processing. These capabilities include performance analysis, partitioning assistance, and automatic scheduling and partitioning. The scheduling and partitioning functions will recognize the coarse-grain nature of signal processing dataflow graphs to optimize partitioning for ACS.

Current methods for logic generation on Adaptive Computing Systems are either built around libraries of functions or around general-purpose logic synthesis. As part of this effort, we are implementing "smart generators" that are extensions of the concept of a parameterized library. These generators will be tailored to signal processing functions and will include rules that capture specific implementation techniques and trade-offs. For example, a smart generator for a complex multiplier is able to trade between a three-multiplier implementation and a four-multiplier implementation according to area and latency constraints. Additionally, we are providing generators for both hardware and software interfaces to the Adaptive Computing System.

All of the algorithm analysis and mapping capabilities to be developed on this program will be captured in a set of software tools. These tools will be built on the existing Ptolemy signal representation and analysis system from UC Berkeley. Ptolemy provides an open software environment with well-defined interfaces among its functional areas. Ptolemy has been implemented in C++ using a well documented, object-oriented software architecture. In this project, we are extending Ptolemy by developing a new ACS domain that separates the interface specification from implementation for each signal processing functional block. The algorithms of interest to this project are represented by dataflow graphs comprised of these functional block, which follow a synchronous dataflow model of computation. We are using a Corona/Core architecture, where each block has an common interface known as the Corona, and one or more implementations, known as the Cores. A retargeting mechanism allows the users change Cores and hence implementation, which moves the dataflow graph between various simulation models (floating point, fixed point) and implementations (C code, VHDL code, etc.). This library of Corona/Core functional blocks is used to represent multiple implementations of signal processing operations for ACS and to share data among functions.

Building on Ptolemy will allow both rapid insertions of our new capabilities as well as the ability for additional researchers to build their own capabilities and libraries. This approach has been used successfully by groups outside UC Berkeley who regularly extend Ptolemy. This program will release software every six months, with the first ACS domain implementation released in June 1998. Each software release will be followed by a demonstration of implementing a significant military signal processing algorithm on ACS hardware. We are currently planning a digital communication demonstration, a signal detection and classification demonstration, an image formation/automatic target recognition demonstration, and finally a demonstration using a government supplied test bed.