Path-Sensitized Covering Graph Method for Technology Mapping of Complex Gates

Ja-Choon JEONG; Chong-Min KYUNIG

Path-Sensitized Covering Graph Method for Technology Mapping of Complex Gates

Ja-Choon JEONG, Chong-Min KYUNIG

Full Text Views

0

Cite this

Summary :

This paper proposes a new technology mapping procedure for minimizing the area and/or delay of complex logic gates using the so-called Path-Sensitized Covering Graph (PSCG) constructed from the given Boolean network and library cells. In the earlier tree covering algorithms, the original DAG (Directed Acyclic Graph) covering problem is only approximately solved by reducing the problem size and the search space based on the partitioning of the whole circuit at the multiple fan-out node, which makes the resultant solution locally optimal. Compared to this, our algorithm is more general in that it does not arbitrarily partition the DAG into a set of trees. This is necessary not to exclude the possibility of mapping into some library cell a portion of a given circuit across branching points (fan-out nodes). Three different problems, i.e., area minimization, delay minimization considering the capacitive loading, and area minimization under timing constraint are formulated as a nonlinear 0-1 integer programming problem for which a recently developed MFA (Mean Field Annealing) algorithm was successfully applied. Results on the performance of this procedure using a set of MCNC Benchmark examples have shown a notable improvement compared to the earlier tree covering algorithm for the case of area minimization.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.10 pp.3057-3064

Publication Date: 1991/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on JTC-CSCC '90)

Category: VLSI Design Technology

Authors

Ja-Choon JEONG
Chong-Min KYUNIG

Keyword

Cite this

Copy

Ja-Choon JEONG, Chong-Min KYUNIG, "Path-Sensitized Covering Graph Method for Technology Mapping of Complex Gates" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 10, pp. 3057-3064, October 1991, doi: .
Abstract: This paper proposes a new technology mapping procedure for minimizing the area and/or delay of complex logic gates using the so-called Path-Sensitized Covering Graph (PSCG) constructed from the given Boolean network and library cells. In the earlier tree covering algorithms, the original DAG (Directed Acyclic Graph) covering problem is only approximately solved by reducing the problem size and the search space based on the partitioning of the whole circuit at the multiple fan-out node, which makes the resultant solution locally optimal. Compared to this, our algorithm is more general in that it does not arbitrarily partition the DAG into a set of trees. This is necessary not to exclude the possibility of mapping into some library cell a portion of a given circuit across branching points (fan-out nodes). Three different problems, i.e., area minimization, delay minimization considering the capacitive loading, and area minimization under timing constraint are formulated as a nonlinear 0-1 integer programming problem for which a recently developed MFA (Mean Field Annealing) algorithm was successfully applied. Results on the performance of this procedure using a set of MCNC Benchmark examples have shown a notable improvement compared to the earlier tree covering algorithm for the case of area minimization.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_10_3057/_p

Copy

@ARTICLE{e74-a_10_3057,
author={Ja-Choon JEONG, Chong-Min KYUNIG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Path-Sensitized Covering Graph Method for Technology Mapping of Complex Gates},
year={1991},
volume={E74-A},
number={10},
pages={3057-3064},
abstract={This paper proposes a new technology mapping procedure for minimizing the area and/or delay of complex logic gates using the so-called Path-Sensitized Covering Graph (PSCG) constructed from the given Boolean network and library cells. In the earlier tree covering algorithms, the original DAG (Directed Acyclic Graph) covering problem is only approximately solved by reducing the problem size and the search space based on the partitioning of the whole circuit at the multiple fan-out node, which makes the resultant solution locally optimal. Compared to this, our algorithm is more general in that it does not arbitrarily partition the DAG into a set of trees. This is necessary not to exclude the possibility of mapping into some library cell a portion of a given circuit across branching points (fan-out nodes). Three different problems, i.e., area minimization, delay minimization considering the capacitive loading, and area minimization under timing constraint are formulated as a nonlinear 0-1 integer programming problem for which a recently developed MFA (Mean Field Annealing) algorithm was successfully applied. Results on the performance of this procedure using a set of MCNC Benchmark examples have shown a notable improvement compared to the earlier tree covering algorithm for the case of area minimization.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Path-Sensitized Covering Graph Method for Technology Mapping of Complex Gates
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3057
EP - 3064
AU - Ja-Choon JEONG
AU - Chong-Min KYUNIG
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1991
AB - This paper proposes a new technology mapping procedure for minimizing the area and/or delay of complex logic gates using the so-called Path-Sensitized Covering Graph (PSCG) constructed from the given Boolean network and library cells. In the earlier tree covering algorithms, the original DAG (Directed Acyclic Graph) covering problem is only approximately solved by reducing the problem size and the search space based on the partitioning of the whole circuit at the multiple fan-out node, which makes the resultant solution locally optimal. Compared to this, our algorithm is more general in that it does not arbitrarily partition the DAG into a set of trees. This is necessary not to exclude the possibility of mapping into some library cell a portion of a given circuit across branching points (fan-out nodes). Three different problems, i.e., area minimization, delay minimization considering the capacitive loading, and area minimization under timing constraint are formulated as a nonlinear 0-1 integer programming problem for which a recently developed MFA (Mean Field Annealing) algorithm was successfully applied. Results on the performance of this procedure using a set of MCNC Benchmark examples have shown a notable improvement compared to the earlier tree covering algorithm for the case of area minimization.
ER -