Timing and low power emerge as the most important goals in contemporary design. Meanwhile, the majority of placement algorithms developed by industry and academia still compete on the bases of the shorter combined interconnection length. In this paper, we present a standard cell placer that has timing and power minimization as main goals and is substantially superior in this respect to the popular commercial timing-driven placer. Simultaneously, the new placer is at least as good as the commercial placer w/r to the combined interconnection length. The improvement in timing and power is achieved by careful balancing between iterative and constructive parts of the placement procedure implemented by dynamic reevaluation of constraints for the constructive part of the algorithm. The new placer improves timing by 23% on the average, or for the same timing, reduces power by 14% on the average. It runs more than 2 times faster than the commercial tool.

In a process of IP selection, it is necessary to establish whether a candidate IP is equivalent to a behavioral model of a design proposed by a customer. It is desirable to perform this verification to exclude IPs, which "don't match" the rest of the design. This work combines a simulation approach to establishing equivalence between models with formal regular expression techniques to provide transaction-level preliminary evaluation of IP suitability. Such evaluation could precede a decision to acquire IP.

Criticality metrics is a type of predictive models used in VLSI design. This work demonstrates that timing in physical design could be substantially improved if circuits were subjected to timing criticality analysis prior to layout and new criticality metrics were used to drive layout system. These new metrics are computed as ratios of net physical characteristics to the net delay bounds determined by an optimal bounds computation algorithm. Attempts to develop criticality metrics prior to layout were made before, but these metrics were not based on the bound ideology. The paper provides probabilistic interpretation of new criticality metrics and derivation of some important properties of these metrics. Evaluation of net criticality by new metrics can be easily merged with any layout system that allows weights to be assigned to nets on placement and/or routing steps. The methodology has been tested with a commercial layout system from a leading CAD provider. When the new criticality information was supplied to a basic commercial standard cell placer and router, timing was improved by 29.5% for the set of testcases. The achieved result is 12% better than timing generated by a targeted timing-driven layout system from the same provider. All additional computations related to the new criticality metrics require only negligible increase in run time of the basic layout system.

Application of fuzzy logic structures in CAD of digital electronics substantially improves quality of design solutions by providing designers with flexibility in formulating goals and selecting tradeoffs. In addition, the following aspects of a design process are positively impacted by application of fuzzy logic: utilization of domain knowledge, interpretation of uncertainties in design data, and adaptation of design algorithms. We successfully applied fuzzy logic structures in conjunction with constructive and iterative algorithms for selecting of design solutions for different stages of the design process. We also introduced fuzzy logic software development tool to be used in CAD applications.

No abstract available.

No abstract available.

In this work, a technology-mapping procedure for FPGAs was developed, which takes into consideration multiple objectives while focusing on delay optimization. A constructive heuristic was used to minimize circuit delay and maximize the utility of CLBs. The target architecture of this mapper is Xilinx 4000 series, and a set of MCNC benchmarks was used to test the performance.

A contemporary definition of VLSI placement problem is characterized by multiple objectives. These objectives are: timing, chip area, interconnection length and possibly others. In this paper, fuzzy logic has been used to facilitate multiobjective decision-making in placement for standard cell design style. A placement process has been defined in terms of linguistic variables, linguistic values and membership functions. Various objectives have been related by hierarchical fuzzy logic rules implemented as object-oriented programming objects. It is demonstrated that a designed fuzzy logic system is flexible in selecting goals and considering tradeoffs. Details of implementation, experimental results and comparisons with other systems are provided.>

In this paper, a methodology for computation of PCB and MCM net length bounds consistent with timing and noise constraints has been introduced. The length of lines and their segments is derived first from equations based on semiempirical formulas and these values of length are used as initial values for AWE-based simulation. For the simulated length of line, the delay at receivers is presented by multivariable Taylor series with respect to length of segments for multi-pin nets. Partial derivatives for this representation are computed numerically on AWE simulation step. Resulting linear delay functions are used in linear programming formulation to find maximal lengths consistent with timing bounds. This work will help to reduce a number of iterations in PCB and MCM design and thus influence a length of design cycle and quality of solutions.

An application of constructive successive augmentation methodology to VLSI placement under constraints on routability, area and timing is described. To improve effectiveness of decision making, the placement algorithm uses adaptive and look-ahead procedures. This methodology was implemented in the placer-router JUNE for macrocell-library-based sea-of-gates design style with over-the-cell routing. JUNE achieves high utilization of area and timing requirements for real-life designs.>

Predictions of path criticalities are included into a constructive timing-driven placement procedure.These predictions are periodically performed through the placement process and are interlaced with placement steps.New emerging critical paths are treated preferentially improving convergence of the procedure.Consequently, timing of final placement is improved.Real 20K CMOS sea-of-gates designs illustrated the methodology.

An analytical method for general floorplan design and optimization is proposed. This method is based on a mixed integer programming model and application of a standard mathematical software. The method allows arbitrary combinations of rigid and flexible modules. Various objective functions such as chip area, interconnection length, timing delays or any combination of them are permitted. Routing space is estimated by the global router. Experimental data are provided.>

An adaptive timing-driven layout system, called JUNE, has been developed. The constructive algorithm, which combines placement with the global routing, constructs a placement satisfying timing and routability constraints. The placement problem for each macro is solved hierarchically as a sequence of two optimization problems followed by an adaptive correction procedure. Experimental results for industrial sea-of-gates chips confirmed effectiveness of this approach.

An analytical method for general floorplan design and optimization is proposed. This method is based on a mixed integer programming model and application of a standard mathematical software. The method allows arbitrary combinations of rigid and flexible modules. Various objective functions such as chip area, interconnection length, timing delays or any combinations of them are permitted. Routing space is estimated by the global router. Experimental data are provided.

Novel methodology and algorithms for the derivation of timing constraints on all the interconnects were developed and applied to solving layout related timing problems. This methodology is based on detailed information on timing characteristics of cells and nets. A minimax approach for identifying maximal delay bounds for nets which do not violate the timing constraints on any of the logical paths in the design was proposed. An approximation algorithm with proven polynomial time behavior was described. The recursive application of this algorithm results in the distribution of the whole remaining path slacks between the comprising nets, and as a result, zero slack is achieved. The obtained timing bounds were applied to produce layouts free from timing problems.>

An approach is proposed to the prediction, prior to layout, of the paths and nets that will most likely be critical after layout. The approach makes use of the notion of categorization. The parameters that are highly correlated with the total path delay are first identified. These parameters are combined in a single score function. This function is evaluated for each enumerated path. The k paths with the smallest scores (or largest depending on the score function) are the most critical paths. The nets covered by the selected paths are the predicted critical nets. The nets are also ranked according to their coverage frequencies, timing (load factors), and physical characteristics (number of loading pins). A description is given of the delay model used and the authors' approach to the prediction of the dangerous paths and nets. Some experimental results are presented.>

In this paper, we present algorithms and experimental results for an automated layout synthesis procedure that is used in a high-level silicon compiler. The techniques consist of a unique approach to generalized cell synthesis, together with a novel solution of the placement and routing problem. Our algorithms take advantage of a larger space of possible solutions than is available in conventional, fixed-cell approaches to achieve compact and efficient layouts.

We formulate a class of adaptive heuristics for combinatorial optimization. Recently proposed methods such as simulated annealing, probabilistic hill climbing, and sequence heuristics, as well as classical perturbation methods are all members of this class of adaptive heuristics. We expose the issues involved in using an adaptive heuristic in general, and simulated annealing, probabilistic hill climbing, and sequence heuristics in particular. These issues are investigated experimentally.

The performance of simulated annealing is compared to that of other Monte Carlo methods for optimization. Our experiments show that these other methods often perform better than simulated annealing.