Modern FPGA architectures support flexible polarity propagation in the fabric of logic blocks and interconnects. For example, the output of a lookup-table (LUT) logic block can be inverted by inverting all the bits in the LUT table. The rise and fall delays in either a LUT or a routing multiplexer usually differ substantially. The flexibility of polarity propagation and the difference between the rise and fall delays provide an opportunity to further optimize timing. This paper describes an algorithm to minimize the longest path delay by adjusting LUT output polarity after routing. The algorithm can be extended to reduce active leakage power in routing multiplexers while meeting timing constraints. The algorithm is efficient,easy to implement, and does not require change in placement and routing. Preliminary experiments show that the algorithm can reduce the longest path delay by up to 5.8% and on average 2.5% on a set of customer designs.

Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.

In this paper we present a timing-driven router for symmetrical array-based FPGAs. The routing resources in the FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, the traditional measure of routing delay on the basis of geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing rees, arising from the special properties of FPGA routing architectures. Based on the solutions to the routing-tree problem, we present a routing algorithm that is able to utilize various routing segments with global considerations to meet timing constraints. Experimental results show that our approach is very effective in reducing timing violations.

In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementations. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).

In this paper, we present a timing-driven global router for symmetrical-array-based FPGAs. The routing resources in the symmetrical-array-based FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, traditional measure of routing delay based on the geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing trees, arising from the special properties of FPGA routing architectures. We explore the complexity of the routing-tree problem and present efficient and effective approximation algorithms for the problem. Based on the solutions to the routing-tree problem, we present a global-routing algorithm which is able to utilize various routing segments with global consideration to meet the timing constraints. Experimental results on benchmark circuits show that our approach is promising.

In segmented channel routing of row-based FPGA's, the routability and interconnection delays depend on the choice of upper bounds on the number of programmable switches allocated for routing net segments in the channel. Traditionally, the upper bounds for the net segments in the same channel are set uniformly. In this paper, we present algorithms for determining the upper bounds for all of the net segments of a net simultaneously, so that the predefined source-to-sink delay bound on the net is satisfied and the routability of the net is maximized. The upper bounds on net segments in a channel determined by the algorithms in general are nonuniform. Experimental results show that the algorithms can significantly improve routability and reduce delay bound violation as compared with the traditional, uniform upper bound approach.

Unlike traditional ASIC technologies, the geometric structures of clock trees in a field-programmable gate array (FPGA) are usually fixed and cannot be changed for different circuit designs. Furthermore, the clock pins are connected to the clock trees via programmable switches. As a result, the load capacitances of a clock tree may be changed, depending on the utilization and distribution of logic modules in an FPGA. It is possible to minimize clock skew by carefully distributing the load capacitances or, equivalently, the logic modules used for the circuit design implementation. In this paper we present an algorithm for selecting logic modules used for circuit placement such that the clock skew is minimized. The algorithm can be applied to a variety of clock tree architectures, including those used in the major commercial FPGA's. The algorithm can also be extended to handle buffered clock trees and multiple clock trees Experimental results show that the algorithm can reduce clock skews significantly as compared with the traditional placement algorithms which do not consider clock skew minimization.

In segmented channel routing of row-based FPGAs, the routability and interconnection delays depend on the choice of the upper bounds on the number of programmable switches used in routing net segments in the channel.Traditionally, the upper bounds for the net segments in the same channel are set uniformly.In this paper, we present algorithms for determining the upper bounds for all net segments of a net simultaneously, so that the prede ned source-to-sink delay bound on the net is satis ed and the routability o f t h e net is maximized.The upper bounds on net segments in a channel thus in general are non-uniform.Preliminary experimental results show that the algorithms can signi cantly improve routability and reduce delay bound violation as compared with the traditional approach.

Unlike traditional ASIC technologies, the geometrical structures of clock trees in an FPGA are usually xed and cannot be changed for dierent circuit designs.Moreover, the clock pins are connected to the clock trees via programmable switches.As a result, the load capacitances of a clock tree may b e c hanged, depending on the utilization and distribution of logic modules in an FPGA.It is possible to minimize clock s k ew by distributing the load capacitances, or equivalently the logic modules used by the circuit design, carefully according to the circuit design.In this paper we present an algorithm for selecting logic modules used for circuit placement such that the clock s k ew is minimized.The algorithm can be applied to a variety of clock tree architectures, including those used in major commercial FPGAs.Furthermore, the algorithm can be extended to handle buered clock trees and multi-phase clock trees.Experimental results show that the algorithm can reduce clock s k ews signi cantly as compared with the traditional placement algorithms which do not consider clock s k ew minimization.

We address the problem of designing switch modules for FPGAs and FPICs to maximize routability under area and delay constraints. The switch module design problem is closely related to two-dimensional segmentation design for FPGAs and FPICs. We study the properties of switch modules and present an algorithm for switch module design. We also present an algorithm to analyze the routability of a given switch module.

The channel segmentation design problem for row-based field-programmable gate arrays (FPGAs) is to design a segmented channel to maximize the probability of successful routing. An algorithm which takes an arbitrary net distribution and an integer K (specifying the maximum number of segments allowed in routing a net) as inputs, and automatically generates a segmented channel which is most suitable for K-segment channel routing is presented. The algorithm was tested extensively over various net distributions. An algorithm for segmented channel routing based on reducing the problem to the maximum independent set problem for undirected graphs is also presented.>