When dealing with partially reconfigurable designs on field-programmable gate array, floorplanning represents a critical step that highly impacts system's performance and reconfiguration overhead. However, current vendor design tools still require the floorplan to be manually defined by the designer. Within this paper, we provide a novel floorplanning automation framework, integrated in the Xilinx tool chain, which is based on an explicit enumeration of the possible placements of each region. Moreover, we propose a genetic algorithm (GA), enhanced with a local search strategy, to automate the floorplanning activity on the defined direct problem representation. The proposed approach has been experimentally evaluated with a synthetic benchmark suite and real case studies. We compared the designed solution against both the state-of-the-art algorithms and alternative engines based on the same direct problem representation. Experimental results demonstrated the effectiveness of the proposed direct problem representation and the superiority of the defined GA engine with respect to the other approaches in terms of exploration time and identified solution.

The aim of this paper is to show a novel floorplanner based on Mixed-Integer Linear Programming (MILP), providing a suitable formulation that makes the problem tractable using state-of-the-art solvers. The proposed method takes into account an accurate description of heterogeneous resources and partially reconfigurable constraints of recent FPGAs. A global optimum can be found for small instances in a small amount of time. For large instances, with a time limited search, a 20% average improvement can be achieved over floorplanners based on simulated annealing. Our approach allows the designer to customize the objective function to be minimized, so that different weights can be assigned to a linear combination of metrics such as total wire length, aspect ratio and area occupancy.

It is well known that optimizations made by traditional logic synthesis tools often correlate poorly with post-layout performance; this is largely a result of interconnect effects only visible after layout. As a result, several attempts at physically aware logic synthesis have been made (e.g.,[2], [9], [14], [4], [7], [12], [16], [15]). In this paper a corrective methodology is proposed for timing-driven logic restructuring at the placement level; the approach currently focuses on LUT-based FPGAs.

It is well known that optimizations made by traditional logic synthesis tools often correlate poorly with post-layout performance; this is largely a result of interconnect effects only being visible after layout. In this paper, acorrectivemethodology is proposed for timing-driven logic restructuring at the placement level. The approach focuses on a lookup table (LUT)-based field programmable gate arrays. The approach is iterative in nature. In each iteration, using current placement information, the method induces a timing-critical fan-in tree via (temporary) replication. Such trees are then reimplemented where the degrees of freedom include functional decomposition of LUTs, ldquomini-LUTrdquo tree mapping, and physical embedding. A dynamic programming algorithm optimizes over all of these freedoms simultaneously.Allsimple disjoint LUT decompositions (i.e., Ashenhurst style) are encoded in a ldquomini-LUTrdquo tree using choice nodes similar to those in the paper by Lehman At the same time, because embedding is done simultaneously, interconnect delay is directly taken into account. Over multiple iterations, the design is progressively improved. The framework has been implemented, and promising experimental results are reported.

Parallel prefix adder is the most flexible and widely-used binary adder for ASIC designs. Many high-level synthesis techniques have been developed to find optimal prefix structures for specific applications. However, the gap between these techniques and back-end designs is increasingly large. In this paper, we propose an integer linear programming method to build minimal-power prefix adders within given timing and area constraints. It counts both gate and wire capacitances in the timing and power models, considers static and dynamic power consumptions, and can handle gate sizing and buffer insertion to improve the performance further. The proposed method is also adaptive for non-uniform arrival time and required time on each bit position. Therefore our method produces the optimum prefix adder for realistic constraints.

The traditional repeater insertion in an integrated circuit (IC) is aimed at eliminating cycle (setup) time violations at the worst process corner. Subsequently, special measures are adopted to remedy hold-time violations identified at the best process corner. However, aggressive delay reduction for fixing setup time violations could introduce new hold-time violations that did not exist before. Designers are usually un-ware of these newly created hold-time violations as they do not compare hold-time violations pre and post repeater insertion. However, identifying these nets and rerunning them with the presented technique to deal with hold time requirements can reduce the number of repeaters and design turn-around time. The power vs. delay trade-off technique presented is found to be extremely useful in limiting the number of repeaters to an acceptable limit. Concurrent treatment of setup time and hold time helps in better timing convergence for the affected nets by avoiding creation of new violations. Satisfying a minimum and a maximum slews along with accurate RC and gate timing models helps attain good timing correlation/convergence with a static timer.

The main goal of this paper is to develop deeper insights into viable placement-level optimization of routing. Two primary contributions are made. First, an experimental framework in which the viability of "predictive" or "probabilistic" models of routing congestion for optimization during detailed placement can be evaluated is developed. The main criterion of consideration in these experiments is how (un)reliably various models from the literature detect routing hot spots. It was concluded that such models appear to be too unreliable for detailed placement optimization. Second, motivated by the first result, a single combinatorial framework in which cell placement and "exact" routing structures are captured and optimized is presented; the framework relies on the "trunk decomposition" of global routing structures, and optimization is performed by generalization of the "optimal interleaving" algorithm. An implementation of this framework is studied in the field-programmable gate array domain. The technique can reduce the number of channels at maximum density by more than 60% on average with maximum reduction of more than 81% for optimized global routing taking only 75% of the Versatile Place and Route (VPR) placement and routing runtime combined. For the standard cell domain, routing-based interleaving, on average, reduces the maximum track count by more than two tracks with a maximum reduction of nine tracks

Several recent papers have utilized logic replication driven by placement-level timing analysis for improving clock period (e.g., [1], [8], [18], and [2]). All of these papers demonstrated, through various optimization strategies, the potential of the basic technique of replication. In this paper we propose a number of techniques aimed at more fully realizing this potential within the framework employed in [8]. As reported in [7], there are situations in which the approach of [8] fails to yield significant additional improvement due largely to the effects of reconvergence in the netlist. We suggest the use of rectilinear Steiner arborescence embedding as a tool for overcoming this limitation. We also propose techniques for fanout partitioning and cell relocation which are cognizant of both wirelength and timing impact for improved solution quality. We report the effect of other techniques including new replication cost computation, lower-bounding of achievable clock period, and wirelength estimation. We have implemented and experimented with these techniques in FPGA domain. In many cases we were able to approach a fixed flip-flop lower-bound on achievable clock period. Promising experimental results are reported with average 17.4% (up to 39.9%) delay reduction compared with the timing-driven placement from VPR[16] and average 9.3% (up to 37.2%) reduction compared with the basic fanin tree embedder from [8].

We present global routing optimization methods which are not based on rip-up and re-route framework. In particular, the routing optimization is based on trunk decomposition [13] of the global routing. In this framework, the route of a net is decomposed into sets of wiring segments. By viewing a wiring segment as an "atomic object" of perturbation, we can efficiently evaluate the effect of routing tree perturbation. We propose two complementary routing optimization methods, namely segment partitioning and segment migration. These targeted optimizers can improve congestion related routing objectives by quickly shuffling wiring segments across different routing channels. Our routing approach produces better results compared to rip-up and re-route method based router Labyrinth [14] with average total overflow reduction of more than 88% while taking only 61% of runtime required by ripup and reroute phase of Labyrinth. When applied to the output of Labyrinth, the approach, on average, reduces the total overflow by more than 97% with complete overflow elimination for four circuits, while requiring additional runtime of just 33%. On a larger benchmark suite, the total overflow reduction of more than 86% is obtained, with complete overflow elimination for eight circuits, while requiring only 19% additional runtime.

This paper presents a set of techniques for placement-coupled timing-driven logic replication. Two components are at the core of the approach. First, is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second, the replication tree is introduced, which allows to induce large fanin trees from a given circuit, which can then be optimized by the embedder. The authors have built an optimization engine around these two ideas and report promising results for the field-programmable gate array (FPGA) domain including clock period reductions of up to 36% compared with a timing-driven placement from versatile place and route (VPR) (Marquardt , 2000) and almost double the average improvement of local replication (Beraudo and Lillis, 2003). These results are achieved with modest area and runtime overhead. In addition, issues that arise due to reconvergence in the circuit specification are addressed. The authors build on the replication tree idea and enhance the timing-driven fanin tree embedding algorithm to optimize subcritical paths, yielding even better delay improvements.

A method for timing driven placement is presented. The core of the approach is optimal timing-driven relaxed placement based on a linear programming (LP) formulation. The formulation captures all topological paths in a linear sized LP and thus, heuristic net weights or net budgets are not necessary. Additionally, explicit enumeration of a large number of paths is avoided. The flow begins with a given placement and iteratively extracts timing-critical sub-circuits, optimally places the sub-circuit by LP and applies a timing-driven legalizer. The approach is applied to the FPGA domain and yields an average of 19.6% reduction in clock period of routed MCNC designs versus [6] (with reductions up to 39.5%).

Placement strategies for cell-based designs which use a linear programming (LP) relaxation are widely believed to have certain weaknesses. Among these is the phenomenon that the relaxed placement produced by the LP-solver often has excessive cell overlap; this makes the relaxed solution quite distant from a legal one and raises questions about the value of the relaxed solution. An implication of this phenomenon is that, while the objective function value (HPWL) yielded by the LP is a valid lower bound on the achievable wire-length, it is quite distant from known upper bounds produced by quality placement tools - i.e., the lower bounds appear to be loose. In this paper we experiment with some straightforward generalizations of the basic LP-formulation aimed at tightening the lower bound. We show that this approach has an interesting dual effect: in addition to tightening lower bounds, it also results in a quantifiably better cell distribution than the simpler LP-formulation. Based on this idea, we have developed a placer which employs the Relaxation Based Local Search framework. Experimental results are reported for PEKO and MCNC FPGA benchmarks.

We present a set of techniques for placement-coupled, timing-driven logic replication. Two components are at the core of the approach. First is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second we introduce the Replication Tree which allows us to induce large fanin trees from a given circuit which can then be optimized by the embedder. We have built an optimization engine around these two ideas and report promising results for the FPGA domain including clock period reductions of up to 36% compared with a timing-driven placement from VPR [12] and almost double the average improvement of local replication from [1]. These results are achieved with modest area and runtime overhead.

The main goal of This work is to develop deeper insights into viable placement-level optimization of routing. Two primary contributions are made. First, an experimental framework in which the viability of predictive models of routing congestion for optimization during detailed placement can be evaluated, is developed. The main criteria of consideration in these experiments is how (un)reliably various models from the literature detect routing hot-spots. We conclude that such models appear to be too unreliable for detailed placement optimization. Second, motivated by the first result, we present a unified combinatorial framework in which cell placement and exact routing structures are captured and optimized; the framework relies on the trunk-decomposition of global routing structures and optimization is performed by a generalized optimal interleaving algorithm (Hur and Lillis, 2000). A proof of concept implementation of this framework is studied in the FPGA domain. The technique can reduce the number of channels at maximum density by almost 45% on average with maximum reduction of 68% for optimized global routing.

Logic replication for placement level timing optimization is studied in the context of FPGAs. We make the observation that critical paths are dominated by interconnect delay and are frequently highly circuitous. We propose a systematic replication technique to “straighten ” such paths. The resulting algorithm has several components: cell selection, slot selection for a duplicate cell, fanout partitioning and placement legalization. This algorithm is described and promising preliminary experimental results are reported with up to 29 % improvement in critical path delay.

We give an overview of a buffer tree synthesis package which pays particular attention to the following issues: routing and buffer blockages, minimization of interconnect and buffer costs, congestion, exploitation of temporal locality among the sinks, and addressing sink polarity requirements. Experimental results demonstrate the effectiveness of the tool in comparison with previously proposed techniques.

We present the S-Tree algorithm for synthesis of buffered interconnects. The approach incorporates a unique combination of real-world issues (handling of routing and buffer blockages, cost minimization, critical sink isolation, sink polarities), robustness and scalability. The algorithm is able to achieve the slack comparable to that of buffered P-Tree [7] using less resources (wire and buffers) in an order of magnitude less cpu time.

We give an overview of a buffer tree synthesis package which pays particular attention to the following issues: routing and buffer blockages, minimization of interconnect and buffer costs, exploitation of temporal locality among the sinks and addressing sink polarity requirements. Experimental results demonstrate the effectiveness of the tool in comparison with previously proposed techniques.

We study the problem of performing buffer insertion in the context of a given layout. In a practical situation, there are restrictions on where buffers may be inserted; for instance, it may be possible to route wires over a preplaced macro cell, but may not be possible to insert buffers in that region. As a result, it is desirable to perform route planning and buffer insertion simultaneously. Furthermore it is necessary that such an algorithm be aware of the trade-off between cost (e.g., total capacitance) and delay. In this context we propose the delay reduction to cost ratio (DRCR) problem and present a fast algorithm for the same. Solutions identified by the algorithm are characterized with respect to the overall cost versus performance trade-off curve. Computational experiments demonstrate the viability of the approach.

Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world “difficult” instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

We study the problem of performing buffer insertion in the context of a given layout in a practical situation, there are restrictions on where buffers may be inserted while routing over such regions may be possible (e.g., due to the presence of macro cells). As a result, it is desirable to perform route planning and biffer insertion simultaneously. Further it is necessary that such an algorithm be aware of the tradeoff between cost (e.g. total capacitance) and delay. In this context we propose the Delay Reduction to Cost Ratio (DRCR) problem and present a fast algorithm for the same. Solutions identified by the algorithm are characterized with respect to the overall cost vs. performance tradeoff curve. Computational experiments demonstrate the viability of the approach.

We give an overview of a standard-cell placer Mongrel. The prototype tool adopts a middle-down methodology in which a grid is imposed over the layout area and cells are assigned to bins forming a global placement. The optimization technique applied in this phase is based on the Relaxation-Based Local Search (RBLS) framework in which a combinatorial search mechanism is driven by an analytical engine. This enables a more global view of the problem and results in complex modifications of the placement in a single search "move". Details of this approach including a novel placement legalization procedure are presented. When a global placement has converged, a detailed placement is formed and further optimized by the proposed optimal interleaving technique. Experimental results are presented and are quite promising, demonstrating that there is significant room for improvement in state of the art placement.

This paper studies a natural formulation of the timing-driven maze routing problem. A multigraph model appropriate for global routing applications is adopted; the model naturally captures blockages, limited routing and wire-sizing resources, layer assignment, etc. Each edge in the multigraph is annotated with resistance and capacitance values associated with the particular wiring segment. The timing-driven maze routing problem is then to find paths which exhibit low resistance-capacitance (RC) delay or achieve a tradeoff between RC delay and total capacitance. An easy-to-implement labeling algorithm is presented to solve the problem along with effective speedup enhancements to the basic algorithm which yield up to 300 times speedup. It is suggested that such an algorithm will become a fundamental tool in an arsenal of interconnect optimization techniques. The tractability of the approach is supported via computational experiments.

This paper presents two primary results relevant to physical design problems in CAD/VLSI through a case study of the linear placement problem.First a local search mechanism which incorporates a neighborhood operator based on constraint relaxation is proposed.The strategy exhibits many of the desirable features of analytical placement while retaining the flexibility and non-determinism of local search.The second and orthogonal contribution is in netlist clustering.We characterize local optima in the linear placement problem through a simple visualization toolthe displacement graph.This characterization reveals the relationship between clusters and local optima and motivates a dynamic clustering scheme designed specifically for escaping such local optima.Promising experimental results are reported.

This paper studies a natural formulation of the timing-driven maze routing problem. A multigraph model appropriate for global routing applications is adopted; the model naturally captures blockages, limited routing and wire-sizing resources, layer assignment, etc. Each edge in the multigraph is annotated with resistance and capacitance values associated with the particular wiring segment. The timing-driven maze routing problem is then to find paths which exhibit low resistance-capacitance (RC) delay or achieve a tradeoff between RC delay and total capacitance. An easy-to-implement labeling algorithm is presented to solve the problem along with effective speedup enhancements to the basic algorithm which yield up to 300 times speedup. It is suggested that such an algorithm will become a fundamental tool in an arsenal of interconnect optimization techniques. The tractability of the approach is supported via computational experiments.

This paper presents new results in the area of timing optimization for multisource nets. The augmented RC-diameter (ARD) is suggested as a natural and practical performance measure and a linear time algorithm for computing the ARD of a multisource net is presented. Building on the ARD measure, we characterize the multisource optimization problem in terms of operations on piece-wise linear functions. This characterization is then used to develop an algorithm for optimal repeater insertion: for a given multisource topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the "min cost timing feasible" problem formulation. The algorithm has been implemented and computational results demonstrate the viability of the approach.

The inaccuracy of Elmore delay #3# for interconnect delay estimation is well-documented. However it remains a popular delay measure to drive performance optimization procedures such as wire-sizing and topology construction. This paper studies the merits of incorporating #better-than-Elmore" delay measures into the optimization process. The proposed delay metrics use a table-lookup methodtoincorporate better load modeling and approximate the e#ect of signal slew. We demonstrate that the proposed metrics exhibit a much narrower error distribution than Elmore delay, eliminating Elmore's frequent gross delay over-estimation. Finally we show the improvement in solution quality which can be had by incorporating the new metrics into a timing driven topology construction algorithm. 1 Introduction The advent of deep submicron #DSM# technology has produced a great deal of interest in CAD algorithms for interconnect delay optimization. Past work includes algorithms for bu#er ins...

In this paper we present a new layout-driven timing model based on asymptotic waveform evaluation (AWE) for improved timing analysis during routing. Our model enables the bottom-up computation of interconnect tree moments, and can be easily integrated with such a global router. Such an integration achieves incremental layout optimization, i.e., timing analysis and routing are tightly coupled, with feedback between them. This achieved incremental layout optimization, through our innovative timing model, is the main contribution of this work.

This paper presents new results in the area of timingoptimization for multi-source nets. The Augmented RC-Diameter (ARD) is proposed as a natural and practical performance metric and a linear time algorithm for computingthe ARD of a multi-source net is presented. Building onthe ARD, an algorithm for optimal repeater insertion is presented: for a given multi-source topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the min cost timing feasibleproblem formulation. The algorithm has been implementedand preliminary experimental results are promising.

This paper addresses the linear placement problem by using a spectral approach.It has been demonstrated that, by giving a more a c curate representation of the linear placement problem, a linear objective function yields better placement quality in terms of wire length than a quadratic objective function as in the eigenvector approach [4][11][6].On the other hand, the quadratic objective function has an advantage in that it tends to place c omponents more s p arsely than the linear objective function, resulting in a continuous solution closer to a physically feasible discrete solution.In this paper, we propose an -order objective function to capture the strengths of both the linear and quadratic objective functions.We demonstrate that our approach yields improved s p e ctral placements.We also present a bottom-up clustering algorithm which iteratively collapses pairs of nodes in a graph using local and global connectivity information, where the global connectivity information is derived f r om the clustering property of the eigenvector approach.The eect of our new spectral linear placement and clustering approach is demonstrated o n b enchmark circuits from MCNC.

We present new algorithms for construction of performance driven Rectilinear Steiner Trees under the Elmore delay model.Our algorithms represent a departure f r om previous approaches in that we derive an explicit area/delay tradeo curve.We achieve this goal by limiting the solution space to the set of topologies induced b y a p ermutation on the sinks of the net.This constraint allows ecient identi cation of optimal solutions while still providing a rich solution space.We also incorporate simultaneous wire sizing.Our technique consistently p r o duces topologies equalling the performance o f previous approaches with substantially less area overhead.

We present an algorithm for simultaneously finding a rectilinear Steiner tree T and buffer insertion points into T. The objective of the algorithm is to minimize a cost function (e.g., total area or power) subject to given timing constraints on the sinks of the net. An interesting side-effect of our approach is that we are able to derive an entire cost/delay tradeoff curve for added flexibility. The solutions produced by the algorithm are optimal subject to the constraint that the routing topology be induced by a permutation on the sinks of the net. We show that high quality sink permutations can be derived from a given routing structure such as the minimum spanning tree. This derivation provides an error bound on the minimum area solution induced by the permutation. The effectiveness of our algorithm is demonstrated experimentally.

We propose a unified solution to both linear placement and partitioning. Our approach combines the well-known eigenvector optimization method with the recursive max-flow min-cut method. A linearized eigenvector method is proposed to improve the linear placement. A hypergraph maxflow algorithm is then adopted to efficiently find the max-flow min-cut. In our unified approach, the max-flow min-cut provides an optimal ordered partition subject to the given seeds and the eigenvector placement provides heuristic information for seed selection. Experimental results on MCNC benchmarks show that our approach is superior to other methods for both linear placement and partitioning problems. On average, our approach yields an improvement of 45.1% over eigenvector approach in terms of total wire length, and yields an improvement of 26.9% over PARABOLI[6] in terms of cut size.

We present efficient, optimal algorithms for timing optimization by discrete wire sizing and buffer insertion. Our algorithms are able to minimize dynamic power dissipation subject to given timing constraints. In addition, we compute the complete power-delay tradeoff curve for added flexibility. We extend our algorithm to take into account the effect of signal slew on buffer delay which can contribute substantially to overall delay. The effectiveness of these methods is demonstrated experimentally.