Design routability is a major concern in the application-specific design flow, particularly with today's increasingly aggressive process technology nodes. Increased die areas, cell densities, routing layers, and net count all contribute to complex interconnect requirements, which can significantly deteriorate performance and sometimes lead to unroutable solutions. Congestion analysis and optimization must be performed early in the design cycle to improve routability. This paper presents a congestion estimation algorithm for a placed net list. We propose a net-based stochastic model for computing expected horizontal and vertical track usage, which considers routing blockages. The main advantages of this algorithm are its accuracy and fast runtime. We show that the congestion estimated by this algorithm correlates well with postroute congestion and present experimental results of subsequent congestion minimization based on this algorithm.

Abstract — We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA’s). This problem was first introduced in [21]. They used it to evaluate the routability properties of switch modules which they proposed. Only an approximation algorithm for the problem was proposed by them. We give an optimal algorithm for the problem based on integer linear programming (ILP). Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems. We then propose a precomputation that eliminates the need to use ILP on-line. We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known. Thus, the switch module routing problem can be solved in polynomial time for these special cases. Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router. A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions. Index Terms—Field-programmable gate array, global routing. I.

Technology mapping requires the unmapped logic network to be represented in terms of base functions, usually two-input NORs and inverters.Technology decomposition is the step that transforms arbitrary networks to this form.Typically, such decomposition schemes ignore the fact that certain circuit elements can be mapped more eciently by treating them separately during decomposition.Multiplexers are one such category of circuit elements.They appear very naturally in circuits, in the form of datapath elements and as a result of synthesis of CASE statements in HDL speci cations of control logic.Mapping them using multiplexers in technology libraries has many advantages.In this paper, we give an algorithm for optimally decomposing multiplexers, so as to minimize the delay of the network, and demonstrate its eectiveness in improving the quality of mapped circuits.

No abstract available.

The need for a two-way interaction between logic synthesis and FPGA logic module design has been stressed recently. Having a logic module that can implement many functions is a good idea only if one can also give a synthesis strategy that makes efficient use of this functionality. Traditionally, technology mapping algorithms have been developed after the logic architecture has been designed. We follow a dual approach, by focusing on a specific technology mapping algorithm, namely, the structural tree-based mapping algorithm, and designing a logic module that can be mapped efficiently by this algorithm. It is known that the tree-based mapping algorithm makes optimal use of a library of functions, each of which can be represented by a tree of AND, OR, and NOT gates (series-parallel or SP functions). We show how to design a SP function with a minimum number of inputs that can implement all possible SP functions with a specified number of inputs. For instances, we demonstrate a seven-input SP function that can implement all four-input SP functions. Mapping results show that, on an average, the number blocks of this function needed to map benchmark circuits are 12% less than those for Actel's ACT1 logic modules. Our logic modules show a 4% improvement over ACT1, if the block count is scaled to take into account the number of transistors needed to implement different logic modules.

FPGA technologies employ replicated programmable logic blocks. These can be look-up tables or more complex macro-cells. In this paper, we give a method to design macro-cell logic modules, based on an extension of classical work on designing Universal Logic Modules (ULM ). Specifically, we give a technique to design a class of logic modules that specialize to a large number of functions under complementations and permutations of inputs, bridging of inputs and assignment of 0/1 to inputs. Thus, a lot of functions can be implemented using a single logic module. The significance of our work lies in our ability to generate a large set of such logic modules. A choice can be made from this set based on design criteria. We demonstrate the technique by generating a set of 471 8-input functions that have a much higher coverage than the 8-input cells employed by Actel's FPGAs. Our functions can specialize to up to 23 times the number of functions that Actel functions can. We also show t...

We address the technology mapping problem for lookup table FPGAs. The area minimization problem for mapping K-bounded networks, consisting of nodes with at most K inputs using K-input lookup tables is known to be NP-complete for K/spl ges/5. The complexity was unknown for K=2, 3, and 4. The corresponding delay minimization problem (under the constant delay model) was solved in polynomial time by the flow-map algorithm, for arbitrary values of K. We study the class of K-bounded networks, where all nodes have exactly K inputs. We call such networks K-exact. We give a characterization of mapping solutions for such networks. This leads to a polynomial time algorithm for computing the simultaneous area and delay minimum mapping for such networks using K-input lookup tables. We also show that the flow-map algorithm minimizes the area of the mapped network as well, for K-exact networks. We then show that for K=2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be solved in polynomial time, resolving an open problem.

With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. We consider the gridded channel routing problem where, specifically, the channel has 3 routing layers in the VHV configuration. Given a horizontal track assignment for the nets, we present an optimal algorithm for minimizing the crosstalk between vertical wiring segments in the channel by finding an optimal vertical layer assignment for them. We show an algorithm that minimizes total crosstalk between between wires on the same V layer on adjacent columns of the grid in O(/spl nu/ log /spl nu/) time using O(/spl nu/) memory, where the channel has /spl nu/ columns. We then extend this algorithm to consider crosstalk between wires in non-adjacent columns and between wires on different layers.