Linear programming (LP) based methods are attractive for solving the placement problem because of their ability to model Half-Perimeter Wirelength (HPWL) and timing. However, it has been technically difficult to model overlaps in LP. This difficulty in modeling overlaps restricted the domain of LP-based methods to incremental placers, where LP is used to calculate the optimal locations of a small subset of cells with no regard to overlaps. In this paper, we enlarge the scope of LP-based methods from just operating on a small subset of cells to operating on all cells of a functional block circuit. We show how to model, reduce and prevent overlaps in LP-based placement flows. We use our ideas to construct (1) a global optimal whitespace allocator, and (2) a global overlap remover and cell spreader. We also modify our methods to fit in a timing-driven placement flow. Compared to our default industrial flow, our results show an improvement by an average of 7.64% in wirelength, and by an average of 21% in total negative slack. Furthermore, we conduct a benchmarking study, where we surprisingly show that academic placers fail to consistently produce good results on relatively small functional blocks.

This paper presents a novel placement algorithm for timing optimization based on a new and powerful concept, which we term differential timing analysis. Recognizing that accurate optimization requires timing information from a signoff static timing analyzer, we propose an incremental placement algorithm that uses timing information from a signoff static timing engine. We propose a set of differential timing analysis equations that accurately capture the effect of placement perturbations on changes in timing from the signoff timer. We have formulated an incremental placement optimization problem based on differential timing analysis as a single linear programming (LP) problem which is solved to generate the new timing-optimized placement.Our experiments show that the worst negative slack (WNS) improves by an average of 30% and the total negative slack (TNS) improves by 33% on average for a set of circuits from a 3.0 GHz microprocessor that were already synthesized and placed by a leading industrial physical synthesis tool. We also show that multiple iterations of our engine give further TNS improvements - an average improvement of 51%, which implies that our placer will significantly speed up timing convergence.

We present an exact solution to the technology mapping problem for field-programmable gate arrays (FPGAs), where the objective is to minimize the number of lookup tables (LUTs) required to map a logic circuit. The key idea is to compactly formulate the mapping problem as a mixed-integer linear-programming (MILP) problem, which can then be solved by any off-the-shelf MILP solver. MILP problem formulations are systematically developed for various classes of circuits with increasing complexities-trees, monotone circuits, and general nonmonotone circuits, where the monotonicity of a circuit implies that the number of signals increases monotonically as the circuit is traversed from primary outputs to primary inputs. Several circuit properties related to reconvergent paths and monotone signal sets are determined, which provide insight into the mapping problem for LUTs. Our experiments show that optimal mappings for circuits with several hundred gates can be obtained very quickly by solving their MILP formulations exactly. For larger circuits, we present two powerful heuristic approximation methods based on partitioning the circuit or simplifying its structure. We show that these approximations yield near-optimal solutions for several benchmark circuits.

This paper describes a new force directed global placement algorithm that exploits and extends techniques from two leading placers, Force-directed [12] [26] and Mongrel [22]. It combines the strengths of force directed global placement with Mongrel's cell congestion removal to significantly improve the quality of placement during the difficult overlap removal stage of global placement. This is accomplished by using the spreading force in [12] to direct and control Mongrel's ripple move optimization. This new placer is called Force Directed Mongrel (FD-Mongrel). FD-Mongrel also incorporates physical net constraints [26], and improves the congestion model for sparse placements. We propose a new placement flow that uses a limited number of the spreading iterations of [12] to form a preliminary global placement. We then use the new FD-Mongrel described in this paper to remove cell overlaps, while meeting net constraints and optimizing wirelength. We present results on wirelength as well as timing driven placement flows.

This paper presents a new timing driven force directed placement algorithm that meets physical net length constraints as well as constraints on specific pin sets. It is the first force directed placement algorithm that meets precise half perimeter bounding box constraints on critical nets. It builds on the work of Eisenmann et al. [12], adding a new net model that changes the contribution of constrained nets in the quadratic programming problem, during solving for each force generation step. We propose several methods for selecting and constraining critical nets to achieve improved timing. Our work suggests that the force directed method with net constraints is a powerful tool for placement and timing convergence, achieving an average worst negative slack optimization exploitation of 64% and average total negative slack optimization exploitation of 48% results on 16 industry circuits from a 1.5GHz microprocessor.

We present a general technology-mapping methodology (TULIP) for field-programmable gate arrays (FPGAs) that can yield optimal results, and is applicable to any FPGA with a logic block composed of lookup tables (LUTs). We introduce the concept of a virtual switch to model the internal connections of a logic block with multiple LUTs; each configuration of virtual switches is called a multiple-LUT block (MLB). A logic block can be precisely defined by a small but complete set of representative configurations called an MLB basis. The MLB bases for various commercial FPGA families are demonstrated. Given a logic block represented by its MLB basis, technology mapping is precisely formulated as a graph-covering problem, which is transformed into a mixed integer-linear programming (MILP) optimization problem in order to achieve our optimality and generality objectives. The MILP model is solved using a general-purpose MILP solver tool. The results of using TULIP for mapping some ISCAS-85 benchmark circuits to a variety of logic blocks are presented. Circuits of a few hundred gates can be mapped directly in a few minutes. To map larger circuits to complex logic blocks, some approximation techniques are proposed based on partitioning the input circuit and simplifying the MLB basis. We show that these approximations result in close-to-optimal mappings of the benchmark circuits.

Datapath circuits exhibit a very high degree of regularity, which is exploited by designers to generate layouts with a high density and performance as well as to reduce the overall design effort. Regularity in a datapath circuit manifests itself at functional, structural, and topological levels. Functional regularity of a circuit implies the existence of logically equivalent subcircuits-a common feature of datapath circuits. We present a new and comprehensive approach to extract functional regularity for datapath circuits from their high-level or gate-level descriptions. The key step is the generation of a large set of templates, where a template is a subcircuit with multiple instances in the circuit. Two novel template generation algorithms are presented-one for templates with a tree structure, and the other for a special class of multioutput templates, called single-principal-output-graph (SPOG) templates, where all outputs of a template are in the transitive fanin of a particular output. The set of templates generated is shown to be complete under a few simplifying, yet practical, assumptions, which is key in obtaining a desirable cover of the circuit using templates. We present a few extensions to our regularity extraction approach to demonstrate its generality; these extensions include hierarchical representation of regularity and generation of instances of user-specified templates. We show that the generation of the above two classes of templates results in good covers for datapath circuits with a regular bus structure, including several International Conference on Computer-Aided Design benchmark circuits. The regularity extracted from these circuits can be used to easily understand their structure. We have successfully used our approach to identify bit slices of very large datapath circuits from general-purpose microprocessors.

Inmajority ojhigh-performance custom ICdesigns, designers tuke advantage of the high degTee of Regularitypresent in circuits to generate eficient layouts in terms area and perfomance aswellas to Teducethe design effort.Inthis paper, we present a general and comprehensive approach to extTact functional regularity for datapath ciTcuits from their behavioralor structural HDL descn.ptions.The fundamental step is the generation ofa large set of templates, where a template as a subcircuit with multiple instances in the ciTcuit.Two novel template generation algorithms aTe presented -one fortemplates with a tree structure, andtheother foraspecial class of multi-output templates, called single-p n.ncipaloutput (single-PO) templates, wheTe all outputs of a template are in thetransitive faninof a particular output.The set of template$ generated is complete under a few simplifying, yet practical, assumptions.This is key to obtaining a desirable couerof theciTcuit using templates.Weshow that excellent cover$ are obtained for van"ous circuits, including ISCAS benchmarks.We also demonstrate that the regularitg extracted for these circuits can be used to understand their under[ging structure.We have successfully used our approach to identify bit slices of very large datapath circuits from general-purpose microprocessors.

We present a general approach to the FPGA technology mapping problem that applies to any logic block composed of lookup tables (LUTs) and can yield optimal solutions. The connections between LUTs of a logic block are modeled by virtual switches, which define a set of multiple-LUT blocks (MLBs) called an MLB-basis. We identify the MLB-bases for various commercial logic blocks. Given a n MLB-basis, we formulate FPGA mapping as a mixed integer linear programming (MILP) problem to achieve both the generality and the optimality objectives. We solve the MILP models using a general-purpose MILP solver, and present the results of mapping some ISCAS.85 benchmark circuits with a variety of commercial FPGAs. Circuits of a few hundred gates can be mapped in reasonable time using the MILP approach directly. Larger circuits can be handled by partitioning them prior to technology mapping. We show that optimal or provably near-optimal solutions can be obtained for the large ISCAS.85 benchmark circuits using partitions defined by their high-level functions.

We show that the FPGA technology mapping problem can be efficiently implemented as a mixed integer linear programming (MILP) problem which generates truly optimal mappings. The MILP approach can handle a wide variety of FPGA logic block architectures. We present a compact MILP formulation for logic blocks based on lookup tables (LUTs) or multiplexes. We also show that the MILP formulation can be easily modified to optimize area delay, or a combination of both. We demonstrate that moderately large benchmark circuits can be mapped in a reasonable time using the MILP approach directly. For larger circuits, we propose a technique of partitioning a circuit prior to mapping, which drastically reduces the computation time with little or no loss in optimality.

We have developed a mathematical model for estimating the probability of routing on an electrically programmable logic cell array (LGA). Using the model the variation of the routability or the probability of routing with the average span of the nets, and flexibility of programming resources is determined. The results obtained from the model have been verified experimentally. As expected, the routability also increases when the number of programming elements is increased. We also show a three dimensional relationship between routability, placement, and programming flexibility. Our results show a strong relationship between module placement and the routability for an LCA.>