.0018-9162/97/$10.00 © 1997 IEEE38 ComputerSeeking Solutions in ConfigurableComputingConfigurable computing systems com-bine programmable hardware withprogrammable processors to capitalizeon the strengths of hardware and soft-ware. Often these systems must alsoaddress the difficulties of both hardware and software,because they mix the technology. While the origins ofconfigurable computing go back at least 30 years, thepast eight years have brought about a significantincrease in research activity.Since at least 1989,1configurable computing sys-tems2have demonstrated the potential for achievinghigh performance for a range of applications, includ-ing image filtering, convolution, morphology, featureextraction, and object tracking. Researchers havedeveloped prototype systems that achieve performancean order of magnitude higher than more conventionalapproaches for a number of applications. However,realizing this potential outside of the laboratory hasproven difficult because these systems rely on manip-ulating low-level abstractions—digital circuits, forexample—and thus require highly skilled developers.CURRENT STATE OF AFFAIRSThe earliest configurable computing machine waslikely proposed, designed, and implemented by GeraldEstrin at UCLA in the early 1960s.3Estrin proposed the“fixed plus variable structure computer,” which dedi-cated hardware to both an (inflexible) abstraction of aprogrammable processor and a (flexible) componentthat implemented digital logic. This basic architecture,which supports programmed hardware and software, isat the core of all subsequent configurable computingsystems. Unfortunately, Estrin’s architectural conceptswere well ahead of the enabling technology, and he wasonly able to prototype a crude approximation of hisvision. Many of the concepts that are now being dis-covered by the configurable computing community liequietly unheeded in Estrin’s early publications.The enabling technology behind the renewed inter-est in configurable computing is the availability ofhigh-density VLSI devices that use programmableswitches to implement flexible hardware architectures.These chips contain memory cells that hold both con-figuration information for the programmable switchesand state information for active computations. Beforeprogramming, the chips present a partial architecture,which is then refined according to the configurationinformation. The configured device provides an exe-cution environment for a specific application.The most common devices used for configurablecomputing are field programmable gate arrays. FPGAspresent the abstraction of gate arrays, allowing devel-opers to manipulate flip-flops, small amounts of mem-ory, and logic gates.Figure 1 illustrates the basic architectural compo-nents of all configurable computers. This highlyabstracted model allows a wide range of design choices,all of which revolve around three main decisions.• Granularity of programmable hardware. Mostexisting configurable computers use commercialFPGAs. Consequently, application developmentinvolves the use of traditional CAD tools, whichwere developed for application-specific integratedcircuits (ASICs). Many application developersfind this low-level abstraction difficult to workwith, and the systems achieve poor circuit den-sity for highly regular structures such as multi-pliers. To raise the level of abstraction, severalconfigurable computing systems under develop-ment limit the programmable hardware to theinterconnect, and in the place of gates and flip-flops they use components such as arithmetic logicunits (ALUs) or multipliers.• Proximity of the CPU to the programmable hard-ware. First-generation systems typically usedperipheral buses like the Sparc SBus to provide acoprocessor-like structure. Recently, some re-searchers have argued that the programmablehardware must be much closer to the processor,perhaps even on the datapath, fed by processorregisters. This issue affects hardware design aswell as application development.• Capacity. Different system designers have madedrastically different choices about fundamentalquestions of system capacity. What is the bestratio of programmable hardware to memory sizeConfigurable computing offers the potential of producing powerful newcomputing systems. Will current research overcome the dearth of commercial applicability to make such systems a reality?William H.Mangione-SmithUniversity ofCalifornia, Los AngelesBrad HutchingsBrigham YoungUniversityDavid AndrewsUniversity ofArkansasAndré DeHonUniversity ofCalifornia,BerkeleyCarl EbelingUniversity ofWashingtonReiner HartensteinUniversity ofKaiserslauternOskarMencerStanford UniversityJohn MorrisUniversity ofWestern AustraliaKrishna PalemNew York UniversityViktor K.PrasannaUniversity ofSouthern CaliforniaHenk A.E. SpaanenburgLockheedSandersTheme Feature.and bandwidth? Or processor communicationbandwidth? How much programmable hardwareis required: an unlimited amount for applicationswith unbounded parallelism or only so much?Granularity of programmable hardwareThe configurable computing community is dividedinto two camps, according to the level of abstractionprovided by the programmable hardware. The major-ity of current research efforts use commercial FPGAsand manipulate digital circuits through logic gates andflip-flops. We will refer to these devices as netlist com-puters. As part of conventional CAD development ofASICs, digital circuits are translated into netlists,which are composed of logic gates and flip-flops.In the second camp are the newer architectures,which are based on “chunky” function units such ascomplete ALUs and multipliers. These architectureslimit the programmable hardware to the interconnectamong the function units, but implement those unitsin much less IC area.Netlist computers. A typical netlist computingdevice is an FPGA containing thousands of low-pow-ered processing elements. For example, an FPGA cellmight consist of a single flip-flop and a function gen-erator that implements a Boolean function of fourvariables. FPGAs have a programmable interconnectthat is manipulated as individual wires. Because oftheir fine granularity, netlist computers are the mostflexible configurable computers; their elements canbe used to implement state machines, datapaths, andnearly any digital circuit. This flexibility is purchasedwith additional silicon, and it results in lowered per-formance on certain classes of problems, comparedto chunky architectures. The