In this paper we study the effect of post-layout pin permutation of designs for FPGA devices with non-uniform cell delays. We present a simple, but timing optimal, pin permutation scheme, and report the results of applying the scheme on a set of public logic synthesis benchmark designs that were synthesized and placed by state-of-the-art commercial FPGA design tools configured to maximum optimization level. Despite the preceding optimizations, we still observed an average timing improvement of 3.7%. This demonstrates the importance of fully utilizing non-uniform cell delays during design optimizations for modern FPGA devices and the still presenting potential of improvement.

This paper presents a new approach to timing optimization for FPGA designs, namely incremental physical resynthesis, to answer the challenge of effectively integrating logic and physical optimizations without incurring unmanageable runtime complexity. Unlike previous approaches to this problem which limit the types of operations and/or architectural features, we take advantage of many architectural characteristics of modern FPGA devices, and utilize many types of optimizations including cell repacking, signal rerouting, resource retargeting, and logic restructuring, accompanied by efficient incremental placement, to gradually transform a design via a series of localized logic and physical optimizations that verifiably improve overall compliance with timing constraints. This procedure works well on small and large designs, and can be administered through either an automatic optimizer, or an interactive user interface. Our preliminary experiments showed that this approach is very effective in fixing or reducing timing violations that cannot be reduced by other optimization techniques: For a set of test cases to which this is applicable, the worst timing violation is reduced by an average of 42.8%.

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.

No abstract available.

The increasing popularity of the field programmable gate-array (FPGA) technology has generated a great deal of interest in the algorithmic study and tool development for FPGA-specific design automation problems. The most widely used FPGAs are LUT based FPGAs, in which the basic logic element is a K -input one-output lookup-table (LUT) that can implement any Boolean function of up to K variables. This unique feature of the LUT has brought new challenges to logic synthesis and optimization, resulting in many new techniques reported in recent years. This article summarizes the research results on combinational logic synthesis for LUT based FPGAs under a coherent framework. These results were dispersed in various conference proceedings and journals and under various formulations and terminologies. We first present general problem formulations, various optimization objectives and measurements, then focus on a set of commonly used basic concepts and techniques, and finally summarize existing synthesis algorithms and systems. We classify and summarize the basic techniques into two categories, namely, logic optimization and technology mapping , and describe the existing algorithms and systems in terms of how they use the classified basic techniques. A comprehensive list of references is compiled in the attached bibliography.

We study the nominal delay minimization problem in LUT-based FPGA technology mapping, where interconnect delay is assumed proportional to net fannout size. We prove that the delay-optimal K-LUT mapping problem under the nominal delay model is NP-hard when K≥3, and remains NP-hard for duplication-free mapping and tree-based mapping for K≥5 (but is polynomial time solvable for K = 2). We also present a simple heuristic to take nominal delay into consideration during LUT mapping for delay minimization.

The field programmable gate-array (FPGA) has become an important technology in VLSI ASIC designs. In the past few years, a number of heuristic algorithms have been proposed for technology mapping in lookup-table (LUT) based FPGA designs, but none of them guarantees optimal solutions for general Boolean networks and little is known about how far their solutions are away from the optimal ones. This paper presents a theoretical breakthrough which shows that the LUT-based FPGA technology mapping problem for depth minimization can be solved optimally in polynomial time. A key step in our algorithm is to compute a minimum height K-feasible cut in a network, which is solved optimally in polynomial time based on network flow computation. Our algorithm also effectively minimizes the number of LUT's by maximizing the volume of each cut and by several post-processing operations. Based on these results, we have implemented an LUT-based FPGA mapping package called FlowMap. We have tested FlowMap on a large set of benchmark examples and compared it with other LUT-based FPGA mapping algorithms for delay optimization, including Chortle-d, MIS-pga-delay, and DAG-Map. FlowMap reduces the LUT network depth by up to 7% and reduces the number of LUT's by up to 50% compared to the three previous methods.>

In this paper, we study the area and depth trade-off in lookup-table (LUT) based FPGA technology mapping. Starting from a depth-optimal mapping solution, we perform a sequence of depth relaxation operations and area-minimizing mapping procedures to produce a set of mapping solutions for a given design with smooth area and depth trade-off. As the core of the area minimization step, we have developed a polynomial time optimal algorithm for computing an area-minimum mapping solution without node duplication for a K-bounded general Boolean network, which makes a significant step towards complete understanding of the general area minimization problem in FPGA technology mapping. The experimental results on MCNC benchmark circuits show that our solution sets outperform the solutions produced by most existing mapping algorithms in terms of both area and depth minimization.>

In this paper we study the area and depth traak-o~in L(JT based FPGA technology mapping.Starting from a depth-optimal mapping solution, we peform a number of depth relaxation operations to obtain a new network with bounded increase in depth and advantageous to subsequent re-mapping for area minimization.We thzm re-map the resulting network to obtain an area-minimized mapping solution.By gradually increasing the depth bound, for each design we are able to produce a set of mapping solutions with smooth area and depth trade-ofi For the area minimization step, we have developed an optimal algorithm for computing an area-minimum mapping solution without node duplication.Experitnental resrdts show that our solution sets outperform the solutions produced by many existing mapping algorithms in terms of both area and depth minimization.

We present an integrated approach to synthesis and mapping to go beyond the combinatorial limit set up by the depth-optimal FlowMap algorithm. The new algorithm, named FlowSYN, uses the global combinatorial optimization techniques to guide the Boolean synthesis process during depth minimization. The combinatorial optimization is achieved by computing a series of minimum cuts of fixed heights in a network based on fast network flow computation, and the Boolean optimization is achieved by efficient OBDD-based implementation of functional decomposition. The experimental results show that FlowSYN improves FlowMap in terms of both the depth and the number of LUTs in the mapping solutions. Moreover, FlowSYN also outperforms the existing FPGA synthesis algorithms for depth minimization.

Presents a polynomial time technology mapping algorithm, called Flow-Map, that optimally solves the lookup-table (LUT)-based field-programmable gate array (FPGA) technology mapping problem for depth minimization for general Boolean networks. This theoretical breakthrough makes a sharp contrast with the fact that the conventional technology mapping problem in library-based designs is NP-hard. A key step in Flow-Map is to compute a minimum height K-feasible cut in a network, solved by network flow computation. The algorithm also effectively minimizes the number of LUTs by maximizing the volume of each cut and by several postprocessing operations. The Flow-Map algorithm was tested on a a set of benchmarks and achieved reductions of both the network depth and the number of LUTs in mapping solutions as compared with previous algorithms.>

A graph-based technology mapping algorithm, called DAG-Map, for delay optimization in lookup-table-based field programmable gate array (FPGA) designs is presented. The algorithm carries out technology mapping and delay optimization on the entire Boolean network, instead of decomposing it into fanout-free trees and mapping each tree separately as in most previous algorithms. As a preprocessing step, a general algorithm that transforms an arbitrary n-input network into a two-input network with only O(1) factor increase in the network depth is introduced. Also presented is a graph-matching-based technique used as a postprocessing step which optimizes the area without increasing the delay. The DAG-Map algorithm was tested on the MCNC logic synthesis benchmarks. Compared with previous algorithms, it reduces both the network depth and the number of lookup-tables.>