This paper presents Gatling-V, an FPGA-optimized implementation of the RISC-V Vector extension that concurrently executes up to four vector instructions. The main innovation is using a multi-banked ASIC approach to build a vector register file from simple dual-port (1R1W) BRAMs rather than using traditional FPGA-based multi-port techniques. This saves both logic and BRAM, improves clock speed, and supports multiple overlapping in-flight instructions as well as vector chaining. However, it is limited to launching one vector instruction every two cycles. Using this technique, we build a RISC-V vector core that runs at 500MHz on AMD UltraScale+ HBM (16nm) with a 4R4W/8R8W register file and 2/4 fully parallel ALUs that use chaining (convoying) to reach peak utilization on sequentially dependent (independent) instructions with vectors longer than 36/72 (4/8) elements of 64b words, respectively. On microbenchmarks, the 4-ALU implementation is over 6 times faster than Saturn-V, an FPGA-optimized RISC-V vector engine, while consuming only twice as many LUTs but similar BRAMs and DSPs.

To date, the most promising methods for 8-bit DNN training use two different floating-point formats: a 5-bit ex-ponent for greater range on gradients in the backwards pass, and a 4-bit exponent with less range but greater precision for representing weights and activations in the forward pass. Ordinarily, subnormal representations are also used to extend the range and provide gradual underflow, but subnormals require considerable special-case logic which increases the cost of area-critical operators such as multiply-accumulate units. Instead, this paper proposes to replace traditional subnormals with what we call supernormal values where mantissa bits are converted into exponent bits at both the subnormal/zero and infinity ends of the range. Hence, supernormals provide maximal range extension by sacrificing some precision at both ends. The logic required to implement supernormals is a trivial change to existing logic that processes normalised values, thus avoiding the logic overhead of subnormals while providing a larger range extension. We use the range extension provided by supernormals in new mixed-precision 8-bit formats to showcase training results that are comparable to the state-of-the-art while showing an area savings.

Training Deep Neural Networks (DNNs) is computationally demanding, leading to a growing interest in reduced precision formats to enhance hardware efficiency. Several frame-works explore custom number formats with parameterizable precision through software emulation on CPUs or GPUs. However, they lack comprehensive support for different rounding modes and struggle to accurately evaluate the impact of custom precision for FPGA-based targets. This paper introduces MPTorch-FPGA, an extension of the MPTorch framework for performing custom, multi-precision inference and training computations in CPU, GPU, and FPGA environments in PyTorch. MPTorch-FPGA can generate a model-specific accelerator for DNN training, with customizable sizes and arithmetic implementations, providing bit-level accuracy with respect to emulated low precision DNN training on GPUs or CPUs. An offline matching algorithm selects one of several pre-generated (static) FPGA configurations using a custom performance model to estimate latency. To showcase the versatility of MPTorch-FPGA, we present a series of training benchmarks using diverse DNN models, exploring a range of number format configurations and rounding modes. We report both accuracy and hardware performance metrics, verifying the precision of our performance model by comparing estimated and measured latencies across multiple benchmarks. These results highlight the flexibility and practical value of our framework.

Custom hardware instructions are frequently used to accelerate software. However, the number of active custom instructions - and speedup opportunities - are limited in resourceconstrained systems, such as those using small embedded FPGAs (eFPGAs). Hence, it is desirable to be able to dynamically reconfigure this resource to allow an application to change the accelerator logic. While an existing method called CX Table is described the Draft CX Specification to manage accelerators, it is not suitable for lightweight embedded systems because (1) virtual memory is required to isolate processes, and (2) an implied table lookup is required when switching custom instruction sets. This paper presents CIA Direct, a lightweight alternative to CX Table. It moves the table into a privileged control register to avoid virtual memory and external memory accesses. It provides inter-process virtualization of accelerator state, but intra-process virtualization has performance limitations. This paper also describes CxBex, the first ASIC implementation of CIA Direct. It contains a hard RISC-V processor with an eFPGA to support multiple custom instruction accelerators under dynamic reconfiguration. Unique to CxBex, context switching keeps multiple independent state context intact in eFPGA block during reconfiguration. Intended for lightweight embedded systems, this work demonstrates that the CIA Direct approach is simpler, reduces CPU complexity, eliminates dependence on external memory, and manages dynamic reconfiguration using exceptions.

Embedded systems are becoming increasingly complex and heterogeneous, featuring multiple processor cores (which might themselves be heterogeneous) as well as specialized hardware accelerators, all accessing shared memory. Many accelerators are non-coherent (i.e., do not support hardware cache coherence) because it reduces hardware complexity, cost, and power consumption, while potentially offering superior performance. However, the disadvantage of non-coherence is that the software must explicitly synchronize between accelerators and processors, and this synchronization is notoriously error-prone. We propose an analysis technique to find data races in software for heterogeneous systems that include non-coherent accelerators. Our approach builds on classical results for data race detection, but the challenge turns out to be analyzing cache behavior rather than the behavior of the non-coherent accelerators. Accordingly, our central contribution is a novel, sound (data-race-preserving) abstraction of cache behavior. We prove our abstraction sound, and then to demonstrate the precision of our abstraction, we implement it in a simple dynamic race detector for a system with a processor and a massively parallel accelerator provided by a commercial FPGA-based accelerator vendor. On eleven software examples provided by the vendor, the tool had zero false positives and was able to detect previously unknown data races in two of the 11 examples.

Routing congestion is one of the many factors that need to be minimized during the physical design phase of large integrated circuits. In this article, we propose a novel congestion estimation method, called MEDUSA , that consists of three parts: (1) a feature extraction and “hyper-image” encoding; (2) a congestion estimation method using a fixed-resolution convolutional neural network model that takes a tile of this hyper-image as input and makes accurate congestion predictions for a small region of the circuit; and (3) a sliding-window method for repeatedly applying this convolutional neural network on a layout, thereby producing higher-resolution congestion maps for arbitrarily large circuits. The proposed congestion estimation approach works with both 2D (collapsed) and 3D global routing. Using both quantitative metrics and qualitative visual inspection, congestion maps produced with MEDUSA show better accuracy than prior estimation techniques. Global routers typically use estimation techniques during their first router iteration and then switch to using actual congestion information extracted from the intermediate router solutions. Experimental results within the same global router infrastructure show a significant impact on quality after the first routing iteration; other estimation techniques result in an average of 22% to 54% higher initial overflow counts. This initial quality improvement carries through to the final global routing solution, with other estimation techniques needing up to 5% more routing iterations and up to 3× more runtime, on average. Compared with other global routers, MEDUSA achieves comparable wire length results and lower total overflow counts (more legal global routing solutions) and is typically faster.

The most compute-intensive stage of deep neural network (DNN) training is matrix multiplication where the multiply-accumulate (MAC) operator is key. To reduce training costs, we consider using low-precision arithmetic for MAC operations. While low-precision training has been investigated in prior work, the focus has been on reducing the number of bits in weights or activations without compromising accuracy. In contrast, the focus in this paper is on implementation details beyond weight or activation width that affect area and accuracy. In particular, we investigate the impact of fixed- versus floating-point representations, multiplier rounding, and floating-point exceptional value support. Results suggest that (1) low-precision floating-point is more area-effective than fixed-point for multiplication, (2) standard IEEE-754 rules for subnormals, NaNs, and intermediate rounding serve little to no value in terms of accuracy but contribute significantly to area, (3) low-precision MACs require an adaptive loss-scaling step during training to compensate for limited representation range, and (4) fixed-point is more area-effective for accumulation, but the cost of format conversion and downstream logic can swamp the savings. Finally, we note that future work should investigate accumulation structures beyond the MAC level to achieve further gains.

Embedded systems are becoming increasingly complex and heterogeneous, featuring multiple processor cores (which might themselves be heterogeneous) as well as specialized hardware accelerators, all accessing shared memory. Many accelerators are non-coherent (i.e., do not support hardware cache coherence) because it reduces hardware complexity, cost, and power consumption, while potentially offering superior performance. However, the disadvantage of non-coherence is that the software must explicitly synchronize between accelerators and processors, and this synchronization is notoriously error-prone.

The success of DNN pruning has led to the development of energy-efficient inference accelerators that support pruned models with sparse weight and activation tensors. Because the memory layouts and dataflows in these architectures are optimized for the access patterns during inference, however, they do not efficiently support the emerging sparse training techniques. In this paper, we demonstrate (a) that accelerating sparse training requires a co-design approach where algorithms are adapted to suit the constraints of hardware, and (b) that hardware for sparse DNN training must tackle constraints that do not arise in inference accelerators. As proof of concept, we adapt a sparse training algorithm to be amenable to hardware acceleration; we then develop dataflow, data layout, and load-balancing techniques to accelerate it. The resulting system is a sparse DNN training accelerator that produces pruned models with the same accuracy as dense models without first training, then pruning, and finally retraining, a dense model. Compared to training the equivalent unpruned models using a state-of-the-art DNN accelerator without sparse training support, Procrustes consumes up to 3.26× less energy and offers up to 4× speedup across a range of models, while pruning weights by an order of magnitude and maintaining unpruned accuracy.

In this paper we investigate using low-level loop analysis to identify common loop patterns in the netlist generated by the synthesis flow and use loop optimization techniques to increase Fmax of applications implemented on Xilinx FPGAs. Ordinarily, feed-forward paths in the netlist can be easily pipelined. The focus of this study is only sequential loops (with feedback cycles) that are more challenging to optimize. We show using low-level loop analysis, we can improve Fmax on average by 57% and achieve an average Fmax of 714MHz across seven industrial designs. Using aggressive loop combining, we also show that we can save 18% area on average while still improving the Fmax by 15% to 41% on four of the seven designs.

Ternary Content Addressable Memories (TCAMs) are massively parallel search engines enabling the usage of "don't care" wildcards when searching for data. TCAMs are used in a wide variety of applications, such as routing tables for IP forwarding, which have been recently implemented using FPGAs. However, traditional "brute force" CAM architectures that use FPGA SRAM blocks (BRAMs) involve swapping address and data lines and are very inefficient. In this paper, a novel, efficient and modular technique for Longest-Prefix Match (LPM) TCAMs using FPGA BRAMs is proposed. Hierarchical search is exploited to achieve a linear storage growth and high storage efficiency. Compared to other methods, our LPM-TCAM design accommodates 5.5x more data for the same SRAM area without degrading the performance. A fully parameterized Verilog implementation is being released as an open source library. The library has been extensively tested using Altera's Quartus and ModelSim.

This paper presents an FPGA-based overlay for accelerating computer vision applications written in OpenVX. A software programmer simply writes an application using the standard OpenVX API. The OpenVX overlay consists of an architecture and a runtime system that runs any OpenVX application, unmodified, in an accelerated manner on an FPGA. The architecture uses a Soft Vector Processor (SVP) for general acceleration, and a library of Vector Custom Instructions (VCIs) to further accelerate specific OpenVX kernels in the FPGA fabric. The VCIs are predesigned in advance by a skilled FPGA designer. The runtime system analyzes the OpenVX computational graph and selects some kernel nodes to be executed by VCIs, with the remaining kernel nodes to be executed by the SVP. In making the selection, the runtime system uses an optimization algorithm and relies upon bitstream relocation and bitstream merging to fit multiple VCIs into a single, fixedsize Partially Reconfigurable Region (PRR). The optimization algorithm must select the VCIs that satisfy the area constraint of the PRR and give the best overall application acceleration. For example, on a Canny-blur OpenVX application, an 8-lane SVP achieves speedup of 5.3 over the hard ARM Cortex-A9. Selecting some nodes as VCIs provides another 3.5 times speedup, for an overall speedup of 18.5. The overlay enables OpenVX programmers with no FPGA design knowledge to accelerate their application.

Real-time vision applications place stringent performance requirements on embedded systems. To meet performance requirements, embedded systems often require hardware implementations. This approach is unfavorable as hardware development can be difficult to debug, time-consuming, and require extensive skill. This paper presents a case study of accelerating face detection, often part of a complex image processing pipeline, using a software/hardware hybrid approach. As a baseline, the algorithm is initially run on a scalar ARM Cortex-A9 application processor found on a Xilinx Zynq device. Next, using a previously designed vector engine implemented in the FPGA fabric, the algorithm is vectorized, using only standard vector instructions, to achieve a 25× speedup. Then, we accelerate the critical inner loops by adding two hardware-assisted custom vector instructions for an additional 10× speedup, yielding 248× speedup over the initial Cortex-A9 baseline. Collectively, the custom instructions require fewer than 800 lines of VHDL code, including comments and blank lines. Compared to previous hardware-only face detection systems, our work is 1.5 to 6.8 times faster. This approach demonstrates that good performance can be obtained from software-only vectorization, and a small amount of custom hardware can provide a significant acceleration boost.

With the rise of FPGA-based implementation of Computer Vision (CV) applications, the need for a programming method that achieves the target throughput or area-budget while retaining flexibility is magnified. High-level synthesis (HLS) tools provide this opportunity while eliminating the necessity of hardware engineering knowledge. Existing methods of programming FPGAs with HLS require the user to explicitly manage resources at every stage in their algorithm in order to meet a specified area target or throughput target. In this paper, we provide a framework for meeting such targets with compute graphs specified in OpenVX, a C-based programming environment for computer vision. To do this, we build our own OpenVX system using Xilinx Vivado HLS, and add an algorithmic layer which allows the user to specify an area budget (while maximizing throughput) or a throughput target (while minimizing area). Our OpenVX system consists of a series of compute kernels, prewritten in C++ for HLS and heavily parameterized as well as an Intra-node Optimizer to enable the creation of different size/throughput targets using different image tile-sizes. It also uses a heuristic algorithm with an Inter-node Optimizer step which combines/splits kernels and then replicates them to minimize the area cost. We evaluate the system on typical OpenVX benchmarks under a variety of fixed area constraints, and find that our system is able to automatically achieve over 95% area utilization. We also evaluate the system with same benchmarks under variety of fixed throughput targets, and find our system saves up to 30% in area cost compared to manually parallelized implementations. Our results show our heuristic approach is able to hit the same throughput targets and save 19% area on average compared to existing ILP approaches. While existing methods can easily achieve a single design point, they are unable to automatically generate a set of solutions from the same source; a prominent capability embedded in our tool. Moreover our tool uses Inter-node Optimizer to find better space/time tradeoffs.

Recent work has shown how multi-ported RAMs can be built out of dual-ported RAMs. Such techniques combine two structures: a set of "data banks" to hold the data, and a method for selecting the bank containing the last-written data, often called a live-value table (LVT). Most previous work has focused on the design of the LVT to reduce area and improve performance. In this paper, we instead reduce area by optimizing the design of the "data banks" portion. The optimization is embedded into a memory compiler that solves a set cover problem. When the set cover problem is solved optimally, the data banks use minimum area. Our technique applies to multi-ported RAMs that have a structural pattern we describe as "switched ports". Switched ports are a generalization of true ports, where a certain number of write ports can be dynamically switched into a possibly different number of read ports using one common read/write control signal. Furthermore, a given application may have multiple sets, each set with a different read/write control. While previous work generates multi-port RAM solutions that contain only true ports, or only simple ports, we contend that using only these two models is too limiting and prevents optimizations from being applied. Experimental results on 10 random instances of multi-port RAMs show 17% BRAM reduction on average compared to the best of other approaches. The compiler and a fully parameterized Verilog implementation is released as an open source library. The library has been extensively tested using Altera's EDA tools.

Multiported RAMs are essential for high-performance parallel computation systems. VLIW and vector processors, CGRAs, DSPs, CMPs, and other processing systems often rely upon multiported memories for parallel access. Although memories with a large number of read and write ports are important, their high implementation cost means that they are used sparingly. As a result, FPGA vendors only provide dual-ported block RAMs (BRAMs) to handle the majority of usage patterns. Furthermore, recent attempts to create FPGA-based multiported memories suffer from low storage utilization. Whereas most approaches provide simple unidirectional ports with a fixed read or write, others propose true bidirectional ports where each port dynamically switches read and write. True RAM ports are useful for systems with transceivers and provide high RAM flexibility; however, this flexibility incurs high BRAM consumption. In this article, a novel, modular, and BRAM-based switched multiported RAM architecture is proposed. In addition to unidirectional ports with fixed read/write, this switched architecture allows a group of write ports to switch with another group of read ports dynamically, hence altering the number of active ports. The proposed switched-ports architecture is less flexible than a true-multiported RAM where each port is switched individually. Nevertheless, switched memories can dramatically reduce BRAM consumption compared to true ports for systems with alternating port requirements. Previous live-value-table (LVT) and XOR approaches are merged and optimized into a generalized and modular structure that we call an invalidation-based live-value-table (I-LVT). Like a regular LVT, the I-LVT determines the correct bank to read from, but it differs in how updates to the table are made; the LVT approach requires multiple write ports, often leading to an area-intensive register-based implementation, whereas the XOR approach suffers from excessive storage overhead since wider memories are required to accommodate the XOR-ed data. Two specific I-LVT implementations are proposed and evaluated: binary and thermometer coding. The I-LVT approach is especially suitable for deep memories because the table is implemented only in SRAM cells. The I-LVT method gives higher performance while occupying fewer BRAMs than earlier approaches: for several configurations, BRAM usage is reduced by greater than 44% and clock speed is improved by greater than 76%. The I-LVT can be used with fixed ports, true ports, or the proposed switched ports architectures. Formal proofs for the suggested methods, resources consumption analysis, usage guidelines, and analytic comparison to other methods are provided. A fully parameterized Verilog implementation is released as an open source library. The library has been extensively tested using Altera’s EDA tools.

Binary Content Addressable Memories (BCAMs), also known as associative memories, are hardware-based search engines. BCAMs employ a massively parallel exhaustive search of the entire memory space, and are capable of matching a specific data within a single cycle. Networking, memory management, pattern matching, data compression, DSP, and other applications utilize CAMs as single-cycle associative search accelerators. Due to the increasing amount of processed information, modern BCAM applications demand a deep searching space. However, traditional BCAM approaches in FPGAs suffer from storage inefficiency. In this paper, a novel, efficient and modular technique for constructing BCAMs out of standard SRAM blocks in FPGAs is proposed. Hierarchical search is employed to achieve high storage efficiency. Previous hierarchical search approaches cannot be cascaded since they provide a single matching address, this incurs an exponential increase of RAM consumption as pattern width increases. Our approach, however, efficiently regenerates a match indicator for every single address by storing indirect indices for address match indicators. Hence, the proposed method can be cascaded and exponential growth is alleviated into linear. Our method exhibits high storage efficiency and is capable of implementing up to 9 times wider BCAMs compared to other approaches. A fully parameterized Verilog implementation is being released as an open source library. The library has been extensively tested using Altera's Quartus and Model Sim.

Overlays are emerging as useful design patterns for solving reconfigurable computing problems. Overlays consist of compiler-like tools and an architecture written in RTL, making it easier for users to quickly compile high-level languages into FPGAs. Despite a high degree of regularity and repetition present in most overlays, it takes a long time for FPGA tools to generate the configuration bit stream. This paper proposes a methodology called Rapid Overlay Builder, or ROB, that combines module relocation, module variants and an efficient form of "router less" module stitching that we call zipping. Our case study demonstrates up to 22 times speedup in compile-time over a regular Xilinx ISE compilation, while achieving higher clock speeds. By applying ROB, we anticipate that overlays can be implemented more quickly and with more consistent clock rates.

Soft vector processors can accelerate data parallel algorithms on FPGAs while retaining software programmability. To handle divergent control flow, vector processors typically use mask registers and predicated instructions. These work by executing all branches and finally selecting the correct one. Our work improves FPGA based vector processors by adding wavefront skipping, where wavefronts that are completely masked off are skipped. This accelerates conditional algorithms, particularly useful where elements terminate early if simple tests fail but require extensive processing in the worst case. The difference in logic speed and RAM area for FPGA based circuits versus ASICs led us to a different implementation than used in fixed vector processors, storing wavefront offsets in on-chip BRAM rather than computing wavefronts skipped dynamically. Additionally, we allow for partitioning the wavefronts so that partial wavefronts can skip independently of one another. We show that <5% extra area can give up to 3.2× better performance on conditional algorithms. Partial wavefront skipping may not be generally useful enough to be added to a fixed vector processor; it provides up to 65% more performance for up to 27% more area. In an FGPA, however, the designer can use it to make application specific tradeoffs between area and performance.

Floating point implementation has been a hot topic in recent FPGA research. This paper describes a method to optimize area of combined floating point and integer arithmetic unit through sharing the largest component in each operation on an FPGA. Specifically, the operations included are: addition, subtraction, multiplication, division, shift left/right, rotate left/right, as well as integer-to-floating-point and floating-point-to-integer conversion. The resource usage for the fused unit is compared with the segregated units that are multiplexed. Result shows a significant area reduction achieved using this technique with minimal performance penalty.

Field programmable gate array (FPGA) routing is one of the most time consuming steps in a typical computer-aided design flow. The problem itself is similar to the NP-complete problem of computing a set of disjoint paths in a graph. The routing resource graph (RRG) that represents an FPGA routing network is necessarily large, and becomes even larger when modeling modern FPGAs that integrate sparse intracluster routing crossbars. This paper introduces two scalable heuristics that reduce the runtime and memory footprint of FPGA routing: 1) selective RRG expansion (SERRGE), which employs an application-specific memory manager that stores the RRG in a compressed form, and dynamically decompresses it as the router proceeds and 2) partial prerouting (PPR) locally routes all nets within each logic cluster, followed by a global routing stage to complete the routes. PPR and SERRGE converge faster than a traditional router using a fully expanded RRG. PPR runs faster and uses less memory than SERRGE, while SERRGE yields the highest clock frequencies among the three.

Multi-ported RAMs are essential for high-performance parallel computation systems. VLIW and vector processors, CGRAs, DSPs, CMPs and other processing systems often rely upon multi-ported memories for parallel access, hence higher performance. Although memories with a large number of read and write ports are important, their high implementation cost means they are used sparingly in designs. As a result, FPGA vendors only provide dual-ported block RAMs to handle the majority of usage patterns. In this paper, a novel and modular approach is proposed to construct multi-ported memories out of basic dual-ported RAM blocks. Like other multi-ported RAM designs, each write port uses a different RAM bank and each read port uses bank replication. The main contribution of this work is an optimization that merges the previous live-value-table (LVT) and XOR approaches into a common design that uses a generalized, simpler structure we call an invalidation-based live-value-table (I-LVT). Like a regular LVT, the I-LVT determines the correct bank to read from, but it differs in how updates to the table are made; the LVT approach requires multiple write ports, often leading to an area-intensive register-based implementation, while the XOR approach uses wider memories to accommodate the XOR-ed data and suffers from lower clock speeds. Two specific I-LVT implementations are proposed and evaluated, binary and one-hot coding. The I-LVT approach is especially suitable for larger multi-ported RAMs because the table is implemented only in SRAM cells. The I-LVT method gives higher performance while occupying less block RAMs than earlier approaches: for several configurations, the suggested method reduces the block RAM usage by over 44% and improves clock speed by over 76%. To assist others, we are releasing our fully parameterized Verilog implementation as an open source hardware library. The library has been extensively tested using ModelSim and Altera's Quartus tools.

Soft vector processors (SVPs) achieve significant performance gains through the use of parallel ALUs. However, since ALUs are used in a time-multiplexed fashion, this does not exploit a key strength of FPGA performance: pipeline parallelism. This paper shows how streaming pipelines can be integrated into the datapath of a SVP to achieve dramatic speedups. The SVP plays an important role in supplying the pipeline with high-bandwidth input data and storing its results using on-chip memory. However, the SVP must also perform the housekeeping tasks necessary to keep the pipeline busy. In particular, it orchestrates data movement between on-chip memory and external DRAM, it pre- or post-processes the data using its own ALUs, and it controls the overall sequence of execution. Since the SVP is programmed in C, these tasks are easier to develop and debug than using a traditional HDL approach. Using the N-body problem as a case study, this paper illustrates how custom streaming pipelines are integrated into the SVP datapath and multiple techniques for generating them. Using a custom pipeline, we demonstrate speedups over 7,000 times and performance-per-ALM over 100 times better than Nios II/f. The custom pipeline is also 50 times faster than a naive Intel Core i7 processor implementation.

Binary Content Addressable Memories (BCAMs) are massively parallel search engines capable of searching the entire memory space in a single clock cycle. BCAMs are used in a wide range of applications, such as memory management, networks, data compression, DSP, and databases. Due to the increasing amount of processed information, modern BCAM applications demand a deep searching space. However, traditional BCAM approaches in FPGAs suffer from storage inefficiency. In this paper, a novel and efficient technique for constructing deep and narrow BCAMs out of standard SRAM blocks in FPGAs is proposed. This technique is most efficient for deep and narrow CAMs since the BRAM consumption is exponential to pattern width. Using Altera's Stratix V device, traditional methods achieve up to 64K-entry BCAM while the proposed technique achieves up to 4M entries. For the 64K-entry test-case, traditional methods consume 43 times more ALMs and achieves only one-third of the Fmax. A fully parameterized Verilog implementation is available1. This implementation has been extensively tested using Altera's tools.

Overclocking a CPU is a common practice among home-built PC enthusiasts where the CPU is operated at a higher frequency than its speed rating. This practice is unsafe because timing errors cannot be detected by modern CPUs and they can be practically undetectable by the end user. Using a timing speculation technique such as Razor, it is possible to detect timing errors in CPUs. To date, Razor has been shown to correct only unidirectional, feed-forward processor pipelines. In this paper, we safely overclock 2D arrays by extending Razor correction to cover bidirectional communication in a tightly coupled or lockstep fashion. To recover from an error, stall wavefronts are produced which propagate across the device. Multiple errors may arise in close proximity in time and space; if the corresponding stall wavefronts collide, they merge to produce a single unified wavefront, allowing recovery from multiple errors with one stall cycle. We demonstrate the correctness and viability of our approach by constructing a proof-of-concept prototype which runs on a traditional Altera FPGA. Our approach can be applied to custom computing arrays, systolic arrays, CGRAs, and also time-multiplexed FPGAs such as those produced by Tabula. As a result, these devices can be overclocked and safely tolerate dynamic, data-dependent timing errors. Alternatively, instead of overclocking, this same technique can be used to `undervolt' the power supply and save energy.

Custom instruction set extensions can substantially boost performance of reconfigurable softcore CPUs. While this approach is commonly tailored to one specific FPGA system, we are presenting a fine-grained FPGA-like overlay architecture which can be implemented in the user logic of various FPGA families from different vendors. This allows the execution of a portable application consisting of a program binary and an overlay configuration in a completely heterogeneous environment. Furthermore, we are presenting different optimizations for dramatically reducing the implementation cost of the proposed overlay architecture. In particular, this includes the mapping of the overlay interconnection network directly into the switch fabric of the hosting FPGA. Our case study demonstrates an overhead reduction of an order of magnitude as compared to related approaches.

Throughput processing involves using many different contexts or threads to solve multiple problems or subproblems in parallel, where the size of the problem is large enough that latency can be tolerated. Bandwidth is required to support multiple concurrent executions, however, and utilizing multiple external memory channels is costly. For small working sets, FPGA designers can use on-chip BRAMs achieve the necessary bandwidth without increasing the system cost. Designing algorithms around fixed-size local memories is difficult, however, as there is no graceful fallback if the problem size exceeds the amount of local memory. This paper introduces TputCache, a cache designed to meet the needs of throughput processing on FPGAs, giving the throughput performance of on-chip BRAMs when the problem size fits in local memory. The design utilizes a replay based architecture to achieve high frequency with very low resource overheads.

This paper presents the ZUMA open FPGA overlay architecture. It is an open-source, cross-compatible embedded FPGA architecture that is intended to overlay on top of an existing FPGA, in essence an ”FPGA-on-an-FPGA.” This approach has a number of benefits, including bitstream compatibility between different vendors and parts, compatibility with open FPGA tool Hows, and the ability to embed some programmable logic into systems on FPGAs without the need for releasing or recompiling the master netlist. These options can enhance design possibilities and improve designer productivity. Previous attempts to map an FPGA architecture into a commercial FPGA have had an area penalty of 100x at best [4]. Through careful architectural and implementation choices to exploit low-level elements of the host architecture, ZUMA reduces this penalty to as low as 40x. Using the VTR (VPR6) academic tool How, we have been able to compile the entire MCNC benchmark suite to ZUMA. We invite authors of other tool Hows to target ZUMA.

VENICE is a new soft vector processor (SVP) for FPGA applications that is designed for maximum through-put with a small number (1 to 4) of ALUs. By increasing clock speed and eliminating bottlenecks in ALU utilization, VENICE achieves over 2x better performance-per-logic block than VEGAS, the previous best SVP. VENICE is also simpler to program, as its instructions use standard C pointers into a scratchpad memory rather than vector registers.

This paper describes the compiler design for VENICE, a new soft vector processor (SVP). The compiler is a new back-end target for Microsoft Accelerator, a high-level data parallel library for C++ and C#. This allows us to automatically compile high-level programs into VENICE assembly code, thus avoiding the process of writing assembly code used by previous SVPs. Experimental results show the compiler can generate scalable parallel code with execution times that are comparable to hand-written VENICE assembly code. On data-parallel applications, VENICE at 100MHz on an Altera DE3 platform runs at speeds comparable to one core of a 3.5GHz Intel Xeon W3690 processor, beating it in performance on four of six benchmarks by up to 3.2x.

In floating-point datapaths synthesized on FPGAs, the shifters that perform mantissa alignment and normalization consume a disproportionate number of LUTs. Shifters are implemented using several rows of small multiplexers; unfortunately, multiplexer-based logic structures map poorly onto LUTs. FPGAs, meanwhile, contain a large number of multiplexers in the programmable routing network; these multiplexer are placed under static control of the FPGA's configuration bitstream. In this work, we modify some of the routing multiplexers in the intra-cluster routing network of a CLB in an FPGA to implement shifters for floating-point mantissa alignment and normalization; the number of CLBs required for these operations is reduced by 67%. If shifting is not required, the routing multiplexers that have been modified can be configured to operate as normal routing multiplexers, so no functionality is sacrificed. The area overhead incurred by these modifications is small, and there is no need to modify every routing multiplexer in the FPGA. Experiments show that there is no negative impact in terms of clock frequency or routability for benchmarks that do not use the dynamic multiplexers.

This work describes a novel approach to FPGA placement. Most conventional FPGA CAD flow clusters circuits into CLBs prior to placing it. We show that is it possible to achieve 28% and 21% improvement in wirelength and minimum channel width respectively, while suffering only 1.8% in critical path delay by placing individual LUTs directly. By utilizing a good parallel placer, the novel approach can achieve speedups over the conventional uni-processor placers as well.

Modern FPGAs employ sparse crossbars in their intra-cluster routing. Modeling these crossbars enlarges the routing resource graph (RRG), a data structure used by most FPGA routers, while enlarging the search space for finding legal routes. We introduce two scalable routing heuristics for FPGAs with sparse intra-cluster routing crossbars: SElective RRG Expansion (SERRGE), which compresses the RRG, and dynamically decompresses it during routing, and Partial Pre-Routing (PPR), which locally routes all nets in each cluster, and routes global nets afterwards. Our experiments show that: (1) PPR and SERRGE converge faster than a traditional router using a fully-expanded RRG; (2) they both achieve better routability than the traditional router, given a limited runtime budget, with SERRGE achieving 1–2% better routability than PPR, on average; and (3) PPR uses far less memory and runs much faster than SERRGE, making it ideal for high capacity FPGAs.

FPGAs are increasingly being used to implement many new applications, including pipelined processor designs. Designers often employ memories to communicate and pass data between these pipeline stages. However, one-cycle communication between sender and receiver is often required. To implement this read-immediately-after-write functionality, bypass registers are needed by most FPGA memory blocks. Read and write latencies to these memories and the bypass can limit clock frequencies, or require extra resources to further pipeline the bypass. Instead of further pipelining the bypass, this paper applies clock skew scheduling to memory write and read ports of a simple bypass circuit. We show that the clock skew provides an improved Fmaxwithout requiring the area overhead of the pipelined bypass. Many configurations of pipelined memory systems are implemented, and their speed and area compared to our design. Memory clock skew scheduling yields the best Fmaxof all techniques which preserve functionality, an improvement of 56% over the baseline clock speed, and 14% over the best conventional design. Furthermore, the suggested technique consumes 46% fewer resources than the next best performing technique.

This paper presents VENICE, a new soft vector processor (SVP) for FPGA applications. VENICE differs from previous SVPs in that it was designed for maximum throughput with a small number (1 to 4) of ALUs. By increasing clockspeed and eliminating bottlenecks in ALU utilization, VENICE can achieve over 2x better performance-per-logic block than VEGAS, the previous best SVP. While VENICE can scale to a large number of ALUs, a multiprocessor system of smaller VENICE SVPs is shown to scale better for benchmarks with limited innerloop parallelism. VENICE is also simpler to program, as its instructions use standard C pointers into a scratchpad memory rather than vector registers.

This paper presents VEGAS, a new soft vector architecture, in which the vector processor reads and writes directly to a scratchpad memory instead of a vector register file. The scratchpad memory is a more efficient storage medium than a vector register file, allowing up to 9x more data elements to fit into on-chip memory. In addition, the use of fracturable ALUs in VEGAS allow efficient processing of bytes, halfwords and words in the same processor instance, providing up to 4x the operations compared to existing fixed-width soft vector ALUs. Benchmarks show the new VEGAS architecture is 10x to 208x faster than Nios II and has 1.7x to 3.1x better area-delay product than previous vector work, achieving much higher throughput per unit area. To put this performance in perspective, VEGAS is faster than a leading-edge Intel processor at integer matrix multiply. To ease programming effort and provide full debug support, VEGAS uses a C macro API that outputs vector instructions as standard NIOS II/f custom instructions.

Modern FPGAs are used to implement a wide range of circuits, many of which have coarse-grained and fine-grained components. The ever-increasing size of these circuits places great demand on CAD tools to synthesize circuits faster and without loss in quality. Synthesizing coarse-grained components onto fine-grained FPGA resources is inefficient, and past attempts to optimize FPGAs for word-oriented datapaths have met with limited success. This paper presents a CAD flow to fully compile Verilog into a configuration bitstream for a new type of FPGA with time-multiplexed coarse-grained resources. We demonstrate two approaches with gains of 61x and 42x in synthesis time on average compared to QuartusII, but due to time-multiplexing and current synthesis limitations we achieve circuit speeds of 14x and 8.5x slower on average. We show the tools can also trade density for maximum clock frequency.

The battle of fixed function devices vs. programmable devices has been won by the programmables. The question facing us now is to determine what kinds of programmability to place on next generation systems/devices. Research and development on many applications has shown that different kinds of hardware and software programmability succeed for different application classes: powerful, singlethread-optimized CPUs continue to do very well for many applications; the General Purpose GPU is carving a niche in high throughput, parallel floating point codes in addition to its home turf of graphics; the FPGA is particularly good at variable bit-size computations and data steering, as well as parallel distributed control of networks. Future systems may well need all three types of these types of engines, and perhaps interesting mixtures of them. This is particularly true when we deal with the combined goals of optimizing cost, performance and energy.

This paper describes a parallel implementation of the timing-driven VPR~5.0 simulated annealing engine. By restricting the move distance to a confined neighborhood, it is possible to consider a large number of non-conflicting moves in parallel and achieve a deterministic result. The full timing-driven algorithm is parallelized, including the detailed timing analysis updates done periodically while placement progresses. The limited move slightly degrades the placement quality, but this is necessary to expose greater degrees of parallelism. The overall bounding box metric degrades about 11% and critical path delay metric degrades about 8% compared to VPR's original algorithm, but we show the amount of degradation is independent of the number of threads. Overall, the parallel implementation scales to a speedup of 123x using 25 threads compared to VPR. With additional tuning effort, we believe the algorithm can be scaled to a larger number of threads, perhaps even run on a GPU, with little additional quality degradation.

As process technology scales, the design effort and nonrecurring engineering (NRE) costs associated with the development of integrated circuits is becoming extremely high. Structured ASICs offer one solution to these problems. However, to realize their full potential, their performance and cost advantages, architectures, and CAD must be fully understood. We believe that this can lead to wider adoption of structured ASICs. In this paper, we take a step in this direction and investigate the area, delay, power, and cost tradeoffs in metal-programmable structured ASICs (MPSAs). In particular, we quantify the impact of the number of user-defined (custom) metal mask layers on these metrics. Results indicate that for lowest cost, the number of custom layers should be minimized, especially for small die sizes (e.g., less than 100${\hbox {mm}}^{2}$). Delay and power, however, can be improved by a few additional custom layers. With two custom metal layers, MPSAs can be 2$\times$–10$\times$cheaper than cell-based ICs (CBICs).

In this paper, we evaluate the performance of an FPGA-like interconnect fabric for structured ASICs which is based upon fixed metal and programmable vias. We call this type of device a via-programmed structured ASIC or VPSA. We look at two different types of VPSA routing fabrics: one uses jumper wiring and the other uses crossover wiring. The performance of these fabrics is compared against an ASIC-like interconnect fabric, otherwise known as a metal-programmed structured ASIC or MPSA, which can be configured by customizing metal and via layers. We study the impact of these routing fabrics on cost, area, power and delay metrics. The results for different fabrics span a wide range, suggesting the routing architecture plays a very important role in their overall performance and it should be thoroughly researched.

PERG is a pattern matching engine designed for locating pre-defined byte string patterns (rules) from the ClamAV virus signature database in a data stream. This paper presents PERG-Rx, an extension of PERG that adds limited regular expression support for wildcard patterns used by rules that represent polymorphic viruses. To reduce the amount of state needed to track so many regular expressions, PERG-Rx employs a lossy scheme which increases the rate of false positives detected as the required state grows. The scalability and dynamic updatability of the PERG-Rx architecture to database updates are also evaluated.

FPGA user clocks are slow enough that only a fraction of the interconnect's bandwidth is actually used. There may be an opportunity to use throughput-oriented interconnect to decrease routing congestion and wire area using on-chip serial signaling, especially for datapath designs which operate on words instead of bits. To do so, these links must operate reliably at very high bit rates. We compare wave pipelining and surfing source-synchronous schemes in the presence of power supply and crosstalk noise. In particular, supply noise is a critical modeling challenge; better models are needed for FPGA power grids. Our results show that wave pipelining can operate at rates as high as 5Gbps for short links, but it is very sensitive to noise in longer links and must run much slower to be reliable. In contrast, surfing achieves a stable operating bit rate of 3Gbps and is relatively insensitive to noise.

Recompiling a large circuit after making a few logic changes is a time-consuming process. We present an incremental placement algorithm for FPGAs that is focused on extremely fast runtime for changes which can be localized. It is capable of handling multiple changes across large regions of an FPGA. This is especially useful when used with a floorplan where a modified subcircuit is instantiated several times in the design hierarchy or where several subcircuits are modified. The algorithm is simpler and faster than past approaches because its insertion and legalization steps are based on CPU-efficient shifting steps which do not continuously evaluate the impact of each move on costs. Instead, any lost quality is recovered by a fast, low-temperature anneal at the end. When 35,000 out of 50,000 LUTs are modified, the incremental placement (including fast anneal) is 7 times faster than VPR's "fast placement" from scratch with only 2% quality degradation. The key concepts utilized in the incremental placement algorithm include uses of floor-planning constraints, CPU-efficient CLB shifting, super placement grid and a tuned annealing refinement process.

This paper describes PGR, an architectural technique to reduce dynamic power via GlitchLess or to improve performance via clock skew scheduling (CSS) and delay padding (DP). It is integrated into VPR 5.0, and is invoked after the routing stage. We use programmable delay elements (PDEs) as a novel architecture modification to insert delay on FF clock inputs, enabling all optimization steps to share it, avoiding multiple architecture modifications. The central theme of this paper is considering the trade-off between power and performance, and finding an appropriate compromise considering process variation and timing uncertainties. Overall, an average of 15% speedup can be achieved via CSS alone, or up to 37% for individual circuits. Although delay padding only benefits several circuits, the average improvement of those circuits is an additional 10% of the original period, or up to 23% for individual circuits. In addition, a new model to estimate glitching power is proposed, taking into account the analog behavior of glitch pulse width reduction as it travels along FPGA routing tracks. We show that the original glitch estimation method can underestimate glitching power by up to 48%, and overestimate by up to 15%. GlitchLess is performed on both the original VPR and post-CSS solutions. We are able to eliminate on average 16% of glitching power, and up to 63% for individual circuits.

A computational circuit is custom-designed hardware which promises to offer maximum speedup of computationally intensive software algorithms. However, the practical needs to manage development cost and many low-level physical design details erodes much of the potential speedup by distracting attention away from high-level architectural design. Instead, designers need an inexpensive, processor-like platform where computational circuits can be rapidly synthesized and simulated. This enables rapid architectural evolution and mitigates the risk of producing custom hardware. In this paper we present a tool flow (RVETool) for compiling computational circuits into a massively parallel processor array (MPPA). We demonstrate the CAD runtime is on average 70x faster than FPGA tools, with a circuit speed 6.4x slower than FPGA devices. Unlike the fixed logic capacity of FPGAs, RVETool can trade area for simulation performance by targeting a wide range of processor cores.

Wave pipelining has gained attention for NoC interconnect by its promise of high bandwidth using simple circuits. Reliability issues must be addressed before wave pipelining can be used in practice; so, we develop a statistical model of dynamic timing uncertainty. We show that it is important to distinguish between static and dynamic sources of timing uncertainty, because source-synchronous wave pipelining is much more sensitive to the latter. We use HSPICE simulations to develop a model for a wave pipelined link in a 65 nm CMOS process and apply a statistical approach to determine the achievable throughput at acceptable bit-error rates. Reliability estimates show that a modest amount of dynamic noise can cut achievable throughput in half for a ten-stage wave-pipelined link, and will further degrade longer links. After accounting for noise, traditional globally synchronous design is shown to offer higher throughput than the wave-pipelined design.

Current FPGA soft processor systems use dedicated hardware modules or accelerators to speed up data-parallel applications. This work explores an alternative approach of using a soft vector processor as a general-purpose accelerator. The approach has the benefits of a purely software-oriented development model, a fixed ISA allowing parallel software and hardware development, a single accelerator that can accelerate multiple applications, and scalable performance from the same source code. With no hardware design experience needed, a software programmer can make area-versus-performance trade-offs by scaling the number of functional units and register file bandwidth with a single parameter. A soft vector processor can be further customized by a number of secondary parameters to add or remove features for a specific application to optimize resource utilization. This article introduces VIPERS, a soft vector processor architecture that maps efficiently into an FPGA and provides a scalable amount of performance for a reasonable amount of area. Compared to a Nios II/s processor, instances of VIPERS with 32 processing lanes achieve up to 44× speedup using up to 26× the area.

Multicore processors are now commodity items, and this has created an unprecedented buzz about exploiting parallelism to maximize performance. This is publicity has renewed interest in a long-standing problem: how much parallelism can we really exploit? Can extreme parallel computing be successfully delivered to the masses?

Modern FPGAs can implement large, custom compute engines that are designed to exploit extreme amounts of parallel computation. Through parallelism, these systems achieve orders of magnitude higher performance than the fastest microprocessors. Building such custom compute engines with existing hardware design languages is too difficult and time-consuming. For this to become mainstream technology, the task of designing such parallel systems must be as simple as possible. Thus, high-level languages are needed which can specify a custom compute engine or be compiled to run on predesigned parallel systems. In this workshop, we will examine several approaches for specifying extremely parallel computations in high-level languages. These can be used to build parallel systems in FPGAs, or they can be used to specify parallel computations in other competing architectures. By examining several different approaches, one gains insight into the best approach for solving a given problem. Ideally, this will also inspire new approaches for designing with extreme parallelism

The currently accepted method of accelerating applications in FPGA soft processor systems is to design a custom hardware accelerator. This paper suggests the alternative approach of adding a vector processing core to the soft processor as a general-purpose accelerator. The approach has the benefit of a purely software-oriented development model. With no hardware design experience needed, a software programmer can make area-versus-performance tradeoffs by scaling the number of functional units or vector lanes. This paper shows that a vector processing architecture maps efficiently into an FPGA and provides a scalable amount of performance for a reasonable amount of area. Three configurations of the soft vector processor with different performance levels are estimated to achieve scalable speedup ranging from 3-29x for 6-30x the area of a Nios II/s processor on three benchmark kernels. The results compare favourably to accelerators designed using Altera's C2H compiler, a C-to-hardware tool that is also easy to use

PERG is an FPGA application that accelerates the process of searching a stream of bytes against a large, fixed database of string patterns. The stream could be network, disk, or file traffic, while the pattern database may represent computer viruses, spam, keyword sequences, or watermarks. A full pattern, or rule, consists of a sequence of one or more segments separated by gaps. Each segment is an exact sequence of bytes, possibly 100s of bytes long. Each gap contains arbitrary bytes, but is a known length. PERG uses a pattern compiler to transform a database of these rules into a hardware implementation. To the authorspsila knowledge, this is the first pattern match engine hardware designed for large virus databases. It is also first among network intrusion detection systems (NIDS), which are similar in nature to PERG, to implement Bloomier filters. Like hash tables, Bloomier filters produce false positives due to aliasing, so all potential matches must be verified by exact matching. However, Bloomier filters are more powerful than their ancestral Bloom filters because they can identify the exact rule of a potential match. This enables two key advantages for PERG. First, it allows PERG to use a checksum to very efficiently reduce false positives. Second, exact matching with PERG filters is much faster than with Bloom filter systems because only one suspect pattern needs to be checked, not all patterns. To reduce memory requirements, PERG packs as many segments as possible into each Bloomier filter by consolidating several different segment lengths into the same filter unit. This is done by dividing each segment into two smaller but overlapping fragments of the same length. Dividing into non-overlapping fragments would create shorter fragments of uneven lengths, leading to higher false positives and differing lengths to consolidate later. Using the ClamAV antivirus database, PERG fits 80,282 patterns containing over 8,224,848 characters into a single modest FPGA chip with a small (4 MB) off-chip memory. It uses just 26 filter units, resulting in roughly 26x improved density (characters per memory bit) compared to the next-best NIDS pattern match engine which fits only 1/250ththe characters. PERG can scan at roughly 200 MB/s and match the speed of most network or disk interfaces.

CAD tool designers are always searching for more benchmark circuits to stress their software. In this article we present a heuristic method to generate benchmark circuits specially suited for incremental place-and-route tools. The method removes part of a real circuit and replaces it with an altered version of the same circuit to mimic an incremental design change. The alteration consists of two steps: mutate followed by perturb . The perturb step exactly preserves as many circuit characteristics as possible. While perturbing, reproduction of interconnect locality, a characteristic that is difficult to measure reliably or reproduce exactly, is controlled using a new technique, ancestor depth control (ADC). Perturbing with ADC produces circuits with postrouting properties that match the best techniques known to-date. The mutate step produces targetted mutations resulting in controlled changes to specific circuit properties (while keeping other properties constant). We demonstrate one targetted mutation heuristic, scale, to significantly change circuit size with little change to other circuit characteristics. The method is simple enough for inclusion in a CAD tool directly, and fast enough for use in on-the-fly benchmark generation.

This paper describes GlitchLess, a circuit-level technique for reducing power in field-programmable gate arrays (FPGAs) by eliminating unnecessary logic transitions called glitches. This is done by adding programmable delay elements to the logic blocks of the FPGA. After routing a circuit and performing static timing analysis, these delay elements are programmed to align the arrival times of the inputs of each lookup table (LUT), thereby preventing new glitches from being generated. Moreover, the delay elements also behave as filters that eliminate other glitches generated by upstream logic or off-chip circuitry. On average, the proposed implementation eliminates 87% of the glitching, which reduces overall FPGA power by 17%. The added circuitry increases the overall FPGA area by 6% and critical-path delay by less than 1%. Furthermore, since it is applied after routing, the proposed technique requires little or no modifications to the routing architecture or computer-aided design (CAD) flow.

This paper describes a technique that reduces dynamic power in FPGAs by reducing the number of glitches in the global routing resources. The technique involves adding programmable delay elements within the logic blocks of an FPGA to programmably align the arrival times of early-arriving signals to the inputs of the lookup tables and to filter out glitches generated by earlier circuitry. On average, the proposed technique eliminates 91% of the glitching, which reduces overall FPGA power by 18%. The added circuitry increases overall area by 5% and critical-path delay by less than 1%. Furthermore, since it is applied after routing, the proposed technique requires no modifications to the existing FPGA routing architecture or CAD flow.

Embedded applications today require high computational power that is not met by current FPGA-based soft processors. Although performance of data-parallel applications can be addressed by custom-designed hardware accelerators, such an approach is difficult for embedded software developers with little hardware design experience. Instead, vector processing can be used to speed up these same data-parallel applications. The vector programming model is easy to understand by software developers, making it easier for them to extract the parallelism without any hardware design knowledge. This paper proposes a soft vector processor for the Stratix III FPGA that can be scaled to different levels of performance and resource utilization. It has several configurable features that can be included or excluded to optimize the soft processor for a given application. Performance estimates of the soft vector processor using three embedded benchmark kernels show speedup of up to 16.6 x over an idealized Nios II processor while using 10.9 x the area.

FPGA architects are always searching for more benchmark circuits to stress CAD tools and device architectures. In this paper we present a new method to generate benchmark circuits by removing part of a real circuit and replacing it with a synthetic clone. This replacement or stitching process can easily introduce combinational loops if the synthetic circuit contains an input-to-output dependence that was not in the original subcircuit it is replacing. We show that this can be expressed as the graph monomorphism problem, and that a solution to that problem gives a precise stitching assignment that is cycle-free. This technique can be used to create new benchmark circuits that are identical to the original circuit except for small, local changes. The resulting semi-synthetic benchmarks are ideal for testing incremental place and route tools.

Each new semiconductor technology node brings smaller transistors and wires. Although this makes transistors faster, wires get slower. As FPGA device designers strive to obtain the lowest possible circuit delays from a given technology node, they must take an increasingly interconnect-focused viewpoint in the design process. In particular, for long interconnect wires, signals now require rebuffering somewhere in the middle of the wire. This paper presents a framework for designing and evaluating long, buffered interconnect wires in FPGAs with near-optimal delay performance. Given a target physical wire length, width and spacing, the method determines the number, size, and position of buffers required to obtain the fastest signal velocity for programmable interconnect. A metric introduced during the design is the "path delay profile", or the arrival time of a signal at different points of a long wire. This method is used to design buffering strategies for interconnect based on 0.5mm, 2mm, and 3mm wire lengths in 180nm technology. These interconnect designs are coded into VPR along with an improved timing analyzer which accurately determines the "path delay profile" arrival times. Using VPR, average critical-path delay is reduced by 19% for 0.5mm wires and by up to 46% for 3mm wires over previous designs given in Lemieux et al. (2004)

FPGA architects are always searching for more benchmark circuits to stress CAD tools and device architectures. In this paper we present a new heuristic to generate benchmark circuits specifically for incremental place and route tools. The method removes part of a real circuit and replaces it with a modified version of the same circuit to mimic an incremental design change. The generation procedure exactly preserves key circuit characteristics and achieves a post-routing channel width, critical path, and wire length that closely approximates those of the original circuit. Additionally, the method is fast and thus is suitable for use in on-the-fly benchmark generation

FPGA device area is dominated by interconnect, so low-cost FPGA architectures often have reduced interconnect capacity. This limited routing capacity creates a hard channel width constraint that can make it difficult for CAD tools to successfully map a circuit into these devices. Instead of migrating a design to a high-cost, resource-rich architecture that is easier to route, we present a cheaper alternative: a fully automated CAD flow (Un/DoPack) that finds local regions of high interconnect demand and reduces it by spreading out the logic in that region. This is done by introducing whitespace in the form of empty logic elements (LEs) within the configurable logic blocks (CLBs) of the congested region. After spreading, the congested region occupies more routing channels and so obtains access to greater aggregate interconnect capacity. Although this has the side effect of using more CLBs, it has the advantage of lowering peak interconnect demands and making a previously-unroutable circuit routable. We also design a new set of synthetic benchmark circuits that model interconnect variation within a large design. Using these benchmarks, we show that circuits with high interconnect variation require FPGA devices to have large channel widths. However, since congestion of such circuits is localized, Un/DoPack is very good at reducing the peak demands of circuits with high interconnect variation. Our results suggest that even for an average Rent exponent of 0.62 (a modest value), a large variation of this exponent within a design will also require FPGAs to have large channel widths. Thus, it is crucial to study interconnect variation of benchmark circuits when designing lowcost FPGAs. Previous research studying interconnect properties focuses on average Rent exponent values of each design, but we believe new work should study variation as well. For circuits with high interconnect variation, we demonstrate that channel widths can be reduced by up to ~40% with only ~10% increase in area.

Over the past ten years, as integrated circuits became increasingly more complex and expensive, the industry began to embrace new design and reuse methodologies that are collectively referred to as system-on-chip (SoC) design. In this paper, we focus on the reuse and integration issues encountered in this paradigm shift. The reusable components, called intellectual property (IP) blocks or cores, are typically synthesizable register-transfer level (RTL) designs (often called soft cores) or layout level designs (often called hard cores). The concept of reuse can be carried out at the block, platform, or chip levels, and involves making the IP sufficiently general, configurable, or programmable, for use in a wide range of applications. The IP integration issues include connecting the computational units to the communication medium, which is moving from ad hoc bus-based approaches toward structured network-on-chip (NoC) architectures. Design-for-test methodologies are also described, along with verification issues that must be addressed when integrating reusable components.

In this paper we present a system level technique for mapping large, multiple-IP-block designs to channel-width constrained FPGAs. Most FPGA clustering tools [2, 3, 11] aim to reduce the amount of inter-cluster connections, hence reducing channel width needs. However, if this exceeds the FPGA's channel width (a hard constraint), then the circuit still cannot be routed. Previous work [11, 12] depopulates logic clusters (CLBs) to reduce channel width. By depopulating non-uniformly, i.e. depopulate more in hard-to-route regions, we show a graceful trade-off between channel width and CLB count. This makes it possible to target specific channel-width constraints during clustering with minimal CLB inflation. Results show channel width decreases of up to 20% with a 5% increase in area. Further decreases of nearly 50% are possible at 3.3 times the original area. Despite the area increase, this technique creates routable solutions from otherwise-unroutable circuits.

Future process nodes have such small feature sizes that there will be an increase in the number of manufacturing defects per die. For large FPGAs, it will be critical to tolerate multiple defects (Campregher et al., 2005). We propose a number of changes to the detailed routing architecture of island-style FPGAs to tolerate multiple random, distributed interconnect defects without re-routing and with minimal impact on signal timing. Our scheme is a user option prebuilt into an architecture, requiring +11% area for additional multiplexers. Unused (spare) wiring tracks are also needed, bringing total overhead to 24% to tolerate stuck-at or open faults, or 34% to include bridging. User circuits that do not fully stress the routing network already have these tracks freely available. The delay penalty is programmable: 5-10% if defect rates are expected to be sufficiently low, but can be as high as 25% if defect rates are high. Our schemes can tolerate more than 10 interconnect defects for large array sizes of 128 /spl times/ 128. Unlike row/column redundancy schemes, our schemes are scalable: they naturally tolerate more defects as the FPGA array size increases. This work is the first detailed analysis of fine-grained defect-tolerant schemes in FPGAs.

Modern FPGA architectures from Altera and Xilinx have shifted away from allowing multiple drivers to connect to each interconnect wire. This work advocates the need for this shift to single-driver wiring by investigating the necessary architectural and circuit design changes. When single-driver wiring is used, area improves by 25%, delay improves by 9%, and area-delay improves by 32% compared to bidirectional wiring. Wiring capacitance is reduced by 37% due to reduced switch loading and physical wire length shrinkage. Furthermore, it is shown that larger circuits tend to realize larger savings. No significant CAD tool changes are needed.

This paper examines circuit design of buffered routing switches in symmetrical, island-style FPGAs. The effects of switch size, tile length, level-restoring, and slow input slew rates are examined. Two new fanin-based switch designs are used to eliminate nearly all of the increase in delay that arises from fanout with a previous switch design. Alternating between buffers and pass transistors is shown to improve connection delay without fanout by 25%. To take advantage of this, we propose schemes to replace some buffers with pass transistors to simultaneously reduce area and delay. Routing a suite of MCNC benchmark circuits shows that 14% in area-delay, or 7% in delay can be saved using the new switch schemes. Alternatively, approximately 13% in area can be saved with no degradation to delay.

In FPGAs, the internal connections in a cluster of lookup tables (LUTs) are often fully-connected like a full crossbar. Such a high degree of connectivity makes routing easier, but has significant area overhead. This paper explores the use of sparse crossbars as a switch matrix inside the clusters between the cluster inputs and the LUT inputs. We have reduced the switch densities inside these matrices by 50% or more and saved from 10 to 18% in area with no degradation to critical-path delay. To compensate for the loss of routability, increased compute time and spare cluster inputs are required. Further investigation may yield modest area and delay reductions.

A method for evaluating and constructing sparse crossbars which are both area efficient and highly routable is presented. The evaluation method uses a network flow algorithm to accurately compute the percentage of random test vectors that can be routed. The construction method attempts to maximize the spread of the switch locations, such that any given subset of input wires can connect to as many output wires as possible. Based on Hall's Theorem, we argue that this increases the likelihood of routing.

Small-scale multiprocessors are becoming increasingly economical and common, whereas larger multiprocessors continue to have higher per-node costs. The NUMAchine multiprocessor project seeks to make large-scale multiprocessors more economical while maintaining high performance by exploring architectural and hardware features for low-cost, modular multiprocessors. To demonstrate our approach, we have implemented a prototype system that is scalable to 128 processors. An efficient directory-based cache coherence protocol exploits our hierarchical ring-based interconnect and supports sequential consistency. This paper documents the design choices and the resulting performance of the system using both simulation results and measurements on the prototype hardware.

This paper describes the design and implementation of the NUMAchine multiprocessor. As the market for CC-NUMA multiprocessors expands, this research project provides a timely architectural design and cost-effective prototype. The key to the successful implementation of our 48-processor prototype is the use of off-the-shelf components and programmable logic devices. Since this machine will serve as a research vehicle for parallel software development, a number of hardware features to enhance experimentation have been included in the design.

We present results which show that a separate global and detailed routing strategy can be competitive with a combined routing process.Under restricted architectural assumptions, we compute a new lower bound for detailed routing and show that our detailed router typically requires no more than two extra routing tracks above this computed limit.Also, experimental results show that the Mapping Anomaly presented in [20], which suggests that separated routing may yield arbitrarily poor results in certain instances, is a concern only if nets are restricted to a single track domain.Finally, to motivate future work, we show the latest two-step routing results that we have achieved with the VPR global router and SEGA detailed router tools on the largest CBL benchmark circuits.j Penllis&m to m&e digitnl/hnrd copies ofall or port of this materin for personal or chwoom use is granted witbout fee provided that the copies are not made or distributed for profit or commercial advantage.the COPY-._.-_._-. .~