Simulated annealing, a methodology for solving combinatorial optimization problems, is a very computationally expensive algorithm and, as such, numerous researchers have undertaken efforts to parallelize it. In this paper, we investigate three of these parallel simulated annealing strategies when applied to standard cell placement, specifically the TimberWolfSC placement tool. We have examined a parallel moves strategy, as well as two new approaches to parallel cell placement-multiple Markov chains and speculative computation. These algorithms have been implemented in ProperPLACE, our parallel cell placement application, as part of the ProperCAD II project. We have constructed ProperPLACE so that it is portable across a wide range of parallel architectures. Our parallel moves algorithm uses novel approaches to dynamic message sizing, message prioritization, and error control. We show that parallel moves and multiple Markov chains are effective approaches to parallel simulated annealing when applied to TimberWolfSC, yet speculative computation is wholly inadequate.

Present design for testability techniques, in general, result in a large area overhead und perjormance clegruclation. An algorithm is presented which uses the layoul infornzation as well as the knowledge generated during the testgeneration process to select a set of observable lestpoints. These testpoints are implemented at the luyout level and suffer virtually no area and performance overhead. We have petjiormecl an experimentul evuluation of this technique where testpoints were inserted to sequentiul ISCAS-benchmarks and the fault coverage was obtained along with the urea and the performance overheads. The results show that our design for testubiliv method is cost effective and produces a high jault coverage for sequential circuits.

An accurate timing model is presented for MOS circuits, which is based on a multiple-valued logic representation, accurate RC models for delay calculations derived from transistor characteristics and slope information, and accurate models for physical failures. A delay fault simulator (FACT) based on this model has been implemented. Results for various MOS circuits are described and compared with those for SPICE and RSIM.>