Reduction of Power Consumption in FPGAs - An Overview <s> FPGA Routing Resources Architecture <s> The relationship between the routability of a field-programmable gate array (FPGA) and the flexibility of its interconnection structures is examined. The flexibility of an FPGA is determined by the number and distribution of switches used in the interconnection. While good routability can be obtained with a high flexibility, a large number of switches will result in poor performance and logical density because each switch has significant delay and area. The minimum number of switches required to achieve good routability is determined by implementing several industrial circuits in a variety of interconnection architectures. These experiments indicate that high flexibility is essential for the connection block that joins the logic blocks to the routing channel, but a relative low flexibility is sufficient for switch blocks at the junction of horizontal and vertical channels. Furthermore, it is necessary to use only a few more routing tracks than the absolute minimum possible with structures of surprisingly low flexibility. > <s> BIB001 </s> Reduction of Power Consumption in FPGAs - An Overview <s> FPGA Routing Resources Architecture <s> In this paper, we present a bottom-up clustering algorithm based on recursive collapsing of small cliques in a graph. The sizes of the small cliques are derived using random graph theory. This clustering algorithm leads to a natural parallel implementation in which multiple processors are used to identify clusters simultaneously. We also present a cluster-based partitioning method in which our clustering algorithm is used as a preprocessing step to both the bisection algorithm by Fiduccia and Mattheyses and a ratio-cut algorithm by Wei and Cheng. Our results show that cluster-based partitioning obtains cut sizes up to 49.6% smaller than the bisection algorithm, and obtains ratio cut sizes up to 66.8% smaller than the ratio-cut algorithm. Moreover, we show that cluster-based partitioning produces much stabler results than direct partitioning. <s> BIB002 </s> Reduction of Power Consumption in FPGAs - An Overview <s> FPGA Routing Resources Architecture <s> In this paper, we present a general synthesis system for SRAM-based FPGAs named RASP. RASP consists of a core with a set of synthesis and optimization algorithms for technology independent logic synthesis and technology mapping for generating generic look-up tables (LUTs), together with a set of architecture-specific technology mapping routines to map the generic LUT network to programmable logic blocks (PLBs) for various SRAM-based FPGA architectures. Via a set of design representation converter routines, these architecture-independent and dependent synthesis algorithms are easily linked, and the entire system is seamlessly integrated into the design flow of commercial FPGA design systems. As a result, RASP can produce highly optimized designs for various SRAM-based FPGA architectures, and can be quickly adapted for new SRAM-based FPGA architectures. We compare RASP performance with that of several commercial synthesis systems on the MCNC logic synthesis benchmarks and a video compressor/decompressor. For almost all cases, RASP produces mapping solutions with significantly smaller critical path delay after place and route than current commercial synthesis systems. <s> BIB003 </s> Reduction of Power Consumption in FPGAs - An Overview <s> FPGA Routing Resources Architecture <s> Cut enumeration is a common approach used in a number of FPGA synthesis and mapping algorithms for consideration of various possible LUT implementations at each node in a circuit. Such an approach is very general and flexible, but often suffers high computational complexity and poor scalability. In this paper, we develop several efficient and effective techniques on cut enumeration, ranking and pruning. These techniques lead to much better runtime and scalability of the cut-enumeration based algorithms; they can also be used to compute a tight lower-bound on the size of an area-minimum mapping solution. For area-oriented FPGA mapping, experimental results show that the new techniques lead to over 160X speed-up over the original optimal duplication-free mapping algorithm, achieve mapping solutions with 5-21% smaller area for heterogeneous FPGAs compared to those by Chortle-crf, MIS-pga-new, and TOS-TUM, yet with over 100X speed-up over MIS-pganew and TOS-TUM. <s> BIB004 </s> Reduction of Power Consumption in FPGAs - An Overview <s> FPGA Routing Resources Architecture <s> This paper attempts to quantify the optimality of FPGA technology mapping algorithms. We develop an algorithm, based on Boolean satisfiability (SAT), that is able to map a small subcircuit into the smallest possible number of lookup tables (LUTs) needed to realize its functionality. We iteratively apply this technique to small portions of circuits that have already been technology mapped by the best available mapping algorithms for FPGAs. In many cases, the optimal mapping of the subcircuit uses fewer LUTs than is obtained by the technology mapping algorithm. We show that for some circuits the total area improvement can be up to 67%. <s> BIB005
Routing resources in FPGAs can be divided into two components; segmented local routing and dedicated routing. Segmented local routing is used to provide connection among the logic blocks. As depicted in Figure  5 , the segmented wires are prefabricated in channels to provide programmable connections between switch blocks, connection blocks, and logic blocks. The number of wires in one channel is usually denoted by W BIB001 . The I/O of the logic blocks are dynamically connected to the segmented routing channels on all four sides using connection blocks. The number of wires in each channel to which a logic block pin can connect to is called the connection block flexibility Fc. In addition, the switch blocks provide programmable connectivity between the horizontal and vertical wires. The switch block flexibility Fs is defined as the number of wires to which each incoming wire can connect to in a switch block. The segment length of a certain wire segment is defined as the number of logic blocks spanned by the routing wire. Modern FPGAs use a combination of wires of different segment lengths to achieve the optimum performance in terms of routability, delay, or both. Dedicated routing is used for global signals that fan out to a large number of logic blocks, e.g., clock and reset, thus providing low-skew. Moreover, some commercial FPGAs employ PLLs and Delay-Locked Loops (DLLs) for further skew reduction. Modern FPGAs have the flexibility to provide different clock domains inside the FPGA to enable asynchronous designs. FPGAs are implemented using a huge number of programmable switches that are used to implement a certain logic function. The CAD tools of FPGAs transform the design, entered either as a schematic or using a hardware description language, to a stream of `1's and `0's that program the FPGA during the configuration time. The flow chart in Figure 6 shows the different steps involved in the CAD flow for a typical FPGA design. In the synthesis phase, the circuit description is converted to a netlist of basic logic gates. This phase is usually divided into two different stages; logic optimization and technology mapping BIB002 BIB003 BIB004 BIB005 . Logic optimization is a technology-independent stage that involves simplifying the logic function of the design without the use of any technology information. Any redundant logic is removed at this stage. The optimized user circuit is then mapped into LUTs and flip-flops in the technology mapping stage, where each k-bounded logic function in the circuit is mapped into a k-LUT. This step resolves to find a set of k-feasible cuts that include all the nodes in the circuit in such a way to minimize the delay, area, and/or power dissipation of the final implementation. The process of technology mapping is often treated as a covering problem.