(57)【要約】【課題】設計した論理回路から冗長回路を自動的に検出する。【解決手段】回路構造解析手段３が、記憶手段１に格納された論理回路のうち、検証する論理回路部の構造を解析して、論理回路部の入力信号が分岐するパスを検出し、分岐したパスのいずれかを入力信号から分離し、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加し、２分決定グラフ作成手段４が、擬似端子を含めた論理回路部の２分決定グラフを作成し、冗長回路検出手段５が、作成した２分決定グラフを検証して矛盾箇所を探し、矛盾箇所に対応する論理回路部のパスを冗長回路として検出する。【選択図】図１
2008198160.tif 000002
【特許請求の範囲】
【請求項１】
設計した論理回路に含まれる冗長部分を検出する冗長回路検出方法において、
回路構造解析手段が、記憶手段に格納された前記論理回路のうち、検証する論理回路部の構造を解析して、前記論理回路部の入力信号が分岐するパスを検出し、分岐したパスのいずれかを前記入力信号から分離し、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加するステップと、
２分決定グラフ作成手段が、前記擬似端子を含めた前記論理回路部の２分決定グラフを作成するステップと、
冗長回路検出手段が、作成した前記２分決定グラフを検証して矛盾箇所を探し、前記矛盾箇所に対応する前記論理回路部のパスを冗長回路として検出するステップと、
を有することを特徴とする冗長回路検出方法。
【請求項２】
表示手段が、検出した前記冗長回路の情報を表示装置に表示するステップを、さらに有することを特徴とする請求項１記載の冗長回路検出方法。
【請求項３】
前記表示手段は、前記論理回路部における前記冗長回路部分を強調表示することを特徴とする請求項２記載の冗長回路検出方法。
【請求項４】
挿入手段が、検出された前記冗長回路に、信号検出用のフリップフロップを挿入するステップを、さらに有することを特徴とする請求項１乃至３のいずれか一項に記載の冗長回路検出方法。
【請求項５】
設計した論理回路に含まれる冗長部分を検出する処理をコンピュータに機能させるプログラムにおいて、
コンピュータを、
記憶手段に格納された前記論理回路のうち、検証する論理回路部の構造を解析して、前記論理回路部の入力信号が分岐するパスを検出し、分岐したパスのいずれかを前記入力信号から分離し、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加する回路構造解析手段、
前記擬似端子を含めた前記論理回路部の２分決定グラフを作成する２分決定グラフ作成手段、
作成した前記２分決定グラフを検証して矛盾箇所を探し、前記矛盾箇所に対応する前記論理回路部のパスを冗長回路として検出する冗長回路検出手段、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、設計した論理回路に含まれる冗長部分を検出する冗長回路検出方法及びプログラムに関する。
【背景技術】
【０００２】
特定用途向け集積回路（ＡＳＩＣ：Application Specific Integrated Circuit）の回路設計では、以下のような設計工程が用いられている。
図１２は、従来のＡＳＩＣの設計工程の流れを示すフローチャートである。
【０００３】
まず、顧客の要求を分析して、システムがどのようなサービスを提供するかを定義し、システム運用に関する制約条件を規定した要求仕様を作成する（ステップＳ５０）。
次に、システム設計を行う。ここでは、ステップＳ５０で明確にした要求仕様を実現するために必要となるシステムとしての動作仕様を策定する（ステップＳ５１）。その後、ステップＳ５１の処理で策定した動作仕様に基づき、回路の動作処理を決定し、回路記述言語にてアーキテクチャ・機能設計を行う（ステップＳ５２）。続いて、論理設計を行い、回路記述言語で表現された論理を論理回路に変換し、所望のテクノロジのライブラリセルにマッピングを行う（ステップＳ５３）。
【０００４】
その後、テスト設計では、製造段階でのトランジスタ故障を検出するための回路を設計し、ステップＳ５３の処理で作成した論理回路に挿入する（ステップＳ５４）。そして、以上の処理により作成された回路を基にレイアウト設計を行い、ＡＳＩＣデバイスの配置、配線を行い、マスクデータを作成する（ステップＳ５５）。
【０００５】
次に、ステップＳ５５の処理で作成されたマスクデータに基づき、試作・評価を行い、ＡＳＩＣを製造して、良品であるか否かなどをテストする（ステップＳ５６）。製造・テストの結果、良品と判定された場合には製品として出荷する（ステップＳ５７）。
【０００６】
なお、設計された論理回路を２分決定グラフで表現してフォーマル・ベリフィケーション（形式的検証）を行うことが知られている（例えば、非特許文献１，２参照）。
【非特許文献１】藤田，「フォーマル・ベリフィケーションの基本原理（２）」，Design Wave Magazine，２００３年９月，ｐ．１４４−１５０
【非特許文献２】藤田，「フォーマル・ベリフィケーションの基本原理（３）」，Design Wave Magazine，２００３年１０月，ｐ．１４９−１５５
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで上記のステップＳ５３の工程では、ＲＴＬ（Register Transfer Level）と呼ばれる回路記述言語から論理合成によりゲートレベルの論理回路を設計する際に、冗長回路が生成される場合がある。冗長回路は、論理的にあってもなくてもよいパスである。設計した論理回路に冗長回路が含まれると、ゲート数・消費電力の増加、故障検出率やタイミングの悪化をもたらす。
【０００８】
従来では、回路図を目視にて確認し、冗長回路を探し出していたため、膨大な時間が必要となっていた。
本発明はこのような点に鑑みてなされたものであり、設計した論理回路から容易に冗長回路を検出可能な冗長回路検出方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明者らは、回路構造解析手段が、記憶手段に格納された前記論理回路のうち、検証する論理回路部の構造を解析して、前記論理回路部の入力信号が分岐するパスを検出し、分岐したパスのいずれかを前記入力信号から分離し、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加するステップと、２分決定グラフ作成手段が、前記擬似端子を含めた前記論理回路部の２分決定グラフを作成するステップと、冗長回路検出手段が、作成した前記２分決定グラフを検証して矛盾箇所を探し、前記矛盾箇所に対応する前記論理回路部のパスを冗長回路として検出するステップと、を有することを特徴とする冗長回路検出方法を提案する。
【００１０】
上記の構成によれば、論理回路部の入力信号が分岐するパスが検出され、分岐したパスのいずれかが入力信号から分離される。分離されたパスには、擬似的に他の入力信号を設定する擬似端子が付加される。そして、付加された擬似端子を含めた論理回路部を表す２分決定グラフが作成され、作成された２分決定グラフから矛盾箇所が探し出され、その矛盾箇所に対応する論理回路部のパスが冗長回路として検出される。
【発明の効果】
【００１１】
本発明は、論理回路部の入力信号が分岐するパスを分離し、擬似端子を付加して２分決定グラフで表し、この２分決定グラフから矛盾箇所を探してそれに対応するパスを冗長回路して検出するので、冗長回路の検出を自動的に行うことが可能となり、今まで人手によって行っていた作業を効率的に行うことができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
図１は、本実施の形態の冗長回路検出方法の概略を示す図である。
本実施の形態の冗長回路検出方法では、記憶手段１（例えば、ＨＤＤ（Hard Disk Drive））に格納された論理回路を、以下の各手段で処理する。なお、各手段の詳細は後述する。
【００１３】
まず、ノード分解手段２は、記憶手段１に格納された論理回路を解析して、外部端子−ＦＦ（フリップフロップ）間またはＦＦ−ＦＦ間のノードに分解する。
回路構造解析手段３は、分解されたノードの論理回路部を検証対象として、その回路構造を解析する。そして、論理回路部の入力信号が分岐するパスを検出し、分岐したパスのいずれかをその入力信号から分離する。さらに、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加する。
【００１４】
図２は、論理回路部に擬似端子を付加した例を示す図である。
なお、以下の説明では、端子名と信号名とに同じ符号を用いることにする。
論理回路部１０への入力信号Ｘ１〜Ｘ３は、図示しないＦＦの出力端子、または外部端子から入力される。出力信号Ｑ１は、図示しないＦＦの入力端子、または外部端子に出力される。
【００１５】
論理回路部１０は、インバータ回路１１、ＡＮＤ回路１２、ＯＲ回路１３により構成されている。入力信号Ｘ１は、インバータ回路１１の入力端子とＯＲ回路１３の一方の入力端子に入力される。ＡＮＤ回路１２の３つの入力端子には、インバータ回路１１の出力信号と入力信号Ｘ２，Ｘ３とが入力される。ＡＮＤ回路１２の出力信号はＯＲ回路１３の他方の入力端子に入力される。ＯＲ回路１３の出力信号が論理回路部１０の出力信号Ｑ１となる。
【００１６】
このような論理回路部１０では、入力信号Ｘ１のパスが分岐して、インバータ回路１１とＯＲ回路１３とに入力しているため、回路構造解析手段３は、分岐したパスの一方を切断して入力信号Ｘ１から分離している（図の×印）。そして、分離したパスに、擬似的に他の入力信号Ｘ１ａを設定する擬似端子Ｘ１ａを付加している。
【００１７】
図３は、論理回路部の他の例を示す図である。
ここでも、図２と同様に擬似端子を付加した例を示している。
論理回路部２０は、ＡＮＤ回路２１，２２、ＯＲ回路２３により構成されている。入力信号Ｘ４は、ＡＮＤ回路２１の一方の入力端子に入力される。入力信号Ｘ５は、ＡＮＤ回路２２の一方の入力端子に入力される。入力信号Ｘ６は、分岐してＡＮＤ回路２１，２２の他方の入力端子に入力される。ＡＮＤ回路２１，２２の出力信号は、それぞれＯＲ回路２３に入力され、ＯＲ回路２３の出力が論理回路部２０の出力信号Ｑ２となる。
【００１８】
このような論理回路部２０では、入力信号Ｘ６のパスが分岐してＡＮＤ回路２１，２２の両方に入力しているため、回路構造解析手段３は、分岐したパスの一方を切断して入力信号Ｘ６から分離している（図の×印）。そして、分離したパスに、擬似的に他の入力信号Ｘ６ａを設定する擬似端子Ｘ６ａを付加している。
【００１９】
２分決定グラフ作成手段４は、擬似端子Ｘ１ａ，Ｘ６ａを付加した論理回路部１０，２０を表す２分決定グラフを作成する。
図４は、図２の論理回路部を表す２分決定グラフの例を示す図である。
【００２０】
また、図５は、図３の論理回路部を表す２分決定グラフの例を示す図である。
２分決定グラフを構成する各ノードは、図２や図３の端子Ｘ１〜Ｘ６，Ｘ１ａ，Ｘ６ａや、端子Ｑ１，Ｑ２に対応している。このような２分決定グラフは、公知の方法で生成可能である。例えば、非特許文献１にはａｐｐｌｙアルゴリズムにより、論理回路を２分決定グラフに変換する手法が紹介されている。
【００２１】
次に、冗長回路検出手段５は、作成した２分決定グラフに矛盾箇所がないか否か、すなわちパスとして成立しない箇所がないかを探索し、矛盾箇所に対応する論理回路部のパスを冗長回路として検出する。
【００２２】
図４の２分決定グラフにおいて、入力信号Ｘ１が０で、入力信号Ｘ１ａが１となる部分では、実際に入力信号Ｘ１ａは入力信号Ｘ１と同一であるので矛盾する。よって、図４において、点線で示した部分が矛盾箇所として検出され、この矛盾箇所に対応する図２の論理回路部１０のパスが冗長回路として検出される。
【００２３】
一方、図５の２分決定グラフでは、入力信号Ｘ６ａが１および０の両方の場合で、矛盾無くパスが成立する（パスＡ，Ｂ）。よって、図３のような論理回路部からは冗長回路が検出されない。
【００２４】
表示手段６は、検出された冗長回路を、例えば、ディスプレイ７などに表示させてユーザに提示する。
上記のような手法によれば、冗長回路の検出が自動的に行え、容易となり、今まで人手によって行っていた作業を効率的に行うことができる。
【００２５】
次に、本実施の形態の冗長回路検出方法の詳細を説明する。
図６は、冗長回路検出処理を行うコンピュータのハードウェア構成例である。
コンピュータ５０は、ＣＰＵ（Central Processing Unit）５１、半導体メモリ５２、入力Ｉ／Ｆ（Interface）５３、グラフィック処理部５４、ＨＤＤ５５などによって構成され、これらはバス５６を介して相互に接続されている。
【００２６】
ここで、ＣＰＵ５１は、半導体メモリ５２およびＨＤＤ５５に格納されているプログラムや各種データなどに応じて各部を制御し、図１に示した各手段の処理を行う。
半導体メモリ５２は、例えばフラッシュメモリなどであり、ＣＰＵ５１が実行する基本的なプログラムやデータを格納している。
【００２７】
入力Ｉ／Ｆ５３には、キーボード５３ａやマウス５３ｂなどの入力装置が接続されており、ユーザにより入力された情報を受信し、バス５６を介してＣＰＵ５１に伝送する。
グラフィック処理部５４には、ディスプレイ５４ａが接続されており、ＣＰＵ５１からの描画命令に従って、ディスプレイ５４ａ上に、冗長回路の検出結果などを表示する。
【００２８】
ＨＤＤ５５は、ＣＰＵ５１が実行するＯＳ（Operation System）のほか、図示しているような各種データやプログラムを格納している。
ネットリストは、論理合成によって作成されたゲートレベルの論理回路情報である。
【００２９】
ノード分解プログラムは、与えられたネットリストを解析し、回路の構造を外部端子−ＦＦ間またはＦＦ−ＦＦ間のノードに分解するプログラムである。
回路構造解析プログラムは、ノード分解プログラムにて分解されたノードの論理回路部の構造を解析して、擬似端子を付加するプログラムである。
【００３０】
２分決定グラフ作成プログラムは、擬似端子を付加した論理回路部（以下擬似回路と呼ぶ）から２分決定グラフを作成するプログラムである。
冗長回路検出プログラムは、２分決定グラフ作成プログラムで作成された２分決定グラフから矛盾箇所を探し、矛盾箇所に対応する論理回路部のパスを冗長回路として検出するプログラムである。
【００３１】
冗長回路情報表示プログラムは、冗長回路検出プログラムで検出した冗長回路の情報をディスプレイ５４ａに表示するプログラムである。
ノード情報データベースは、ノード分解プログラムで分解されたノードの情報を格納する。
【００３２】
擬似回路データベースは、回路構造解析プログラムで作成した擬似回路を格納する。
２分決定グラフデータベースは、２分決定グラフ作成プログラムで作成された２分決定グラフを格納する。
【００３３】
冗長回路情報データベースは、冗長回路検出プログラムで検出した冗長回路の情報を格納する。
テストポイント挿入プログラムは、冗長回路検出プログラムで検出した冗長回路に後述のテストポイントを挿入することにより、故障検出率を向上するような対策を行うプログラムである。
【００３４】
なお、上記では処理ごとに異なるプログラムとしているが、これらを組み合わせて１つのプログラムとしてもよい。
また、処理内容を記述したプログラムは、ＨＤＤ５５以外にも、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【００３５】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００３６】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００３７】
以下、図６の構成による本実施の形態の冗長回路検出方法の詳細を説明する。
図７は、本実施の形態の冗長回路検出方法の処理の流れを示すフローチャートである。
まず、ＣＰＵ５１はノード分解プログラムを実行する。ノード分解プログラムが実行されると、ＨＤＤ５５に格納されたネットリストが読み出され、ノードが解析され、ＦＦ−ＦＦ間、または外部端子−ＦＦ間のノードの論理回路部に分解される。分解されたノードの情報はＨＤＤ５５のノード情報データベースに格納される（ステップＳ１０）。
【００３８】
図８は、ノード情報データベースの例である。
ここでは、図２のような論理回路部（ただし、擬似端子付加前）のノード情報の一例を示している。スタートポイントとして端子Ｘ１〜Ｘ３と、エンドポイントとして端子Ｑ１が指定されており、さらにスタートポイントとエンドポイントとの接続関係を示す論理式が表されている。論理式（Ｘ１｜（〜Ｘ１＆Ｘ２＆Ｘ３））は、入力信号Ｘ１を反転したものと入力信号Ｘ２，Ｘ３との論理積の結果に対して、入力信号Ｘ１との論理和をとることを示している。
【００３９】
上記のようなノード解析、分解処理が終わると、ＣＰＵ５１は回路構造解析プログラムを実行する。回路構造解析プログラムが実行されると、ノード情報データベースに格納されたノードの情報が読み出される。そして、読み出されたノードの論理回路部において、入力信号が分岐するパスが検出され、分岐したパスのいずれかを入力信号から分離する。例えば、図２のような論理回路部の場合、インバータ回路１１の入力側のパスを分離するか、ＯＲ回路１３の入力側のパスを分離する。さらに、分離したパスに擬似的に他の入力信号を設定する擬似端子を付加する。擬似端子が付加された擬似回路は、ＨＤＤ５５の擬似回路データベースに格納される（ステップＳ１１）。
【００４０】
図９は、擬似回路データベースの例である。
ここでは、擬似端子付加後の、図２のような擬似回路の情報を示している。図８で示したノード情報データベースのスタートポイントに、擬似端子Ｘ１ａを追加し、スタートポイントとエンドポイントとの接続関係を示す論理式を記録している。論理式（Ｘ１｜（〜Ｘ１ａ＆Ｘ２＆Ｘ３））は、入力信号Ｘ１ａを反転したものと入力信号Ｘ２，Ｘ３との論理積の結果に対して、入力信号Ｘ１との論理和をとることを示している。
【００４１】
次に、ＣＰＵ５１は２分決定グラフ作成プログラムを実行し、擬似回路データベースから擬似回路を読み出して、図４、図５のような２分決定グラフを作成する。そして作成した２分決定グラフをＨＤＤ５５の２分決定グラフデータベースに格納する（ステップＳ１２）。
【００４２】
その後、ＣＰＵ５１は、冗長回路検出プログラムを実行し、２分決定グラフを解析して、図４で示したような、パスとして成立しない矛盾箇所を探索し、冗長回路を検出する（ステップＳ１３）。
【００４３】
冗長回路が検出されると、ＣＰＵ５１は、冗長回路情報表示プログラムを実行し、グラフィック処理部５４を制御して、ステップＳ１３の処理で検出した冗長回路の情報をディスプレイ５４ａに表示させる（ステップＳ１４）。
【００４４】
図１０は、冗長回路情報の表示例である。
検出した冗長回路のパスの情報を、例えば、スタートポイントからエンドポイントまで表示する。さらに、図のように回路図を表示して、冗長回路と判定されたパスを太線にしたり、色づけして強調表示するようにしてもよい。これにより、ユーザに直感的かつ視覚的に冗長箇所を認識させることができる。
【００４５】
なお、図４、図５で示したような２分決定グラフを表示するようにしてもよい。
また、冗長回路情報を他のソフトウェアで読み込んで処理を行うこともできる。
次に、ＣＰＵ５１はテストポイント挿入プログラムを実行して、冗長箇所にテストポイントを挿入する（ステップＳ１５）。
【００４６】
テストポイントは、図１２のステップＳ５６の出荷前のテスト工程において、故障検出率を向上させるための技術である。本実施の形態では、ステップＳ１３の処理で検出された冗長箇所にテストポイントとしてＦＦを挿入する。
【００４７】
図１１は、テストポイント挿入後の論理回路部である。
図２と同じ構成要素については同一符号としている。
冗長箇所にあるインバータ回路１１の出力が、１または０で固定されるような故障が発生した場合、外部ではそれを検出することができない。この変化を見るためにテストポイント挿入プログラムが実行されると、例えば、インバータ回路１１の出力にＤ端子を接続した信号検出用のＦＦ６０が挿入される。このＦＦ６０はＤ端子、ＳＩＮ端子とＳＯＵＴ端子を備え、ＳＩＮ信号によって、インバータ回路１１の出力の状態をラッチして、クロック信号ＣＫによって、ＳＯＵＴ端子から後段のＦＦ６０−１のＳＩＮ端子に出力する。ＦＦ６０−１〜６０−ｎは数珠繋ぎに接続されており、スキャンチェーンと呼ばれている。ＦＦ６０−１に取り込まれた信号は、クロック信号ＣＫに応じてシフトされていき、最後段のＦＦ６０−ｎのＳＯＵＴ端子と接続された外部端子ＯＵＴから出力される。
【００４８】
これにより、ユーザは出荷前のテスト工程において、冗長箇所の故障を容易に検出することができる。
以上、本発明を実施の形態に基づいて説明したが、本発明は上記に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【００４９】
【図１】本実施の形態の冗長回路検出方法の概略を示す図である。
【図２】論理回路部に擬似端子を付加した例を示す図である。
【図３】論理回路部の他の例を示す図である。
【図４】図２の論理回路部を表す２分決定グラフの例を示す図である。
【図５】図３の論理回路部を表す２分決定グラフの例を示す図である。
【図６】冗長回路検出処理を行うコンピュータのハードウェア構成例である。
【図７】本実施の形態の冗長回路検出方法の処理の流れを示すフローチャートである。
【図８】ノード情報データベースの例である。
【図９】擬似回路データベースの例である。
【図１０】冗長回路情報の表示例である。
【図１１】テストポイント挿入後の論理回路部である。
【図１２】従来のＡＳＩＣの設計工程の流れを示すフローチャートである。
【符号の説明】
【００５０】
１  記憶手段
２  ノード分解手段
３  回路構造解析手段
４  ２分決定グラフ作成手段
５  冗長回路検出手段
６  表示手段
７  ディスプレイ
【図１】
2008198160.tif 000003
【図２】
2008198160.tif 000004
【図３】
2008198160.tif 000005
【図４】
2008198160.tif 000006
【図５】
2008198160.tif 000007
【図６】
2008198160.tif 000008
【図７】
2008198160.tif 000009
【図８】
2008198160.tif 000010
【図９】
2008198160.tif 000011
【図１０】
2008198160.tif 000012
【図１１】
2008198160.tif 000013
【図１２】
2008198160.tif 000014