Effectively estimating and managing congestion during placement can save substantial placement and routing runtime. In this article, we present a machine-learning model for accurately and efficiently estimating congestion during FPGA placement. Compared with the state-of-the-art machine-learning congestion-estimation model, our results show a 25% improvement in prediction accuracy. This makes our model competitive with congestion estimates produced using a global router. However, our model runs, on average, 291× faster than the global router. Overall, we are able to reduce placement runtimes by 17% and router runtimes by 19%. An additional machine-learning model is also presented that uses the output of the first congestion-estimation model to determine whether or not a placement is routable. This second model has an accuracy in the range of 93% to 98%, depending on the classification algorithm used to implement the learning model, and runtimes of a few milliseconds, thus making it suitable for inclusion in any placer with no worry of additional computational overhead.

Avoiding congestion for routing resources has become one of the most important placement objectives. In this paper, we present a machine-learning model for accurately and efficiently estimating congestion during FPGA placement. Compared with the state-of-the-art machine-learning congestion-estimation model, our results show a 25% improvement in prediction accuracy. This makes our model competitive with congestion estimates produced using a global router. However, our model runs, on average, 291x faster than the global router.

Optimizing for routability during FPGA placement is becoming increasingly important, as failure to spread and resolve congestion hotspots throughout the chip, especially in the case of large designs, may result in placements that either cannot be routed or that require the router to work excessively hard to obtain success. In this article, we introduce a new, analytic routability-aware placement algorithm for Xilinx UltraScale FPGA architectures. The proposed algorithm, called GPlace3.0, seeks to optimize both wirelength and routability. Our work contains several unique features including a novel window-based procedure for satisfying legality constraints in lieu of packing, an accurate congestion estimation method based on modifications to the pathfinder global router, and a novel detailed placement algorithm that optimizes both wirelength and external pin count. Experimental results show that compared to the top three winners at the recent ISPD’16 FPGA placement contest, GPlace3.0 is able to achieve (on average) a 7.53%, 15.15%, and 33.50% reduction in routed wirelength, respectively, while requiring less overall runtime. As well, an additional 360 benchmarks were provided directly from Xilinx Inc. These benchmarks were used to compare GPlace3.0 to the most recently improved versions of the first- and second-place contest winners. Subsequent experimental results show that GPlace3.0 is able to outperform the improved placers in a variety of areas including number of best solutions found, fewest number of benchmarks that cannot be routed, runtime required to perform placement, and runtime required to perform routing.

Traditional FPGA flows that wait until the routing stage to tackle congestion are quickly becoming less effective. This is due to the increasing size and complexity of FPGA architectures and the designs targeted for them. In this paper, we present two new congestion-aware placement tools for Xilinx UltraScale architectures, called GPlace-pack and GPlace-flat, respectively. The former placer participated in the ISPD 2016 Routability-driven Placement Contest for FPGAs, and finished in third place overall. The latter placer was subseqently developed based on our experience in the contest with GPlace-pack. Results obtained indicate that GPlace-flat is on average 5.3× faster than GPlace-pack. The post routing results show that GPlace-flat is able to obtain a further 22.5% improvement in wirelength and a 40.0% improvement in runtime compared to GPlace-pack.

A two-stage optimization methodology is proposed to solve the fixed-outline floorplanning problem that is a global optimization problem for wirelength minimization. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using second-order cone optimization. A Voronoi diagram is employed to obtain a planar graph and thus a relative position matrix to connect the two stages. Overlap-free and deadspace-free floorplans are achieved in a fixed outline and floorplans with any specified percentage of whitespace can be produced. Experimental results on GSRC benchmarks demonstrate that we obtain significant improvements on the best results known in the literature for these benchmarks. Most importantly, our methodology provides greater improvement over other floor-planners as the number of modules increases.

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988.

We present a new framework for efficiently finding competitive solutions for the facility-layout problem. This framework is based on the combination of two new mathematical-programming models. The first model is a relaxation of the layout problem and is intended to find good starting points for the iterative algorithm used to solve the second model. The second model is an exact formulation of the facility-layout problem as a nonconvex mathematical program with equilibrium constraints (MPEC). Aspect ratio constraints, which are frequently used in facility-layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are easily incorporated into this new framework. Finally, we present computational results showing that the complete framework can be solved efficiently using widely available optimization software, and the resulting layouts improve on those obtained using previous approaches in the literature. Moreover, the framework can be used to find different competitive layouts with relatively little computational effort, which is advantageous for a user who wishes to consider several competitive layouts rather than simply using a mathematically optimal layout.

Modern integrated circuit design involves the layout of circuits consisting of millions of switching elements or transistors. Due to the sheer complexity of the problem, optimizing the connectivity between transistors is very difficult. The circuit interconnection is the single most important factor in performance criteria such as signal delay, power dissipation, circuit size, and cost. These factors dictate that interconnections, i.e., wires, be made as short as possible. The wire-minimization problem is generally formulated as a sequence of discrete optimization subproblems that are known to be NP-hard. Hence, they can only be solved approximately using meta-heuristics. These methods are computationally expensive and the quality of the solution depends to a great extent on an appropriate choice of starting configuration and modeling techniques. In this paper, new modeling techniques are used to solve the routing problem formulated as an integer programming problem. The main contribution of this paper is a proposed global routing heuristic that combines the wire length, channel congestion, and number of pins in routes to find the best wiring layout of a circuit. By adding information such as channel congestion and the number of pins in each route as well as the wire length, the quality of the solution is improved. In addition, the solutions of the large relaxed linear programming problems are skewed towards a zero-one solution, resulting in faster convergence. The developed LP models in this paper are useful when solving the global routing problem for two reasons; first, the new interior-point algorithms to solve the LP problem are polynomial in time. Second, “near optimal wiring” is obtained in polynomial time without performing randomized rounding.

Many fields, ranging from bioinformatics to databases to large-scale integrated circuits, deal with the interrelation between elementary objects. Objects are represented as vertices and the relationships between them are represented as nets (edges that connect two or more vertices) in the form of a hypergraph. We seek a placement of vertices that groups like objects and separates unlike objects. This involves separating related objects into a few, possibly disjoint, blocks. These hypergraph-partitioning problems are NP-hard so cannot be solved exactly, except for very small instances. We develop and use a numerical technique based on eigenvector decomposition of the connectivity matrix associated with the circuit netlist to partition hypergraphs emanating from circuit netlists. The eigenvector components of the circuit connectivity matrix are then used to determine vertex coordinates in one dimension that are then rounded in some fashion to determine block assignments. The inherent difficulty with eigenvector techniques is that the eigenvector components tend to cluster, making it difficult to determine correct block assignments. Our technique uses weights on nets, vertices, and fixed vertices to obtain a more “discrete” placement of vertices, making it easier to determine correct block assignments.

Analytic placement methods that simultaneously minimize wire length and spread cells are receiving renewed attention from both academia and industry. We describe the implementation details of a force-directed placer, FDP. Specifically, we provide: (1) a description of efficient force computation for spreading cells; (2) an illustration of numerical instability in these methods and a means by which these instabilities are avoided; (3) spread metrics for measuring cell distribution throughout the placement region; and (4) a complementary technique which aids in directly minimizing HPWL. We present results comparing our analytic placer to other academic tools for both standard cell and mixed-size designs. Compared to Kraftwerk and Capo 8.7, our tool produces results with an average improvement of 9% and 3%, respectively.

Traditionally, analytic placement has used linear or quadratic wirelength objective functions. Minimizing either formulation attracts cells sharing common signals (nets) together. The result is a placement with a great deal of overlap among the cells. To reduce cell overlap, the methodology iterates between global optimization and repartitioning of the placement area. In this work, we added new attractive and repulsive forces to the traditional formulation so that overlap among cells is diminished without repartitioning the placement area. The superiority of our approach stems from the fact that our new formulations are convex and no hard constraints are required. A preliminary version of the new placement method is tested using a set of MCNC benchmarks and, on average, the new method achieved 3.96% and 7.6% reduction in wirelength and CPU time compared to TimberWolf v7.0 in the hierarchical mode.

In VLSI layout optimization, the placement problem is usually solved with simulated annealing or heuristic algorithms. These procedures often begin with random initial configurations but may benefit greatly (in terms of execution time or quality of solution) when good initial relative placements are provided. Weis and Mlynski [1987] have presented a linear programming formulation for generating relative placements. In this paper, we show how efficient interior point and preconditioned conjugate gradient methods can be applied to solve large sparse linear programs based on Weis and Mlynski's approach.>

A fast eigenvector technique for obtaining good initial node partitions of netlists for use in interchange heuristics is described. The method is based on approximating the netlist or hypergraph by a weighted graph G, such that the sum of the cut edges in G tightly underestimates the number of cut nets in any netlist partition. An eigenvector technique is used to partition the graph G into k blocks of fixed module size. Another feature of this graph underestimation model of the netlist is that it allows one to obtain lower bounds on the actual number of cut nets. A multiblock node interchange heuristic is tested on the one resulting netlist partition obtained by this eigenvector approach on a variety of small to large sized benchmark netlist partitioning problems (between 300 to 12000 modules and nets). Test results on the larger netlists show that in most cases this eigenvector-node interchange approach yields netlist partitions with comparable or fewer cut nets than the best netlist partitions obtained by using node interchange heuristics alone on many random initial netlist partitions.>

A linear-programming (LP) solution technique is applied to solve the global routing problem. Minimal spanning trees that were found in the subgrid by generating vertical and horizontal lines about the points of a given net and a modified interior point approach that reduces the number of arc constraints which were considered in the routing problem were used to reduce the problem site. An interior point algorithm approach is developed to solve the resulting LP problem. A FORTRAN code ROUTFAST is tested on several problems of varying arc capacities. ROUTFAST is compared with MINOS 5.0 which is a Simplex-based code on the same set of problems. ROUTFAST is at least 8-20 times faster than MINOS on the largest problems tested and seems to be getting faster as the problem size and arc capacity increases. Using a modification (ROUTLP) to solve four benchmark gate-array layout problems, ROUTFAST yielded competitive global routing results to TimberWolfSC Version 5.4 and in a fraction of TimberWolfSC's running time.>

It is an accepted practice in signal delay estimation to model MOS digital circuits as RC circuits. In most cases Elmore's definition is exactly equivalent to the group delay of the network at zero frequency. A computationally efficient noniterative method to calculate this delay for networks with any linear elements and arbitrary topology is presented. It is shown that in RC networks under certain conditions, the Elmore delay and the 50% unit step response delay are related by a constant which is largely independent of the element values and topology. An efficient method to obtain sensitivities of the delay with respect to any element in the network is presented.>

There is a class of graph partitioning algorithms which improve an initial partition by interchanging nodes between the subsets of the initial partition. These algorithms tend to require long running times because usually many trials must be made before the right combination of nodes to interchange is found. In this paper we describe a fast procedure for determining sets of nodes to interchange in order to improve an initial partition.