This dissertation focuses on optimal generation of design-specific cell libraries. In cell-based integrated circuit design, a cell library defines the final quality of a design. Hence, use of a general-purpose cell library may lead to a poor quality. We address various issues regarding optimal generation of design-specific cell libraries, targeting high-performance digital circuit design.

The goal of the first part of the dissertation is to provide the key components required to successfully realize the automatic generation of design-specific cell libraries, which consists of cell logic type selection and drive strength type selection.

Chapter 2 addresses feasibility issues on transistor-level optimization. During transistor-level optimization, cell layout synthesis and characterization steps are the major bottlenecks with respect to runtime. To resolve this drawback, we present a fast and accurate prelayout estimation technique of cell characteristics. Our estimation technique is based on quick transistor placement. Given a transistor-level circuit of a cell, layout parasitics are estimated using quick transistor placement. Then, the cell is characterized by simulating an estimated circuit which is built according to the estimated layout parasitics. Experimental results on a 0.13um industrial standard cell library demonstrate that the proposed technique estimates the cell characteristics with a reasonable accuracy in a negligibly small amount of time.

Chapter 3 addresses a cell logic type selection problem for design-specific cell libraries. Our methodology consists of two steps: logic-rich cell library generation and cell logic type count minimization. We propose a cell logic type count minimization method which minimizes the logic type count iteratively under performance constraints. Experimental results on the ISCAS 85 benchmark suite in an industrial 90nm technology demonstrate that it is feasible to find the minimal set of cell logic types under performance constraints.

Chapter 4 addresses a performance-constrained cell count minimization problem for continuously-sized circuits. After providing a formal formulation of the problem, we propose an effective heuristic for the problem. The proposed hill-climbing heuristic iteratively minimizes the number of cells under performance constraints such as area, delay and power. Experimental results on the ISCAS 85 benchmark suite in an industrial 90nm technology demonstrate its effectiveness. We also discuss several implementation issues towards a practical application of the proposed method to large-scale circuits.

The second part of the dissertation focuses on transistor-level topology synthesis, which is an important component in the manual generation phase where portions of a circuit are manually identified and cells for the portions are synthesized at the transistor level. We present three transistor-level topology synthesis methods. Although their objectives are to minimize the transistor count, they have different solution spaces. Combining these methods, the minimum solution in larger solution space can be obtained.

Chapter 5 presents a method for synthesis of minimal static CMOS circuits where the solution space is restricted to the circuit structures which can be obtained by performing algebraic transformations on an arbitrary prime-and-irredundant two-level circuit. The circuit structures are implicitly enumerated via structural transformations on a single graph structure, then a dynamic-programming based algorithm efficiently finds the minimum solution among them. Experimental results on a benchmark suite targeting standard cell implementations demonstrate the feasibility of the proposed procedure. We also demonstrate the efficiency of the proposed algorithm by a numerical analysis on randomly-generated problems. It is also shown that the proposed procedure sometimes generates significantly smaller circuits compared to conventional approach.

Chapter 6 presents an exact method for minimum logic factoring which can be viewed as the synthesis of a static CMOS compound gate. We first introduce a novel graph structure, called an X-B (eXchanger Binary) tree, which implicitly enumerates binary trees. Using this X-B tree, the factoring problem is compactly transformed into a quantified Boolean formula (QBF) and is solved by general-purpose QBF solver. Experimental results on artificially-created benchmark functions show that the proposed method successfully finds the exact minimum solutions to the problems with up to 12 literals.

Chapter 7 studies the synthesis of read-once switch networks in which every variable appears only once. The proposed procedure is based on the notions of prime implicants and unateness, which establish a basis for Boolean expression synthesis. We also propose a pruning technique for an efficient search. Experimental results on randomly-generated problems with up to 20 switches demonstrate that the proposed procedure successfully solves about 90% of the problems in 10 minutes each and the resulting read-once switch networks are up to 78% smaller compared to series-parallel switch networks.

Chapter 8 conducts an experimental study using a circuit consisting of C432 and C499 from the ISCAS 85 benchmark suite as a design example. We compare the circuits synthesized with a typical cell library and optimal design-specific libraries in an industrial 90nm technology, and demonstrate that using the design-specific cell libraries, the area-delay tradeoff curve is shifted to the left-bottom from that using the typical library. Comparing between the area-optimal circuits, the area is improved by 27.3%. And, comparing between the delay-optimal circuits, the maximum delay is improved by 22.4%. These results clearly prove the effectiveness of the flow and the key components for optimal generation of design-specific cell libraries.

　本論文は「Optimal Generation of Design-Specific Cell Libraries(設計固有セルライブラリの最適生成手法)」と題し、論理集積回路のセルベース設計毎に特化したセルライブラリを最適自動的合成する手法について研究したもので、英文で記述され九章より構成されている．

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

　第二章は「Cell Characteristics Estimation Using Quick Transistor Placement(トランジスタの高速配置を用いたセル特性の推定)」と題し、与えられたセル回路のトランジスタネットワークから論理段を分離抽出して各論理段内の詳細配置を高速に推定し、その推定配置をもとにセルの遅延時間、消費電力、セル面積、入力容量等のセル特性を高精度で予測する手法について述べている．

　第三章は「Logic Type Selection for Design-Specific Cell Library(設計固有セルライブラリのための論理タイプ選択)」と題し、与えられた設計に適したセルライブラリが含むべき論理タイプの選択手法について述べている．一定の制約の下で全ての論理タイプを網羅的に生成したあと、複数の異なる駆動力を持つセルライブラリを合成し、最後に論理タイプの数を最小化する経験的手法について述べており、幾つかの実験結果をもとにその有効性を検証している．

　第四章は「Performance-Constrained Cell Count Minimization for Continuously-Sized Circuits(連続的にサイジングした回路を対象とした性能制約下でのセル数最小化)」と題し、セル回路の各トランジスタ寸法を連続的に最適化することを前提としたセル特性のモデル化手法を提案している．次にそれにもとづき、与えられた性能制約下でセルの種類を最小化する手法を述べ、実験的にその有効性を検証している．

　第五章は「Synthesis of Minimal Static CMOS Circuits(最小スタティックCMOS回路の合成)」と題し、一定の制約下で最小の多入力-多出力-多段スタティックCMOS回路を合成する効率的手法について述べている．回路をAND2/INVのネットワークで表現したマッピンググラフを構成することで、網羅的に回路を生成・評価して最小の回路を発見する手法であり、ベンチマーク回路に応用することでその有効性を検証している．

　第六章は「Exact Minimum Logic Factoring via Quantified Boolean Satisfiability(限量子付き論理充足可能性判定問題による厳密最小論理因数分解)」と題し、与えられた論理関数を厳密に最小の直並列トランジスタ回路として合成する手法について述べている．論理関数を実現する回路を網羅的に表現できる枝交換表現を内包する「X-B木」を定義し、木の「枝交換状態」を表すパラメータを変数とした限量子付き論理充足可能性判定問題の解法プログラムを用いて、厳密に最小な直並列CMOS回路を発見する手法について提案している．

　第七章は「Synthesis of Read-Once Switch Network(リードワンススイッチ回路網の合成)」と題し、各論理入力でゲートが制御されるトランジスタが一個に限定されたスイッチ回路網(リードワンススイッチ回路網)の構成論的合成手法について述べている．リードワンススイッチ回路網で与えられた論理関数を合成可能な場合には、最小のトランジスタで実現される回路であることが保証されている．いくつかの合成実験結果をもとにその合成手法の有効性と限界を述べている．

　第八章は「Optimal Generation of Design-Specific Cell Libraries: A Case Study(設計固有セルライブラリの最適生成：ケーススタディ)」と題し、本論文で提案している手法を組み合わせて、ベンチマーク回路に対して最適生成したセルライブラリと従来から用いられている標準的セルライブラリとを比較した実験結果を示し、本論文で合成したセルライブラリが遅延時間-回路面積の観点で従来のものに比較して20〜30%程度のコスト低減効果があることを示している．

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

　以上、本論文は論理集積回路のセルベース設計において、設計固有の最適化セルライブラリを自動合成する手法を提案し、従来の標準セルライブラリに比較して遅延時間-回路面積コスト低減に有効であることを実験的に示したもので電子工学の発展に寄与する点が少なくない．

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