The recent progress in VLSI process technologies enables us to integrate a large number of 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 designing VLSIs is the cell-based design. In this design flow, we use a standard-cell library. The characteristics of cells including cell delay, area, and power as well as yield 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 application-specific and semi-custom domains. Therefore, their performance has significant effects on the final performance of the synthesized VLSI. This thesis focuses on the optimization methods for standard-cell layouts. We propose minimum-width transistor placement and intra-cell routing via Boolean satisfiability to optimize the area of the cell layouts. We also propose a comprehensive cell layout 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 the 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 with the case of pairing the complementary P and N type transistors. Our 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 with cell layout compaction. This result shows that our cell layout styles defined for the SAT formulation is practical enough to generate the layout 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 to 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 a given transistor-level netlist into blocks considering the transistor connections by diffusions. Intra-block placement uses an exact transistor placement method proposed in Chapter 2, and hierarchically generates the transistor placement with routability. The comparison results with the flat cell layout synthesis method for 30 benchmark circuits show that the proposed method generates the same width layout as the flat method except one circuit and drastically reduces the runtime for cell layout synthesis. The comparison results with the commercial cell generation tool without cell layout compaction show that the total cell width of 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 can conclude that the proposed method can be used as a quick layout generator in the area 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 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-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 conventional exact transistor placement method is applicable only to dual CMOS cells. Since non-dual CMOS cells occupy a major part of an industrial standard-cell library, the exact minimum-width transistor placement should be applied even to non-dual CMOS cells. 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. The experimental results show that it is not only applicable to CMOS cells with any types of structure, but also more effective even for dual CMOS cells compared with the transistor placement method only for dual cells. The hierarchical single-row approach which is based on circuit partitioning reduces the runtime drastically and generates 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 method for dual cells generates 43% and 32%, respectively. This chapter also shows the generalization results of the single-row transistor placement method into the multi-row placement and proposes an exact minimum-width multi-row transistor placement method for general CMOS cells. The experimental results of the multi-row placement method show that the proposed method generates more area-efficient placement than the conventional method only for dual cells by using the gate connection 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 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 effect of critical areas. The effect of the sensitivity reduction on the yield 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 selected from the exhaustively-generated layouts by using the proposed sensitivity to wiring faults as a cost function. 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. The experimental results on our comprehensive layout synthesis method to 8 CMOS logic circuits which have up to 14 transistors show that the fault sensitivities are 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 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 the original 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 as LP, a new accurate linear delay model which approximates the difference from the original delay is also proposed. The effectiveness of the proposed method for OPC mask data volume reduction is also shown in this chapter. This timing-aware de-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 parametric yield 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). Experimental results show that the developed delay model is accurate enough to constrain the delay during de-compaction. The CA is correctly minimized under given timing constraint, and the maximum CA reduction is about 25% on an average of 8 cells. Experimental results on a 90nm cell layouts show that the proposed method is also effective for OPC mask data volume reduction and reduces the fractured mask data size 4.28% on an average in the case that 10% delay increase is allowed. The proposed redundant contact insertion method under the timing-aware de-compaction framework inserts the redundant contacts as many as possible under given timing and area constraints using LP. The extension of the de-compaction method to a gate layout pattern regularity enhancement is also shown to be effective 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 edge placement error (EPE) estimation shows that the standard deviation of the gate CD EPE distribution is reduced by about 28% compared with that of the original layouts. The proposed timing-aware yield enhancement method enables us to explore the trade-off between performance and yield. We can pick up the yield/performance variants from the trade-off curve and provide a yield-enhanced library. The proposed method is the essential technique to realize the yield-aware VLSI design methodologies.

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 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 and reliability improvements.

　本論文は「Optimal Layout Synthesis of Standard Cells in Large Scale Integration(大規模集積回路におけるスタンダードセルレイアウトの最適自動合成手法」と題し、論理集積回路で用いられる標準セル回路の面積、遅延、歩留まり等をコスト関数として最適レイアウトを自動合成する手法について研究したもので、英文で記述され七章より構成されている．

　第一章はIntroduction(序論)であり研究の背景と研究の目的、および論文の構成を述べている．

　第二章は「Exact Minimum-Width Cell Layout Synthesis for Dual CMOS Cells(双対型CMOSセルの厳密最小幅セルレイアウト合成)」と題し、p型トランジスタ回路部とn型トランジスタ回路部が双対性を有するCMOS回路を対象として、一定のセル高さ制約の下で最小幅のレイアウトを合成する手法を提案している．トランジスタの配置、ソース・ドレインの向きおよび配線をブール代数の充足判定問題(SAT)として定式化する手法を提案し、厳密に最小幅を有するセルレイアウトを合成できることを示すとともに、2値の整数線形計画法による方法と比較し、その優位性を示している．またコンパクションを併用する経験的アルゴリズムの商用ツールとも比較して、コンパクション前であっても3%程度の面積増で合成できることを示している．

　第三章は「Hierarchical Extension for Large Cell Layout Synthesis(大規模セルレイアウト合成のための階層的拡張)」と題し、第二章で述べている厳密解法をより大きなセル回路へ応用するための階層化設計手法について述べている．トランジスタ回路のブロック分割手法、ブロック内配置、ブロック配置、およびセル内配線法を定式化し、階層化により僅かの幅増加の場合があるものの、大幅な計算時間の短縮と大きなセルへの適用が可能であることを実験的に示している．

　第四章は「Exact Minimum-Width Transistor Placement for General CMOS Cells(一般のCMOSセルの厳密最小幅トランジスタ配置)」と題し、双対性の制約を外したCMOSセル回路を対象として、一定の高さ制約の下で最小幅のセル合成のためのトランジスタ配置を自動生成する手法を提案している．配置様式については複数行を持つ配置に拡張する手法を示し、大きな回路に対する階層化設計手法についても示し、ベンチマーク回路を用いてその有効性を示している．

　第五章は「Yield-Optimal Cell Layout Synthesis for CMOS Logic Cells(CMOS論理セルのための歩留まり最適化セルレイアウト合成)」と題し、与えられた論理を実現する最小幅セルレイアウトの中で配線のパーティクル欠陥歩留まりを決定するクリティカル面積が最小のセルレイアウトを合成する手法を提案している．第二章で提案した厳密最小幅合成手法を拡張し、網羅的にセルレイアウトを生成する手法と、クリティカル面積計算アルゴリズムを併用する方法である。ベンチマーク回路を用いて最小配線長レイアウトに比較して本手法で合成したレイアウトが15%程度クリティカル面積が実効的に小さくなることを示している．

　第六章は「Yield Optimization by Timing-Aware Cell Layout De-Compaction(タイミングに配慮したレイアウト伸張による歩留まり最適化)」と題し、与えられた遅延制約のもとで、セルレイアウトの幅を最適に伸張することにより、パーティクル欠陥歩留まりを決定するクリティカル面積を最小化する線形計画法にもとづく手法を提案している．また同様の伸張方法を用いて、マスク製作時の光学近接補正によるショット数増加の抑制、冗長コンタクト挿入によるコンタクト欠陥救済、規則性向上によるパラメタバラツキ抑制のためにも応用できることを示し、ベンチマーク回路を用いてその有効性を示している．

　第七章は「結論」であり本論文の研究成果をまとめている．

　以上、本論文は大規模集積回路で用いられる標準セル回路のレイアウトの最適自動合成手法を提案し、面積最小セル合成、歩留まり最適化セル合成およびマスクショット数最適化セル合成等に適用することでその有効性を示したもので電子工学の発展に寄与する点が少なくない．

　よって本論文は博士(工学)の学位請求論文として合格したものと認められる．