Reconfigurable computing: a survey of systems and software
---
paper_title: A representation for dynamic graphs in reconfigurable hardware and its application to fundamental graph algorithms

paper_content:

This paper gives a representation for graph data structures as electronic circuits in reconfigurable hardware. Graph properties, such as vertex reachability, are computed quickly by exploiting a graph's edge parallelism—signals propagate along many graph edges concurrently. This new representation admits arbitrary graphs in which vertices/edges may be inserted and deleted dynamically at low cost—graph modification does not entail any re-fitting of the graph's circuit. Dynamic modification is achieved by rewriting cells in a reconfigurable hardware array. Dynamic graph algorithms are given for vertex reachability, transitive closure, shortest unit path, cycle detection, and connected-component identification. On the task of computing a graph's transitive closure, for example, simulation of such a dynamic graph processor indicates possible speedups greater than three orders of magnitude compared to an efficient software algorithm running on a contemporaneously fast uniprocessor. Implementation of a prototype in an FPGA verifies the accuracy of the simulation and demonstrates that a practical and efficient (compact) mapping of the graph construction is possible in existing FPGA architectures. In addition to speeding conventional graph computations with dynamic graph processors, we note their potential as parallel graph reducers implementing general (Turing equivalent) computation.
---
paper_title: Hardware-software codesign and parallel implementation of a Golomb ruler derivation engine

paper_content:

A new architecture for Golomb ruler derivation has been developed so that rulers up to 24 marks can be proven on it. In this architecture, 8-mark stubs that are derived on a personal computer are subsequently processed by the FCCM, called GE2, allowing for parallel processing of as many stubs as are the available FPGAs. Actual runs of the new design have been performed on the TOP parallel FPGA machine at Virginia Tech. This paper presents the design improvements over the original architecture, which include single FPGA implementation, hardware/software codesign, FIFO based I/O, design for parallel execution, and performance results from actual runs.
---
paper_title: Architecture and design of GE1, an FCCM for Golomb ruler derivation

paper_content:

A new architecture for Golomb ruler derivation has been developed, and an FPGA-based custom compute engine of the new architecture has been fully designed. The new FCCM, called GE1, is presented in terms of its datapath, and control path. Portions of the GE1 have been implemented to verify functional correctness and accuracy of the simulation results. The new machine requires twenty Xilinx 5000 series FPGA's for derivation of the 20 mark Golomb ruler, and its performance is roughly 30 times that of a high-end workstation, making its cost-performance ratio exceptionally good for derivation of new rulers.
---
paper_title: Seeking solutions in configurable computing

paper_content:

Configurable computing offers the potential of producing powerful new computing systems. Will current research overcome the dearth of commercial applicability to make such systems a reality? Unfortunately, no system to date has yet proven attractive or competitive enough to establish a commercial presence. We believe that ample opportunity exists for work in a broad range of areas. In particular, the configurable computing community should focus on refining the emerging architectures, producing more effective software/hardware APIs, better tools for application development that incorporate the models of hardware reconfiguration, and effective benchmarking strategies.
---
paper_title: FPGA implementation of a microcoded elliptic curve cryptographic processor

paper_content:

Elliptic curve cryptography (ECC) has been the focus of much recent attention since it offers the highest security per bit of any known public key cryptosystem. This benefit of smaller key sizes makes ECC particularly attractive for embedded applications since its implementation requires less memory and processing power. In this paper a microcoded Xilinx Virtex based elliptic curve processor is described. In contrast to previous implementations, it implements curve operations as well as optimal normal basis field operations in F(2/sup n/); the design is parameterized for arbitrary n; and it is microcoded to allow for rapid development of the control part of the processor. The design was successfully tested on a Xilinx Virtex XCV300-4 and, for n=113 bits, utilized 1290 slices at a maximum frequency of 45 MHz and achieved a thirty-fold speedup over an optimized software implementation.
---
paper_title: Factoring large numbers with programmable hardware

paper_content:

Most advanced forms of security for electronic transactions rely on the public-key cryptosystems developed by Rivest, Shamir and Adleman. Unfortunately, these systems are only secure while it remains difficult to factor large integers. The fastest published algorithms for factoring large numbers have a common sieving step. These sieves collect numbers that are completely factored by a set of prime numbers that are known in advance. Furthermore, the time required to execute these sieves currently dominates the runtime of the factoring algorithms. We show how the sieving process can be mapped to the Mojave configurable computing architecture. The mapping exploits unique properties of the sieving algorithms to fully utilize the bandwidth of a multiple bank interleaved memory system. The sieve has been mapped to a single programmable hardware unit on the Mojave computer, and achieves a clock frequency of 16 MHz. The full system implementation sieves over 28 times faster than an UltraSPARC Workstation. A simple upgrade to 8ns SRAMs will result in a speedup factor of 160.
---
paper_title: An FPGA implementation and performance evaluation of the Serpent block cipher

paper_content:

With the expiration of the Data Encryption Standard (DES) in 1998, the Advanced Eneryption Standard (AES) development process is well underway. It is hoped that the result of the AES process will be the specification of a new non-classified encryption algorithm that will have the global acceptance achieved by DES as well as the capability of long-term protection of sensitive information. The technical analysis used in determining which of the potential AES candidates will be selected as the Advanced Encryption Algorithm includes efficiency testing of both hardware and software implementations of candidate algorithms. Reprogrammable devices such as Field Programmable Gate Arrays (FPGAs) are highly attractive options for hardware implementations of encryption algorithms as they provide cryptographic algorithm agility, physical security, and potentially much higher performance than software solutions. This contribution investigates the significance of an FPGA implementation of Serpent, one of the Advanced Encryption Standard candidate algorithms. Multiple architecture options of the Serpent algorithm will be explored with a strong focus being placed on a high speed implementation within an FPGA in order to support security for current and future high bandwidth applications. One of the main findings is that Serpent can be implemented with encryption rates beyond 4 Gbit/s on current FPGAs.
---
paper_title: Genetic algorithms in software and in hardware-a performance analysis of workstation and custom computing machine implementations

paper_content:

The paper analyzes the performance differences found between the hardware and software versions of a genetic algorithm used to solve the travelling salesman problem. The hardware implementation requires 4 FPGA's on a Splash 2 board and runs at 11 MHz. The software implementation was written in C++ and executed on a 125 MHz HP PA-RISC workstation. The software run time was more than four times that of the hardware (up to 50 times as many cycles). The paper analyses the contribution made to this performance difference by the following hardware features: hard-wired control, custom address generation logic, memory hierarchy efficiency, and both fine- and course-grained parallelism. The results indicate that the major contributor to the hardware performance advantage is fine-grained parallelism-RTL-level parallelism due to operator pipelining. This alone accounts for as much as a 38X cycle-count reduction over the software in one section of the algorithm. The next major contributors include hard-wired control and custom address generation which account for as much as a 3X speedup in other sections of the algorithm. Finally, memory hierarchy inefficiencies in the software (cache misses and paging) and coarse-grained parallelism in the hardware are each shown to have lesser effect on the performance difference between the implementations.
---
paper_title: Automated target recognition on SPLASH 2

paper_content:

Automated target recognition is an application area that requires special-purpose hardware to achieve reasonable performance. FPGA-based platforms can provide a high level of performance for ATR systems if the implementation can be adapted to the limited FPGA and routing resources of these architectures. The paper discusses a mapping experiment where a linear-systolic implementation of an ATR algorithm is mapped to the SPLASH 2 platform. Simple column oriented processors were used throughout the design to achieve high performance with limited nearest neighbor communication. The distributed SPLASH 2 memories are also exploited to achieve a high degree of parallelism. The resulting design is scalable and can be spread across multiple SPLASH 2 boards with a linear increase in performance.
---
paper_title: Software technologies for reconfigurable systems

paper_content:

FPGA-based systems are a significant area of computing, providing a high-performance implementation substrate for many different applications. However, the key to harnessing their power for most domains is developing mapping tools for automatically transforming a circuit or algorithm into a configuration for the system. In this paper we review the current state-of-the-art in mapping tools for FPGA-based systems, including single-chip and multi-chip mapping algorithms for FPGAs, software support for reconfigurable computing, and tools for run-time reconfigurability. We also discuss the challenges for the future, pointing out where development is still needed to let reconfigurable systems achieve all of their promise.
---
paper_title: The Roles of FPGAs in Reprogrammable Systems

paper_content:

Reprogrammable systems based on field programmable gate arrays are revolutionizing some forms of computation and digital logic. As a logic emulation system, they provide orders of magnitude faster computation than software simulation. As a custom-computing machine, they achieve the highest performance implementation for many types of applications. As a multimode system, they yield significant hardware savings and provide truly generic hardware. In this paper, we discuss the promise and problems of reprogrammable systems. This includes an overview of the chip and system architectures of reprogrammable systems as well as the applications of these systems. We also discuss the challenges and opportunities of future reprogrammable systems.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Parallel Processing in a Restructurable Computer System

paper_content:

Pragmatic problem studies predict gains in computation speeds in a variety of computational tasks when executed on appropriate problem-oriented configurations of the variable structure computer. The economic feasibility of the system is based on utilization of essentially the same hardware in a variety of special purpose structures. This capability is achieved by programmed or physical restructuring of a part of the hardware. Existence of important classes of problems which the variable structure computer system promises to render practically computable, as well as use of the system for experiments in computer organization and for evaluation of new circuits and devices warrant construction of a variable structure computer. This paper describes the organization, programming, and hardware of a variable structure computer system presently under construction at UCLA.
---
paper_title: The programmable logic data book

paper_content:

Improvement to video-telephone systems allowing a called subscriber to have at his disposal on his television receiver screen, before he takes off his handset, information about the person who has initiated the call. Each subscriber station has a handset, a television camera, a television receiver and a character generator and is connected to a switching network by a telephone line, an incoming video line and an outgoing video line. Means are provided in the calling station for connecting to the outgoing video line the character generator when the calling subscriber takes down the handset and the television camera when video signals are detected on the incoming video line and in the called station for supplying with current the television receiver when ringing tone signals are detected on the telephone line.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: A reconfigurable arithmetic array for multimedia applications

paper_content:

In this paper we describe a reconfigurable architecture optimised for media processing, and based on 4-bit ALUs and interconnect.
---
paper_title: A quantitative analysis of reconfigurable coprocessors for multimedia applications

paper_content:

Recently, computer architectures that combine a reconfigurable (or retargetable) coprocessor with a general-purpose microprocessor have been proposed. These architectures are designed to exploit large amounts of fine grain parallelism in applications. In this paper, we study the performance of the reconfigurable coprocessors on multimedia applications. We compare a Field Programmable Gate Array (FPGA) based reconfigurable coprocessor with the array processor called REMARC (Reconfigurable Multimedia Array Coprocessor). REMARC uses a 16-bit simple processor that is much larger than a Configurable Logic Block (CLB) of an FPGA. We have developed a simulator, a programming environment, and multimedia application programs to evaluate the performance of the two coprocessor architectures. The simulation results show that REMARC achieves speedups ranging from a factor of 2.3 to 7.3 on these applications. The FPGA coprocessor achieves similar performance improvements. However, the FPGA coprocessor needs more hardware area to achieve the same performance improvement as REMARC.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: A quantitative analysis of reconfigurable coprocessors for multimedia applications

paper_content:

Recently, computer architectures that combine a reconfigurable (or retargetable) coprocessor with a general-purpose microprocessor have been proposed. These architectures are designed to exploit large amounts of fine grain parallelism in applications. In this paper, we study the performance of the reconfigurable coprocessors on multimedia applications. We compare a Field Programmable Gate Array (FPGA) based reconfigurable coprocessor with the array processor called REMARC (Reconfigurable Multimedia Array Coprocessor). REMARC uses a 16-bit simple processor that is much larger than a Configurable Logic Block (CLB) of an FPGA. We have developed a simulator, a programming environment, and multimedia application programs to evaluate the performance of the two coprocessor architectures. The simulation results show that REMARC achieves speedups ranging from a factor of 2.3 to 7.3 on these applications. The FPGA coprocessor achieves similar performance improvements. However, the FPGA coprocessor needs more hardware area to achieve the same performance improvement as REMARC.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: A detailed router for field-programmable gate arrays

paper_content:

A detailed routing algorithm, called the coarse graph expander (CGE), that has been designed specifically for field-programmable gate arrays (FPGAs) is described. The algorithm approaches this problem in a general way, allowing it to be used over a wide range of different FPGA routing architectures. It addresses the issue of scarce routing resources by considering the side effects that the routing of one connection has on another, and also has the ability to optimize the routing delays of time-critical connections. CGE has been used to obtain excellent routing results for several industrial circuits implemented in FPGAs with various routing architectures. The results show that CGE can route relatively large FPGAs in very close to the minimum number of tracks as determined by global routing, and it can successfully optimize the routing delays of time-critical connections. CGE has a linear run time over circuit size. >
---
paper_title: Architecture of Field-Programmable Gate Arrays

paper_content:

A survey of field-programmable gate array (FPGA) architectures and the programming technologies used to customize them is presented. Programming technologies are compared on the basis of their volatility, size parasitic capacitance, resistance, and process technology complexity. FPGA architectures are divided into two constituents: logic block architectures and routing architectures. A classification of logic blocks based on their granularity is proposed, and several logic blocks used in commercially available FPGAs are described. A brief review of recent results on the effect of logic block granularity on logic density and performance of an FPGA is then presented. Several commercial routing architectures are described in the context of a general routing architecture model. Finally, recent results on the tradeoff between the flexibility of an FPGA routing architecture, its routability, and its density are reviewed. >
---
paper_title: Exploring optimal cost-performance designs for Raw microprocessors

paper_content:

The semiconductor industry roadmap projects that advance in VLSI technology will permit more than one billion transistors on a chip by the year 2010. The MIT Raw microprocessor is a proposed architecture that strives to exploit these chip-level resources by implementing thousands of tiles, each comprising a processing element and a small amount of memory, coupled by a static two-dimensional interconnect. A compiler partitions fine-grain instruction-level parallelism across the tiles and statically schedules inter-tile communication over the interconnect. Because Raw microprocessors fully expose their internal hardware structure to the software, they can be viewed as a gigantic FPGA with coarse-grained tiles, in which software orchestrates communication over static interconnections. One open challenge in Raw architectures is to determine their optimal grain size and balance. The grain size is the area of each tile, and the balance is the proportion of area in each tile devoted to memory, processing, communication, and I/O. If the total chip area is fixed, more area devoted to processing will result in a higher processing power per node, but will lead to a fewer number of tiles. This paper presents an analytical framework using which designers can reason about the design space of Raw microprocessors. Based on an architectural model and a VLSI cost analysis, the framework computes the performance of applications, and uses an optimization process to identify designs that will execute these applications most cost-effectively.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: A reconfigurable multiplier array for video image processing tasks, suitable for embedding in an FPGA structure

paper_content:

This paper presents a design for a reconfigurable multiplier array. The multiplier is constructed using an array of 4 bit Flexible Array Blocks (FABs), which could be embedded within a conventional FPGA structure. The array can be configured to perform a number of 4n/spl times/4m bit signed/unsigned binary multiplications. We have estimated that the FABs are about 25 times more efficient in area than the equivalent multiplier implemented using a conventional FPGA structure alone.
---
paper_title: The programmable logic data book

paper_content:

Improvement to video-telephone systems allowing a called subscriber to have at his disposal on his television receiver screen, before he takes off his handset, information about the person who has initiated the call. Each subscriber station has a handset, a television camera, a television receiver and a character generator and is connected to a switching network by a telephone line, an incoming video line and an outgoing video line. Means are provided in the calling station for connecting to the outgoing video line the character generator when the calling subscriber takes down the handset and the television camera when video signals are detected on the incoming video line and in the called station for supplying with current the television receiver when ringing tone signals are detected on the telephone line.
---
paper_title: A reconfigurable arithmetic array for multimedia applications

paper_content:

In this paper we describe a reconfigurable architecture optimised for media processing, and based on 4-bit ALUs and interconnect.
---
paper_title: A quantitative analysis of reconfigurable coprocessors for multimedia applications

paper_content:

Recently, computer architectures that combine a reconfigurable (or retargetable) coprocessor with a general-purpose microprocessor have been proposed. These architectures are designed to exploit large amounts of fine grain parallelism in applications. In this paper, we study the performance of the reconfigurable coprocessors on multimedia applications. We compare a Field Programmable Gate Array (FPGA) based reconfigurable coprocessor with the array processor called REMARC (Reconfigurable Multimedia Array Coprocessor). REMARC uses a 16-bit simple processor that is much larger than a Configurable Logic Block (CLB) of an FPGA. We have developed a simulator, a programming environment, and multimedia application programs to evaluate the performance of the two coprocessor architectures. The simulation results show that REMARC achieves speedups ranging from a factor of 2.3 to 7.3 on these applications. The FPGA coprocessor achieves similar performance improvements. However, the FPGA coprocessor needs more hardware area to achieve the same performance improvement as REMARC.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Hybrid product term and LUT based architectures using embedded memory blocks

paper_content:

The Embedded System Block (ESB) of the APEX20K programmable logic device family from Altera Corporation includes the capability of implementing product term macrocells in addition to flexibly configurable ROM and dual port RAM. In product term mode, each ESB has 16 macrocells built out of 32 product terms with 32 literal inputs. The ability to reconfigure memory blocks in this way represents a new and innovative use of resources in a programmable logic device, requiring creative solutions in both the hardware and software domains. The architecture and features of this Embedded System Block are described.
---
paper_title: SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays

paper_content:

It has become clear that large embedded configurable memory arrays will be essential in future FPGAs. Embedded arrays provide high-density high-speed implementations of the storage parts of circuits. Unfortunately, they require the FPGA vendor to partition the device into memory and logic resources at manufacture-time. This leads to a waste of chip area for customers that do not use all of the storage provided. This chip area need not be wasted, and can in fact be used very efficiently, if the arrays are configured as large multi-output ROMs, and used to implement logic. In order to efficiently use the embedded arrays in this way, a technology mapping algorithm that identifies parts of circuits that can be efficiently mapped to an embedded array is required. In this paper, we describe such an algorithm. The new tool, called SMAP, packs as much circuit information as possible into the available memory arrays, and maps the rest of the circuit into four-input lookup-tables. On a set of 29 sequential and combinational benchmarks, the tool is able to map, on average, 60 4-LUTs into a single 2-Kbit memory array. If there are 16 arrays available, it can map, on average, 358 4-LUTs to the 16 arrays.
---
paper_title: A reconfigurable multiplier array for video image processing tasks, suitable for embedding in an FPGA structure

paper_content:

This paper presents a design for a reconfigurable multiplier array. The multiplier is constructed using an array of 4 bit Flexible Array Blocks (FABs), which could be embedded within a conventional FPGA structure. The array can be configured to perform a number of 4n/spl times/4m bit signed/unsigned binary multiplications. We have estimated that the FABs are about 25 times more efficient in area than the equivalent multiplier implemented using a conventional FPGA structure alone.
---
paper_title: The programmable logic data book

paper_content:

Improvement to video-telephone systems allowing a called subscriber to have at his disposal on his television receiver screen, before he takes off his handset, information about the person who has initiated the call. Each subscriber station has a handset, a television camera, a television receiver and a character generator and is connected to a switching network by a telephone line, an incoming video line and an outgoing video line. Means are provided in the calling station for connecting to the outgoing video line the character generator when the calling subscriber takes down the handset and the television camera when video signals are detected on the incoming video line and in the called station for supplying with current the television receiver when ringing tone signals are detected on the telephone line.
---
paper_title: Technology mapping for FPGAs with embedded memory blocks

paper_content:

Modern field programmable gate arrays (FPGAs) provide embedded memory blocks (EMBs) to be used as on-chip memories. In this paper, we explore the possibility of using EMBs to implement logic functions when they are not used as on-chip memory. We propose a general technology mapping problem for FPGAs with EMBs for area and delay minimization and develop an efficient algorithm based on the concepts of Maximum Fanout Free Cone (MFFC) [3] and Maximum Fanout Free Subgraph (MFFS) [7], named EMB_Pack, which minimizes the area after or before technology mapping by using EMBs while maintaining the circuit delay. We have tested EMB_Pack on MCNC benchmarks on Altera's FLEX10K device family [1]. The experimental results show that compared with the original mapped circuits generated from CutMap [5] without using EMBs, EMB_Pack as postprocessing can further reduce up to 10% of the area on the mapped circuits while maintaining the layout delay by making efficient use of available EMB resources. Compared with CutMap-e without using EMBs, EMB_Pack as pre-mapping processing followed by CutMap-e can reduce 6% of the area while maintaining the circuit optimal delay.
---
paper_title: HSRA: high-speed, hierarchical synchronous reconfigurable array

paper_content:

There is no inherent characteristic forcing Field Programmable Gate Array (FPGA) or Reconfigurable Computing (RC) Array cycle times to be greater than processors in the same process. Modern FPGAs seldom achieve application clock rates close to their processor cousins because (1) resources in the FPGAs are not balanced appropriately for high-speed operation, (2) FPGA CAD does not automatically provide the requisite transforms to support this operation, and (3) interconnect delays can be large and vary almost continuously, complicating high frequency mapping. We introduce a novel reconfigurable computing array, the High-Speed, Hierarchical Synchronous Reconfigurable Array (HSRA), and its supporting tools. This packagedemonstrates that computing arrays can achieve efficient, high-speedoperation. We have designedand implemented a prototype component in a 0.4 m logic design on a DRAM process which will support 250MHz operation for CAD mapped designs.
---
paper_title: FPGA routing architecture: segmentation and buffering to optimize speed and density

paper_content:

In this work we investigate the routing architecture of FPGAs, focusing primarily on determining the best distribution of routing segment lengths and the best mix of pass transistor and tri-state buffer routing switches. While most commercial FPGAs contain many length 1 wires (wires that span only one logic block) we find that wires this short lead to FPGAs that are inferior in terms of both delay and routing area. Our results show instead that it is best for FPGA routing segments to have lengths of 4 to 8 logic blocks. We also show that 50% to 80% of the routing switches in an FPGA should be pass transistors, with the remainder being tri-state buffers. Architectures that employ the best segmentation distributions and the best mixes of pass transistor and tri-state buffer switches found in this paper are not only 11% to 18% faster than a routing architecture very similar to that of the Xilinx XC4000X but also considerably simpler. These results are obtained using an architecture investigation infrastructure that contains a fully timing-driven router and detailed area and delay models.
---
paper_title: More wires and fewer LUTs: a design methodology for FPGAs

paper_content:

In designing FPGAs, it is important to achiev e a good balance bet w een the number of logic blocks, suc h has Look-Up Tables (LUTs), and wiring resources. It is difficult to find an optimal solution. In this paper, w e presen t an FPGA design methodology to efficiently find well-balanced FPGA architectures. The method covers all aspects of FPGA development from the architecture-decision process to physical implementation. It has been used to develop a new FPGA that can implement circuits that are twice as large as those implementable with the previous version but with half the number of logic blocks. This indicates that the methodology is effectiv e in dev eloping well-balanced FPGAs.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: Hierarchical interconnection structures for field programmable gate arrays

paper_content:

Field programmable gate arrays (FPGA's) suffer from lower density and lower performance than conventional gate arrays. Hierarchical interconnection structures for field programmable gate arrays are proposed. They help overcome these problems. Logic blocks in a field programmable gate array are grouped into clusters. Clusters are then recursively grouped together. To obtain the optimal hierarchical structure with high performance and high density, various hierarchical structures with the same routability are discussed. The field programmable gate arrays with new architecture can be efficiently configured with existing computer aided design algorithms. The k-way min-cut algorithm is applicable to the placement step in the implementation. Global routing paths in a field programmable gate array can be obtained easily. The placement and global routing steps can be performed simultaneously. Experiments on benchmark circuits show that density and performance are significantly improved.
---
paper_title: Routing architectures for hierarchical field programmable gate arrays

paper_content:

This paper evaluates an architecture that implements a hierarchical routing structure for FPGAs, called a hierarchical FPGA (HFPGA). A set of new tools has been used to place and route several circuits on this architecture, with the goal of comparing the cost of HFPGAs to conventional symmetrical FPGAs. The results show that HFPGAs can implement circuits with fewer routing switches, and fewer switches in total, compared to symmetrical FGPAs, although they have the potential disadvantage that they may require more logic blocks due to coarser granularity. >
---
paper_title: Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization)

paper_content:

FPGA users often view the ability of an FPGA to route designs with high LUT (gate) utilization as a feature, leading them to demand high gate utilization from vendors. We present initial evidence from a hierarchical array design showing that high LUT utilization is not directly correlated with efficient silicon usage. Rather, since interconnect resources consume most of the area on these devices (often 80-90%), we can achieve more area efficient designs by allowing some LUTs to go unused—allowing us to use the dominant resource, interconnect, more efficiently. This extends the "Sea-ofgates" philosophy, familiar to mask programmable gate arrays, to FPGAs. Also introduced in this work is an algorithm for "depopulating" the gates in a hierarchical network to match the limited wiring resources.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: PipeRench: A Reconfigurable Architecture and Compiler

paper_content:

With the proliferation of highly specialized embedded computer systems has come a diversification of workloads for computing devices. General-purpose processors are struggling to efficiently meet these applications' disparate needs, and custom hardware is rarely feasible. According to the authors, reconfigurable computing, which combines the flexibility of general-purpose processors with the efficiency of custom hardware, can provide the alternative. PipeRench and its associated compiler comprise the authors' new architecture for reconfigurable computing. Combined with a traditional digital signal processor, microcontroller or general-purpose processor, PipeRench can support a system's various computing needs without requiring custom hardware. The authors describe the PipeRench architecture and how it solves some of the pre-existing problems with FPGA architectures, such as logic granularity, configuration time, forward compatibility, hard constraints and compilation time.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Mesh routing topologies for multi-FPGA systems

paper_content:

There is currently great interest in using fixed arrays of FPGAs for logic emulators, custom computing devices, and software accelerators. An important part of designing such a system is determining the proper routing topology to use to interconnect the FPGAs. This topology can have a great effect on the area and delay of the resulting system. Tree, bipartite graph, and mesh inter-connection schemes have all been proposed for use in FPGA-based systems. In this paper we examine mesh interconnection schemes, and propose several constructs for more efficient topologies. These reduce inter-chip delays by more than 60% over the basic 4-way Mesh. >
---
paper_title: The Transmogrifier-2: a 1 million gate rapid prototyping system

paper_content:

This paper describes the Transmogrifier-2, a second generation multi-FPGA system. The largest version of the system will comprise 16 boards that each contain two Altera 10K50 FPGAs, four I-cube interconnect chips, and up to 8 Mbytes of memory. The inter-FPGA routing architecture of the TM-2 uses a novel interconnect structure, a non-uniform partial crossbar, that provides a constant delay between any two FPGAs in the system. The TM-2 architecture is modular and scalable, meaning that various sized systems can be constructed from the same board, while maintaining routability and the constant delay feature. Other features include a system-level programmable clock that allows single-cycle access to off-chip memory, and programmable clock waveforms with resolution to 10ns. The first Transmogrifier-2 boards have been manufactured and are functional. They have recently been used successfully in some simple graphics acceleration applications.
---
paper_title: An efficient logic emulation system

paper_content:

The Realizer, is a logic emulation system that automatically configures a network of field-programmable gate arrays (FPGAs) to implement large digital logic designs, is presented. Logic and interconnect are separated to achieve optimum FPGA utilization. Its interconnection architecture, called the partial crossbar, greatly reduces system-level placement and routing complexity, achieves bounded interconnect delay, scales linearly with pin count, and allows hierarchical expansion to systems with hundreds of thousands of FPGA devices in a fast and uniform way. An actual multiboard system has been built, using 42 Xilinx XC3090 FPGAs for logic. Several designs, including a 32-b CPU datapath, have been automatically realized and operated at speed. They demonstrate very good FPGA utilization. The Realizer has applications in logic verification and prototyping, simulation, architecture development, and special-purpose execution. >
---
paper_title: A hybrid complete-graph partial-crossbar routing architecture for multi-FPGA systems

paper_content:

Multi-FPGA systems (MFSs) are used as custom computing machines, logic emulators and rapid prototyping vehicles. A key aspect of these systems is their programmable routing architecture; the manner in which wires, FPGAs and Field-Programmable Interconnect Devices (FPIDs) are connected. Several routing architectures for MFSs have been proposed [Arno92] [Butt92] [Hauc94] [Apti96] [Vuil96] and previous research has shown that the partial crossbar is one of the best existing architectures [Kim96] [Khal97]. In this paper we propose a new routing architecture, called the Hybrid Complete-Graph and Partial-Crossbar (HCGP) which has superior speed and cost compared to a partial crossbar. The new architecture uses both hard-wired and programmable connections between the FPGAs. We compare the performance and cost of the HCGP and partial crossbar architectures experimentally, by mapping a set of 15 large benchmark circuits into each architecture. A customized set of partitioning and inter-chip routing tools were developed, with particular attention paid to architecture-appropriate inter-chip routing algorithms. We show that the cost of the partial crossbar (as measured by the number of pins on all FPGAs and FPIDs required to fit a design), is on average 20% more than the new HCGP architecture and as much as 35% more. Furthermore, the critical path delay for designs implemented on the partial crossbar increased, and were on average 9% more than the HCGP architecture and up to 26% more. Using our experimental approach, we also explore a key architecture parameter associated with the HCGP architecture: the proportion of hard-wired connections versus programmable connections, to determine its best value.
---
paper_title: The Roles of FPGAs in Reprogrammable Systems

paper_content:

Reprogrammable systems based on field programmable gate arrays are revolutionizing some forms of computation and digital logic. As a logic emulation system, they provide orders of magnitude faster computation than software simulation. As a custom-computing machine, they achieve the highest performance implementation for many types of applications. As a multimode system, they yield significant hardware savings and provide truly generic hardware. In this paper, we discuss the promise and problems of reprogrammable systems. This includes an overview of the chip and system architectures of reprogrammable systems as well as the applications of these systems. We also discuss the challenges and opportunities of future reprogrammable systems.
---
paper_title: Synthesis and floorplanning for large hierarchical FPGAs

paper_content:

Because the VLSI circuits complexity growth, the trend in design is towards divide-and-conquer schemes, in which circuits are composed of blocks, standard macros or custom macros. From the other side, to allow an implementation of large digital circuits, increased capacity target FPGAs are organized hierarchically. In this paper, we present a hierarchical FPGA floorplanning method which takes into account both the hierarchy of the design and the hierarchy of the target. The method aims at minimization the timing and balancing cost of the floorplan and is based on automatic detection of macro blocks and assigning them to the target FPGA hierarchical zones.
---
paper_title: FPGA routing and routability estimation via Boolean satisfiability

paper_content:

Guaranteeing or even estimating the routability of a portion of a placed field programmable gate array (FPGA) remains difficult or impossible in most practical applications. In this paper, we develop a novel formulation of both routing and routability estimation that relies on a rendering of the routing constraints as a single large Boolean equation. Any satisfying assignment to this equation specifies a complete detailed routing. By representing the equation as a binary decision diagram (BDD), we represent all possible routes for all nets simultaneously. Routability estimation is transformed to Boolean satisfiability, which is trivial for BDD's. We use the technique in the context of a perfect routability estimator for a global router. Experimental results from a standard FPGA benchmark suite suggest the technique is feasible for realistic circuits, but refinements are needed for very large designs.
---
paper_title: A new retiming-based technology mapping algorithm for LUT-based FPGAs

paper_content:

In this paper, w e presen t a new retiming-based technology mapping algorithm for look-up table-based field programmable gate arrays. The algorithm is based on a novel iterative procedure for computing all k -cuts of all nodes in a sequen tialcircuit, in the presence of retiming. The algorithm completely avoids flow computation whic his the bottleneck of previous algorithms. Due to the fact that k is very small in practice, the procedure for computing all k -cuts is v ery fast. Experimental results indicate the overall algorithm is very efficient in practice.
---
paper_title: A detailed router for field-programmable gate arrays

paper_content:

A detailed routing algorithm, called the coarse graph expander (CGE), that has been designed specifically for field-programmable gate arrays (FPGAs) is described. The algorithm approaches this problem in a general way, allowing it to be used over a wide range of different FPGA routing architectures. It addresses the issue of scarce routing resources by considering the side effects that the routing of one connection has on another, and also has the ability to optimize the routing delays of time-critical connections. CGE has been used to obtain excellent routing results for several industrial circuits implemented in FPGAs with various routing architectures. The results show that CGE can route relatively large FPGAs in very close to the minimum number of tracks as determined by global routing, and it can successfully optimize the routing delays of time-critical connections. CGE has a linear run time over circuit size. >
---
paper_title: Fast module mapping and placement for datapaths in FPGAs

paper_content:

By tailoring a compiler tree-parsing tool for datapath module mapping, we produce good quality results for datapath synthesis in very fast run time. Rather than flattening the design to gates, we preserve the datapath structure; this allows exploitation of specialized datapath features in FPGAs, retains regularity, and also results in a smaller problem size. To further achive high mapping speed, we formulate the problem as tree covering and solve it efficiently with a linear-time dynamic programming algorithm. In a novel extension to the tree-covering algorithm, we perform module placement simultaneously with the mapping, still in linear time. Integrating placement has the potential to increase the quality of the result since we can optimize total delay including routing delays. To our knowledge this is the first effort to leverage a grammar-based tree covering tool for datapath module mapping. Further, it is the first work to integrate simultaneous placement with module mapping in a way that preserves linear time complexity.
---
paper_title: Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT

paper_content:

1. ABSTRACT lier BDD-based methods. Boolean-based routing transforms the geometric FPGA routing task into a single, large Boolean equation with the property that any assignment of input variables that “satisfies” the equation (that renders equation identically “1”) specifies a valid routing. The formulation has the virtue that it considers all nets simultaneously, and the absence of a satisfying assignment implies that the layout is unroutable. Initial Boolean-based approaches to routing used Binary Decision Diagrams (BDDs) to represent and solve the layout problem. BDDs, however, limit the size and complexity of the FPGAs that can be routed, leading these approaches to concentrate only on individual FPGA channels. In this paper, we present a new search-based Satisfiability (SAT) formulation that can handle entire FPGAs, routing all nets concurrently. The approach relies on a recently developed SAT engine (GRASP) that uses systematic search with conflict-directed non-chronological backtracking, capable of handling very large SAT instances. We present the first comparisons of search-based SAT routing results to other routers, and offer the first evidence that SAT methods can actually demonstrate the unroutability of a layout. Preliminary experimental results suggest that this approach to FPGA routing is more viable than ear1.1
---
paper_title: A methodology for fast FPGA floorplanning

paper_content:

Floorplanning is an important problem in FPGA circuit mapping. As FPGA capacity grows, new innovative approaches will be required for efficiently mapping circuits to FPGAs. In this paper we present a macro based floorplanning methodology suitable for mapping large circuits to large, high density FPGAs. Our method uses clustering techniques to combine macros into clusters, and then uses a tabu search based approach to place clusters while enhancing both circuit routability and performance. Our method is capable of handling both hard (fixed size and shape) macros and soft (fixed size and variable shape) macros. We demonstrate our methodology on several macro based circuit designs and compare the execution speed and quality of results with commercially available CAE tools. Our approach shows a dramatic speedup in execution time without any negative impact on quality.
---
paper_title: A New FPGA Technology Mapping Approach by Cluster Merging

paper_content:

In this paper, a new technology mapping method based on the cluster merging is proposed. It provides better global view on optimal technology mapping and formalization. In addition, it supports both MUX-based and LUT-based FPGA allowing various cost functions. Experimental results on MCNC benchmarks show that our approach produces the best results for MUX-based FPGA case in terms of cell count.
---
paper_title: Algorithms for an fpga switch module routing problem with application to global routing

paper_content:

We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGAs). This problem was first introduced by Zhu et al. (1993). They used it to evaluate the routability properties of switch modules which they proposed. Only an approximation algorithm for the problem was proposed by them. We give an optimal algorithm for the problem based on integer linear programming (ILP). Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems. We then propose a precomputation that eliminates the need to use ILP on-line. We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known. Thus, the switch module routing problem can be solved in polynomial time for these special cases. Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router. A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions.
---
paper_title: A fast routability-driven router for FPGAs

paper_content:

Three factors are driving the demand for rapid FPGA compilation. First, as FPGAs have grown in logic capacity, the compile computation has grown more quickly than the compute power of the available computers. Second, there exists a subset of users who are willing to pay for very high speed compile with a decrease in quality of result, and accordingly being required to use a larger FPGA or use more real-estate on a given FPGA than is otherwise necessary. Third, very high speed compile has been a long-standing desire of those using FPGA-based custom computing machines, as they want compile times at least closer to those of regular computers. This paper focuses on the routing phase of the compile process, and in particular on routability-driven routing (as opposed to timing-driven routing). We present a routing algorithm and routing tool that has three unique capabilities relating to very high-speed compile: For a “low stress” routing problem (which we define as the case where the track supply is at least 10% greater than the minimun number of tracks per channel actually needed to route a circuit) the routing time is very fast. For example, the routing phase (after the netlist is parsed and the routing graph is constructed) for a 20,000 LUT/FF pair circuit with 30% extra tracks is only 23 seconds on a 300 MHz Sparcstation. For low-stress routing problems the routing time is near-linear in the size of the circuit, and the linearity constant is very small: 1.1 ms per LUT/FF pair, or roughly 55,000 LUT/FF pairs per minute. For more difficult routing problems (where the track supply is close to the minimum needed) we provide a method that quickly identifies and subdivides this class into two sub-classes: (i) those circuits which are difficult (but possible) to route and will take significantly more time than low-stress problems, and (ii) those circuits which are impossible to route. In the first case the user can choose to continue or reduce the amount of logic; in the second case the user is forced to reduce the amount of logic or obtain a larger FPGA.
---
paper_title: SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays

paper_content:

It has become clear that large embedded configurable memory arrays will be essential in future FPGAs. Embedded arrays provide high-density high-speed implementations of the storage parts of circuits. Unfortunately, they require the FPGA vendor to partition the device into memory and logic resources at manufacture-time. This leads to a waste of chip area for customers that do not use all of the storage provided. This chip area need not be wasted, and can in fact be used very efficiently, if the arrays are configured as large multi-output ROMs, and used to implement logic. In order to efficiently use the embedded arrays in this way, a technology mapping algorithm that identifies parts of circuits that can be efficiently mapped to an embedded array is required. In this paper, we describe such an algorithm. The new tool, called SMAP, packs as much circuit information as possible into the available memory arrays, and maps the rest of the circuit into four-input lookup-tables. On a set of 29 sequential and combinational benchmarks, the tool is able to map, on average, 60 4-LUTs into a single 2-Kbit memory array. If there are 16 arrays available, it can map, on average, 358 4-LUTs to the 16 arrays.
---
paper_title: The programmable logic data book

paper_content:

Improvement to video-telephone systems allowing a called subscriber to have at his disposal on his television receiver screen, before he takes off his handset, information about the person who has initiated the call. Each subscriber station has a handset, a television camera, a television receiver and a character generator and is connected to a switching network by a telephone line, an incoming video line and an outgoing video line. Means are provided in the calling station for connecting to the outgoing video line the character generator when the calling subscriber takes down the handset and the television camera when video signals are detected on the incoming video line and in the called station for supplying with current the television receiver when ringing tone signals are detected on the telephone line.
---
paper_title: Cut ranking and pruning: enabling a general and efficient FPGA mapping solution

paper_content:

Cut enumeration is a common approach used in a number of FPGA synthesis and mapping algorithms for consideration of various possible LUT implementations at each node in a circuit. Such an approach is very general and flexible, but often suffers high computational complexity and poor scalability. In this paper, we develop several efficient and effective techniques on cut enumeration, ranking and pruning. These techniques lead to much better runtime and scalability of the cut-enumeration based algorithms; they can also be used to compute a tight lower-bound on the size of an area-minimum mapping solution. For area-oriented FPGA mapping, experimental results show that the new techniques lead to over 160X speed-up over the original optimal duplication-free mapping algorithm, achieve mapping solutions with 5-21% smaller area for heterogeneous FPGAs compared to those by Chortle-crf, MIS-pga-new, and TOS-TUM, yet with over 100X speed-up over MIS-pganew and TOS-TUM.
---
paper_title: Synthesis Methods for Field Programmable Gate Arrays

paper_content:

Field programmable gate arrays (FPGA ’s) reduce the turnaround time of application-spec@c integrated circuits from weeks to minutes. However, the high complexity of their architectures makes manual mapping of designs time consuming and error prone thereby offsetting any turnaround advantage. Consequently, effective design automation tools are needed to reduce design time. Among the most important is logic synthesis. While standard synthesis techniques could be used for FPGA’s, the quality of the synthesized designs is often unacceptable. As a result, much recent work has been devoted to developing logic synthesis tools targeted to different FPGA architectures. The paper surveys this work. The three most popular types of FPGA architectures are considered, namely those using logic blocks based on lookuptables, multiplexers and wide AND/OR arrays. The emphasis is on tools which attempt to minimize the area of the combinational logic part of a design since little work has been done on optimizing performance or routability, or on synthesis of the sequential part of a design. The different tools surveyed are compared using a suite of benchmark designs.
---
paper_title: VPR: A new packing, placement and routing tool for FPGA research

paper_content:

We describe the capabilities of and algorithms used in a ne w FPGA CAD tool, Versatile Place and Route (VPR). In terms of minimizing routing area, VPR outperforms all published FPGA place and route tools to which we can compare. Although the algorithms used are based on pre viously known approaches, we present several enhancements that improve run-time and quality. We present placement and routing results on a new set of lar ge circuits to allo w future benchmark comparisons of FPGA place and route tools on circuit sizes more typical of today’s industrial designs. VPR is capable of targeting a broad range of FPGA architectures, and the source code is publicly available. It and the associated netlist translation / clustering tool VPACK ha ve already been used in a number of research projects w orldwide, and should be useful in many areas of FPGA architecture research.
---
paper_title: Technology mapping for FPGAs with embedded memory blocks

paper_content:

Modern field programmable gate arrays (FPGAs) provide embedded memory blocks (EMBs) to be used as on-chip memories. In this paper, we explore the possibility of using EMBs to implement logic functions when they are not used as on-chip memory. We propose a general technology mapping problem for FPGAs with EMBs for area and delay minimization and develop an efficient algorithm based on the concepts of Maximum Fanout Free Cone (MFFC) [3] and Maximum Fanout Free Subgraph (MFFS) [7], named EMB_Pack, which minimizes the area after or before technology mapping by using EMBs while maintaining the circuit delay. We have tested EMB_Pack on MCNC benchmarks on Altera's FLEX10K device family [1]. The experimental results show that compared with the original mapped circuits generated from CutMap [5] without using EMBs, EMB_Pack as postprocessing can further reduce up to 10% of the area on the mapped circuits while maintaining the layout delay by making efficient use of available EMB resources. Compared with CutMap-e without using EMBs, EMB_Pack as pre-mapping processing followed by CutMap-e can reduce 6% of the area while maintaining the circuit optimal delay.
---
paper_title: A Performance and Routability Driven Router for FPGAs Considering Path Delays

paper_content:

This paper presents a new performance and routability driven router for symmetrical array based Field Programmable Gate Arrays (FPGAs). The objectives of our proposed routing algorithm are twofold: (1) improve the routability of the design (i.e., minimize the maximumrequired routing channel density) and (2) improve the overall performance of the design (i.e., minimize the overall path delay). Initially, nets are routed sequentially according to their criticalities and routabilities. The nets/paths violating the routing-resource and timing constraints are then resolved iteratively by a rip-up-and-rerouter, which is guided by a simulated evolution based optimization technique. The proposed algorithm considers the path delays and routability throughout the entire routing process. Experimental results show that our router can significantly improve routability and reduce delay over many existing routing algorithms.
---
paper_title: VLSI cell placement techniques

paper_content:

VLSI cell placement problem is known to be NP complete. A wide repertoire of heuristic algorithms exists in the literature for efficiently arranging the logic cells on a VLSI chip. The objective of this paper is to present a comprehensive survey of the various cell placement techniques, with emphasis on standard cell and macro placement. Five major algorithms for placement are discussed: simulated annealing, force-directed placement, min-cut placement, placement by numerical optimization, and evolution-based placement. The first two classes of algorithms owe their origin to physical laws, the third and fourth are analytical techniques, and the fifth class of algorithms is derived from biological phenomena. In each category, the basic algorithm is explained with appropriate examples. Also discussed are the different implementations done by researchers.
---
paper_title: Performance driven floorplanning for FPGA based designs

paper_content:

Increasing design densities on large FPGAs and greater demand for performance, has calledfor special purpose tools like floorplanner, performance driven router, and more. In this paper we present a floorplanning based design mapping solution that is capable of mapping macro cell based designs as well as hierarchicaldesigns on FPGAs. The mapping solution has been tested extensively on a large collection of designs. We not only outperform state of the art CAE tools from industry in terms of execution time but also achieve much better performance in terms of timing. These methods are especially suitable for mapping designs on very large FPGAs.
---
paper_title: Software technologies for reconfigurable systems

paper_content:

FPGA-based systems are a significant area of computing, providing a high-performance implementation substrate for many different applications. However, the key to harnessing their power for most domains is developing mapping tools for automatically transforming a circuit or algorithm into a configuration for the system. In this paper we review the current state-of-the-art in mapping tools for FPGA-based systems, including single-chip and multi-chip mapping algorithms for FPGAs, software support for reconfigurable computing, and tools for run-time reconfigurability. We also discuss the challenges for the future, pointing out where development is still needed to let reconfigurable systems achieve all of their promise.
---
paper_title: New performance-driven FPGA routing algorithms

paper_content:

Motivated by the goal of increasing the performance of FPGA-based designs, we propose new Steiner and arborescence FPGA routing algorithms. Our Steiner tree constructions significantly outperform the best known ones and have provably good performance bounds. Our arborescence heuristics produce routing solutions with optimal source-sink pathlengths, and with wirelength on par with the best existing Steiner tree heuristics. We have incorporated these algorithms into an actual FPGA router, which routed a number of industrial circuits using channel width considerably smaller than is achievable by previous routers. Our routing results for both the 3000 and 4000-series Xilinx parts are currently the best known in the Literature.
---
paper_title: Trading quality for compile time: ultra-fast placement for FPGAs

paper_content:

The demand for high-speed FPGA compilation tools has occured for three reasons: first, as FPGA device capacity has grown, the computation time devoted to placement and routing has grown more dramatically than the compute power of the available computers. Second, there exists a subset of users who are willing to accept a reduction in the quality of result in exchange for a high-speed compilation. Third, high-speed compile has been a long-standing desire of users of FPGA-based custom computing machines, since their compile time requirements are ideally closer to those of regular computers. This paper focuses on the placement phase of the compile process, and presents an ultra-fast placement algorithm targeted to FPGAs. The algorithm is based on a combination of multiple-level, bottom-up clustering and hierarchical simulated annealing. It provides superior area results over a known high-quality placement tool on a set of large benchmark circuits, when both are restricted to a short run time. For example, it can generate a placement for a 100,000-gate circuit in 10 seconds on a 300 MHz Sun UltraSPARC workstation that is only 33% worse than a high-quality placement that takes 524 seconds using a pure simulated annealing implementation. In addition, operating in its fastest mode, this tool can provide an accurate estimate of the wirelength achievable with good quality placement. This can be used, in conjunction with a routing predictor, to very quickly determine the routability of a given circuit on a given FPGA device.
---
paper_title: General modeling and technology-mapping technique for LUT-based FPGAs

paper_content:

We present a general approach to the FPGA technology mapping problem that applies to any logic block composed of lookup tables (LUTs) and can yield optimal solutions. The connections between LUTs of a logic block are modeled by virtual switches, which define a set of multiple-LUT blocks (MLBs) called an MLB-basis. We identify the MLB-bases for various commercial logic blocks. Given a n MLB-basis, we formulate FPGA mapping as a mixed integer linear programming (MILP) problem to achieve both the generality and the optimality objectives. We solve the MILP models using a general-purpose MILP solver, and present the results of mapping some ISCAS.85 benchmark circuits with a variety of commercial FPGAs. Circuits of a few hundred gates can be mapped in reasonable time using the MILP approach directly. Larger circuits can be handled by partitioning them prior to technology mapping. We show that optimal or provably near-optimal solutions can be obtained for the large ISCAS.85 benchmark circuits using partitions defined by their high-level functions.
---
paper_title: PathFinder: a negotiation-based performance-driven router for FPGAs

paper_content:

Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm that converges to a solution in which all signals are routed while achieving close to the optimal performance allowed by the placement. Routability is achieved by forcing signals to negotiate for a resource and thereby determine which signal needs the resource most. Delay is minimized by allowing the more critical signals a greater say in this negotiation. Because PathFinder requires only a directed graph to describe the architecture of routing resources, it adapts readily to a wide variety of FPGA architectures such as Triptych, Xilinx 3000 and mesh-connected arrays of FPGAs. The results of routing ISCAS benchmarks on the Triptych FPGA architecture show an average increase of only 4.5% in critical path delay over the optimum delay for a placement. Routes of ISCAS benchmarks on the Xilinx 3000 architecture show a greater completion rate than commercial tools, as well as 11% faster implementations.
---
paper_title: Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation

paper_content:

In this paper, we developed Boolean matching techniques for complex programmable logic blocks (PLBs) in LUT-based FPGAs. A complex PLB can not only be used as a K -input LUT, but also can implement some wide functions of more than K variables. We apply previous and develop new functional decomposition methods to match wide functions to PLBs. We can determine exactly whether a given wide function can be implemented with a XC4000 CLB or other three PLB architectures (including the XC5200 CLB). We evaluate functional capabilities of the four PLB architectures on implementing wide functions in MCNC benchmarks. Experiments show that the XC4000 CLB can be used to implement up to 98% of 6-cuts and 88% of 7-cuts in MCNC benchmarks, while two of the other three PLB architectures have a smaller cost in terms of logic capability per silicon area. Our results are useful for designing future logic unit architectures in LUT based FPGAs.
---
paper_title: Acceleration of an FPGA router

paper_content:

The authors describe their experience and progress in accelerating an FPGA router. Placement and routing is undoubtedly the most time-consuming process in automatic chip design or configuring programmable logic devices as reconfigurable computing elements. Their goal is to accelerate routing of FPGAs by 10 fold with a combination of processor clusters and hardware acceleration. Coarse-grain parallelism is exploited by having several processors route separate groups of nets in parallel. A hardware accelerator is presented which exploits the fine-grain parallelism in routing individual nets.
---
paper_title: Technology mapping of heterogeneous LUT-based FPGAs

paper_content:

New techniques have been developed for the technology mapping of FPGAs containing more than one size of look-up table. The Xil inx 4000 series is one such family of devices. These have a very large share of the FPGA market, and yet the associated technology mapping problem has hardly been addressed in the literature. Our method extends the standard techniques of functional decomposition and network covering. For the decomposition, we have extended the conventional binpacking (cube-packing) algorithms so that it produces two sizes of bins. We have also enhanced it to explore several packing possibilities, and include cube division and cascading of nodes. The covering step is based on the concept of flow networks and cut-computation. We devised a theory that reduces the flow network sizes so that a dynamic programming approach can be used to compute the feasible cuts in the network. An iterative selection algorithm can then be used to compute the set cover of the network. Experimental results show good performances for the Xilinx 4K devices (about 25% improvement over MOFL and 10% over comparable algorithms in SIS in terms of CLBs).
---
paper_title: An Efficient Algorithm for Performance-Optimal FPGA Technology Mapping with Retiming

paper_content:

It is known that most field programmable gate array (FPGA) mapping algorithms consider only combinational circuits. Pan and Liu [1996] recently proposed a novel algorithm, named SeqMapII, of technology mapping with retiming for clock period minimization. Their algorithm, however, requires O(K/sup 3/n/sup 5/log(Kn/sup 2/)logn) run time and O(K/sup 2/n/sup 2/) space for sequential circuits with n gates. In practice, these requirements are too high for targeting K-lookup-table-based FPGA's implementing medium or large designs. In this paper, we present three strategies to improve the performance of the SeqMapII algorithm significantly. Our algorithm works in O(K/sup 2/nln|P/sub v/|logn) run time and O(K|P/sub v/|) space, where n/sub l/ is the number of labeling iterations and |P/sub v/| is the size of the partial flow network. In practice, both n/sub l/ and |P/sub v/| are less than n. Area minimization is also considered in our algorithm based on efficient low-cost K-cut computation.
---
paper_title: Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams

paper_content:

This paper proposes an efficient algorithm for technology mapping targeting table look-up (TLU) blocks. It is capable of minimizing either the number of TLUs used or the depth of the produced circuit. Our approach consists of two steps. First a network of super nodes, is created. Next a Boolean function of each super node with an appropriate don't care set is decomposed into a network of TLUs. To minimize the circuit's depth, several rules are applied on the critical portion of the mapped circuit.
---
paper_title: Timing driven floorplanning on programmable hierarchical targets

paper_content:

The goal of this paper is to perform a timing optimization of a circuit described b y a network of cells on a target structure whose connection delays ha v ediscrete values follo wing its hierarch y. The circuits is modelled by a set of timed cones whose delay histograms allow their classification into critical, potential critical and neutral cones according to predicted delays. The floorplanning is then guided b y this cone structuring and has two innov ativ e features:first, it is shown that the placement of the elements of the neutral cones has no impact on timing results, th us a significant reduction is obtained; second, despite a greedy approach, a near optimal floorplan is achieved in a large number of examples.
---
paper_title: NAPA C: compiling for a hybrid RISC/FPGA architecture

paper_content:

Hybrid architectures combining conventional processors with configurable logic resources enable efficient coordination of control with datapath computation. With integration of the two components on a single device, loop control and data-dependent branching can be handled by the conventional processor. While regular datapath computation occurs on the configurable hardware. This paper describes a novel pragma-based approach to programming such hybrid devices. The NAPA C language provides pragma directives so that the programmer (or an automatic partitioner) can specify where data is to reside and where computation is to occur with statement-level granularity. The NAPA C compiler, targeting National Semiconductor's NAPA1000 chip, performs semantic analysis of the pragma-annotated program and co-synthesizes a conventional program executable combined with a configuration bit stream for the adaptive logic. Compiler optimizations include synthesis of hardware pipelines from pipelineable loops.
---
paper_title: An operating system for custom computing machines based on the Xputer paradigm

paper_content:

The paper presents an operating system (OS) for custom computing machines (CCMs) based on the Xputer paradigm. Custom computing tries to combine traditional computing with programmable hardware, attempting to gain from the benefits of both adaptive software and optimized hardware. The OS running as an extension to the actual host OS allows a greater flexibility in deciding what parts of the application should run on the configurable hardware with structural code and what on the host-hardware with conventional software. This decision can be taken late - at run-time - and dynamically, in contrast to early partitioning and deciding at compile-time as used currently on CCMs. Thus the CCM can be used concurrently by multiple users or applications without knowledge of each other. This raises programming and using CCMs to levels close to modem OSes for sequential von Neumann processors.
---
paper_title: The Garp architecture and C compiler

paper_content:

Various projects and products have been built using off-the-shelf field-programmable gate arrays (FPGAs) as computation accelerators for specific tasks. Such systems typically connect one or more FPGAs to the host computer via an I/O bus. Some have shown remarkable speedups, albeit limited to specific application domains. Many factors limit the general usefulness of such systems. Long reconfiguration times prevent the acceleration of applications that spread their time over many different tasks. Low-bandwidth paths for data transfer limit the usefulness of such systems to tasks that have a high computation-to-memory-bandwidth ratio. In addition, standard FPGA tools require hardware design expertise which is beyond the knowledge of most programmers. To help investigate the viability of connected FPGA systems, the authors designed their own architecture called Garp and experimented with running applications on it. They are also investigating whether Garp's design enables automatic, fast, effective compilation across a broad range of applications. They present their results in this article.
---
paper_title: A hardware/software partitioning algorithm for custom computing machines

paper_content:

In this paper an Hardware/Software partitioning algorithm is presented. Appropriate cost and performance estimation functions were developed, as well, as techniques for their automated calculation. The partitioning algorithm that explores the parallelism in acyclic code regions is part of a larger tool kit specific for custom computing machines. The tool kit includes a parallelising compiler, an hardware/software partitioning program, as well as, a set of programs for performance estimation and system implementation. It speeds up the computationally intensive tasks using a FPGA based processing platform to augment the functionality of the processor with new operations and parallel capacities. An example was used to demonstrate the proposed partitioning techniques.
---
paper_title: A CAD Suite for High-Performance FPGA Design

paper_content:

This paper describes the current status of a suite of CAD tools designed specifically for use by designers who are developing high-performance configurable-computing applications. The basis of this tool suite is JHDL, a design tool originally conceived as a way to experiment with Run-Time Reconfigured (RTR) designs. However, what began as a limited experiment to model RTR designs with Java has evolved into a comprehensive suite of design tools and verification aids, with these tools being used successfully to implement high-performance applications in Automated Target Recognition (ATR), sonar beamforming, and general image processing on configurable-computing systems.
---
paper_title: Fast integrated tools for circuit design with FPGAs

paper_content:

To implement high-density and high-speed FPGA circuits, designers need tight control over the circuit implementation process. However, current design tools are unsuited for this purpose as they lack fast turnaround times, interactiveness, and integration. We present a system for the Xilinx XC6200 FPGA, which addresses these issues. It consists of a suite of tightly integrated tools for the XC6200 architecture centered around an architecture-independent tool framework. The system lets the designer easily intervene at various stages of the design process and features design cycle times (from an HDL specification to a complete layout) in the order of seconds.
---
paper_title: NAPA C: compiling for a hybrid RISC/FPGA architecture

paper_content:

Hybrid architectures combining conventional processors with configurable logic resources enable efficient coordination of control with datapath computation. With integration of the two components on a single device, loop control and data-dependent branching can be handled by the conventional processor. While regular datapath computation occurs on the configurable hardware. This paper describes a novel pragma-based approach to programming such hybrid devices. The NAPA C language provides pragma directives so that the programmer (or an automatic partitioner) can specify where data is to reside and where computation is to occur with statement-level granularity. The NAPA C compiler, targeting National Semiconductor's NAPA1000 chip, performs semantic analysis of the pragma-annotated program and co-synthesizes a conventional program executable combined with a configuration bit stream for the adaptive logic. Compiler optimizations include synthesis of hardware pipelines from pipelineable loops.
---
paper_title: JHDL-an HDL for reconfigurable systems

paper_content:

JHDL is a design tool for reconfigurable systems that allows designers to express circuit organizations that dynamically change over time in a natural way, using only standard programming abstractions found in object-oriented languages. JHDL manages FPGA resources in a manner that is similar to the way object-oriented languages manage memory: circuits are treated as distinct objects and a circuit is configured onto a configurable computing machine (CCM) by invoking its constructor effectively "constructing " an instance of the circuit onto the reconfigurable platform just as object instances are allocated in memory with conventional object-oriented languages. This approach of using object constructors/destructors to control the circuit lifetime on a CCM is a powerful technique that naturally leads to a dual simulation/execution environment where a designer can easily switch between either software simulation or hardware execution on a CCM with a single application description. Moreover JHDL supports dual hardware/software execution; parts of the application described using JHDL circuit constructs can be executed on the CCM while the remainder of the application the-GUI for example-can run on the CCM host. Based on an existing programming language (Java), JHDL requires no language extensions and can be used with any standard Java 1.1 distribution.
---
paper_title: The Garp architecture and C compiler

paper_content:

Various projects and products have been built using off-the-shelf field-programmable gate arrays (FPGAs) as computation accelerators for specific tasks. Such systems typically connect one or more FPGAs to the host computer via an I/O bus. Some have shown remarkable speedups, albeit limited to specific application domains. Many factors limit the general usefulness of such systems. Long reconfiguration times prevent the acceleration of applications that spread their time over many different tasks. Low-bandwidth paths for data transfer limit the usefulness of such systems to tasks that have a high computation-to-memory-bandwidth ratio. In addition, standard FPGA tools require hardware design expertise which is beyond the knowledge of most programmers. To help investigate the viability of connected FPGA systems, the authors designed their own architecture called Garp and experimented with running applications on it. They are also investigating whether Garp's design enables automatic, fast, effective compilation across a broad range of applications. They present their results in this article.
---
paper_title: The Transmogrifier C hardware description language and compiler for FPGAs

paper_content:

The Transmogrifier C hardware description language is almost identical to the C programming language, making it attractive to the large community of C-language programmers. This paper describes the semantics of the language and presents a Transmogrifier C compiler that targets the Xilinx 4000 FPGA. The compiler is operational and has produced several working circuits, including a graphics display driver.
---
paper_title: Exploiting reconfigurability through domain-specific systems

paper_content:

Domain-specific systems represent an important opportunity for FPGA-based systems. They provide a way to exploit the low-level flexibility of the device through the use of domain-specific libraries of specialized circuit elements. Moreover, reconfigurability of the FPGAs is also exploited by reusing these circuit elements to implement a wide variety of applications within the specific domain. Application areas such as image processing, signal processing, graphics, DNA analysis, and other areas are important areas that can use this approach to achieve high levels of performance at reasonable cost. Unfortunately, current CAD tools are a relatively poor match for the design needs of such systems. However, some of the additions listed in this paper should not be too difficult to implement and they would greatly ease the design of such systems.
---
paper_title: An Universal CLA Adder Generator for SRAM-Based FPGAs

paper_content:

In this paper we present an universal module generator for hierarchical carry lookahead adders of any word length which is suitable for most SRAM-based FPGA architectures. We introduce a generic model of SRAM-based FPGAs taking different configurations of the logic blocks into account. Considering the logical structure of CLA adders we efficiently perform technology mapping including an adaptive structure generation process as well as signal flow driven placement and partitioning which is necessary if the macro exceeds the limitations given by the FPGA's pin or CLB count.
---
paper_title: A Case Study of Partially Evaluated Hardware Circuits: Key-Specific DES

paper_content:

FPGA based data encryption provides greater flexibility than ASICs and higher performance than software. Because FPGAs can be reprogrammed, they allow a single integrated circuit to efficiently implement multiple encryption algorithms. Furthermore, the ability to program FPGAs at runtime can be used to improve the performance through dynamic optimization. This paper describes the application of partial evaluation to an implementation of the Data Encryption Standard (DES). Each end user of a DES session shares a secret key, and this knowledge can be used to improve circuit performance. Key-specific encryption circuits require fewer resources and have shorter critical paths than the completely general design. By applying partial evaluation to DES on a Xilinx XC4000 series device we have reduced the CLB usage by 45% and improved the encryption bandwidth by 35%.
---
paper_title: Automated field-programmable compute accelerator design using partial evaluation

paper_content:

This paper describes a compiler that generates both hardware and controlling software for field-programmable compute accelerators. By analyzing a source program together with part of its input, the compiler generates VHDL descriptions of functional units that are mapped on a set of FPGA chips and an optimized sequence of control constructions that run on the customized machine. The primary technique employed in the compiler is partial evaluation, which is used to transform an application program together with part of its input into an optimized program. Further phases in the compiler identify pieces of the program that can be realized in hardware and schedule computations to execute on the resulting hardware. Finally, a set of specialized functional units generated by the compiler for a timing simulation program is used to demonstrate the approach.
---
paper_title: Run-time parameterised circuits for the Xilinx XC6200

paper_content:

Current design tools support parameterisation of circuits, but the parameters are fixed at compile-time. In contrast, the circuits discussed in this paper fix their parameters at run-time. Run-time parameterised circuits can potentially out-perform custom VLSI hardware by optimising the FPGA circuit for a specific instance of a problem rather than for a general class of problem. This paper discusses the design of run-time parameterised circuits, and presents a study of run-time parameterised circuits for finite field operations on the Xilinx XC6200. The paper includes a comparison with implementation on a self-timed version of the XC6200 architecture, which illustrates the potential benefits of self-timing for dynamically reconfigurable systems.
---
paper_title: Parallelizing Applications into Silicon

paper_content:

The next decade of computing will be dominated by embedded systems, information appliances and application-specific computers. In order to build these systems, designers will need high-level compilation and CAD tools that generate architectures that effectively meet the needs of each application. In this paper we present a novel compilation system that allows sequential programs, written in C or FORTRAN, to be compiled directly into custom silicon or reconfigurable architectures. This capability is also interesting because trends in computer architecture are moving towards more reconfigurable hardware-like substrates, such as FPGA based systems. Our system works by successfully combining two resource-efficient computing disciplines: Small Memories and Virtual Wires. For a given application, the compiler first analyzes the memory access patterns of pointers and arrays in the program and constructs a partitioned memory system made up of many small memories. The computation is implemented by active computing elements that are spatially distributed within the memory array. A space-time scheduler assigns instructions to the computing elements in a way that maximizes locality and minimizes physical communication distance. It also generates an efficient static schedule for the interconnect. Finally, specialized hardware for the resulting schedule of memory accesses, wires, and computation is generated as a multi-process state machine in synthesizable Verilog. With this system, implemented as a set of SUIF compiler passes, we have successfully compiled programs into hardware and achieve specialization performance enhancements by up to an order of magnitude versus a single general purpose processor. We also achieve additional parallelization speedups similar to those obtainable using a tightly-interconnected multiprocessor.
---
paper_title: Fast compilation for pipelined reconfigurable fabrics

paper_content:

In this paper we describe a compiler which quickly synthesizes high quality pipelined datapaths for pipelined reconfigurable devices. The compiler uses the same internal representation to perform synthesis, module generation, optimization, and place and route. The core of the compiler is a linear time place and route algorithm more than two orders of magnitude faster than traditional CAD tools. The key behind our approach is that we never backtrack, rip-up, or re-route. Instead, the graph representing the computation is preprocessed to guarantee routability by inserting lazy noops. The preprocessing steps provides enough information to make a greedy strategy feasible. The compilation speed is approximately 3000 bit-operations/second (on a PII/400Mhz) for a wide range of applications. The hardware utilization averages 60% on the target device, PipeRench.
---
paper_title: Specifying and Compiling Applications for RAPID

paper_content:

Efficient, deeply pipelined implementations exist for a wide variety of important computation-intensive applications, and many special-purpose hardware machines have been built that take advantage of these pipelined computation structures. While these implementations achieve high performance, this comes at the expense of flexibility. On the other hand, flexible architectures proposed thus far have not been very efficient. RaPiD is a reconfigurable pipelined datapath architecture designed to provide a combination of performance and flexibility for a variety of applications. It uses a combination of static and dynamic control to efficiently implement pipelined computations. This control, however, is very complicated; specifying a computation's control circuitry directly would be prohibitively difficult. This paper describes how specifications of a pipelined computation in a suitably high-level language are compiled into the control required to implement that computation in the RaPiD architecture. The compiler extracts a statically configured datapath from this description, identifies the dynamic control signals required to execute the computation, and then produces the control program and decoding structure that generates these dynamic control signals.
---
paper_title: NAPA C: compiling for a hybrid RISC/FPGA architecture

paper_content:

Hybrid architectures combining conventional processors with configurable logic resources enable efficient coordination of control with datapath computation. With integration of the two components on a single device, loop control and data-dependent branching can be handled by the conventional processor. While regular datapath computation occurs on the configurable hardware. This paper describes a novel pragma-based approach to programming such hybrid devices. The NAPA C language provides pragma directives so that the programmer (or an automatic partitioner) can specify where data is to reside and where computation is to occur with statement-level granularity. The NAPA C compiler, targeting National Semiconductor's NAPA1000 chip, performs semantic analysis of the pragma-annotated program and co-synthesizes a conventional program executable combined with a configuration bit stream for the adaptive logic. Compiler optimizations include synthesis of hardware pipelines from pipelineable loops.
---
paper_title: Automated field-programmable compute accelerator design using partial evaluation

paper_content:

This paper describes a compiler that generates both hardware and controlling software for field-programmable compute accelerators. By analyzing a source program together with part of its input, the compiler generates VHDL descriptions of functional units that are mapped on a set of FPGA chips and an optimized sequence of control constructions that run on the customized machine. The primary technique employed in the compiler is partial evaluation, which is used to transform an application program together with part of its input into an optimized program. Further phases in the compiler identify pieces of the program that can be realized in hardware and schedule computations to execute on the resulting hardware. Finally, a set of specialized functional units generated by the compiler for a timing simulation program is used to demonstrate the approach.
---
paper_title: Multi-FPGA systems

paper_content:

Multi-FPGA systems are a growing area of research. They offer the potential to deliver high performance solutions to general computing tasks, especially for the prototyping of digital logic. However, to realize this potential requires a flexible, powerful hardware substrate and a complete, high quality and high performance automatic mapping system. ::: The primary goal of this thesis is to offer a disciplined look at the issues and requirements of multi-FPGA systems. This includes an in-depth study of some of the hardware and software issues of multi-FPGA systems, especially logic partitioning and mesh routing topologies, as well as investigations into problems that have largely been ignored, including pin assignment and architectural support for logic emulator interfaces. We also present Springbok, a novel rapid-prototyping system for board-level designs.
---
paper_title: I/O and performance tradeoffs with the FunctionBus during multi-FPGA partitioning

paper_content:

We improve upon a new approach for automatically partitioning a system among several FPGAs. The new approach partitions a system's functional specification, now commonly available, rather than its structural implementation. The improvement uses a bus, the FunctionBus, for implementing function calls among FPGA's, The bus can be used with any number of and its protocol uses only a small amount of existing FPGA hardware, requiring no special hardware. While functional rather than structural partitioning can substantially reduce the number of input/output pins using (I/O) the FunctionBus takes such reduction even further. In particular, performance and I/0can be traded-off by varying the bus size, as demonstrated using several examples.
---
paper_title: Pin Assignment for Multi-FPGA Systems

paper_content:

Multi-FPGA systems have tremendous potential, providing a high-performance computing substrate for many different applications. One of the keys to achieving this potential is a complete, automatic mapping solution that creates high-quality mappings in the shortest possible time. In this paper, we consider one step in this process, the assignment of inter-FPGA signals to specific I/O pins on the FPGAs in a multi-FPGA system. We show that this problem can neither be handled by pin assignment methods developed for other applications nor standard routing algorithms. Although current mapping systems ignore this issue, we show that an intelligent pin assignment method can achieve both quality and mapping speed improvements over random approaches. Intelligent pin assignment methods already exist for multi-FPGA systems, but are restricted to topologies where logic-bearing FPGAs cannot be directly connected. In this paper, we provide three new algorithms for the pin assignment of multi-FPGA systems with arbitrary topologies. We compare these approaches on several mappings to current multi-FPGA systems, and show that the force-directed approach produces better mappings, in significantly shorter time, than any of the other approaches.
---
paper_title: Using cone structures for circuit partitioning into FPGA packages

paper_content:

Circuit designers and high-level synthesis tools have traditionally used circuit hierarchy to partition circuits into packages. However hierarchical partitioning can not be easily performed if hierarchical blocks have too large a size or too many I-Os. This problem becomes more frequent with field-programmable gate arrays (FPGAs) which commonly have small size limits and up to ten times smaller I-O pin limits. An I-O bottleneck often occurs which during circuit partitioning means more required packages and more ordinary signal wires crossing between the packages. More critical timing paths between packages are cut and circuit operational frequencies are drastically reduced. In this paper, two new partitioning algorithms are presented that use cone structures to partition large hierarchical blocks into FPGA's. Cone structures are minimum cut partitioning structures for netlists with low fanout, and clustering structures for partitioning netlists with high fanout. Cone structures also allow for full containment of critical paths. When used with good merging and cutting strategies, results show the cone partitioning algorithms given here produces fewer FPGG partitions than min-cut with good performance.
---
paper_title: Automatic mapping of algorithms onto multiple FPGA-SRAM modules

paper_content:

This paper describes the processes that have been developed to allow the automatic mapping of technology independent algorithms onto a network of reconfigurable hardware modules. The VHDL language is used at the behavioural level of abstraction to describe the algorithm. Each reconfigurable hardware module comprises of a single FPGA and SRAM. A mesh configuration of these modules provides the resources for data manipulation and data storage required by the algorithm. By pre-processing the algorithm prior to synthesis, and then performing network partitioning on the synthesised netlist, a hardware implementation is realised on multiple modules. This approach means that an algorithm may be mapped onto a versatile hardware system which is not constrained by the limitations of the target technology.
---
paper_title: Virtual wires: overcoming pin limitations in FPGA-based logic emulators

paper_content:

Existing FPGA-based logic emulators only use a fraction of potential communication bandwidth because they dedicate each FPGA pin (physical wire) to a single emulated signal (logical wire). Virtual wires overcome pin limitations by intelligently multiplexing each physical wire among multiple logical wires and pipelining these connections at the maximum clocking frequency of the FPGA. A virtual wire represents a connection from a logical output on one FPGA to a logical input on another FPGA. Virtual wires not only increase usable bandwidth, but also relax the absolute limits imposed on gate utilization. The resulting improvement in bandwidth reduces the need for global interconnect, allowing effective use of low dimension inter-chip connections (such as nearest-neighbor). Nearest-neighbor topologies, coupled with the ability of virtual wires to overlap communication with computation, can even improve emulation speeds. The authors present the concept of virtual wires and describe their first implementation, a 'softwire' compiler which utilizes static routing and relies on minimal hardware support. Results from compiling netlists for the 18 K gate Sparcle microprocessor and the 86 K gate Alewife Communications and Cache Controller indicate that virtual wires can increase FPGA gate utilization beyond 80 percent without a significant slowdown in emulation speed. >
---
paper_title: Software technologies for reconfigurable systems

paper_content:

FPGA-based systems are a significant area of computing, providing a high-performance implementation substrate for many different applications. However, the key to harnessing their power for most domains is developing mapping tools for automatically transforming a circuit or algorithm into a configuration for the system. In this paper we review the current state-of-the-art in mapping tools for FPGA-based systems, including single-chip and multi-chip mapping algorithms for FPGAs, software support for reconfigurable computing, and tools for run-time reconfigurability. We also discuss the challenges for the future, pointing out where development is still needed to let reconfigurable systems achieve all of their promise.
---
paper_title: TIERS: Topology independent pipelined routing and scheduling for VirtualWire compilation

paper_content:

TIERS is a new pipelined routing and scheduling algorithm implemented in a complete VirtualWire TM compilation and synthesis system. TIERS is described and compared to prior work both analytically and quantitatively. TIERS improves system speed by as much as a factor of 2.5 over prior work. TIERS routing results for both Altera and Xilinx based FPGA systems are provided.
---
paper_title: Multiterminal net routing for partial crossbar-based multi-FPGA systems

paper_content:

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.
---
paper_title: Improving simulation accuracy in design methodologies for dynamically reconfigurable logic systems

paper_content:

This paper presents a new approach to the simulation of Dynamically Reconfigurable Logic (DRL) systems, which offers better accuracy of modelling dynamic reconfiguration than previously reported simulation techniques. Our method, named Clock Morphing, is based on modelling dynamic reconfiguration via a reconfigured module clock signal while using a dedicated signal value to indicate dynamic reconfiguration. We also discuss problems associated with the other DRL simulation techniques, describe the main principles of the proposed simulation method and evaluate its feasibility by implementing of a Clock Morphing based DRL simulation in VHDL.
---
paper_title: A CAD Suite for High-Performance FPGA Design

paper_content:

This paper describes the current status of a suite of CAD tools designed specifically for use by designers who are developing high-performance configurable-computing applications. The basis of this tool suite is JHDL, a design tool originally conceived as a way to experiment with Run-Time Reconfigured (RTR) designs. However, what began as a limited experiment to model RTR designs with Java has evolved into a comprehensive suite of design tools and verification aids, with these tools being used successfully to implement high-performance applications in Automated Target Recognition (ATR), sonar beamforming, and general image processing on configurable-computing systems.
---
paper_title: A Simulation Tool for Dynamically Reconfigurable Field Programmable Gate Arrays

paper_content:

The emergence of static memory-based field programmable gate arrays (FPGAs) that are capable of being dynamically reconfigured, i.e., partially reconfigured while active, has initiated research into new methods of digital systems synthesis. At present, however, there are virtually no specific CAD tools to support the design and investigation of digital systems using dynamic reconfiguration. This paper reports on an investigation of new CAD tools and the development of a new simulation technique, called dynamic circuit switching (DCS), for dynamically reconfigurable systems. The principles of DCS are presented and examples of its application are described.
---
paper_title: Debugging techniques for dynamically reconfigurable hardware

paper_content:

Testing dynamically reconfigurable systems imposes new challenges which require special treatment. We present tools and techniques we developed for debugging a dynamically reconfigurable system that performs run-time constant propagation optimisations. An application for monitoring the effect of run-time specialisation is presented and we show how we adapted standard testability techniques to evaluate the performance of specialised circuits. We also outline how NDLs that capture reconfiguration at a high level can assist with debugging.
---
paper_title: JHDL-an HDL for reconfigurable systems

paper_content:

JHDL is a design tool for reconfigurable systems that allows designers to express circuit organizations that dynamically change over time in a natural way, using only standard programming abstractions found in object-oriented languages. JHDL manages FPGA resources in a manner that is similar to the way object-oriented languages manage memory: circuits are treated as distinct objects and a circuit is configured onto a configurable computing machine (CCM) by invoking its constructor effectively "constructing " an instance of the circuit onto the reconfigurable platform just as object instances are allocated in memory with conventional object-oriented languages. This approach of using object constructors/destructors to control the circuit lifetime on a CCM is a powerful technique that naturally leads to a dual simulation/execution environment where a designer can easily switch between either software simulation or hardware execution on a CCM with a single application description. Moreover JHDL supports dual hardware/software execution; parts of the application described using JHDL circuit constructs can be executed on the CCM while the remainder of the application the-GUI for example-can run on the CCM host. Based on an existing programming language (Java), JHDL requires no language extensions and can be used with any standard Java 1.1 distribution.
---
paper_title: The design and implementation of a context switching FPGA

paper_content:

Dynamic reconfiguration of field programmable gate arrays (FPGAs) has recently emerged as the next step in reconfigurable computing. Sanders, A Lockheed Martin Company, is developing the enabling technology to exploit dynamic reconfiguration. The device being developed is capable of storing four configurations on-chip and switching between them on a clock cycle basis. Configurations can be loaded while other contexts are active. A powerful cross-context data sharing mechanism has been implemented. The current status of this work and future work are described.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: The design and implementation of a context switching FPGA

paper_content:

Dynamic reconfiguration of field programmable gate arrays (FPGAs) has recently emerged as the next step in reconfigurable computing. Sanders, A Lockheed Martin Company, is developing the enabling technology to exploit dynamic reconfiguration. The device being developed is capable of storing four configurations on-chip and switching between them on a clock cycle basis. Configurations can be loaded while other contexts are active. A powerful cross-context data sharing mechanism has been implemented. The current status of this work and future work are described.
---
paper_title: DPGA utilization and application

paper_content:

Dynamically Programmable Gate Arrays (DPGAs) are programmable arrays which allow the strategic reuse of limited resources. In so doing, DPGAs promise greater capacity, and in some cases higher performance, than conventional programmable device architectures where all array resources are dedicated to a single function for an entire operational epoch. This paper examines several usage patterns for DPGAs including temporal pipelining, utility functions, multiple function accommodation, and state-dependent logic. In the process, it offers insight into the application and technology space where DPGA-style reuse techniques are most beneficial.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: The programmable logic data book

paper_content:

Improvement to video-telephone systems allowing a called subscriber to have at his disposal on his television receiver screen, before he takes off his handset, information about the person who has initiated the call. Each subscriber station has a handset, a television camera, a television receiver and a character generator and is connected to a switching network by a telephone line, an incoming video line and an outgoing video line. Means are provided in the calling station for connecting to the outgoing video line the character generator when the calling subscriber takes down the handset and the television camera when video signals are detected on the incoming video line and in the called station for supplying with current the television receiver when ringing tone signals are detected on the telephone line.
---
paper_title: A time-multiplexed FPGA

paper_content:

This paper describes the architecture of a time-multiplexed FPGA. Eight configurations of the FPGA are stored in on-chip memory. This inactive on-chip memory is distributed around the chip, and accessible so that the entire configuration of the FPGA can be changed in a single cycle of the memory. The entire configuration of the FPGA can be loaded from this on-chip memory in 30 ns. Inactive memory is accessible as block RAM for applications. The FPGA is based on the Xilinx XC4000E FPGA, and includes extensions for dealing with state saving and forwarding and for increased routing demand due to time-multiplexing the hardware.
---
paper_title: PipeRench: A Reconfigurable Architecture and Compiler

paper_content:

With the proliferation of highly specialized embedded computer systems has come a diversification of workloads for computing devices. General-purpose processors are struggling to efficiently meet these applications' disparate needs, and custom hardware is rarely feasible. According to the authors, reconfigurable computing, which combines the flexibility of general-purpose processors with the efficiency of custom hardware, can provide the alternative. PipeRench and its associated compiler comprise the authors' new architecture for reconfigurable computing. Combined with a traditional digital signal processor, microcontroller or general-purpose processor, PipeRench can support a system's various computing needs without requiring custom hardware. The authors describe the PipeRench architecture and how it solves some of the pre-existing problems with FPGA architectures, such as logic granularity, configuration time, forward compatibility, hard constraints and compilation time.
---
paper_title: Configuration caching vs data caching for striped FPGAs

paper_content:

Striped FPGA [1], or pipeline-recon gurable FPGA provides hardware virtualization by supporting fast run-time recon guration. In this paper we show that the performance of striped FPGA depends on the recon guration pattern, the run time scheduling of con gurations through the FPGA. We study two main con guration scheduling approachesCon guration Caching and Data Caching. We present the quantitative analysis of these scheduling techniques to compute their total execution cycles taking into account the overhead caused by the IO with the external memory. Based on the analysis we can determine which scheduling technique works better for the given application and for the given hardware parameters.
---
paper_title: PipeRench: A Reconfigurable Architecture and Compiler

paper_content:

With the proliferation of highly specialized embedded computer systems has come a diversification of workloads for computing devices. General-purpose processors are struggling to efficiently meet these applications' disparate needs, and custom hardware is rarely feasible. According to the authors, reconfigurable computing, which combines the flexibility of general-purpose processors with the efficiency of custom hardware, can provide the alternative. PipeRench and its associated compiler comprise the authors' new architecture for reconfigurable computing. Combined with a traditional digital signal processor, microcontroller or general-purpose processor, PipeRench can support a system's various computing needs without requiring custom hardware. The authors describe the PipeRench architecture and how it solves some of the pre-existing problems with FPGA architectures, such as logic granularity, configuration time, forward compatibility, hard constraints and compilation time.
---
paper_title: Compilation tools for run-time reconfigurable designs

paper_content:

This paper describes a framework and tools for automating the production of designs which can be partially reconfigured at run time. The tools include: a partial evaluator, which produces configuration files for a given design, where the number of configurations can be minimised by a process, known as compile-time sequencing; an incremental configuration calculator, which takes the output of the partial evaluator and generates an initial configuration file and incremental configuration files that partially update preceding configurations; and a tool which further optimises designs for FPGAs supporting simultaneous configuration of multiple cells. While many of our techniques are independent of the design language and device used, our tools currently target Xilinx 6200 devices. Simultaneous configuration, for example, can be used to reduce the time for reconfiguring an adder to a subtractor from time linear with respect to its size to constant time at best and logarithmic time at worst.
---
paper_title: A dynamic reconfiguration run-time system

paper_content:

The feasibility of run-time reconfiguration of FPGAs has been established by a large number of case studies. However, these systems have typically involved an ad hoc combination of hardware and software. The software that manages the dynamic reconfiguration is typically specialised to one application and one hardware configuration. We present three different applications of dynamic reconfiguration, based on research activities at Glasgow University, and extract a set of common requirements. We present the design of an extensible run-time system for managing the dynamic reconfiguration of FPGAs, motivated by these requirements. The system is called RAGE, and incorporates operating-system style services that permit sophisticated and high level operations on circuits.
---
paper_title: Debugging techniques for dynamically reconfigurable hardware

paper_content:

Testing dynamically reconfigurable systems imposes new challenges which require special treatment. We present tools and techniques we developed for debugging a dynamically reconfigurable system that performs run-time constant propagation optimisations. An application for monitoring the effect of run-time specialisation is presented and we show how we adapted standard testability techniques to evaluate the performance of specialised circuits. We also outline how NDLs that capture reconfiguration at a high level can assist with debugging.
---
paper_title: A Case Study of Partially Evaluated Hardware Circuits: Key-Specific DES

paper_content:

FPGA based data encryption provides greater flexibility than ASICs and higher performance than software. Because FPGAs can be reprogrammed, they allow a single integrated circuit to efficiently implement multiple encryption algorithms. Furthermore, the ability to program FPGAs at runtime can be used to improve the performance through dynamic optimization. This paper describes the application of partial evaluation to an implementation of the Data Encryption Standard (DES). Each end user of a DES session shares a secret key, and this knowledge can be used to improve circuit performance. Key-specific encryption circuits require fewer resources and have shorter critical paths than the completely general design. By applying partial evaluation to DES on a Xilinx XC4000 series device we have reduced the CLB usage by 45% and improved the encryption bandwidth by 35%.
---
paper_title: Improving functional density through run-time constant propagation

paper_content:

Circuit specialization techniques such as constant propagation are commonly used to reduce both the hardware resources and cycle time of digital circuits. When reconfigurable FPGAs are used, these advantages can be extended by dynamically specializing circuits using run-time reconfiguration (RTR). For systems exploiting constant propagation, hardware resources can be reduced by folding constants within the circuit and dynamically changing the constants using circuit reconfiguration. To measure the benefits of circuit specialization, a functional density metric is presented. This metric allows the analysis of both static and run-time reconfigured circuits by including the cost of circuit reconfiguration. This metric will be used to justify runtime constant propagation as well as analyze the effects of reconfiguration time on run-time reconfigured systems.
---
paper_title: Run-time parameterised circuits for the Xilinx XC6200

paper_content:

Current design tools support parameterisation of circuits, but the parameters are fixed at compile-time. In contrast, the circuits discussed in this paper fix their parameters at run-time. Run-time parameterised circuits can potentially out-perform custom VLSI hardware by optimising the FPGA circuit for a specific instance of a problem rather than for a general class of problem. This paper discusses the design of run-time parameterised circuits, and presents a study of run-time parameterised circuits for finite field operations on the Xilinx XC6200. The paper includes a comparison with implementation on a self-timed version of the XC6200 architecture, which illustrates the potential benefits of self-timing for dynamically reconfigurable systems.
---
paper_title: Circuit partitioning for dynamically reconfigurable FPGAs

paper_content:

Dynamically recon gurable FPGAs have the potential to dramatically improve logic density by time-sharing a physical FPGA device. This paper presents a networkow based partitioning algorithm for dynamically recon gurable FPGAs based on the architecture in [2]. Experiments show that our approach outperforms the enhanced force-directed scheduling method in [2] in terms of communication cost.
---
paper_title: A CAD Suite for High-Performance FPGA Design

paper_content:

This paper describes the current status of a suite of CAD tools designed specifically for use by designers who are developing high-performance configurable-computing applications. The basis of this tool suite is JHDL, a design tool originally conceived as a way to experiment with Run-Time Reconfigured (RTR) designs. However, what began as a limited experiment to model RTR designs with Java has evolved into a comprehensive suite of design tools and verification aids, with these tools being used successfully to implement high-performance applications in Automated Target Recognition (ATR), sonar beamforming, and general image processing on configurable-computing systems.
---
paper_title: JHDL-an HDL for reconfigurable systems

paper_content:

JHDL is a design tool for reconfigurable systems that allows designers to express circuit organizations that dynamically change over time in a natural way, using only standard programming abstractions found in object-oriented languages. JHDL manages FPGA resources in a manner that is similar to the way object-oriented languages manage memory: circuits are treated as distinct objects and a circuit is configured onto a configurable computing machine (CCM) by invoking its constructor effectively "constructing " an instance of the circuit onto the reconfigurable platform just as object instances are allocated in memory with conventional object-oriented languages. This approach of using object constructors/destructors to control the circuit lifetime on a CCM is a powerful technique that naturally leads to a dual simulation/execution environment where a designer can easily switch between either software simulation or hardware execution on a CCM with a single application description. Moreover JHDL supports dual hardware/software execution; parts of the application described using JHDL circuit constructs can be executed on the CCM while the remainder of the application the-GUI for example-can run on the CCM host. Based on an existing programming language (Java), JHDL requires no language extensions and can be used with any standard Java 1.1 distribution.
---
paper_title: Scheduling designs into a time-multiplexed FPGA

paper_content:

An algorithm is presented for partitioning a design in time. The algorithm devides a large, technology-mapped design into multiple configurations of a time-multiplexed FPGA. These configurations are rapidly executed in the FPGA to emulate the large design. The tool includes facilities for optimizing the partitioning to improve routability, for fitting the design into more configurations than the depth of the critical path and for compressing the critical path of the design into fewer configurations, both to fit the design into the device and to improve performance. Scheduling results are shown for mapping designs into an 8-configuration time-multiplexed FPGA and for architecture investigation for a time-multiplexed FPGA.
---
paper_title: Temporal partitioning and scheduling data flow graphs for reconfigurable computers

paper_content:

FPGA-based configurable computing machines are evolving rapidly. They offer the ability to deliver very high performance at a fraction of the cost when compared to supercomputers. The first generation of configurable computers (those with multiple FPGAs connected using a specific interconnect) used statically reconfigurable FPGAs. On these configurable computers, computations are performed by partitioning an entire task into spatially interconnected subtasks. Such configurable computers are used in logic emulation systems and for functional verification of hardware. In general, configurable computers provide the ability to reconfigure rapidly to any desired custom form. Hence, the available resources can be reused effectively to cut down the hardware costs and also improve the performance. In this paper, we introduce the concept of temporal partitioning to partition a task into temporally interconnected subtasks. Specifically, we present algorithms for temporal partitioning and scheduling data flow graphs for configurable computers. We are given a configurable computing unit (RPU) with a logic capacity of S/sub RPU/ and a computational task represented by an acyclic data flow graph G=(V, E). Computations with logic area requirements that exceed S/sub RPU/ cannot be completely mapped on a configurable computer (using traditional spatial mapping techniques). However, a temporal partitioning of the data flow graph followed by proper scheduling can facilitate the configurable computer based execution. Temporal partitioning of the data flow graph is a k-way partitioning of G=(V, E) such that each partitioned segment will not exceed S/sub RPU/ in its logic requirement. Scheduling assigns an execution order to the partitioned segments so as to ensure proper execution. Thus, for each segment in {s/sub 1/,s/sub 2/,...,s/sub k/}, scheduling assigns a unique ordering S/sub i/-j,1/spl les/i/spl les/k,1/spl les/j/spl les/k, such that the computation would execute in proper sequential order as defined by the flow graph G=(V, E).
---
paper_title: Configuration prefetch for single context reconfigurable coprocessors

paper_content:

Current reconfigurable systems suffer from a significant overhead due to the time it takes to reconfigure their hardware. In order to deal with this overhead, and increase the power of reconfigurable systems, it is important to develop hardware and software systems to reduce or eliminate this delay. In this paper we propose one technique for significantly reducing the reconfiguration latency: the prefetching of configurations. By loading a configuration into the reconfigurable logic in advance of when it is needed, we can overlap the reconfiguration with useful computation. We demonstrate the power of this technique, and propose an algorithm for automatically adding prefetch operations into reconfigurable applications. This results in a significant decrease in the reconfiguration overhead for these applications.
---
paper_title: A dynamic instruction set computer

paper_content:

A dynamic instruction set computer (DISC) has been developed that supports demand-driven modification of its instruction set. Implemented with partially reconfigurable FPGAs, DISC treats instructions as removable modules paged in and out through partial reconfiguration as demanded by the executing program. Instructions occupy FPGA resources only when needed and FPGA resources can be reused to implement an arbitrary number of performance-enhancing application-specific instructions. DISC further enhances the functional density of FPGAs by physically relocating instruction modules to available FPGA space.
---
paper_title: Sequencing run-time reconfigured hardware with software

paper_content:

Run-Time Reconfigured systems offer additional hardware resources to systems based on reconfigurable FPGAs. These systems, however, are often difficult to build and must tolerate substantial reconfiguration times. A processor based architecture has been built to simplify the development of these systems by providing programmable control of hardware sequencing while retaining the performance of hardware. Configuration overhead of this system is reduced by "caching" hardware on the reconfigurable resource. An image processing application was developed on this system to demonstrate both the performance improvements of custom hardware and the ease of software development.
---
paper_title: Compilation tools for run-time reconfigurable designs

paper_content:

This paper describes a framework and tools for automating the production of designs which can be partially reconfigured at run time. The tools include: a partial evaluator, which produces configuration files for a given design, where the number of configurations can be minimised by a process, known as compile-time sequencing; an incremental configuration calculator, which takes the output of the partial evaluator and generates an initial configuration file and incremental configuration files that partially update preceding configurations; and a tool which further optimises designs for FPGAs supporting simultaneous configuration of multiple cells. While many of our techniques are independent of the design language and device used, our tools currently target Xilinx 6200 devices. Simultaneous configuration, for example, can be used to reduce the time for reconfiguring an adder to a subtractor from time linear with respect to its size to constant time at best and logarithmic time at worst.
---
paper_title: Runlength compression techniques for FPGA configurations

paper_content:

The time it takes to reconfigure FPGAs can be a significant overhead for reconfigurable computing. In this paper we develop new compression algorithms for FPGA configurations that can significantly reduce this overhead. By using runlength and other compression techniques, files can be compressed by a factor of 3.6 times. Bus transfer and decompression hardware are also discussed. This results in a single compression methodology which achieves higher compression ratios than existing algorithms in an off-line version, as well as a somewhat lower quality compression approach which is suitable for on-line use in dynamic circuit generation and other mapping-time critical situations.
---
paper_title: Automating production of run-time reconfigurable designs

paper_content:

This paper describes a method that automates a key step in producing run-time reconfigurable designs: the identification and mapping of reconfigurable regions. In this method, two successive circuit configurations are matched to locate the components common to them, so that reconfiguration time can be minimized. The circuit configurations are represented as a weighted bipartite graph, to which an efficient matching algorithm is applied. Our method, which supports hierarchical and library-based design, is device-independent and has been tested using Xilinx 6200 FPGAs. A number of examples in arithmetic, pattern matching and image processing are selected to illustrate our approach.
---
paper_title: Don't Care discovery for FPGA configuration compression

paper_content:

One of the major overheads in reconfigurabl e computing is the time it takes to reconfigure the devices in the system. The configuration compression algorithm presented in our previous paper [Hauck98c] is one efficient technique for reducing this overhead. In this paper, we develop an algorithm for finding Don’t Care bits in configuration s to improve the compatibility of the configuration data. With the help of the Don’t Cares, higher configuration compression ratios can be achieved by using our modified configuration compression algorithm. This improves compression ratios of a factor of 7, where our original algorithm only achieved a factor of 4. 1. Configuration Compression FPGAs are often used as powerful hardware for applications that require high speed computation. One major benefit provided by FPGAs is the ability to reconfigure during execution. For systems in which reconfiguration was done infrequently, the time to reconfigure the FPGA was of little concern. However, as more and more applications involve run-time reconfiguration, fast reconfiguration of FPGAs becomes an important issue [Hauck98a]. In most systems an FPGA must sit idle while it is being reconfigured, wasting cycles that could otherwise be used to perform useful work. For example, applications on the DISC and DISC II system spend 25% [Withlin96] to 71% [Wirthlin95] of their execution time performing reconfiguration. Thus, a reduction in the amount of cycles wasted to reconfiguration can significantly improve performance. Previously, we have presented methods for overlapping reconfiguration with computation via configuration prefetching [Hauck98b]. We have also presented a technique for reducing the overhead by compressing the configuration datastreams [Hauck98c]. In this paper, we will present a technique for finding possible Don’t Cares in configuration data such that higher compression ratios can be achieved.
---
paper_title: Configuration compression for FPGA-based embedded systems

paper_content:

Field programmable gate arrays (FPGAs) are a promising technology for developing high-performance embedded systems. The density and performance of FPGAs have drastically improved over the past few years. Consequently, the size of the configuration bit-streams has also increased considerably. As a result, the cost-effectiveness of FPGA-based embedded systems is significantly affected by the memory required for storing various FPGA configurations. This paper proposes a novel compression technique that reduces the memory required for storing FPGA configurations and results in high decompression efficiency. Decompression efficiency corresponds to the decompression hardware cost as well as the decompression rate. The proposed technique is applicable to any SRAM-based FPGA device since configuration bit-streams are processed as raw data. The required decompression hardware is simple and the decompression rate scales with the speed of the memory used for storing the configuration bit-streams. Moreover, the time to configure the device is not affected by our compression technique. Using our technique, we demonstrate up to 41% savings in memory for configuration bit-streams of several real-world applications.
---
paper_title: Configuration relocation and defragmentation for run-time reconfigurable computing

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. By mapping the compute-intensive sections of an application to reconfigurable hardware, custom computing systems exhibit significant speedups over traditional microprocessors. However, this potential acceleration is limited by the requirement that the speedups provided must outweigh the considerable cost of reconfiguration. The ability to relocate and defragment configurations on field programmable gate arrays (FPGAs) can dramatically decrease the overall reconfiguration overhead incurred by the use of the reconfigurable hardware. We therefore present hardware solutions to provide relocation and defragmentation support with a negligible area increase over a generic partially reconfigurable FPGA, as well as software algorithms for controlling this hardware. This results in factors of 8 to 12 improvement in the configuration overheads displayed by traditional serially programmed FPGAs.
---
paper_title: Configuration caching vs data caching for striped FPGAs

paper_content:

Striped FPGA [1], or pipeline-recon gurable FPGA provides hardware virtualization by supporting fast run-time recon guration. In this paper we show that the performance of striped FPGA depends on the recon guration pattern, the run time scheduling of con gurations through the FPGA. We study two main con guration scheduling approachesCon guration Caching and Data Caching. We present the quantitative analysis of these scheduling techniques to compute their total execution cycles taking into account the overhead caused by the IO with the external memory. Based on the analysis we can determine which scheduling technique works better for the given application and for the given hardware parameters.
---
paper_title: Run-time compaction of FPGA designs

paper_content:

Controllers for dynamically reconfigurable FPGAs that are capable of supporting multiple independent tasks simultaneously need to be able to place designs at run-time when the sequence or geometry of designs is not known in advance. As tasks arrive and depart the available cells become fragmented, thereby reducing the controller's ability to place new tasks. The response times of tasks and the utilization of the FPGA consequently suffer. In this paper, we describe and assess a task compaction heuristic that alleviates the problems of external fragmentation by exploiting partial reconfiguration. We identify a region of the chip that can satisfy the next request after the designs occupying the region have been moved. The approach is simple and platform independent. We show by simulation that for a wide range of task sizes and configuration delays, the response of overloaded systems can be improved significantly.
---
paper_title: PipeRench: A Reconfigurable Architecture and Compiler

paper_content:

With the proliferation of highly specialized embedded computer systems has come a diversification of workloads for computing devices. General-purpose processors are struggling to efficiently meet these applications' disparate needs, and custom hardware is rarely feasible. According to the authors, reconfigurable computing, which combines the flexibility of general-purpose processors with the efficiency of custom hardware, can provide the alternative. PipeRench and its associated compiler comprise the authors' new architecture for reconfigurable computing. Combined with a traditional digital signal processor, microcontroller or general-purpose processor, PipeRench can support a system's various computing needs without requiring custom hardware. The authors describe the PipeRench architecture and how it solves some of the pre-existing problems with FPGA architectures, such as logic granularity, configuration time, forward compatibility, hard constraints and compilation time.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Dynamic reconfiguration to support concurrent applications

paper_content:

This paper describes the development of a dynamically reconfigurable system that can support multiple applications running concurrently. A dynamically reconfigurable system allows hardware reconfiguration while part of the reconfigurable hardware is busy computing. An FPGA resource manager (RM) is developed to allocate and de-allocate FPGA resources and to preload FPGA configuration files. For each individual application, different tasks that require FPGA resources are represented as a flow graph which is made available to the RM so as to enable efficient resource management and preloading. The performance of using the RM to support several applications is summarized. The impact of supporting concurrency and preloading in reducing application execution time is demonstrated.
---
paper_title: Memory interfacing and instruction specification for reconfigurable processors

paper_content:

As custom computing machines evolve, it is clear that a major bottleneck is the slow interconnection architecture between the logic and memory. This paper describes the architecture of a custom computing machine that overcomes the interconnection bottleneck by closely integrating a fixed-logic processor, a reconfigurable logic array, and memory into a single chip, called OneChip-98. The OneChip-98 system has a seamless programming model that enables the programmer to easily specify instructions without additional complex instruction decoding hardware. As well, there is a simple scheme for mapping instructions to the corresponding programming bits. To allow the processor and the reconfigurable array to execute concurrently, the programming model utilizes a novel memory-consistency scheme implemented in the hardware. To evaluate the feasibility of the OneChip-98 architecture, a 32-bit MIPS-like processor and several performance enhancement applications were mapped to the Transmogrifier-2 field programmable system. For two typical applications, the 2-dimensional discrete cosine transform and the 64-tap FIR filter, we were capable of achieving a performance speedup of over 30 times that of a stand-alone state-of-the-art processor.
---
paper_title: Safe and protected execution for the Morph/AMRM reconfigurable processor

paper_content:

Technology scaling of CMOS processes brings relatively faster transistors (gates) and slower interconnects (wires), making viable the addition of reconfigurability to increase performance. In the Morph/AMRM system we are exploring the addition of reconfigurable logic, deeply integrated with the processor core, employing the reconfigurability to manage the cache, datapath, and pipeline resources more effectively. However, integration of reconfigurable logic introduces significant protection and safety challenges for microprocess execution. We analyze the protection structures in a state of the art microprocessor core (R10000), identifying the few critical logic blocks and demonstrating that the majority of the logic in the processor core can be safely reconfigured. Subsequently, we propose a protection architecture for the Morph/AMRM reconfigurable processor which enable nearly the full range of power of reconfigurability in the processor core while requiring only a small number of fixed logic features which to ensure safe, protected multiprocess execution.
---

Title: Reconfigurable Computing: A Survey of Systems and Software

Section 1: Introduction
Description 1: Introduce the concept of reconfigurable computing, its significance, and the survey's purpose.

Section 2: Technology
Description 2: Discuss the foundational technology behind reconfigurable computing and its evolution.

Section 3: Hardware
Description 3: Explore the different hardware architectures used in reconfigurable computing systems.

Section 4: Coupling
Description 4: Examine various methods of coupling reconfigurable hardware with traditional microprocessors.

Section 5: Traditional FPGAs
Description 5: Provide an overview of the structure and function of traditional FPGAs used in reconfigurable computing.

Section 6: Logic Block Granularity
Description 6: Analyze the impact of the granularity of logic blocks on performance and design complexity.

Section 7: Heterogeneous Arrays
Description 7: Discuss the use of heterogeneous structures within reconfigurable systems to improve performance.

Section 8: Routing Resources
Description 8: Detail the routing resources in reconfigurable architectures and their optimization.

Section 9: One-Dimensional Structures
Description 9: Describe the concept and execution of one-dimensional reconfigurable architectures.

Section 10: Multi-FPGA Systems
Description 10: Cover the additional hardware considerations in systems composed of multiple FPGAs.

Section 11: Hardware Summary
Description 11: Summarize the various hardware design choices and their implications in reconfigurable computing.

Section 12: Software
Description 12: Discuss the software environment required to design and compile configurations for reconfigurable hardware.

Section 13: Hardware-Software Partitioning
Description 13: Explain how systems partition tasks between reconfigurable hardware and traditional software execution.

Section 14: Circuit Specification
Description 14: Describe the methods available for specifying circuits to be implemented on reconfigurable hardware.

Section 15: Circuit Libraries
Description 15: Discuss the use of pre-designed circuit or macro libraries to expedite design.

Section 16: Circuit Generators
Description 16: Explain how circuit generators can customize modules to meet application-specific requirements.

Section 17: Partial Evaluation
Description 17: Introduce the concept of partial evaluation to optimize circuit configurations.

Section 18: Memory Allocation
Description 18: Detail strategies for effective memory allocation in reconfigurable systems.

Section 19: Parallelization
Description 19: Discuss techniques for incorporating parallelism into reconfigurable computing applications.

Section 20: Multi-FPGA System Software
Description 20: Examine the software challenges and solutions for systems using multiple FPGAs.

Section 21: Design Testing
Description 21: Describe methods for testing and verifying the design of circuits for reconfigurable systems.

Section 22: Software Summary
Description 22: Summarize the role of software tools in the design and use of reconfigurable computing systems.

Section 23: Run-Time Reconfiguration
Description 23: Discuss the principles and benefits of run-time reconfiguration in reconfigurable computing.

Section 24: Reconfigurable Models
Description 24: Define the different types of reconfigurable models, including single context, multicontext, and partially reconfigurable systems.

Section 25: Pipeline Reconfigurable
Description 25: Introduce the concept of pipeline reconfigurable systems and their execution models.

Section 26: Run-Time Partial Evaluation
Description 26: Explain the advantages of run-time partial evaluation for optimizing configurations based on runtime data.

Section 27: Compilation and Configuration Scheduling
Description 27: Discuss strategies for compiling and scheduling configurations in run-time reconfigurable systems.

Section 28: Fast Configuration
Description 28: Present methods for reducing configuration overhead in reconfigurable systems.

Section 29: Potential Problems with RTR
Description 29: Identify potential issues with run-time reconfiguration and solutions to mitigate them.

Section 30: Run-Time Reconfiguration Summary
Description 30: Summarize the key points and benefits of run-time reconfiguration in reconfigurable systems.

Section 31: Conclusion
Description 31: Conclude by summarizing the importance, challenges, and future directions of reconfigurable computing.