Optimal Layout Synthesis of Standard Cells
in Large Scale Integration⎛⎞⎜⎜⎜ 大規模集積回路におけるスタンダードセルレイアウトの ⎟⎟⎟
⎜⎜⎜
⎟⎟⎟
⎝
⎠
最適自動合成手法

A Dissertation
Submitted to the Department ofElectronic Engineering,
the University of Tokyo
in Partial Fulfillment of the Requirements
for the Degree of Doctor of Philosophy

Supervisor: Professor Kunihiro Asada

Tetsuya Iizuka
DEPARTMENT OF ELECTRONIC ENGINEERING,THE UNIVERSITY OF TOKYO

December 2006

c 2006 by Tetsuya Iizuka, All Rights Reserved.
Copyright Abstract
This thesis focuses on the optimization methods for standard cell layouts. Standard cells
are the most fundamental components of VLSI, and provide the building blocks for creatinglarge complex functions in both application-specific and semi-custom domains. Therefore,
their performance has significant eﬀects on the final performance of the synthesized VLSI.
We propose a minimum-width transistor placement and an intra-cell routing via Boolean
satisfiability to optimize the area of the cell layouts. We also propose a comprehensive celllayout synthesis method and a cell layout de-compaction method for yield optimization.
Chapter 2 proposes a minimum-width layout synthesis method for dual CMOS cells via
Boolean Satisfiability (SAT). Cell layout synthesis problems, i.e., the transistor placement
and the intra-cell routing problems are first transformed into SAT problems by this formulation. The proposed method guarantees to generate minimum-width cell layouts with routability under our layout styles. This method places complementary P and N type transistors individually during transistor placement, and can generate smaller width layout compared withthe case of pairing the complementary P and N type transistors. The experimental results
show that the proposed method generates the cell layouts of 30 dual CMOS logic circuits
in 58% runtime with only 5% area increase compared with the commercial cell generation
tool with cell layout compaction. This result indicates that our cell layout styles defined for
the SAT formulation is practical enough to generate the layout of dual CMOS cells quickly
with a little area overhead. Since this method still has a restriction in gate connection style
between P and N type transistors, it is applicable only to dual CMOS cells. The extension of
the transistor placement method for non-dual cells is explained in Chapter 4.
Chapter 3 describes a hierarchical extension of the cell layout synthesis method proposed
in Chapter 2 for the cell layout synthesis of large dual CMOS cells. This method partitions agiven transistor-level netlist into blocks considering the transistor connections by diﬀusions.
Intra-block placement uses the exact transistor placement method proposed in Chapter 2, andhierarchically generates the transistor placement with routability. The comparison resultswith the flat cell layout synthesis method show that the proposed hierarchical method reduces
the runtime for cell layout synthesis drastically with little width increase. The comparisoniAbstractii

results with the commercial cell generation tool without cell layout compaction show thatthe total cell width is increased about 4% by the proposed method due to the layout style
restriction, whereas the runtime is only about 3% of that of the commercial tool. These
results show the eﬀectiveness of the proposed method as a quick layout generator in the areaof transistor-level circuit optimization such as on-demand cell layout synthesis.
Chapter 4 shows flat and hierarchical approaches for generating a minimum-width transistor placement of CMOS cells in presence of non-dual P and N type transistors, whereas
the cell layout synthesis methods proposed in the previous chapters are only for dual cells.
This chapter targets the minimum-width transistor placement, and does not take the intra-cellroutings into consideration. Our approaches are the first exact transistor placement methods
which can be applied to CMOS cells with any types of structure, whereas almost all of theconventional exact transistor placement method is applicable only to dual CMOS cells. Experimental results show that the proposed method is not only applicable to CMOS cells withany types of structure, but also more eﬀective even for dual CMOS cells compared with thetransistor placement method proposed in Chapter 2. The hierarchical single-row approach isshown to be eﬀective to reduce the runtime drastically. This chapter also shows the generalization results of the single-row transistor placement method into the multi-row placement.
The proposed exact minimum-width multi-row transistor placement method generates morearea-eﬃcient placement than the conventional method only for dual cells by using the gateconnection style which is more suitable for multi-row transistor placement than the conventional style and can solve the cells with up to 26 transistors in reasonable runtime.
Chapter 5 introduces a cell layout synthesis technique to optimize the yield. The yieldcost metric used in this chapter is the sensitivity to wiring faults due to spot defects. The
sensitivity to faults on intra-cell routings is modeled with consideration to the spot defects
size distribution and the end eﬀect of critical areas. The impact of the sensitivity reduction
on the yield improvement is also discussed in this chapter. The minimum-width cell layoutof CMOS logic cells are comprehensively generated using the transistor placement method
proposed in Chapter 2 and the comprehensive intra-cell routing method proposed in thischapter. The yield optimal layouts are selected from the exhaustively-generated layouts byusing the proposed sensitivity to wiring faults as a cost function. The experimental results
on 8 CMOS logic circuits which have up to 14 transistors show that the fault sensitivity is
reduced about 15% on an average by selecting the minimum-sensitivity layouts rather thanselecting the minimum-wire-length layouts.

Abstractiii

Chapter 6 proposes a timing-aware cell layout de-compaction method for yield optimization using Linear Programming (LP). The proposed method performs a de-compaction of theoriginal layout in order to improve the yield by minimizing the Critical Area (CA) inside
the cell. This yield improvement procedure is executed under given timing constraints. To
formulate the timing constraints into LP, a new accurate linear delay model which approximates the diﬀerence from the original delay is proposed. Using the proposed timing-aware
yield enhancement method, we can explore the trade-oﬀ between yield and performance, andcan pick up the yield/performance variants from the trade-oﬀ curve. The eﬀectiveness of the
proposed method for OPC mask data volume reduction is also shown in this chapter. The
experimental results on 90nm cell layouts demonstrate an average of 4.28% reduction in thefractured mask data size in the case that 10% delay increase is allowed. This timing-awarede-compaction framework is extended to the redundant contact insertion adjacent to the original single contacts to minimize the yield loss due to contact failure. To take the parametricyield into account, the proposed method is also extended to the gate layout pattern regularity
enhancement to reduce the systematic variation of the gate critical dimensions (CD). Theedge placement error (EPE) estimation results show that the standard deviation of the gate
CD EPE distribution is reduced by about 28% compared to that of the original layouts.
We are sure that these results in this thesis such as the exact minimum-width cell layout
synthesis techniques, the comprehensive cell layout synthesis method, and the cell layout decompaction method for yield optimization will be used for standard-cell layout optimizationin terms of area, delay, and yield, and contribute to the VLSI performance and reliability
improvements.

Acknowledgments
During my years in the University of Tokyo, I have been very fortunate to be surroundedby teachers, family, friends, and colleagues who have continually oﬀered me support andencouragement. I would like to thank, from the bottom of my heart, for their contributions tomy professional and personal growth.
With the utmost gratitude, I would like to thank the dissertation supervisor, Prof. Kunihiro
Asada for his keen insight, enduring guidance, and encouragement throughout my undergraduate and graduate studies. His wisdom and knowledge not only in the field of my research
have greatly expanded my interest in and enriched my knowledge of VLSI and philosophy
about research, and his constant support, fruitful discussion, and many great opportunities
he gave me since my undergraduate years led me to become a full-fledged member of society. I feel very fortunate to have taken him as my supervisor, and I will forever cherish thisexperience as my lifetime guidance.
I would also like to deeply thank Prof. Makoto Ikeda for his meaningful advices and discussions on my research. I greatly appreciate his constructive support and the time he waswilling to spend for providing a comfortable environment to promote my research progress.
I am deeply grateful to Mr. Hiroaki Yoshida, who is a research colleague in Asada-Ikeda
laboratory, for his professional experience and extensive knowledge. His diligent support in
the start-up phase of my undergraduate research made me take a significant step toward mylife as a researcher. He also provided a friendly atmosphere and a plenty of relaxed time inthe laboratory. The time spent with him talking about both professional and private topics
is an essential part of my laboratory life. I could never bring my research to be successful
without his direct support and kind advices.
I would like to acknowledge Dr. Yusuke Oike, who is currently in Sony Corp., for his valuable advices originated in his exceptional research talent, and indispensable encouragement
during my years in the laboratory. I decided to proceed to Ph.D. course and worked hardon trying to follow him. The inherited mental attitude and enthusiasm toward research activities were fundamental for the success of my research and will be invaluable assets in myprofessional career.
iv

Acknowledgmentsv

I would like to thank Dr. Toru Nakura, who is currently in NEC Corp., for his encouragement and thoughtful advices originated in his professional experience and self-confidence inbeing mature engineer. He gave me many technical suggestions on my research as well as
frank advices on both professional and private topics. He has been a senior adviser of mylife.
I am grateful to all the current and past members in Asada-Ikeda laboratory for their helpful advices, heartful encouragement, comfortable research circumstances and pleasant time:in particular, Prof. Toru Ishihara, who is currently in Kyushu University, for his great dealof support in the start-up phase of my research; Dr. Hiroaki Yamaoka, who is currently
in Toshiba Corp., for his friendly talk and many essential advices on my laboratory life;
Dr. Satoshi Komatsu, for his generous support and advices on my research and many otheractivities in the laboratory; Mr. Routong Zheng, for his assistance for establishing CAD
environment which is essential to my research; Dr. Masahiro Sasaki, for his advices on myresearch as well as other chip design activities; Mr. Yusuke Yachide and Mr. Taisuke Kazama,
for having many discussions as well as a plenty of pleasant time with me; Ms. Noriko
Yokochi, Ms. Naomi Yoshida, and Ms. Yukako Maruyama, for their helpful assistance formy research activities in the laboratory.
I would like to acknowledge my dissertation committee, Prof. Tadashi Shibata,Prof. Masahiro Fujita, Prof. Minoru Fujishima, and Prof. Makoto Takamiya, for their extremely valuable suggestions and comments.
I wish to thank all the members of VLSI Design and Education Center (VDEC), the University of Tokyo, for their support in CAD environment and VLSI process technologies. The
CAD tools and process technologies used in this study have been provided by Synopsys,Inc., Cadence Design Systems, Inc., Mentor Graphics, Corp., Rohm Corp., and Semiconductor Technology Academic Research Center (STARC) through VDEC.
I also wish to thank the Grant-in-Aid for Scientific Research of the Japan Society for the
Promotion of Science (JSPS) for the financial support.
I would like to give my thanks to all of my friends, especially in Wimbledon Tennis Teamof the University of Tokyo who have been giving me a plenty of pleasant and relaxed time,and encouragement for a long time of my life in the University of Tokyo.
Finally, I would like to express my greatest appreciation to my parents, Katsumi and
Makiko, and to my grandparents, Keiichi and Michi, for their constant support and encouragement throughout my life.

Contents
Abstracti

Acknowledgmentsiv

List of Figuresix

List of Tables

xiii

Chapter 1 Introduction

1

1.1

Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Research Objectives and Thesis Organization . . . . . . . . . . . . . . . . .

3

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

6

2.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Layout Styles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3

Transistor Placement Formulation . . . . . . . . . . . . . . . . . . . . . . .

9

2.4

Intra-Cell Routing Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.6

2.5.1

Comparison with the 0-1 ILP Formulation . . . . . . . . . . . . . . . 16

2.5.2

Comparison with the Commercial Cell Generation Tool . . . . . . . 18

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

23

3.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2

Layout Styles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3

Hierarchical Transistor Placement . . . . . . . . . . . . . . . . . . . . . . . 25

3.4

3.3.1

Partitioning into Logic Blocks . . . . . . . . . . . . . . . . . . . . . 26

3.3.2

Intra-Block Transistor Placement Formulation . . . . . . . . . . . . . 26

3.3.3

Inter-Block Placement Formulation . . . . . . . . . . . . . . . . . . 30

Intra-Cell Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

vi

vii

Contents

3.5

Overall Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.6

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.7

3.6.1

Transistor Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.6.2

Cell Layout Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 33

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells 36
4.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.2

Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3

Flat Single-Row Transistor Placement . . . . . . . . . . . . . . . . . . . . . 40

4.4

Hierarchical Single-Row Transistor Placement . . . . . . . . . . . . . . . . . 42

4.5

Generalization to Multi-Row Transistor Placement . . . . . . . . . . . . . . 46

4.6

4.7

4.5.1

Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.5.2

Placement Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 46

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6.1

Single-Row Flat Approach . . . . . . . . . . . . . . . . . . . . . . . 50

4.6.2

Single-Row Hierarchical Approach . . . . . . . . . . . . . . . . . . 54

4.6.3

Multi-Row Placement . . . . . . . . . . . . . . . . . . . . . . . . . 56

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

60

5.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.2

Wiring Fault Model for Yield Cost Function . . . . . . . . . . . . . . . . . . 61

5.3

Layout Styles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.4

Comprehensive Cell Layout Synthesis . . . . . . . . . . . . . . . . . . . . . 65
5.4.1

Transistor Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.4.2

Intra-Cell Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.5

Overall System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.6

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.7

Discussion of Yield Cost Metrics . . . . . . . . . . . . . . . . . . . . . . . . 75

5.8

5.7.1

Lithography Impact on the Critical Area . . . . . . . . . . . . . . . . 75

5.7.2

Relation Between Sensitivity and Performance . . . . . . . . . . . . 77

5.7.3

Relation Between Sensitivity and Yield . . . . . . . . . . . . . . . . 77

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

viii

Contents

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

80

6.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.2

Problem Definition and Design Rule Constraints . . . . . . . . . . . . . . . . 82

6.3

Yield Cost Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.1

Critical Area Minimization . . . . . . . . . . . . . . . . . . . . . . . 83

6.3.2

OPC Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.3.3

Redundant Contact Insertion . . . . . . . . . . . . . . . . . . . . . . 88

6.3.4

Gate Layout Pattern Regularity Enhancement . . . . . . . . . . . . . 90

6.4

Delay Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.5

Overall Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.6

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

6.7

6.6.1

Critical Area Minimization . . . . . . . . . . . . . . . . . . . . . . . 100

6.6.2

OPC Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6.6.3

Redundant Contact Insertion . . . . . . . . . . . . . . . . . . . . . . 110

6.6.4

Gate Layout Pattern Regularity Enhancement . . . . . . . . . . . . . 112

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Chapter 7 Conclusions

120

Bibliography

123

List of Publications

129

List of Figures
1.1

A simplified flow diagram of the cell-based LSI design. . . . . . . . . . . . .

2

1.2

A flow diagram of the yield-aware cell-based LSI design. . . . . . . . . . . .

3

1.3

The proposed cell layout optimization methods in perspective. . . . . . . . .

4

2.1

An illustration of the layout styles of the proposed SAT-based cell layout
synthesis for dual CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . .

92.2

A SAT formulation of the transistor placement for dual CMOS cells. . . . . . 10

2.3

A SAT formulation of the intra-cell routing. . . . . . . . . . . . . . . . . . . 12

2.4

Our SAT-based cell layout synthesis flow. . . . . . . . . . . . . . . . . . . . 15

2.5

The example result of fad1 cell layout generated by the proposed SAT-based
cell layout synthesis method for dual CMOS cells. . . . . . . . . . . . . . . . 21

3.1

An illustration of the layout styles of the hierarchical SAT-based cell layout
synthesis for dual CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2

Schematic of 2-input multiplexer and its logic block partitioning. . . . . . . . 26

3.3

The problem definition of the intra-block transistor placement. . . . . . . . . 27

3.4

Additional variables introduced to maximize the number of the connections
by diﬀusion sharing between logic blocks. . . . . . . . . . . . . . . . . . . . 28

3.5

The problem definition of the inter-block placement. . . . . . . . . . . . . . 31

3.6

Our hierarchical SAT-based cell layout synthesis flow. . . . . . . . . . . . . . 32

3.7

A layout of buﬀered full adder generated by the proposed hierarchical SATbased cell layout synthesis method. . . . . . . . . . . . . . . . . . . . . . . . 35

4.1

An example of a dual CMOS circuit which has a non-dual structure after
transistor folding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2

The problem definition of the single row transistor placement for non-dual
CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3

Schematic of 3-input multiplexer and its logic block partitioning. . . . . . . . 43ix

List of Figures

4.4x

Additional variables introduced to maximize the number of the connections
by diﬀusion sharing between logic blocks. . . . . . . . . . . . . . . . . . . . 44

4.5

The problem definition of the inter-block placement. . . . . . . . . . . . . . 45

4.6

The problem definition of the multi-row transistor placement for dual andnon-dual CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.7

Examples of the layout of the cell number 7 in Table 4.9 created by (a)theconventional and (b)the proposed multi-row placement method. The conventional style assumes the pair of P/N transistors with the same gate input
signals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.1

Critical areas between two wire segments spaced by d with the defect size x. . 62

5.2

Critical areas between two wire segments spaced by d when the defect size x
is larger than 2d + w. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.3

Grid models used in our comprehensive intra-cell routing system. . . . . . . 66

5.4

Wire branching constraint of the proposed comprehensive intra-cell routing
method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.5

The flow diagram of our comprehensive intra-cell router. . . . . . . . . . . . 68

5.6

A sample problem for explaining our comprehensive intra-cell router. . . . . 70

5.7

An example of all possible connection patterns inside a column. . . . . . . . 70

5.8

An example of all possible patterns to be extended to the subsequent column
generated from the pattern (d) in Figure 5.7. . . . . . . . . . . . . . . . . . . 71

5.9

The flow diagram of our yield-optimal cell layout synthesis system. . . . . . 72

5.10 Changes in layout sensitivity to spot defects by selecting the sensitivityminimum layouts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.11 The optimal layouts of “mux2” in Table 5.2 generated by our method andselected by (a)wire length and (b)sensitivity to spot defects. . . . . . . . . . . 75
5.12 Lithography impact on the critical area before and after OPC for 340 celllayouts in a 90nm technology. . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.13 The relation between two cost metrics in the case of the exhaustivelygenerated 27414 cell layouts of xnor2. . . . . . . . . . . . . . . . . . . . . . 77
5.14 The impact of the sensitivity reduction on the yield of the first metal layer. . . 78
6.1

Overview of the proposed timing-aware cell layout yield enhancement framework. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

List of Figures

6.2

xi

An example of a constraint graph constructed for polygons inside a given
layout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.3

The conceptual layouts of 2-input NAND created by the conventional and thetiming-aware de-compaction methods. . . . . . . . . . . . . . . . . . . . . . 84

6.4

Schematic diagram of a short type critical area. . . . . . . . . . . . . . . . . 84

6.5

Variation of (a)vertical and (b)horizontal critical areas after horizontal decompaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.6

Change of the vertical critical area by the width or space. . . . . . . . . . . . 86

6.7

Calculation of the vertical critical area. . . . . . . . . . . . . . . . . . . . . . 86

6.8

The expected mask cost and mask data size in the future technologies. . . . . 87

6.9

The conceptual example of OPC data volume reduction by expanding the
spacing between the polygons. . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.10 The change of the OPC pattern from (a)hammer head style to (b)serif style. . 88
6.11 Formulation of the redundant contact insertion. . . . . . . . . . . . . . . . . 89
6.12 Required gate CD control in the future technologies. . . . . . . . . . . . . . 91
6.13 The conceptual example of gate layout pattern regularity enhancement for
the regular pitch P by the proposed regularity enhancement method. . . . . . 92
6.14 The regularity cost function used in the proposed regularity enhancement
method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.15 An example of 2-input NAND and its RC network for calculating Elmore delay. 94
6.16 Preliminary results of delay variation by changing the transistor width andthe input slew. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.17 Preliminary results of output slew variation by changing the transistor width
and the input slew. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.18 The linear approximation of the intra-layer cross coupling capacitance between two vertically parallel wire segments. . . . . . . . . . . . . . . . . . . 97
6.19 Approximation of the cross coupling capacitance between two signals A and
B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.20 The overall flow diagram of the proposed timing-aware yield enhancement
method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.21 Accuracy of the proposed delay model in the case of the single-stage cell
NOR4 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

List of Figuresxii

6.22 Accuracy of the proposed delay model in the case of the multi-stage cell
ADDH 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.23 Trade-oﬀ curves of (a)target delay versus CA and (b)cell area versus CA in
the case of the single-stage cell NOR4 1. . . . . . . . . . . . . . . . . . . . . 105
6.24 Trade-oﬀ curves of (a)target delay versus CA and (b)cell area versus CA in
the case of the multi-stage cell OR3 2. . . . . . . . . . . . . . . . . . . . . . 106
6.25 The fractured mask data size of 20 cells in (a)90nm and (b)65nm technology
in the case that 10% delay increase is allowed. . . . . . . . . . . . . . . . . . 108
6.26 The reduction ratio of the fractured mask data size after de-compaction depending on the technology nodes. . . . . . . . . . . . . . . . . . . . . . . . 109
6.27 An example of OPC results in 65nm technology (a)before and (b)after decompaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.28 Accuracy of the proposed delay model in the case of NOR4 1. . . . . . . . . 113
6.29 Trade-oﬀ curves of target delay versus number of additional contacts in thecase of NOR4 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.30 The gate CD EPE histogram of all the cells used in this experiment without
OPC to highlight the eﬀectiveness. . . . . . . . . . . . . . . . . . . . . . . . 116
6.31 Accuracy of the cell delay constraint in the case of the largest example in
Table 6.9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.32 Trade-oﬀ curve between regularity enhancement and target cell delay in thecase of the largest example in Table 6.9. . . . . . . . . . . . . . . . . . . . . 118

List of Tables
2.1

Our layout styles of the proposed SAT-based cell layout synthesis for dual
CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

8The problem size comparison results of the transistor placement for dual cells
between ILP and SAT formulations. . . . . . . . . . . . . . . . . . . . . . . 16

2.3

The runtime comparison results of the transistor placement for dual cells between ILP and SAT formulations. . . . . . . . . . . . . . . . . . . . . . . . 17

2.4

The width comparison results of the cell layout synthesis between the commercial cell generation tool and the proposed method. . . . . . . . . . . . . . 19

2.5

The runtime comparison results of the cell layout synthesis between the commercial cell generation tool and the proposed method. . . . . . . . . . . . . . 20

3.1

Our layout styles of the hierarchical SAT-based cell layout synthesis for dual
CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2

The variables used for the intra-block transistor placement formulation. . . . 28

3.3

Comparison results between the proposed hierarchical transistor placement
and the original flat method proposed in Chapter 2. . . . . . . . . . . . . . . 34

3.4

Comparison results with the commercial cell generation tool and the original
flat method proposed in Chapter 2. . . . . . . . . . . . . . . . . . . . . . . . 34

4.1

The numbers of non-dual cells in commercial standard-cell libraries. . . . . . 37

4.2

The variables used for the formulation of the single-row transistor placement
for non-dual CMOS cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.3

The variables used for the formulation of the multi-row placement. . . . . . . 48

4.4

Cells used for the experiment of the single-row transistor placement. . . . . . 51

4.5

Problem size comparison results between the exact single-row transistor
placement method for dual cells and the proposed flat approach. . . . . . . . 52

4.6

Width and runtime comparison results between the exact single-row transistor placement method for dual cells and the proposed flat approach. . . . . . 52

xiii

List of Tables

4.7

xiv

Comparison results between our flat and hierarchical approaches of thesingle-row transistor placement. . . . . . . . . . . . . . . . . . . . . . . . . 53

4.8

Comparison of the number of cells that can be applied to the proposed exact
single-row transistor placement method and the method for dual cells in thecase of a cell library with 340 cells. . . . . . . . . . . . . . . . . . . . . . . 55

4.9

Cells used for the experiment of the multi-row transistor placement. . . . . . 55

4.10 Problem size of the proposed multi-row transistor placement formulation. . . 57
4.11 Width and runtime comparison results of the proposed multi-row transistor
placement method. The conventional style assumes the pair of P/N transistors
with the same gate input signals. . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1

Our layout styles of the proposed comprehensive cell layout synthesis method. 64

5.2

The results of the comprehensive cell layout synthesis. . . . . . . . . . . . . 73

5.3

The cell selection results of the comprehensive cell layout synthesis. . . . . . 73

6.1

The topological characteristics of the benchmark circuits used for the experiment of the critical area minimization. . . . . . . . . . . . . . . . . . . . . . 100

6.2

The performance characteristics of the benchmark circuits used for the experiment of the critical area minimization. . . . . . . . . . . . . . . . . . . . 101

6.3

The delay accuracy of the proposed timing-aware critical area minimization
method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6.4

Results of the critical area minimization by the proposed method. . . . . . . . 103

6.5

The topological characteristics of the benchmark circuits used for the experiment of redundant contact insertion. . . . . . . . . . . . . . . . . . . . . . . 110

6.6

The performance characteristics of the benchmark circuits used for the experiment of redundant contact insertion. . . . . . . . . . . . . . . . . . . . . 110

6.7

The delay accuracy of the proposed timing-aware redundant contact insertion
method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.8

Results of the redundant contact insertion by the proposed method. . . . . . . 112

6.9

The delay accuracy, area increase, and runtime of the proposed regularity
enhancement method with 10% allowable delay increase. . . . . . . . . . . . 114

6.10 The regularity cost reduction of the proposed regularity enhancement methodwith 10% allowable delay increase. . . . . . . . . . . . . . . . . . . . . . . . 115

Chapter 1
Introduction

1.1 Background
The recent progress in VLSI process technologies enables us to integrate a large numberof transistors on one chip, and significantly improves the circuit performance. On the other
hand, due to the ever-increasing design complexity of the VLSI, we could never design any
competitive SoCs within practical time-to-market without automated design techniques.
One of the major automated design methodologies for VLSIs is the cell-based design. Figure 1.1 shows the simplified flow diagram of the cell-based LSI design. In this design flow, acircuit mask layout is automatically generated through logic synthesis and place&route processes from a hardware description written in Hardware Description Language (HDL). This
design flow has been automated by a lot of EDA vendors, and a lot of commercial tools arealso available[1, 2, 3, 4, 5]. In these logic synthesis and place&route stage, we use a standardcell library. The characteristics of cells including cell delay, area, and power are used in the
logic synthesis stage, and the physical layout of each cell is used in the place&route stage. As
is clear from this design flow, standard cells are the most fundamental components of VLSI,and provide the building blocks for creating large complex functions in both applicationspecific and semi-custom domains. Therefore, their performance has significant eﬀects on
the final performance of the synthesized VLSI.
Until recently, a lot of papers have been published in the area of the automatic cell layout synthesis[6, 7, 8, 9, 10]. Conventionally, these standard cells are usually designed andthoroughly optimized by hand. However, the progress in the automatic transistor-level layout
generation now enables us to automatically generate the cell layouts which have comparable
quality to those designed by hand and drastically reduces the required time for creating new
standard-cell libraries. Moreover, some automatic cell synthesis methods are also used for1

2

Chapter 1 Introduction

Hardware Description

Logic Synthesis

Cell Characteristics
Area, Delay, PowerStandard-Cell
Library
Place & RoutePhysical Layout

Mask Layout

Figure 1.1 A simplified flow diagram of the cell-based LSI design.

on-demand cell synthesis. Especially in the area of the on-demand cell synthesis, not only thequality of cells but also the runtime reduction is extremely important. The coupling between
on-demand cell synthesis and the technology mapping phase of logic synthesis can replace
the concept of a cell library, and it is possible to reduce silicon area by a tighter coupling
between cell generation and the automatic place&route system[11]. Based on these reasons, several commercial tools in automated standard-cell layout synthesis are widely usednow[12, 13].
These standard cells are usually optimized for area, delay, and power and these factors are
their basic characteristics used during logic synthesis and physical optimization. Therefore,
almost all of the conventional methods and commercial tools target to optimize these factors.
On the other hand, the recent progress in VLSI manufacturing technology and shrinking feature size lead to some new issues such as Design For Manufacturability (DFM). DFM is
generally defined as a set of techniques to modify the design of circuits in order to makethem more manufacturable, i.e., to improve their yield. Due to very high costs associatedwith the manufacturability of deep sub-micron integrated circuits, even a small yield improvement can be extremely significant. Recently, a lot of papers related to VLSI yield improvement have been published[14, 15, 16, 17, 18]. Figure 1.2 illustrates the conceptual flow
diagram of the yield-aware cell-based LSI design. The yield-aware logic synthesis[17] introduces the manufacturability cost into logic synthesis and replaces the traditional area-driven
technology mapping with a new manufacturability-driven one. The yield-aware physicaloptimization[18] integrates manufacturability information into the timing-driven synthesis

3

Chapter 1 Introduction

Hardware Description

Yield-Aware
Logic Synthesis
Yield-Awareness
Small Area

Yield-Aware
Physical Optimization

High Speed
Low Power

Standard-Cell
Library

Yield-Aware
Mask Layout
Figure 1.2 A flow diagram of the yield-aware cell-based LSI design.

and place&route cost function. In these yield-aware design flows, the yield-awareness is also
a fundamental characteristic of the standard-cell layouts. Therefore, now the standard cells
have to be optimized not only for area, delay, and power, but also for yield.

1.2 Research Objectives and Thesis Organization
This thesis focuses on the optimization methods for standard-cell layouts. Figure 1.3 illustrates the proposed optimization methods in perspective. There are two main optimization
targets in this thesis, cell area optimization and yield optimization. Transistor placement andintra-cell routing methods for minimum-width cell layout synthesis via Boolean satisfiability
are presented in Chapter 2 through Chapter 4. Chapters 2 and 3 propose flat and hierarchical cell layout synthesis methods for dual CMOS cells, respectively. The extension of thesemethods to the minimum-width transistor placement which is applicable to non-dual cells is
explained in Chapter 4. Then, Chapter 5 shows a comprehensive cell layout synthesis method
for yield optimization. This method utilizes the above-mentioned minimum-width transistor
placement methods proposed for the cell area optimization, and routes the placements using
a comprehensive intra-cell router in a grid-based manner. Yield-optimal cell layouts are selected from the exhaustively-generated cell layouts. Chapter 6 describes a timing-aware celllayout de-compaction method for yield optimization. This method performs a de-compactionof a given cell layout in a grid-less manner under given timing constraints for further yield
optimization. A detailed explanation of each chapter is described as follows.

4

Chapter 1 Introduction

Cell Area Optimization

Chapter 2

Chapter 3

Transistor Placement
Applicable toNon-Dual Cells

Chapter 4

Comprehensive
Cell Layout Synthesis

Chapter 5Intra-cell routing
in a grid-basedmannerGrid-Based
Yield-Optimal
Cell Layout

only for Dual Cells

Hierarchical
Extension

Minimum-Width
Transistor Placement

Cell Layout Synthesis

Flat Synthesis

Yield Optimization
Timing-Aware Cell
Layout De-Compaction

Chapter 6
De-compaction
in a grid-lessmannerFigure 1.3 The proposed cell layout optimization methods in perspective.

Chapter 2 proposes a minimum-width layout synthesis method for dual CMOS cells via
Boolean Satisfiability (SAT). Cell layout synthesis problems, i.e., the transistor placement
and the intra-cell routing problems are first transformed into SAT problems by this formulation. The proposed method guarantees to generate minimum-width cells with routability
under our layout styles. This method places complementary P and N type transistors individually during transistor placement, and can generate smaller width layout compared withthe case of pairing the complementary P and N type transistors. Since this method still has
a restriction in gate connection style between P and N type transistors, it is applicable only
to dual CMOS cells. The extension of the transistor placement method for non-dual cells is
explained in Chapter 4.
Chapter 3 describes a hierarchical extension of the cell layout synthesis method proposed in
Chapter 2 for cell layout synthesis of large dual CMOS cells. This method partitions a given
transistor-level netlist into blocks considering the transistor connections by diﬀusions. Intrablock placement uses an exact transistor placement method which is proposed in Chapter 2,
and hierarchically generates the transistor placement with routability. Experimental results
show that the proposed method reduces the runtime for cell layout synthesis drastically withlittle width increase. The proposed method can be used as a quick layout generator in thearea of transistor-level circuit optimization such as on-demand cell layout synthesis.
Chapter 4 shows flat and hierarchical approaches for generating a minimum-width transistor placement of CMOS cells in presence of non-dual P and N type transistors, whereas thecell layout synthesis methods proposed in the previous chapters are only for dual cells. This
chapter targets the minimum-width transistor placement, and does not take the intra-cell routings into consideration. Our approaches are the first exact transistor placement method which
can be applied to CMOS cells with any types of structure, whereas almost all of the conven-Chapter 1 Introduction

5

tional exact transistor placement method is applicable only to dual CMOS cells. This chapter
also shows the generalization results of the single-row transistor placement method into themulti-row placement. The proposed exact minimum-width multi-row transistor placement
method uses more eﬃcient gate connection style and generates more area-eﬃcient transistor
placements than the conventional multi-row transistor placement method only for dual cells.
Chapter 5 introduces a cell layout synthesis technique to optimize the yield. The yield cost
metric used in the proposed method is the sensitivity to wiring faults due to spot defects. The
sensitivity to faults on intra-cell routings is modeled with consideration to the spot defects
size distribution and the end eﬀect of critical areas. Although the critical area used for thesensitivity calculation is extracted from the original layout patterns without lithographic simulation, the feasibility of the proposed sensitivity model to the practical lithography system is
discussed. The impact of the sensitivity reduction on the yield improvement is also discussed
in this chapter. The minimum-width cell layout of CMOS logic cells are comprehensively
generated using the transistor placement method proposed in Chapter 2 and the comprehensive intra-cell routing method proposed in this chapter. The yield optimal layouts are selectedfrom the exhaustively-generated layouts by using the proposed sensitivity to wiring faults asa cost function.
Chapter 6 proposes a timing-aware cell layout de-compaction method for yield optimization using Linear Programming (LP). The proposed method performs a de-compaction of theoriginal layout in order to improve the yield by minimizing the critical area inside the cell.
This yield improvement procedure is executed under given timing constraints. To formulate
the timing constraints into LP, a new accurate linear delay model which approximates thediﬀerence from the original delay is proposed. The eﬀectiveness of the proposed method
for OPC mask data volume reduction is also shown in this chapter. This timing-aware decompaction framework is extended to the redundant contact insertion adjacent to the original
single contacts to minimize the yield loss due to contact failure. To take the parametricyield into account, the proposed method is also extended to the gate layout pattern regularity enhancement to reduce the systematic variation of the gate critical dimensions. Using
the proposed timing-aware yield enhancement method, we can explore the trade-oﬀ between
yield and performance, and can pick up the yield/performance variants from the trade-oﬀ
curve.
Finally, Chapter 7 gives conclusions of this thesis.

Chapter 2
Exact Minimum-Width Cell Layout
Synthesis for Dual CMOS Cells
2.1 Introduction
This chapter targets to minimize the area of the dual CMOS cells and proposes a minimumwidth layout synthesis method which is applicable only to dual CMOS cells. The proposed
method generates minimum-width routable cell layouts via Boolean Satisfiability (SAT). In
the area of the automated cell layout synthesis, several exact cell layout synthesis methods
have been proposed. Gupta and Hayes proposed the CMOS cell width minimization via Integer Linear Programming (ILP)[19, 20, 21]. This method solves the width minimization of
two dimensional transistor placement exactly. However, this method treats complementary P
and N type transistors as a pair and aligns only these transistors vertically. There are somecases that the cell width becomes smaller when complementary transistors are not aligned
vertically. Maziasz and Hayes proposed the exact algorithm for width and height minimization of CMOS cells[22]. This method minimizes both width and height considering intra-cellroutability. However, this method also treats complementary transistors as a pair and thelayout styles of this method have some diﬀerence from the practical cell layout styles. For
example, it does not use horizontal polysilicon for routing.
We propose a minimum-width cell layout synthesis method for dual CMOS cells via SAT.
Devadas has transformed various layout problems such as channel routing and partitioning
into SAT problems[23]. However, the transistor placement and intra-cell routing problems
could not be solved. The formulation of cell layout synthesis problems, i.e., transistor placement and intra-cell routing problems, need some specific constraints such as diﬀusion sharing
and complex routing patterns. We define the practical styles for cell layout to formulate these
constraints into SAT, and cell layout synthesis problems are first transformed into SAT prob6

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

7lems by our formulation.
The proposed method generates the minimum-width transistor placement with routability
under our layout styles via SAT. The proposed method places complementary P and N typetransistors individually during transistor placement, and can generate smaller width layout
than the conventional exact methods explained above which treats the complementary P and
N type transistors as a pair. Furthermore, we define more practical layout styles than theprevious exact cell layout synthesis method, so that we can handle the multiple-sized transistors and the horizontal polysilicon. Our method does not minimize the cell height since
we focus on the standard-cell layout synthesis whose height is usually fixed. Our SAT-based
cell layout synthesis method generates the minimum-width placements in much shorter runtime than the 0-1 ILP-based transistor placement method, and also generates cell layouts
in shorter runtime than the commercial cell generation tool. Therefore, it can significantly
shorten the time-to-market of a cell library, and can also be used for many other applications
such as on-demand cell synthesis, since it generates a layout quickly from a netlist, not froma pre-defined symbolic layout.
In Section 2.2, our layout styles are defined. The formulations of transistor placement andintra-cell routing are explained in Section 2.3 and Section 2.4, respectively. Experimental
results are shown in Section 2.5, and finally Section 2.6 summarizes this chapter.

2.2 Layout Styles
Our layout styles are described in Table 2.1 and illustrated in Figure 2.1. By using thesestyles, the cell layout synthesis problems are eﬃciently transformed into SAT problems
and a SAT solver can search for a solution quickly. The general styles for one dimensional width minimization of static dual CMOS logic cells were proposed by Uehara andvanCleemput[24]. Our layout style No. 1 through 5 are for the transistor placement essentially based on Uehara’s styles. However, our layout styles have some diﬀerences from theirs.
The first diﬀerence is the style No. 3. The complementary transistors have to be aligned vertically in Uehara’s style. In contrast, transistors which have the same gate input signals canbe aligned vertically in our layout style. As explained in Section 2.1, there are some casesthat the generated layout has smaller width using our layout style. Moreover, our method canhandle the cell circuits with non-complementary topologies in P/N type transistor networks
if the circuit has no P and N type transistors which can not be paired by the common gate
input signal. The second diﬀerence is that our method can take multiple-sized transistors as

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

8

Table 2.1 Our layout styles of the proposed SAT-based cell layout synthesis for dual CMOS cells.

1. Static dual CMOS logic circuits.
2. Transistors are drawn up in two horizontal rows. The upper row is for P type transistors and the bottom row is for N type transistors.
3. Two transistors which have the same gate input signals are vertically aligned.
4. Two transistors which have the same diﬀusion terminals are placed in the neighboring columns to share their diﬀusions.
5. The bottom of the P diﬀusions and the top of the N diﬀusions are aligned to GRegion.
6. The intra-cell routing uses polysilicon and first metal layers.
7. All nets which connect diﬀusion terminals of P type transistors are in P-region.
8. All nets which connect diﬀusion terminals of N type transistors are in N-region.
9. All nets which connect gate terminals are in G-, Top- or Bottom-regions.
10. Gate terminals are connected by the polysilicon layer in Top- or Bottom-region, andby the first metal layer in G-region.
11. The same signals in P-region and N-region are connected by the vertical first metal
through G-region at the top of N-region and the bottom of P-region.
12. Vertical first metals and the gate terminals are connected by the horizontal firstmetals in G-region.
13. VDD are connected from the top of P-diﬀusion through Top-region by the verticalfirst metal.
14. GND are connected from the bottom of N-diﬀusion through Bottom-region by thevertical first metal.
15. Single contact is assumed to be enough to connect between metal and diﬀusion orpolysilicon.
16. No dogleg is used.

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

Width

9

VDD

Polysilicon

Top-Region
VDD-net

P-FET

P-Region

P-net

V-net

G-net
G-Region

Metal1

N-FET

N-net

N-Region

GND-netDiffusion sharing

Diffusion gap

Bottom-Region
GND

Figure 2.1 An illustration of the layout styles of the proposed SAT-based cell layout synthesis fordual CMOS cells.

an input, so that it can deal with more practical problems, while almost all previous optimalcell layout synthesis methods assumed the uniform-sized transistors. To treat multiple-sizedtransistors, the bottom of the P-diﬀusions and the top of the N-diﬀusions are aligned to the
G-region, as described by No. 5 in Table 2.1 and illustrated in Figure 2.1.
The layout styles No. 6 through 16 in Table 2.1 are for intra-cell routing. These styles are
based on Maziasz’s styles[22]. Five routing regions are defined in the cell area as defined in
Maziasz’s styles. P- and N-regions are over the each diﬀusion, G-region is between the Pand N-regions, Top-region is above the P-region and Bottom-region is below the N-region,
as shown in Figure 2.1. Our method can deal with outer channel polysilicon routing, i.e.,the connection which runs above P diﬀusions and below N diﬀusions as described by No. 9
and 10 in Table 2.1. By using outer channel routing, we can avoid the second metal layers
for intra-cell routing in many cases. Therefore, our routing styles will be widely accepted inpractical applications.

2.3 Transistor Placement Formulation
In this section, we explain the SAT constraints for transistor placement. Given N P and N N
type transistors, we have to place these 2N transistors in the minimum area. This problem canChapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

Used Column

10

Unused Column

same signals(vertical GATE)

000 001 010 011 100 101 110 111
P-MOS : p3 p2 p 1
N-MOS : n3 n2 n1

same signals
different signals(diffusion sharing) (diffusion gap)

Figure 2.2 A SAT formulation of the transistor placement for dual CMOS cells.

be transformed into the problem that places all transistors using minimum number of columns
as illustrated in Figure 2.2. The P type transistors are aligned in the upper row and the N typetransistors are in the bottom (No. 2 in Table 2.1). The P and N type transistors which areplaced in the same column must have the same gate input signals (No. 3 in Table 2.1). The
neighboring transistors must face the diﬀusions which belong to the same signal each otherto share their diﬀusions (No. 4 in Table 2.1). The empty columns result in the diﬀusion gaps
in the final layouts. We transform these constraints into Boolean constraints.
Each transistor has P variables to identify its placement where P = log2 W and W is thenumber of the columns, and one variable to identify whether the source/drain terminals areflipped or not. X indicates a minimum integer which is equal to or larger than X. Thus,
the total number of variables needed for this formulation is 2N × (log2 W + 1). Here, we
describe the Boolean constraints.
Transistor overlap constraints: N type transistors must not overlap in the same column,
which is expressed by the following logic equationni1 ⊕ n j1 ∨ ni2 ⊕ n j2 ∨ · · · ∨ niP ⊕ n jP = 1(2.1)

where ni1 , ni2 , . . . , niP are the variables for placement of an N type transistor i, and ⊕ is the
exclusive-or Boolean operator. The same logic equation must hold for P type transistors.
Unused column constraints: If W < 2P , the columns with the top 2P − W distinct bit
vectors of length P, correspond to unused columns as illustrated in Figure 2.2. No N typetransistors can be placed in these unused columns. The following logic equation expresses
this constraint for N type transistors.
ni1 ⊕ u1 ∨ ni2 ⊕ u2 ∨ · · · ∨ niP ⊕ uP = 1(2.2)

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

11

where uk1 , uk2 , . . . , ukP are constant bit vectors which indicate the unused column k. The same
logic equation must hold for P type transistors.
Vertical gate constraints: The P and N type transistors which are placed in the same
column must have the same gate input signals. Assume Gip is the group of P type transistors
which have the same gate input signals as that of an N type transistor i, this constraint isexpressed as follows.
(ni1 ⊕ p j1 ∨ ni2 ⊕ p j2 ∨ · · · ∨ niP ⊕ p jP ) = 1(2.3)

j∈G ip

Neighboring Transistor constraints: The transistors which face the diﬀusions which belong to the diﬀerent signals each other can not be in the neighboring columns. Assume fni isthe variable which determines the flip of an N type transistor i, and Cn (i, k) takes the valueof 1 if an N type transistor i is in the column k, the following logic equation expresses thisconstraint for N type transistors.
GAPn (i, j) ∧W−2Cn (i, k) ∧ Cn ( j, k + 1) = 0

(2.4)

k=0

Here, GAPn (i, j) takes the value of 1 if an N type transistor i can not share its diﬀusion with
an N type transistor j placed to its immediate right, otherwise 0. The same logic equationmust holds for P type transistors.
These Boolean constraints express all the possible placement in W columns under our
layout styles. These constraints are expressed in Conjunctive Normal Form (CNF) to besolved by the CNF-SAT solver. If there is no satisfiable assignment using W columns, it
is guaranteed that there is no possible placement of width W. Therefore, we can find theminimum-width placement using a procedure described below.
1. For a given transistor netlist, enumerate the number of transistors. The initial numberof column W is set to the number of N type transistors (=#P-FETs).
2. Search for a satisfiable assignment for the Boolean constraints constructed for W
columns. If a satisfiable assignment is found, these transistors can be placed in W
columns and this procedure terminates. Otherwise, go to step 3.
3. W = W + 1. Go to step 2 again.

12

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

10

Top-Region

10
for P-Net
P Net 01

p2 p1

P-Region00
00 for G-Net
000 001 010 011 100 101 110 111 01
00

G-Regionfor V-Net

for N-Net 01

n2 n1

g2 g 1v3 v2 v 1

N-Region

10
11

Bottom-Region

Figure 2.3 A SAT formulation of the intra-cell routing.

2.4 Intra-Cell Routing Formulation
We next explain the SAT constraints of the intra-cell routing in this section. After a transistor placement is generated using the formulation explained in Section 2.3, its intra-cellroutability is checked using the constraints explained in this section. Our styles of the intracell routing are listed by No. 6 through 16 in Table 2.1. We defined five types of net listed
below as illustrated in Figure 2.1.
N-net The net which connects the diﬀusion terminals of N type transistors.
P-net The net which connects the diﬀusion terminals of P type transistors.
G-net The net which connects the gate terminals.
V-net The net which connects the diﬀusion terminals of P and N type transistors, and thegate terminals.
VDD/GND-net The net which connects the VDD/GND signals to VDD/GND rail whichruns top/bottom of cell area.
We also defined the region where each type of net can be placed as described by No. 7 through14 in Table 2.1. Bit vectors which correspond to the row or column numbers are assigned
to each region as illustrated in Figure 2.3. The routing grids are also defined as illustrated
in Figure 2.3. We use the columns which are shifted by a half column in the G-region. The

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

13

number of rows of the N-region (P-region) is determined by the maximum width of N typetransistors (P type transistors) and the design rules since the grid size is determined by theminimum width and spacing rules of metal or polysilicon and some other design rules. The
numbers of rows of the Top-region and the Bottom-region are both fixed to 1. Therefore, thenumber of rows of the G-region Wg is given by the following equation
Wg = Hcell − W p − Wn − 2(2.5)

where Hcell is the total number of rows of each cell, which is fixed for all cells so that theheight of all cells are uniform, and W p and Wn are the number of rows of P and N region,
respectively.
Assume that Pn , P p , Pg , and Pv are the number of the Boolean variables for each type of net,
they are expressed as Pn = log2 Wn , P p = log2 W p , Pg = log2 (Wg + 2), Pv = log2 Wv 
where Wn , W p , and Wg are the number of the rows of each region, and Wv is the number ofthe columns of the G-region. G-nets can be placed in Wg + 2 rows since they can be placedin the Top- and Bottom-region besides the G-region. The variables of the nets which belong
to more than two groups consist of the combination of each group’s variables. Therefore, thetotal number of variables Ptotal , used for the SAT formulation of intra-cell routing is expressedasPtotal =ai Pn + bi P p + ci Pg + di Pv

(2.6)

i∈net

where ai , bi , ci , and di are the variables which take the value of 1 if the net i belongs to eachgroup, otherwise 0. Here, we construct the Boolean constraints:
Net overlap constraints: We define the interval of an N-net i as In (i) = [lni , rni ], where lni
is the position of the leftmost terminal in the N-region which the net has to be connected to,
and rni is the position of the rightmost one. Two nets with intersecting intervals can not be
placed in the same row. For each net pair i and j, the logic equation describing this constraint
is as follows
ni1 ⊕ n j1 ∨ ni2 ⊕ n j2 ∨ . . . ∨ niPn ⊕ n jPn = 1(2.7)

i  j, In (i) ∩ In ( j)  φ
where ni1 , ni2 , · · · , niPn are the variables which correspond to the placement of an N-net i. The
same logic equation must hold for P-nets and G-nets. For V-nets, all pairs of nets must satisfy
the above logic equation. Therefore, the logic equation for V-nets is expressed as follows
vi1 ⊕ v j1 ∨ vi2 ⊕ v j2 ∨ . . . ∨ viPv ⊕ v jPv = 1, i  j(2.8)

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

14

where, vi1 , vi2 , · · · , viPv are the variables which correspond to the placement of a V-net i.
Unused row/column constraints: If Wv < 2Pv for V-nets, the columns with 2Pv −Wv distinct
bit vectors correspond to unused columns. No net can be placed in these unused columns.
The same case emerges when Wg + 2 < 2Pg for G-nets. Whereas for N(P)-nets, if minni < 2Pn(min pi < 2P p ) where minni (min pi ) is the minimum grid number of N(P) diﬀusions whose
signal has to be connected to an N(P)-net i, the N(P)-net i can not be placed in the columns
denoted by 2Pn − minni (2P p − min pi ) distinct bit vectors. This constraint enables us to routethe multiple-sized transistors. This constraint is expressed by the following logic equation.
ni1 ⊕ uk1 ∨ ni2 ⊕ uk2 ∨ · · · ∨ niPn ⊕ ukPn = 1(2.9)

The constant bit vector uk1 , uk2 , . . . , ukPn indicates the unused row/column. The same logic
equation must hold for P-nets, G-nets, and V-nets.
VDD/GND-net constraints: P-nets must not overlap the VDD-nets. We assume V is thegroup of the column numbers which has to be connected to VDD. If x ∈ V and x ∈ I p (i),a P-net i can not be placed in the top row of the minimum-width diﬀusion whose column
belongs to I p (i) and V. For N-nets, they must not overlap the GND-nets. We define the group
G whose members are the column numbers which has to be connected to GND. If x ∈ G andx ∈ In (i), an N-net i can not be placed in the bottom row of the minimum-width diﬀusion
whose column belongs to In (i) and G. These constraint is expressed as equation (2.9) where
uk1 , uk2 , . . . , ukPn (ukP p ) indicate the row where N(P)-nets can not be placed in.
V-net connection through the G-region constraints: If a V-net i is placed in the column
ci , there must be no horizontal net over the column c in the G-region so that the V-net cango through the G-region. Assume Hg is the group of horizontal nets in the G-region andIhg (i) = [li , ri] is the interval of the horizontal net where li (ri ) is the leftmost (rightmost)terminal or net in the G-region, this constraint is described as follows.
|X| = 0, X = {x | x ∈ Hg , ci ∈ Ihg (x)}(2.10)

V-net to gate connection constraints: If a V-net i must be connected to the gate terminals,
this V-net has to be connected to these terminals in the G-region by horizontal first metal
layer. Therefore, there has to be at least one empty row between this V-net and terminals in
the G-region. This constraint is described as follows using Hg and Ihg defined before.
|X| < Wg , X = {x | x ∈ Hg , Ihg (x) ∩ Ihg (i)  φ}

(2.11)

15

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

A transistor netlist
Count #NFET or #PFET
Initial #column = #N/P-FET

Generate a CNF P fortransistor placement#column++
CNF P satisfiable ?

noyes
Add a constraint
clause to CNF P

Generate a CNF R for
intra-cell routingno

CNF R satisfiable ?

yes

A minimum-width cell layout
Figure 2.4 Our SAT-based cell layout synthesis flow.

V-net to diﬀusion connection constraints: If a V-net i must be connected to the diﬀusion
terminals of N type transistors, this V-net is connected to these diﬀusion terminals in the top
row of the N-region by horizontal first metal layer. Therefore, there has to be no other net
placed between such V-nets and terminals in the top row of the N-region. Assume Hn is thegroup of horizontal nets which are placed in the top row of the N-region and Ihn ( j) = [l j , r j ]is the interval of the horizontal net where l j (r j ) is the leftmost (rightmost) terminal or net in
the N-region, this constraint is described as follows.
|X| = 0, X = {x | x ∈ Hn , Ihn (x) ∩ Ihn (i)  φ}

(2.12)In the case of P type transistors, this V-net and terminals must be connected to in the bottom
row of the P-region and the same logic equation must hold for P type transistors.
The SAT formulation which consists of these constraints allows us to determine whether
the placement is routable or not. To find a routable placement, we iterate the generation ofplacements and satisfiability checks. If a placement is proved to be unroutable, we add a newclause which suppresses the previous placement to CNF for transistor placement to generatea new placement. These clauses are called constraint clause. The flow of our SAT-based celllayout synthesis is illustrated in Figure 2.4.

16

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

Table 2.2 The problem size comparison results of the transistor placement for dual cells between ILP
and SAT formulations.

Problem Size

CircuitILP

name#tr. #col.

ao222

14

ao44

#var.

SAT

#ineq. #var.

#cla.

8 1054

1926

56

1624

20

11 2767

5450

100

5360

aoi211

8

4

394

24

244

fad1

28

15 7011 14082

140 47404

gen3

16

10 1509

2836

80

3342

maj3

12

6

699

1214

48

1100

mux2

12

8

699

1240

48

1260

nand2

4

2

39

56

8

18

nand3

6

3

114

178

18

94

xnor2

10

6

432

716

40

790

241

2.5 Experimental Results
The formulations explained in Section 2.3 and Section 2.4 and the flow illustrated in Figure 2.4 enable us to generate a minimum-width routable cell layout from a netlist via Boolean
satisfiability. To test the eﬀectiveness of our SAT-based cell layout synthesis method, we
compare it with a 0-1 ILP-based transistor placement and a commercial cell generation tool.

2.5.1 Comparison with the 0-1 ILP Formulation
We conducted the runtime comparison with 0-1 ILP formulation in transistor placement
stage. To conduct the experiment, we also transformed the transistor placement problems
into the 0-1 ILP problems. Our formulation of the 0-1 ILP is based on the Gupta and Hayes’
formulation[20]. The diﬀerences from [20] are that we assume only one dimensional placement and P and N type transistors with the same gate input signals can be aligned vertically,
while their formulation assumed two dimensional placement and only complementary P and
N type transistors are aligned vertically.
We used the CNF-SAT solver Chaﬀ [25], the 0-1 ILP solver OPBDP[26], and the generic
ILP solver CPLEX[27] for the experiments. The Chaﬀ and OPBDP experiments were con-

17

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

Table 2.3 The runtime comparison results of the transistor placement for dual cells between ILP and
SAT formulations.

Runtime (sec.)

Circuit

ILP

SAT

name

#tr. #col. OPBDP

CPLEX

OPBDP

CPLEX

Chaﬀ

ao222

14

8

0.59

134.17

1.30

14.17

0.15

ao44

20

11

1551.45

>3600

20.36

>3600

0.66

aoi211

8

4

0.07

0.04

0.03

0.06

0.01

fad1

28

15

>3600

>3600

>3600

gen3

16

10

9.95 2872.81

11.6 2150.69

1.67

maj3

12

6

0.30

15.42

0.19

2.01

0.06

mux2

12

8

0.39

37.74

0.92

20.12

0.23

nand2

4

2

0.03

∼0

0.05

0.02

0.03

nand3

6

3

0.04

0.02

0.03

0.03

0.01

xnor2

10

6

0.17

1.56

0.30

1.91

0.08

Total Ratio——>33.04>71.18>17.72>68.211.00>3600 201.05

ducted on a 750MHz UltraSPARC-III workstation with 2GB of RAM. The CPLEX experiments were done on a Pentium-III 1GHz with 2GB of RAM. We used default settings forall of them. A time-out limit of 3,600 seconds was used for each run. We experimented the
ILP formulation based on the Gupta and Hayes’ formulation and the ILP formulation simply
transformed from CNF for the SAT solver, as an input file for the two ILP solvers. Tables 2.2
and 2.3 list the results of solving the transistor placement problems by SAT and ILP solvers.
Although both tables contain only 10 circuits, we tested 30 static dual CMOS logic circuits
in a standard-cell library. The data in the row of Total Ratio in Table 2.3 means the ratio of
the total runtime for the 30 circuits. For each circuit, Table 2.2 indicates the number of transistors, the number of columns after placement, the problem size for the ILP as well as for
the SAT formulations (number of ILP variables and inequalities are expressed as #var. and#ineq.; CNF variables and clauses are as #var. and #cla.). The problem size of SAT formulation is the size of the problem which has a satisfiable assignment first. Table 2.3 shows the
OPBDP and CPLEX runtimes using the ILP formulation, and OPBDP, CPLEX, and Chaﬀ
runtimes using the SAT formulation as the input.
Compared with the two ILP solvers, the SAT solver Chaﬀ has shorter runtimes in mostChapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

18

cases. Moreover, the ILP solvers can not solve some large circuits in one hour whereas Chaﬀ
can in minutes. The total runtime of the ILP solvers are about 17 to 70 times longer thanthe SAT solver. These results clearly show that the SAT formulation and the SAT solver are
more suitable for solving the transistor placement problems.
The layouts generated by our method are equal to or smaller than the one dimensionallayout generated by Gupta and Hayes’ method[19] which treats complementary P and N typetransistors as a pair. For example, the width of the full adder “fad1” in Table 2.3 is 15 using
our method whereas the minimum width of the one dimensional layout of the full adderdescribed in [19] is 16.

2.5.2 Comparison with the Commercial Cell Generation Tool
We also compared our cell generation method with the commercial cell generation tool
ProGenesis[13]. The experiments were conducted on a 750MHz UltraSPARC-III workstation with 2GB of RAM. Tables 2.4 and 2.3 list the results of generating the 30 static dual
CMOS logic circuits in a standard-cell library by our method and ProGenesis. The height of
all circuits is fixed to 10 rows in this experiment. Table 2.4 shows the number of transistors,
the SAT problem size of the intra-cell routing, the width of cells generated by the ProGenesis
and our method. Table 2.5 shows the runtime spent on generating a routable cell layout froma netlist. In the column of Resultant Width in Table 2.4, we assumed the 0.35μm process technology. The layouts generated by ProGenesis and our method are both design rule correct.
The column width for ProGenesis lists the width of the generated layout after compaction
and the asterisk in this column means that it uses second metal layers to route these circuits.
The column #col. for ProGenesis lists the number of columns of the generated symboliclayouts before compaction. The column width for the proposed method lists the width of thegenerated layout by the proposed method without compaction. The column #col. shows thenumber of columns needed for each circuit to complete the intra-cell routing using our layoutstyle.
One column is added to the minimum-width placement of ao33, ao44, oa33, and oa44 tocomplete the intra-cell routing of each circuit, and the width of these cells in column are
1 column larger than the commercial tool as shown in tables 2.2 and 2.4. Because of therouting restrictions of out layout styles, the numbers of columns of these cells are larger thanthose generated by ProGenesis. Although the number of columns of cell mux2 generated by
the proposed method is also larger, this reason is not the routing restriction but the transistor

19

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

Table 2.4 The width comparison results of the cell layout synthesis between the commercial cell
generation tool and the proposed method.
Circuit
name

#tr.

ao222
ao33
ao44
aoi21
aoi211
buf1
eno
eor
fad1
gen2
gen3
maj3
mux2
nand2
nand22
nand3
nand4
nand44
nor2
nor22
nor3
nor4
nor44
oa222
oa33
oa44
oai21
oai211
xnor2
xor2
Total

14
16
20
6
8
4
10
10
28
12
16
12
12
4
6
6
8
10
4
6
6
8
10
14
16
20
6
8
10
10
—

SAT
Problem Size
#var. #cla.
14
20
20
5
7
4
8
8
36
14
20
14
22
4
6
4
4
8
4
6
5
5
8
14
17
20
7
7
14
14
—

337
1102
1420
14
16
49
144
144
6169
295
520
215
900
4
81
7
7
150
4
81
8
8
150
335
1095
1506
18
18
229
219
—

Resultant Width
ProGenesis
width (μm)#col.

Proposedwidth (μm)

11.85
13.95
15.50
5.40
6.45
3.90
8.40
8.40
26.05*
11.00*
21.40*
10.80
10.60
3.70
5.80
5.40
6.90
8.30
3.90
5.40
5.10
8.10
8.10
12.00
13.25
15.70
5.40
6.55
8.80
8.65
285.2 (1.00)

13.20
15.90
18.90
5.40
6.90
4.20
8.40
8.40
24.00
11.70
16.20
10.20
13.20
3.90
5.70
5.40
6.90
8.70
3.90
5.70
5.40
6.90
8.70
13.20
15.90
18.90
5.40
6.90
10.20
10.20
298.5 (1.05)

8
9
11
3
4
2
5
5
15
7
10
6
6
2
3
3
4
5
2
3
3
4
5
8
9
11
3
4
6
6
172 (1.00)

#col.

8
10
12
3
4
2
5
5
15
7
10
6
8
2
3
3
4
5
2
3
3
4
5
8
10
12
3
4
6
6
178 (1.03)

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

20

Table 2.5 The runtime comparison results of the cell layout synthesis between the commercial cell
generation tool and the proposed method.
Circuit
name

#tr.

ao222
ao33
ao44
aoi21
aoi211
buf1
eno
eor
fad1
gen2
gen3
maj3
mux2
nand2
nand22
nand3
nand4
nand44
nor2
nor22
nor3
nor4
nor44
oa222
oa33
oa44
oai21
oai211
xnor2
xor2
Total

14
16
20
6
8
4
10
10
28
12
16
12
12
4
6
6
8
10
4
6
6
8
10
14
16
20
6
8
10
10
—

SAT
Problem Size
#var. #cla.
14
20
20
5
7
4
8
8
36
14
20
14
22
4
6
4
4
8
4
6
5
5
8
14
17
20
7
7
14
14
—

337
1102
1420
14
16
49
144
144
6169
295
520
215
900
4
81
7
7
150
4
81
8
8
150
335
1095
1506
18
18
229
219
—

Runtime (sec.)
ProGenesis

Proposed

144.96185.07291.79
28.51
52.06
18.67
77.67
63.54
509.27141.17386.69
87.93
77.28
16.56
27.02
25.91
33.84
76.76
16.73
30.77
26.53
40.98
62.03
167.45204.5295.87
30.03
54.60
55.43
59.00
3288.62 (1.00)

1.06
392.26637.26
0.04
0.02
0.06
0.04
0.06
305.76
0.16
2.20
0.20
6.42
0.04
0.04
0.04
0.04
0.06
0.05
0.05
0.06
0.07
0.07
1.07
443.94116.41
0.04
0.05
0.09
0.12
1907.78 (0.58)

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

21

Figure 2.5 The example result of fad1 cell layout generated by the proposed SAT-based cell layout
synthesis method for dual CMOS cells.

placement restriction. The P and N type transistors which are placed in the same column
must have the same gate input signals in the proposed method, whereas ProGenesis does
not have such restriction. Because of this restriction, the width of the cell mux2 which includes transmission gates becomes larger than ProGenesis. The width increase in terms ofthe number of columns is about 3% for total of 30 circuits used in this experiment.
ProGenesis generates smaller width layouts for 18 circuits after layout compaction, since
it can use the bending gate in the G-region and the smaller width diﬀusion if it has no contact on it during compaction, whereas the proposed method does not include the compaction.
However, it uses the second metal layers to complete the intra-cell routing for fad1, gen2,
gen3 and the width of fad1, gen3, maj3, nand22, nor4 are larger than our method. The runtimes of our method are smaller than ProGenesis for almost all cases as shown in Table 2.5.
The proposed method generates all these 30 circuits in total 58% runtime with only 5% area
increase compared with ProGenesis. These results show that our cell layout styles defined for
the SAT formulation is practical enough to generate the layout of dual CMOS cells quickly
with a little area overhead. The snapshot of fad1 layout generated by the proposed method is
illustrated in Figure 2.5 for example.

Chapter 2 Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells

22

2.6 Summary
We proposed a minimum-width cell layout synthesis method for dual CMOS cells via
Boolean Satisfiability (SAT). Cell layout synthesis problems are first transformed into SAT
problems by our formulation. We presented that the SAT formulation is more suitable for thetransistor placement by comparing the runtime of the SAT and the 0-1 ILP formulations of
the transistor placement problems. We also presented that the width of placements generated
by our method are smaller than that of the conventional exact transistor placement methodby using our layout styles. The proposed method generates the cell layouts of 30 static dual
CMOS logic circuits in 58% runtime with only 5% area increase compared with the commercial cell generation tool ProGenesis with cell layout compaction. These results showedthat our cell layout styles defined for the SAT formulation is practical enough to generate thelayout of dual CMOS cells quickly with a little area overhead. We can conclude from theseresults that our method can significantly shorten time-to-market of a cell library and can also
be useful for many other applications such as on-demand cell layout synthesis. Since thismethod still has a restriction in gate connection style between P and N type transistors, it isapplicable only to dual CMOS cells. The extension of the transistor placement method to
non-dual cells is explained in Chapter 4.

Chapter 3
Hierarchical Extension for Large Cell
Layout Synthesis
3.1 Introduction
This chapter describes a hierarchical extension of the layout synthesis method explained in
Chapter 2 for layout synthesis of large dual CMOS cells. The proposed method partitions agiven transistor-level netlist into blocks considering the transistor connections by diﬀusions
and places all transistors hierarchically. Intra-block placement uses an exact transistor placement method which is proposed in Chapter 2. During intra-block transistor placement, a
new optimization cost is introduced to maximize the number of the connections by diﬀusion sharing between logic blocks in the subsequent inter-block placement step. This new
cost function is a key to realize a hierarchical transistor placement and the drastic runtime
reduction with little increase in cell width. Intra-cell routability of the generated transistor
placement is also checked in the same manner as in Chapter 2 in order to generate a routable
cell layout.
The layout styles of the hierarchical cell layout synthesis method are defined in Section 3.2.
Section 3.3 and Section 3.4 explain the formulation of the hierarchical transistor placement
and intra-cell routings. In Section 3.6, experimental results of the proposed cell layout synthesis are presented. Finally, Section 3.7 summarizes this chapter.

3.2 Layout Styles
Our cell layout styles for the hierarchical cell layout synthesis are described in Table 3.1
and illustrated in Figure 3.1. These styles are basically same as the styles used in Chapter 2.
Particularly the layout styles No. 5 and 10 in Table 3.1, the alignment style of the multiple23

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

24

Table 3.1 Our layout styles of the hierarchical SAT-based cell layout synthesis for dual CMOS cells.

1. Static dual CMOS logic circuits.
2. Transistors are drawn up in two horizontal rows. The upper row is for P type transistors and the bottom row is for N type transistors.
3. Two transistors which have the same gate input signals are vertically aligned.
4. Two transistors which have the same diﬀusion terminals are placed in the neighboring columns to share their diﬀusions.
5. The top of the P diﬀusions are aligned to Top-Region and the bottom of the N
diﬀusions are aligned to Bottom-Region.
6. The intra-cell routing uses polysilicon and first metal layers.
7. All nets which connect diﬀusion terminals of P type transistors are in P-region.
8. All nets which connect diﬀusion terminals of N type transistors are in N-region.
9. All nets which connect GATE terminals are in G-, Top- or Bottom-regions.
10. Gate terminals are connected by the polysilicon layer in Top- or Bottom-region, andby the first metal or polysilicon layer in G-region.
11. The same signals in P-region and N-region are connected by the vertical first metal
through G-region at the top of N-region and the bottom of P-region.
12. Vertical first metals and the GATE terminals are connected by the horizontal firstmetals in G-region.
13. VDD are connected from the top of P-diﬀusion through Top-region by the verticalfirst metal.
14. GND are connected from the bottom of N-diﬀusion through Bottom-region by thevertical first metal.
15. Single contact is assumed to be enough to connect between metal and diﬀusion orpolysilicon.
16. No dogleg is used.

25

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis
VDD
Polysilicon

Top-region

P-region
P-FET

Metal1

G-region

N-region
N-FET

Diffusion sharing

Diffusion gap

Bottom-region
GND

Figure 3.1 An illustration of the layout styles of the hierarchical SAT-based cell layout synthesis fordual CMOS cells.

sized P and N type transistors and the usage of polysilicon layer inside the G-region are
diﬀerent from the styles in Chapter 2. Although these styles are changed to improve theintra-cell routability, they do not have a significant eﬀect on the results of the cell layout
synthesis. Under these layout styles, the proposed method synthesizes the layout of the dual
CMOS logic cells hierarchically.

3.3 Hierarchical Transistor Placement
In this section, we explain the formulation of the hierarchical transistor placement. The
proposed hierarchical transistor placement method has three steps, partitioning, intra-block
placement, and inter-block placement. The proposed method partitions a given transistorlevel netlist into blocks considering the transistor connections by diﬀusions, then place alltransistors inside each block in minimum width via Boolean satisfiability. After all the intrablock transistor placements are finished, all the blocks are placed in minimum-width in thesame manner as the intra-block transistor placement. Detailed explanation of each step isdescribed as follows.

26

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

VDD
D0
Y

S0

D1
GND
Figure 3.2 Schematic of 2-input multiplexer and its logic block partitioning.

3.3.1 Partitioning into Logic Blocks
Our approach first partitions the given circuit into logic blocks. Conventionally, several
hierarchical layout synthesis methods for runtime reduction have been proposed[28, 29]. The
proposed method partitions a given transistor network into logic blocks in the same manneras these methods[28, 29]. A logic block consists of transistors that are connected together
by their diﬀusions except power and ground. An example of the partitioning result of 2input multiplexer is shown in Figure 3.2. Two clocked inverters whose outputs are connected
are identified as one logic block using our partitioning procedure. Since it is important tomaximize the diﬀusion sharing between transistors in order to minimize the placement width,
the partitioning procedure based on the diﬀusion connections is not expected to worse theresults severely.

3.3.2 Intra-Block Transistor Placement Formulation
Next, we explain the intra-block transistor placement procedure. The proposed method
uses Boolean satisfiability to generate the minimum-width intra-block transistor placement.
In this chapter, we use Pseudo-Boolean formulation[30] to formulate the hierarchical celllayout synthesis. Pseudo-Boolean formulation can handle Conjunctive Normal Form (CNF),

27

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

Cp(0,2) = 1
Column No. 0

1same signals

2

3

4

5

2

0

3

1

4

PMOS

4

1

0

3

2

NMOS

different signals
same signals Cn(2,5) = 1(diffusion gap) (diffusion sharing)
Figure 3.3 The problem definition of the intra-block transistor placement.

Pseudo-Boolean Form (PBF), and optimization constraints[30]. PBF constraints are expressed by linear inequalities of Boolean variables. Since this intra-block transistor placement formulation requires an optimization constraint, we select this formulation.
When N N type transistors and N P type transistors are given, this problem is defined as
the problem to place these 2N transistors in the minimum area. This problem can be transformed into the problem that places all transistors using the minimum number of columns
as illustrated in Figure 3.3. As explained in Section 3.2, the P type transistors are aligned in
the upper row and the N type transistors are in the bottom. Two neighboring transistors must
face the diﬀusions which belong to the same signals each other to connect their source ordrain by diﬀusion sharing. The empty columns result in the diﬀusion gaps in the final layout.
These transistor placement constraints are same as those explained in Chapter 2. Under theseplacement constraints, we search for a possible placement with minimum number of columnsof the placement area.
When the intra-block transistor placement is formulated, a new optimization cost is introduced to maximize the number of the connections by diﬀusion sharing between logic blocks
in the subsequent inter-block placement step. The diﬀusions which can be shared between
logic blocks are only power and ground in our partitioning procedure. For maximizing thenumber of the connections by diﬀusion sharing in the inter-block placement step, it is betterto place the diﬀusions which belong to VDD and GND on the edge of the placement of eachblock as illustrated in Figure 3.4. Therefore, we introduce new variables El and Er , and a new
optimization function into the formulation of transistor placement to maximize the numberof the connections by diﬀusion sharing. E l (E r ) takes the value of 1 unless the diﬀusions of28

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

Y

A
B
GND

(a)

GND

Y

Can be shared

VDD

VDD
Y

Er = 0Y

Y
GND

B

Er = 1 E l = 1
VDDA

El = 1Y

VDD(b)Figure 3.4 Additional variables introduced to maximize the number of the connections by diﬀusion
sharing between logic blocks.

Table 3.2 The variables used for the intra-block transistor placement formulation.

namenumbercondition which makes the value 1

Cn (i, k)

N ×W

N-FET i is placed in the column k.

C p (i, k)

N ×W

P-FET i is placed in the column k.

F n (i)N

N-FET i is flipped.

F p (i)N

P-FET i is flipped.

E r , El2

The diﬀusions on the right/left edge of the intra-block
placement do not belong to VDD and GND.

the left (right) edge are assigned to the pair of VDD and GND as illustrated in Figure 3.4.
We explain the details of the placement formulation in the following paragraph.
In our formulation of intra-block transistor placement, W + 1 Boolean variables are introduced for each transistor to identify its location and whether it is flipped or not, where W
is the number of the columns of the placement area. In addition, 2 Boolean variables are
required to identify whether the diﬀusions of left and right edges of the intra-block placement is a pair of VDD and GND signals or not. All variables required for this formulation
are listed in Table 3.2. Table 3.2 shows the names of the variable type, the numbers of eachtype of variables, and the conditions when each type of variables takes the value of 1. Some
example cases of such conditions are also illustrated in Figure 3.3. These variables are used
to formulate the transistor placement constraints as Conjunctive Normal Form (CNF) and
Pseudo-Boolean Form (PBF) constraints. We formulate the following Boolean constraints
which express all the possible transistor placements in W columns under our layout style.

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

29

Objective function: For maximizing the number of the connections by diﬀusion sharing
in the inter-block placement step, it is better to place diﬀusions that belong to VDD and GND
on the edge of the placement of each block. Therefore, we introduce the objective function
as follows.
Minimize : E r + E l(3.1)

Transistor overlap constraint: N (P) type transistors must not overlap in the same column.
This constraint is expressed by the following PBF constraints.
N−1

Cn (i, k) ≤ 1,

0≤k<W

(3.2)

C p (i, k) ≤ 1,

0≤k<W

(3.3)

i=0
N−1

i=0

Transistor instantiation constraint: Each transistor must be instantiated once. The following PBF constraints express this constraint.
W−1

Cn (i, k) = 1,

0≤i<N

(3.4)

C p (i, k) = 1,

0≤i<N

(3.5)

k=0
W−1

k=0

Diﬀerent gate constraint: P and N type transistors which have diﬀerent gate input signals must not be placed in the same column. This constraint is expressed as following PBF
constraints.
Cn (i, k) + C p ( j, k) ≤ 1,

0≤k<W

(3.6)

GAT En (i)  GAT E p ( j)(3.7)

where i and j meet following condition.
0 ≤ i < N,

0 ≤ j < N,

where GAT E n (i) and GAT E p ( j) means that the gate input signal of N type transistor i and P
type transistor j, respectively.
Neighboring transistors constraint: Two transistors facing the diﬀusions which belong to
the diﬀerent signals each other can not be placed in the neighboring columns. For example,
N type transistors 4 and 1 in Figure 3.3 can not be placed in the neighboring columns. This

30

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

constraint is expressed by the following logic equation for N type transistors.
GAPn (i, j) ∧W−2Cn (i, k) ∧ Cn ( j, k + 1) = 0

(3.8)

k=0

i  j,

0 ≤ i < N,0≤ j<N

Here, GAPn (i, j) is the logic function of F n (i) and F n ( j), and takes the value of 1 if N typetransistor i can not share its diﬀusion with N type transistor j placed to its immediate right,
otherwise 0. This logic equation is expressed as CNF. The same constraint is also expressed
as follows for P type transistors.
GAP p (i, j) ∧W−2
C p (i, k) ∧ C p ( j, k + 1) = 0

(3.9)

k=0

i  j,

0 ≤ i < Y,0≤ j<Y

Finally, we can determine whether given transistors can be placed in W columns or notusing these constraints. If no satisfiable assignment is found by the Boolean solver, it isguaranteed that there is no possible placement of W columns. Therefore, we can find an
exact minimum-width transistor placement using the procedure described below.
1. For a given transistor netlist, count the number of N and P type transistors. The initial
number of column W is set to the number of N type transistors(=#P-FET).
2. Search for a satisfiable assignment for the Boolean constraints constructed for W
columns. If a satisfiable assignment is found, these transistors can be placed in W
columns and this procedure terminates. Otherwise, go to step 3.
3. W = W + 1. Go to step 2 again.

3.3.3 Inter-Block Placement Formulation
After intra-block placement of all the blocks are finished, these blocks are placed in theminimum area. In the proposed method, inter-block placement is also based on Boolean Satisfiability. The inter-block placement problem is formulated as Pseudo-Boolean formulationin the same manner as the intra-block placement. The problem definition of the inter-block
placement is shown in Figure 3.5. In the formulation of the inter-block placement, each logic
block is placed in one column and two logic blocks must not overlap in the same column.
Two logic blocks facing the diﬀusions that can not be shared each other must not be placedon the neighboring column, as illustrated in Figure 3.5.

31

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

Column No.
0

1

2
VDD
GND

Logic Block 2

Logic Block 3

Logic Block 1

different signals(diffusion gap)

3

inter-block sharing signals(diffusion sharing)

Figure 3.5 The problem definition of the inter-block placement.

These constraints are expressed as CNF and PBF constraints in the same manner as explained in Section 3.3.2. Therefore, we obtain an exact minimum-width block placement
using the following procedure similar to that in Section 3.3.2.
1. For a given partitioned block list, count the number of logic blocks. The initial numberof column W is set to the number of the blocks.
2. Search for a satisfiable assignment for the Boolean constraints constructed for W
columns. If a satisfiable assignment is found, these blocks can be placed in W columns
and this procedure terminates. Otherwise, go to step 3.
3. W = W + 1. Go to step 2 again.

3.4 Intra-Cell Routing
The routability check of the intra-cell wiring is formulated in the same manner as explainedin Chapter 2. Since the routability check consumes extremely less time than the transistor
placement procedure, the routability check is executed flatly to the generated transistor placement in the proposed method.

3.5 Overall Flow
Figure 3.6 shows the overall cell layout synthesis flow of the proposed method. In thislayout synthesis flow, the routability check is executed once for each block after intra-blocktransistor placement. Therefore, all blocks are guaranteed to be routed individually before
inter-block placement step. After inter-block placement, the routability is checked again

32

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

Transistor-level netlist
Logic block
partitioning
Intra-block
placement
constraint
clauseNext
block

Routable ?

noyesNo moreblocks ?

noyesInter-block
placement
constraint
clauseno

Routable ?
yesCell Layout
Figure 3.6 Our hierarchical SAT-based cell layout synthesis flow.

for whole transistor placement iteratively until a routable block placement is found. If aplacement is found to be unroutable in the routability check point, a constraint clause isadded to the set of placement constraints in order not to generate this unroutable placement
again.

3.6 Experimental Results
The proposed hierarchical cell layout synthesis method is implemented to show its eﬀectiveness. In this experiment, we used Pseudo-Boolean Solver, PBS[30] to solve formulated
satisfiability problems. PBS is a complete Boolean solver which can handle CNF, PBF, andoptimization constraints.

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

33

3.6.1 Transistor Placement
First, the comparison results between the proposed hierarchical transistor placement
method and the original flat placement method explained in Chapter 2 are shown. In thecase of only transistor placement generation, all the routability check in the flow shown in
Figure 3.6 is not executed. Table 3.3 summarizes the comparison results. This table shows
the circuit name, the number of transistors inside each circuit, the number of columns of thegenerated placement, and runtime. Flat in this table indicates the original flat method andHierarchical indicates the proposed hierarchical method. Although this table shows the results of only 5 circuits, the experiment is conducted for 30 circuits. The row Total(30 circ.)
shows the total of 30 circuits. The results show that all the placements generated by the proposed method have the same width as those generated by the flat method. The runtimes are
drastically reduced by the hierarchical method particularly in the case of large cells such as
fad1 (full adder).

3.6.2 Cell Layout Synthesis
Next, we compared the proposed cell layout synthesis method with a commercial cell layout synthesis tool ProGenesis[13] and the original flat synthesis method explained in Chapter 2. In this comparison, the commercial tool only generates the symbolic layout without
layout compaction. The comparison results are shown in Table 3.4. This table shows thecircuit name, the number of columns of the generated placement, and runtime comparison.
Commercial, Flat, and Hier. indicate the commercial tool, the original flat synthesis method,
and the proposed hierarchical method, respectively. Although this table also shows the resultsof only 5 circuits, the comparison is conducted for 30 circuits.
Compared with the original flat method, the proposed method generates 1 column larger
cell layout only for mux2 circuit. On the other hand, the runtime of the proposed method
is drastically reduced compared with the flat method. These results show that the proposedhierarchical cell layout synthesis method realizes a drastic runtime reduction with little increase in cell width. Figure 3.7 illustrates a layout of a buﬀered full adder cell generated by
the proposed method. This cell has 40 transistors and can not be solved by the original flat
method in practical runtime, whereas the proposed method can solve it less than 1 minute.
Cell width comparison with the commercial tool shows that the total cell width of the
proposed method is increased about 4%. The reason of this cell width increase is the layoutstyle restriction that only the P and N type transistors which have the same gate input signal

34

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

Table 3.3 Comparison results between the proposed hierarchical transistor placement and the original
flat method proposed in Chapter 2.

Circuits

Width (#column)

Runtime (sec.)

name#transistors

Flat

Hierarchical

Flat

Hierarchical

aoi21

6

3

3

0.02

0.03

mux2

12

8

8

0.23

0.13

ao33

16

9

9

0.25

0.06

oa44

20

11

11

0.69

0.04

fad1

28

15

15

201.050.28

Total(30 circuits)

—

174

174

205.86

2.49

Ratio

—

1.000

1.000

1.000

0.012

Table 3.4 Comparison results with the commercial cell generation tool and the original flat method
proposed in Chapter 2.

Circuits

Width (#column)

Runtime (sec.)

nameCommercial

Flat

Hier.

Commercial

Flat

Hier.

aoi21

3

3

3

18.78

0.04

0.06

mux2

6

8

9

24.23

6.42

1.45

ao33

9

10

10

28.12

392.26

2.57

oa44

11

12

12

32.00

116.41

4.60

fad1

15

15

15

73.06

305.76

1.24

Total(30 circ.)

172

178

179

789.45

1907.78 19.93

Ratio

1.000

1.035 1.041

1.000

2.416

0.025

Chapter 3 Hierarchical Extension for Large Cell Layout Synthesis

35

Figure 3.7 A layout of buﬀered full adder generated by the proposed hierarchical SAT-based celllayout synthesis method.

can be placed in the same column in the proposed method, whereas the commercial tool does
not have such restriction. The runtime of the proposed method, however, is only about 3%of that of the commercial tool. These results show that the proposed method can generate
the cell layout much more quickly with a little width increase compared with the commercial
tool.

3.7 Summary
This chapter proposed a hierarchical layout synthesis method for large dual CMOS cells via
Boolean Satisfiability. Experimental results showed that the proposed hierarchical method
generates the same width placement as the exact flat method explained in Chapter 2 anddrastically reduces the runtime for transistor placement. The comparison results of the celllayout synthesis for 30 benchmark circuits showed that the proposed method generates thesame width layout as the flat method except one circuit. The comparison results with the commercial cell generation tool without cell layout compaction showed that the total cell widthof the proposed method is increased about 4% due to the layout style restriction, whereas
the runtime is only about 3% of that of the commercial tool. From these results, we canconclude that the proposed method can be used as a quick layout generator in the area oftransistor-level circuit optimization such as on-demand cell layout synthesis.

Chapter 4
Exact Minimum-Width Transistor
Placement for General CMOS Cells
4.1 Introduction
This chapter shows a minimum-width transistor placement method which is applicableto CMOS cells in presence of non-dual P and N type transistors, whereas the cell layout
synthesis methods explained in the previous chapters are only for dual cells. This chapter
only targets the minimum-width transistor placement, and does not take the intra-cell routings
into consideration. The proposed method are the first exact method which can be applied
to CMOS cells with any types of structure, whereas almost all of the conventional exacttransistor placement method[19, 22, 24] are applicable only to dual CMOS cells. All of thesemethods make pairs of complementary P and N type transistors and align them in minimum
width. Therefore, all these methods can not be applied to some cells that have non-dual P
and N type transistors. Even for the dual circuits, these methods can not always generate
the minimum-width layouts, since the width depends on pairing of P and N type transistors.
Since non-dual CMOS cells occupy a major part of an industrial standard-cell library, theexact minimum-width transistor placement should be applied even to non-dual CMOS cells.
Zhang et al.[31] proposed the novel transistor pairing algorithm which is applicable tothe cells including non-series-parallel networks. This algorithm decides pairs of P and N
type transistors for general complex gates, in which there are more than two transistors witha common input signal in their gates, so that the resulting cell width is minimized. Thismethod, however, is not an exact method and generates large placement when a given cell
has a transistor which does not have a pair transistor with the common gate input signal.
We have proposed a cell layout synthesis method using Boolean Satisfiability (SAT) in
Chapter 2. This method can generate an exact minimum-width transistor placement for non36

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

37

Table 4.1 The numbers of non-dual cells in commercial standard-cell libraries.

total number

the number ofof cells

non-dual cells

130nm A

527

274

52%

130nm B

578

294

51%

90nm A

462

90

19%

90nm B

340

176

52%

cell libraryratio

series-parallel networks if there is no P and N type transistors which can not be paired by thecommon gate input signal. However, this method has the pairing restriction same as [31] andis not applicable to the cells including the P and N type transistors which can not be paired by
the common gate input signal. This chapter proposes a minimum-width transistor placement
method for CMOS cells in presence of non-dual P and N type transistors using SAT.
There are three main contributions of this work. First, an exact transistor placement problem of non-dual CMOS cells is defined for the first time. Table 4.1 lists the numbers ofcells including non-dual P and N type transistors in several industrial standard-cell libraries.
In a standard-cell library, not only flip flops or three-state buﬀers but also intrinsically dual
CMOS circuits possibly have non-dual P and N type transistors as a result of transistor folding to meet height requirement, as shown in Figure 4.1. As a practical matter, non-dual
CMOS cells occupy about a half of an industrial standard-cell library. We propose a PseudoBoolean[30] formulation of an exact minimum-width transistor placement problem of nondual CMOS cells. As explained in Chapter 3, Pseudo-Boolean formulation can handle Conjunctive Normal Form (CNF), Pseudo-Boolean Form (PBF), and optimization constraints.
PBF constraints are expressed by linear inequalities of Boolean variables. The proposed
method can solve all these non-dual cells that can not be solved by the conventional exacttransistor placement methods only for dual cells. In addition, P and N type transistors with
common gate input signal are aligned vertically as much as possible for ease of intra-cellrouting which follows the transistor placement. Using this formulation, an exact minimumwidth transistor placement is generated for the cells to which the conventional exact method
only for dual cells is not applicable. Moreover, this method generates a smaller width placement even for a number of dual cells by introducing the pairs of P and N type transistors with
diﬀerent gate input signals.
Second, the hierarchical approach of the transistor placement is also presented for practical

38

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

3

2

1

Split wide
transistors

1

1

1

1

Requiredcell height(a) Original Netlist(dual structure)(b) Netlist after transistor folding(non-dual structure)

Figure 4.1 An example of a dual CMOS circuit which has a non-dual structure after transistor folding.

use. Although this approach has possibility to generate wider placement than that generated
flatly, the experimental results show that it generates the transistor placements with little
increase in cell width. It generates a minimum-width transistor placement hierarchically inabout one second even for the cells with large number of transistors, whereas the runtimes ofour flat approach is over one hour for larger cells with more than 24 transistors.
Third, we generalize the proposed single-row placement method to the multi-row placement and propose an exact minimum-width multi-row transistor placement method for dual
and non-dual CMOS cells. The multi-row style layout is essential in several applications
such as data paths in which the height of cells is variable while the width of cells is often predetermined. The multi-row style also has flexibility to place large P transistors and small N
transistors together and vice versa. Moreover, the multi-row style has other advantages overthe single-row style. It oﬀers control over the cell shape and aspect ratio, and can also reducethe intra-cell routing and wire lengths. Therefore, the multi-row style cell layout attracts
attention on recent deep sub-micron technologies and a lot of place&route and cell layout
synthesis tools begin to support multi-height cells. The proposed method uses an eﬃcientgate connection style and generates more area-eﬃcient transistor placements than the conventional exact minimum-width multi-row style transistor placement method only for dual
cells.

39

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Cp(0,2) = 1
Column No. 0
samesignals

D(0) = 0

1

2

3

4

5

2

0

3

1

4

4

1

0

3

2

P-FET
different
signals

D(5) = 1

N-FET
different signals

same signals

Cn(2,5) = 1

Different gate input pair
#Column = 6#Different Gate = 2

diffusion gap

diffusion sharing

Figure 4.2 The problem definition of the single row transistor placement for non-dual CMOS cells.

Section 4.2 describes the problem definition of the single-row transistor placement method
for non-dual CMOS cells. The Boolean formulation of our flat and hierarchical single-row
transistor placements are explained in Section 4.3 and Section 4.4, respectively. Next, Section 4.5 generalizes the single-row placement method to multi-row placement. Then, Section 4.6 presents the experimental results and finally Section 4.7 summarizes this chapter.

4.2 Problem Definition
When X N type transistors and Y P type transistors are given, we have to place these X + Y
transistors in the minimum area. This problem can be transformed into the problem thatplaces all transistors using the minimum number of columns as illustrated in Figure 4.2. The
P type transistors are aligned in the upper row and the N type transistors are in the bottom.
Two neighboring transistors face the diﬀusions that belong to the common signals each otherto connect their source or drain by diﬀusion sharing. The empty columns result in the diﬀu-

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

40

Table 4.2 The variables used for the formulation of the single-row transistor placement for non-dual
CMOS cells.

namenumbercondition which makes the value 1

Cn (i, k)

X×W

N-FET i is placed in the column k.

C p (i, k)

Y ×W

P-FET i is placed in the column k.

F n (i)X

N-FET i is flipped.

F p (i)Y

P-FET i is flipped.

D(k)

W

Diﬀerent gate input pair is placed in the column k.

sion gaps in the final layout as illustrated in Figure 4.2. The P and N type transistors placed in
the same column form a transistor pair. When a pair of P and N type transistors have diﬀerent
gate input signals, this pair is called a diﬀerent gate input pair. For example, P type transistor
4 and N type transistor 2 in Figure 4.2 form a diﬀerent gate input pair. If a column has only a
P or an N type transistor, this transistor is also called a diﬀerent gate input pair. Under theselayout styles, the transistor placement problem is transformed into the Conjunctive Normal
Form (CNF) and Pseudo-Boolean Form (PBF) constraints. We will explain two approaches
for generating a minimum-width single-row transistor placement in following sections. First,
the flat approach which generates an exact minimum-width placement of any types of CMOS
cells will be explained. Next, we will explain the hierarchical approach which reduces theruntime drastically with little increase in cell width.

4.3 Flat Single-Row Transistor Placement
In our formulation of the flat approach, W + 1 variables are introduced for each transistor
to identify its location and whether it is flipped or not, where W is the number of the columnsof the placement area. Additional W variables are needed to identify whether the diﬀerent
gate input pair is placed in each column or not. All variables needed for this formulation
are listed in Table 4.2. Table 4.2 shows the names of the variable type, the numbers ofeach type of variables, and the conditions when each type of variables takes the value of
1. Some example cases of such conditions are also illustrated in Figure 4.2. We formulate
the following Boolean constraints which express all the possible transistor placements in W
columns under our layout style.

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

41

Transistor overlap constraint: N type transistors must not overlap in the same column.
This constraint is expressed by the following PB constraints.
X−1

Cn (i, k) ≤ 1,

0≤k<W

(4.1)

i=0

The same constraint is expressed as PB constraints for P type transistors.
Y−1

C p (i, k) ≤ 1,

0≤k<W

(4.2)

i=0

Transistor instantiation constraint: Each transistor must be instantiated once. The following PB constraints express this constraint.
W−1

Cn (i, k) = 1,

0≤i<X

(4.3)

C p (i, k) = 1,

0≤i<Y

(4.4)

k=0
W−1

k=0

Neighboring transistors constraint: Two transistors facing the diﬀusions which belong to
the diﬀerent signals each other can not be placed in the neighboring columns. For example,
N type transistors 4 and 1 in Figure 4.2 can not be placed in the neighboring columns. This
constraint is expressed by the following logic equation.
GAPn (i, j) ∧W−2Cn (i, k) ∧ Cn ( j, k + 1) = 0

(4.5)

k=0

i  j,

0 ≤ i < X,

0≤ j<X

Here, GAPn (i, j) is the logic function of F n (i) and F n ( j), and takes the value of 1 if N typetransistor i can not share its diﬀusion with N type transistor j placed to its immediate right,
otherwise 0. This logic equation is expressed as CNF. The same constraint is also expressed
as follows for P type transistors.
GAP p (i, j) ∧W−2
C p (i, k) ∧ C p ( j, k + 1) = 0

(4.6)

k=0

i  j,

0 ≤ i < Y,0≤ j<Y

Objective function: The number of the diﬀerent gate input pairs is minimized for ease of
intra-cell routing which follows the transistor placement. The objective function is expressed
as follows.
W−1

D(k)

Minimize :
k=0

(4.7)

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

42

Definition of D(k): When a diﬀerent gate input pair is placed in the column k, the value ofD(k) must be 1. This definition is expressed by the following logic equation,Cn (i, k) ∧ C p ( j, k) ,D(k) =

(4.8)

i, j

0≤k<W
GAT En (i)  GAT E p ( j),(4.9)

0 ≤ i < X, 0 ≤ j < Y
where GAT En (i) and GAT E p ( j) mean the gate input signals of N type transistor i and P
type transistor j, respectively. This logic equation is transformed into the PB constraints asfollows for all combinations of i and j expressed by (4.9)
Cn (i, k) + C p ( j, k) ≤ D(k) + 1,

(4.10)

0≤k<W
under the condition that D(k) is minimized. The minimization condition of each D(k) value
is already expressed by the objective function (4.7). Therefore, this definition is simply
expressed by the PB constraints (4.10) for all combinations of i and j expressed by (4.9).
When the column k has only a P or an N type transistor, D(k) also takes a value of 1.
Finally, we can determine whether given transistors can be placed in W columns or notusing these constraints. If no satisfiable assignment is found by the Boolean solver, it isguaranteed that there is no possible placement of W columns. Therefore, we can find an
exact minimum-width transistor placement using the procedure described below.
1. For a given transistor netlist, count the number of N and P type transistors. The initial
number of column W is set to max(#N-FET, #P-FET).
2. Search for a satisfiable assignment of the Boolean constraints constructed for W
columns. If a satisfiable assignment is found, these transistors can be placed in W
columns and this procedure terminates. Otherwise, go to step 3.
3. W = W + 1. Go to step 2 again.

4.4 Hierarchical Single-Row Transistor Placement
As explained in Section 4.1, the flat approach can not solve the cells with large numberof transistors in reasonable time. Therefore, we also propose a hierarchical approach of our43

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

VDD
D0
A

B

Y

S0
D2

S1
D1
GND

Figure 4.3 Schematic of 3-input multiplexer and its logic block partitioning.

transistor placement method based on circuit partitioning for practical use. The hierarchical transistor placement procedure used in this method is similar to that of Chapter 3 andalso composed of partitioning, intra-block placement, and inter-block placement. However,the partitioning and intra-block placement procedures have some diﬀerences to handle nondual CMOS cells eﬀectively. The details of these procedures are explained in the following
paragraphs.
Partitioning: Our approach first partitions the given cell into logic blocks. A logic
block consists of transistors that are connected together by their diﬀusions except powerand ground. We also recognize a transmission gate as a logic block in this partitioning procedure. Figure 4.3 shows an example of 3-input multiplexer circuit. A transmission gate is
identified as an individual logic block. Two clocked inverters whose outputs are connected
are identified as one logic block using our partitioning procedure.
Intra-block placement: Next, intra-block placement of each logic block is performed using the procedure explained in Section 4.3. In this stage, an exact minimum-width transistor
placement of each block is generated. When Pseudo-Boolean constraints are generated, one
new optimization cost is introduced to maximize the number of the connections by diﬀusion
sharing between logic blocks in the inter-block placement step. The diﬀusions which can be44

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Can be shared

VDD

VDD
Y

Er = 0Y

Y
GND

B

Er = 1 E l = 1
VDDA

El = 1
Y

VDD

Y

A
B
(a)

A

Er = 1

A

B

B

A

B

El = 0Can be shared

El = 1(b)
Er = 0A

B

A

B

Can be shared

GND

GND

Y

Figure 4.4 Additional variables introduced to maximize the number of the connections by diﬀusion
sharing between logic blocks.

shared between logic blocks are power, ground, and the diﬀusions of the transmission gates.
For example of the Figure 4.3, signal name “VDD”, “GND”, “A”, and “B” can be shared by
two blocks. These signals are called inter-block sharing signals hereafter. For maximizing
the number of the connections by diﬀusion sharing in the inter-block placement step, it isbetter to place the diﬀusions that belong to the inter-block sharing signals on the edge of theplacement of each block as illustrated in Figure 4.4. Therefore, we introduce new variables
E l and E r , and a new objective function into the formulation of transistor placement to maximize the number of the connections by diﬀusion sharing. E l (E r ) takes the value of 1 unlessthe diﬀusions of the left (right) edge are assigned to the pair of the inter-block sharing signals
as illustrated in Figure 4.4. The new objective function is expressed as follows.
W−1

Minimize : (W + 1) × (E l + E r ) +D(k)(4.11)

k=0

In our formulation, the number of the connections by diﬀusion sharing between logic blocks
has the higher priority than the number of the diﬀerent gate input pairs. Therefore, E l and E rhave the coeﬃcient W + 1 to have larger cost than the diﬀerent gate input pairs.
Inter-block placement: Inter-block placement is also based on Boolean Satisfiability. The
constraints explained in Section 4.3 except “diﬀerent gate constraints” and the “objective

45

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Column No.
0

1

2
VDD
GND

Logic Block 2

Logic Block 3

Logic Block 1

different signals(diffusion gap)

3

inter-block sharing signals(diffusion sharing)

Figure 4.5 The problem definition of the inter-block placement.

function” are needed for the formulation of the inter-block placement. The problem definitionof the inter-block placement is shown in Figure 4.5. In the formulation of the inter-block
placement, each logic block is placed in one column and two logic blocks must not overlap
in the same column. Two logic blocks facing the diﬀusions that can not be shared each othermust not be placed in the neighboring column, as illustrated in Figure 4.5.
These constraints are expressed as CNF and PBF constraints in the same manner as explained in Section 4.3. Therefore, we obtain an exact minimum-width block placement using
the same procedure as explained in Section 4.3. Finally, the flow of our hierarchical approachfor transistor placement is described as follows.
1. A given transistor netlist is partitioned into logic blocks.
2. Exact minimum-width transistor placements are generated for each block using thenew objective function and the same flow as explained in Section 4.3.
3. After placements of all blocks are generated, count the number of the logic blocks. The
initial number of the column W is set to the number of logic blocks.
4. Search for a satisfiable assignment of the Boolean constraints for the inter-block placement of W columns. If a satisfiable assignment is found, these logic blocks can beplaced in W columns and this procedure terminates. Otherwise, go to step 5.
5. W = W + 1. Go to step 4 again.
Although this approach has a possibility to generate wider placement than that of the flat
approach, the experimental results show that it generates the transistor placements quickly
with little increase in cell width.

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

46

4.5 Generalization to Multi-Row Transistor Placement
In this section, we generalize the single-row placement method for dual and nondual CMOS cells explained previously to the multi-row placement and propose an exact
minimum-width multi-row transistor placement method for dual and non-dual CMOS cells.

4.5.1 Problem Definition
When X N type transistors, Y P type transistors, and the number of the P/N row R are
given, we have to place these X + Y transistors in the minimum width. This problem canbe transformed into the problem which places all transistors using the minimum number ofcolumns. Figure 4.6 illustrates the problem definition of the proposed multi-row transistor
placement. Column, row, and boundary are defined as shown in Figure 4.6 (a), respectively.
Although we assume two P/N rows and these rows abut their P transistor side each other (socalled NPPN style) in this figure, the number of P/N rows and their directions can be changed.
Moreover, our formulation can be extended to handle other styles, e.g., NPN or PNP styles,
and so on. Two horizontally neighboring transistors face the diﬀusions that belong to thecommon signals each other to connect their source or drain by diﬀusion sharing. The empty
columns result in the diﬀusion gaps in the final layout as illustrated in Figure 4.6 (b). Whentwo vertically neighboring transistors have diﬀerent gate input signals, these gate signals can
not be connected. This point is called a diﬀerent gate as shown in Figure 4.6 (b). Diﬀerent
gate is defined on the boundary. If one of the vertically neighboring grids has a transistor
and the other does not, this point is also called a diﬀerent gate. The conventional multirow transistor placement method does not consider the gate connection between two P/Nrows. Our gate connection style is a key to handling the multi-row placement of CMOS cells
including non-dual P and N type transistors eﬃciently. Under these layout styles, the multirow transistor placement problem is transformed into the Conjunctive Normal Form (CNF)
and Pseudo-Boolean Form (PBF) constraints.

4.5.2 Placement Formulation
In our formulation of the multi-row transistor placement, C × R + 1 variables are introduced
for each transistor to identify its location and whether it is flipped or not, where C and R
are the number of columns and rows of the placement area, respectively. The value of R is
assumed to be given as an input. Additional C × (2 × R − 1) variables are needed to identify

47

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

different signals

same signals

col. 0 col. 1 col. 2 col. 3 col. 4 col. 5
N-FET

boundary 0

samesignals

P-FET

row 0

different
signalsboundary 1

P-FET

boundary 2

row 1
N-FET
same signals

different signals(a) place each transistor on a grid#column = 6#different gate = 6

different
gate

diffusion sharing diffusion gap(b) a created layout from (a)Figure 4.6 The problem definition of the multi-row transistor placement for dual and non-dual CMOS
cells.

whether there is a diﬀerent gate on each boundary of vertically neighboring grids or not. The
number of the diﬀerent gate is minimized in our formulation for ease of intra-cell routing
which follows the transistor placement. All variables needed for this formulation are listed
in Table 4.3. Table 4.3 shows the names of the variable type, the numbers of each type ofvariables, and the conditions when each type of variables takes the value of 1. We formulate
the following Boolean constraints which express all the possible transistor placements in C
columns and R rows under our layout style.

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

48

Table 4.3 The variables used for the formulation of the multi-row placement.

namenumbercondition which makes the value 1

Ln (i, k, l)

X ×C ×R

N-FET i is placed in the column k, row l.

L p ( j, k, l)

Y ×C×R

P-FET j is placed in the column k, row l.

F n (i)X

N-FET i is flipped.

F p ( j)Y

P-FET j is flipped.

D(k, l)C × (2 × R − 1)

Diﬀerent gate is placed in the column k, boundary l.

Transistor overlap constraint: N type transistors must not overlap in the same column
and the same row. This constraint is expressed by the following PBF constraints.
X−1

Ln (i, k, l) ≤ 1, 0 ≤ k < C, 0 ≤ l < R(4.12)

i=0

The same constraint is expressed as PBF constraints for P type transistors.
Y−1

L p ( j, k, l) ≤ 1, 0 ≤ k < C, 0 ≤ l < R(4.13)

j=0

Transistor instantiation constraint: Each transistor must be instantiated once. The following PBF constraints express this constraint.
C−1 R−1

Ln (i, k, l) = 1, 0 ≤ i < X(4.14)

L p ( j, k, l) = 1, 0 ≤ j < Y(4.15)

k=0 l=0C−1 R−1

k=0 l=0

Neighboring transistors constraint: Two N type transistors facing the diﬀusions which
belong to the diﬀerent signals each other can not be placed in the horizontally neighboring
grids. This constraint is expressed by the following logic equation.
GAPn (i, j) ∧C−2Ln (i, k, l) ∧ Ln ( j, k + 1, l) = 0(4.16)

k=0

i  j, 0 ≤ i < X, 0 ≤ j < X, 0 ≤ l < R
Here, GAPn (i, j) is the logic function of F n (i) and F n ( j), and takes the value of 1 if N typetransistor i can not share its diﬀusion with N type transistor j placed to its immediate right,
otherwise 0. This logic equation is expressed as CNF. The same constraint is also expressedChapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

49

as follows for P type transistors.
GAP p (i, j) ∧C−2
L p (i, k, l) ∧ L p ( j, k + 1, l) = 0(4.17)

k=0

i  j, 0 ≤ i < Y, 0 ≤ j < Y, 0 ≤ l < R
Objective function: The number of the diﬀerent gate is minimized for ease of intra-cellrouting which follows the transistor placement. The objective function is expressed as follows.
C−1 2R−2

D(k, l)Minimize :(4.18)

k=0 l=0

Definition of D(k, l): When a diﬀerent gate is placed in the column k, boundary l, the valueof D(k, l) must be 1. Inside row r(= l/2), this definition is expressed by the following logic
equation,D(k, l) =

Ln (i, k, r) ∧ L p ( j, k, r) ,(4.19)

i, j

0 ≤ k < C, 0 ≤ r < R
GAT E n (i)  GAT E p ( j), 0 ≤ i < X, 0 ≤ j < Y(4.20)

where GAT En (i) and GAT E p ( j) mean the gate input signals of N type transistor i and P
type transistor j, respectively. This logic equation is transformed into the PBF constraints asfollows for all combinations of i and j expressed by (4.20)
Ln (i, k, r) + L p ( j, k, r) ≤ D(k, l) + 1,

(4.21)

0 ≤ k < C, 0 ≤ r < R
under the condition that D(k, l) is minimized. The minimization condition of each D(k, l)value is already expressed by the objective function (4.18). Therefore, this definition is simply expressed by the PBF constraints (4.21) for all combinations of i and j expressed by(4.20). When the column k, row r has either a P or an N type transistor, D(k, l) also takes
a value of 1. D(k, l) is defined not only inside each P/N row (e.g., boundaries 0 and 2 inFigure 4.6 (a)), but also on the boundary between two P/N rows (e.g., boundary 1 in Figure 4.6 (a)) in similar manner.
Finally, we can determine whether given transistors can be placed in C columns and R
rows or not, using these constraints. If no satisfiable assignment is found by a Boolean

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

50

constraint solver, it is guaranteed that there is no possible placement of C columns and R
rows. Therefore, we can find an exact minimum-width multi-row transistor placement using
the procedure described below.
1. A netlist and the number of rows R are given.
2. For a given transistor netlist, count the number of N and P type transistors. The initial
number of column C is set to max(#N-FET, #P-FET) / R4.1 .
3. Search for a satisfiable assignment of the Boolean constraints constructed for C
columns and R rows. If a satisfiable assignment is found, these transistors can beplaced in the C columns and R rows, and this procedure terminates. Otherwise, go tostep 4.
4. C = C + 1. Go to step 3 again.

4.6 Experimental Results
The proposed flat and hierarchical single-row transistor placement methods and multi-row
transistor placement method were implemented to show the eﬀectiveness of the proposed
methods. In this experiment, we used PBS[30] for a Boolean constraint solver. PBS canhandle CNF constraints, PBF constraints, and optimizations. The results of each placement
method are shown in the following sections.

4.6.1 Single-Row Flat Approach
The characteristics of the cells used for the experiment of single-row placement methods
are shown in Table 4.4. Tables 4.5 and 4.6 show the comparison with the exact transistor
placement method for dual cells explained in Chapter 2, which is applicable to the cells thatcan not be applied to other conventional exact methods such as [22] and [19]. Moreover, it
theoretically generates the same or smaller width placement than that of other existing exacttransistor placement methods for dual cells.
Table 4.5 compares the problem sizes of each formulation, and Table 4.6 compares thenumbers of columns of generated placement, and the total runtimes of each method for generating the minimum-width transistor placement from a netlist. In Table 4.5, #variable,#clause, and #inequality mean the number of variables, clauses, and inequalities of each
4.1

X indicates a minimum integer which is equal to or larger than X.

51

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Table 4.4 Cells used for the experiment of the single-row transistor placement.

Cell No.

Circuit#transistor

1

Series-parallel circuit for Y = (A ∨ B) ∧ C

10

2

Three-state buﬀer

12

3

2-input multiplexer

14

42-input AND

15

5

Series-parallel circuit for Y = (A ∧ B) ⊕ C

18

63-input exclusive OR

20

73-input exclusive NOR

22

8

D Flip Flop24

9

D Flip Flop (buﬀered)26

103-input exclusive NOR (buﬀered)28

formulation, respectively. Since both methods are based on the Boolean satisfiability, theproblem size of each formulation is also compared in this table. In Table 4.6, #column and#diﬀerent mean the number of columns and the number of the diﬀerent gate input pairs ofgenerated placement, respectively. The value of #diﬀerent for the placement method only fordual cells is always 0, since it always makes pairs of P and N type transistors with a common
gate input signal. The proposed method used PBS for a Boolean constraint solver since it
creates CNF, PBF, and optimization constraints, whereas the placement method for dual cells
used Chaﬀ [25] for a CNF-SAT solver since it creates only CNF constraints. Since PBS is
proposed to generalize the algorithms used in Chaﬀ to solve 0-1 ILP problems that may include PBF and optimization constraints, Chaﬀ finds solutions more quickly to the problemsof pure CNF constraints. For some cells which have more than 20 transistors, we have foundthat Chaﬀ can find solutions much more quickly to the problems created by the placement
method for dual cells than PBS. Therefore, the placement method for dual cells used Chaﬀ
in this experiment.
The cell number 2 (three-state buﬀer) has transistors which can not be paired by the common gate input signals. Although the cell number 4 (2-input AND) is an intrinsically dual
CMOS circuit, this cell also has non-dual P and N type transistors as a result of transistor folding. Therefore, the placement method only for dual cells can not be applied to these cells,
whereas the proposed flat approach generates the exact minimum-width transistor placementsof them as shown in Table 4.6. In the case of the cell number 10, the runtime was over 3600

52

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Table 4.5 Problem size comparison results between the exact single-row transistor placement methodfor dual cells and the proposed flat approach.

Problem Size

Cell
No.

Dual
#variable

Proposed#clause #variable #inequality#clause

1

40

760

65

121

488

2

N/A

N/A

103

251

1104

3

70

2522

103

251

1104

4

N/A

N/A

143

336

1960

5

90

4588

208

699

4212

6

100

6412

251

1011

6320

7

110

8478

321

1427

9120

8

144

17122

349

1163

11040

9

130

13070

404

2127

14170

10

140

15516

434

2465

15860

Table 4.6 Width and runtime comparison results between the exact single-row transistor placement
method for dual cells and the proposed flat approach.

Cell
No.

Width
Dual

Runtime (sec.)

Proposed#column #column #diﬀerent

Dual

Proposed

1

6

5

2

0.03

0.04

2

N/A

7

2

N/A

0.15

3

9

7

2

0.86

0.17

4

N/A

8

1

N/A

0.49

5

10

10

0

1.66

2.03

6

14

11

2

55.82

29.06

7

15

13

2

159.63969.96

8

18

13

4

1382.98

1240.83

9

—

—

—

>3600

>3600

10

16

—
—
1730.13>3600— : the procedure does not terminate after 3600 seconds

53

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Table 4.7 Comparison results between our flat and hierarchical approaches of the single-row transistor
placement.

Cell
No.

Width

Runtime (sec.)

Flat

Hierarchical#column #diﬀerent#column #diﬀerent

Flat

Hierarchical

1

5

2

6

0

0.04

0.02

2

7

2

7

2

0.15

0.02

3

7

2

7

2

0.17

0.14

4

8

1

8

1

0.49

0.03

5

10

0

10

2

2.03

0.08

6

11

2

11

4

29.06

0.29

7

13

2

13

4

969.96

3.39

8

13

4

13

4

1240.83

0.31

9

—

—

15

4

>3600

1.21

10

—

—

16
4
>3600
1.85
— : the procedure does not terminate after 3600 seconds

seconds for the flat approach, and that of both the flat approach and the placement methodfor dual cells were over 3600 seconds in the case of the cell number 9. In the other cases, theproposed method generated the same or smaller width placements by introducing diﬀerent
gate input pairs. Although the intra-cell routing may become diﬃcult by introducing thediﬀerent gate input pairs, it is easy to complete it if using the second metal layer. The runtimes of the proposed flat approach were comparable to the exact method for dual cells forcells with about 20 transistors, but the runtimes became over one hour for cells with about
26 transistors whereas the dual method could solve the cells with about 28 transistors in one
hour under our experimental setup. The next experimental results show that these runtimes
can be reduced drastically using the hierarchical approach.
We also compared the proposed transistor placement method for non-dual cells with thecommercial cell generation tool ProGenesis[13] for the “mux2” circuit which the transistor
placement method for dual cells proposed in Chapter 2 generates larger width placements
than the commercial tool as shown in Table 2.4. The method in Chapter 2 generates thelarger width placement because of the gate connection restriction between P and N type transistors, and generates the placement of 8 columns whereas the commercial tool generates theChapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

54

6 column placement. The transistor placement proposed in this chapter has no restrictionin the gate connection between P and N type transistors and the experimental result demonstrated that the proposed method generates the 6 column placement for this circuits. From
this result, we can conclude that the proposed transistor placement method considers the gateconnection between P and N type transistors more eﬃciently than the placement method fordual cells, and generates more area-eﬃcient transistor placement.

4.6.2 Single-Row Hierarchical Approach
Table 4.7 shows the comparison result between our flat and hierarchical approaches. This
table compares the numbers of the columns and the diﬀerent gate input pairs of the generated
placements, and the total runtimes. The width of the generated placement increased in thecase of the cell number 1, and the numbers of diﬀerent gate input pairs increased in the casesof the cells number 5, 6, and 7. This table clearly shows that the runtimes for transistor
placement was drastically reduced by our hierarchical approach with little increase in cellwidth. Moreover, this hierarchical approach could solve the cells with larger number oftransistors. The solutions for the cells number 9 and 10 were generated within two seconds by
the hierarchical approach, whereas the flat approach could not generate the solutions within
one hour.
Table 4.8 compares the numbers of cells that can be applied to the exact transistor placement method for dual cells explained in Chapter 2 and the proposed flat and hierarchicalapproaches in the case of an industrial standard-cell library of a 90nm technology including
340 cells. This table shows the numbers of the cells and coverage ratios of the cells thatare applicable to each method and that can be solved in 3600 seconds. Since the proposed
method is applicable to CMOS cells with any types of structures, this method was applied toall of the 340 cells, whereas the method for dual cells was about a half. The coverage ratiosof the cells that can be solved in 3600 seconds by the flat approach and the method for dual
cells are 43% and 32%, respectively. The number of the cells solved by the flat approach waslarger than that of the dual one since the proposed method can be applied to non-dual circuits as well. Among the cells solved by both methods, the proposed flat approach generated
smaller width placements for 29 out of 103 dual cells by introducing the diﬀerent gate input
pairs. Using the hierarchical approach, the coverage ratio increased to 81%, and only 3 outof 147 cells have one column wider placement. Among the 144 cells whose width are kept
minimum, only 16 cells have larger number of diﬀerent gate input pairs than the placement

55

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Table 4.8 Comparison of the number of cells that can be applied to the proposed exact single-row
transistor placement method and the method for dual cells in the case of a cell library with 340 cells.

placement

applicablesolvablemethod#cells coverage #cells coverage

Dual

164

48%

110

32%

Proposed (flat)

340

100%

147

43%

Proposed (hierarchical)

340

100%

274

81%

Table 4.9 Cells used for the experiment of the multi-row transistor placement.

Cell No.

Circuit#transistor

1

Series-parallel circuit for (A0 ∨ A1) ⊕ B

12

2

Half-adder14

3

Series-parallel circuit for (A0 ∨ A1) ⊕ B

18(buﬀered)4

D latch19

53-input XNOR

20

62-input multiplexer

21

73-input XNOR (buﬀered)22

8

D flip flop

24

94-input multiplexer

26

10Full adder28

generated by the flat approach. The rest of 19% cells can not be solved within one hour by the
proposed hierarchical approach since these cells have logic blocks with large number of transistors even after the partitioning procedure. We expect the hierarchical approach can solve
all of the cells by improving the partitioning algorithm to partition the large logic blocks into
multiple blocks. Although the total time for generating 81% of 340 cells was about 7 hours,a large part of this time was consumed by several cells. Except these time-consuming cells,
76% of 340 cells were solved in 30 minutes. This result also shows that our hierarchicalapproach reduced the runtimes drastically with little increase in cell width.

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

56

4.6.3 Multi-Row Placement
We used another set of 10 CMOS cells from a standard-cell library of 90nm technology
for the experiment of multi-row transistor placement. The characteristics of the cells used inthis experiment are summarized in Table 4.9. Table 4.10 summarizes the problem size of the
proposed multi-row transistor placement formulation and Table 4.11 shows the comparison
results with the conventional style multi-row placement method[19]. In the conventional
style, only P and N type transistors with the same gate input signal can be placed in thesame column in each P/N row, and the gate connection between two adjacent P/N rows is
not considered. This conventional style placement method was also formulated in the samemanner as the proposed method for comparison in this experiment, although the original
method[19] was solved using ILP. We assumed two P/N rows and NPPN placement style forboth methods.
In Table 4.10, #variable, #clause, and #inequality mean the number of variables, clauses,
and inequalities of the proposed formulation, respectively. Table 4.11 shows the numbers ofcolumns of generated placement, and the total runtimes of each method for generating theminimum-width transistor placement from a netlist. In the column of width, #column and#diﬀerent mean the number of columns and the number of the diﬀerent gate of generated
placement, respectively. Since the conventional style does not consider the gate connection
between two adjacent rows, this table does not show the number of diﬀerent gate for theconventional style. However, it is notable that the gates of the P/N transistor pair inside each
P/N row are always connected in the conventional style.
The cells number 4 and 6 in Table 4.9 have non-dual structure and have transistors which
can not be paired by the common gate input signals. Therefore, the conventional style can not
be applied to these cells, whereas the proposed method generates the exact minimum-widthtransistor placements of them as shown in Table 4.11. In the case of the cell number 10, theruntime was over 3600 seconds for the proposed method. In the other cases, the proposed
method generated the same or smaller width placements by using our gate connection style.
The runtimes of the proposed method were comparable to the case of using conventional stylefor the cells with up to 22 transistors and much shorter for the cells number 8 and 9, but theruntime became over one hour for the cell with 28 transistors whereas the conventional style
could solve this cell within one hour under our experimental setup. Although the runtime
depends not only on the number of the transistors but also on the connections inside the cell,these results show that the proposed method can solve the cells with up to 26 transistors in

57

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

Table 4.10 Problem size of the proposed multi-row transistor placement formulation.

Cell
No.

#transistor

Problem Size#variable #inequality#clause

1

12

93

294

504

2

14

138

486

1200

3

18

213

1028

2496

4

19

265

1399

3460

5

20

278

1628

3560

6

21

291

1653

4700

7

22

304

1954

4480

8

24

330

2280

5360

9

26

411

3162

6816

10

28

441

7344

3796

Table 4.11 Width and runtime comparison results of the proposed multi-row transistor placement
method. The conventional style assumes the pair of P/N transistors with the same gate input signals.

Cell
No.

Width
#transistor

Runtime (sec.)

Conventional

Proposed#column#column #diﬀerent

Conventional

Proposed

1

12

4

3

4

0.13

0.04

2

14

4

4

2

0.21

0.21

3

18

5

5

2

1.47

1.81

4

19

N/A

6

8

N/A

90.30

5

20

7

6

5

37.67

87.99

6

21

N/A

6

3

N/A

42.09

7

22

7

6

6

34.91

157.09

8

24

—

6

8

>3600

47.00

9

26

—

7

8

>3600

631.27

10

28

8

—
—
735.05>3600— : the procedure does not terminate after 3600 seconds

58

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

N12

B

N6

C

C

A

N12

A

C

C

N6

N2

B

N-FET
P-FET
N2

N4

B

A

N4

N3

N3

P-FET
N6

N4

N-FET
#column = 7(a) the conventional method#column = 6(b) the proposed method

Figure 4.7 Examples of the layout of the cell number 7 in Table 4.9 created by (a)the conventionaland (b)the proposed multi-row placement method. The conventional style assumes the pair of P/Ntransistors with the same gate input signals.

reasonable time. Figure 4.7 shows examples of the layout of the cell number 7 in Table 4.9
created by the conventional and the proposed method. This result clearly shows that the proposed method considers the gate connection more eﬃciently and creates more area-eﬃcient
multi-row transistor placement than the conventional one.

4.7 Summary
This chapter proposed flat and hierarchical approaches for generating a minimum-width
single-row transistor placement of CMOS cells in presence of non-dual P and N type transistors, and generalized the single-row placement method to the multi-row placement method.
Our approaches are the first exact minimum-width transistor placement method for non-dual
CMOS cells. The flat single-row approach generated smaller width placement for 29 out of
103 dual cells than the placement method for dual cells explained in Chapter 2 which theoretically generates the smallest width placement among the existing exact methods for dual
cells. The experimental results showed that it is not only applicable to CMOS cells withany types of structure, but also more eﬀective even for dual CMOS cells compared with thetransistor placement method only for dual cells.
The hierarchical single-row approach which is based on circuit partitioning reduced theruntime drastically and generated 81% of 340 cells in an industrial standard-cell library of
a 90nm technology within one hour for each cell, whereas the flat approach and the exact

Chapter 4 Exact Minimum-Width Transistor Placement for General CMOS Cells

59

method only for dual cells generated 43% and 32%, respectively. Except several cells which
consumed a large part of runtime, 76% of 340 cells were solved in 30 minutes. By improving
the partitioning algorithm, we expect to implement a new hierarchical approach which covers
100% cells of industrial libraries.
The experimental results of the exact minimum-width multi-row transistor placement
method showed that the proposed method generates more area-eﬃcient multi-row placement
than the conventional method only for dual cells by using the gate connection style which ismore suitable for multi-row transistor placement than the conventional style and can solve
the cells with up to 26 transistors in reasonable runtime.

Chapter 5
Yield-Optimal Cell Layout Synthesis for
CMOS Logic Cells
5.1 Introduction
The recent improvement of VLSI process technologies enables us to integrate a large number of transistors on one chip, and significantly improves the circuit performance. On theother hand, the methodology of VLSI design becomes more and more complex and somenew problems, such as Design For Manufacturability (DFM) have arisen. Due to the very
high costs associated with the manufacturability of sub-micron integrated circuits, even a
modest yield improvement can be extremely significant. In order to achieve the high yield,a standard-cell layout synthesis considering the DFM is required since standard-cells are themost basic elements of the cell-based design methodology as described in Chapter 1.
This chapter describes a comprehensive CMOS logic cell layout synthesis technique foryield optimization by minimizing the sensitivity to wiring faults due to spot defects. Spotdefect is one of the main sources of electrical failure in VLSI integrated circuits. We modeled
the sensitivity to wiring faults on intra-cell routings with consideration to the spot defects size
distribution and the end eﬀect of critical areas. Critical area is defined as the area in which thecenter of a spot defect must fall to cause a fault. We comprehensively generate the minimumwidth layouts of CMOS logic cells and the exact optimal layouts are selected from all thepossible minimum-width layouts by using our model of the sensitivity to wiring faults as acost metric. Although the critical area used for the sensitivity calculation is extracted fromthe original layout patterns, the feasibility of the proposed sensitivity model to the practicallithography system is discussed. Moreover, the adequacy of the proposed sensitivity to theother cost metrics such as the cell delay and the total intra-cell wire length is demonstrated.
The impact of the sensitivity reduction on the yield is also discussed in this chapter.
60

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

61

At first, Section 5.2 explains our yield cost metric for intra-cell routings and our layoutstyles are described in Section 5.3. Our comprehensive layout synthesis method and overallsystem are explained in Section 5.4 and Section 5.5 respectively, and experimental results areshown in Section 5.6. Section 5.7 discusses the relation of the critical area between before
and after lithography, and the adequacy of the proposed sensitivity. In addition, the impact of
the cost metric used in the proposed method on yield is also discussed in this section. Finally,
Section 5.8 summarizes this chapter.

5.2 Wiring Fault Model for Yield Cost Function
Critical area is defined as the area in which the center of a spot defect must fall to cause afault. Random defects caused by particulate contamination have been typically the dominantreason for yield losses[32]. Therefore, the correct estimation of the critical areas plays animportant role in layout sensitivity to spot defects and yield prediction. The spot defect size
distribution and the critical area are defined as D(x) and A(x) respectively, where x is the spot
defect size. Assuming the area distribution of defect density is uniform and written as P0 , thefault probability P is expressed as:max

P = P0D(x)A(x)dx

(5.1)

min

where min and max are the minimum and the maximum defect size[33]. The spot defects
size distribution function can be assumed to beD(x) =

X0 2
x3

(5.2)

where X0 is the peak defect size of the distribution[34]. We consider only a bridging faultof two wire segments on the same layer due to a spot defect, which is called fault type OE(One-layer Extra-material defect). Since it is impossible to define the shape of a real spot
defect, the shape of defect is assumed to be rectangular for simplicity. The critical areas of
two wire segments whose width are w and spaced by d with the defect size x are illustrated
in Figure 5.1.

The slashed area of Figure 5.1 (a) illustrates the critical area between twoparallel wire segments. This type of critical area is defined as L(x). Assume that the lengthof overlapped section is l, the critical area is expressed as l × (x − d) when the end eﬀect
is neglected[33]. We take the end eﬀect into account so that the model can be applicable tomore complex intra-cell routings, and the back-slashed areas are added to the critical area

62

x-d

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

l
w
d

x

x-d

x/2

x/2

x

x-d

(b) The critical area L(x)when l = -dx-d(a) The critical area between
parallel wire segments

The Critical Areax-dx

End Effect
The Overlapped Critical Area(c) The critical area at the corner

Figure 5.1 Critical areas between two wire segments spaced by d with the defect size x.

L(x) which is newly expressed as
L(x) = (x + l) × (x − d),(l ≥ −d).

(5.3)

L(x) is calculated in the range of l ≥ −d. When l = −d, the shape of the critical area L(x)becomes square as illustrated in Figure 5.1 (b). Figure 5.1 (c) illustrates the critical area atthe “L” type corner. Because the end sections of two critical areas are overlapped here, thearea illustrated as a black square is counted twice. Therefore, this area is subtracted oncefrom the critical area. If the corner type is “T” or “+”, the area of the square is subtracted
two or three times respectively. The black square area R(x) is expressed as
R(x) = (x − d)2 .

(5.4)

The total critical area is calculated using these equations when the size of the spot defectis x. The probabilities of fault which results from each critical area is calculated using theequation (5.1) and the defect size distribution function (5.2) as follows:max

P L = P0 X0 2
min

1
L(x)dx
x3

(5.5)

63

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

Critical Area A
Critical Area B

d+w

Critical Area Cl

2d + w + l
Figure 5.2 Critical areas between two wire segments spaced by d when the defect size x is larger than
2d + w.

where PL is the probability of fault which results from the critical area L(x). Since P0 and X0
are process-dependent constant in this equation, these factors are excluded in the following
discussion. The integral value without P0 X0 2 is defined as a Sensitivity to spot defect andwritten as S L . If the defect size x is smaller than d, the defects will not cause any fault
because of the zero critical area. If d ≤ x < 2d + w, the critical area L(x) is expressed as
the equation (5.3). The critical areas when the defect size x is equal to 2d + w are illustrated
in Figure 5.2. For 2d + w < x, the adjacent critical areas have overlapped sections andthese sections are calculated redundantly. Since a standard-cell layout commonly has dense
wiring, this causes overestimation of the sensitivity. Therefore, we assume the critical area issaturated to (2d + w + l) × (d + w) for 2d + w ≤ x. As a result, the sensitivity is expressed as
2d+w

SL =
d

(x + l)(x − d)dx +x3

(2d + w + l)(d + w)
dx.
x3
2d+w
max

(5.6)

By setting max to ∞, we obtain
S L = ln

2d + w l − d 1
1
+
−
.
d
2 d 2d + w(5.7)

By calculating in the same manner, we also obtain the sensitivity S R which results from thecritical area R(x) as follows:
S R = lnd+w
2d + w−.
d
2d + w(5.8)

These sensitivities are calculated between two diﬀerent wire segments only when these areplaced on the neighboring grids as a result of a grid-based intra-cell routing. The total sensitivity is calculated as follows:Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

64

Table 5.1 Our layout styles of the proposed comprehensive cell layout synthesis method.

1. Static CMOS logic circuits.
2. Transistors are drawn up in two horizontal rows, the upper row for P type transistors
and the bottom row for N type transistors.
3. Two transistors which have the same gate input signals are vertically aligned.
4. All transistors are uniform-sized.
5. The intra-cell routing uses only first metal layer.
6. VDD are connected from the top of P-diﬀusion to the top boundary by the verticalfirst metal.
7. GND are connected from the bottom of N-diﬀusion to the bottom boundary by thevertical first metal.
8. A single contact hole is assumed to be enough to connect metal and diﬀusion orpolysilicon.

1. Enumerate the adjacent parallel wire segments and calculate the sensitivity using theequation (5.7) for each wire segment.
2. Enumerate the overlapped critical areas at the corner and calculate the redundant sensitivity using the equation (5.8) for each overlapped critical area.
3. Subtract the sum of the redundant sensitivities from the sum of the sensitivities of theadjacent parallel wire segments.
The sensitivity calculated using our model is more accurate than that using the conventionalmodel which does not take the end eﬀect of the critical area into consideration. The conventional model neglects about 40% of the sensitivities compared with our model. Therefore,
our model is more suitable for the cell layout which has dense and complex intra-cell wirings.

5.3 Layout Styles
Our layout styles are described in Table 5.1. The layout styles No. 1 through 3 for thetransistor placement are based on the transistor placement styles defined in Chapter 2, since
the cell layout synthesis method in this chapter uses the minimum-width transistor placement
method proposed in Chapter 2. Although we assumed that all transistors are uniform-sizedfor simplicity in this chapter, it is easy to extend it to handle multiple-sized transistors. The

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

65

layout styles No. 5 through 8 in Table 5.1 are for intra-cell routing. We use only first metal
layer for intra-cell routing since it is suitable for standard-cell layouts. A single contact hole isassumed to be enough to connect the metal and diﬀusion or polysilicon due to the commonlyused silicidation.

5.4 Comprehensive Cell Layout Synthesis
5.4.1 Transistor Placement
Our method utilizes the procedure proposed in Chapter 2 to generate the minimum widthtransistor placements. In Chapter 2, the minimum width placements are generated one by
one until a routable placement is found via Boolean satisfiability. To generate all possible minimum-width placements comprehensively, we repeatedly generate a minimum-width
placement until no other placement is found for the width of the minimum-width placement.
Although the layout style used in this chapter assumes that two transistors which have thesame gate input signals are vertically aligned for simplicity, the comprehensive intra-cellrouting method explained in the following section is applicable to the placement which has avertically aligned P and N type transistor pair with diﬀerent gate input signals. Therefore, we
can also use the minimum-width transistor placement method for non-dual cells proposed in
Chapter 4 to generate all possible minimum-width placements, though the proposed comprehensive cell layout synthesis method uses the transistor placement method only for dual cells
in this chapter.

5.4.2 Intra-Cell Routing
The proposed cell layout synthesis method uses a comprehensive intra-cell router to realize
an exhaustive pattern generation for intra-cell routing. Conventionally, several exact routing algorithms have been proposed[23, 35, 36]. Among them, [35] can generate all routing
patterns exactly, but can not solve larger problems than 4×4 grids. On the other hand, [36]can solve larger problems, but this method has some restrictions and the search space of thismethod is too small for general cell generation. In this chapter, we propose a new exact
routing algorithm that can solve problems which is large enough to generate standard cellrouting patterns and its search space is much larger than that of [36] by using more practical
restrictions for standard cells. In our method, a generated placement is transformed into agrid model problem illustrated in Figure 5.3 (a). When it is given to our router, the grids forChapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

66

Before routing

After routing(a) An original grid modeltransformed froma transistor placement(b) A modified grid model given
to our comprehensive
grid router

Figure 5.3 Grid models used in our comprehensive intra-cell routing system.

gate, between the P and N diﬀusions, are shifted half grid to the left, since our method routes
the problems of complete grid model as illustrated in Figure 5.3 (b). Our method routes agiven grid model problem from left to right, column by column. Inside each column, all possible patterns are generated for each pattern of the previous column considering VDD/GND
terminals, diﬀusion silicides, gate, and I/O. VDD terminals must be connected from the topof P diﬀusion to the top boundary of routing area, and GND terminals from the bottom of N
diﬀusion to the bottom. A single contact hole is assumed to be enough to connect the metal
and the terminals on the diﬀusion or polysilicon because of the silicides. When redundant
via holes are needed, it is easy to add them to all generated routing patterns after routing isfinished and select the optimal one. If a gate terminal is an input port and is not connected
to other terminals by metal layer, at least one grid of this terminal must be reserved so thatan I/O contact can be placed on it. It also considers the design rules so as not to generate
the routing patterns which violate metal design rules when the grids are transformed backto the original grid position as shown in Figure 5.3 (a). The proposed intro-cell router has aconstraint for search space reduction as follows:• A single net can not fork when it extends to the subsequent column.
Figure 5.4 illustrates examples about this restriction. The routing pattern of Figure 5.4 (a) is
not generated by the proposed method since a single net forks to extend to the subsequentcolumn and this pattern violates the above restriction. On the other hand, the pattern of
Figure 5.4 (b) is allowed because two nets, which is not connected yet, are extended to the67

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells(a) Constrained pattern.

(b) Allowed pattern.

Figure 5.4 Wire branching constraint of the proposed comprehensive intra-cell routing method.

subsequent column individually and connected inside the subsequent column.
Figure 5.5 illustrates the flow of our intra-cell routing. The detail of each procedure is
described as follows. The numbers below corresponds to the numbers in Figure 5.5. Eachprocedure is explained using a sample problem illustrated in Figure 5.6. This figure showsthat the nets on the left are extended to the leftmost column. The thick rectangles in thisfigure indicate the terminals on source or drain, and the narrow rectangles indicate those on
gate. The nets and terminals that have the same number have to be connected to each otheron at least one grid.
1. At first, the pattern to be routed in the current column is determined by the terminal
pattern of this column and the net pattern given from the previous column. If there aresome terminals which are already connected, these terminals are removed from thispattern. Figure 5.7 (a) shows an example of this procedure. The terminal number 4
on the bottom row is removed because this terminal is already connected to the net bysilicides.
2. Next, all the terminals which are not connected yet are found and all possible connection patterns are generated considering the silicides and space of I/O contact. In
Figure 5.7 (a), the terminals number 5 and 6 can be connected inside this column. The
patterns illustrated in Figure 5.7 (b), (c), (d), and (e) show all the possible connection
patterns generated from Figure 5.7 (a).

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

68

A grid model problem
All possible
routing patterns

Finish all columns ?

yes
no

yes

Finish all previous
patterns ?

(5) Check if each pattern isvalid or not in the next columnno(1) Determine the pattern tobe routed in current column(4) Generate all possible ports
patterns to the next column(2) Find split nets and generate
all possible connections(3) Determine the nets to beextended to the next column

Figure 5.5 The flow diagram of our comprehensive intra-cell router.

3. Then, the nets which have to be extended to the subsequent column, i.e., the nets withunconnected terminals, are determined for each pattern generated in the former step.
For example of the pattern of Figure 5.7 (d), the nets number 3, 4, and 6 have otherunconnected terminals in the following columns and the net number 5 is not finishedconnection yet. Therefore, these nets have to be extended to the next column.
4. All possible net patterns extended to the subsequent column are generated for eachpattern generated in the step 3. Figure 5.8 illustrates all the possible patterns generated
from the pattern of Figure 5.7 (d). Because of the constraint explained before, a single
net can not fork when it extends to the subsequent column. Each net in this figure has
at most one extension to the subsequent column.
5. Finally, check if all the generated patterns to the subsequent column are valid or not. If
some nets of a generated pattern conflict to other connections of nets or I/Os, this pattern is impossible and removed from the group of generated patterns. For example of
Figure 5.8, (d-1) and (d-2) have nets which conflict all the terminals of terminal number 4 in the subsequent column in Figure 5.6. Therefore, these patterns are removed
and others are given to the subsequent column.

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

69

These procedures are applied for each pattern of each column and generate all possible routing patterns of a given grid-model problem under our layout styles.

5.5 Overall System
Using the procedures described in Section 5.4, we can generate all possible layouts comprehensively. Then calculate the sensitivity using the model described in Section 5.2 for eachlayout. To obtain the exact yield-optimal layouts, the proposed method does not use heuristic approaches. The proposed method selects the yield-optimal layout from all the possible
minimum-width layouts. Although the sensitivity can be reduced by inserting redundant
spaces, this chapter targets to generate the yield-optimal minimum-width cell layout. It is
possible to optimize the yield further by adjusting the space between wires in a grid-lessmanner after the yield-optimal layouts are selected. Moreover, if there are spaces between
cells after placing the generated cells, we can also improve the yield by increasing the widthof a cell without any area overhead. The next chapter proposes a further yield optimization by
inserting redundant spaces through a cell layout de-compaction in a grid-less manner. Overall flow of our yield-optimized cell layout synthesis is illustrated in Figure 5.9 and describedas follows.
1. For a given transistor netlist, generate a minimum-width transistor placement using theprocedure explained in Chapter 2. The number of diﬀusion gaps of this placement isdefined as G.
2. Comprehensively route the generated placement using the procedure explained in Section 5.4.2. If this placement is routable, generate routed layouts. Otherwise no solution.
3. Find another placement with G gaps using the procedure explained in Chapter 2. If
there is one, go to step 2 again. Otherwise go to step 4.
4. If there is no routed layout, increment G and generate a transistor placement with G
gaps using the procedure explained in Chapter 2. Then go to step 2 again. Otherwise
go to step 5.
5. Place the I/O contact holes for each generated layout if needed. If several possible I/Oplacement patterns can exist for one layout, generate all possible I/O patterns.
6. Calculate the sensitivity for each layout and find the optimal solution.

70

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

6
3

6
3

5
4

3

V

3

3

V

3

3

V

3

5

4

5

4

4

G

: Source/Drain

6: Gate
4

G

6

4

G

6

Figure 5.6 A sample problem for explaining our comprehensive intra-cell router.

3

3

3

3

3

6 3
3

6 3
3

6 3
3

3

3

3

3

3

6
33

6
33

6 5
3

6 5
3

6 5
3

5

5

5

5

5
5

5

5
5

5 4

5 4

4

5 4

4

4

4

(a)

(b)

4

4

4

(c)

(d)

(e)

Figure 5.7 An example of all possible connection patterns inside a column.

71

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

3

3

3

3

3

3

3

3

3

5

6
3

5

6
3

6

5

5

5

5

5

5

5

4
4

(d-1)

4

(d-2)

3
3
3

3
3

6

5

(d-3)

6

3
3

3

3

5

5

6

5

5

5

5

5

5

4

4
4

(d-4)

(d-5)

(d-6)

Figure 5.8 An example of all possible patterns to be extended to the subsequent column generated
from the pattern (d) in Figure 5.7.

72

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

A transistor netlist
Generate a minimum-width
placement
G = #Diffusion gaps
Route the placement
comprehensively

yes

Is there anotherplacement with G gaps ?

noAre there
any routed layouts ?

G++

no

yes
Insert I/O contacts andgenerate all possible patterns

Calculate the sensitivity
and find the optimal layouts

Yield-optimal cell layouts
Figure 5.9 The flow diagram of our yield-optimal cell layout synthesis system.

5.6 Experimental Results
We applied our layout synthesis method to 8 CMOS logic circuits in a standard-cell library,which have up to 14 transistors. Tables 5.2 and 5.3 summarize the results. In this experiment, we assumed a 0.35μm process technology and used 8 rows for routing grids. For eachcircuit, these tables indicate the number of transistors, the number of columns of routing
grids, the number of possible placements, the number of routable placements, the numberof generated layouts, the CPU times for layout synthesis and for selecting the sensitivityminimum layout, the minimum sensitivity value S min and the average sensitivity value of all
wire-length-minimum layouts S wire . This table also shows the percentage of reduction in
the sensitivity by selecting the sensitivity-minimum layout. This percentage is calculated by

73

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

Table 5.2 The results of the comprehensive cell layout synthesis.

Circuit

Cell synth.

Selection

CPU(sec.)

CPU(sec.)

948852

14685.04

323.70

4

999

0.36

0.17

4

4

8839

1.70

1.60

6

2

1

19648

13.70

4.45

12

8

24

2

34120

419.98

10.38

mux2

12

9

144

4

392

6449.82

0.19

nand4

8

5

4

4

38366

3.01

6.92

xnor2

10

7

144

24

27414

2164.30

6.97

#tr.

#col.

#place#route#layout

ao222

14

9

32

8

aoi21

6

4

4

aoi211

8

5

eno

10

gen2

name

Table 5.3 The cell selection results of the comprehensive cell layout synthesis.

Circuit

Minimum

Average sens.

Reduction

namesensitivity S min

wire-min. S wire

ratio (%)

ao222

18.04

20.55

12.19

aoi21

5.37

6.56

18.10

aoi211

6.08

7.13

14.77

eno

11.35

13.33

14.93

gen2

17.78

20.90

14.91

mux2

31.72

33.79

6.10

nand4

5.37

6.38

15.78

xnor2

11.18

15.27

26.81

(S wire − S min )/S wire × 100. As shown in Table 5.2, our method generates the layout comprehensively in only a few seconds for circuits with up to 8 transistors, whereas the runtime isseverely high for the circuit with 14 transistors. In the case of standard-cell layout synthesis,
we are allowed to consume relatively long time to obtain high quality layouts. For larger
circuits, however, we need to utilize some heuristic techniques such as netlist partitioning fortransistor placement or branch-and-bound for intra-cell routing to solve them in reasonable
time, even though these techniques do not guarantee the optimality.
In Figure 5.10, the minimum sensitivity value and the minimum, average, and maximum

74

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

ao222
Sensitivity Min.
Wire Length Min. (Sens. Min.)
Wire Length Min. (Sens. Ave.)
Wire Length Min. (Sens. Max.)

aoi21
aoi211
eno
gen2
mux2
nand4
xnor2
0

5

10
15
20
25
30
Sensitivity to Spot Defects (A.U.)

35

Figure 5.10 Changes in layout sensitivity to spot defects by selecting the sensitivity-minimum layouts.

sensitivity value of wire-length-minimum layouts are plotted for comparison. These results
show that the wire-length-minimum layouts are not always the optimal layout for the sensitivity to spot defects. Compared with the average sensitivity value of all the wire-lengthminimum layouts, our method can improve the sensitivity about 15% on an average of 8
circuits by picking up the optimal layout of sensitivity from all the generated layouts.
The snapshots of the wire-length-minimum layout and sensitivity-minimum layout of mux2
are illustrated in Figure 5.11 for example. The sensitivity optimal layout has smaller sensitivity whereas its wire length are longer than the wire length optimal layout. We also compared
the cell delay of these two layouts. The sum of the delay of all the timing arc with no output
capacitance was calculated in simulation. A timing arc is defined as a signal flow from an
input to an output on a cell, e.g., A rise → Y fall. The comparison result shows that the delayof the sensitivity-minimum layout is slower only 0.23% than that of wire-length-minimum
layout. This result shows that there is little performance degradation between these two layouts and the layouts selected by the sensitivity are acceptable also in terms of cell delay.

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells(a) Wire length minimum
Sensitivity: 33.34
Wire length: 60.075(b) Sensitivity to spot defects minimum
Sensitivity: 31.72
Wire length: 63.0

Figure 5.11 The optimal layouts of “mux2” in Table 5.2 generated by our method and selected by(a)wire length and (b)sensitivity to spot defects.

5.7 Discussion of Yield Cost Metrics
5.7.1 Lithography Impact on the Critical Area
The critical area used for modeling the sensitivity through this section is calculated fromthe original layout pattern of the first metal layer. However, the actual patterns printed on thesilicon wafer usually changes due to lithography and/or Optical Proximity Correction (OPC).
Therefore, it is necessary to clarify the impact of the lithography processes on the criticalarea. We used a cell library of a 90nm technology to show the eﬀect of the lithography.
Although we used cell layouts of a 0.35μm technology in the experimental results section,a 90nm cell library which includes the subwavelength feature size is used to highlight the
optical proximity eﬀects in this section. Figure 5.12 shows the relations between the criticalarea of the original layout patterns and the patterns after lithographic simulation before andafter OPC, respectively. The reference line in this figure indicates y = x. The critical areaplotted in this graph is calculated only for a bridging fault of two wire segments on the samelayer due to a spot defect, which is called fault type OE (One-layer Extra-material defect).
This graph plots the critical area of 340 cells in a 90nm cell library using the defect size of
1.5 times larger value than the minimum spacing of the first metal layer. Let D denote thedefect size, the OE type critical area calculation procedure in this experiment is written as
follows.

76

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

2

CA of the metal1 printed image [um ]4.5
Before OPC
After OPC
Reference (y = x)

4
3.5
3
2.5
2
1.5
1
0.5
0
0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

2

CA of the original metal1 pattern [um ]Figure 5.12 Lithography impact on the critical area before and after OPC for 340 cell layouts in a
90nm technology.

1. Expand the polygons on the first metal layer by D/2 moving the sides of the polygons
perpendicularly.
2. Sum up the overlapped areas of the expanded polygons.
The printed images are obtained by the lithographic simulation using Calibre OPC[37].
The lithographic condition used in this experiment is summarized as follows.
• Lithography Wavelength: 193nm• Numerical Aperture: 0.8• Mask Reduction Factor: 4
As shown in this graph, the critical areas of the printed images after OPC are almost always
equal to that of the original layouts under this condition. Both before and after OPC, thecorrelation coeﬃcients between the critical area of the printed images and the original layouts
are almost equal to 1. Therefore, the critical area of the printed images has strong correlation
with the original critical area even without OPC. We can conclude from this result that the
proposed model of sensitivity to wiring fault calculated from the critical area of the original
layout pattern also has strong correlation with the sensitivity after lithography, and can beused to model the yield of the printed images on the silicon wafers.

77

55

55

50

50

Sensitivity to Wiring Fault [A.U.]

Sensitivity to Wiring Fault [A.U.]

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

45
40
35
30
25
20
1.46 1.47 1.48 1.49 1.5 1.51 1.52 1.53
Sum of All Path Delay [nsec]

45
40
35
30
25
20
28

30

32 34 36 38 40
Total Wire Length [#grid]42(a) Cell delay and sensitivity(b) Wire length and sensitivity
Figure 5.13 The relation between two cost metrics in the case of the exhaustively-generated 27414
cell layouts of xnor2.

5.7.2 Relation Between Sensitivity and PerformanceThis section describes the relation between the proposed sensitivity to wiring faults andother cost metrics of cell layout, such as cell delay and total intra-cell wire length. Figure 5.13 (a) and (b) show the relation between cell delay and sensitivity, and wire length andsensitivity, respectively, in the case of the comprehensively-generated 27414 cell layouts of“xnor2” in Table 5.2. For each layout of xnor2, we simulated and summed up the delay of
all the timing arcs, and plotted it in the graph (a). Both (a) and (b) show the positive correlation between two cost metrics, and the values of the correlation coeﬃcient are 0.77 and 0.76,
respectively. There are strong correlations both between cell delay and sensitivity, and wire
length and sensitivity. Therefore, we can conclude that the selected layout by the sensitivity
might have the acceptable quality in terms of the other cost metrics such as cell delay andtotal intra-cell wire length.

5.7.3 Relation Between Sensitivity and Yield
This section describes the relation between the sensitivity and yield. Given the critical areaof the first metal layer, the yield of this layer can be modeled using a Poisson-based yieldmodel[38]:max

Ymet1 = exp −P0

D(x)A(x)dx
min

(5.9)

78

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

Ymet1 after minimizing sensitivity

1

0.1

Sens. 10% reduction
Sens. 20% reduction
Sens. 30% reduction
No reduction (ref.)

0.01
0.01

0.1

1

Ymet1 before minimizing sensitivity

Figure 5.14 The impact of the sensitivity reduction on the yield of the first metal layer.

where Ymet1 is the yield of the first metal layer. This equation can also be expressed as below:
Ymet1 = exp −P0 X0 2 × S met1

(5.10)

where S met1 is the sensitivity of the first metal layer. We define the sensitivity reduction ratio
σ and the yield improvement ratio φ as follows:
S orig − S met1,
S origYmet1 − Yorig
φ=
Yorig

σ=

(5.11)(5.12)

where S orig and Yorig are the value of the sensitivity and yield before the sensitivity is minimized, respectively. Although P0 X0 2 is the process-dependent constant and is hard to be determined accurately, we can derive the relation between σ and φ using the equations (5.10),(5.11), and (5.12) as follows:
φ = exp(−σ log Yorig ) − 1.

(5.13)

Using this equation, the relation between the yield value before and after sensitivity minimization can be illustrated as Figure 5.14. This graph clearly shows that the impact of thesensitivity reduction on the yield improvement is greater when the original yield value Yorig
is small. For example of the sensitivity reduction is 20% case, the yield improvement φ is
0.20% when Yorig = 0.99, while 4.56% when Yorig = 0.80.

Chapter 5 Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells

79

The total yield Ytotal can be expressed as the product of all yield loss reasons like below[38]:N

Ytotal =Yi(5.14)

i=1

where N is the number of yield loss reasons and Yi is the yield value of each reason. Therefore, the yield improvement ratio φ is the same value for both the yield of the first metal layer
and the total yield if the yield values of all the other reasons remain the same. From this pointof view, we can conclude that our method is more eﬀective when the total yield value of the
manufacturing process is small, i.e., the process is not mature yet.

5.8 Summary
An optimal cell layout synthesis technique to minimize the sensitivity to wiring faults has
been presented in this chapter. The sensitivity to wiring fault due to spot defects for intracell routings was modeled considering the spot defects size distribution and the end eﬀect of
critical areas, and used as a cost function. The impact of the sensitivity reduction on the yield
improvement is also described. Our cell layout synthesis technique generates the minimum
width layouts of CMOS logic cells comprehensively, and selects the optimal layouts based on
the cost functions. We applied our comprehensive layout synthesis method to 8 CMOS logic
circuits which have up to 14 transistors and the results show that the fault sensitivities are
reduced about 15% compared with the wire-length-minimum layouts. Our layout synthesis
method will be applicable for deriving the optimal cell layouts by some other cost metrics,
such as power, delay, and signal integrity, if reasonable cost functions are given.

Chapter 6
Yield Optimization by Timing-Aware Cell
Layout De-Compaction
6.1 Introduction
This chapter targets a timing-aware cell layout de-compaction method for yield enhancement.

Recently, a lot of papers related to VLSI yield improvement have been

published[14, 15, 16, 17, 18]. Most of them are proactive methodologies, which are not apost process. In [17], logic synthesis for manufacturability is proposed. This methodology
introduces the manufacturability cost into logic synthesis and replaces the traditional areadriven technology mapping with a new manufacturability-driven one. It realizes larger reduction of the manufacturability cost when yield-optimized cells are available in the cell library.
A new design flow proposed in [18] integrates manufacturability information into the timingdriven synthesis and place&route cost function. Yield-aware logic synthesis, place&route,and timing optimization are executed incrementally in this design flow. This flow uses a
DFM extension library, which has variants of the basic logic functions with diﬀerent manufacturability costs. They demonstrated the advantages of their methodology by applying it toseveral commercial ICs.
As stated above, a yield-enhanced standard-cell library is essential to these yield-aware
VLSI design methodologies. Yield-enhanced standard-cell libraries were, however, designed
mainly by hand and there is no fully automated standard cell yield optimization method
proposed for this purpose. This chapter proposes an automatic yield-optimization technique for standard cells. Several papers have proposed the de-compaction method for yieldoptimization[39, 40]. However, these methods consider only yield and area as costs, andthe circuit performances are not considered. The careless modification of the original layout
may degrade its performances severely and the created layout is not always acceptable for the80

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

81

Trade-Off Curve of Performance vs. Yieldhigh

De-Compactedwith No Constraints

Yield

This Work
Yield and Performance Variantsof the Original Cell Layout

low

Original Cell Layout
Cell Delay / Cell Area

Yield Enhanced
Cell Library
Original
Cell Library

Yield-Aware
Logic Synthesis

Yield-Aware
Physical Optimization

Figure 6.1 Overview of the proposed timing-aware cell layout yield enhancement framework.

target performances. Therefore, we propose a timing-aware cell layout de-compaction technique for yield optimization. The proposed method relaxes the width of a given cell layout
under given timing constraints to optimize the yield. Since there is normally a high quality,
hand-crafted original cell library, it is straightforward to optimize the yield by relaxing thewidth of the original layout with low computational eﬀort, rather than creating it from scratch.
Moreover, the layout after de-compaction preserves the integrity and the predictability of theoriginal layout because it also preserves the relative geometry as the original layouts.
The proposed method optimizes the yield by minimizing the Critical Area (CA). Criticalarea is defined as the area in which the center of a spot defect must fall to cause a fault andits reduction plays an important role for yield enhancement. This de-compaction frameworkis also eﬀective for OPC-relaxation. The OPC-relaxation results in terms of the fractured
mask data size reduction is also shown in this chapter. Moreover, the proposed framework is
applied to the redundant contact insertion adjacent to the single contacts. Recently, contact
failure becomes one of the most dominant yield loss reasons and redundant contact insertionis highly recommended to improve the yield. To take the parametric yield into account,the proposed de-compaction framework is also extended to the gate layout pattern regularity
enhancement to reduce the systematic variation of the gate critical dimensions.

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

82

The overview of the proposed method is illustrated in Figure 6.1. This method createsa yield-optimized cell layout under given various timing constraints and can pick up theyield variants of a cell layout from the cell delay versus yield trade oﬀ curve. These cells
are prepared as a yield-enhanced cell library and used for the yield-aware logic synthesis
and physical optimization. The proposed method performs a de-compaction of the original
cell layout using Linear Programming (LP). We develop a new accurate linear delay model
to formulate the timing constraints into LP. This model approximates the delay diﬀerence
from the original delay induced by the diﬀerences of the parasitic capacitances after decompaction.
Section 6.2 defines the problem solved in this chapter and explains the LP formulationof the design rule constraints. The formulation of the yield cost metrics, i.e., critical area
minimization, OPC relaxation, redundant contact insertion, and gate layout pattern regularity enhancement are explained in Section 6.3. Section 6.4 introduces the developed delay
model, and the overall flow of the proposed method is described in Section 6.5. Then, theexperimental results are shown in Section 6.6. Finally, Section 6.7 summarizes this chapter.

6.2 Problem Definition and Design Rule Constraints
The yield enhancement problem explained in this chapter is defined as follows:• Given: Original cell layout• Minimize: Yield cost function• Subject to:
1. Design rule constraints
2. Timing constraints
Design rule constraints are formulated from a constraint graph constructed from a given layout, i.e., a set of polygons, as shown in Figure 6.2. The target of the proposed de-compaction
method is standard cells and their heights are usually fixed. Therefore, we explain the decompaction of only horizontal direction. Each constraint exists between the vertical edges ofpolygons. Each vertex of the graph corresponds to each vertical edge of polygons and eachedge of the graph has a weight value which corresponds to either the value of the minimum
space or width. Once a constraint graph is constructed, it is straightforward to formulate the83

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

w
s

c

d

s

w
a

w
g

b

s

e

f

h

s

w
Figure 6.2 An example of a constraint graph constructed for polygons inside a given layout.

linear constraints. For example of Figure 6.2, a minimum-width constraint b − a ≥ w, and aminimum-spacing constraint g − d ≥ s, etc., are extracted.
Formally speaking, a node Vi in a constraint graph represents a layout element E i , usuallyan edge of a polygon or an instance of an object such as via. For example, let xi represent
the x coordinate of a layout element E i , the minimum spacing constraint between two layout
elements E i and E j is written as x j − xi ≥ di j , where di j is the minimum distance required by adesign rule. This constraint corresponds to a directed arc Ai j , from node Vi to V j with weight
di j in the constraint graph.
Of course, not only spacing and width design rules, but also other miscellaneous rules areformulated to create a layout without design rule violations after de-compaction. The LP
formulation of the yield cost functions and the timing constraints will be explained in thefollowing sections.

6.3 Yield Cost Metrics
6.3.1 Critical Area Minimization
In this section, we will explain how to minimize the total CA. Figure 6.3 shows the conceptual illustration of the cell layouts created by the conventional de-compaction method andthe proposed timing-aware de-compaction method by minimizing the critical area. The conventional timing-unaware method increases the width and space in the original layout for CA
minimization, whereas the timing-aware one does not increase the width and space of thenets which have an eﬀect on the target delay during CA minimization to meet the given timing constraint. Therefore, the proposed method creates the yield and performance variants of

84

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Width: X

Width: 1.5X

Width: 1.2X

Critical area: A
Fall delay: D

Critical area: 0.5A
Fall delay: 1.2D

Critical area: 0.6A
Fall delay: 1.05D(a) The original layout.

(b) The conventional
de-compaction.

(c) Timing-awarede-compaction.

Figure 6.3 The conceptual layouts of 2-input NAND created by the conventional and the timingaware de-compaction methods.

w
s

Wire

Spot DefectCritical Area

D-s

D

w

Wire

D/2
Figure 6.4 Schematic diagram of a short type critical area.

a cell layout depending on the given timing constraint. Figure 6.4 illustrates the schematic
diagram of short type CA between two parallel wire segments whose width are w and spacedby s with the defect size D. We assume that the shape of the spot defect is square for simplicity of the CA calculation. If the center of the defect falls inside the CA, these two wires
are connected and cause a fault. Open type CA is also defined for each single wire segmentin the same manner. The total CA is calculated if the coordinates of all edges are known. In
our formulation, all these coordinates are given as variables and the total CA should be minimized. Figure 6.5 shows variation of vertical and horizontal CA of both short and open type

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

85

Relaxed width/space > D(a) Vertical critical area.

Increase length(b) Horizontal critical area.
Figure 6.5 Variation of (a)vertical and (b)horizontal critical areas after horizontal de-compaction.

after horizontal de-compaction. The vertical CA are reduced by relaxing the width/space ofpolygons and finally become 0 when the width/space becomes the same value as the defectsize D, whereas the horizontal CA are possibly increased since the length of horizontal wire
segments are increased by horizontal de-compaction. The horizontal CA is easy to formulate
as a linear function because it increases in proportion to the length. On the other hand, thecalculation of the vertical CA is not so easy because it changes as shown in Figure 6.6. The
critical area should be 0 if the width/space is larger than the defect size D. To realize thisfunction, we use temporary variables r and l. These variables are defined as follows:
x1 + x2,
2
x1 + x2
,
l≤
2

r≥

D
2
D
l ≤ x2 −2r ≥ x1 +

(6.1)
(6.2)

where x1 and x2 are the right and left edge of the polygons, respectively, as shown in Figure 6.7, and D is the defect size. Assume A is the vertical CA between these polygons, A
can be written as A ∝ (r − l). To minimize the CA A, r should be minimized and l should be86D

width/
space

Figure 6.6 Change of the vertical critical area by the width or space.

x2-

x2

x1

x2

(a) x2 - x1 < D(x1+x(=r 2)/2= l)minimum
width/space(x1 x1+x
2)/2

Critical Area

x2-

x1+

D/
2
D/
2

D/
2
x1+ (=l)D/
2(=r)

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction(b) x2 - x1 > D

Figure 6.7 Calculation of the vertical critical area.

maximized. Under this condition, r and l are described as follows.
⎧⎪⎪⎪⎨ r = x1 + D/2, l = x2 − D/2 (x2 − x1 ≤ D)⎪⎪⎪⎩
r = l = (x1 + x2 )/2(x2 − x1 > D)

(6.3)

Figure 6.7 also illustrates these conditions. We can formulate the cost function as a sum ofCAs, each of which is formulated as Figure 6.6 using these variables.

6.3.2 OPC Relaxation
As the VLSI feature sizes are substantially smaller than the lithography wavelength, theresolution enhancement techniques (RETs) such as Optical Proximity Correction (OPC) andPhase Shift Masks become essential to draw the patterns correctly. Due to these RETs,
the VLSI lithography processes become more and more complex and the cost of the masks
is expected to increase steeply along with the mask data size as shown in Figure 6.8[41].
Among several RETs, OPC is one of the main contributors to the mask cost, which includes the mask data preparation and the mask writing process costs. Both of the costs
increase almost in proportion to the data size of the mask writer format, which is converted
by fracturing the GDSII layout data into rectangles and trapezoids. Therefore, the OPC alleviation by modifying the layout has a significant eﬀect on the mask data size reduction.
Recently, a lot of papers have been published in the area of the lithography-aware design

87

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

1800
Mask Cost
Mask Data Size

Mask Cost [$m]

20

1600
1400
1200

15

1000
800

10

600
400

5

Mask Data Size [GB]

25

200
0

2005 2006 2007 2008 2009 2010 2011 2012 2013(80) (70) (65) (57) (50) (45) (40) (36) (32)0Year (Technology Node [nm])Figure 6.8 The expected mask cost and mask data size in the future technologies.

methodology[42, 43, 44, 45, 46, 16]. Among them, [42, 46] address the mask cost reduction problem considering the design intent. These OPC techniques are aware of the design
informations, e.g., timing slacks. Features in the layout which are not timing-critical might
be expected to tolerate a larger degree of variation, and corrected by the less aggressive OPC.
These papers showed significant reduction in OPC data volume with little or no increasein circuit delay. In this section, we will demonstrate the OPC relaxation in terms of themask cost reduction using the proposed timing-aware cell layout de-compaction framework.
The proposed de-compaction method expands the spacings between the polygons inside thelayout and eases the optical proximity eﬀects under given timing constraints under timing
constraints. The layout after de-compaction can be printed correctly even by the modest
OPC. Therefore, we can generate the OPC-friendly cell layouts and can reduce the OPC data
size in terms of the fractured mask data size using the proposed method.
Figure 6.9 illustrates the conceptual example of OPC data volume reduction. By expanding
the spacings between the polygons, the optical proximity eﬀect between these polygons is
reduced and the pattern modification by OPC is also reduced. The complex OPC results
lead to complex mask patterning and large mask data volume. Therefore, the OPC relaxation
through de-compaction is eﬀective for OPC data volume reduction. This space expansion
procedure is almost same as the wire spreading procedures to minimize the critical area
between two wire segments explained in the previous section. Although the wire spreading

88

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Expanding the space byhorizontal de-compaction
(a)

(b)

Figure 6.9 The conceptual example of OPC data volume reduction by expanding the spacing between
the polygons.

Expanding the width

(a)

(b)

Figure 6.10 The change of the OPC pattern from (a)hammer head style to (b)serif style.

procedure for critical area minimization also increases the wire width to avoid disconnection
type failures, the wire width expansion is not eﬀective for OPC data volume reduction. When
the width of the wire increases wider than some threshold value, the OPCed pattern of thiswire changes from so-called hammer-head style to serif style pattern as shown in Figure 6.10,
and results in the data volume increase. Therefore, the proposed OPC-relaxation method
executes only wire space expansion during de-compaction in the same manner as the previous
section, whereas the width of the wire segments keep the same value as those of before thede-compaction.

6.3.3 Redundant Contact Insertion
In this section, we will explain how to maximize the number of the additional redundantcontacts under timing and area constraints. In addition to the critical area based on the random defect related faults, there are a lot of other yield loss reasons in reality. Contact/Via
open failure is one of the most important[47, 48, 49]. Due to various reasons such as cut
misalignment in a manufacturing process, electro-migration and thermal stress, a contact
may fail partially or completely. A well-known method to improve the contact yield is to89

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Additional
Contact

c
x1 x2

x1

(a) No additional contact (ri = 1).

x2(b) An additional contact can be inserted (ri = 0).

Figure 6.11 Formulation of the redundant contact insertion.

add a redundant contact adjacent to a single contact. Also for standard cells, the redundantcontact insertion is commonly used to improve their yield[50]. In this section, we explain
the formulation of the redundant contact insertion for standard cells under the timing-awarede-compaction framework.
The proposed method inserts redundant contacts adjacent to as many single contacts as
possible under given timing and area constraints. Since two parallel contacts are assumed to
be enough for yield enhancement, at most one redundant contact is inserted adjacent to eachsingle contact. In our formulation, a Boolean variable is assigned to every single contact.
Assume that the variable is written as ri for a single contact i, this variable takes the value of
0 if a redundant contact is inserted adjacent to this single contact, otherwise 1. Therefore, tomaximize the number of the redundant contacts, the cost function of the LP is formulated asfollows.
ri

Minimize :

(6.4)

i

We use Figure 6.11 to explain the constraint of the variable ri . Figure 6.11 shows the simplified example of the contact insertion to the diﬀusion area. If the space between a contact anda gate becomes larger than the space for an additional contact, ri takes the value of 0. This
constraint is written as⎧⎪⎪⎪⎨ ri = 1 (x2 − x1 < c),⎪⎪⎪⎩ ri = 0 (x2 − x1 ≥ c)

(6.5)

where c is the distance required for an additional contact. Under the condition of minimizing
ri , this constraint is expressed as follows.
x2 − x1 − c + c × ri ≥ 0(6.6)

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

90This constraint is formulated for every single contact inside the given layout. Using these
constraints and the cost function, the proposed method inserts the redundant contact as many
as possible under given timing constraints. Of course this optimization constraint can be usedin linear combination with the critical area minimization which is explained in Section 6.3.1.
Since the variables ri are Boolean, while all the other variables are real numbers, the problem
solved in the proposed method can be referred to as Mixed Integer Linear Programming(MILP).

6.3.4 Gate Layout Pattern Regularity Enhancement
Not only the functional yield considered in the previous sections, but also the parametricyield of the circuits become more and more important in the recent VLSI processes. As the
VLSI technologies scale down to the subwavelength lithographic regime, the process parameter variations lead to severe variability of chip performances and both timing and power ofintegrated circuits are increasingly aﬀected by process variations. Among many process variation sources, one of the most important parameter variations aﬀecting circuit performance isthe gate length variation of MOS transistors, since it directly aﬀects both transistor switching
speed and leakage power[51, 48, 52]. However, the gate Critical Dimension (CD) control
in the future technologies is projected as one of the most diﬃcult problems in International
Technology Roadmap for Semiconductors(ITRS)[41] and indicated that the manufacturable
solutions are not known after 2007 as shown in Figure 6.12.
Although the impacts from both systematic and random CD variations become greaterand greater, it is reported that more than 50% of transistor gate length variations are due tosystematic sources[52]. Empirical data show that the intra-die systematic CD variations resulting from the layout pattern non-uniformity are becoming comparable to, even dominant
over lot to lot, wafer to wafer, and die to die variations[53]. Moreover, CD variation due tothe depth of focus variation is known to show diﬀerent behavior dependent on the pitches of
CD patterns[15] and introduces the significant problems about the performance predictability. To reduce the systematic process variations, the regular layout has been shown to beeﬀective[54]. Therefore, various regular design styles have been suggested[55, 56] and Restrictive Design Rules (RDR) [57, 14] have also been utilized to improve pattern printability
and reduce variations. As for the standard cell layouts, the technology migration techniquewith on-pitch constraint has been proposed in [58]. Although the conventional technology
migration techniques use linear shrink in conjunction with legalization technique to clean up

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

91

Gate CD Control (3 Sigma) [nm]3.4Interim solutions are known
Manufacturable solutions are
NOT known

3.2
3.0
2.8
2.6
2.4
2.2
2.0
1.8
1.6
1.4
1.2

2005 2006 2007 2008 2009 2010 2011 2012 2013(80) (70) (65) (57) (50) (45) (40) (36) (32)Year (Technology Node [nm])Figure 6.12 Required gate CD control in the future technologies.

the ground rule violations, this technique legalizes a given layout in order to meet on-pitch
constraints with minimum layout perturbation.
In this section, we propose a gate layout pattern regularity enhancement method to reduce
the systematic variation of the gate CD. The proposed method performs a de-compaction ofa cell layout considering the on-pitch constraints and enhances the pattern regularity under
given timing constraints using LP. In contrast to [58] which minimizes the layout perturbation
to meet the design rules and on-pitch constraints during technology migration, the proposed
method minimizes the regularity cost under the design rules and timing constraints during
de-compaction. Using the proposed timing-aware regularity enhancement method, we can
explore the trade-oﬀ between performance and regularity cost, and can pick up the regularity
variants from the trade-oﬀ curve.
To enhance the regularity, gate patterns in a cell layout have to meet three restrictions: fixedgate length, single orientation, and uniform pitch. We assume that the gate patterns in a given
cell layout always have first two factors: fixed gate length and single orientation. Figure 6.13
shows the conceptual example of the regularity enhancement. As shown in this figure, thegate patterns in a layout are aligned in regular pitch during de-compaction under design ruleand timing constraints.
The cost of the regularity is defined as shown in Figure 6.14. A piecewise linear costfunction is used in the proposed method. When the gate layout pattern is placed in theChapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction
P

P

P

P

92

P

(a) The given original layout.
P

P

P

P

P

P

P

(b) The layout after regularity enhancement.
Figure 6.13 The conceptual example of gate layout pattern regularity enhancement for the regularpitch P by the proposed regularity enhancement method.

regular pitch, the cost is 0. As the distance between the gate and the regular pitch increases,
the regularity cost increases linearly. This cost function is equivalent to the distance from thenearest regular pitch. The LP formulation of this cost function is explained in the following
paragraph.
Let Egate denote the set of layout elements of transistor gate, the regularity cost used in thispaper is written as

Eig ∈Egate|xgi − ki P|,(6.7)

where xgi is an x coordinate of a gate element E ig , P is the regular pitch and ki is an integer
variable. This objective function is linearized by introducing two variables Li and Ri for each

93

Regularity
Cost

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-CompactionPP

P : Regular Pitch
P

X
Figure 6.14 The regularity cost function used in the proposed regularity enhancement method.

element Eig . The linear formulation of this minimization constraint is written as follows.
(Ri − Li )Minimize :(6.8)

Eig ∈Egate

Subject to : Li ≤ xgi , Li ≤ ki P

(6.9)

Ri ≥ xgi , Ri ≥ ki P

(6.10)In this formulation, Li is smaller than both xgi and ki P, whereas Li is maximized by theminimization constraint (6.8). Therefore, Li is always equal to the smaller one of xgi or ki P.
On the other hand, Ri is larger than both xgi and ki P, whereas Ri is minimized. Therefore, Ri
is always equal to the larger one of them. Since ki is an integer variable, the distance between
a gate and the nearest regular pitch is calculated. By minimizing this cost function, we can
optimize the regularity of the given cell layout. Since the proposed formulation includes theinteger variables ki whereas all the other variables are real numbers, this formulation is also
referred to as Mixed Integer Linear Programming (MILP).

6.4 Delay Model
We need a linear delay model to formulate the timing constraint as LP. The well-known
linear timing approximation is Elmore delay model. Figure 6.15 (a) illustrates a simple example of 2-input NAND. When the input signal A rises from logic level 0 to 1, then the output
signal Y falls to logic level 0. In this situation, this transistor network is replaced by an RC
network shown in Figure 6.15 (b) which consists of ON resistors R1 and R2 of the transistors
M1 and M2, respectively, and parasitic capacitors C1 and C2 . Using Elmore delay model, we
can calculate the fall delay of the output signal Y as follows.
DelayA→Y = (R1 + R2 ) × C1 + R2 × C2

(6.11)

94

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Y
A

B 1
Y

1 B

R1

M1

R2
A

C2

C1

M2

(a) Transistor network of 2-input NAND.

(b) RC network of 2-input NAND
for fall delay of output signal Y.

Figure 6.15 An example of 2-input NAND and its RC network for calculating Elmore delay.

However, this model is not accurate enough to model the transistors of the recent deep submicron technologies. Therefore, we develop a new delay model which only calculates thedelay diﬀerence induced by the diﬀerence of parasitic elements after de-compaction. Since
the proposed method performs a de-compaction of a given original layout, we can extract
the original parasitic elements and simulate the original delay values from this layout using
a SPICE-like circuit simulator. Once the original delay value is simulated, a delay diﬀerenceby the diﬀerence of the parasitic capacitances is approximated by a linear function. Figure 6.16 shows the graphs of fall delay of an N type transistor versus output capacitance. The
schematic of the simulated circuit is shown in Figure 6.16 (a). Figure 6.16 (b) shows thedelay variation by changing the width of the transistor and (c) shows the delay variation bychanging the value of gate input slew. In both cases, the delay increases almost in proportion
to the output capacitance, and the slope values are diﬀerent from each other. In addition, theslew value of the output signal can also be approximated as a linear function to the output
capacitance. The slope value of the slew is also dependent on the transistor width and thegate input slew. Figure 6.17 (a) shows the output slew variation by changing the width of thetransistor and (b) shows the output slew variation by changing the value of gate input slew.
Therefore, these slope values are calculated in advance and stored as a table of transistor
width and input slew for P and N type transistors, respectively.
Using these slope values, the procedure of delay or slew increase calculation is written as
follows.
1. Convert a given transistor network into an RC network and formulate the Elmore delay

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

95

Fall Delay
Input Slew

Transistor
Width

OutputCapacitance(a) Test circuit.
20.0

Fall Delay [psec]

18.0

Input Slew = 20psec

16.0
14.0
12.0
10.0
8.0

.2
=0

μm

h

idt

W

4 μm

=0.

th
Wid

6 μm
h=0.
Widt =0.8μm
Width
1.0μm
Width=

6.0
4.0

0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0
Output Capacitance [fF](b) Output delay variation by transistor width.
20.0Transistor Width = 0.4μm
18.0
sec
Fall Delay [psec]

16.0

50p

w=
Sle

14.0
12.0
10.0
8.0
6.0

ec
20ps
=
w
Sle
c
10pse
Slew= 5psec
Slew=
ec
=1ps
Slew

4.0
2.0
0

0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0
Output Capacitance [fF](c) Output delay variation by input slew.
Figure 6.16 Preliminary results of delay variation by changing the transistor width and the input slew.

96

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

30

Input Slew = 20psec

Fall Slew [psec]

25

.2μ

m

0
th=

d

Wi

20

4 μm
h=0.
Widt
.6μm
Width=0μm
Width=0.8m
Width=1.0μ

15
10
5
0
0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Output Capacitance [fF](a) Output slew variation by transistor width.
22

Transistor Width = 0.4μm

20Fall Slew [psec]

18

Sl

50
ew=

pse

c

16
14

sec
20p ec=cw
Sle =10ps =1pse
w
w
e
Sl
Sle
sec
p
5
=
lew

12
10
8

S

6
4
2
0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Output Capacitance [fF](b) Output slew variation by input slew.
Figure 6.17 Preliminary results of output slew variation by changing the transistor width and the
input slew.

function in the same manner as shown in Figure 6.15.
2. Replace the values of ON resistors by the slope values that are determined by the valuesof the width and the gate input slew of each transistor.
3. Replace the values of parasitic capacitors by the diﬀerence of each parasitic capacitor
after de-compaction.
For example of Figure 6.15, the fall delay increase ΔDelayA→Y is described as a linear func-

97

Intra-layer Cross
Coupling Capacitance Ccross

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

A

ActualApprox.
Spacing between Two
Wire Segments SAB

B
Spacing SAB

Cross Coupling Capacitance
CcrossVertically Parallel
Two Wire Segments

Figure 6.18 The linear approximation of the intra-layer cross coupling capacitance between two
vertically parallel wire segments.

tion of parasitic capacitance diﬀerences as follows,
ΔDelayA→Y = (k1 + k2 ) × ΔC1 + k2 × ΔC2(6.12)

where k1 and k2 are the delay slope values of the transistors M1 and M2, respectively, andΔC1 and ΔC2 are the diﬀerences of the parasitic capacitors C1 and C2 after de-compaction,
respectively. Using this model, we can describe the timing constraints by a linear inequationastargetDelayinitial
A→Y + ΔDelay A→Y ≤ Delay A→Y(6.13)

targetwhere Delayinitial
A→Y and Delay A→Y are the original and the target cell delay, respectively. The

increase of the output slew is also modeled in the same manner.
The diﬀerence of the parasitic capacitances also has to be linearly modeled by the coordinates of polygons in the original layout. The diﬀusion capacitance is calculated by a linear
function of the area and the perimeter of the diﬀusion region. The parasitic capacitance ofwires to ground or between overlapped layers is also calculated by a linear function of the areaof the overlapped regions. For intra-layer cross coupling capacitances, it is easy to extract thecapacitances between horizontally parallel wire segments because the de-compaction of thehorizontal direction only increases the length of the parallel wires and this type of capacitanceis mainly proportional to the length of the parallel wires. However, the coupling capacitances
between vertically parallel wire segments are not so easy to calculate because the distance
between these two wires are increased by the horizontal de-compaction and the capacitancevalue is not proportional but inversely proportional to the distance. Therefore, we approximate the value of this type of capacitance by linear function which is proportional to the98

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

A

B

Ccross(a)

A

B

CcrossCcross(b)

Figure 6.19 Approximation of the cross coupling capacitance between two signals A and B.

distance with negative slope value as shown in Figure 6.18. A capacitor between two signals
is approximated by two capacitors from each signal to ground as shown in Figure 6.19. Bothof them have the same capacitance as the original capacitor. Experimental results will showthat these approximations are accurate enough to calculate the timing constraints under the
proposed timing-aware de-compaction framework. At this stage, we can describe the timing constraints as linear functions of the coordinates of the polygons in the layout and canformulate them into the LP problem.
This model requires the slew of all the gate input signals in advance to determine the slope
values of all the transistors. Therefore, this model describes the delay and slew value of
single-stage transistor networks, since all the gate input waveforms are given for these cells.
For multi-stage cells, on the other hand, the slew value of an inner node, which is an output
of one stage and inputs to other stages, is not given in advance. Therefore, we have toapproximate the change of the slew value of this inner node to apply the proposed model tomulti-stage cells. The preliminary experiment, however, shows that the changes of the slew
values of inner nodes caused by our de-compaction method are within several percents andthese slew changes have little eﬀects on the delay changes. For this reason, we use the slew
values of the inner nodes of the original layout for the slew values of the inner nodes during
de-compaction in the case of the multi-stage cells. These original slew values of the inner
nodes are simulated and saved at the same time of the original delay simulation. Experimental
results will show that even this simple approximation realizes accurate timing constraints forthe multi-stage cells.

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Original Cell Info.

Original layout
Original netlist

99

Design Constraints
Maximum delay
for each arc
Maximum width

Linear Constraints Generator
Yield Cost
Function

Design Rule
Constraints

TimingConstraints

Linear Programming Solver

De-Compacted Layout
Figure 6.20 The overall flow diagram of the proposed timing-aware yield enhancement method.

6.5 Overall Flow
Figure 6.20 shows the overall flow diagram of the proposed method. The input to the
proposed method is the original cell information and design constraints. The original cell
information includes the original GDSII format cell layout for polygon information and the
netlist of the cell in SPICE format for transistor connection information. Design constraints
include the target cell delay for each timing arc and the maximum cell width. A timing arc
is defined as a signal flow from an input to an output on a cell, e.g., A rise → Y fall. Thesemaximum delay and area values are given as plain text format in a specific syntax. Although
the maximum width constraint was not explained in the previous sections, it can be formulated as a part of the design rule constraints. Using these informations, the linear constraints
generator, which implements the proposed timing-aware cell layout de-compaction for yield
optimization, formulates the constraints explained in the previous sections and generates aninput LP file for the LP solver. The yield cost function is selected from CA minimization,
OPC relaxation, redundant contact insertion, or gate layout pattern regularity enhancement.
Of course, the linear combination of these cost functions can be used as the yield cost function. Then, the LP solver searches for the solution of the generated LP problem. Finally, a
GDSII file of the cell layout after de-compaction is created from the solution of LP solver

100

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.1 The topological characteristics of the benchmark circuits used for the experiment of thecritical area minimization.

Circuit

Explanation#stage #trans.

NAND3 13-input NAND

1

6

NAND3 23-input NAND (buﬀered)1

12

NAND4 34-input NAND (buﬀered)1

36

NOR4 14-input NOR

1

8

NOR4 24-input NOR (buﬀered)1

28

ON2222 3 A series-parallel circuit

1

56

ADDH 1

Half Adder

4

14

OR3 2

3-input OR (buﬀered)2

23

which is equivalent to the coordinates of the polygons inside the layout. During final GDSII
file generation, the width of the outside frame of the generated cell is enlarged to fit themultiple of the fixed pitch to be used as a standard cell layout.

6.6 Experimental Results
6.6.1 Critical Area Minimization
The proposed timing-aware de-compaction method for critical area minimization was implemented to show its eﬀectiveness. In this experiment, we used ILOG CPLEX 9.1[27] for
an LP solver and 8 cells from a standard-cell library of a 90nm technology were used as
benchmarks. Among these 8 cells, 6 cells are single-stage and the others are multi-stage.
Tables 6.1 and 6.2 summarize the characteristics of these cells. These tables show the circuit name, the explanation of each circuit, the number of the stages inside each circuit, thenumber of transistors, the original cell delay value, the original cell area, and the originalcritical area. Delayorig column shows the original delay of a timing arc. The delay values ofthese arcs were constrained in this experiment. To calculate the original cell delay, a netlist
with parasitic capacitances is extracted using Mentor Graphics Calibre xL[59] and simulatedusing Synopsys HSPICE[60]. The tables of the delay slope value(Figure 6.16) for P and N
type transistors are also calculated using HSPICE in advance. In this experiment, we did notconnect an additional capacitor to the output net to clarify the eﬀect of the intra-cell parasitic elements. The defect size used in this experiment is 1.5 times larger than the minimum

101

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.2 The performance characteristics of the benchmark circuits used for the experiment of thecritical area minimization.

Circuit

Delayorig [psec] Areaorig [μm2 ] CAorig [μm2 ]NAND3 1

33.05

3.70

0.97

NAND3 2

34.56

6.53

1.97

NAND4 3

53.11

22.15

10.97

NOR4 1

73.65

4.76

1.30

NOR4 2

65.95

17.41

8.47

ON2222 3

64.83

28.75

9.92

ADDH 1

78.56

8.77

2.38

OR3 2

92.85

12.52

4.17

width/space of the first metal layer and the CAs are calculated only for the first metal layers.
All the experiments were conducted on a Linux machine with Xeon 3.4GHz processor and
2GB of RAM.
Tables 6.3 and 6.4 summarize the results of the proposed timing-aware de-compaction
method. These tables show the target and the actual delay value, the cell area, and the CAof the generated cell layouts. Delay error is calculated by (ttarget − tactual )/ttarget × 100, wherettarget and tactual are the target and the actual delay, respectively. “No constraint” in the columnof Target means that no timing constraints were set in this case. Because the vertical CA
decreases but the horizontal CA possibly increases by horizontal de-compaction, there must
be an optimal value of the total CA. The value of CA in the no constraint case is the minimum
CA value for each cell. The runtime to create the de-compacted layout is about 0.1 second
even for the largest example of ON2222 3 which consists of 56 transistors. The runtime forcreating the tables of slope values and the first HSPICE simulation for each cell is excluded
because they are conducted just once in advance. The delay values of the generated layouts
are also simulated by HSPICE using a netlist extracted by Calibre xL. The errors of the target
and actual delay values are less than 1% for most cases and the average absolute error is
0.49%. Figure 6.21 plots the target and the simulated delay values in the case of the singlestage cell NOR4 1 when the input signal to the P type transistor connected to VDD falls
from logic level 1 to 0. The simulated delay values show good accordance with the target
delay values. Figure 6.22 also plots the target and the simulated delay values in the case of
the multi-stage cell ADDH 1. These results show that the developed delay model is accurate

102

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.3 The delay accuracy of the proposed timing-aware critical area minimization method.

Circuit

NAND3 1

NAND3 2

NAND4 3

NOR4 1

NOR4 2

ON2222 3

ADDH 1

OR3 2
average

Target [psec]

Actual [psec] error [%]

35

34.98

0.06

37

36.77

0.63

No constraint

37.92

—

35

34.95

0.14

36

35.76

0.67

No constraint

36.54

—

54

53.81

0.35

55

54.72

0.51

No constraint

55.83

—

76

75.59

0.54

80

79.62

0.48

No constraint

81.33

—

67

67.47

-0.70

70

68.87

1.64

No constraint

70.06

—

66

65.63

0.56

67

66.18

1.25

No constraint

67.65

—

79

79.08

-0.10

80

80.03

-0.05

No constraint

80.91

—

94

94.06

-0.06

96

95.88

0.13

No constraint

97.91

—

—

—

0.49

103

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.4 Results of the critical area minimization by the proposed method.

Circuit

NAND3 1

NAND3 2

NAND4 3

NOR4 1

NOR4 2

ON2222 3

ADDH 1

OR3 2
average

Target [psec]

Area [μm2 ] increase [%] CA [μm2 ] reduction [%]

35

5.70

54.05

0.47

51.55

37

5.70

54.05

0.47

51.55

No constraint

5.70

54.05

0.47

51.55

35

8.11

24.20

1.56

20.81

36

8.49

30.02

1.47

25.38

No constraint

8.49

30.02

1.47

25.38

54

23.87

7.77

10.29

6.20

55

24.81

12.01

10.10

7.93

No constraint

25.58

15.49

10.00

8.84

76

5.71

19.96

0.92

29.23

80

6.02

26.47

0.85

34.61

No constraint

6.02

26.47

0.85

34.61

67

19.33

11.03

7.59

10.39

70

20.25

16.31

7.30

13.81

No constraint

20.76

19.24

7.27

14.17

66

31.20

8.52

9.11

8.17

67

31.29

8.83

8.94

9.88

No constraint

31.68

10.19

8.86

10.69

79

10.94

24.74

1.87

21.43

80

10.74

22.46

1.82

23.53

No constraint

10.74

22.46

1.82

23.53

94

14.91

19.09

3.04

27.10

96

15.62

24.76

2.94

29.50

No constraint

15.78

26.04

2.93

29.74

—

—

25.50*—
24.81*∗ : An average of the no constraint cases

104

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Simulated Delay [psec]

81
Simulated points
Reference

80
79
78
77
76
75
74
73

73

74

75

76
77
78
79
Target Delay [psec]

80

81

Simulated Delay [psec]

Figure 6.21 Accuracy of the proposed delay model in the case of the single-stage cell NOR4 1.

80.6
80.4 Simulated points
Reference
80.2
80
79.8
79.6
79.4
79.2
79
78.8
78.6
78.4
78.4 78.6 78.8 79 79.2 79.4 79.6 79.8 80 80.2 80.4 80.6
Target Delay [psec]

Figure 6.22 Accuracy of the proposed delay model in the case of the multi-stage cell ADDH 1.

enough for the proposed de-compaction method and can be applied to both single and multistage cells.
After de-compaction, the cell areas increase about 10 to 50% and the CAs decrease about 10
to 50% depending on the cells and the constraints. The average values of the cell area increase
and the CA reduction without timing constraints are about 26% and 25%, respectively. As
the timing constraint becomes tight, the cell area increase and CA reduction become small.
In the cases of NAND3 1, NAND3 2, NOR4 1, and ADDH 1, the proposed method createsthe cells with smaller delay than the no constraint case while their area and CA is equal tothat of the no constraint case. As a special case, cell area of ADDH 1 with 79 psec delay
constraint is larger than that of the 80 psec constraint. These results show the fact that the

105

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

1.3
Critical Area [um 2]

1.25
1.2
1.15
1.1
1.05
1
0.95
0.9
0.85
0.8

73

74

75 76 77 78 79
Target Delay [psec]

80

81

6

6.2

(a) Target delay versus critical area.
1.3

Critical Area [um2]

1.25
1.2
1.15
1.1
1.05
1
0.95
0.9
0.85
0.8
4.6

4.8

5

5.2 5.4 5.6 5.8
Cell Area [um2](b) Cell area versus critical area.
Figure 6.23 Trade-oﬀ curves of (a)target delay versus CA and (b)cell area versus CA in the case of
the single-stage cell NOR4 1.

layout impacts on the timing are diﬀerent by location, and the significance of the timing
consideration during layout de-compaction. Figure 6.23 and Figure 6.24 show the trade-oﬀ
curves of target delay versus CA and cell area versus CA in the cases of the single-stage cell
NOR4 1 and the multi-stage cell OR3 2, respectively. As shown in these figures, the criticalareas are minimized under given timing or area constraints for both cases. The conventional
simple de-compaction method can not create these various yield-optimized cell layouts. On
the other hand, the proposed method can pick up the yield and performance variants of a celllayout from these trade-oﬀ curves.

106

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

4.2

Critical Area [um 2]

4
3.8
3.6
3.4
3.2
3
2.8
92.5 93 93.5 94 94.5 95 95.5 96 96.5 97
Target Delay [psec](a) Target delay versus critical area.
4.2

Critical Area [um2]

4
3.8
3.6
3.4
3.2
3
2.8
12.5

13

13.5

14
14.5 15
Cell Area [um2]

15.5

16

(b) Cell area versus critical area.
Figure 6.24 Trade-oﬀ curves of (a)target delay versus CA and (b)cell area versus CA in the case of
the multi-stage cell OR3 2.

6.6.2 OPC Relaxation
This section shows the experimental results of the proposed timing-aware OPC relaxation
method. In this experiment, we also used ILOG CPLEX 9.1[27] for an LP solver, and 20 celllayouts from a standard-cell library of a 90nm technology were used as benchmarks. The
maximum wiring space allowed during de-compaction is defined as 1.5 times larger value
than the minimum space of the first metal layer, whereas the width of the wire segments keep
the same value as those of before the de-compaction as explained in Section 6.3.2. The OPC
cost in terms of the fractured mask data size is calculated only for the first metal layer. All

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

107

the experiments were conducted on a Linux machine with Xeon 3.4GHz processor and 2GBof RAM. The runtime to perform a cell layout de-compaction was less than 0.1 seconds evenfor the largest example which consists of 32 transistors.
The fractured mask data size comparison between before and after de-compaction is shownin Figure 6.25. These two graphs show the fractured mask data size for 20 cell layouts in
90nm and 65nm technology, respectively. The 65nm cell layouts used in this experiment are
prepared by shrinking the 90nm cell layouts. The OPC simulation and the fractured mask data
size calculation is conducted using Mentor Graphics Calibre[61]. The lithographic condition
used in this experiment is summarized as follows.
• Lithography Wavelength: 193nm• Numerical Aperture: 0.8• Mask Reduction Factor: 4
In this experiment, all cells are allowed 10% delay increase during de-compaction. However,
13 cells among 20 cells were enlarged to the maximum width through the de-compaction
under this constraint. Therefore, the average delay increase of these 20 cells after decompaction was about 6.73%. Under this condition, the average area overhead was 31.2%.
As shown in these graphs, the fractured mask data size is reduced in the case of almost allcells for both 90nm and 65nm technologies. The data size was reduced 4.28% and 6.65%
on an average in the case of 90nm and 65nm technology, respectively, and the maximum
reduction ratios were 13.2% and 18.4%, respectively. The reduction of fractured mask data
size directly translates to lower costs through shorter mask data preparation and mask writing
time, and higher mask yield.
Figure 6.26 shows the expected maximum and average fractured mask data size reduction
ratio depending on the technology nodes from 90nm to 65nm. The cells used in this experiment are also prepared by shrinking the 90nm cell layouts. All the simulations are conductedunder the same lithographic conditions as explained before. As shown in this figure, the proposed de-compaction method for OPC mask data volume reduction is expected to be more
eﬀective in the small feature size technology.
Figure 6.27 illustrates an example of OPC results before and after de-compaction in thecase of 65nm cell layout. From this figure, we can see that some pattern modifications by
OPC is eﬀectively removed by the de-compaction with small delay increase, particularly on
the corner of wires.

108

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

250
Original polygon
OPCed before de-compaction
OPCed after de-compaction

Fractured Data Size

200

150

100

50

0

1

5

10

15

20

15

20

Circuit Number(a) 90nm technology.
250
Original polygon
OPCed before de-compaction
OPCed after de-compaction

Fractured Data Size

200

150

100

50

0

1

5

10

Circuit Number(b) 65nm technology.
Figure 6.25 The fractured mask data size of 20 cells in (a)90nm and (b)65nm technology in the casethat 10% delay increase is allowed.

109

Fractured Data Size Reduction Ratio [%]Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

22
20

Maximum Reduction
Average Reduction

18
16
14
12
10
8
6
4
90nm

85nm

80nm
75nm
Technology Node

70nm

65nm

Figure 6.26 The reduction ratio of the fractured mask data size after de-compaction depending on thetechnology nodes.

(a) Fractured mask data size = 242.

(b) Fractured mask data size = 219, Delay increase = 3.4%, Area increase = 15.7%.
Figure 6.27 An example of OPC results in 65nm technology (a)before and (b)after de-compaction.

110

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.5 The topological characteristics of the benchmark circuits used for the experiment of redundant contact insertion.

Circuit

Explanation#trans. #stage

NAND3 13-input NAND

61

NAND3 23-input NAND (buﬀered)

121

NAND4 34-input NAND (buﬀered)36

1

NOR4 14-input NOR

8

1

NOR4 24-input NOR (buﬀered)28

1

ON2222 3

A series-parallel circuit

56

1

Table 6.6 The performance characteristics of the benchmark circuits used for the experiment of
redundant contact insertion.

Circuit

Delayorig [psec]

Areaorig [μm2 ]#Single Contact

NAND3 1

33.05

3.70

7

NAND3 2

34.56

6.53

10

NAND4 3

53.11

22.15

20

NOR4 1

73.65

4.76

9

NOR4 2

65.95

17.41

28

ON2222 3

64.83

28.75

62

6.6.3 Redundant Contact Insertion
This section shows the experimental results of the proposed timing-aware redundant contact insertion method. In this experiment, we also used ILOG CPLEX 9.1[27] for an MILP
solver and the 6 single-stage cells from a standard-cell library of a 90nm technology wereused as benchmarks. Tables 6.5 and 6.6 summarize the characteristics of these cells. All theexperiments were conducted on a Linux machine with Xeon 3.4GHz processor and 2GB of
RAM. These tables show the circuit name, the explanation of each circuit, the number of transistors, the number of the stages inside each circuit, the original cell delay value, the original
cell area, and the number of the single contacts inside the original cell layouts. Delayorig column shows the original delay of a timing arc. The delay values of these arcs were constrainedin this experiment.
Tables 6.7 and 6.8 show the results of the proposed timing-aware redundant contact insertion method. These tables show the target and the actual delay value, the cell area, and thenumber of the additional contacts inside the generated cell layouts. Delay error is calculated

111

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.7 The delay accuracy of the proposed timing-aware redundant contact insertion method.

CircuitTarget [psec]

NAND3 1

NAND3 2

NAND4 3

NOR4 1

NOR4 2

ON2222 3
average

Actual [psec] error [%]

36

36.18

-0.50

39

39.65

-1.64

No constraint

41.78

—

36

35.47

1.49

39

37.79

3.20

No constraint

42.61

—

55

54.75

0.46

60

57.97

3.50

No constraint

65.83

—

78

78.31

-0.40

86

85.59

0.48

No constraint

93.88

—

71

71.31

-0.43

77

75.67

1.76

No constraint

83.98

—

71

69.18

2.63

77

72.70

5.91

No constraint

81.75

—

—

—

1.87

by (ttarget −tactual )/ttarget ×100, where ttarget and tactual are the target and the actual delay, respectively. “No constraint” in the column of Target means that no timing constraints were set inthis case. The runtime to insert the redundant contacts is about 2 second even for the largest
example of ON2222 3 which consists of 56 transistors. The average absolute error of thetarget and actual delay value is less than 2%. Figure 6.28 plots the target and the simulateddelay values in the case of NOR4 1 when the input signal to the P type transistor connected
to VDD falls from logic level 1 to 0. The simulated delay values show good accordance withthe target delay values.

Figure 6.29 shows the trade-oﬀ curves of target delay and cellarea versus number of the additional contacts in the case of NOR4 2. As the timing and area
constraint become tight, the coverage of the redundant contact becomes small. These graphs
show that the redundant contacts are correctly inserted under the given timing/area constraint.

112

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.8 Results of the redundant contact insertion by the proposed method.

CircuitTarget [psec]

Area [μm2 ]

36

5.12

38.38

3

42.9

39

6.58

77.84

6

85.7

No constraint

6.63

79.19

7

100

36

8.34

27.72

4

40.0

39

9.42

44.26

7

70.0

No constraint

11.52

76.42

10

100

55

24.27

9.57

5

25.0

60

28.05

26.64

11

55.0

No constraint

34.62

56.30

20

100

78

6.33

32.98

4

44.4

86

7.83

64.50

7

77.8

No constraint

8.57

80.04

9

100

71

23.38

34.29

13

46.4

77

25.68

47.50

19

67.9

No constraint

30.21

73.52

28

100

71

35.66

24.03

24

38.7

77

38.40

33.57

36

58.1

No constraint

47.58

65.50

62

100

—

—

71.83*——∗ : An average of the no constraint cases

NAND3 1

NAND3 2

NAND4 3

NOR4 1

NOR4 2

ON2222 3
averageincrease [%] #Additional

Coverage [%]6.6.4 Gate Layout Pattern Regularity Enhancement
This section shows the experimental results of the proposed timing-aware gate layout pattern regularity enhancement method. In this experiment, we also used ILOG CPLEX 9.1[27]for an MILP solver, and 25 cell layouts from a standard-cell library of a 90nm technology
were used as benchmarks. The regular pitch used in this experiment is defined as two times
larger value than the minimum allowable spacing between gates without a contact between
them. All the experiments were conducted on a Linux machine with Xeon 3.4GHz processor
and 2GB of RAM.

113

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

92

Simulated points
Reference

Simulated Delay [psec]

90
88
86
84
82
80
78
76
74
72
72

74

76

78

80

82

84

86

88

90

92

Target Delay [psec]

Figure 6.28 Accuracy of the proposed delay model in the case of NOR4 1.
Number of Additional Contacts

25
20
15
10
5
0
66

68

70

72

74

76

78

80

82

84

Target Delay [psec](a) Target delay versus number of additional contacts

Number of Additional Contacts

30
25
20
15
10
5
0
16

18

20

22

24

26

28

30

2

Cell Area [um ](b) Cell area versus number of additional contacts
Figure 6.29 Trade-oﬀ curves of target delay versus number of additional contacts in the case of
NOR4 2.

114

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.9 The delay accuracy, area increase, and runtime of the proposed regularity enhancement
method with 10% allowable delay increase.

Cell

Transistor

Delay Error

Area Increase

RuntimeNumber

Count

[%]

[%]

[sec]

1

4

2.59(max.)

31.0

0.03

2

6

-0.01

26.5

0.03

3

6

0.73(max.)

23.4

0.03

4

6

1.41(max.)

31.3

0.03

5

7

0.45(max.)

22.6

0.04

6

8

0.92(max.)

25.1

0.05

7

8

-1.36

23.8

0.05

8

8

-3.26

44.3

0.02

9

8

-0.66

31.6

0.06

10

8

1.37(max.)

24.2

0.04

11

10

-3.00

38.4

0.05

12

10

2.27(max.)

31.3

0.08

13

10

0.24(max.)

25.6

0.07

14

12

0.02(max.)

31.9

0.05

15

12

-0.86

31.7

0.05

16

12

1.06(max.)

22.6

0.11

17

14

-1.53

46.8

0.08

18

16

-2.03

36.0

0.27

19

20

-0.71

48.3

0.30

20

20

-0.86

46.4

0.27

21

24

-2.81

48.3

0.64

22

28

0.59

36.5

14.62

23

32

-1.51

31.9

5.12

24

32

4.24(max.)

31.1

0.15

25

36

0.73

30.7

81.89

Average

—

1.42*
32.9
—
∗: An average absolute error of non-maximum cases.

115

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

Table 6.10 The regularity cost reduction of the proposed regularity enhancement method with 10%
allowable delay increase.

Cell

Transistor

Regularity Cost

Regularity Cost

Reduction#Perfectly

NumberCount

before RE [A.U.]

after RE [A.U.][%]

On-Pitch Gates

1

4

650

100

84.6

3

2

6

810

140

82.7

4

3

6

850

250

70.6

3

4

6

810

100

87.7

5

5

7

830

100

88.0

6

6

8

980

400

59.1

4

7

8

1010

240

76.2

6

8

8

1010

0

100

8

9

8

1000

160

84.0

5

10

8

1050

440

58.1

4

11

10

1310

80

93.9

8

12

10

1340

280

79.1

8

13

10

1530

480

68.6

5

14

12

1520

480

68.4

7

15

12

1560

400

74.4

7

16

12

1320

480

63.6

8

17

14

1920

100

94.8

12

18

16

2160

440

79.6

9

19

20

2520

500

80.2

15

20

20

2510

300

88.0

16

21

24

3210

540

83.2

19

22

28

3580

960

73.2

23

23

32

3960

820

79.3

23

24

32

2020

0

100

32

25

36

4310

1230

71.5

23

Average

—

—

—

79.6

—

116

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

350

Original Layout
Redundant Contact Insertion
Regularity Enhancement

Number of Data Points

300

mreg =4.75
σreg =0.91

250
200

morig=6.48
σorig =1.27

150

mred =5.20
σ red =1.57

100
50
0

3

4

5
6
7
8
Edge Placement Error [nm]910

Figure 6.30 The gate CD EPE histogram of all the cells used in this experiment without OPC tohighlight the eﬀectiveness.

Tables 6.9 and 6.10 summarize the detailed experimental results of the proposed timingaware regularity enhancement method when 10% delay increase is allowed during regularity
enhancement (RE). These tables show the number of transistors, the delay error between
the target and actual delay, the area increase, the runtime for each cell, the regularity cost
before and after RE and its reduction ratio, and the number of gates placed perfectly on-pitch
after RE. Delay error is calculated by (ttarget − tactual )/ttarget × 100, where ttarget and tactual are
the target and the actual delay, respectively. (max.) in the delay error column means thatthe maximum delay during regularity enhancement, which is equivalent to the delay of theregularity-enhanced cell with no timing constraint, is smaller than the target delay. Therefore,
an average of absolute delay error is calculated without these cases. The average absolute
error is about 1.4% and we can conclude that the delay increases are accurately constrained
during regularity enhancement. The average regularity cost reduction of 79.6% is achieved by
the proposed method. As a result, 73.7% gates in the regularity-enhanced layouts are placed
perfectly on-pitch when 10% delay increase is allowed. Since the regular pitch used in thisexperiment is a little larger than the usual cases, this result is rather optimistic. However,this result clearly shows that the proposed method eﬀectively enhances the regularity by decompaction of the cell layout.
Figure 6.30 plots the gate CD Edge Placement Error (EPE) distribution before and after
de-compaction for all of the cells used in this experiment with 10% allowable delay increase.
This figure shows the EPE distributions of the original and the regularity-enhanced cell lay-

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

117

outs generated by the proposed regularity enhancement method. In addition, the EPE distribution of the cell layouts through timing-aware redundant contact insertion explained in
the previous section is also plotted for comparison. Note that the redundant contact insertionis executed under the same timing constraints of the previous experiment without considering regularity constraint. Moreover, each generated cell has almost equal cell area to thecorresponding regularity-enhanced cells. In this experiment, the print images used for calculating the EPE values are simulated using Calibre[37] through mask layout without OPC tohighlight the eﬀectiveness of the proposed method. The lithographic condition used in thisexperiment is summarized as follows.
• Lithography Wavelength: 193nm• Numerical Aperture: 0.8• Mask Reduction Factor: 4
As shown in this figure, the average value m of EPE decreases both through redundant contact insertion and regularity enhancement since the average pitch of the gate layouts increases.
However, the standard deviation σ of EPE distribution is increased through redundant contact insertion due to the extra non-uniformity. On the other hand, the proposed regularity
enhancement method eﬀectively reduces the EPE distribution by introducing the gate layout
pattern uniformity. The standard deviation σ of the EPE distribution is reduced by about
28% compared to that of the original layouts. This result shows that the proposed regularity
enhancement method can reduce the systematic variation of the gate CD.
The timing accuracy of the proposed timing-aware regularity enhancement in the case of
the largest example of 4-input NAND which has 36 transistors is shown in Figure 6.31. This
figure plots the target and the simulated delay increase in the case that the input signal to the
N type transistor connected to GND rises from logic level 0 to 1. The simulated delay values
show good accordance with the target delay values. This result clearly shows the timing
accuracy of the proposed timing-aware regularity enhancement method.
Figure 6.32 shows the trade-oﬀ curve of target delay versus regularity cost reduction ratio
in the case of the same example. The proposed regularity enhancement method can pick up
the regularity and performance variants of the original cell layout from this curve and thesecells are prepared as a yield-enhanced library which is essential to realize yield-aware VLSI
design flows.

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

118

18
Simulated Points
Reference (y = x)

Actual Delay Increase [%]

16
14
12
10
8
6
4
2
0
0

2

4

6

8

10 12 14 16 18

Target Delay Increase [%]Figure 6.31 Accuracy of the cell delay constraint in the case of the largest example in Table 6.9.

Regularity Cost Reduction [%]

80
70
60
50
40
30
20
10
0
0

2

4
6
8 10 12 14 16 18
Target Delay Increase [%]Figure 6.32 Trade-oﬀ curve between regularity enhancement and target cell delay in the case of thelargest example in Table 6.9.

Chapter 6 Yield Optimization by Timing-Aware Cell Layout De-Compaction

119

6.7 Summary
This chapter proposed a yield optimization method for standard cells by cell layout decompaction under timing constraints. The proposed method performs a de-compaction of
the original layout under given timing constraints using LP. We developed a new linear delay
model which approximates the diﬀerence from the original cell delay and used this model toformulate the timing constraints as LP. Experimental results showed that the developed delay
model is accurate enough to constrain the delay during de-compaction. The maximum CA
reduction was about 25% on an average of 8 cells.
The proposed method was also shown to be eﬀective for OPC mask data volume reduction.
The proposed de-compaction method expands the spacings of the polygons inside the layout
and eases the optical proximity eﬀects under given timing constraints using LP. We use thefractured mask data size during mask creation to evaluate the OPC cost. Experimental results
on a 90nm cell layouts showed that the proposed method reduces the fractured mask data size
4.28% on an average in the case that 10% delay increase is allowed. The eﬀectiveness of the
proposed method in the future technology was also demonstrated.
The redundant contact insertion was realized by the proposed timing-aware de-compaction
framework. The proposed method inserts the redundant contacts as many as possible under
given timing and area constraints using LP.
This chapter also showed the extension of the de-compaction method to a gate layout pattern regularity enhancement to reduce the systematic variation of the gate CD. With 10%
allowable delay increase, 73.7% gates of 25 cells in a 90nm technology are placed perfectly
on-pitch by the proposed method. Experiment on the EPE estimation showed that the standard deviation of the gate CD EPE distribution is reduced by about 28% compared to that of
the original layouts and showed that the proposed regularity enhancement method is eﬀective
for reducing the systematic CD variation.
The proposed timing-aware yield enhancement method enables us to explore the tradeoﬀ between yield and performance. We can pick up the yield/performance variants fromthe trade-oﬀ curve and provide a yield-enhanced cell library. The proposed method is theessential technique to realize the yield-aware VLSI design methodologies.

Chapter 7
Conclusions
This thesis focused on the optimization methods for standard-cell layouts. We have proposed
minimum-width transistor placement and intra-cell routing via Boolean satisfiability to optimize the area of the cell layouts, and also proposed a comprehensive cell layout synthesis
method and a cell layout de-compaction method for yield optimization. The followings areconclusions through this thesis.
Chapter 2: We have proposed a minimum-width cell layout synthesis method for dual
CMOS cells via Boolean Satisfiability. Cell layout synthesis problems i.e., the transistor
placement and the intra-cell routing problems are first transformed into SAT problems by ourformulation. We have presented that the SAT formulation is more suitable for the transistor
placement by comparing the runtime of the SAT and the 0-1 ILP formulations of it. We havealso presented that the width of the placements generated by the proposed method are smaller
than that of the conventional method by using our layout styles. Our method generates thecell layouts of 30 static dual CMOS logic circuits in 58% runtime with only 5% area increase
compared with the commercial cell generation tool with cell layout compaction. These results
showed that our cell layout styles defined for the SAT formulation is practical enough togenerate the layout of dual CMOS cells quickly with a little area overhead.
Chapter 3: We have proposed a hierarchical layout synthesis method for large dual CMOS
cells via Boolean Satisfiability. Experimental results showed that the proposed hierarchicaltransistor placement method generates the same width placement as the exact flat method
proposed in Chapter 2 and drastically reduces the runtime. The comparison results of thecell layout synthesis for 30 benchmark circuits showed that the proposed method generates
the same width layout as the flat method except one circuit. The comparison results withthe commercial cell generation tool without cell layout compaction showed that the total
cell width is increased about 4% by the proposed method due to the layout style restriction,
120

Chapter 7 Conclusions

121

whereas the runtime is only about 3% of that of the commercial tool. From these results, we
can conclude that the proposed method can be used as a quick layout generator in the area oftransistor-level circuit optimization such as on-demand cell layout synthesis.
Chapter 4: We have proposed flat and hierarchical approaches for generating a minimumwidth single-row transistor placement of CMOS cells in presence of non-dual P and N typetransistors and generalized the single-row placement method to the multi-row placement
method. Our approaches are the first exact minimum-width transistor placement method
for non-dual CMOS cells. The experimental results showed that the flat single-row approach
generates smaller width placement for 29 out of 103 dual cells than the transistor placement
method for dual cells explained in Chapter 2 which theoretically generates the smallest width
placement among the existing exact methods for dual cells. This result showed that the proposed method is not only applicable to CMOS cells with any types of structure, but also more
eﬀective even for dual CMOS cells compared with the transistor placement method only fordual cells. The hierarchical single-row approach which is based on circuit partitioning reduced the runtime drastically and generated 81% of 340 cells in an industrial standard-celllibrary of a 90nm technology within one hour for each cell, whereas the flat approach andthe exact method only for dual cells generated 43% and 32%, respectively. The experimental
results of the multi-row placement method showed that the proposed method generates morearea-eﬃcient placement than the conventional method only for dual cells by using the gateconnection style which is more suitable for multi-row transistor placement than the conventional style and can solve the cells with up to 26 transistors in reasonable runtime.
Chapter 5: We have proposed an optimal cell layout synthesis technique to minimize thesensitivity to wiring faults. The sensitivity to wiring fault due to spot defects for intra-cellroutings was modeled considering the spot defects size distribution and the end eﬀect of
critical areas, and used as a cost function. The impact of the sensitivity reduction on theyield improvement was also discussed in this chapter. Our cell layout synthesis techniquegenerates the minimum width layouts of CMOS logic cells comprehensively, and selects the
optimal layouts based on the cost functions. We applied our comprehensive layout synthesis
method to 8 CMOS logic circuits which have up to 14 transistors and the results showed thatthe fault sensitivity is reduced about 15% on an average by selecting the minimum-sensitivity
layouts rather than selecting the minimum-wire-length layouts. Our layout synthesis method
is applicable for deriving the optimal cell layouts by some other cost metrics, such as power,
delay, and signal integrity, if reasonable cost functions are given.

Chapter 7 Conclusions

122

Chapter 6: We have proposed a timing-aware cell layout de-compaction method foryield optimization using Linear Programming (LP). The proposed method performs a decompaction of the original layout in order to improve the yield by minimizing the CriticalArea (CA) inside the cell. This yield improvement procedure is executed under given timing constraints. We developed a new linear delay model which approximates the diﬀerence
from the original cell delay and used this model to formulate the timing constraints as LP.
Experimental results showed that the developed delay model is accurate enough to constrain
the delay during de-compaction. The CA is correctly minimized under the given timing
constraint, and the maximum CA reduction was about 25% on an average of 8 cells. The
proposed method was also shown to be eﬀective for OPC mask data volume reduction. The
proposed de-compaction method expands the spacings of the polygons inside the layout andrelaxes the optical proximity eﬀects under given timing constraints. Experimental results
on a 90nm cell layouts showed that the proposed method reduces the fractured mask data
size 4.28% on an average in the case that 10% delay increase is allowed. The redundantcontact insertion was realized under the proposed timing-aware de-compaction framework.
The proposed method inserts the redundant contacts as many as possible under given timing
and area constraints using LP. This chapter also showed the extension of the de-compaction
method to a gate layout pattern regularity enhancement to reduce the systematic variation of
the gate critical dimension (CD). With 10% allowable delay increase, 73.7% gates of 25 cells
in a 90nm technology are placed perfectly on-pitch by the proposed method. Experimenton the edge placement error (EPE) estimation showed that the standard deviation of the gate
CD EPE distribution is reduced by about 28% compared with that of the original layouts
and the proposed regularity enhancement method is eﬀective for reducing the systematic CD
variation. The proposed timing-aware yield enhancement method enables us to explore thetrade-oﬀ between yield and performance. We can pick up the yield/performance variantsfrom the trade-oﬀ curve and provide a yield-enhanced cell library. The proposed method isthe essential technique to realize the yield-aware VLSI design methodologies.
Now we are sure that these results in this thesis such as the exact minimum-width celllayout synthesis techniques, the comprehensive cell layout synthesis method, and the celllayout de-compaction method for yield optimization will be used for standard-cell layout
optimization in terms of area, delay, and yield, and contribute to the VLSI performance andreliability improvement.

Bibliography[1] Synopsys, Inc., Design Compiler User Guide, 2005.
[2] Synopsys, Inc., Astro User Guide, 2005.
[3] Cadence Design Systems, Inc., Quick Reference for Cadence Synthesis, 2005.
[4] Cadence Design Systems, Inc., Encounter User Guide, 2005.
[5] Magma Design Automation, Inc., Blast Fusion User Guide, 2003.
[6] R. Bar-Yehuda, J. A. Feldman, R. Y. Pinter, and S. Wimer, “Depth-First-Search andDynamic Programming Algorithms for Eﬃcient CMOS Cell Generation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 7, pp.
737–743, Jul. 1989.
[7] C. J. Poirier, “Excellerator: Custom CMOS Leaf Cell Layout Generator,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 7, pp.
744–755, Jul. 1989.
[8] Y.-C. Hsieh, “LiB: A Cell Layout Generator,” in Proceedings of ACM/IEEE 27th Design
Automation Conference, 1990, pp. 474–479.
[9] C. Ong, J. Li, and C. Lo, “GENAC: An Automatic Cell Synthesis Tool,” in Proceedingsof ACM/IEEE 26th Design Automation Conference, 1989, pp. 239–243.
[10] M. Guruswamy, R. L. Maziasz, D. Dulitz, S. Raman, V. Chiluvuri, A. Fernandez, andL. G. Jones, “CELLERITY: A Fully Automatic Layout Synthesis System for Standard Cell Libraries,” in Proceedings of ACM/IEEE 34th Design Automation Conference,
1997, pp. 327–332.
[11] M. Lefebvre, D. Marple, and C. Sechen, “The Future of Custom Cell Generation in
Physical Synthesis,” in Proceedings of ACM/IEEE 34th Design Automation Conference,
1997, pp. 446–451.
123

Bibliography124[12] Synopsys, Inc., abraCAD Documentation, 2003.
[13] Prolific, Inc., ProGenesis Guide, 2003.
[14] L. Capodieci, P. Gupta, A. B. Kahng, D. Sylvester, and J. Yang, “Toward a Methodology
for Manufacturability-Driven Design Rule Exploration,” in Proceedings of ACM/IEEE
41st Design Automation Conference, 2004, pp. 311–316.
[15] P. Gupta and F.-L. Heng, “Toward a Systematic-Variation Aware Timing Methodology,”
in Proceedings of ACM/IEEE 41st Design Automation Conference, 2004, pp. 321–326.
[16] J. Mitra, P. Yu, and D. Z. Pan, “RADAR: RET-Aware Detailed Routing Using Fast
Lithography Simulations,” in Proceedings of ACM/IEEE 42nd Design Automation Conference, 2005, pp. 369–372.
[17] A. Nardi and A. L. Sangiovanni-Vincentelli, “Synthesis for Manufacturability: a Sanity
Check,” in Proceedings of IEEE/ACM Design, Automation and Test in Europe, 2004,
pp. 796–801.
[18] C. Guardiani, N. Dragone, and P. McNamara, “Proactive Design For Manufacturability (DFM) for Nanometer SoC Designs,” in Proceedings of IEEE Custom Integrated
Circuits Conference, 2004, pp. 309–316.
[19] A. Gupta and J. P. Hayes, “Width Minimization of Two-Dimensional CMOS Cells Using Integer Programming,” in Proceedings of IEEE/ACM International Conference on
Computer Aided Design, 1996, pp. 660–667.
[20] A. Gupta and J. P. Hayes, “CLIP: An Optimizing Layout Generator for TwoDimensional CMOS Cells,” in Proceedings of ACM/IEEE 34th Design Automation Conference, 1997, pp. 452–455.
[21] A. Gupta and J. P. Hayes, “Optimal 2-D Cell Layout with Integrated Transistor Folding,”
in Proceedings of IEEE/ACM International Conference on Computer Aided Design,
1998, pp. 128–135.
[22] R. L. Maziasz and J. P. Hayes, “Exact Width and Height Minimization of CMOS Cells,”
in Proceedings of ACM/IEEE 28th Design Automation Conference, 1991, pp. 487–493.

Bibliography125[23] S. Devadas, “Optimal Layout via Boolean Satisfiability,” in Proceedings of IEEE/ACM
International Conference on Computer Aided Design, 1989, pp. 294–297.
[24] T. Uehara and W. M. vanCleemput, “Optimal Layout of CMOS Functional Arrays,”
IEEE Transactions on Computers, vol. C-30, no. 5, pp. 305–312, May 1981.
[25] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik, “Chaﬀ: Engineering an Eﬃcient SAT Solver,” in Proceedings of ACM/IEEE 38th Design Automation
Conference, 2001, pp. 530–535.
[26] P. Barth, “A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean
Optimization,” Research Report MPI-I-95-2-003, Max-Planck-Institut für Informatik,Jan. 1989.
[27] ILOG, Inc., ILOG CPLEX User’s Manual, 2005.
[28] T. Sadakane, H. Nakao, and M. Terai, “A New Hierarchical Algorithm for Transistor
Placement in CMOS Macro Cell Design,” in Proceedings of IEEE Custom Integrated
Circuits Conference, 1995, pp. 461–464.
[29] A. Gupta, S. C. The, and J. P. Hayes, “XPRESS: A Cell Layout Generator with Integrated Transistor Folding,” in Proceedings of IEEE European Design and Test Conference, 1996, pp. 393–400.
[30] F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah, “Generic ILP versus Specialized 0-1 ILP: An Update,” in Proceedings of IEEE/ACM International Conference on
Computer Aided Design, 2002, pp. 450–457.
[31] H. Zhang and K. Asada, “An Improved Algorithm of Transistor Pairing for Compact
Layout of Non-Series-Parallel CMOS Networks,” in Proceedings of IEEE Custom Integrated Circuits Conference, 1993, pp. 17.2.1–17.2.4.
[32] R. W. Dutton and A. J. Strojwas, “Perspectives on Technology and Technology-Driven
CAD,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 12, pp. 1544–1560, Dec. 2000.
[33] E. P. Huijbregtz, H. Xue, and J. A. G. Jess, “Routing for Reliable Manufacturing,” IEEE
Transactions on Semiconductor Manufacturing, vol. 8, no. 2, pp. 188–194, May 1995.

Bibliography126[34] C. H. Stapper, “Modeling of Defects in Integrated Circuit Photolithographic Patterns,”
IBM Journal of Research and Development, vol. 28, no. 4, pp. 461–475, Jul. 1984.
[35] F. Schmiedle, R. Drechsler, and B. Becker, “Exact Channel Routing Using Symbolic
Representation,” in Proceedings of IEEE International Symposium on Circuit and Systems, 1999, pp. 394–397.
[36] K. Sulimma and W. Kunz, “An Exact Algorithm for Solving Diﬃcult Detailed Routing
Problems,” in Proceedings of ACM International Symposium on Physical Design, 2001,
pp. 198–203.
[37] Mentor Graphics, Corp., Calibre Model-Based OPC User’s Manual, 2005.
[38] H. T. Heineken, J. Khare, and W. Maly, “Yield Loss Forecasting in the Early Phases of
the VLSI Design Process,” in Proceedings of IEEE Custom Integrated Circuits Conference, 1996, pp. 27–30.
[39] C. Bamji and E. Malavasi, “Enhanced Network Flow Algorithm for Yield Optimization,” in Proceedings of ACM/IEEE 33rd Design Automation Conference, 1996, pp.
746–751.
[40] Y. Bourai and C.-J. R. Shi, “Layout Compaction for Yield Optimization via CriticalArea Minimization,” in Proceedings of IEEE/ACM Design, Automation and Test in Europe, 2000, pp. 122–125.
[41] Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2005.
[42] P. Gupta, A. B. Kahng, D. Sylvester, and J. Yang, “A Cost-Driven Lithographic Correction Methodology Based on Oﬀ-the-Shelf Sizing Tools,” in Proceedings of ACM/IEEE
40th Design Automation Conference, 2003, pp. 16–21.
[43] Q. D. Qian and S. X.-D. Tan, “Advanced Physical Models for Mask Data Verification
and Impacts on Physical Layout Synthesis,” in Proceedings of IEEE International Symposium on Quality Electronic Design, 2003, pp. 125–130.
[44] L. D. Huang and M. D. F. Wong, “Optical Proximity Correction (OPC)-Friendly Maze
Routing,” in Proceedings of ACM/IEEE 41st Design Automation Conference, 2004, pp.
186–191.

Bibliography127[45] Y. C. Ban, S. H. Choi, K. H. Lee, D. H. Kim, J.-S. Hong, Y.-H. Kim, M.-H. Yoo, and
J.-T. Kong, “A Fast Lithography Verification Framework for Litho-Friendly Layout Design,” in Proceedings of IEEE International Symposium on Quality Electronic Design,
2005, pp. 169–174.
[46] P. Gupta, A. B. Kahng, D. Sylvester, and J. Yang, “Performance-Driven OPC for Mask
Cost Reduction,” in Proceedings of IEEE International Symposium on Quality Electronic Design, 2005, pp. 270–257.
[47] K.-Y. Lee and T.-C. Wang, “Post-Routing Redundant Via Insertion for Yield/Reliability
Improvement,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation
Conference, 2006, pp. 303–308.
[48] J. Luo, S. Sinha, Q. Su, J. Kawa, and C. Chiang, “An IC Manufacturing Yield Model
Considering Intra-Die Variations,” in Proceedings of ACM/IEEE 43rd Design Automation Conference, 2006, pp. 749–754.
[49] H.-Y. Chen, M.-F. Chiang, Y.-W. Chang, L. Chen, and B. Han, “Novel Full-Chip Gridless Routing Considering Double-Via Insertion,” in Proceedings of ACM/IEEE 43rd
Design Automation Conference, 2006, pp. 755–760.
[50] A. B. Kahng, L. K. Scheﬀer, M. Orshansky, and A. Strojwas, “DFM Tools and Methodologies for 65nm and Below,” in Tutorial of IEEE/ACM Asia and South Pacific Design
Automation Conference, 2006.
[51] M. Orshansky, L. Milor, P. Chen, K. Keutzer, and C. Hu, “Impact of Spatial Intrachip
Gate Length Variability on the Performance of High-Speed Digital Circuits,” IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21,
no. 5, pp. 544–553, May 2002.
[52] K. Cao, S. Dobre, and J. Hu, “Standard Cell Characterization Considering Lithography
Induced Variations,” in Proceedings of ACM/IEEE 43rd Design Automation Conference,
2006, pp. 801–804.
[53] B. E. Stine, D. S. Boning, and J. E. Chung, “Analysis and Decomposition of Spatial
Variation in Integrated Circuit Process and Devices,” IEEE Transactions on Semiconductor Manufacturing, vol. 10, no. 1, pp. 24–41, Feb. 1997.

Bibliography128[54] L.-T. Pang and B. Nikolic, “Impact of Layout on 90nm CMOS Process Parameter Fluctuations,” in IEEE Symposium on VLSI Circuits Digest of Technical Papers, 2006, pp.
69–70.
[55] L. Pileggi, H. Schmit, A. J. Strojwas, P. Gopalakrishnan, V. Kheterpal, A. Koorapaty, C. Patel, V. Rovner, and K. Y. Tong, “Exploring Regular Fabrics to Optimize the
Performance-Cost Trade-Oﬀ,” in Proceedings of ACM/IEEE 40th Design Automation
Conference, 2003, pp. 782–787.
[56] V. Kheterpal, V. Rovner, T. G. Hersan, D. Motiani, Y. Takegawa, A. J. Strojwas, and
L. Pileggi, “Design Methodology for IC Manufacturability Based on Regular Logic
Bricks,” in Proceedings of ACM/IEEE 42nd Design Automation Conference, 2005, pp.
353–358.
[57] L. W. Liebmann, “Layout Impact of Resolution Enhancement Techniques: Impedimentor Opportunity?” in Proceedings of ACM International Symposium on Physical Design,
2003, pp. 110–117.
[58] X. Yuan, K. W. McCullen, F.-L. Heng, R. F. Walker, J. Hibbeler, R. J. Allen, and R. R.
Narayan, “Technology Migration Technique for Designs with Strong RET-driven Layout Restrictions,” in Proceedings of ACM International Symposium on Physical Design,
2005, pp. 175–182.
[59] Mentor Graphics, Corp., Calibre xL User’s Manual, 2005.
[60] Synopsys, Inc., HSPICE Simulation and Analysis User Guide, 2005.
[61] Mentor Graphics, Corp., Calibre Mask Data Preparation User’s Manual, 2005.

List of Publications
Journal Papers
1. T. Iizuka, M. Ikeda, and K. Asada, “High Speed Layout Synthesis for Minimum-Width
CMOS Logic Cells via Boolean Satisfiability,” IEICE Transactions on Fundamentals
of Electronics, Communications and Computer Sciences, vol. E87-A, no. 12, pp. 3293–
3300, Dec. 2004.
2. T. Iizuka, M. Ikeda, and K. Asada, “Yield-Optimal Layout Synthesis of CMOS Logic
Cells by Wiring Fault Minimization,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E88-A, no. 7, pp. 1957–1963,
Jul. 2005.
3. T. Iizuka, M. Ikeda, and K. Asada, “Exact Minimum-Width Transistor Placement for
Dual and Non-Dual CMOS Cells,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E88-A, no. 12, pp. 3485–3491, Dec.
2005.
4. T. Iizuka, M. Ikeda, and K. Asada, “Timing-Aware Cell Layout De-Compaction for
Yield Optimization by Critical Area Minimization,” IEEE Transactions on Very Large
Scale Integration Systems. (submitted)

129

List of Publications

130

International Conference Papers
1. T. Iizuka and K. Asada, “An Exact Algorithm for Practical Routing Problems,” inProceedings of the Third IEEE Asia-Pacific Conference on ASICs, pp. 343–346, Aug.
2002.
2. T. Iizuka, M. Ikeda, and K. Asada, “High Speed Layout Synthesis for Minimum-Width
CMOS Logic Cells via Boolean Satisfiability,” in Proceedings of IEEE/ACM Asia andSouth Pacific Design Automation Conference, pp. 149–154, Jan. 2004.
3. T. Iizuka, M. Ikeda, and K. Asada, “Exact Wiring Fault Minimization via Comprehensive Layout Synthesis for CMOS Logic Cells,” in Proceedings of IEEE International
Symposium on Quality Electronic Design, pp. 377–380, Mar. 2004.
4. T. Iizuka, M. Ikeda, and K. Asada, “Minimum-Width Transistor Placement Without
Dual Constraint for CMOS Cells,” in Proceedings of ACM Great Lakes Symposium on
VLSI, pp. 74–77, Apr. 2005.
5. T. Iizuka, M. Ikeda, and K. Asada, “Timing-Driven Cell Layout De-Compaction for
Yield Optimization by Critical Area Minimization,” in Proceedings of IEEE/ACM
Design, Automation and Test in Europe, pp. 884–889, Mar. 2006.
6. T. Iizuka, M. Ikeda, and K. Asada, “Exact Minimum-Width Multi-Row Transistor
Placement for Dual and Non-Dual CMOS Cells,” in Proceedings of IEEE International
Symposium on Circuits and Systems, pp. 5431–5434, May 2006.
7. T. Iizuka, M. Ikeda, and K. Asada, “Timing-Driven Redundant Contact Insertion forStandard Cell Yield Enhancement,” in Proceedings of IEEE International Conference
on Electronics, Circuits and Systems, pp. 704–707, Dec. 2006.
8. T. Iizuka, M. Ikeda, and K. Asada, “OPC-Friendly De-Compaction with Timing Constraints for Standard Cell Layouts,” IEEE International Symposium on Quality Electronic Design, Mar. 2007. (to appear)
9. T. Iizuka, M. Ikeda, and K. Asada, “Timing-Aware Cell Layout Regularity Enhancement for Reduction of Systematic CD Variation,” ACM/IEEE 44th Design Automation
Conference, Jun. 2007. (submitted)

List of Publications

131

Domestic Conference Papers
1. T. Iizuka, M. Ikeda, and K. Asada, “An Exact Algorithm for Practical Routing Problems,” in Proceedings of IEICE Society Conference, A-3-6, p. 61, Sep. 2002.
(in Japanese)
2. T. Iizuka, M. Ikeda, and K. Asada, “Cell Layout Synthesis via Boolean Satisfiability,”in Proceedings of IPSJ DA Symposium, pp. 139–144, Jul. 2003. (in Japanese)
3. T. Iizuka, M. Ikeda, and K. Asada, “Exact Wiring Fault Minimization via Comprehensive Layout Synthesis for CMOS Logic Cells,” IEICE Technical Report, vol. 103,
no. 476, pp. 157–161, Nov. 2003. (in Japanese)
4. T. Iizuka, M. Ikeda, and K. Asada, “Minimum-Width Transistor Placement Method
via Boolean Constraints for Non-Complementary Transistors,” in Proceedings of IPSJDA Symposium, pp. 121–126, Jul. 2004. (in Japanese)
5. T. Iizuka, H. Yoshida, M. Ikeda, and K. Asada, “Hierarchical Layout Synthesis for
CMOS Logic Cells via Boolean Satisfiability,” IEICE Technical Report, vol. 104,
no. 478, pp. 1–6, Dec. 2004. (in Japanese)
6. T. Iizuka, M. Ikeda, and K. Asada, “Computational Cost Reduction for MinimumWidth Transistor Placement of Arbitrary Circuit Structures,” in Proceedings of IPSJDA Symposium, pp. 121–126, Aug. 2005. (in Japanese)
7. T. Iizuka, M. Ikeda, and K. Asada, “Timing-Driven Cell Layout De-Compaction for
Yield Optimization by Critical Area Minimization,” IEICE Technical Report, vol. 105,
no. 442, pp. 79–84, Dec. 2005. (in Japanese)
8. T. Iizuka, M. Ikeda, and K. Asada, “Exact Minimum-Width Multi-Row Transistor
Placement for Dual and Non-Dual CMOS Cells,” in Proceedings of IEICE Society
Conference, A-3-20, p. 64, Sep. 2006. (in Japanese)List of Publications

132

Awards
1. IEICE Young Researcher’s Award
T. Iizuka, M. Ikeda, and K. Asada, “An Exact Algorithm for Practical Routing Problems,” in Proceedings of IEICE Society Conference, A-3-6, p. 61, Sep. 2002.
(in Japanese)
2. Inose Science Award from Association for Promotion of Electrical, Electronic and Information Engineering, Jul. 2003.
3. Outstanding Paper Award from IPSJ SIGSLDM
T. Iizuka, M. Ikeda, and K. Asada, “Minimum-Width Transistor Placement Method
via Boolean Constraints for Non-Complementary Transistors,” in Proceedings of IPSJDA Symposium, pp. 121–126, Jul. 2004. (in Japanese)
4. Nikkei-BP LSI IP Design Award (Development Promotion)
T. Iizuka, M. Ikeda, and K. Asada, “Yield-Optimized CMOS Logic Cell Layout IP
Synthesis System”, May 2005. (in Japanese)
5. IPSJ Yamashita SIG Research Award
T. Iizuka, M. Ikeda, and K. Asada, “Computational Cost Reduction for MinimumWidth Transistor Placement of Arbitrary Circuit Structures,” in Proceedings of IPSJDA Symposium, pp. 121–126, Aug. 2005. (in Japanese)
6. Nikkei-BP LSI IP Design Award (IP Award)
T. Iizuka, M. Ikeda, and K. Asada, “Yield-Optimized Standard Cell Layout IP Synthesis System”, May 2006. (in Japanese)
7. Best Student Paper Award from IEEE International Conference on Electronics, Circuits
and Systems
T. Iizuka, M. Ikeda, and K. Asada, “Timing-Driven Redundant Contact Insertion forStandard Cell Yield Enhancement,” in Proceedings of IEEE International Conference
on Electronics, Circuits and Systems, pp. 704–707, Dec. 2006.