Placement Optimization by Trembling Spot-Check

Masahiko TOYONAGA; Hiroaki OKUDE; Toshiro AKINO

Placement Optimization by Trembling Spot-Check

Masahiko TOYONAGA, Hiroaki OKUDE, Toshiro AKINO

Full Text Views

0

Share
Cite this

Summary :

In this paper we describe a new non-deterministic optimization method for standard-cell placement based on a method of theoretical physics, which we call the Trembling Spot-Check (TSC). First we discuss the analogy between a primitive cell placement system and a magnetic spin system by mapping from the placement evaluation function to the energy function, where the primitive placement system consists of the same area size cell and interconnections related to its four neighbor cells. Then we introduce a computational state calculation method using the theory for the magnetic spin system, called the `mean-field method'. The placement improvement process by TSC is similar to the energy minimization process by the mean-field method at temperature 0. To prevent the final state of the system from falling into a local minima, we adopt the redundance factor to this method by paying attention to the concept of fluctuation in statistical physics. This method of optimization, called TSC, has two such special features that it needs no annealing process and requires only one parameter definition concerning the redundancy. These two faculities in TSC make it possible to achieve the minimal solution without the bore process such as in the method of Simulated Annealing (SA). This new non-deterministic method of optimization is applied to both primitive and standard-cell placement problems. In the standard-cell placement problem each cell has the same height and various widths, and the interconnections between cells are very complicated. In the primitive placement experiments, TSC is compared with SA by the total interconnection length costs of the final states and CPU time to obtain them. In the standard-cell placement problem, the area size is evaluated. We suggest a simple model for standard-cell evaluation function derived from the area size estimation. It consists of averaged values of channel heights and their standard deviations. The results in the primitive placements show that TSC requires almost 1/10 times less CPU time than SA to achieve the same level solution. Almost the same results can be observed in the experiments of standard-cell placement.

Publication: IEICE TRANSACTIONS on transactions Vol.E72-E No.12 pp.1350-1359

Publication Date: 1989/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on the 2nd Karuizawa Workshop on Circuits and Systems)

Category: VLSI Design Technology

Authors

Masahiko TOYONAGA
Hiroaki OKUDE
Toshiro AKINO

Keyword

Cite this

Copy

Masahiko TOYONAGA, Hiroaki OKUDE, Toshiro AKINO, "Placement Optimization by Trembling Spot-Check" in IEICE TRANSACTIONS on transactions, vol. E72-E, no. 12, pp. 1350-1359, December 1989, doi: .
Abstract: In this paper we describe a new non-deterministic optimization method for standard-cell placement based on a method of theoretical physics, which we call the Trembling Spot-Check (TSC). First we discuss the analogy between a primitive cell placement system and a magnetic spin system by mapping from the placement evaluation function to the energy function, where the primitive placement system consists of the same area size cell and interconnections related to its four neighbor cells. Then we introduce a computational state calculation method using the theory for the magnetic spin system, called the `mean-field method'. The placement improvement process by TSC is similar to the energy minimization process by the mean-field method at temperature 0. To prevent the final state of the system from falling into a local minima, we adopt the redundance factor to this method by paying attention to the concept of fluctuation in statistical physics. This method of optimization, called TSC, has two such special features that it needs no annealing process and requires only one parameter definition concerning the redundancy. These two faculities in TSC make it possible to achieve the minimal solution without the bore process such as in the method of Simulated Annealing (SA). This new non-deterministic method of optimization is applied to both primitive and standard-cell placement problems. In the standard-cell placement problem each cell has the same height and various widths, and the interconnections between cells are very complicated. In the primitive placement experiments, TSC is compared with SA by the total interconnection length costs of the final states and CPU time to obtain them. In the standard-cell placement problem, the area size is evaluated. We suggest a simple model for standard-cell evaluation function derived from the area size estimation. It consists of averaged values of channel heights and their standard deviations. The results in the primitive placements show that TSC requires almost 1/10 times less CPU time than SA to achieve the same level solution. Almost the same results can be observed in the experiments of standard-cell placement.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e72-e_12_1350/_p

Copy

@ARTICLE{e72-e_12_1350,
author={Masahiko TOYONAGA, Hiroaki OKUDE, Toshiro AKINO, },
journal={IEICE TRANSACTIONS on transactions},
title={Placement Optimization by Trembling Spot-Check},
year={1989},
volume={E72-E},
number={12},
pages={1350-1359},
abstract={In this paper we describe a new non-deterministic optimization method for standard-cell placement based on a method of theoretical physics, which we call the Trembling Spot-Check (TSC). First we discuss the analogy between a primitive cell placement system and a magnetic spin system by mapping from the placement evaluation function to the energy function, where the primitive placement system consists of the same area size cell and interconnections related to its four neighbor cells. Then we introduce a computational state calculation method using the theory for the magnetic spin system, called the `mean-field method'. The placement improvement process by TSC is similar to the energy minimization process by the mean-field method at temperature 0. To prevent the final state of the system from falling into a local minima, we adopt the redundance factor to this method by paying attention to the concept of fluctuation in statistical physics. This method of optimization, called TSC, has two such special features that it needs no annealing process and requires only one parameter definition concerning the redundancy. These two faculities in TSC make it possible to achieve the minimal solution without the bore process such as in the method of Simulated Annealing (SA). This new non-deterministic method of optimization is applied to both primitive and standard-cell placement problems. In the standard-cell placement problem each cell has the same height and various widths, and the interconnections between cells are very complicated. In the primitive placement experiments, TSC is compared with SA by the total interconnection length costs of the final states and CPU time to obtain them. In the standard-cell placement problem, the area size is evaluated. We suggest a simple model for standard-cell evaluation function derived from the area size estimation. It consists of averaged values of channel heights and their standard deviations. The results in the primitive placements show that TSC requires almost 1/10 times less CPU time than SA to achieve the same level solution. Almost the same results can be observed in the experiments of standard-cell placement.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Placement Optimization by Trembling Spot-Check
T2 - IEICE TRANSACTIONS on transactions
SP - 1350
EP - 1359
AU - Masahiko TOYONAGA
AU - Hiroaki OKUDE
AU - Toshiro AKINO
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 12
JA - IEICE TRANSACTIONS on transactions
Y1 - December 1989
AB - In this paper we describe a new non-deterministic optimization method for standard-cell placement based on a method of theoretical physics, which we call the Trembling Spot-Check (TSC). First we discuss the analogy between a primitive cell placement system and a magnetic spin system by mapping from the placement evaluation function to the energy function, where the primitive placement system consists of the same area size cell and interconnections related to its four neighbor cells. Then we introduce a computational state calculation method using the theory for the magnetic spin system, called the `mean-field method'. The placement improvement process by TSC is similar to the energy minimization process by the mean-field method at temperature 0. To prevent the final state of the system from falling into a local minima, we adopt the redundance factor to this method by paying attention to the concept of fluctuation in statistical physics. This method of optimization, called TSC, has two such special features that it needs no annealing process and requires only one parameter definition concerning the redundancy. These two faculities in TSC make it possible to achieve the minimal solution without the bore process such as in the method of Simulated Annealing (SA). This new non-deterministic method of optimization is applied to both primitive and standard-cell placement problems. In the standard-cell placement problem each cell has the same height and various widths, and the interconnections between cells are very complicated. In the primitive placement experiments, TSC is compared with SA by the total interconnection length costs of the final states and CPU time to obtain them. In the standard-cell placement problem, the area size is evaluated. We suggest a simple model for standard-cell evaluation function derived from the area size estimation. It consists of averaged values of channel heights and their standard deviations. The results in the primitive placements show that TSC requires almost 1/10 times less CPU time than SA to achieve the same level solution. Almost the same results can be observed in the experiments of standard-cell placement.
ER -