We present hls4ml , a free and open source platform that translates machine learning (ML) models from modern deep learning frameworks into high-level synthesis (HLS) code that can be integrated into full designs for field-programmable gate arrays (FPGAs) or application-specific integrated circuits (ASICs). With its flexible and modular design, hls4ml supports a large number of deep learning frameworks and can target HLS compilers from several vendors, including Vitis HLS, Intel oneAPI and Catapult HLS. Together with a wider eco-system for software-hardware co-design, hls4ml has enabled the acceleration of ML inference in a wide range of commercial and scientific applications where low latency, resource usage, and power consumption are critical. In this article, we describe the structure and functionality of the hls4ml platform. The overarching design considerations for the generated HLS code are discussed, together with selected performance results.

FPGAs are a compelling substrate for supporting machine learning inference. Tools such as High-Level Synthesis and hls4ml can shorten the development cycle for deploying ML algorithms on FPGAs, but can struggle to handle the large on-chip storage needed for many of these models. In particular the high BRAM usage found in many of these flows can cause Place & Route failures during synthesis. In this paper we propose using a Simulated-Annealing based flow to perform BRAM-aware quantization. This approach trades off inference accuracy with BRAM usage, to provide a high-quality inference engine that still meets on-chip resource constraints. We demonstrate this flow for Transformer-based machine learning algorithms, which include Flash Attention in a Stream-based Dataflow architecture. Our system imposes minimal accuracy drops, yet can reduce BRAM usage by 20%-50%, and improve power efficiency by 264%-812% compared to existing Transformer-based accelerators on FPGAs

In-time particle trajectory reconstruction in the Large Hadron Collider is challenging due to the high collision rate and numerous particle hits. Using GNN (Graph Neural Network) on FPGA has enabled superior accuracy with flexible trajectory classification. However, existing GNN architectures have inefficient resource usage and insufficient parallelism for edge classification. This paper introduces a resource-efficient GNN architecture on FPGAs for low latency particle tracking. The modular architecture facilitates design scalability to support large graphs. Leveraging the geometric properties of hit detectors further reduces graph complexity and resource usage. Our results on Xilinx UltraScale+ VU9P demonstrate 1625x and 1574x performance improvement over CPU and GPU respectively.

As FPGAs are integrated into to the cloud, they become useful in a number of areas where they were not traditionally considered, such as processing genomics data. For many genomics applications, such as K-mer counting, the off-chip DRAM (and sometimes SRAM) memory subsystems provided by most FPGA boards for high capacity storage are not efficient. Recently new styles of memory have been developed, though their role in reconfigurable computing systems can be unclear. One of the challenges these memory systems present to FPGA designers is identifying how they can be used in current systems, and what new applications become possible. In this paper we describe how and why K-mer counting is one such use for an FPGA-attached Hybrid Memory Cube (HMC). The HMC's high random-access rate is ideal for large Bloom filters, an efficient structure for checking membership in a set, or even counting occurrences. Our HMC based counting Bloom filter, useful in a bioinformatics context, achieves a speedup of 13x over traditional FPGA-attached DRAM and 9.31x to 17.6x over multi-core, multi-threaded software on our host system.

Data compression techniques have been the subject of intense study over the past several decades due to exponential increases in the quantity of data stored and transmitted by computer systems. Compression algorithms are traditionally forced to make tradeoffs between throughput and compression quality (the ratio of original file size to compressed file size). FPGAs represent a compelling substrate for streaming applications such as data compression thanks to their capacity for deep pipelines and custom caching solutions. Unfortunately, data hazards in compression algorithms such as LZ77 inhibit the creation of deep pipelines without sacrificing some amount of compression quality. In this work we detail a scalable fully pipelined FPGA accelerator that performs LZ77 compression and static Huffman encoding at rates up to 5.6 GB/s. Furthermore, we explore tradeoffs between compression quality and FPGA area that allow the same throughput at a fraction of the logic utilization in exchange for moderate reductions in compression quality. Compared to recent FPGA compression studies, our emphasis on scalability gives our accelerator a 3.0x advantage in resource utilization at equivalent throughput and compression ratio.

Coarse Grained Reconfigurable Arrays (CGRAs) offer improved energy efficiency and performance over conventional architectures. However, modulo counter based control of these devices limits efficiency for applications with multiple execution modes. This work presents a new type of architecture that adds support for branching control flow to CGRAs. The pipelined program counter CGRA framework blends the high parallelism of traditional CGRAs with the flexibility of commodity processors. Offset Pipelined Scheduling (OPS) is the basis of an enhanced CGRA tool chain targeting these devices. OPS is shown to provide an average 1.94× speed up for benchmarks that are resource limited when modulo scheduled.

Data compression is crucial in large-scale storage servers to save both storage and network bandwidth, but it suffers from high computational cost. In this work, we present a high throughput FPGA based compressor as a PCIe accelerator to achieve CPU resource saving and high power efficiency. The proposed compressor is differentiated from previous hardware compressors by the following features:1) targeting Xpress9 algorithm, whose compression quality is comparable to the best Gzip implementation (level 9), 2) a scalable multi-engine architecture with various IP blocks to handle algorithmic complexity as well as to achieve high throughput, 3) supporting a heavily multi-threaded server environment with an asynchronous data transfer interface between the host and the accelerator. The implemented Xpress9 compressor on Altera Stratix V GS performs 1.6-2.4Gbps throughput with 7 engines on various compression benchmarks, supporting up to 128 thread contexts.

Datacenter workloads demand high computational capabilities, flexibility, power efficiency, and low cost. It is challenging to improve all of these factors simultaneously. To advance datacenter capabilities beyond what commodity server designs can provide, we have designed and built a composable, reconfigurable fabric to accelerate portions of large-scale software services. Each instantiation of the fabric consists of a 6×8 2-D torus of high-end Stratix V FPGAs embedded into a half-rack of 48 machines. One FPGA is placed into each server, accessible through PCIe, and wired directly to other FPGAs with pairs of 10 Gb SAS cables. In this paper, we describe a medium-scale deployment of this fabric on a bed of 1,632 servers, and measure its efficacy in accelerating the Bing web search engine. We describe the requirements and architecture of the system, detail the critical engineering challenges and solutions needed to make the system robust in the presence of failures, and measure the performance, power, and resilience of the system when ranking candidate documents. Under high load, the largescale reconfigurable fabric improves the ranking throughput of each server by a factor of 95% for a fixed latency distribution—or, while maintaining equivalent throughput, reduces the tail latency by 29%.

Over the last decade, the number of known biologically important non-coding RNAs (ncRNAs) has increased by orders of magnitude. The function performed by a specific ncRNA is partially determined by its structure, defined by which nucleotides of the molecule form pairs. These correlations may span large and variable distances in the linear RNA molecule. Because of these characteristics, algorithms that search for ncRNAs belonging to known families are computationally expensive, often taking many CPU weeks to run. To improve the speed of this search, multiple search algorithms arranged into a series of progressively more stringent filters can be used. In this paper, we present an FPGA based implementation of some of these algorithms. This is the first FPGA based approach to attempt to accelerate multiple filters used in ncRNA search. The FPGA is reconfigured for each filter, resulting in a total system speedup of 25x when compared with a single CPU.

Bioinformatics is an emerging field with seemingly limitless possibilities for advances in numerous areas of research and applications. We propose a scalable FPGA-based solution to the short read mapping problem in DNA sequencing, which greatly accelerates the task of aligning short length reads to a known reference genome. We compare the runtime, power consumption, and sensitivity of the hardware system to the BFAST and Bowtie software tools. The hardware system demonstrates a 250X speedup versus BFAST and a 31X speedup versus Bowtie on eight CPU cores. Also, the hardware system is more sensitive than Bowtie, which aligns approximately 80% of the short reads, as compared to 91% aligned by the hardware.

Coarse Grained Reconfigurable Arrays (CGRAs) are a promising class of architectures for accelerating applications using a large number of parallel execution units for high throughput. While they are typically very efficient for a single task, all functional units are required to perform in lock step; this makes some classes of applications more difficult to program and efficiently use resources. Other architectures like Massively Parallel Processor Arrays (MPPAs) are better suited for these applications and excel at executing unrelated tasks simultaneously, but the amount of resources dedicated to a single task is limited.

Coarse Grained Reconfigurable Arrays (CGRAs) are a promising class of architectures for accelerating applications using a large number of parallel execution units for high throughput. While they are typically good at utilizing many processing elements for a single task with automatic parallelization, all processing elements are required to perform their operations in lock step; this makes applications that involve multiple data streams, multiple tasks, or unpredictable schedules more difficult to program and use their resources inefficiently. Other architectures like Massively Parallel Processor Arrays (MPPAs) are better suited for these applications and excel at executing unrelated tasks simultaneously, but the amount of resources easily utilized for a single task is limited. We are developing a new architecture with the multi-task flexibility of an MPPA and the automatic parallelization of a CGRA. A key to the flexibility of MPPAs is the ability for subtasks to execute independently instead of in lock step with all other subtasks on the array. In this paper, we develop the special network and control circuitry to add support for this execution style in a CGRA with less than 2% area overhead. Additionally, we also describe the CAD tool modifications and application developer guidelines for utilizing the resulting hybrid CGRA/MPPA architecture.

Signal processing applications have been shown to map well to time multiplexed coarse grained reconfigurable array (CGRA) devices, and can often be decomposed into a set of communicating kernels. This decomposition can facilitate application development and reuse but has significant consequences for tools targeting these devices in terms of allocation and arrangement of resources. This paper presents a CGRA floorplanner to optimize the division and placement of resources for multi-kernel applications. The task is divided into two phases aligned with the respective goals. Resource allocation is accomplished through incremental assignment to minimize performance bottlenecks while operating within the bounds of the maximum available resources. The resulting allocation of resources is arranged in the device using simulated annealing and a perimeter-based cost function which serves to minimize resources needed for both interand intra-kernel communications. The floorplanner is applied to a set of multi-kernel benchmarks demonstrating resource allocations providing maximum throughput across a range of available resources. The algorithms are very fast, taking only a few seconds while producing high quality results. Inter-kernel wire lengths are almost always minimal, and the resource allocation is proven optimal.

In this paper, we use an FPGA platform and a high level synthesis tool, called Impulse C, to speedup a statistical Line Of Reaction (LOR) estimation for a high-resolution Positron Emission Tomography (PET) scanner. The estimation algorithm provides a significant improvement over conventional methods, but the execution time is too long to be practical for clinic applications. Impulse C allows us to rapidly map a C program into a platform with a host processor coupled to an FPGA device. However, the generated HDLs from the original codes are very inefficient, and the execution time is even worse than the software code. We describe some optimization methods for the algorithm using Impulse C. These methods could also be applied to other applications or used to improve the high level synthesis tools. The results show that the FPGA implementation can obtain a 82× speedup over the optimized software.

Coarse Grained Reconfigurable Arrays (CGRAs) are typically very efficient for a single task. However all functional units are required to perform in lock step, wasting resources and making complex programming flows difficult. Massively Parallel Processor Arrays (MPPAs) excel at executing unrelated tasks simultaneously, but limit the amount of resources dedicated to a single task. We propose an architecture with an MPPA's design flexibility and a CGRA's throughput, capable of processing and transferring data in a pre-compiled schedule, with dynamic transfers between components. Alternative interconnect strategies are compared for silicon area cost and power utilization.

Functional units provide the backbone of any spatial accelerator by providing the computing resources. The desire for having rich and expensive functional units is in tension with producing a regular and energy-efficient computing fabric. This paper explores the design trade-off between complex, universal functional units and simpler, limited functional units.

Fine-grain reconfigurable devices suffer from the time needed to load the configuration bitstream. Even for small bitstreams in partially reconfigurable FPGAs this time cannot be neglected. In this article we survey the performance of the factors that contribute to the reconfiguration speed. Then, we study an FPGA-based system architecture and with real experiments we produce a cost model of Partial Reconfiguration (PR). This model is introduced to calculate the expected reconfiguration time and throughput. In order to develop a realistic model we take into account all the physical components that participate in the reconfiguration process. We analyze the parameters that affect the generality of the model and the adjustments needed per system for error-free evaluation. We verify it with real measurements, and then we employ it to evaluate existing systems presented in previous publications. The percentage error of the cost model when comparing its results with the actual values of those publications varies from 36% to 63%, whereas existing works report differences up to two orders of magnitude. Present work enables a user to evaluate PR and decide whether it is suitable for a certain application prior entering the complex PR design flow.

While traditional methods of designing FPGA applications have relied on schematics or HDL, much interest has been shown in C-to-FPGA tool flows that allow users to design FPGA hardware in C. We evaluate a C-to-FPGA tool flow (Impulse C) by analyzing the performance of three independent implementations of the Computed tomography (CT) filtered backprojection (FBP) algorithm developed using C, Impulse C, and VHDL respectively. In the process, we compare the design process of Impulse C versus HDL, and discuss the benefits and challenges of using Impulse C. In addition, we explore the benefits of tightly-coupled FPGA acceleration offered by the XtremeData XD1000. The results of this paper demonstrate that Impulse C designs can achieve over 61x improvement over multi-threaded software (8 threads), and close to the same performance as VHDL, while significantly reducing the design effort, and that tightly-coupled FPGA coprocessors like the XD1000 effectively overcomes the traditional communication bottleneck between CPU and FPGA.

Efficient storage in spatial processors is increasingly important as such devices get larger and support more concurrent operations. Unlike sequential processors that rely heavily on centralized storage, e.g. register files and embedded memories, spatial processors require many small storage structures to efficiently manage values that are distributed throughout the processor's fabric. The goal of this work is to determine the advantages and disadvantages of different architectural structures for storing values on-chip when optimizing for energy efficiency as well as area. Examination of applications for coarse-grained reconfigurable arrays (CGRAs) shows that most values are short-lived; they are produced and consumed quickly, but the distribution of value lifetimes has a reasonably long tail. We take advantage of this distribution to optimize register storage structures for managing short-, medium-, and long-lived values. We show that using a combination of register storage structures, each tailored for values with different lifetimes, provides a reduction in overall area-energy product to 0.69× the area-energy of the baseline architecture, without loss of performance. Finally we provide energy profiles, characteristics, and comparisons of each register structure to enable architects to guide future design choices.

When utilizing reconfigurable hardware there are many applications that will require more memory than is available in a single hardware block. While FPGAs have tools and mechanisms for building logically larger memories, it often requires developer intervention on word-oriented devices like Massively Parallel Processor Arrays (MPPAs). We examine building larger memories on the Ambric MPPA. Building an efficient structure requires low-level development and analysis of latency and bandwidth effects of network and protocol choices. We build a network that only requires only five instructions per transaction after optimization. The resource use and performance suggests architectural enhancements that should be considered for future devices.

While most of the electronics industry is dependent on the ever-decreasing size of lithographic transistors, this scaling cannot continue indefinitely. Nanoelectronics (circuits built with components on the scale of 10 nm) seem to be the most promising successor to lithographic based ICs. Molecular-scale devices including diodes, bistable switches, carbon nanotubes, and nanowires have been fabricated and characterized in chemistry labs. Techniques for self-assembling these devices into different architectures have also been demonstrated and used to build small-scale prototypes. While these devices and assembly techniques will lead to nanoscale electronics, they also have the drawback of being prone to defects and transient faults. Fault-tolerance techniques will be crucial to the use of nanoelectronics. Lastly, changes to the software tools that support the fabrication and use of ICs will be needed to extend them to support nanoelectronics. This paper introduces nanoelectronics and reviews the current progress made in research in the areas of technologies, architectures, fault tolerance, and software tools.

In this paper we present SPR, a new architecture-adaptive mapping tool for use with Coarse-Grained Reconfigurable Architectures (CGRAs). It combines a VLIW style scheduler and FPGA style placement and pipelined routing algorithms with novel mechanisms for integrating and adapting the algorithms to CGRAs. We introduce a latency padding technique that provides feedback from the placer to the scheduler to meet the constraints of a fixed frequency device with configurable interconnect. Using a new dynamic clustering method during placement, we achieved a 1.3x improvement in throughput of mapped designs. Finally, we introduce an enhancement to the PathFinder algorithm for targeting architectures with a mix of dynamically multiplexed and statically configurable interconnects. The enhanced algorithm is able to successfully share statically configured interconnect in a time-multiplexed way, achieving an average channel width reduction of .5x compared to non-shared static interconnect.

Modern Field Programmable Gate Arrays (FPGAs) are capable of performing complex discrete signal processing algorithms with clock rates above 100MHz. This combined with FPGA's low expense, ease of use, and selected dedicated hardware make them an ideal technology for a data acquisition system for positron emission tomography (PET) scanners. Our laboratory is producing a high-resolution, small-animal PET scanner that utilizes FPGAs as the core of the front-end electronics. For this next generation scanner, functions that are typically performed in dedicated circuits, or offline, are being migrated to the FPGA. This will not only simplify the electronics, but the features of modern FPGAs can be utilizes to add significant signal processing power to produce higher resolution images. In this paper two such processes, sub-clock rate pulse timing and event localization, will be discussed in detail. We show that timing performed in the FPGA can achieve a resolution that is suitable for small-animal scanners, and will outperform the analog version given a low enough sampling period for the ADC. We will also show that the position of events in the scanner can be determined in real time using a statistical positioning based algorithm.

Spatially-tiled architectures, such as coarse-grained reconfigurable arrays (CGRAs), are powerful architectures for accelerating applications in the digital-signal processing, embedded, and scientific computing domains. In contrast to field-programmable gate arrays (FPGAs), another common accelerator, they typically time-multiplex their processing elements and are word rather than bit-oriented. These differences lead us to re-examine some of the traditional architecture choices made for FPGAs as we move to these coarser-granularity architectures. In this paper we study the efficiency of time-multiplexing global interconnect as architectures scale from single-bit to multi-bit datapaths. Using the Mosaic infrastructure, we analyzed the design trade-offs involved in static vs. time-multiplexed routing for global interconnect channels, as well as the benefit of including a dedicated bit-wide control interconnect to supplement the word-wide datapath of a CGRA. We show that a time-multiplexed interconnect is beneficial in these coarse-grained systems, reducing the area-energy product to 0.32times the area-energy product of a fully static interconnect. We also show that for our benchmarks, which include single-bit control logic, providing both word and bit-wide interconnect resources further reduces the area-energy product to 0.94times that of an exclusively word-wide interconnect.

FPGA application developers often use pipelining, C-slowing and retiming to improve the performance of their designs. Unfortunately, registered netlists present a fundamentally different problem to CAD tools, potentially limiting the benefit of these techniques. In this paper we discuss some of the inherent issues pipelined netlists pose to existing timing-driven placement approaches. We then present two algorithmic modifications that reduce post-routing critical path delay by an average of 40%.

Although pipelining or C-slowing an FPGA-based application can potentially dramatically improve the performance, this poses a question for conventional reconfigurable architectures and CAD tools: what is the best way to support these new extra registers? While there have been multiple research efforts to address this problem, they generally impose strict architectural requirements, offer limited retiming capabilities, or require multiple iterations with no guarantees regarding feasible implementations. In this paper we introduce a new simulated annealing-based placement and retiming approach that provides the capability to aggressive apply retiming on a wide range of netlists, for arbitrary architectures, while maintaining predictable results. Our results show that for heavily pipelined applications, this methodology can produce netlists and placements with 1.65x better post-routing critical path delay as compared to the classical approach of retiming before timing-driven VPR placement, and 1.08x better than retiming before our improved timing-driven placer.

Modern Field Programmable Gate Arrays (FPGAs) are capable of performing complex discrete signal processing algorithms with clock rates of above 100MHz. This combined with FPGAs low expense, ease of use, and selected dedicated hardware make them an ideal technology for a data acquisition system for positron emission tomography (PET) scanner. Our laboratory is producing a high-resolution, small-animal PET scanner that utilizes FPGAs as the core of the front-end electronics. While this scanner uses an Altera ACEX1k and has limited complexity, we are also developing a new set of front-end electronics based on an Altera StratixII. This next generation scanner utilizes many of the features of modern FPGAs to add significant signal processing to produce higher resolution images. One such process we discuss is sub-clock rate pulse timing. We show that timing performed in the FPGA can achieve a resolution that is suitable for small-animal scanners, and will outperform the analog version given a low enough sampling period for the ADC

With the density of field-programmable gate arrays (FPGAs) steadily increasing, FPGAs have reached the point where they are capable of implementing complex floating-point applications. However, their general-purpose nature has limited the use of FPGAs in scientific applications that require floating-point arithmetic due to the large amount of FPGA resources that floating-point operations still require. This paper considers three architectural modifications that make floating-point operations more efficient on FPGAs. The first modification embeds floating-point multiply-add units in an island-style FPGA. While offering a dramatic reduction in area and improvement in clock rate, these embedded units are a significant change and may not be justified by the market. The next two modifications target a major component of IEEE compliant floating-point computations: variable length shifters. The first alternative to lookup tables (LUTs) for implementing the variable length shifters is a coarse-grained approach: embedded variable length shifters in the FPGA fabric. These shifters offer a significant reduction in area with a modest increase in clock rate and are smaller and more general than embedded floating-point units. The next alternative is a fine-grained approach: adding a 4:1 multiplexer unit inside a configurable logic block (CLB), in parallel to each 4-LUT. While this offers the smallest overall area improvement, it does offer a significant improvement in clock rate with only a trivial increase in the size of the CLB.

Reconfigurable hardware is ideal for use in systems-on-a-chip (SoC), as it provides both hardware-level performance and post-fabrication flexibility. However, any one architecture is rarely equally optimized for all applications. SoCs targeting a specific set of applications can greatly benefit from incorporating customized reconfigurable logic instead of generic field-programmable gate-array (FPGA) logic. Unfortunately, manually designing a domain-specific architecture for every SoC would require significant design time. Instead, this paper discusses our initial efforts towards creating a reconfigurable hardware generator capable of automatically creating flexible, yet domain-specific, designs. Our tests indicate that our generated architectures are more than 5times smaller than equivalent FPGA implementations and nearly as area-efficient as standard cell designs. We also use a novel technique employing synthetic circuit generation to demonstrate the flexibility of our architecture generation techniques.

Reconfigurable hardware has been shown to provide an efficient compromise between the flexibility of software and the performance of hardware. However, even coarse-grained reconfigurable architectures target the general case and miss optimization opportunities present if characteristics of the desired application set are known. Restricting the structure to support a class or a specific set of algorithms can increase efficiency while still providing flexibility within that set. By generating a custom array for a given computation domain, we explore the design space between an ASIC and an FPGA. However, the manual creation of these customized reprogrammable architectures would be a labor-intensive process, leading to high design costs. Instead, we propose automatic reconfigurable architecture generation specialized to given application sets. This paper discusses configurable ASIC (cASIC) architecture generation that creates hardware on average up to 12.3x smaller than an FPGA solution with embedded multipliers and 2.2x smaller than a standard cell implementation of individual circuits

This paper presents tools that automate the creation of domain-specific complex programmable logic devices (CPLDs), targeted for systems-on-a-chip. By tailoring full-crossbar-based CPLDs to the domains that they support, we provide results that beat fixed reconfigurable architectures by 5.5times-11.8times on average in terms of area-delay product. We also create sparse-crossbar-based CPLD architectures, using a novel switch-smoothing algorithm that makes the crossbars amenable to layout. This algorithm reduced the wire jog pitch of our largest layout from 48 to just 3, allowing for a compact very-large-scale-integration layout. These sparse-crossbar-based CPLDs require just 0.37times the area and 0.30times the delay of our full-crossbar-based CPLDs. We also address the question of how best to add resources to a CPLD in order to support future, unknown circuits, concluding that the best strategy is to add 5% to the crossbar switch density and to provide additional programmable logic arrays of the same size found in the base architecture

Due to their generic and highly programmable nature, FPGAs provide the ability to implement a wide range of applications. However, it is this nonspecific nature that has limited the use of FPGAs in scientific applications that require floating-point arithmetic. Even simple floating-point operations consume a large amount of computational resources. In this paper, we introduce embedding floating-point multiply-add units in an island style FPGA. This has shown to have an average area savings of 55.0% and an average increase of 40.7% in clock rate over existing architectures.

While previous research has shown that FPGAs can efficiently implement many types of computations, their flexibility inherently limits their clock rate. Several research groups have attempted to address this by developing new architectures that include registered switchpoints within their interconnect. Unfortunately, this pipelined communication presents a new and difficult problem for detailed routing tools. Known as the N-Delay Routing Problem, it has been proven to be NP-Complete. Although there have been two heuristics developed to address this issue, both have certain limitations and neither approach considers timing during the routing process. While timing-driven conventional routing is largely considered to be a solved problem, there are several issues inherent to the N-Delay Routing problem make addressing timing particularly difficult. In this paper we discuss the nature of these problems and present a new timing-driven pipeline-aware router that produces as much as 60% better critical path delay than previous efforts.

Many System-on-a-Chip devices would benefit from the inclusion of reprogrammable logic on the silicon die, as it can add general computing ability, provide run-time reconfigurability, or even be used for post-fabrication modifications. Also, by tailoring the logic to the SoC domain, additional area and delay gains can be achieved over current, more general reconfigurable fabrics. This paper presents our work on creating efficient CPLD architectures for SoC, including the creation of sparse crossbars, and a novel switch smoothing algorithm which makes the crossbars amenable to layout. For our largest architecture, the switch smoothing algorithm reduced the layout's wire jog pitch from 48 to just 3, allowing for a compact VLSI layout. This has helped pave the way for our sparse-crossbar based CPLDs, which require just .37x the area and .30x the delay of our full-crossbar based CPLDs.However, regardless of how efficient an architecture we develop, it is useless if it does not have enough resources to support the circuits to be implemented. We also address the question of how best to add resources to a CPLD in order to support future, unknown circuits, concluding that the best strategy is to add 5% to the crossbar switch density and to provide additional PLAs of the same size found in the base architecture.

FPGAs have reached densities that can implement floating point applications, but floating-point operations still require a large amount of FPGA resources. One major component of IEEE compliant floating-point computations is variable length shifters. They account for over 30% of a double-precision floating-point adder and 25% of a double-precision multiplier. This paper introduces two alternatives for implementing these shifters. One alternative is a coarse-grained approach: embedding variable length shifters in the FPGA fabric. These units provide significant area savings with a modest clock rate improvement over existing architectures. Another alternative is a fine-grained approach: adding a 4:1 multiplexer inside the slices, in parallel to the LUTs. While providing a more modest area savings, these multiplexers provide a significant boost in clock rate with a small impact on the FPGA fabric

We present a pipelining-aware router for fieldprogrammable gate arrays (FPGAs). The problem of routing pipelined signals is different from the conventional FPGA routing problem. The two-terminal N/sub D/ pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N/spl ges/1) distinct pipelining resources. In the case of a multiterminal pipelined signal, the problem is to find a minimum spanning tree (MST) that contains sufficient pipelining resources such that pipelining constraints at each sink are satisfied. In this paper, we first present an optimal algorithm for finding a lowest cost 1/sub D/ route. The optimal 1/sub D/ algorithm is then used as a building block for a greedy two-terminal N/sub D/ router. Next, we discuss the development of a multiterminal routing algorithm (PipeRoute) that effectively leverages both the 1/sub D/ and N/sub D/ routers. Finally, we present a preprocessing heuristic that enables the application of PipeRoute to pipelined FPGA architectures. PipeRoute's performance is evaluated by routing a set of benchmark netlists on the reconfigurable pipelined datapath (RaPiD) architecture. Our results show that the architecture overhead incurred in routing netlists on RaPiD is less than 20%. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

Previous research has shown both theoretically and practically that simulated annealing can greatly benefit from the incorporation of an adaptive range limiting window to control the acceptance ratio of swaps during placement. However, the implementation of such a system is not necessarily obvious. Existing range limiting techniques have several fundamental shortcomings when dealing with both standard island-style FPGAs and more exotic architectures. In this paper we discuss the nature of these problems and present a new algorithm that attempts to deal with these issues.

There have been many papers proposing the use of logarithmic numbers (LNS) as an alternative to floating point because of simpler multiplication, division and exponentiation computations. However, this advantage comes at the cost of complicated, inexact addition and subtraction, as well as the need to convert between the formats. In this work, we created a parameterized LNS library of computational units and compared them to an existing floating point library. Specifically, we considered multiplication, division, addition, subtraction, and format conversion to determine when one format should be used over the other and when it is advantageous to change formats during a calculation.

Reconfigurable logic fills a useful niche between the flexibility provided by a processor and the performance provided by custom hardware. This work presents the creation of domain-specific CPLD architectures, a project termed Totem-CPLD (part of the larger Totem project at UW). For the scope of this work, a CPLD is a collection of PLAs connected by a full crossbar, and they are made "domain-specific" by altering the input, product term, and output capacities of the PLAs in the architecture.

When designing systems-on-a-chip (SoCs), a unique opportunity exists to generate custom FPGA architectures that are specific to the application domain in which the device is used. The inclusion of such devices provides an efficient compromise between the flexibility of software and the performance of hardware, while at the same time allowing for post-fabrication modification of the SoC. To automate the layout of reconfigurable subsystems for systems-on-a-chip, we present the circuit generator method. The circuit generator method enables a designer to leverage the regularity that exists in FPGAs, creating structures that have only the needed resources to support the specified application domain. To facilitate this we have created generators that automatically produce the various components of the custom reconfigurable device. Compared to the unaltered full-custom tile, we achieve designs that are on average approximately 46% smaller and 16% faster, while continuing to support the algorithms in the particular application domain.

Current FPGA placement algorithms estimate the routability of a placement using architecture-specific metrics. The shortcoming of using architecture-specific routability estimates is limited adaptability. A placement algorithm that is targeted to a class of architecturally similar FPGAs may not be easily adapted to other architectures. The subject of this paper is the development of a routability-driven architecture adaptive FPGA placement algorithm called Independence. The core of the Independence algorithm is a simultaneous place-and-route approach that tightly couples a simulated annealing placement algorithm with an architecture adaptive FPGA router (Pathfinder). The results of our experiments demonstrate Independence's adaptability to island-style and hierarchical FPGA architectures. The quality of the placements produced by Independence is within 5% of the quality of VPR's placements and 17% better than the placements produced by HSRA's place-and-route tool. Further, our results show that Independence produces clearly superior placements on routing-poor island-style FPGA architectures.

Many system-on-a-chip devices would benefit from the inclusion of reprogrammable logic on the silicon die, as it can add general computing ability, provide run-time reconfigurability, or even be used for post-fabrication modifications. Also, by catering the logic to the SoC domain, additional area and delay gains can be achieved over current, more general reconfigurable fabrics. This paper presents tools that automate the creation of domain-specific CPLDs for SoC, including an architecture generator for finding appropriate architectures and a layout generator for creating efficient layouts. By tailoring CPLDs to the domains that they are supporting, we provide results that beat representative fixed architectures by 5.6/spl times/ to 11.9/spl times/ on average in terms of area-delay product.

Current FPGA placement algorithms estimate the routability of a placement using architecture-specific metrics. The shortcoming of using architecture-specific routability estimates is limited adaptability. A placement algorithm that is targeted to a class of architecturally similar FPGAs may not be easily adapted to other architectures. The subject of this paper is the development of a routability-driven architecture adaptive FPGA placement algorithm called Independence. The core of the Independence algorithm is a simultaneous place-and-route approach that tightly couples a simulated annealing placement algorithm with an architecture adaptive FPGA router (Pathfinder). The results of our experiments demonstrate Independence's adaptability to island-style FPGAs, a hierarchical FPGA architecture (HSRA), and a coarse-grained reconfigurable architecture (RaPiD). The quality of the placements produced by Independence is within 1.2% of the quality of VPRs placements. 17% better than the placements produced by HSRA's placer, and within 0.7% of RaPiD's placer. Further, our results show that Independence produces clearly superior placements on routing-poor island-style FPGA architectures.

The development of domain-specialized reconfigurable devices, and even the nature of domains themselves, has been largely unexplored. In part this is because the same architectural improvements that allow domain-specialized field programmable gate arrays (FPGAs) to outperform conventional reconfigurable devices also significantly change the design problem. The migration from completely generic lookup tables (LUTs) and highly connected routing fabrics to specialized coarse-grain functional units and very structured communication resources presents designers with the problem of how to best customize the system based upon anticipated usage. In this paper, the authors establish the nature of many of these problems and illustrate the difficulties of determining the appropriate number and ratio of functional units considering the demands of a diverse domain. The authors present three algorithms that attempt to balance the hardware needs of the domain while considering design constraints such as the performance and area of the system.

In this paper, we present an implementation of the image compression routine set partitioning in hierarchical trees (SPIHT) in reconfigurable logic. A discussion on why adaptive logic is required, as opposed to an application specific integrated circuit (ASIC), is provided along with background material on the image compression algorithm. We analyzed several discrete wavelet transform (DWT) architectures and selected the folded DWT design. In addition we provide a study on what storage elements are required for each wavelet coefficient. A modification to the original SPIHT algorithm is implemented to parallelize the computation. The architecture of our SPIHT engine is based upon fixed-order SPIHT, developed specifically for use within adaptive hardware. For an N/spl times/N image fixed-order SPIHT may be calculated in N/sup 2//4 cycles. Square images which are powers of 2 up to 1024/spl times/1024 are supported by the architecture. Our system was developed on an Annapolis Microsystems WildStar board populated with Xilinx Virtex-E parts. The system achieves a 450/spl times/ speedup versus a microprocessor solution, with less than a 0.2-db loss in peak signal-to-noise ratio over traditional SPIHT.

This paper presents an algorithm for lossy compression of hyperspectral images for implementation on field programmable gate arrays (FPGA). To greatly reduce the bit rate required to code images, linear prediction is used between the bands to exploit the large amount of inter-band correlation. The prediction residual is compressed using the set partitioning in hierarchical trees algorithm. To reduce the complexity of the predictive encoder, this paper proposes a bit plane-synchronized closed loop predictor that does not require full decompression of a previous band at the encoder. The new technique achieves almost the same compression ratio as standard closed loop predictive coding and has a simpler on-board implementation.

In this paper, we present a method for FPGA datapath precision optimization subject to user-defined area and error constraints. This work builds upon our previous research which presented a methodology for optimizing the dynamic range- the most significant bit position. In this work, we present an automated optimization technique for the least-significant bit position of circuit datapaths. We present results describing the effectiveness of our methods on typical signal and image processing kernels.

The focus of this work is the automatic generation of mask layouts, which is performed by the VLSI layouts, which is performed by the VLSI generator. This paper also presents method of automating the layout process, the template reduction method. The goal of the template reduction is not only the removal of unneeded routing resource, but also the removal of unneeded functional units. Benchmarking results show that template reduction method is able to reduce the number of functional units by an average of 45% and the routing resources by an average of 75%. It is found that the template reduction method produces circuits that are on average 53.4% smaller and 13.9% faster than the unreduced template.

We present a methodology for FPGA datapath precision optimization subject to user-defined area and error constraints. This work builds upon our previous research which presented a methodology for optimizing for dynamic range--the most significant bit position. In this work we define the problem of least significant bit optimization and propose optimization techniques that provide finer control of area-to-error tradeoffs than more traditional methods. We present some preliminary results describing the effectiveness of our techniques on typical signal and image processing kernels.

Traditional metrics used to compare hardware designs include area, performance, and power. However, these metrics do not form a complete evaluation of reconfigurable hardware. For these designs, flexibility is also a key issue, since it is the flexibility of reconfigurable hardware that allows it to implement a variety of circuits. Despite its importance, there is not yet an established method to measure flexibility. This paper explores the flexibility testing issue for domain-specific reconfigurable architectures. We discuss the concept of flexibility as it pertains to domain-specific architectures, and propose a flexibility testing technique involving synthetic circuit generation. This technique is then used to compare three different domain-specific architecture generation algorithms, demonstrating that the testing can in fact differentiate between architectures of differing levels of flexibility.

In this work, we parameterize and explore the interconnect structure of pipelined FPGAs. Specifically, we explore the effects of interconnect register population, length of registered routing track segments, registered IO terminals of logic units, and the flexibility of the interconnect structure on the performance of a pipelined FPGA. Our experiments with the RaPiD [4] architecture identify tradeoffs that must be made while designing the interconnect structure of a pipelined FPGA. The post-exploration architecture that we found shows a 19% improvement over RaPiD, while the area overhead incurred in placing and routing benchmarks netlists on the post-exploration architecture is 18%.

By strictly separating reconfigurable logic from the host processor, current custom computing systems suffer from a significant communication bottleneck. In this paper, we describe Chimaera, a system that overcomes the communication bottleneck by integrating reconfigurable logic into the host processor itself. With direct access to the host processor's register file, the system enables the creation of multi-operand instructions and a speculative execution model key to high-performance, general-purpose reconfigurable computing. Chimaera also supports multi-output functions and utilizes partial run-time reconfiguration to reduce reconfiguration time. Combined, the system can provide speedups of a factor of two or more for general-purpose computing, and speedups of 160 or more are possible for hand-mapped applications.

Although domain-specialized FPGAs (field programmable gate arrays) can offer significant area, speed and power improvements over conventional reconfigurable devices, there are several unique and unexplored design problems that complicate their development. One source of these problems is that the designers often opt to replace more universal, fine-grain logic elements with a specialized set of coarse-grain functional units to improve computation speed and reduce routing complexity. One issue this introduces is that it is not obvious how to simultaneously consider all applications in a domain and determine the most appropriate overall number and ration of the different functional units. In this paper, we illustrate how this problem manifests itself during the development of an encryption-specialized FPGA architecture. We present three algorithms that solve this problem by balancing the hardware needs of the domain while considering performance and area requirements. We believe these concerns need to be addressed by future CAD tools in order to develop more sophisticated application-specialized reconfigurable devices.

The design of a routing channel for an FPGA is a complex process, requiring the careful balance of flexibility with silicon efficiency. With the growing move towards embedding FPGAs into SoC designs, and the opportunity to automatically generate FPGA architectures, this problem becomes even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks on the tracks. This paper focuses on the last of these problems, the placement of breaks in tracks to maximize overall flexibility. We have developed both an optimal algorithm and a number of heuristics to solve the track placement problem. The optimal algorithm finds a best solution provided the problem meets a number of restrictions. Most of the heuristics are without restrictions, and the most promising of these find solutions on average within 1.13% of optimal. Full text available as UWEE Technical Report #UWEETR-2002-0013 at http://www.ee.washington.edu/.

We present a pipelining-aware router for FPGAs. The problem of routing pipelined signals is different from the conventional FPGA routing problem. For example, the two terminal N-Delay pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N > 1) distinct pipelining resources. In the case of a multi-terminal pipelined signal, the problem is to find a Minimum Spanning Tree that contains sufficient pipelining resources such that the delay constraint at each sink is satisfied. We begin this work by proving that the two terminal N-Delay problem is NP-Complete. We then propose an optimal algorithm for finding a lowest cost 1-Delay route. Next, the optimal 1-Delay router is used as the building block for a greedy two terminal N-Delay router. Finally, a multi-terminal routing algorithm (PipeRoute) that effectively leverages the 1-Delay and N-Delay routers is proposed. PipeRoute's performance is evaluated by routing a set of retimed benchmarks on the RaPiD [2] architecture. Our results show that the architecture overhead incurred in routing retimed netlists on RaPiD is less than a factor of two. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

Currently, few tools exist to aid the FPGA developer in translating an algorithm designed for a general-purpose-processor into one that is precision-optimized for FPGAs. This task requires extensive knowledge of both the algorithm and the target hardware. We present a design-time tool, Precis, which assists the developer in analyzing the precision requirements of algorithms specified in MATLAB. Through the combined use of simulation, user input, and program analysis, we demonstrate a methodology for precision analysis that can aid the developer in focusing their manual precision optimization efforts.

In this paper we present an implementation of the image compression routine SPIHT in reconfigurable logic. A discussion on why adaptive logic is required, as opposed to an ASIC, is provided along with background material on the image compression algorithm. We analyzed several discrete wavelet transform architectures and selected the folded DWT design. In addition we provide a study on what storage elements are required for each wavelet coefficient. The paper uses a modification to the original SPIHT algorithm needed to parallelize the computation. The architecture of the SPIHT engine is based upon fixed-order SPIHT, developed specifically for use within adaptive hardware. For an N /spl times/ N image fixed-order SPIHT may be calculated in N/sup 2//4 cycles. Square images which are powers of 2 up to 1024 /spl times/ 1024 are supported by the architecture. Our system was developed on an Annapolis Microsystems WildStar board populated with Xilinx Virtex-E parts.

One of the major overheads for reconfigurable computing is the time it takes to reconfigure the devices in the system. This overhead limits the speedup possible in this paradigm. In this paper we explore configuration prefetching techniques for reducing this overhead. By overlapping the configuration loadings with the computation on the host processor the reconfiguration overhead can be reduced. Our prefetching techniques target to the reconfigurable systems containing a Partial Reconfigurable FPGA with Relocation + Defragmentation (R+D model) since the R+D FPGA showed high hardware utilization. We have investigated various techniques including static configuration prefetching, dynamic configuration pre-fetching, and hybrid prefetching. We have developed prefetching algorithms that significantly reduce the reconfiguration overhead.

When designing SOCs, a unique opportunity exists to generate custom FPGA architectures that are specific to the application domain in which the device will be used. The inclusion of such a device will provide an efficient compromise between the flexibility of software and the performance of hardware, while at the same time allowing for post-fabrication modification of circuits. To automate the layout of reconfigurable subsystems for system-on -a-chip we present template reduction, standard cell, and circuit generator methods. We explore the standard cell method, as well as the creation of FPGA-specific standard cells. Compared to full custom circuits, we achieve designs that are 46% smaller and 36% faster when the application domain is well known in advance. In cases where no reduction from the full functionality is possible, the standard cell approach is 42% larger and 64% slower than full-custom circuits. Standard cells can thus provide competitive implementations, with significantly greater opportunity for adaptation to new domains.

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.

Many applications of FPGAs, especially logic emulation and custom computing, require the quick placement and routing of circuit designs. In these applications, the advantages FPGA-based systems have over software simulation are diminished by the long run-times of current CAD software used to map the circuit onto FPGAs. To improve the run-time advantage of FPGA systems, users may be willing to trade some mapping quality for a reduction in CAD tool runtimes. In this paper, we seek to establish how much quality degradation is necessary to achieve a given runtime improvement. For this purpose, we implemented and investigated numerous placement and routing algorithms for FPGAs. We also developed new tradeoff-oriented algorithms, where a tuning parameter can be used to control this quality vs. runtime tradeoff. We show how different algorithms can achieve different points within this tradeoff spectrum, as well as how a single algorithm can be tuned to form a curve in the spectrum. We demonstrate that the algorithms vary widely in their tradeoffs, with the fastest algorithm being 8x faster than the slowest, and the highest quality algorithm being 5x better than the least quality algorithm. Compared to the commercial Xilinx CAD tools, we can achieve a 3x speed-up by allowing 1.27x degradation in quality, and a factor of 1.6x quality improvement with 2x slowdown.

Recently, high-level languages such as MATLAB have become popular in prototyping algorithms in domains such as signal and image processing. Many of these applications whose subtasks have diverse execution requirements, often employ distributed, heterogeneous, reconfigurable systems. These systems consist of an interconnected set of heterogeneous processing resources that provide a variety of architectural capabilities. The objective of the MATCH (MATLAB Compiler for Heterogeneous Computing Systems) compiler project at Northwestern University is to make it easier for the users to develop efficient code for distributed heterogeneous, reconfigurable computing systems. Towards this end we are implementing and evaluating an experimental prototype of a software system that will take MATLAB descriptions of various applications, and automatically map them on to a distributed computing environment consisting of embedded processors, digital signal processors and field-programmable gale arrays built from commercial off-the-shelf components. We provide an overview of the MATCH compiler and discuss the testbed which is being used to demonstrate our ideas. We present preliminary experimental results on some benchmark MATLAB programs with the use of the MATCH compiler.

Custom computing systems exhibit significant speedups over traditional microprocessors by mapping compute-intensive sections of a program to reconfigurable logic (Hauck, 1998). However, the high overhead of reconfiguration can limit the execution times achievable with these systems. Research has shown that the ability to relocate and defragment configurations on an FPGA dramatically decreases the overall configuration overhead (Li et al., 2000). We therefore explore the adaptation of the Xilinx 6200 series FPGA for relocation and defragmentation. Due to some of the complexities involved with this structure, we also present a novel architecture designed from the ground up to provide relocation and defragmentation support with a negligible area increase over a generic partially reconfigurable FPGA.

Although run-time reconfigurable systems have been shown to achieve very high performance, the speedups over traditional microprocessor systems are limited by the cost of configuration of the hardware. We explore the idea of configuration caching. We present techniques to carefully manage the configurations present on the reconfigurable hardware throughout program execution. Through the use of the presented strategies, we show that the number of required reconfigurations is reduced, lowering the configuration overhead. We extend these techniques to a number of different FPGA programming models, and develop both lower bound and realistic caching algorithms for these structures.

Reconfigurable hardware has the potential for significant performance improvements by providing support for application-specific operations. We report our experience with Chimaera, a prototype system that integrates a small and fast reconfigurable functional unit (RFU) into the pipeline of an aggressive, dynamically-scheduled superscalar processor. Chimaera is capable of performing 9-input/1-output operations on integer data. We discuss the Chimaera C compiler that automatically maps computations for execution in the RFU. Chimaera is capable of: (1) collapsing a set of instructions into RFU operations, (2) converting control-flow into RFU operations, and (3) supporting a more powerful fine-grain data-parallel model than that supported by current multimedia extension instruction sets (for integer operations), Using a set of multimedia and communication applications bye show that even with simple optimizations. The Chimaera C compiler is able to map 22% of all instructions to the RFU on the average. A variety of computations are mapped into RFU operations ranging from as simple as add/sub-shift pairs to operations of more than 10 instructions including several branches. Timing experiments demonstrate that for a 4-way out-of-order superscalar processor Chimaera results in average performance improvements of 21%, assuming a very aggressive core processor design (most pessimistic RFU latency model) and communication overheads from and to the RFU.

Carry chains are an important consideration for most computations, including FPGA's. Current FPGA's dedicate a portion of their logic to support these demands via a simple ripple carry scheme. In this paper, we demonstrate how more advanced carry constructs can he embedded into PPGA's, providing significantly higher performance carry computations. We redesign the standard ripple carry chain to reduce the number of logic levels in each cell. We also develop entirely new carry structures based on high-performance adders such as carry select, carry lookahead, and Brent-Kung. Overall, these optimizations achieve a speedup in carry performance of 3.8 times over current architectures.

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.

One of the major overheads in reconfigurable computing is the time it takes to reconfigure the devices in the system. The configuration compression algorithm presented in our previous work [1] is one efficient technique for reducing this overhead. In this paper, we develop an algorithm for finding Don’t Care bits in configurations 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 achieves a compression ratio of a factor of 7, where our previous 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 [2]. 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 % [3] to 71 % [4] of their execution time performing reconfiguration. Thus, a

Logic partitioning is an important area of very large scale integration computer aided design and there have been numerous approaches proposed. Logic replication, the duplication of logic in order to minimize communication between partitions, can be an effective component of a complete partitioning solution. In this paper we seek a better understanding of the important issues in logic replication. By adding new optimizations to existing algorithms we are able to significantly improve the quality of these techniques, achieving up to 13.9% better results than the best existing replication techniques. When integrated into our already state-of-the-art (nonreplication) partitioner, we improve overall cutsizes by 38.8%, while requiring the duplication of at most 7% of the logic.

One of the major overheads in reconfigurable computing is the time it takes to reconfigure the devices in the system. This overhead limits the speedups possible in this exciting new paradigm. In this paper me explore one technique for reducing this overhead: the compression of configuration datastreams. We develop an algorithm, targeted to the decompression hardware imbedded in the Xilinx XC6200 series field-programmable gate array architecture, that can radically reduce the amount of data needed to transfer during reconfiguration. This results in an overall reduction of about a factor of four in total bandwidth required for reconfiguration.

Internet-based computing has significant potential for improving most high-performance computing, including VLSI CAD. In this paper we consider the ramifications of the Internet on electronics design, and develop two models for Web-based CAD. We also investigate the security of these systems, and propose methods for protection against threats both from unrelated users, as well as from the CAD tools and tool developers themselves. These techniques provide methods for hiding unnecessary information. Such techniques will be key to the development of future Internet-based CAD applications, since serious CAD users will be unwilling to use any CAD methodology that risks exposing their designs to outsiders. By enabling Web-based CAD, these techniques can improve CAD performance, enable collaboratory design, and create a usage-based pricing methodology.

One of the major overheads in reconfigurable computing is the time it takes to reconfigure the devices in the system. This overhead limits the speedups possible in this exciting new paradigm. In this paper we explore one technique for reducing this overhead: the compression of configuration datastreams. We develop an algorithm, targeted to the decompression hardware imbedded in the Xilinx XC6200 series FPGA architecture, that can radically reduce the amount of data needed to transfer during reconfiguration. This results in an overall reduction of almost 4 in total bandwidth required for reconfiguration.

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.

Carry chains are an important consideration for most computations, including FPGAs. Current FPGAs dedicate a portion of their logic to support these demands via a simple ripple carry scheme. In this paper we demonstrate how more advanced carry constructs can be embedded into FPGAs, providing significantly higher performance carry computations. We redesign the standard ripple carry chain to reduce the number of logic levels in each cell. We also develop entirely new carry structures based on high performance adders such as Carry Select, Carry Lookahead, and Brent-Kung. Overall, these optimizations achieve a speedup in carry performance of 3.8 times over current architectures.

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. Crossbar, Hierarchical Crossbar, and Mesh interconnection 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 interchip delays by more than 60% over the basic four-way Mesh.

By strictly separating reconfigurable logic from their host processor, current custom computing systems suffer from a significant communication bottleneck. In this paper we describe Chimaera, a system that overcomes this bottleneck by integrating reconfigurable logic into the host processor itself with direct access to the host processor's register file, the system enables the creation of multi-operand instruction and a speculative execution model key to high performance, general-purpose reconfigurable computing. It also supports multi-output functions, and utilizes partial run-time reconfiguration to reduce reconfiguration time. Combined, this system can provide speedups of a factor of two or more for general-purpose computing, and speedups of 160 or more are possible for hand-mapped applications.

Logic replication, the duplication of logic in order to limit communication between partitions, is an effective part of a complete partitioning solution. In this paper we seek a better understanding of the important issues in logic replication. By developing new optimizations to existing algorithms we are able to significantly improve the quality of these techniques, achieving up to 12.5% better results than the best existing replication techniques. When integrated into our already state-of-the-art partitioner we improve overall cutsizes by 37.8%, while requiring the duplication of at most 7% of the logic.

Logic partitioning is an important issue in VLSI CAD, and has been an area of active research for at least the last 25 years. Numerous approaches have been developed and many different techniques have been combined for a wide range of applications. In this paper, we examine many of the existing techniques for logic bipartitioning and present a methodology for determining the best mix of approaches The result is a novel bipartitioning algorithm that includes both new and preexisting techniques. Our algorithm produces results that are at least 16% better than the state of the art while also being efficient in run time.

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.

One of the critical issues for multi-FPGA systems is developing software tools for automatically mapping circuits. In this paper we consider one step in this process, partitioning. We described the task of finding partition orderings, i.e., determining the way in which a circuit should be bipartitioned so as to best map it to a multi-FPGA system. This allows multi-FPGA partitioners to harness standard partitioning techniques. We develop an algorithm for finding partition orderings, which includes a method for increasing parallelism in the process, as well as for including multi-sectioning and multi-way partitioning algorithms. This method is very efficient, and capable of handling most of the current multi-FPGA topologies.

Asynchronous design has been an active area of research since at least the mid 1950's, but has yet to achieve widespread use. We examine the benefits and problems inherent in asynchronous computations, and in some of the more notable design methodologies. These include Huffman asynchronous circuits, burst-mode circuits, micropipelines, template-based and trace theory-based delay-insensitive circuits, signal transition graphs, change diagrams, and complication-based quasi-delay-insensitive circuits.>

Field-programmable gate arrays (FPGAs) are an important implementation medium for digital logic. Unfortunately, they currently suffer from poor silicon area utilization due to routing constraints. In this paper we present Triptych, an FPGA architecture designed to achieve improved logic density with competitive performance. This is done by allowing a per-mapping tradeoff between logic and routing resources, and with a routing scheme designed to match the structure of typical circuits. We show that, using manual placement, this architecture yields a logic density improvement of up to a factor of 3.5 over commercial FPGAs, with comparable performance. We also describe Montage, the first FPGA architecture to fully support asynchronous and synchronous interface circuits.

Field-programmable gate arrays (FPGAs) are becoming an increasingly important implementation medium for digital logic. One of the most important keys to using FPGAs effectively is a complete, automated software system for mapping onto the FPGA architecture. Unfortunately, many of the tools necessary require different techniques than traditional circuit implementation options, and these techniques are often developed specifically for only a single FPGA architecture. In this paper we describe automatic mapping tools for Triptych, an FPGA architecture with improved logic density and performance over commercial FPGAs. These tools include a simulated-annealing placement algorithm that handles the routability issues of fine-grained FPGAs, and an architecture-adaptive routing algorithm that can easily be retargeted to other FPGAs. We also describe extensions to these algorithms for mapping asynchronous circuits to Montage, the first FPGA architecture to completely support asynchronous and synchronous interface applications.

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.>