Search

This article proposes a novel approach to handle macro placement. Previous works usually apply the simulated annealing (SA) algorithm to handle this problem. However, the SA-based approaches usually have difficulty in handling preplaced macros and require longer runtime. To resolve these problems, we propose a macro placement procedure based on the corner stitching data structure and then apply an efficient and effective simulated evolution algorithm to further refine placement results. In order to relieve local routing congestion, we propose to expand areas of movable macros according to the design hierarchy before applying the macro placement algorithm. Finally, we extend our macro placement methodology to consider dataflow constraint so that dataflow-related macros can be placed at close locations. The experimental results show that our approach obtains a better solution than a previous macro placement algorithm and a tool. Besides, placement quality can be further improved when the dataflow constraint is considered.

This paper proposes a novel approach to handle the macro placement problem, which integrates the simulated evolution algorithm and corner stitching data structure. Unlike the simulated annealing based algorithm which has to pack each macro to a contour in its representation, a macro can be placed at any empty region according to the corner stitching. Hence, even when a chip contains several preplaced macros which do not abut to boundaries, it can be easily handled by our approach. Moreover, we further apply an efficient and effective simulated evolution algorithm to refine a placement. To avoid standard cells being placed at a small region or being pushed away from related macros in the cell placement stage, our macro placement method also preserves placement areas for standard cells by expanding macros according to the design hierarchy. The experimental results show that our approach obtains better results than CP-tree and a commercial tool in term of wirelength and routability. More importantly, our methodology can complete a large test case in 6 minutes that CP-tree fails to get a result in one day, and their runtime is 659 times longer than ours even when large test cases are ignored.

The paper introduces a routability-driven placement prototyping algorithm for hierarchical mixed-size circuits and pays special attention to regular placement of macros. The three-stage algorithm has become the most popular placement approach for commercial design flows, where placement prototyping plays a critical role in the algorithm because distribution of cells and macros is mainly determined by it. SOC circuits usually contain sets of macros which have identical shapes and are in similar hierarchies. If these macros can be placed regularity, powerplanning will become easier and better routability may be obtained. To consider placement regularity, the paper proposes a physical aware clustering algorithm which is possible to cluster two objects with large area. Experimental results have demonstrated effectiveness of our methodology according to industrial benchmarks tested by a real design low.

Fixed outline floorplanning has recently attracted more attention due to its usefulness in solving real problems in industry. This paper applies two convex optimization methods, named UFO, to solve this problem, which consists of a global distribution stage followed by a local legalization phase. In the first stage, modules are transformed into circles, and a push-pull (PP) model is proposed to uniformly distribute modules over the fixed outline with consideration of their wirelength. Due to the quality of the PP model, we obtain good results after the first stage. Therefore, it is not necessary to consider wirelength in the legalization phase. In order to maintain good results of the first stage, we propose a procedure to extract the geometric relations of the modules from the results of the first stage and store it in constraint graphs. Then, the locations and shapes of the modules are determined by second-order cone programming, which penalizes overlap and obeys the boundary constraints. Finally, we extend the UFO methodology to consider pre-placed modules in a fixed outline. We have implemented two convex functions on MATLAB, and experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC and MCNC benchmarks.

Floorplanning/placement allocates a set of modules into a chip so that no two modules overlap and some specified objective is optimized. To facilitate floorplanning/placement, we need to develop an efficient and effective representation to model the geometric relationship among modules. In this paper, we present a P-admissible representation, called corner sequence (CS), for nonslicing floorplans. CS consists of two tuples that denote the packing sequence of modules and the corners to which the modules are placed. CS is very effective and simple for implementation. Also, it supports incremental update during packing. In particular, it induces a generic worst case linear-time packing scheme that can also be applied to other representations. Experimental results show that CS achieves very promising results for a set of commonly used MCNC benchmark circuits.

In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

The module placement problem is to determine the co-ordinates of logic modules in a chip such that no two modules overlap and some cost (e.g. silicon area, interconnection length, etc.) is optimised. To shorten connections between inputs and outputs and/or make related modules adjacent, it is desired to place some modules along the specific boundaries of a chip. To deal with such boundary constraints, we explore the feasibility conditions of a B*-tree with boundary constraints and develop a simulated annealing-based algorithm using B*-trees. Unlike most previous work, the proposed algorithm guarantees a feasible B*-tree with boundary constraints for each perturbation. Experimental results show that the algorithm can obtain a smaller silicon area than the most recent work based on sequence pairs.

Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multi-level matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.

To obtain good layout quality and reliability, placement is a very important stage during the physical design of analog circuits. Many works have been proposed to consider topological constraints for analog placement, and they devote to generate compact placements to minimize area and wirelength. However, a compact placement may induce unwanted routing issues. In order to reduce parasitics and cross-talk effects during the routing phase, wires are preferred not to pass above the active area of analog devices. Therefore, it is required to preserve enough routing spaces between devices for successful routing. Currently, there exists limited works studying routability for analog placement, but none of these works consider that symmetry property must be maintained during placement expansion. In this paper, we present a two-stage routability-driven analog placer based on ASF-B*-tree and HB*-tree representations. To reduce running time, our placement algorithm first generates a compact placement to minimize wirelength and area without considering congestion problem. Then, routing congestion regions are expanded locally to resolve the routability problem. Most importantly, the symmetry property of analog placement is always satisfied during the expansion process. Experimental results show that our analog placer can effectively minimize routing congestion without violating the symmetry property after placement expansion.

One of the most important issues during the analog layout phase is to achieve accurate capacitance ratios. However, systematic and random mismatches will affect the accuracy of the capacitance ratios. A common-centroid placement is helpful to reduce the systematic mismatch, but it still needs the property of high dispersion to reduce the random mismatch [10]. To deal with this problem, we propose a simulated annealing [15] based approach to construct a common-centroid placement which exhibits the highest possible degree of dispersion. To facilitate this framework, we first propose the pair-sequence representation to represent a common-centroid placement. Then, we present three operations to perturb the representation, which can increase the degree of dispersion without breaking the common-centroid constraint in the resulting placement. Finally, to enhance the efficiency of our simulated annealing based approach, we propose three techniques to speed up our program. The experimental results show that our placements can simultaneously achieve smaller oxide-gradient-induced mismatch and larger overall correlation coefficients (i.e., higher degree of dispersion) than [10] in all test cases. Besides, our program can run much faster than [10] in larger benchmarks.

In order to handle device matching for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis. In this paper, we deal with the module placement with symmetry constraints for analog design using the transitive closure graph-sequence (TCG-S) representation. Since the geometric relationships of modules are transparent to TCG-S and its induced operations, TCG-S has better flexibility than previous works in dealing with symmetry constraints. We first propose the necessary and sufficient conditions of TCG-S for symmetry modules. Then, we propose a polynomial-time packing algorithm for a TCG-S with symmetry constraints. Experimental results show that the TCG-S based algorithm results in the best area utilization.

Architecture and CAD are closely related issues in FPGA design. Routing architecture design shall optimize routability and facilitate router development; on the other hand, router design shall consider the specific properties of routing architectures to optimize the performance of the router. In this paper, we propose effective and efficient unified matching-based algorithms for array-based FPGA routing and segmentation design. For the segmentation design, we consider the similarity of input routing instances and formulate a net-matching problem to construct the optimal segmentation architecture. For the router design, we present a matching-based timing-driven routing algorithm which can consider a versatile set of routing segments. Experimental results show that our designed segmentations significantly outperform those used in commercially available FPGAs. For example, our designed segmentations achieve, on average, 14.6% and 19.7% improvements in routability, compared with those used in the Lucent Technologies ORCA 2C-series and the Xilinx XC4000E-series FPGAs, respectively.

We extend in this paper the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P*-admissible representations, SP, BSG, and TCG, has its strengths as well as weaknesses. We show the equivalence of the two most promising P*-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a new representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, faster packing and perturbation schemes are possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

Process technology advances will soon make the one-million gate FPGA a reality. A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. One-dimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient matching-based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms previous work.