Central
(RISC)
Processor
Instruction
and Data                               Configurable     I
Memory                   Bus(es)       Logic
(off-chip)                             Gates
,
Embedded
Memory
Figure 1. Typical Configurable System on a Chip (CSoC) architecture. A central RISC processor is built into
the same chip as the logic gates and embedded memory modules, and both have access to local on-board, but off-
chip, memory. The size and number of buses connecting the central processor to the configurable logic can itself be
configured to achieve a bandwidth that is appropriate for the application.
Hardware implementation is sometimes seen as a brute force approach to speeding up algorithms. Generally,
to implement an algorithm in hardware requires a lot more effort than to implement it in software. And gener-
ally, to fit an algorithm into hardware, certain approximations, truncations, and/or simplifications must be made.
These approximations must be traded against the raw speed provided by the fine-grained parallelism in a hardware
implementation.
One very nice example of a co-design was developed by Porter et al.1", It employs a genetic algorithm in software
that specifies the settings of hardware registers to direct a generic image processing operator that is implemented in
an FPGA. Compared to the original all-software version of this algorithm,14 this hardware-accelerated system has a
much smaller operator set, but it makes up for this with a search through operator space that is roughly two orders
of magnitude faster. This example also illustrates the need to decompose an algorithm so that there is a simpler
part (often an "inner loop") that can be sped up in hardware in such a way that doesn't interfere with potentially
complicated branching logic (in the "outer loop"). This complicated outer loop logic is what allows you to design
sophistication into your algorithm, sophistication that may enable further speedup, or that may simply be necessary
to achieve a sophisticated goal.
For algorithms that employ substantial software and hardware components, the biggest challenge is the commu-
nication bandwidth between them. One answer to this bottleneck is a hybrid processor that combines a traditional
microprocessor and programmable logic on the same chip.15-17 (see Fig. 1.) Such hardware is just now becoming
commercially available.18-27 We have recently used the Altera Excalibur board with a soft-core 32-bit NIOS RISC
processor18 as part of a co-design for k-means clustering.28 Unfortunately, the promise of seamless integration of
a fast central processor surrounded by acres of programmable logic remains to be fulfilled. We achieved a 15%
speedup, but were limited by slow memory access and a slow central processor - since the processor on the Excalibur
is implemented as a "soft core" it is constrained to run at the same clock speed as the programmable logic itself.
With a faster hybrid processor (eg, 10x faster than configurable circuits) or dual port memories that both processor
and configurable circuits can access, then we would expect 10x speedup over sequential algorithms. We furthermore
extrapolated the expected performance to the Xilinx-PowerPC hybrid19 and predicted the possibility for two orders
of magnitude acceleration.
In the following two sections, we will discuss the possibilities for further co-design opportunities - these simulta-
neously employ "smart" software and "brute force" hardware to speedup two problems of interest in remote sensing:
image segmentation and endmember estimation.