This paper reviews theoretical advances to the field of simulated annealing optimization and applications to physical design contributed by Ralph Otten. At this year's ISPD, Ralph Otten receives the ISPD Lifetime Achievement award for outstanding contributions made to the field of physical design automation over multiple decades. For this occasion this paper highlights some of the research contributions by Ralph Otten in simulated annealing. It recounts how he moved from applications of simulated annealing to analyzing and understanding the method from a theoretical standpoint and how it was developed into a general purpose algorithm.

This paper presents a methodology for full chip RTL timing closure for very large ASIC's. The methodology is based on the concept of a "Silicon Virtual Prototype". The methodology is based on the scalable technique of clustering and cluster placement and leverages the tight integration between the algorithms by means of a common, unified data model.

In this paper, we show that under the constant delay model the placement problem is equivalent to minimizing a weighted sum of wire lengths. The weights can be efficiently computed once in advance and still accurately reflect the circuit area throughout the placement process. The existence of an efficient and accurate cost function allows us to directly optimize circuit area. This leads to better results compared to heuristic edge weight estimates or optimization for secondary criteria such as wire length. We leverage this property to improve a recursive partitioning based tool flow. We achieve area savings of 27% for some circuits and 15% on average. The use of the constant delay model additionally enables timing closure without iterations.

Non-uniform temperature profiles along global interconnect lines in high-performance ICs can significantly impact the performance of these lines. This paper presents a detailed analysis and modeling of the interconnect performance degradation due to non-uniform temperature profiles that exist along their lengths, which in turn arise due to the thermal gradients in the underlying substrate. A non-uniform temperature-dependent distributed RC interconnect delay model is proposed for the first time. The model has been applied to a wide variety of interconnect layouts and temperature distributions to quantify the impact on signal integrity issues including clock skew fluctuations.

Presents a very efficient optimization method suitable for multi-level combinational circuits. The optimization is based on incremental restructuring of a circuit through a sequence of additions and removals of redundant wires. Our algorithm applies the techniques of automatic test pattern generation (ATPG), which can efficiently detect redundancies. During the ATPG process, certain nodes in the circuit must have particular logic assignments for a test to exist. Based on the properties of these mandatory assignments, we have developed theorems to eliminate unnecessary wire redundancy checking. This results in a significant performance improvement. The fast run time and the excellent scaling to large circuits make our Boolean optimization method practical for industrial applications.

Due to deep sub micron effects, accurate gate sizing is increasingly important. Most advanced methods for sizing assume that gates can be sized continuously, while most design is done with discrete gate array and standard cell libraries. To bridge this gap, this paper proposes a new approach to gate sizing which combines a small number of discrete gate sizes to approximate the ideal of continuous sizing. To date research has focussed on deciding an appropriate set of logic functions for the primitive gates in a library. The main contribution of this paper is the development of a theoretical framework for strategies of drive strength selection for libraries. We demonstrate that nearly continuous sizing can be achieved by combining gates of a small number of sizes. The experimental procedure is based on simulated annealing. The results show that with only 5 discrete sizes any continuous size within a range of two orders of magnitude can be approximated with an accuracy of 1.7%.

This paper presents a very efficient Boolean logic optimization method. The boolean optimization is achieved by adding and removing redundant wires in a circuit. Our algorithm applies the reasoning of Automatic Test Pattern Generation (ATPG) which can detect redundancy efficiently. During the ATPG process, mandatory assignments are assignments which must be satisfied. Our algorithm analyzes different characteristics of mandatory assignments during the ATPG process. New theoretical results based on the analysis are presented which lead to significant performance improvements. The fast run time and the excellent scaling to large problems make our Boolean optimization method practical for industrial applications. Experiments show that the optimization results are comparable to those of Kunz and Pradhan (1994) while the run time is two orders of magnitude faster (average 126/spl times/ speed up). Furthermore, we report optimization results for several large examples, which were previously thought to be too large to be handled by Boolean optimization methods.

This paper presents the mapping problem for pass transistor selector mapping, which has not been addressed before. Pass transistor synthesis is potentially important for semi- or full-custom design techniques, which are increasingly attracting attention. Pass transistors have the advantage that fewer transistors are needed, and that circuits with high fanin and small delay can be constructed. Technology mapping approaches in the existing literature cannot handle these selectors, due to the restriction of I-hot encoding of the control signals. We present a new algorithm to address this problem, which is based an the novel idea of a general Boolean Oracle. Our oracle is based on ATPG techniques, and compared to BDDs, the oracle has the advantage that failure to complete only affects optimization locally, and does not hinder optimization elsewhere in the logic. A limitation of BDDs is that it is difficult to complete the algorithm if a BDD grows too large. The experimental results show up to 82% improvement in transistor count for the MCNC combinatorial multi-level examples.

The paper describes some of the synthesis controls in the BooleDozer synthesis system which are unique in concept and implementation. Rather than attempting to achieve the maximum amount of optimization in the minimum amount of run time, the designer specifies the restructuring level which allows him to specify to what extent the original structure should be preserved. We also describe controls which affect the mapping process. Finally we describe the incremental synthesis feature. The run time can be accurately controlled by a run-time budgeting mechanism.>

Systems for multi-level logic optimization are usually based on a set of specialized, loosely-related transformations which work on a network representation. The sequence of transformations in a synthesis scenario (script) is crucial for the performance of the whole system. This paper presents the application of a genetic algorithm for automatic tuning of scenarios, and therefore an approach for optimizing the synthesis process itself. We introduce a general context-free grammar to describe the set of relevant scenarios. For such grammars, we develop meaningful genetic operators for the implementation of an evolutionary search. Experiments with an industrial logic synthesis system show that our method can improve the efficiency of manually designed standard scenarios by an average of 8%. We also show that this approach can effectively tune scenarios to particular design styles and/or specific synthesis goals.>

This paper presents the timing verification and optimization tools used for the 601, 603, 604 and 620 PowerPC processor designs. The timing verification is done by static timing analysis at the chip level, while the timing optimization is done by synthesis at the macro level. A method for automatically deriving timing constraints for timing optimization is described.>

A method for fan-in ordering of commutative functions in combinational logic is described. The objective is to maximise the worst slack in a multislot timing analysis environment. The main contribution is the notion that the problem can be formulated as a bipartite matching problem, in which the minimum weight of any element is maximised. The advantage of the method is that it gives optimal results over a large range of delay models. The optimization problem can be solved exactly in O(n/sup 2/ square root n In n) time, where n is the number of commutative pins, and only n timing calculations are necessary.>

The number of decrements necessary if the changes in the equilibrium density are bounded is derived for a simulated annealing problem. This gives an expression for the CPU-time of the process when all chains have the same length. This expression can also be used for tuning the annealing schedule for a given total CPU-time, while keeping the disturbance of the equilibrium as small as possible. The expression is also valid for generic annealing processes that use a constant factor to obtain the next value of t (the commonly used schedule).>

The authors propose stopping criteria based on statistics collected during the annealing. In contrast to conventional stop criteria, the proposed criteria do not depend on the move set. Specifically, formulae are presented for detecting that an adequate final temperature has been reached. The arguments of the formulae are obtained by observing the behavior of the variance of the score for the instance at hand. The formulae are based on experience with several applications of simulated annealing as well as facts derived from the theory of homogeneous Markov chains.>