JPH06290230A - 論理シミュレーション装置 - Google Patents

Abstract

(57)【要約】 【目的】本発明は、レベルソート法を用いた論理シミュ
レーションにおいてループを含む論理回路をシミュレー
ションすることができる論理シミュレーション装置を提
供する。 【構成】シミュレーション対象の論理回路から分離され
る組合せ回路部より複数のプリミティブＡ、Ｂ、Ｐのル
ープ回路を抽出し、この回路中のプリミティブＰの出力
を除去して第１の回路を生成するとともに、プリミティ
ブＰの前回の出力信号値を記憶するプリミティブＰＯを
用意して、第１の回路を複製したプリミティブＡ´、Ｂ
´、Ｐ´の第２の回路を用い、第２および第１の回路と
プリミティブＰＯによる縦続接続回路を構成し、さらに
第２の回路の各プリミティブに対し第１の回路の各プリ
ミティブに対する入力と同じ入力を接続する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はプログラム可能な素子を
用いて論理回路の検証を行なうシミュレーションシステ
ムに関するものである。

【０００２】

【従来の技術】ＬＳＩの集積度の向上にともない、近年
の計算機の大規模化、複雑化は著しいものがある。従っ
て、このような大規模計算機を開発するについては、そ
の開発に要する期間、コストを低く抑えることが益々重
要になっており、このために、シミュレーションによる
システム機能、システム性能の検証の重要性が一段と高
まっている。

【０００３】そこで、論理回路を用いたシステムを設計
する場合も、論理回路をモデル化し、それを論理シミュ
レーションすることにより設計検証することが、システ
ムの開発期間を短縮するため、また設計の完成度を高め
るために必要な工程として用いられている。

【０００４】論理回路をソフトウエアで論理シミュレー
ションする場合、回路規模が大きくなるとモデルの記述
量が膨大になるためシミュレーション時間は必然的に膨
大になる。

【０００５】そこで、シミュレーションの高速化のため
さまざまな工夫がなされているが、その一つにレベルソ
ート法がある。

【０００６】このレベルソート法は、あらかじめゲート
の評価順序を決定しておき、シミュレーション実行時に
はこの静的な順序にしたがって評価を行なうようにして
いる。そして、レベルソート法における評価順序の決定
は、「ゲートｇの評価は、ｇの入力側にあるゲートの評
価を修了した後に行なう」というルールの下に行なうよ
うにしており、同期回路の組合せ回路部に関して、回路
安定時の最終値を計算することを目的としている。

【０００７】一方、特開平４−２４３７５５号公報によ
り時分割エミュレータの提案もなされているが、このよ
うな時分割エミュレータにおいては、各タイムスライス
に割り当てる論理演算はレベルソートされていることが
必要である。

【０００８】しかして、このようなレベルソート法によ
れば、通常、組合せ回路部はループを含まないように設
計され、組合せ回路部のモデルもループを含まないの
で、先ほど述べたルールで評価順序を決めるレベルソー
ト法でシミュレーションするのにほとんどの場合は問題
はないが、実際には組合せ回路部にループが含まれる論
理回路が設計されることがあり、このような回路では先
ほど述べたルールに沿った評価順序が決定できないため
レベルソート法では扱うことができなかった。

【０００９】一方、論理回路をシミュレートするシステ
ムの一つに、ハードウェアエミュレータがある。ハード
ウェアエミュレータは、相互接続された複数の論理ブロ
ックからなり、各論理ブロックが、検証対象の回路の動
作と同じ動作をすることにより、回路の論理シミュレー
ションを高速に行なう。論理ブロックとして、例えばＦ
ＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａ
ｔｅ Ａｒｒａｙ）と呼ばれるプログラム可能なゲート
アレイがある。ＦＰＧＡは多数のプログラム可能素子か
らなり、それぞれのプログラム可能素子が一つまたは複
数の回路素子の動作をシミュレートする。

【００１０】シミュレーション対象回路のプログラム可
能素子への割り付け（マッピング）及びプログラム可能
素子間の接続の決定は、コンパイラが行なう。コンパイ
ラによるマッピングの結果得られたそれらのプログラム
情報は、通常シミュレーションの前にエミュレータ内の
メモリにロードされ、シミュレーション時にエミュレー
タがプログラム可能素子の動作を決定するのに使われ
る。

【００１１】ハードウェアエミュレータの欠点の一つは
コンパイル時間が膨大なことである。これは次の理由に
よる。従来のエミュレータアーキテクチャは、隣接する
者同士のみを結ぶメッシュ構造に代表されるようにＦＰ
ＧＡ間の配線の自由度が小さい。また、ＦＰＧＡは組み
込み用途のものが大部分であるため、やはり配線の自由
度が少ない。従って、ＦＰＧＡの回路充填率を上げるた
めには、自由度の少ない配線手段でいかに対象回路のマ
ッピングを実現するかが重要である。

【００１２】このような問題に対する解決策として確率
的アルゴリズム以外に効率のよいものは知られていな
い。通常はシミュレーティッドアニーリング法のよう
に、望ましいマッピングができるまで最適化を繰り返す
確率的方法が採られている。しかし、このような方法で
は回路規模が大きくなるに従い、マッピングに膨大な時
間がかかり、回路が１Ｍゲート規模と大きい場合、コン
パイルが終了するのに数日かかってしまうこともある。
コンパイル時間の増加はシステム検証のターンアラウン
ドの増加につながるため、マッピングアルゴリズムの高
速化は極めて重要である。

【００１３】このように配線自由度が少ないエミュレー
タでは、効率の良いマッピング方式を実現することは容
易でない。このため、上述した特開平４−２４３７５５
号公報では、完全クロスバに代表される配線の自由度が
豊富なエミュレータアーキテクチャが開示されている。
このアーキテクチャでは、プログラム可能素子は多段に
結合された構造であり、プログラム可能素子を時分割に
利用できるという特長もある。また、予めシミュレーシ
ョン対象回路をレベルソートしておき、回路素子のうち
入力から数えたレベルの小さいものから大きいものへと
順にエミュレータ中のプログラム可能素子にマッピング
することによって、バックトラックをほとんど必要とし
ない、高速なマッピングが可能であることが示されてい
る。

【００１４】しかし、このような単純なアルゴリズムで
は、マッピングが単純な分、「プログラム可能素子の回
路充填率」（プログラム可能素子１個当りに割当てられ
ている平均回路素子数）が不十分になるという傾向があ
る。

【００１５】プログラム可能素子を同数有するエミュレ
ータでは、シミュレーション可能な回路規模は回路充填
率に比例するため、回路充填率が低いことは、シミュレ
ーション可能な回路規模が小さいことを意味しており、
従って、多段結合アーキテクチャのエミュレータにおい
ては、マッピング方式の工夫により、回路充填率を向上
させることが重要である。

【００１６】

【発明が解決しようとする課題】このように従来のシミ
ュレーションの高速化のために適用されるレベルソート
法によると、組合せ回路部にループが含まれるような論
理回路が設計された場合、このような回路ではレベルソ
ート法によるルールで評価順序が決定できないことから
扱うことができないという問題点があった。

【００１７】また、従来の多段に結合されたプログラム
可能素子から構成される論理回路シミュレーションシス
テムでは、論理回路の割り付けにおけるプログラム可能
素子の回路充填率が十分でなく、大規模の回路のシミュ
レーションが難しいと言う問題点があった。

【００１８】本発明は、上記事情に鑑みてなされたもの
で、レベルソート法を用いた論理シミュレーションにお
いてループを含む論理回路をシミュレーションすること
ができ、しかも論理回路中のループがシミュレーション
時に発振するか否かも検出できる論理シミュレーション
装置を提供することを目的とする。

【００１９】また、本発明は、多段に結合されたプログ
ラム可能素子から構成される論理回路シミュレーション
システムにおいて、論理回路の割り付けにおけるプログ
ラム可能素子の回路充填率の向上させ、より大規模の回
路をシミュレーション可能にした論理エミュレータを提
供することを目的とする。

【００２０】

【課題を解決するための手段】本発明は、論理回路をレ
ベルソート法を用いてシミュレーションを行なう論理シ
ミュレーション装置において、シミュレーション対象と
なる論理回路を格納する手段と、前記論理回路を組み合
わせ回路部と状態記憶部とに分離する手段と、この手段
で分離された組合せ回路部より複数の論理素子から構成
されるループからなる回路Ａを抽出する手段と、前記回
路Ａ中の論理素子の一つの論理素子Ｚについてその出力
を取り去った回路Ｘを作成する手段、前記論理素子Ｚの
前回の出力信号値を記憶する記憶素子Ｕを作成する手
段、前記回路Ｘを複製した回路Ｙを用いて、前記回路
Ｙ、回路Ｘおよび記憶素子Ｕの縦続接続回路を構成する
手段を有する回路変換手段とを具備し、前記回路Ｙの各
論理素子に対し前記回路Ｘの各論理素子に対する入力と
同じ入力を接続するようにしている。

【００２１】また、本発明は、再プログラム可能な複数
の論理ブロックを多段結合した論理エミュレータにおい
て、入力側からの信号の流れの順にレベルソートされた
プリミティブグラフを入力側から数えて一定のレベルご
とに区切ることで複数の連結成分を生成し、これら連結
成分ごとに論理ブロックに割り付けるようにしている。

【００２２】

【作用】この結果、本発明によれば、組合せ回路部にル
ープを含む論理回路モデルに対し、切断したループを二
つ縦続接続して等価回路モデルに変換することによりレ
ベルソート法によるシミュレーションを行うことがで
き、また、変換前の回路のループの発振の検証も可能に
なる。つまり、論理回路モデルにおいて扱う信号値が２
値（例えば“０”、“１”）しかとらないことから、ル
ープを２周分だけ評価することにより、論理回路モデル
のループの評価、すなわちループの発振の検出とループ
が発振しない場合によりループ中の論理素子の評価を行
うことができる。

【００２３】また、再プログラム可能な複数の論理ブロ
ックからなる論理エミュレータにおいて、各論理ブロッ
クへの論理回路の割り付けの際に、入力側から数えて一
定のレベルごとに区切って得られる回路の連結成分を単
位として割り付けを行なうことで、接続が内部で閉じて
いる回路部分を同一の論理ブロックに割り付けることが
できるようになり、その結果として、プログラム可能素
子の回路充填率が向上し、より大規模の回路のシミュレ
ーションが可能になる。

【００２４】

【実施例】以下、本発明の一実施例を図面に従い説明す
る。

【００２５】図１は、実施例の概略構成を示している。
この場合、シミュレーション部１１、回路モデルを格納
する回路モデル格納部１２、組合せ回路部と状態記憶部
を分離する分離部１３、ループからなる回路を検出する
ループ回路検出部１４、ループからなる回路を等価な回
路に変換する変換部１５から構成されている。

【００２６】そして、このように構成した装置は、図２
に示すステップ２００１〜ステップ２００６の手順に従
って処理が進められる。

【００２７】この場合、論理シミュレータへ入力される
論理回路はネットリストによって表現されている。そし
て、これをシステムの内部表現にモデル化する。

【００２８】シミュレーション部１１は、このようなモ
デル化手段を有している。本実施例ではこのモデル化
は、ネットリスト中の論理素子間接続情報を、プリミテ
ィブのノードとしてそれら間の配線を枝とするプリミテ
ィブグラフに変換することによって行なわれる。ここ
で、プリミティブとは、シミュレーションの１単位であ
り、一つあるいは複数の論理素子の集まりに対応する。
ここでは、信号値は“０”または“１”の２値しか取ら
ないとする。また、外部入力信号端子・外部出力信号端
子は論理素子ではないが、便宜上それらを特別なプリミ
ティブで表現する。以後これらのプリミティブを入力プ
リミティブ・出力プリミティブと呼ぶことにする。ま
た、各プリミティブにはそれぞれ異なるｉｄをつける。

【００２９】回路モデル格納部１２では、プリミティブ
グラフに関する情報を記憶している。この場合、プリミ
ティブグラフは配列の形で格納される。この場合、プリ
ミティブを表す配列要素は、図３に示すように、そのプ
リミティブのｉｄ、そのプリミティブの機能（ＡＮＤ，
ＯＲ，ＮＯＴ，フリップフロップなど）、そのプリミテ
ィブからの出力先のプリミティブのｉｄのリスト、その
プリミティブへの入力元のプリミティブのｉｄのリス
ト、その他入力からのレベルの情報、ループ検出に必要
な情報などを格納するフィールドからなっている。

【００３０】そして、組合せ回路と状態記憶部を分離す
る分離部１３により回路モデル格納部１２に格納された
回路モデル中のフリップフロップそれぞれに対し、新た
に入力ブリミティブと出力プリミティブを作成し、回路
モデルからフリップフロップを強連結成分に分離し、フ
リップフロップへの入力枝を出力プリミティブに、フリ
ップフロップからの入力枝を入力プリミティブにそれぞ
れ接続する。

【００３１】ここで、図４（ａ）（ｂ）に示すように強
連結成分Ａは、有向グラフにおいて有向枝を経由して互
いに行き来できる（到達可能である）ようなノードの集
合と、その集合の要素であるノード間を結ぶ有向枝の集
合の対で定義される。ただし自分自身は到達可能である
ので、ノード一つからなる強連結成分も存在し、もし強
連結成分中に複数のノードが含まれればそれはループの
存在を意味する。

【００３２】ここで、プリミティブグラフを強連結成分
に分解する方法を簡単に述べる。

【００３３】まず、グラフ中のプリミティブＰＯを選択
しそこから有向枝に沿って探索を開始する。もし、ＰＯ
に戻るようなことがあれば探索パスはループになってい
る。この様なループをまとめることにより強連結成分が
得られる。ＰＯに戻るパスがなければＰＯはそれ自身が
強連結成分になる。探索を開始するプリミティブＰＯ
は、それまでに得られたどの強連結成分にも含まれない
プリミティブから選ぶ。そして、選択できるプリミティ
ブがなくなるまで上記操作を行えば、最終的に強連結成
分に分解されたプリミティブグラフが得られることにな
る。

【００３４】このような方法は、グラフを強連結成分へ
分解する一例であり、より効率的な手順およびその詳細
は、例えば「アルゴリズムの設計と解析Ｉ，ＩＩ（サイ
エンス社、１９７７）ｐ．１７０〜ｐ．１７７」に開示
されている。

【００３５】もし、プリミティブグラフにループがなけ
れば、各強連結成分はプリミティブを一つだけしか含ま
ない。プリミティブグラフがループを含めば、そのルー
プは二つ以上のプリミティブからなる強連結成分が存在
することと同値である。

【００３６】従って、各強連結成分に含まれるプリミテ
ィブが一つだけなら、プリミティブグラフはループは含
まないので、そのままプリミティブグラフの交換は行わ
なくて良い。

【００３７】問題は、ある強連結成分が複数のプリミテ
ィブを含む場合である。この場合はグラフはループを含
んでいるので、ループからなる回路を等価な回路に変換
する変換部５を用いるようになる。

【００３８】ここで、かかる変換部１５での変換動作は
次のようになる。

【００３９】まず、単純な例として図５に示すようにプ
リミティブＡ、Ｂ、Ｐからなる一重のループを考える。
このとき回路モデル格納部２においてループＬは、図６
に示すように表現されている。

【００４０】この状態から、 （１）図７のようにループＬ中のプリミティブを一つ選
ぶ。選び方は任意であるが、ここではＰを選ぶことにす
る。この場合、ループ中でＰからの出力を受けているの
はＡであるが、ループＬを構成する枝の中からプリミテ
ィブＰからＡへ向かう枝を除去する。

【００４１】次に、プリミティブＰの前クロックにおけ
る値を出力するようなプリミティブＰＦを状態記憶部に
加え、ＰＦからの出力を与える入力プリミティブＰＩ
と、ＰＦへの入力を与える出力プリミティブＰＯを新た
にプリミティブグラフに加える。 図８は回路モデルを
格納する回路モデル格納部１２に格納された図７に示す
プリミティブグラフを図３に示すデータ構造で表したも
のである。プリミティブＰを表す配列要素の出力先プリ
ミティブのリストからＡのｉｄが取り除かれ、Ａを表す
配列要素のＡへの入力元プリミティブのリストからＰの
ｉｄが取り除かれる。また、ＰＩ、ＰＯを表す配列要素
が配列に加えられる。

【００４２】（２）次に、図９に示すように、（１）に
よってＬから得られるループを含まない部分グラフをＬ
１とし、部分グラフＬ１と同一構造の部分グラフＬ１′
を作る。Ａ′とＰ′も同様に定義する。

【００４３】図１０は、図９に示すプリミティブグラフ
を図３に示すデータ構造で表したものである。Ｌ１内の
プリミティブを表す配列要素の複製が新たに加えられ
る。Ｌ１内での接続関係を保存するように作成した配列
要素の入出力リストにｉｄが加えられる。

【００４４】（３）Ｌ１′への入力枝として、Ｌ１への
入力枝に対応する入力枝を付ける。（図１１では、１１
０１〜１１０４に対応する２１０１〜２１０４を付け
る。）また、Ｌ１′のＰ′からＡへの枝と、ＰＩから
Ａ′への枝、ＰからＰＯへの枝をプリミティブグラフに
付け加える。

【００４５】図１０は、図９に示すプリミティブグラフ
を図３に示すデータ構造で表したものである。（２）で
作成した配列要素Ａ´Ｂ´Ｐ´（ｉｄすなわちＬ１´中
のプリミティブを示す配列要素）の入力リストにＳ、
Ｔ、Ｕのｉｄが付け加えられる。また、図に記入してい
ないが、Ｓ、Ｔ、Ｕの出力リストには、Ａ´、Ｂ´、Ｐ
´ｉｄが付け加えられる。次に、Ａ´の入力リストにＰ
のｉｄが、ＰＩの出力リストにＡ´のｉｄがそれぞれ付
け加えられ（すなわち、ＰＩからＡ´への入力枝が付け
加えられ）、Ａの入力リストにＰ´のｉｄ、Ｐ´の出力
リストにＡのｉｄがそれぞれ付け加えられ（すなわち、
Ｐ´からＡへの入力枝が付け加えられる）。また、Ｐの
出力リストにＰＯのｉｄ、ＰＯの入力リストにＰのｉｄ
が付け加えられる。すなわち、ＰからＰＯへの枝が付け
加えられる。

【００４６】この様にして得られたプリミティブグラフ
がもとのプリミティブグラフと論理的に等価であること
と、ループの発振の検出が可能であることを、図５およ
び図１１を用いて説明する。ここでいう発振とは、ルー
プ中に信号値の反転が奇数回現われ、信号値の確定がで
きなくなることをいう。

【００４７】図１１において、ループを展開した部分Ｅ
ＬへはＰＩおよびＳ、Ｔ、Ｕの四つのプリミティブから
の入力がある。プリミティブＳ、Ｔ、Ｕの評価が行なわ
れた後ＥＬ中のプリミティブの評価が行なわれる。図１
１におけるＰ′、Ｐの値は、それぞれ図５におけるルー
プの一周目、二周目のＰの値に相当する。

【００４８】いま、あるクロックでのＥＬ中のプリミテ
ィブの信号値の評価が行なわれたとする。そして、ま
ず、評価の結果Ｐ′の信号値とＰＩの信号値が同じにな
った場合、同じ入力が変換前のプリミティブグラフに与
えられるとＰの信号値は変化しないことになる。

【００４９】次に、Ｐ′の信号値とＰＩの信号値が異な
るがＰ′とＰの信号値が同じである場合、同じ入力を変
換前のループに与えるとＰの信号値は一度だけ変化し確
定する。これは図５においてループを何周か順をおって
評価するとわかりやすい。

【００５０】一周目においてＰの値は内部状態として持
っていた自分自身の値とＳ、Ｔ、Ｕからの入力によって
変化する。二周目においてＰの値は、一周目において得
られたＰの信号値とＳ、Ｔ、Ｕの信号値によってきまる
が、もし、二周目のＰの値が一周目のＰの値と等しけれ
ば（図１１でＰ′とＰの信号値が等しければ）、二周目
以後のループ評価においてＰの値は変化しない。なぜな
ら、二周目以後はＰを評価するための入力、すなわち前
の周でのＰの信号値とＳ、Ｔ、Ｕが変化しないからであ
る。よって、ループは発振しない。

【００５１】Ｐ′の信号値とＰＦの信号値が異なりＰ′
とＰの信号値も異なる時、同じ入力を変換前のループに
与えるとＰの値は定まらないことが同様の説明でわか
る。すなわち、各信号は二値しかとらないのでＰとＰＦ
の値は等しいことに注意すれば、三周目のＰの信号値は
一周目のＰ信号値と同じになり、以後、奇数周と偶数周
でＰの信号値が異なり、よって、ループは発振する。

【００５２】以上より、ＰとＰ′が等しいか否かをみる
とループの発振がわかり、発振していなければ、変換後
の回路のシミュレーション結果が論理的に正しいことが
分かる。

【００５３】発振の検出を行なうためのモデル変換は次
のように行なう。すなわち、図１３に示すように二つの
プリミティブＰとＰ′の出力信号を入力とし比較をする
プリミティブ（例えば二つの入力のＸＯＲをとるプリミ
ティブ）Ｘｏと、Ｘｏからの出力を受けるアウトプット
プリミティブをモデルに加える。図１４はこのステップ
において変更された回路モデル格納部１２のデータを表
している。発振の検出は、その出力値を例えばホスト計
算機などで監視すればよい。以上がループが単純な場合
の回路モデル変換方法である。

【００５４】これを具体的な回路に適用すると、図１５
（ａ）（ｂ）に示すようになる。この場合、同図（ａ）
に示す回路Ｎは、Ｓ、Ｔ、Ｕの値がそれぞれ１の時、ル
ープに沿って１周すると、論理が反転してしまい発振す
る。しかし、Ｓ、Ｔ、Ｕの値のうちどれか一つが０なら
ば、信号値の反転は偶数回なので発振は生じない。

【００５５】これを上記方法で同図（ｂ）に示す回路Ｎ
´に等価変換した際に回路Ｎ´の各論理素子の評価を行
ってみると次のようになる。

【００５６】ＰＩは前クロックでのＰの信号値を入力す
るプリミティブでありクロック０においては不定Ｘとす
る。

【００５７】ＸｏはＰとＰ´の出力のＸＯＲを取るプリ
ミティブである。ＰとＰ´の出力が等しい時は、Ｘｏの
出力は０であるが、ＰとＰ´の出力が異なる時は、Ｘｏ
の出力は１である。レベルソート法に従って各クロック
での信号値の評価をＡ´、Ｂ´、Ｐ´、Ａ、Ｂ、Ｐ、Ｘ
ｏの順で行った結果は次のようになる。

【００５８】まず、クロック０でのＰＩ、Ｓ、Ｔ、Ｕの
入力をそれぞれＸ、１、１、０とすれば、各素子の出力
信号値はそれぞれＸ、０、１、１、０、１、０となり、
クロック１でのＳ、Ｔ、Ｕの入力をそれぞれ１、１、１
とすれば、ＰＩの値は１なので、各素子の出力信号値は
それぞれ１、１、０、０、０、１、１となる。これによ
り発振が起こらない場合には、正しいシミュレーション
結果が得られ、発振が起こる場合は、Ｘｏの出力で発振
を検知できる。

【００５９】一般の複数プリミティブからなる強連結成
分は、複数ループから構成される場合もあり（図１
６）、また、複数複数プリミティブからなる強連結成分
は回路全体で一つだけとは限らない。この場合前述の方
法を拡張した次のような処理を繰り返し用いればよい。

【００６０】（１）プリミティブを二つ以上含む強連結
成分を一つ選びＳＰＧとする。また、ＳＰＧ内のプリミ
ティブを一つ選びＰとする（図１７）。

【００６１】（２）プリミティブＰに対応するフリップ
フロップＰＦを新たに状態記憶部に加え、ＰＦの出力を
与える入力プリミティブＰＩとＰＦへの入力を与える出
力プリミティブＰＯを、新たに回路モデルに格納する回
路モデル格納部１２のプリミティブグラフに加える。次
に、Ｐから部分グラフＳＰＧに出力する枝を除去し部分
グラフＳＰＧ１を作成する。この操作によりＳＰＧ１内
には、Ｐを含むループは存在しなくなる（図１８）。

【００６２】（３）ＳＰＧ１の強連結成分を求め、も
し、二つ以上のプリミティブを含む強連結成分があれ
ば、そのような強連結成分に対し再帰的にこの処理を行
い、ループに含まない部分グラフＳＰＧ２を作成する
（図１９）。

【００６３】（４）この時点ではすでにＳＰＧ２にはル
ープは含まれないので、部分グラフＳＰＧ２と同一構造
の部分グラフＳＰＧ２′を作り、ＧからＳＰＧ２′へ対
応する入力枝を付ける。その際、Ｐからの出力を受けて
いたプリミティブへの入力にはフリップフロップＰＦの
出力（すなわちＰＩからの入力）を割り当てる。また、
複製した部分グラフＳＰＧ２′に含まれるＰからの出力
を、ＳＰＧ２に含まれるプリミティブでＰからの出力を
受けていたプリミティブへの入力とする（図２０）。さ
らに、ＰＦへの出力としてＰＯへＰからの出力を繋ぐ。

【００６４】ステップ２で強連結成分に含まれるプリミ
ティブの数が少なくとも一つ以上減るので、もし、残り
のグラフ中にループ（即ち複数のプリミティブを含む強
連結成分）があったとしても、そのループ中のプリミテ
ィブ数はもとの強連結成分より一つ以上少ない。よっ
て、この手順を繰り返すことにより最終的に得られるグ
ラフにおいては、全ての強連結成分中はプリミティブを
１個からなる。すなわち、ループを含まない回路に変換
できる。

【００６５】発振を検出するためには、例えば上記手順
におけるＰとＰ′の組に対して、ＰとＰ′の信号値を入
力とし比較をするプリミティブを加えて回路外部に出力
し（すなわち出力プリミティブの入力とし）ホスト計算
機などで監視することにより行う。

【００６６】ループからなる回路を等価な回路に変換す
る変換部１５は、上記の方法で等価変換を施してループ
をなくし、かつ発振を検出できるようになったプリミテ
ィブグラフを記憶装置に格納してシミュレーション部１
に引き渡すようになる。

【００６７】なお、上述した発振の検出法はレベルソー
ト法にのみ限定されるものではない。ループを二周だけ
評価すれば発振を検出できるということは、レベルソー
ト法以外のシミュレーションアルゴリズムに適用でき
る。

【００６８】例えば、ソフトウエアシミュレータなどで
はモデルの複製を作らずに次のようにシミュレーション
する方法も考えられる。すなわち、図２１に示すように
プリミティブグラフに対して、まず、あるクロックにお
けるＬ′の評価を行ないＰの信号値を記憶装置ＰＭに格
納する。次に、ＰＭの値がＰＦの値と等しければ回路は
発振せずＰの評価結果は正しい。ＰＭの値がＰＦの値と
異なればＰＦのかわりにＰＭの値を用いてもう一度Ｌ′
の評価すなわちＰの評価を行なう。そして、Ｐの値とＰ
Ｍの値が同じなら回路は発振せず、Ｐの値とＰＭの値が
異なれば回路は発振する。

【００６９】また、上述では、信号値が２値の場合のみ
述べたが、多値の場合への拡張も可能である。

【００７０】従って、このようにすれば、従来レベルソ
ート法では原理的にシミュレーションできなかった組合
せ回路部にループを含む論理回路について、これを等価
回路モデルに変換することによりレベルソート法でシミ
ュレーションすることができるようになる。また、変換
前の回路ループの発振の検証も行うことができるように
なる。

【００７１】次に、本発明の他の実施例として、ハード
ウェアエミュレータの例を図２２、図２３により説明す
る。

【００７２】図２２はハードウェアエミュレータの構成
図である。この場合、エミュレータ２２１は論理ブロッ
クが専用のＦＰＧＡ２２２で実現される。そして、ＦＰ
ＧＡ２２２は完全クロスバスイッチ２２３を介して多段
に結合されており、信号は入力側から出力側へ一方向に
流れる。なお、ＦＰＧＡ２２２間の結合は部分クロスバ
スイッチで構成されていてもよい。

【００７３】図２３はＦＰＧＡ２２２の構成図である。
ここでのプログラム可能素子は４入力１出力の万能素子
２２２ａからなっている。一般にはＭ入力Ｎ出力型
（Ｍ、Ｎは正の整数）の万能素子であってもよい。そし
て、万能素子２２２ａは完全クロスバスイッチ２２２ｂ
を介して多段に結合されており、信号は入力側から出力
側へ一方向に流れる。なお、万能素子２２２ａ間の結合
は部分クロスバであってもよい。

【００７４】ＦＰＧＡ内の万能素子２２２ａは、４入力
１出力単位にまとめあげられた、複数個の回路素子のシ
ミュレーションを担当する（入力数が４を越える回路素
子がある場合は、それらを４入力１出力の制約を満たす
まで分解して、それらを複数の回路素子として扱
う。）。以下、この４入力１出力単位にまとめあげられ
た回路素子集合をプリミティブと呼ぶことにする。

【００７５】図２４から図２６に、回路のプリミティブ
への変換例を示している。図２４はシミュレーション対
象の回路例を示すもので、ここでは９入力２出力の回路
としてテキサス・インスツルメント製の９ビットのパリ
ティ生成器（ＳＮ７４ＡＬＳ２８０）を示している。そ
して、図２５は、図２４の回路を４入力１出力の制約を
満たすプリミティブへまとめあげた例で、図２６は、図
２５のまとめあげの結果得られたプリミティブグラフで
ある。

【００７６】これら図２４から図２６において、Ａから
Ｉは入力信号、Ｘ、Ｙは出力信号で、１〜３７はプリミ
ティブを示している。そして、各プリミティブ１〜３７
は、入力側から出力へ向かって数えた最長パスの長さの
順にレベルソートされている。

【００７７】レベルソートは、例えば「演算グラフ理論
（コロナ社）」ｐ８０およびｐ３２０に示された手続き
によって、計算機上で容易に実現できる。また、この手
続きによればレベルソートはグラフの枝数に比例する計
算の手間で高速に行うことができる。

【００７８】ここで、万能素子は隣のレベル同士としか
結合されていないため、２レベル以上離れたプリミティ
ブ間での信号値の受渡しは、途中の万能素子にその信号
値を記憶させて実現する。このため、図２６に示すプリ
ミティブグラフに、信号の受渡し用のダミープリミティ
ブを挿入する。このようにして変換されたプリミティブ
グラフを図２７に示している。図２７において３８〜４
４が、出力信号１０、１１、１２、２２、２３、２４、
２８を保持するダミープリミティブである。これらダミ
ープリミティブ３８〜４４は図中では陰影をつけて表現
した。

【００７９】次に、このような手続きを実行するための
プリミティブグラフを表現するデータ構造例を説明す
る。

【００８０】ここで、プリミティブグラフは配列で表さ
れており、各配列要素は、それぞれ一つのプリミティブ
に関する情報を含んでいる。そして、各配列要素は図２
８に示すように、（１）プリミティブｉｄ、（２）入力
プリミティブｉｄのリスト、（３）出力先プリミティブ
ｉｄのリスト、（４）ダミービット、（５）オリジナル
プリミティブｉｄ、（６）レベル、（７）連結成分ｉｄ
からなっている。

【００８１】この場合、上述の（１）〜（３）はグラフ
の接続情報、（４）〜（５）はダミープリミティブ情
報、（６）〜（７）はマッピングに関する情報である。
上記の例では、これらの情報をすべてまとめて一つの配
列として実現したが、それぞれ別々の配列として実現し
ても構わない。ダミービットはプリミティブがダミーの
とき１、そうでないとき０である。オリジナルプリミテ
ィブｉｄは、プリミティブがダミーの場合に、もとのプ
リミティブｉｄを格納する。プリミティブがダミーでな
いときは意味を持たない。

【００８２】以下、論理回路をダミープリミティブを含
むプリミティブグラフとして表現する。

【００８３】次に、図２７に示す回路を、幅方向に４
個、段数方向に３個のプリミティブが並んでいるＦＰＧ
Ａから構成される多段結合エミュレータにマッピングす
る場合を考える。

【００８４】ここでのマッピングは、図２９に示すステ
ップ２９０１〜ステップ２９０８までの処理に従い実行
される。

【００８５】この場合、まず、プリミティブグラフを入
力側からＦＰＧＡの段数である３段で区切る。図３０に
示す１０１から１０４は、このようにして得られた連結
成分を示している。

【００８６】なお、グラフによっては、ＦＰＧＡの段数
以下（例えばこの場合では２段）で区切った方が望まし
い場合もあり、これは適宜使い分けて構わない。また、
レベルで区切るという操作を適用するのは、最初に回路
全体を区切るときだけとは限らない。ＦＰＧＡ一段のマ
ッピングが終了するたびに回路のウェーブフロントから
改めて動的にレベルを計算して、そのレベルソートされ
た回路に対して、レベルで区切りなおしてもよい。

【００８７】連結成分の番号づけ（ｉｄ）は、レベルが
大きいものほど大きい番号になるようにするが、１０
１、１０２、１０３のように同じレベルに対応する連結
成分どうしは、どのような順番に番号づけしても構わな
い。ここでは１０１、１０２、１０３、１０４の順にそ
れぞれ連結成分番号１、２、３、４と番号づけがなされ
ていると仮定する。図２８は、連結成分１０１中のプリ
ミティブ１５を表現するデータ構造であり、ここでのプ
リミティブ１５のレベルは３、連結成分番号は１であ
る。

【００８８】マッピングは、番号の小さい連結成分から
順に行なう。図３０の回路のマッピングを例にとると、
１０１、１０２、１０３の連結成分はＦＰＧＡのサイズ
に収まっており、ＦＰＧＡ一個ずつにそれぞれマッピン
グを適用する。ここで、ある回路がＦＰＧＡのサイズよ
り大きいとは、その回路をレベルの順にソートしたとき
に、ＦＰＧＡの幅を越えてしまうことを指す。

【００８９】図３１の１１１から１１３はそれぞれ、１
０１から１０３の連結成分のマッピングを適用したＦＰ
ＧＡを示している。このように、一段目のレベルのＦＰ
ＧＡ（１１１、１１２、１１３）へのマッピングは、レ
ベルで区切った連結成分情報を利用して効率良く行なう
ことができる。

【００９０】次に、連結成分１０４のマッピングを考え
る。１０４は、ＦＰＧＡのサイズより大きく、ＦＰＧＡ
一個には収まらない。この場合、１０４に対しては以下
のいずれかのマッピング方式を適用する。

【００９１】 （１）接続するプリミティブを順にマッピング （２）プリミティブの番号順にマッピング （３）レベルの低いプリミティブの順にマッピング （４）プリミティブの複製を作り連結成分を複数の連結
成分に分割し、新しく得られた連結成分ごとにマッピン
グ （１）のマッピング方式では、構成成分１０４中のプリ
ミティブの中から適当なプリミティブを出発点として、
ＦＰＧＡ１１４へのマッピングを開始する。出発点とな
るプリミティブは最小レベルのものの中で任意で構わな
い。この例では番号が最も小さいプリミティブ２５を選
ぶ。次にプリミティブ２５の出力先の一つプリミティブ
２９を選び、この入力であるプリミティブ４２、４３を
マッピングする。プリミティブ２５、４２、４３の出力
先のプリミティブにはまだマッピングされていないもの
が含まれるため、これらはダミープリミティブとしてピ
ンまでつなぐ必要がある。従って、ピン数の制約からも
うこれ以上プリミティブをマッピングはできず、ＦＰＧ
Ａ１１４へのマッピングは終了する。同様の操作をＦＰ
ＧＡ１１５、１１６へと適用する。ＦＰＧＡ１１６への
マッピングが終了すると次段のＦＰＧＡへのマッピング
を行なう。ここでも同様の操作により、図３１のような
マッピング結果が得られる。

【００９２】（２）のマッピング方式では、構成成分１
０４中でまだマッピングされていないプリミティブの中
から、最も番号の小さいものを選ぶ。この例では、ＦＰ
ＧＡ１２４へのマッピングは、プリミティブ２５から２
８をマッピングして終了する。次のＦＰＧＡ１２５に
は、プリミティブ２９をマッピングする。そのために２
９への入力であるプリミティブ２５、４２、４３を前段
にマッピングする。このとき、プリミティブ３０、３
１、３２、３３は万能素子及びピンの制約を満たさない
のでマッピングすることはできないが、プリミティブ３
４は制約を満たすため、３４をマッピングして、終了す
る。以下同様の操作により図３２のようなマッピング結
果が得られる。

【００９３】ところで、回路の充填率の向上させるため
には、レベルの小さい順にプリミティブをマッピングす
る方が望ましい。なぜなら、単純にプリミティブの接続
を辿るときに比べて、入力から出力への信号の流れの中
のクリティカルパスを構成する回路素子をできるだけ早
い時期にマッピングするからである。（３）のマッピン
グ方式は、これを実現するものである。

【００９４】図３３のステップ３３０１〜ステップ３３
０６に示すアルゴリズムは、（３）のマッピング方式で
ある。これは図２９中の連結成分ｉのマッピングをさら
に詳細化して示したもので、構成成分１０４中のプリミ
ティブをレベルの小さい順にマッピングする。ＦＰＧＡ
１３４にはプリミティブ２５から２８をマッピングして
終了する。ＦＰＧＡ１３５には、プリミティブ４１から
４３をマッピングする。さらに万能素子に余裕があるた
め、プリミティブ２９をマッピングして終了する。ここ
で、１０４中の最小レベルのプリミティブがすべてマッ
ピングできたので、ＦＰＧＡ１３６には、次の段のプリ
ミティブのうち、まだマッピングされていないプリミテ
ィブ３０をマッピングする。同様の操作により、プリミ
ティブ３３をマッピングして終了する。この結果を図３
４に示す。

【００９５】なお、ＦＰＧＡ１３６へのプリミティブ３
０、３３のマッピングは、次段のＦＰＧＡへのマッピン
グ結果をみると、本来不必要なものである。従って、３
のマッピング方式では図３０の回路をエミュレータにＦ
ＰＧＡ７個でマッピング完了したことになり、（１）あ
るいは（２）のマッピング方式に比べ、ＦＰＧＡの充填
率が向上していることが分かる。

【００９６】このように、ＦＰＧＡのサイズを越える連
結成分に対しては、単純にレベルの小さい順にマッピン
グするのが望ましい。この方式は計算時間のオーバーヘ
ッドがほとんどないため、マッピングの高速性も保持さ
れる。

【００９７】もう一つ、連結成分の大きさがＦＰＧＡの
サイズを越えたときに有効であるのは、他のプリミティ
ブとの接続が多いプリミティブの複製を作り、もとの連
結成分をＦＰＧＡのサイズ以下の部分回路に分割する方
法である。これは（４）のマッピング方式である。

【００９８】次に、図３５に示す回路を段数、幅方向に
４個、段数方向に２個のプリミティブが並んでいるＦＰ
ＧＡから構成されたエミュレータにマッピングする場合
を考える。

【００９９】ＦＰＧＡの段数である２段でこの回路を区
切ったとき、図３５のように連結成分２０１〜２０４に
分割される。ここで、ＦＰＧＡのサイズを越えている連
結成分２０３に着目する。連結成分２０３を番号の順あ
るいはレベルの低い順にマッピングした結果が図３６で
ある。使用したＦＰＧＡは２１３から２１６の４個であ
る。ここで、連結成分２０３中で最もレベルの低いプリ
ミティブのうち、最も出力先のプリミティブ数が多いも
のを選び、それの複製を作る。この例では、そのような
プリミティブの候補として、プリミティブ１５、１６、
１７の３つがあるが、番号が最も小さいプリミティブ１
５を選ぶ。図３７（ａ）は連結成分２０３を構成するプ
リミティブグラフである。図３７（ｂ）はプリミティブ
１５の複製を作成することによって、連結成分２０３が
新たな３つの連結成分２２１、２２２、２２３に分解さ
れた結果を示している。ここで図３７（ｂ）のプリミテ
ィブ１５１、１５２はともにプリミティブ１５の複製を
表している。

【０１００】ここで、１５の複製を作成した後も、依然
としてＦＰＧＡのサイズを越えているため、連結成分２
２１に対して再び上記のプリミティブの複製による分解
を適用する。この結果、プリミティブ１６、１７の順に
複製を作成して得られた分解を図３７（ｃ）に示す。こ
のようにして連結成分２０３は、２３１から２３７のＦ
ＰＧＡのサイズ以下の計７個の連結成分に分解された。
連結成分２３１から２３７にそれぞれ連結成分番号３〜
９を付け、連結成分２０４に連結成分番号１０を付ける
と、図３５のプリミティブグラフは１０個のＦＰＧＡの
サイズ以下の連結成分に分けられたことになる。

【０１０１】以上の複製の作成の際に、プリミティブ１
５に関する情報がどの様に変化するするかを図３８と図
３９に示す。図３８は、複製作成前のプリミティブ情報
であり、図３９は、複製作成後のプリミティブ情報であ
る。図３９は、プリミティブ１５の出力先が１つだけの
３つのプリミティブ１５、１５１，１５２に分かれる。
ここでは、ダミープリミティブへ出力しているプリミテ
ィブに、元のプリミティブ１５と同じｉｄを付けてい
る。

【０１０２】次に、新たに得られた複数個の連結成分を
ＦＰＧＡのサイズ以下という条件を満たしながら、適当
に組み合わせてまとめ上げを行なう。まとめあげの方法
として、例えば次のような手続きがある。

【０１０３】ステップ１ Ｃ、Ｔを空集合、Ｕを上記の
手続きで得られた連結成分を要素とする集合とする。

【０１０４】ステップ２ Ｕが空ならば終了。

【０１０５】ステップ３ Ｕの中から最もサイズが大き
いものＡを選ぶ。

【０１０６】ステップ４ ＴとＡをマージしてできたグ
ラフをＳとする。

【０１０７】ステップ５ ＵがＦＰＧＡのサイズ以下な
らば、ＴをＳに置換え、ＵからＡを除き、そうでなけれ
ば、ＣにＴを登録する。

【０１０８】ステップ６ ステップ２へ行く。

【０１０９】ステップ４でのマージの結果、上記の手続
きを終了した時、Ｃには、ＦＰＧＡの大きさになるまで
まとめあげられた連結成分が要素として含まれる。この
過程で、あるダミープリミティブに対するオリジナルプ
リミティブｉｄと別のプリミティブのｉｄが一致してい
る場合は、プリミティブ同士をまとめることができる。

【０１１０】図３７（ｃ）の複数の連結成分に対して、
上記の手続きを適用する。ステップ３のＡとして、サイ
ズが一番大きいものを選ぶことにする（サイズが等しい
ときは、番号が小さい順に選ぶ）。手続きの終了時に
は、図４０に示すように連結成分２４１、２４２、２４
３にまとめあげが行なわれる。このまとめ上げの際のプ
リミティブ情報の書き換えは、連結成分の分解のときと
同様に行えば良い。必要ならば、生成した複製に対応し
たプリミティブ情報を消去する。

【０１１１】以上で得られた連結成分をもとに、図３５
の回路をプリミティブの複製を作り、グラフを再構成し
たのが、図４１である。図３５での連結成分２０３が、
図４１では、連結成分３１１、３１２、３１３になって
いる。

【０１１２】図４１のグラフをマッピングした結果を図
４２に示す。連結成分３１１、３１２、３１３のマッピ
ングに要したＦＰＧＡは３個であり、図３６に示したよ
うに（３）のマッピング方式を用いた時に、ＦＰＧＡを
４個要した場合に比べ、改善されたことが分かる。

【０１１３】従って、（４）のマッピング方式を用いれ
ば、再プログラム可能な複数の論理ブロックからなる論
理エミュレータにおいて、高速性をほとんど失うことな
くＦＰＧＡの充填率を向上させることができる。また、
プリミティブの複製によるグラフの連結成分の分割およ
び纏め上げ手続きは、機械化が容易であり、また、それ
に要する計算時間もほぼグラフの探索に要する時間と同
等である。つまり、連結成分のまとめあげも機械的であ
り、ほとんどバックトラックをしないため、同様に短時
間で実行できる。これにより、図４３のステップ４２０
１〜ステップ４２０５に示すようにプリミティブの複製
による連結成分の割り付けの手続きについても、多段結
合のエミュレータにおけるマッピングの高速性を失うこ
となく、ＦＰＧＡの充填率を向上を図ることができる。

【０１１４】なお、プログラム可能素子同士の結合が多
段接続方式以外の接続であるようなエミュレータにも本
発明のアルゴリズムは適用可能である。

【０１１５】

【発明の効果】本発明によれば、従来、組合せ回路部に
ループを含む論理回路は、レベルソート法では原理的に
シミュレーションできなかったが、このような論理回路
モデルを等価回路モデルに変換することによりレベルソ
ート法でシミュレーションすることができるようにな
る。また、変換前の回路のループの発振の検証も行うこ
とができる。

【０１１６】また、本発明によれば、再プログラム可能
な複数の論理ブロックからなる論理エミュレータにおい
て、高速性をほとんど失うことなくＦＰＧＡの充填率を
向上させるマッピング方式を実現することができ、同時
に、これら分割の手続きの機械化が容易なことから計算
機上のプログラムとして実現することもできる。

【図面の簡単な説明】

【図１】本発明の一実施例の概略構成を示す図。

【図２】一実施例のモデル変換の手続きを示す図。

【図３】配列要素の構成を示す図。

【図４】強連結成分の分解を説明する図。

【図５】ループを含む回路モデルを示す図。

【図６】ループを含む回路モデルを示す図。

【図７】切断点を指定したループを含む回路モデルを示
す図。

【図８】切断点を指定したループを含む回路モデルを示
す図。

【図９】ループを切断した部分回路を二重化した回路モ
デルを示す図。

【図１０】ループを切断した部分回路を二重化した回路
モデルを示す図。

【図１１】対応する枝を加えた等価回路モデルを示す
図。

【図１２】対応する枝を加えた等価回路モデルを示す
図。

【図１３】発振検出のためのプリミティブを加えた回路
モデルを示す図。

【図１４】発振検出のためのプリミティブを加えた回路
モデルを示す図。

【図１５】回路変換の例を示す図。

【図１６】強連結成分（複数のループ）を含む回路モデ
ルを示す図。

【図１７】切断点を指定して一つのループの切断を行な
った回路モデル１を示す図。

【図１８】切断点を指定して一つのループの切断を行な
った回路モデル２を示す図。

【図１９】ループ切断後の回路モデルと強連結成分を示
す図。

【図２０】等価回路を示す図。

【図２１】ソフトウエアシミュレータの場合のシミュレ
ーション法を説明する図。

【図２２】本発明の他の実施例のエミュレータの構成を
示す図。

【図２３】ＦＰＧＡの構成を示す図。

【図２４】シミュレーション対象回路例を示す図。

【図２５】プリミティブへのまとめあげの例を示す図。

【図２６】プリミティブグラフを示す図。

【図２７】ダミープリミティブの挿入例を示す図。

【図２８】プリミティブ情報を表現するデータ構造を示
す図。

【図２９】回路割り付け手続きの流れを示す図。

【図３０】レベルで区切ったときの連結成分を示す図。

【図３１】回路割り付け結果（プリミティブ接続をたど
る方式）を示す図。

【図３２】回路割り付け結果（プリミティブ番号順方
式）を示す図。

【図３３】連結成分の割り付け手続き（レベルの小さい
順に割り付け）を示す図。

【図３４】回路割り付け結果（レベルの小さい順方式）
を示す図。

【図３５】プリミティブグラフを示す図。

【図３６】回路割り付け結果（レベルの小さい順方式）
を示す図。

【図３７】プリミティブの複製による連結成分の分解を
示す図。

【図３８】複製作成前のプリミティブ情報を示す図。

【図３９】複製作成後のプリミティブ情報を示す図。

【図４０】連結成分のまとめあげを示す図。

【図４１】プリミティブまとめあげ後のプリミティブグ
ラフを示す図。

【図４２】回路割り付け結果（プリミティブまとめあげ
後）を示す図。

【図４３】連結成分の割り付け手続き（プリミティブの
複製による連結成分の分割）を示す図。

【符号の説明】

１１…シミュレーション部、１２…回路モデル格納部、
１３…組合せ回路部と状態記憶部を分離する分離部、１
４…ループ回路検出部、１５…ループからなる回路を等
価な回路に変換する変換部、２２１…エミュレータ、２
２２…ＦＰＧＡ２２２ａ…万能素子、２２２ｂ…完全ク
ロスバスイッチ。

Claims (4)

【特許請求の範囲】
1. 【請求項１】 論理回路をレベルソート法を用いてシミ
   ュレーションを行なう論理シミュレーション装置におい
   て、 シミュレーション対象となる論理回路を格納する手段
   と、 前記論理回路を組み合わせ回路部と状態記憶部とに分離
   する手段と、 この手段で分離された組合せ回路部より複数の論理素子
   から構成されるループからなる回路Ａを抽出する手段
   と、 前記回路Ａ中の論理素子の一つの論理素子Ｚについてそ
   の出力を取り去った回路Ｘを作成する手段、前記論理素
   子Ｚの前回の出力信号値を記憶する記憶素子Ｕを作成す
   る手段、前記回路Ｘを複製した回路Ｙを用いて、前記回
   路Ｙ、回路Ｘおよび記憶素子Ｕの縦続接続回路を構成す
   る手段を有する回路変換手段とを具備し、 前記回路Ｙの各論理素子に対し前記回路Ｘの各論理素子
   に対する入力と同じ入力を接続することを特徴とする論
   理シミュレーション装置。
2. 【請求項２】 前記回路Ｘの論理素子Ｚの出力と前記複
   製された回路Ｙの前記論理素子Ｚに相当する論理素子の
   出力を比較する手段を有し、前記ループの発振するか否
   かを検出可能にした請求項１記載の論理シミュレーショ
   ン装置。
3. 【請求項３】 再プログラム可能な複数の論理ブロック
   を多段結合した論理エミュレータにおいて、 入力側からの信号の流れの順にレベルソートされたプリ
   ミティブグラフを入力側から数えて一定のレベルごとに
   区切ることで複数の連結成分を生成し、これら連結成分
   ごとに論理ブロックに割り付けるようにしたことを特徴
   とする論理エミュレータ。
4. 【請求項４】 論理ブロックに割り付けられた連結成分
   のサイズが前記論理ブロックのサイズを越えるとき、該
   連結成分中で入力側から数えたレベルが最も小さい回路
   素子の複製を作ることで該連結成分を前記論理ブロック
   のサイズ以下の複数の連結成分に分解するとともに、こ
   れら連結成分を前記論理ブロックのサイズ以下という条
   件の下でまとめて前記論理ブロックに割り付けるように
   したことを特徴とする請求項３記載の論理エミュレー
   タ。