WO2000060660A1

WO2000060660A1 - Procede de conception d'un dispositif a semi-conducteur et support d'enregistrement exploitable sur ordinateur

Info

Publication number: WO2000060660A1
Application number: PCT/JP1999/001729
Authority: WO
Inventors: Kazuhiko Eguchi; Toshiyuki Majima; Teruya Tanaka; Kenji Oshima
Original assignee: Hitachi, Ltd.
Priority date: 1999-04-01
Filing date: 1999-04-01
Publication date: 2000-10-12

Description

明細書半導体装置の設計方法及びコンピュータ読み取り可能な記録媒体技術分野

本発明は、半導体装置の設計技術に関し、特に V L S I (Very Large Scale Integration) などの集積回路を実装する半導体チップ設計の初心者に対して、複雑な設計の開始段階でよい初期条件を与えることができる半導体装置の設計方法、およびその設計方法を実現するためのプログラムを記録したところのコンビユータ読み取り可能な記録媒体に適用して有効な技術に関する。背景技術

本発明者が検討した技術として、 V L S Iなどの集積回路を実装する半導体装置の設計は、システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、これにより得られた設計データに基づいて集積回路を論理ゲートレベルで論理設計を行う論理設計工程と、これにより得られた設計データに基づいて論理ゲートをトランジスタレベルで回路設計を行う回路設計工程と、論理設計工程により得られた設計データと、回路設計工程により得られた設計データとに基づいて論理ゲートの配置 ·配線を行うレイァゥト設計工程などを含み、設計技術者によりシステム仕様を満足するように前記各設計工程が進められ、以降の製造 ·試験工程を経て半導体装置が完成されるようになつている。

たとえば、前記レイアウト設計工程において、 V L S Iのフロアプランとは、 V L S Iチップ上における機能ブロックの概略相対配置を決めることである。いわゆるスタンダードセルと呼ばれる、プリミティブな論理構成要素であるセル（ N A N Dゲート、 N O Rゲート、フリップフロップなど）によって構成されるランダムロジック回路の配置問題は、長年に渡る、数多くの研究者の努力により極めて高度に自動化されており、かつそれをインプリメントした有効な E D A ( Electronic Design Automation) ツーノレ力レヽくつ力、商品ィ匕されてレヽる。

しかし、近年の高度な V L S Iはスタンダードセルの部分だけではなく、大きなメモリブロック、 C P Uモジュール、数多くの周辺機器のブロック、時にはァナログモジュールなども搭載する。従って、これらのブロックの相対配置を決めるフロアプランは、最終的なチップのサイズと性能を決定付ける重要な設計工程となっている。既に、いくつかのフロアプランツールが商品化されており、これらはチップ設計を支援する有益な情報を提供してユーザーフレンドリーなフロアプラン操作の環境を提供するが、基本的には編集ツールである。

実際の設計現場では、このフロアプランの配置判断はいまだに設計者の洞察力に頼っている。そして、その結果「誰が」やったかに強く依存する。かつ、この作業は手間がかかる仕事であり、一般的に熟練技術者はより短い時間で、初心者あるいはまだ経験が十分でない技術者よりよい結果を与える。しかし、熟練技術者であっても設計完了までに要する時間は最初にどんな情報が与えられたかに依存する。非熟練技術者の場合は、設計結果である最終チップの設計品質、設計完了までに要する時間もどのような初期値が与えられたかに強く依存する。

そこで、前記のような V L S Iのフロアプランについて、本発明者が検討した結果を以下に示す。すなわち、本発明においては、自動設計によって一度に最終設計結果を与えることよりも、熟練技術者、非熟練技術者を問わず、フロアブラン設計開始に当たってのよりよい初期値を与えるにはどうしたらよいかを主眼とする。このアプローチとして、

( 1 ) 最適化処理手法（たとえば遺伝的アルゴリズム）によりグローバル最適化問題として解くことを試みた。

( 2 ) 実際の設計現場には熟練技術者の知見とノウハウがいっぱいあるが、言語以前の形態で伝えられているものも多い。これらを自然言語の形である程度整理し、フアジィルール化を試みた。

( 3 ) 前項で得られたフアジィルールを基にマクロなプロックの初期配置の推論を試みた。全部のブロックをフアジィ推論で求めるのはルールの複雑化とパラメ

—タ調整の困難化を招き現実性から遠ざかる。しかし、いくつかの決定優先度の高いプロックはファジィ推論で十分決定できる有意性を確かめた。

( 4 ) 前項のフアジィ推論で求めた配置情報を遺伝的アルゴリズムの初期データ生成に応用し、フアジィ推論で実用的に決定できるプロックはそのままにして、ファジィ推論で配置決定することに有意性が少ない、または無いプロックは遺伝的ァルゴリズムの最適化問題解決に任せる手法を考えた。

( 5 ) 上記（1 ) か ( 4 ) 項をインプリメントする実験プログラムを開発し、計算機実験を行い、対象例によっては熟練技術者の設計結果に迫る結果を得ることができた。

詳細は後述するように、この例では、 3種類の例題について、熟練技術者による設計結果と遺伝的アルゴリズムだけによる結果、初期世代の生成にフアジィ推論を採用した結果の比較を示す。遺伝的アルゴリズムだけの場合は、熟練技術者による結果とはまだ大きな開きがあるが、フアジィ推論との組み合わせでは人間が設計した結果に近い結果を得ることもできる見通しを得た。たとえば、遺伝的アルゴリズムなどの最適化処理手法だけを用いた技術としては、特開平 1 0— 2 7 5 1 7 5号公報に記載される技術などがある。

そこで、本発明の目的は、フロアプラン設計、さらに論理クラスタ分割の開始に当たってのよりよい初期値を与えることができ、特に半導体チップ設計などの複雑な設計の開始段階でよい初期条件を与えることができる半導体装置の設計方法、さらにこの設計方法をプログラムとして記憶したコンピュータ読み取り可能な記録媒体を提供するものである。

本発明の前記ならぴにその他の目的と新規な特徴は、本明細書の記述およぴ添付図面から明らかになるであろう。発明の開示

本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。

本発明によれば、前記（1 ) 〜（5 ) のアプローチに基づき、遺伝的アルゴリズムなどの最適化処理手法と、熟練技術者の知見とノウハウのフアジィルール化によるフアジィ推論とを採用した設計方法が提供される。

次に、さらに具体的に述べていくことにする。

本発明は、システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、これにより得られた設計データに基づいて集積回路を論理ゲートレベルで論理設計を行う論理設計工程と、これにより得られた設計データに基づいて論理ゲ一トをトランジスタレベルで回路設計を行う回路設計工程と、論理設計工程により得られた設計データと、回路設計工程により得られた設計データとに基づいて論理ゲートの配置 ·配線を行うレイァゥト設計工程と、を含む半導体装置の設計方法に、たとえば適用される。

すなわち、本発明の一例による半導体装置の設計方法では、前記各設計工程の設計データの作成において、フアジィ推論を用いて複数の設計データ群を作成する工程と、乱数的に複数の設計データ群を作成する工程と、前記各工程により作成された複数の設計データ群に基づいて、最適化処理手法を用いて適合度の高い設計データ群を選択する工程と、この選択された設計データ群に基づいて、最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計デ一タ群を選択しながら順次繰り返して、最適解となる設計データ群を作成するェ程が設けられる。

また、本発明による他の半導体装置の設計方法では、前記各設計工程の設計デ —タの作成において、フアジィ推論を用いて最適解となる一部分の設計データ群を作成する工程と、乱数的に複数の設計データ群を作成する工程と、この作成された複数の設計データ群に基づいて、最適化処理手法を用いて適合度の高い設計データ群を選択する工程と、この選択された設計データ群に基づいて、最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計データ群を選択しながら順次繰り返して、最適解となる他部分の設計データ群を作成する工程が設けられる。

さらに、本発明は、前記半導体装置の設計方法をコンピュータに実行させるためのプログラムを記録した、コンピュータ読み取り可能な記録媒体をも提供するものである。

特に、本発明は、前記レイアウト設計工程におけるフロアプランニングに適用し、最適化処理手法として遺伝的アルゴリズムを用い、遺伝的アルゴリズムの初期の設計データ群をフアジィ推論を用いて生成し、最適解となる設計データ群を用いて複数のブロックを半導体チップ上に配置するものである。さらに、このフロアプランニングにおけるコーディング、評価関数、突然変異、フアジィ推論については、それぞれ後述において詳細する特徴を有するものである。また、本発明は、前記論理設計工程における論理クラスタ分割に適用し、最適化処理手法として遺伝的アルゴリズムを用い、遺伝的アルゴリズムの初期の設計データ群をフアジィ推論を用いて生成し、最適解となる設計データ群を用いて複数のブロックをクラスタに分割するものである。さらに、この論理クラスタ分割におけるフアジィ推論、評価関数については、それぞれ後述において詳細する特徴を有するものである。

本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば、以下のとおりである。

( 1 ) 本発明の半導体装置の設計方法、コンピュータ読み取り可能な記録媒体によれば、遺伝的アルゴリズムなどの最適化処理手法と、技術者の知見とノウハウのフアジィルール化によるフアジィ推論とが採用され、レイアウト設計工程のフロアプランニングへ適用されることにより、フロアプラン設計開始に当たってのよりよい初期値を与えることができるようになる。特に、半導体チップ設計の初心者などに対して、複雑な設計の開始段階でよい初期条件を与えることが可能となる。

( 2 ) 本発明の半導体装置の設計方法、コンピュータ読み取り可能な記録媒体によれば、遺伝的アルゴリズムなどの最適化処理手法と、技術者の知見とノウハウのフアジィルール化によるフアジィ推論とが採用され、論理設計工程の論理クラスタ分割へ適用されることにより、論理クラスタの分割に当たってのよりよい初期値を与えることができるようになる。特に、半導体チップ設計の初心者などに対して、複雑な設計の開始段階でよい初期条件を与えることが可能となる。

( 3 ) この結果、本発明によれば、レイアウト設計工程のフロアプランニング、論理設計工程の論理クラスタ分割において、よりよい初期状態によるフロアブランニングと論理クラスタ分割とを提供することができるので、熟練技術者、非熟練技術者を問わず、半導体装置の設計における最終半導体チップの設計効率と設計品質との両面でよりよい効果を得ることができる自動設計を実現することが可能となる。図面の簡単な説明

図 1は本発明の一実施の形態である半導体装置の設計方法を示すフロー図、図 2は本実施の形態の半導体装置において、フロアプランニング例を示す説明図、図 3は遺伝的アルゴリズムを示すフロー図、図 4はコーディング例を示す説明図、図 5は配置モデル例を示す説明図、図 6は評価関数の評価項目例を示す説明図、図 7は突然変異例を示す説明図、図 8から図 1 0はテストデータ例を示す説明図、図 1 1から図 1 3は遺伝的アルゴリズムの実験結果例を示す説明図、図 1 4およぴ図 1 5はフアジィ推論のルール例を示す説明図、図 1 6はメンバーシップ関数例とフアジィ変数例を示す説明図、図 1 7は実験的ソフトウェアのシステム例を示す構成図、図 1 8はハードウェアのシステム例を示す構成図、図 1 9は初期世代の推論例を示す説明図、図 2 0はファジィ推論による初期配置例を示す説明図、図 2 1は遺伝的アルゴリズムによる個体例を示す説明図、図 2 2から図 2 4はフアジィ推論と遺伝的アルゴリズムの実験結果例を示す説明図、図 2 5はコストの経過例を示すグラフ、図 2 6から図 2 8は論理クラスタ分割例を示す説明図、である。発明を実施するための最良の形態

以下、本発明の実施の形態を図 1〜図 2 8の図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において同一の部材には同一の符号を付し、その繰り返しの説明は省略する。

まず、図 1により本実施の形態の半導体装置の設計方法の一例を説明する。本実施の形態の半導体装置の設計方法は、たとえば V L S Iチップの設計方法とされ、システム仕様に基づいて集積回路の機能設計を行う機能設計工程（S 1 0 1 ) と、これにより得られた設計データに基づいて集積回路を論理ゲートレべルで論理設計を行う論理設計工程（S 1 0 2 ) と、これにより得られた設計データに基づいて論理ゲートをトランジスタレベルで回路設計を行う回路設計工程（ S 1 0 3 ) と、論理設計工程により得られた設計データと、回路設計工程により得られた設計データとに基づいて論理ゲートの配置 ·配線を行うレイァゥト設計工程（S 1 0 4 ) などからなり、これらの設計工程により得られた設計データに基づいてチップ製造工程（S I 05) が行われ、さらにパッケージング 'テステイング工程 (S 106) を経て半導体装置が完成されるようになっている。

本実施の形態においては、各設計工程の設計データを作成する際に、遺伝的ァルゴリズムなどの最適化処理手法と、熟練技術者の知見とノゥハウのフアジィルール化によるフアジィ推論とを用いて、フアジィ推論で求めた配置情報を遺伝的アルゴリズムの初期データ生成に応用し、フアジィ推論で実用的に決定できるブロックはそのままにして、フアジィ推論で配置決定することに有意性が少ない、または無いプロックは遺伝的アルゴリズムの最適化問題解決に任せる手法を採用したものである。

次に、ステップ S 104のレイアウト設計工程におけるフロアプランニングに適用した一例を、たとえば図 2に示すように、内部領域に各ブロック 1 (#0〜 #9) が配置され、その周辺部に I ZOバッファ 2が配置されるような VL S I チップの配置 '配線について、各項目別に順に説明する。ここでは、 3種類の例題について、遺伝的アルゴリズム、フアジィ推論を用いた例を示す。

1. 遺伝的アルゴリズムによるフロアプランニング

この遺伝的アルゴリズムの ED Aに対する幾つかの例は、主としてこのアルゴリズムの最適化の能力および局所的最適化を回避する能力を目的物として得ることができる。ここでは、遺伝的アルゴリズムの VL S I設計のフロアプランニング段階での応用を提案することにより、半導体チップの設計の初心者であっても複雑な設計工程の開始時点において、よりよい初期条件を与えられるようにする技術である。

この遺伝的アルゴリズムの一般的な手順は、たとえば図 3に一例を示すように、まず、初期世代を設定し（S 301) 、評価関数による適合度を評価する（S 3 02) 。そして、次の世代への、エリート保存（S 303) 、選択 Z交差（S 3 04) 、突然変異（S 305) 、淘汰（S 306) を終了条件まで繰り返して行う（S 307) 。終了条件に達したことで終了となる。

1. 1. コーディング

コーディングとは、染色体と目的とする最適化問題との対応付けのことである。この例に関するコーディング方式を、たとえば図 4に示す。図 4 (a) はチップの内部領域に配置されるブロック 1、図 4 (b) は染色体の構造を表す。ここで、各ブロック 1の寸法を示す幅を W、高さを Hとして、その中心の X— Y座標を（ X i， Y i ) 、回転を R iとする。たとえば R i = 0の場合は縦長、 R i = 1の場合は横長の形状とする。

まず、図に示すような X— Y座標を定義する。この場合、ブロック 1の回転も考慮する。 3個の染色体を用意し、これらをそれぞれ X染色体、 Y染色体、回転染色体とする。図 4に示されている（X0， YO) に位置し、回転（R) が 0のブロック 1 (#0) を以下に示すように表す。

• X染色体の 0番目の遺伝子は X 0である。

· Y染色体の 0番目の遺伝子は Y 0である。

•回転染色体の 0番目の遺伝子は 0である。

次に、（X l， Y 1) に位置し、 90度回転したブロック 1 (# 1) を以下に示す。

♦ X染色体の 1番目の遺伝子は X 1である。

· Y染色体の 1番目の遺伝子は Y 1である。

•回転染色体の 1番目の遺伝子は 1である。

ブロック 1同士が重なりあったり、ブロック 1が枠からはみ出すことはこのコ一ディング方式では許容されている。この評価関数を評価することによってプロック 1同士の重なり合いやはみ出しを排除する方法を採用している。

1. 2. 遺伝的アルゴリズムのフロアプランニングに対する応用

目的物の配置のモデルを、たとえば図 5に示す。図 5 (a) はブロック 1の形状とネットリスト、図 5 (b) はチップ領域をそれぞれ表す。この図において矩形のブロック 1は配線経路により接続されて示されている。おのおのの矩形プロック 1の縦横比および寸法も示されている。この図にはそれぞれ寸法と縦横比が対応した半導体チップも示されている。基本的な操作は以下の通りである。

(1) 初期世代をランダムに発生させる。

(2) 評価関数を計算することにより適合度を評価する。

(3) 子孫を発生させる。エリート個体を保存する。選択、交差、突然変異を実行する。 (4) 2および 3の操作を繰り返す。

(5) 発生操作をある程度繰り返した後、最も良好な子孫を選択する。

1. 3. 評価関数

評価関数の構成要素のための最小アイテム数を熟練設計者のやり方を基に選択する。評価関数を評価するときは、ブロック 1間の実質配線長 L i、ブロック 1 同士の重複部分 S i、ブロック 1の指定領域からのはみ出し部分 OV iを考慮に入れる。評価関数パラメータの計算は、たとえば図 6に一例を示す。図 6 (a ) は実質配線長、図 6 (b) は重複部分、図 6 (c) ははみ出し部分をそれぞれ表す。 L iは接続本数により重み付けされた各プロック 1の実質中心間配線長であり、ブロック 1相互の配線長とブロック 1と I ZOバッファ 2との間の配線長とを含んでいる。ブロック 1と I /〇バッファ 2との間の配線経路はブロック 1同士の配線長に対して 1 0倍の重み付けを行っている。 I ZOバッファ 2の相互接続の総数はピンの本数により制限を受ける。 VL S Iの外部ピンの本数は数十本から数百本にわたり様々である。現在の技術では、 1 0 2 4本のピン本数まで対応可能である。一方、ブロック 1間の配線経路の本数は 1 0³から 1 0⁴のオーダ —である。しかしながら、 1配線経路当たり Ι ΖΟバッファ 2の接続による配置の品質に対する影響度は、経験によると、ブロック 1間の 1配線経路当たりのそれの 1 0倍から 2 0倍である。

評価関数 Εは下記の式 1によって与えられる。

E = a∑ L i + j3 ∑ S i + 7 ∑OV i · · · 式 1

ここで、 α, β , γは重み付けとしての調整係数である。各評価項目は図 6に示される。予備的な実験結果からひ = 1、 /3 = 1 0、 γ = 1 0 0 0が選定されている。

1. 4. 突然変異

突然変異とは、たとえば図 7に一例を示すように、前記図 4に示す染色体に対して（図 7 ( a ) ) 、選択されたブロック 1をある距離だけランダムに動かす（図 7 (b) ) とともに、選択されたブロック 1の向きをランダムに変更する（図 7 ( c ) ) ことである。この動かす距離はやはりランダムに決定されるが、ある決められた値よりも小さい値とする。プロック 1群の中でどれくらい突然変異を行うかの比率はプログラム可能であり、経験に基づいて決定される。

1 . 5 . テストデータ

実験を目的として、図 8、図 9、図 1 0に示すような 3つの例をテストデータとして用意した。テストデータは熟練した設計技術者により独自に設計されたものに基づいている。図 8および図 9に対応するテストデータ（1 ) および（2 ) は実際の設計の実施例から構成したものであり、図 1 0に対応するテストデータ

( 3 ) は、このアルゴリズムの性能を試すために意図的に作成したものである。図 8、図 9、図 1 0において、ブロック 1と I ZOバッファ 2間、ブロック 1間の配線は、本数に対応した幅となっている。

プログラムに適用されるものは、ネットリスト（内部のブロック 1および I Z

〇バッファ 2間の接続情報）、目的とするチップの寸法およびそれぞれのブロック 1の寸法に関するデータのみである。

1 . 6 . 遺伝的アルゴリズムの実験結果

図 1 1、図 1 2、図 1 3は、遺伝的アルゴリズムによりフロアプランニングを行った場合の結果を示す。各図の左側（a ) は、前記図 8から図 1 0の例に対応したもので、テストデータを用いて熟練者によって作成されたフロアプランを示している。右側の図（b ) は、実験的なプログラムにより作成された遺伝的アルゴリズムの設計結果を示している。それぞれの場合において、評価関数の値、すなわちコストは 6 0回から 6 5回の世代生成（繰り返し世代）で一定値に収束する。初期世代における個体の数は 2 0 0 0に設定してある。親から発生した子孫の数は 1 5 0 %であり、子孫の総数は合計で 3 0 0 0になる。ただし、次の世代を生む親となり得る個体の数は 2 0 0 0である。残りの 1 0 0 0個の個体は廃棄される。突然変異を発生させる比率は 8 %である。上述のケースでは生き残りェリートの数は 4 0である。

図 1 1によるテストデータ（1 ) の場合では、熟練設計者によって作成された設計例のコスト（すなわち評価関数の値）は 7 1 5 5である。この数字はブロック 1および I /Oバッファ 2間の実質配線長からなる。従って、この値が小さいほど良好な結果が得られたことになる。遺伝的アルゴリズムを用いて初期世代の数を 2 0 0 0とし、 7 0世代まで発生させた場合のコストは 9 7 6 6であった。 4 6世代まで発生させたとき、コストはこの値に達し、それ以降は向上が見られなかった。従って、局所的な最適値に収束してしまったと見なし得る。

遺伝的アルゴリズムに基づいた結果を観察すると、熟練設計者であれば、技術者としての個別的な経験に基づきブロック 1 ( # 9 ) 、ブロック 1 ( # 2 ) およぴブロック 1 ( # 8 ) の位置が不適切であると指摘できる。

テストデータ（2 ) の場合では、遺伝的アルゴリズムを用いてテストデータ（ 1 ) の場合よりも良好な結果を得ている。人手による設計ではコストは 5 0 0 1 であったが、遺伝的アルゴリズムにより発生させた設計ではコストは 5 2 6 6であった。しかしながら、ここでも熟練技術者であればブロック 1 ( # 2 ) とプロック 1 ( # 0 ) は交換されてしかるべきであることが指摘できる。

テストデータ（3 ) に関しては、遺伝的アルゴリズムに基づく結果は、 5 0世代目に評価関数が飽和した後でも依然として望ましい水準に達していない。この範囲ではまだかなりの改善の余地がある。

2 . 遺伝的ァルゴリズムの分析の問題

遺伝的アルゴリズムは、生物学の分野における進化の過程を蓋然論的にシミュレーシヨンしたものである。このアルゴリズムでは初期世代をランダムに、無作為化の方法ほし数発生法）により決定することが多いので、最終的な結果はこの初期条件にしばしば左右される。

遺伝的アルゴリズムは、一般的に全体的な最適化をめざすものであるが、最終結果は初期世代の組み合わせにかなり依存する。すなわち、突然変異の効果として発生する場合を除いて、初期世代の遺伝子の中に含まれていなかった情報を構成要素とする最終結果が生まれる可能性が極めて少ない。初期世代を構成する個体は多数そろえることで、よりよい結果を生み出すようにすることが必要である。しかしながら、初期世代に多数の個体を用意すると、それだけで計算時間が必要になる。さらに満足のいく結果を得るために何回くらいの世代生成が必要となるかを予測することは困難である。

3 . 遺伝的アルゴリズムにおける初期世代に対して適用するフアジィ推論の提案遺伝的アルゴリズムは、最適化問題を解決するには優れた方法であるが、上述したように、まだ多くの改善の余地がある。産業の現場には実務的経験と多くの知識の蓄積を有する多数の熟練者がいる。ここでは、熟練設計者の知識に基づいたフアジィ推論を、遺伝的アルゴリズムの操作における最適な初期条件の設定に応用する方法を提案する。

フアジィ理論は熟練者の知識に基づいて自動制御のシステムを構築する場合に幅広く応用されている。フアジィ理論は、対象物が厳格な数学方程式またはアルゴリズム的方法論によっては記述できないか、または記述することが困難である力その対象物の极いは言葉によってなら記述できるような場合に優れた適合性を発揮する。フアジィ理論に基づいた推論（フアジィ推論）は、自動制御の分野でよく知られている。

ここで、提案する方法は、経験を積んだ V L S I設計者の専門知識から抽出したフアジィ推論を遺伝的アルゴリズムにおける限られた初期条件を得るために応用するものである。フアジィ推論を適用するためには、専門家の知識を入手する必要がある。ただし、自然言語によって記述されたフロアプランニングの配置問題に適用される知識はしばしば複雑かつ曖昧である。

3 . 1 . 設計の知識

以下に示す一例は、 V L S I設計技術者がフロアプランニングをしているときに考える事柄（知識やノウハウ）を記したものである。なお、以下におけるモジュ一ルはブ口ック 1に対応する。

( 1 ) I ZOバッファ 2 (チップの周辺に配置される）の位置が与えられる。 ( 2 ) チップの外形ができる限り正方形になっているかどうかを確かめる。

( 3 ) チップの寸法ができる限り小さく設定されているかどうかを確かめる。

( 4 ) C P Uコアや R AMなどの比較的大きいブロック 1がチップの縁に沿って、できれば角に配置されているかどうかを確かめる。

( 5 ) Iノ Oバッファ 2との接続性の高いモジュール（ブロック 1 ) は、形状や寸法に関わりなくダイの周辺部、すなわちチップ領域の縁に沿って配置されるべきである。

( 6 ) そのモジュールの I ZOバッファ 2との接続性が低い場合は、モジュール (ブロック 1 ) 寸法がそれ程大きくないか、あるいはそのモジュールのその他のモジュールとの接続性が高い場合は、ダイの比較的中央部に配置されてもよい。 ( 7 ) I /Oバッファ 2と内側に配置されるモジュール（ブロック 1 ) との接続性は、遠心系と類似に考えることができ、また内側に配置されるモジュール同士の接続 14は求心系と類似に考えることができる。

( 8 ) モジュール（ブロック 1 ) 同士はもし相互に高い接続性を呈するのであれば、隣接して配置されるべきである。

上記のガイドラインは当然のことながら断定的なものではなく、実際の設計のシチュエーションでは、特性、性能、コスト、その他を比較考量して多くの一層詳しいガイドラインが必要となる。ただし、上述の情報に基づいて遺伝的ァルゴリズムの初期世代に対してファジィ推論を実施するときは、応用の一般性が損なわれることはない。

3 . 2 . フアジィのノレ一ノレ

以下の推論のためのルールは、上述の設計に関するガイドラインに基づいて導かれる。

( 1 ) チップの中心部付近に配置されるモジュール（ブロック 1 ) は、 I ZOバッファ 2に対して接続性の低いものを選び、このモジュールに対して接続性の高いモジュールは隣接する位置に配置する。ただし、この中心部付近に配置されるべきモジュールは、前述のルールにより選択されたモジュールである場合を除き比較的小さいモジュールであるべきである。

( 2 ) 隅に配置されるべきモジュール（ブロック 1 ) としては（4つの隅すベてに同様にいえることであるが）、寸法が大きく隣接するモジュールに対して中程度の接続性を有するものを選ぶ。

( 3 ) I ZOバッファ 2に対して比較的高い接続性を有するモジュール（プロック 1 ) は、有効チップ領域の周辺部に沿って配置されるべきである。ただし、前述のルールの適用の結果としてこの周辺領域が既に他のモジュールが割り当てられているときは、この限りではない。

ファジィ推論における上述のルールは、たとえばチップの中心部付近に配置されるモジュールに関しては図 1 4、チップの隅に配置されるべきモジュールに関しては図 1 5のようにそれぞれ示すことができる。たとえば図 1 4において、 I ZOバッファ 2との接続性が低く、他のモジュールとの接続性が高い場合におい W て、ブロック 1の寸法が小さい場合には適合度が高く、中程度の場合には中程度、大きい場合には適合度が低くなることを表している。他の場合においても同様である。

上述のフアジィのルールのために、メンバーシップ関数およびフアジィ変数が開発されている。たとえば、図 1 6は、実験的なソフトウェアにおいて採用されているメンバ一シップ関数およびフアジィ変数を示すもので、プロック 1の寸法、モジュール（ブロック 1 ) 間の接続性および I ZOバッファ 2との接続性を評価するためのものである。フアジィ変数のためのパラメータは熟練技術者の知識に基づいて決定される。

たとえば、図 16 (a) に示す I /Oバッファ 2との接続性については、配線量を正規化し、その平均値を 1. 0とした場合に、 1. 0以下で接続性が低く、 2. 0以上で接続性が高いとしている。図 16 (b) に示す他のモジュール（ブロック 1) との接続性についても、 0. 5以下で接続性が低く、 0. 8付近で接続性が中程度、 1. 3以上で接続性が高いとしている。また、図 16 (c) に示すブロック 1の寸法については、平均値を 1. 0にして、 0. 6以下で小さく、 1. 0付近で中程度、 3. 0以上で大きいとしている。さらに、適合度の高い、中程度、低い位置は図 16 (d) のようになる。

4. 実施

この提案の有効性を検証するための実験的なソフトウエアが開発されており、このソフトウェアの概要を図 17に示す。このソフトウェアにおいては、メインコントローラ 1 1により、前述したフアジィ推論 12、遺伝的アルゴリズム 13 の各機能を動作させ、結果出力 14を介して図面をリポートとして出力するような構成となっている。フアジィ推論 1 2の機能においては、パラメータと入力デ —タを読み込み（S 1 701) 、パラメータ調整の有無を判定し（S 1702) 、パラメ一タ調整が必要な場合にはパラメータを調整して（S 1 703) 、チップの中心部、隅に配置するブロック 1を推論する（S 1 704) 。この推論結果を遺伝的アルゴリズム 1 3の機能において、初期世代を発生し（S 1705) 、選択、交差、突然変異、エリート保存、淘汰を繰り返して実行する（S 1706) 。このソフトウェアは、たとえば図 18に示すように、前記メインコントローラ 1 1の他に、 R OM、 R AMなどの記憶装置 2 1、キーボード、マウスなどの入力装置 2 2、ディスプレイ、プリンタなどの出力装置 2 3、ディスク装置などの補助記憶装置 2 4などのハードウエアからなるコンピュータシステム上で動作するように構成されている。前記フアジィ推論 1 2、遺伝的アルゴリズム 1 3などの各アルゴリズムは、たとえば補助記憶装置 2 4に挿抜自在とされる C D— R O Mなどの記録媒体 2 5にプログラムとして記録され、このプログラムが記録媒体 2 5から記憶装置 2 1に読み出され、メインコントローラ 1 1の制御に基づいて各処理が実行される。

このソフトウェアでは、遺伝的アルゴリズム 1 3を適用するに先立って、前記 3 . 2において説明したフアジィのルールに基づいたフアジィ推論 1 2によりブロック 1の位置を推論する。このソフトウェアは、さらに必要があればフアジィ変数のためのパラメータを調整する。このパラメータ調整の手順は、逆方向伝達法 (Back propagation Method ；に従つ。

このソフトウエアでは、まずチップの中心部付近に配置するのに最も適したブロック 1を見い出すことを試みる。このソフトウェアでは、前記図 1 4に示したフアジィのルールおよび前記図 1 6において説明したメンバーシップ関数を採用している。この手続きにより選択されたプロック 1がチップの中心部に配置される。選択されたブロック 1は後続のステップの対象物から除外される。

次に、このソフトウェアでは、前記図 1 5において説明したフアジィのルールに基づいて各ブロック 1と各隅との適合値を評価する。メンバ一シップ関数は、上述したものと同様である。 4つの隅は左上、左下、右下および右上の 4隅である。ここでブロック 1 と隅との組み合わせの適合値を試算する。ブロック 1とこれが配置される隅との最良の組み合わせが最良の適合性をもたらす。そこで、選択された最良の組み合わせのブロック 1がその隅に配置され、さらに配置されたプロック 1がチップの境界線からはみ出していないことが確認される。

次に、このソフトウェアでは、残りのブロック 1の組み合わせを調べ、残りの隅に対するプロック 1の配置の仕方の候補を選択する。このソフトウェアでは、大きな数字から先に並べられた適合値に従って、各隅に対する最も適する候補を発見するように試みる。ただし、適合値の程度がある値よりも小さいときは、このソフトウエアでは推論のプロセスを終了し、 2つまたは 3つの候補を推薦するにとどめる。

一旦、推論の結果が得られると、従来の方法でも採用されている同様の方法に従って初期世代をランダムに発生させる（乱数発生）。推論されたブロック 1の遺伝子を推論の結果に基づいて書き換える。遺伝子の書き換えを行う比率は自由にプログラミングできる。ただし、適合値がある値よりも大きいときは、その遺伝子を 1 00%書き換える。また、この適合値がその値を下回るときは、その適合値により遺伝子の 1 00%ではないあるパーセンテージが書き換えられる。このとき、このソフトウェアでは通常の遺伝的アルゴリズムを開始する。たとえば一例として、図 1 9はテストデータ（1) の場合の上述のプロセスを示している。このとき、ソフトウェアがブロック 1の幾何学的配置と接続性に関する情報とを入力パラメータの組としてデータファイルから読み取る。このデータファイルカらはフアジイバラメータも読み出す。接続性情報は、表形式で表された接続性マトリクスにより表現される。表の右半分はブロック 1と I 〇バッファ 2との間の接続情報、左半分はプロック 1間の接続情報をそれぞれ表す。

表に記載されている数はブロック 1間の配線量を正規化した数値である。 1/ Oバッファ 2との接続に関するものはその配線量に対して 1 0倍の重み付けを行つている。これは I /Oバッファ 2とブロック 1との配線の絶対値は、ブロック 1同士の配線の場合と比較してフロアプラン配置における影響力が大きいにも関わらず、小さく（全ピン数により制限を受けている）表現されているからである。まず、このソフトウェアでは、フアジィ推論 1 2によりブロック 1 (# 3) が中央に配置されるブロック 1として選択される。その適合値は 0. 80823である（S 1 901 ) 。

次に、隅に配置するブロック 1の組み合わせを推論する。この場合における最良の適合性を示す配置は、ブロック 1 (# 1) を右上隅に配置することである（適合値は 0. 5475 1 6) (S 1 902) 。次に考えられる適合性はブロック 1 (# 0) を左上隅に配置することである（適合値は 0. 459838) (S 1 903) 。さらに次の適合性は、ブロック 1 (#4) を左下隅に配置することである。このブロック 1 (#4) の適合値は 0. 3095 1 7である（S 1 904 ) 。上述の例は意味のある推論である。

右下隅に配置されるべきブロック 1としては、ブロック 1 (# 7) とブロック 1 (# 9) が候補として考えられる（S 1 9 0 5) 。しかしながら、適合値が極めて小さく、それぞれ 0. 1 5 0 2 0 4と 0. 1 0 5 0 7 1であるので、これらの数値が意味のある推論結果と結びつくか否かを判断することは困難である。ここで編集と併合の機能に基づいてランダムに生成した初期世代の書き換えを行う（S 1 9 0 6) 。推論結果が意味のあるときは、遺伝子の 1 0 0%が置き換えられる。右下隅におけるブロック 1 (# 7) とブロック 1 (# 9) のように適合値が低い（0. 2を下回る）場合は、ブロック 1 (# 7) を当てはめる場合とブロック 1 (# 9) を当てはめる場合とを作成し、結果の良好な方を採用する。本実験プログラムはおよそ 4 5 0 0行のコードからなり、 C言語により記述されている。

4. 1. 実施の個体例

図 2 0、図 2 1は、フアジィ推論 1 2で求められたプロック 1の位置情報（座標値など）の、遺伝的アルゴリズム 1 3の処理への反映方法を示したものである。図 2 0において、実線のブロック 1 (# 3， # 0， # 4, # 7， # 1 ) はファジィ推論 1 2で求められたものであり、残りのブロック 1 (破線で示す # 2， # 5， # 6， # 9， # 8) はフアジィ推論 1 2では決定しないで遺伝的ァルゴリズム 1 3に任せたものとする。

各ブロック 1に対して、図 2 1に示すように複数の個体 1から個体 nがあり、大文字はフアジィ推論 1 2によって求められたブロック 1の中心座標値を示す。ただし、回転（]" = 0または1 ) は乱数発生に従うので、それぞれのケースについてチップエリアからはみ出さないように調整を行う。従って、たとえばブロック 1 (# 0) についていえば、 r 0 = 0の場合の（AO, B O) 、 r 0 = 1の場合の（A 0， B O) の値は異なるが、 r 0が同じであれば全個体をとおして同一値となる。また、イタリック体数字は乱数により発生する値を示す。

従って、図 2 1のように、ブロック 1 (# 0， # 1， # 3 , # 4, # 7 ) については、フアジィ推論 1 2で決定された値（遺伝子）が最終解まで引き継がれる。一方、ブロック 1 (# 2， # 5， # 6， # 8， # 9) においては、乱数発生された値が遺伝的アルゴリズム 1 3により最適化され、終了条件が成立した時点における最良の個体を解として選択する。この最良の個体がフロアプランニングにおけるブロック配置の設計データ群となる。

5. 実験結果

図 22、図 23、図 24は、フアジィ理論によるフアジィ推論 1 2を適用した初期世代に基づいた遺伝的アルゴリズム 1 3によるフロアプランニングをコンビユータで実験した結果を示したものである。

5. 1. テストデータ（1)

図 22は、テストデータ（1) に関してフアジィ推論 1 2と遺伝的ァルゴリズム 1 3とを適用した場合の結果を示している（右側の図（b) 、左側（a) は熟練設計技術者による結果）。

ブロック 1 (# 3) が中央に配置され、ブロック 1 (# 0) が左上隅に配置され、ブロック 1 (#4) が左下隅に配置され、ブロック 1 (# 1) が右上隅に配置され（これは推論の結果）ている点は熟練設計技術者による設計結果と同じである。これらの条件は初期条件として設定され、遺伝的アルゴリズム 1 3による操作をしているときでも変更されることのない条件として維持される。図 22に示すように、右下隅に配置されるブロック 1の候補は数 1 0%である。残りのブロック 1がどのように配置されるかは遺伝的アルゴリズム 1 3に委ねられている。この結果は 1 000個の初期世代に対して 50回の発生操作をすることにより得られたものである。必要とされた計算時間は遺伝的アルゴリズム 1 3のみにより設計を行った場合と比較してはるかに少ないものであった。前記図 1 1に示す結果を得るのに要した時間は、たとえば S p a r c 1 0上で 4時間であつたが、図 21に示す例では 40分であった。この実験的ソフトウェアによる結果のコストは 7476であった。この値は熟練設計技術者が設計した場合の 7 1 55に近いコストである。遺伝的アルゴリズム 1 3のみを用いた場合のコストである 976 6と比較すると実質的な進歩が達成できたといえる。

この結果の視覚的印象は良好である。熟練者が考察して評価した結果では、実際的応用に大きな潜在能力があると認められた。

5. 2. テストデータ（2) 図 23は、テストデータ（2) の結果を示すものである。各ブロック 1の相対位置は熟練設計技術者による設計結果と同様である。

適合値は、チップの中央に配置するブロック 1 (# 3) の場合が 0. 741 5 09、左上隅に配置されたブロック 1 (# 0) の場合は 0. 5 1 6279、左下隅のブロック 1 (# 5) は 0. 42 1 739、右下隅のブロック 1 (# 7) は 0. 304884、右上隅のブロック 1 (# 1) は 0. 242806である。 50回の世代生成を行った後の結果のコストは 4820であった。これは初期世代を 1

000個（遺伝的アルゴリズム 1 3のみの場合の半数）に設定した場合であるが、この遺伝的アルゴリズム 1 3のみの結果と比較して 8%の改善が得られた。この値は熟練設計者による結果と比較すると改善されている。

5. 3. テストデータ（3)

図 24は、テストデータ（3) の結果を示すものである。チップの中央に配置されているブロック 1 (# 9) の適合値は 0. 740964であり、左上隅に配置されているブロック 1 (# 8) の適合値は 0. 586265である。右上隅に配置されているブロック 1 (# 7) の適合値は 0. 231 984である。左下隅に対して最も大きな適合性を示すブロック 1はブロック 1 (# 0) でありこれの適合値が 0. 1 57509であり、次に大きな適合性を示すプロック 1がプロック 1 (# 1) であり、 0. 1 21 322である。ブロック 1 (#4) を右下隅に配置すると 0. 1 2 1 322、もしブロック 1 (# 1) を右下隅に配置すると、このときの適合値は 0. 1 1 0256となり、ブロック 1 (# 6) の場合は 0.

1 10256となる。

このようにして得られた経験と予備的な実験によって分かることは、適合値が 0. 2を下回った場合はそれが意味をなすかどうかは判断が困難であるとレ、うことである。

このことから、左上隅および右上隅の場合は、フアジィ推論 1 2により得られた結果に基づいて配置されるブロック 1の適合性を明らかに上回るブロック 1は存在しないことが分かる。し力しながら、左下隅に対する配置では、ブロック 1 (# 0) およびブロック 1 (# 1) がその他のブロック 1と比較してやや適合性が高いといえる。右下隅に対する配置では、ブロック 1 (#4) およびブロック 1 (# 1) がやや適合性の高い候補であるといえる。ブロック 1 (# 1) を右下隅に配置した場合の適合値は 0. 1 1 0256であり、逆に左下隅に配置した場合の適合値は 0. 1 2 1 322である。従って、後者の場合について試行を行つた。ブロック 1 (# 9) を中央に配置すること、ブロック 1 (# 8) を左上隅に配置すること、およびブロック 1 (# 7) を右上隅に配置することは固定的なものとする。このような条件の下で、以下の 3通りの組み合わせの善し悪しを調べることにする。すなわちブロック 1 (# 1) を左下隅にブロック 1 (#4) を右下隅に配置する組み合わせ、ブロック 1 (# 0) を左下隅にブロック 1 (#4) を右下隅に配置する組み合わせ、ブロック 1 (# 0) を左下隅にブロック 1 (# 1) を右下隅に配置する組み合わせの 3通りである。

ブロック 1 (# 1) を左下隅に、ブロック 1 (#4) を右下隅に配置する組み合わせが最良のコストパフォーマンスとなった。この場合のコストは 6627であり、人手で行った場合の 660 1に近づいており、遺伝的アルゴリズム 1 3のみで行った場合のコストが 9324であることと比較すると大きく改善している。この結果を考察したところ、テストデータ（1) とテストデータ（2) の場合と同様に十分に満足のいくものであった。従って、この目的である「半導体チップ設計などの複雑な設計の開始段階でよい初期条件を与える」とレ、うことは達成されたといえる。

5. 4. コスト（評価関数値）の変化

前記式 1により定義される評価関数に基づいてコストが算出される。図 25はテストデータ（1) の世代数に対するコストの変化を示すグラフである。

ランダムに発生された初期世代（個体数 1 000) での遺伝的アルゴリズム 1

3は世代生成 50回でコストが収束してしまい、コストの 10000程度からそれ以上の改善はほとんどない。この遺伝的アルゴリズム 1 3は局所的最適条件に落ち込んでしまった。

初期世代数を 1 000としてフアジィ推論 1 2を伴ったときの遺伝的アルゴリズム 1 3の場合は 45世代あたりで収束し、この場合は熟練者が設計を行った場合に対してほぼ同レベルに接近している。

6 · ^口 0BH 従って、前記図 1のステップ S 1 0 4のレイァゥト設計工程におけるフロアプランニングに適用した場合において、 V L S Iのフロアプランニングを行うにあたっては、遺伝的アルゴリズム 1 3の初期世代を準備するためにフアジィ推論 1 2を適用することを提案してきたが、実験結果によりこれが実際的な応用にかなり可能性があることが分かった。この目的は、「半導体チップ設計などの複雑な設計の開始段階でよい初期条件を与える」ということにあるが、この目的は概ね達成することができた。さらに、実務的経験に基づいてフアジィ推論 1 2のパラメータを一層適切に調整したり、各ブロック 1の適合値が低い場合の遺伝子の扱いなどを考慮することで、設計効率と設計品質との両面でよりよい効果を得ることができる。

次に、前記図 1のステップ S 1 0 2の論理設計工程における論理クラスタ分割に適用した一例を、前記フロアプランニングと同様のフアジィ推論 1 2 a、遺伝的アルゴリズム 1 3 aを用いた場合について説明する。

1 1 . 遺伝的アルゴリズムにおける論理クラスタ分割

前記のような V L S Iの設計において、チップ全体を一括して処理することは、データ規模の点から効率的ではなく、いくつかのプロック 1に分ける必要があり、これは主にレイァゥトの段階で顕著になる。大規模な回路を一括で自動配置 ·配線することは、ブロック 1内の実装率（面積当たりのトランジスタ数）の低下をもたらし、小規模な多数のブロック 1を使用することはブロック 1間の配線領域の增大を招く。この解決のためには論理データを適した範囲の大きさに分割することが効果的である。

論理データは、通常、たとえば図 2 6に一例を示すように階層的に作成される。図 2 6でブロック 1 (A) は、ブロック 1 ( B ) およびブロック 1 ( C ) とを結線することで作成されており、同様にブロック 1 ( B， C ) もさらに下位のプロック 1を結線することで作成される。このような階層関係を表した例を、たとえば図 2 6に示す。図中、 A〜Zは論理素子（ブロック 1 ) を表す。

このような論理データを、その階層構造に着目し、適したデータをグループに分割することが、論理クラスタの分割である。この分割の例を、たとえば図 2 8 に示す。このクラスタ分割を、前記フロアプランニングと同様に自動化する方法の一例を以下に示す。

1 2 . 実施

まず、 1つのブロック 1に含まれる論理素子数および内部ネット数が適した範囲にあり、かつ外部との接続ネット数が少ないものをフアジィ推論により求める。このとき、図 2 8のブロック 1 ( C ) のように、既にクラスタとして求めたものを含む論理階層の場合、そのクラスタを除いた範囲をクラスタとして考える。図 2 7の例では、クラスタ 3を除きクラスタ 2を作成する。このフアジィ推論 1 2 aは、全ての階層のブロック 1について行い、該当したものだけをクラスタとし、該当しない部分は未定のまま残す。

次に、残った部分に対し乱数的にクラスタの初期値を決定し、遺伝的アルゴリズム 1 3 aにより最適解を求める。このときの評価関数は、（クラスタ内の論理素子数とネット数から求めた推定面積 +プロック 1間ネット数から求めた推定配線面積）とし、これが最小のものを選択することで行う。ここでの面積の推定方法は、経験的関数として予め定義しておく。

なお、面積を最小とする目的や、このための評価関数は一例であり、論理回路を分割する目的に応じた推論ルールと評価関数を用意することで、全ての論理回路の分割を自動化することが可能となる。

1 3 · ？ fe p冊

従って、論理設計工程における論理クラスタ分割に適用した場合にも、論理デ —タを適した範囲の大きさに分割することができるので、大規模な回路を一括で自動配置 ·配線する際のプロック 1内の実装率の低下を抑え、小規模な多数のブロック 1を使用する際のプロック 1間の配線領域の増大を抑制することが可能である。

以上、本発明者によってなされた発明をその実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。たとえば、遺伝的ァルゴリズムの他に、シミュレーテツド ·ァニーリングなどの他の最適化処理手法を用いることも可能である。あるいは、フアジィ推論で得られた結果を制約条件（初期条件）として、残りを他のヒューリスティック（発見的）手法を用いることも可能である。産業上の利用可能性

以上のように、本発明にかかる半導体装置の設計技術は、特に V L S Iなどの集積回路を実装する半導体チップ設計の初心者に対して、複雑な設計の開始段階でよい初期条件を与えることができる半導体装置の設計方法に有用であり、この半導体装置の設計方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体などにも適用することができる。

Claims

請求の範囲

1 . システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、

前記機能設計工程により得られた設計データに基づいて前記集積回路を論理ゲ —トレベルで論理設計を行う論理設計工程と、

前記論理設計工程により得られた設計データに基づいて前記論理ゲートをトランジスタレベルで回路設計を行う回路設計工程と、

前記論理設計工程により得られた設計データと、前記回路設計工程により得られた設計データとに基づいて前記論理ゲートの配置 ·配線を行うレイァゥト設計工程と、を含み、前記各設計工程の設計データの作成において、

フアジィ推論を用レ、て複数の設計データ群を作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 1工程により作成された複数の設計データ群と、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法を用いて適合度の高 V、設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、前記最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計データ群を選択しながら順次繰り返して、最適解となる設計データ群を作成する第 4工程と、を有することを特徴とする半導体装置の設計方法。

2 . システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、

前記機能設計工程により得られた設計データに基づいて前記集積回路を論理ゲ一トレベルで論理設計を行う論理設計工程と、

フアジィ推論を用いて最適解となる一部分の設計データ群を作成する第 1工程と、乱数的に複数の設計データ群を作成する第 2工程と、

前記第 2工程により作成された複数の設計データ群に基づいて、最適化処理手法を用いて適合度の高い設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、前記最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計データ群を選択しながら順次繰り返して、最適解となる他部分の設計データ群を作成する第 4 工程と、を有することを特徴とする半導体装置の設計方法。

3 . 請求項 1または 2記載の半導体装置の設計方法であって、前記レイアウト設計工程は、複数のプロックを半導体チップ上に配置 ·配線するフロアプランニングであり、

前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的ァルゴリズムの初期の設計データ群を前記フアジィ推論を用いて生成し、前記最適解となる設計データ群を用いて前記複数のブロックを前記半導体チップ上に配置することを特徴とする半導体装置の設計方法。

4 . 請求項 3記載の半導体装置の設計方法であって、前記フロアプランニングにおけるコーディングは、

前記各プロックの中心 X— Y座標および回転と、前記遺伝的アルゴリズムの染色体とを対応付けすることを特徴とする半導体装置の設計方法。

5 . 請求項 3記載の半導体装置の設計方法であって、前記フロアプランニングにおける評価は、

前記各ブロック間の実質配線長を L i、重複部分を S i、指定領域からのはみ出し部分を O V iとし、重み付けの係数をひ， β， γとして、

E = a∑L i + j3∑S i + y∑O V i

の評価関数 Eより求めた値に基づいて前記各プロックの配置 ·配線を評価することを特徴とする半導体装置の設計方法。

6 . 請求項 3記載の半導体装置の設計方法であって、前記フロアプランニングにおける突然変異は、

前記複数のブロックのうち、任意のブロックを所定の距離だけ所定の方向に動かすとともに、このプロックの向きを所定の方向に変更することを特徴とする半導体装置の設計方法。

7 . 請求項 3記載の半導体装置の設計方法であって、前記フロアプランニングにおける前記フアジィ推論は、

前記半導体チップの中心部付近に配置されるプロックは Iノ0バッファに対して接続性が低く、寸法が小さいものを選択し、

前記半導体チップの隅に配置されるプロックは寸法が大きく、隣接するプロックとの接続性が中程度のものを選択し、

前記 I Ζοバッファに対して接続性が高いプロックは前記半導体チップの周辺部に沿って配置する、

というルールに基づくものであることを特徴とする半導体装置の設計方法。

8 . 請求項 1または 2記載の半導体装置の設計方法であって、前記論理設計工程は、複数のプロックをクラスタに分割する論理クラスタ分割であり、

前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的ァルゴリズムの初期の設計データ群を前記フアジィ推論を用いて生成し、前記最適解となる設計データ群を用いて前記複数のプロックを前記クラスタに分割することを特徴とする半導体装置の設計方法。

9 . 請求項 8記載の半導体装置の設計方法であって、前記論理クラスタ分割における前記フアジィ推論は、

前記各ブロックに含まれる論理素子数および内部ネット数が所定の範囲にあり、かつ外部との接続ネット数が少ないブロックを求める、というルールに基づくものであることを特徴とする半導体装置の設計方法。

1 0 . 請求項 8記載の半導体装置の設計方法であって、前記論理クラスタ分割における評価は、

前記クラスタ内の論理素子数とネット数とから求めた推定面積と、前記ブロック間のネット数から求めた推定配線面積と、を加算した評価関数より求めた値に基づいて前記クラスタの分割を評価することを特徴とする半導体装置の設計方法。

1 1 . システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、前記機能設計工程により得られた設計データに基づいて前記集積回路を論理ゲ一トレベルで論理設計を行う論理設計工程と、前記論理設計工程により得られた設計データに基づいて前記論理ゲートをトランジスタレベルで回路設計を行う回路設計工程と、

フアジィ推論を用いて複数の設計データ群を作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 1工程により作成された複数の設計データ群と、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法を用いて適合度の高い設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、前記最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計データ群を選択しながら順次繰り返して、最適解となる設計データ群を作成する第 4工程と、を有する半導体装置の設計方法をコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。

1 2 . システム仕様に基づいて集積回路の機能設計を行う機能設計工程と、前記機能設計工程により得られた設計データに基づいて前記集積回路を論理ゲ ―トレベルで論理設計を行う論理設計工程と、

フアジィ推論を用いて最適解となる一部分の設計データ群を作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 3工程により選択された設計データ群に基づいて、前記最適化処理手法を用いてさらに次の複数の設計データ群の作成を適合度の高い設計データ群を選択しながら順次繰り返して、最適解となる他部分の設計データ群を作成する第 4 工程と、

を有する半導体装置の設計方法をコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。

1 3 . 請求項 1 1または 1 2記載のコンピュータ読み取り可能な記録媒体であつて、前記レイアウト設計工程は、複数のブロックを半導体チップ上に配置 ·配線するフロアプランニングであり、

前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的ァルゴリズムの初期の設計データ群を前記フアジィ推論を用いて生成し、前記最適解となる設計データ群を用いて前記複数のブロックを前記半導体チップ上に配置することを特徴とするコンピュータ読み取り可能な記録媒体。

1 4 . 請求項 1 3記載のコンピュータ読み取り可能な記録媒体であって、前記フロアプランニングにおけるコーディングは、

前記各ブロックの中心 X— Y座標おょぴ回転と、前記遺伝的アルゴリズムの染色体とを対応付けすることを特徴とするコンピュータ読み取り可能な記録媒体。

1 5 . 請求項 1 3記載のコンピュータ読み取り可能な記録媒体であって、前記フロアプランニングにおける評価は、

前記各ブロック間の実質配線長を L i、重複部分を S i、指定領域からのはみ出し部分を〇V iとし、重み付けの係数をひ， β , γとして、

Ε = α∑ L i + |3∑ S i + y∑O V i

の評価関数 Eより求めた値に基づいて前記各プロックの配置 ·配線を評価することを特徴とするコンピュータ読み取り可能な記録媒体。

1 6 . 請求項 1 3記載のコンピュータ読み取り可能な記録媒体であって、前記フロアプランニングにおける突然変異は、

前記複数のブロックのうち、任意のブロックを所定の距離だけ所定の方向に動かすとともに、このプロックの向きを所定の方向に変更することを特徴とするコンピュータ読み取り可能な記録媒体。

1 7 . 請求項 1 3記載のコンピュータ読み取り可能な記録媒体であって、前記フロアプランニングにおける前記フアジィ推論は、

前記半導体チップの中心部付近に配置ざれるプロックは I ζοバッファに対して接続性が低く、寸法が小さいものを選択し、

前記 I ZOバッファに対して接続性が高いプロックは前記半導体チップの周辺部に沿って配置する、

というルールに基づくものであることを特徴とするコンピュータ読み取り可能な記録媒体。

1 8 . 請求項 1 1または 1 2記載のコンピュータ読み取り可能な記録媒体であつて、前記論理設計工程は、複数のブロックをクラスタに分割する論理クラスタ分割であり、

前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的ァルゴリズムの初期の設計データ群を前記フアジィ推論を用いて生成し、前記最適解となる設計データ群を用いて前記複数のプロックを前記クラスタに分割することを特徴とするコンピュータ読み取り可能な記録媒体。

1 9 . 請求項 8記載のコンピュータ読み取り可能な記録媒体であって、前記論理クラスタ分割における前記フアジィ推論は、

前記各プロックに含まれる論理素子数および内部ネット数が所定の範囲にあり、かつ外部との接続ネット数が少ないブロックを求める、というルールに基づくものであることを特徴とするコンピュータ読み取り可能な記録媒体。

2 0 . 請求項 1 8記載のコンピュータ読み取り可能な記録媒体であって、前記論理クラスタ分割における評価は、

前記クラスタ内の論理素子数とネット数とから求めた推定面積と、前記ブロック間のネット数から求めた推定配線面積と、を加算した評価関数より求めた値に基づいて前記クラスタの分割を評価することを特徴とするコンピュータ読み取り可能な記録媒体。

2 1 . フアジィ推論を用いて設計データを作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、前記第 1工程により作成された設計データと、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法により適合度の高い設計データを含む設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、最適化処理手法により適合度の高い設計データを含む設計データ群を選択する第 4工程と、を有することを特徴とする半導体装置の設計方法。

2 2 . フアジィ推論を用いて一部分の設計データを作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 2工程により作成された複数の設計データ群に基づいて、最適化処理手法により適合度の高い設計データを含む設計データ群を選択する第 3工程と、前記第 3工程により選択された設計データ群に基づいて、最適化処理手法により適合度の高い設計データ群を選択する第 4工程と、を有することを特徴とする半導体装置の設計方法。

2 3 . 請求項 2 2記載の半導体装置の設計方法であって、前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的アルゴリズムの初期の設計データを前記フアジィ推論を用いて生成することを特徴とする半導体装置の設計方法。

2 4. フアジィ推論を用いて設計データを作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 1工程により作成された設計データと、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法により適合度の高い設計データを含む設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、最適化処理手法により適合度の高い設計データを含む設計データ群を選択する第 4工程と、

をコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。

2 5 . フアジィ推論を用いて一部分の設計データを作成する第 1工程と、

乱数的に複数の設計データ群を作成する第 2工程と、

前記第 2工程により作成された複数の設計データ群に基づいて、最適化処理手法により適合度の高い設計デ一タを含む設計データ群を選択する第 3工程と、前記第 3工程により選択された設計デ一タ群に基づいて、最適化処理手法により適合度の高い設計データ群を選択する第 4工程と、

2 6 . 請求項 2 5記載のコンピュータ読み取り可能な記録媒体であって、前記最適化処理手法として遺伝的アルゴリズムを用い、前記遺伝的アルゴリズムの初期の設計データを前記フアジィ推論を用いて生成することを特徴とするコンビュ一タ読み取り可能な記録媒体。

2 7 . 請求項 2 1記載の半導体装置の設計方法であって、前記フアジィ推論においては、メンバーシップ関数が利用されていることを特徴とする半導体装置の設計方法。

2 8 . 請求項 2 3記載の半導体装置の設計方法であって、前記フアジィ推論においては、メンバーシップ関数が利用されていることを特徴とする半導体装置の設計方法。

2 9 . 請求項 2 4記載のコンピュータ読み取り可能な記録媒体であって、前記ファジィ推論においては、メンバーシップ関数が利用されていることを特徴とするコンピュ一タ読み取り可能な記録媒体。

3 0 . 請求項 2 6記載のコンピュータ読み取り可能な記録媒体であって、前記フアジィ推論においては、メンバーシップ関数が利用されていることを特徴とするコンピュータ読み取り可能な記録媒体。

3 1 . メンバーシップ関数を利用して設計データを作成する第 1工程と、

複数の設計データ群を作成する第 2工程と、

前記第 1工程により作成された設計データと、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法により適合度の高レ、設計データを含む設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、最適化処理手法により適合度の高い設計データ群を選択する第 4工程と、を含むことを特徴とする半導体装置の設計方法。

3 2 . 請求項 3 1記載の半導体装置の設計方法であって、前記第 2工程は、乱数的に前記複数の設計データ群を作成することを特徴とする半導体装置の設計方法。

3 3 . 請求項 3 2記載の半導体装置の設計方法であって、前記最適化処理手法へ提供されるデータのうち、一部が前記第 1工程により作成された設計データであり、一部が前記第 2工程により作成された設計データであることを特徴とする半導体装置の設計方法。

3 4 . メンバーシップ関数を利用して設計データを作成する第 1工程と、

複数の設計データ群を作成する第 2工程と、

前記第 1工程により作成された設計データと、前記第 2工程により作成された複数の設計データ群とに基づいて、最適化処理手法により適合度の高い設計デ一タを含む設計データ群を選択する第 3工程と、

前記第 3工程により選択された設計データ群に基づいて、最適化処理手法により適合度の高い設計データ群を選択する第 4工程と、

3 5 . 請求項 3 4記載のコンピュータ読み取り可能な記録媒体であって、前記第 2工程は、乱数的に前記複数の設計データ群を作成することを特徴とするコンビユータ読み取り可能な記録媒体。

3 6 . 請求項 3 5記載のコンピュータ読み取り可能な記録媒体であって、前記最適化処理手法へ提供されるデータのうち、一部が前記第 1工程により作成された設計データであり、一部が前記第 2工程により作成された設計データであることを特徴とするコンピュータ読み取り可能な記録媒体。