A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two-dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of active programmable switches. An existing field-programmable interconnect chip (FPIC) routing structure can be included as a special case in our class of routing structures. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. We present a sequential routing algorithm based on the solution of the single net routing problem. We take into account the delay introduced by the active programmable switches on a routing path and formulate the single net routing problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm bas a performance bound of min{/spl Delta/(V/Z), |Z|-1}. Experimental results for several industrial circuits show a reduction of up to 41% in the number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.

We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm.

This paper studies the routing problem for a new Field-Programmable Gate Array (FPGA) and Field-Programmable Interconnect Chip (FPIC) routing architecture which improves upon the one proposed in [9] by providing continuing switches along the horizontal and vertical wire segments.The addition of continuing switches leads to higher routability and better timing performance than that for the routing architecture in [9].A two-phase routing algorithm for the new routing architecture is developed.Both the initial routing phase and the rip-up and reroute phase employ a dynamic programming technique.The rip-up and reroute phase can also be applied to the segmented channel routing problem for row-based FPGA routing structures.Experimental results show that routability is improved dramatically and the number of active programmable switches in connecting paths and the total number of programmable switches are reduced, when compared with the results in [9] and [3].The running time of the algorithm is less than 7 seconds for each o f v e industrial circuits.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of programmable switches. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. A sequential routing algorithm which is based on the solution of the single net routing problem is presented. We take into account the delay introduced by the programmable switches on a routing path and formulate the single net routing problem as a Node-Weighted Steiner Minimum Tree (NWSMT) problem in a bipartite graph G. Since our single net routing algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm has a performance bound of min{/spl Delta/(VZ), |Z|-1}. On the other hand, we also prove that it is NP-complete to determine a solution which approximates the optimal solution without any constant bound. Experimental results show a reduction of up to 41% in the number of programmable switches when compared with corresponding results for the conventional FPGA routing structure.

Given a floorplan with L-shaped regions, the problem considered is to choose an implementation from a set of possible implementations for each module such that the resultant floorplan will have minimum area, subject to the constraint that the dual polar graphs of the floorplan must be preserved. The concept of a cut line is extended, and eight types of cut lines that are used to decompose floorplans with L-shaped regions are defined. An O(n/sup 3/) time algorithm for deciding whether a given floorplan is decomposable is presented. A heuristic algorithm, which uses the cut tree obtained by the decomposition algorithm to solve the area minimization problem, is proposed. For floorplans that can not be decomposed by the decomposition algorithm, a branch-and-bound algorithm can be incorporated into the algorithm to solve the area minimization problem. The results obtained are superior to those obtained by running an existing mathematical programming package for at least 1 h, and the execution time is less than 3 min for the most complex test problem.>

The authors propose an algorithm for solving the channel routing problem that arises in QCL (quickly customized logic) technology. Routing in the upper and lower regions of the channel is handled by the algorithms UPPER and LOWER, respectively. All patterns are systematically examined one by one until a routing solution is found. Little computational time is used in determining the routability of each pattern. Consequently, the total running time is reasonable even when a large number of patterns are to be examined. Experimental results are given.>