JP2000305967A - 状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体 - Google Patents
状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体Info
- Publication number
- JP2000305967A JP2000305967A JP11113916A JP11391699A JP2000305967A JP 2000305967 A JP2000305967 A JP 2000305967A JP 11113916 A JP11113916 A JP 11113916A JP 11391699 A JP11391699 A JP 11391699A JP 2000305967 A JP2000305967 A JP 2000305967A
- Authority
- JP
- Japan
- Prior art keywords
- state
- state transition
- unit
- route
- circuit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Abstract
(57)【要約】
【課題】 開始状態から終了状態までの各径路に要する
処理時間が均等になるように状態遷移図を調整する状態
遷移図調整装置と、その状態遷移図調整装置を用いて効
率良く論理回路を設計する論理回路設計装置を提供する
ことを課題とする。 【解決手段】 状態遷移間関係解析部１０２は、状態遷
移図から親子関係を解析し、全経路探索部１０３は、状
態遷移図に含まれる経路を探索し、経路処理時間算出部
１０４は、経路処理時間を算出し、待機状態挿入部１０
５はすべての経路の処理時間が等しくなるように状態図
中に待機状態を挿入し、状態遷移図を調整する。
処理時間が均等になるように状態遷移図を調整する状態
遷移図調整装置と、その状態遷移図調整装置を用いて効
率良く論理回路を設計する論理回路設計装置を提供する
ことを課題とする。 【解決手段】 状態遷移間関係解析部１０２は、状態遷
移図から親子関係を解析し、全経路探索部１０３は、状
態遷移図に含まれる経路を探索し、経路処理時間算出部
１０４は、経路処理時間を算出し、待機状態挿入部１０
５はすべての経路の処理時間が等しくなるように状態図
中に待機状態を挿入し、状態遷移図を調整する。
Description
【０００１】
【発明の属する技術分野】本発明は、状態遷移回路によ
る制御回路を生成する論理回路設計装置に係り、一定の
応答時間の求められる分野の回路を生成する論理回路設
計装置に関する。
る制御回路を生成する論理回路設計装置に係り、一定の
応答時間の求められる分野の回路を生成する論理回路設
計装置に関する。
【０００２】
【従来の技術】論理回路の遅延時間の自動調整に関し
て、静的タイミング解析手法に基づくものがある。その
例として、「遅延時間調整方法および装置」（特開平７
−４９８８５）や「静的タイミング解析のための自動遅
延調整システム」（特開平４−２１６１７３）がある。
て、静的タイミング解析手法に基づくものがある。その
例として、「遅延時間調整方法および装置」（特開平７
−４９８８５）や「静的タイミング解析のための自動遅
延調整システム」（特開平４−２１６１７３）がある。
【０００３】「遅延時間調整方法および装置」（特開平
７−４９８８５）では、図１４に示すフローチャートの
ように、設計対象の論理回路内のすべての信号経路を検
出対象経路として抽出するステップ１４００と、上記検
出対象経路の中から遅延時間調整対象の複数の信号経路
の組を比較対象経路として抽出するステップ１４０１
と、上記比較対象経路を構成する各々の経路のレジスタ
係数を相互に比較するステップ１４０２と、上記各々の
経路のレジスタ係数を相互に比較しその差である係数差
値を供給するステップ１４０３と、上記レジスタ係数の
少ない方の信号経路に上記係数値に等しいレジスタ係数
を持つブロックを挿入するステップ１４０４と、ステッ
プ１４０４の処理結果後の上記各々の経路のレジスタ係
数を相互に再比較するステップ１４０５とを含む。
７−４９８８５）では、図１４に示すフローチャートの
ように、設計対象の論理回路内のすべての信号経路を検
出対象経路として抽出するステップ１４００と、上記検
出対象経路の中から遅延時間調整対象の複数の信号経路
の組を比較対象経路として抽出するステップ１４０１
と、上記比較対象経路を構成する各々の経路のレジスタ
係数を相互に比較するステップ１４０２と、上記各々の
経路のレジスタ係数を相互に比較しその差である係数差
値を供給するステップ１４０３と、上記レジスタ係数の
少ない方の信号経路に上記係数値に等しいレジスタ係数
を持つブロックを挿入するステップ１４０４と、ステッ
プ１４０４の処理結果後の上記各々の経路のレジスタ係
数を相互に再比較するステップ１４０５とを含む。
【０００４】この遅延時間調整方法を実行するコンピュ
ータ支援設計（ＣＡＤ）装置である遅延時間調整装置を
図１５に示す。遅延時間調整装置は、回路図を生成する
回路図エデイタ１５００と、個々の論理回路素子（セ
ル）のレジスタに対する遅延時間比であるレジスタ係数
を含むセルライブラリ１５０１と、セルライブラリ１５
０１からのデータにより回路図エデイタ１５００により
生成された回路データ１５０２と、遅延時間調整処理の
範囲の指定等の実行条件により回路データ１５０２の処
理対象の信号経路（以下、対象経路）の各々についてレ
ジスタ係数を検出し比較する検出比較手段１５０４と、
検出比較手段１５０４の結果のレジスタ係数データをフ
ァイルするレジスタ係数ファイル１５０５と、セルライ
ブラリ１５０１と回路データ１５０２とレジスタ係数フ
ァイル１５０５とからデータの供給を受け回路データ１
５０２からのデータに所要の係数値のレジスタを挿入す
るレジスタ挿入手段１５０６と、レジスタ挿入手段１５
０６の処理結果である同期調整済の回路データを格納す
る同期回路データファイル１５０７とを備える。この装
置により、論理回路の遅延時間を調整する。
ータ支援設計（ＣＡＤ）装置である遅延時間調整装置を
図１５に示す。遅延時間調整装置は、回路図を生成する
回路図エデイタ１５００と、個々の論理回路素子（セ
ル）のレジスタに対する遅延時間比であるレジスタ係数
を含むセルライブラリ１５０１と、セルライブラリ１５
０１からのデータにより回路図エデイタ１５００により
生成された回路データ１５０２と、遅延時間調整処理の
範囲の指定等の実行条件により回路データ１５０２の処
理対象の信号経路（以下、対象経路）の各々についてレ
ジスタ係数を検出し比較する検出比較手段１５０４と、
検出比較手段１５０４の結果のレジスタ係数データをフ
ァイルするレジスタ係数ファイル１５０５と、セルライ
ブラリ１５０１と回路データ１５０２とレジスタ係数フ
ァイル１５０５とからデータの供給を受け回路データ１
５０２からのデータに所要の係数値のレジスタを挿入す
るレジスタ挿入手段１５０６と、レジスタ挿入手段１５
０６の処理結果である同期調整済の回路データを格納す
る同期回路データファイル１５０７とを備える。この装
置により、論理回路の遅延時間を調整する。
【０００５】しかしながら、この発明では、回路中の任
意の２点間の遅延時間を調整することができても、制御
回路の任意の状態間、例えば、開始状態から終了状態の
処理時間を一定にすることができない。また、調整のた
めに追加されるレジスタが増加してしまう。更に、レジ
スタブロックの挿入段階で、レイアウトを考慮していな
いので、タイミングに関する問題が発生し得る。
意の２点間の遅延時間を調整することができても、制御
回路の任意の状態間、例えば、開始状態から終了状態の
処理時間を一定にすることができない。また、調整のた
めに追加されるレジスタが増加してしまう。更に、レジ
スタブロックの挿入段階で、レイアウトを考慮していな
いので、タイミングに関する問題が発生し得る。
【０００６】また、「静的タイミング解析のための自動
遅延調節システム」（特開平４−２１６１７３）は、静
的タイミング解析ベースのタイミング自動遅延調整方法
について開示している。なお、静的タイミング解析の一
例は、米国特許第４２６３６５１号明細書に示されてい
る。特開平４−２１６１７３では、静的条件で多相時刻
論理ネットワークの動作を解析するシステムで、信号遅
延の解析を改善し、遅延時間を調整するものであるが、
レジスタの追加挿入等の機能に関して示されていない。
遅延調節システム」（特開平４−２１６１７３）は、静
的タイミング解析ベースのタイミング自動遅延調整方法
について開示している。なお、静的タイミング解析の一
例は、米国特許第４２６３６５１号明細書に示されてい
る。特開平４−２１６１７３では、静的条件で多相時刻
論理ネットワークの動作を解析するシステムで、信号遅
延の解析を改善し、遅延時間を調整するものであるが、
レジスタの追加挿入等の機能に関して示されていない。
【０００７】従って、この発明では、多相クロックを持
つ論理回路の任意の２転換の遅延時間を調整することが
できても、先ほど、説明したように、制御回路の任意の
状態間、例えば、開始状態から終了状態の処理時間を一
定にすることができない。
つ論理回路の任意の２転換の遅延時間を調整することが
できても、先ほど、説明したように、制御回路の任意の
状態間、例えば、開始状態から終了状態の処理時間を一
定にすることができない。
【０００８】更に、通常、このような処理時間を一定に
する状態遷移回路は、すべての経路を設計者自信が考
え、各経路に費やされる処理時間を計算し、処理時間を
一定にするように、最大の処理時間との差分の時間待機
する状態を挿入することにより作成される。この場合、
待機時間挿入ミスによる処理時間のばらつき、つまり動
作不良がおきる等の問題が発生し得る可能性がある。
する状態遷移回路は、すべての経路を設計者自信が考
え、各経路に費やされる処理時間を計算し、処理時間を
一定にするように、最大の処理時間との差分の時間待機
する状態を挿入することにより作成される。この場合、
待機時間挿入ミスによる処理時間のばらつき、つまり動
作不良がおきる等の問題が発生し得る可能性がある。
【０００９】
【発明が解決しようとする課題】本発明は、上記の問題
を解決するためになされたものであって、特に、総処理
時間が一定になることが要求される分野の回路設計にお
いて、処理の開始から終了までの処理時間がどの経路を
通っても同じ時間になる状態遷移図と、その状態遷移図
から機能記述を生成し、論理合成でネットリストに変換
することを目的とする。また、状態遷移図から一旦、機
能記述に変換する段階で追加挿入した回路を共有化し、
論理合成する回路のゲートサイズ（面積）を小さくする
ことを目的とする。更に、レイアウトのセル配置の際に
状態遷移機械部と出力信号部がグループ化して配置し、
制御回路内のタイミング上のクロックスキューによる問
題などの発生を抑えることを目的とする。
を解決するためになされたものであって、特に、総処理
時間が一定になることが要求される分野の回路設計にお
いて、処理の開始から終了までの処理時間がどの経路を
通っても同じ時間になる状態遷移図と、その状態遷移図
から機能記述を生成し、論理合成でネットリストに変換
することを目的とする。また、状態遷移図から一旦、機
能記述に変換する段階で追加挿入した回路を共有化し、
論理合成する回路のゲートサイズ（面積）を小さくする
ことを目的とする。更に、レイアウトのセル配置の際に
状態遷移機械部と出力信号部がグループ化して配置し、
制御回路内のタイミング上のクロックスキューによる問
題などの発生を抑えることを目的とする。
【００１０】
【課題を解決するための手段】この発明に係る状態遷移
情報調整装置は、開始状態から終了状態までの経路を複
数含む状態遷移情報を調整する状態遷移情報調整装置で
あって、以下の要素を有することを特徴とする。 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索部、（２）探索された複
数の経路について、それぞれの経路処理時間を算出する
経路処理時間算出部、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入部。
情報調整装置は、開始状態から終了状態までの経路を複
数含む状態遷移情報を調整する状態遷移情報調整装置で
あって、以下の要素を有することを特徴とする。 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索部、（２）探索された複
数の経路について、それぞれの経路処理時間を算出する
経路処理時間算出部、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入部。
【００１１】また、経路探索部は、すべての経路を探索
することを特徴とする。
することを特徴とする。
【００１２】また、経路探索部は、以下の要素を有する
ことを特徴とする。 （ａ）シミュレーションに用いるシミュレーション入力
データを記憶するシミュレーション入力データ記憶部、
（ｂ）記憶されているシミュレーション入力データに基
づいてシミュレーションを実行するシミュレーション実
行部、（ｃ）シミュレーションで通過する経路をトレー
スし、経路を探索するトレース経路探索部。
ことを特徴とする。 （ａ）シミュレーションに用いるシミュレーション入力
データを記憶するシミュレーション入力データ記憶部、
（ｂ）記憶されているシミュレーション入力データに基
づいてシミュレーションを実行するシミュレーション実
行部、（ｃ）シミュレーションで通過する経路をトレー
スし、経路を探索するトレース経路探索部。
【００１３】また、状態遷移情報調整装置は、親の状態
遷移の特定状態で、子の状態遷移が開始し、子の状態遷
移が終了した後に、親の状態遷移がその特定状態から進
行する親子関係を解析する状態遷移間関係解析部を有
し、経路探索部は、すべての子の状態遷移について、経
路を探索し、経路処理時間算出部は、すべての子の状態
遷移について、経路処理時間を算出し、待機状態挿入部
は、すべての子の状態遷移について、待機状態を挿入
し、経路探索部は、親の状態遷移について、経路を探索
し、経路処理時間算出部は、親の状態遷移について、経
路処理時間を算出し、待機状態挿入部は、親の状態遷移
について、待機状態を挿入することを特徴とする。
遷移の特定状態で、子の状態遷移が開始し、子の状態遷
移が終了した後に、親の状態遷移がその特定状態から進
行する親子関係を解析する状態遷移間関係解析部を有
し、経路探索部は、すべての子の状態遷移について、経
路を探索し、経路処理時間算出部は、すべての子の状態
遷移について、経路処理時間を算出し、待機状態挿入部
は、すべての子の状態遷移について、待機状態を挿入
し、経路探索部は、親の状態遷移について、経路を探索
し、経路処理時間算出部は、親の状態遷移について、経
路処理時間を算出し、待機状態挿入部は、親の状態遷移
について、待機状態を挿入することを特徴とする。
【００１４】また、待機状態挿入部は、親の状態遷移に
ついて、待機状態を挿入する場合に、親の状態遷移の経
路上にある子の状態遷移の状態遷移情報の経路中に、算
出した待機時間に相当する待機状態を挿入することを特
徴とする。
ついて、待機状態を挿入する場合に、親の状態遷移の経
路上にある子の状態遷移の状態遷移情報の経路中に、算
出した待機時間に相当する待機状態を挿入することを特
徴とする。
【００１５】この発明に係る回路設計装置は、以下の要
素を有することを特徴とする。 （Ａ）状態遷移情報を入力する状態遷移情報入力部、
（Ｂ）入力した状態遷移情報を調整する請求項１記載の
状態遷移情報調整装置、（Ｃ）状態遷移情報調整装置に
より調整された状態遷移情報から機能記述言語を生成す
る機能記述言語生成部、（Ｄ）生成された機能記述言語
から論理回路を合成する論理回路合成部。
素を有することを特徴とする。 （Ａ）状態遷移情報を入力する状態遷移情報入力部、
（Ｂ）入力した状態遷移情報を調整する請求項１記載の
状態遷移情報調整装置、（Ｃ）状態遷移情報調整装置に
より調整された状態遷移情報から機能記述言語を生成す
る機能記述言語生成部、（Ｄ）生成された機能記述言語
から論理回路を合成する論理回路合成部。
【００１６】また、論理回路合成部は、待機状態を設定
する複数のカウンタとして共用される共用カウンタを用
いて、論理回路を合成することを特徴とする。
する複数のカウンタとして共用される共用カウンタを用
いて、論理回路を合成することを特徴とする。
【００１７】また、待機状態挿入部は、状態遷移情報の
経路中に待機状態を挿入する場合に、他の経路中に挿入
された待機状態を共用することを特徴とする。
経路中に待機状態を挿入する場合に、他の経路中に挿入
された待機状態を共用することを特徴とする。
【００１８】また、回路設計装置は、更に、合成された
論理回路を半導体にレイアウトする半導体レイアウト部
を有し、論理回路合成部は、状態機械部回路と出力信号
生成部回路とを有する状態遷移回路を含む論理回路を合
成する場合に、同一の状態遷移回路を構成する状態機械
部回路と出力信号生成部回路とをグループ化するグルー
プ化情報を生成し、半導体レイアウト部は、生成された
グループ化情報に基づいて、同一の状態遷移回路を構成
する状態機械部回路と出力信号生成部回路とを近隣にレ
イアウトすることを特徴とする。
論理回路を半導体にレイアウトする半導体レイアウト部
を有し、論理回路合成部は、状態機械部回路と出力信号
生成部回路とを有する状態遷移回路を含む論理回路を合
成する場合に、同一の状態遷移回路を構成する状態機械
部回路と出力信号生成部回路とをグループ化するグルー
プ化情報を生成し、半導体レイアウト部は、生成された
グループ化情報に基づいて、同一の状態遷移回路を構成
する状態機械部回路と出力信号生成部回路とを近隣にレ
イアウトすることを特徴とする。
【００１９】この発明に係るプログラムを記録したコン
ピュータ読み取り可能な記録媒体は、開始状態から終了
状態までの経路を複数含む状態遷移情報を調整する状態
遷移情報調整処理であって、以下の要素を有する状態遷
移情報調整処理をコンピュータに実行させるためのプロ
グラムを記録したコンピュータ読み取り可能な記録媒体
である。 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索処理、（２）探索された
各経路について、それぞれの経路処理時間を算出する経
路処理時間算出処理、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入処理。
ピュータ読み取り可能な記録媒体は、開始状態から終了
状態までの経路を複数含む状態遷移情報を調整する状態
遷移情報調整処理であって、以下の要素を有する状態遷
移情報調整処理をコンピュータに実行させるためのプロ
グラムを記録したコンピュータ読み取り可能な記録媒体
である。 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索処理、（２）探索された
各経路について、それぞれの経路処理時間を算出する経
路処理時間算出処理、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入処理。
【００２０】
【発明の実施の形態】以下、本発明を図面に示す実施の
形態に基づいて説明する。 実施の形態１．図１に、実施の形態１に係る論理回路設
計装置のブロック図を示す。この構成における基本的動
作について説明する。状態遷移仕様入力部１０１は、状
態遷移回路を入力し、状態遷移図を出力する。状態遷移
図ＤＢ１１１は、出力された状態遷移図をデータベース
として管理する。状態遷移間関係解析部１０２は、複数
の状態遷移間の親子関係を解析する。全経路探索部１０
３は、経路解析条件ファイル１１２の規則に基づき、も
ともとの状態遷移図に記述している遷移条件に関係な
く、実際の回路の動作では起こり得ない経路も含む全経
路の探索を行う。経路解析条件ファイル１１２には、状
態遷移回路に対して、処理開始状態、処理終了状態及び
各状態に要する処理時間と、状態遷移図の閉ループの繰
り返し回数が記述されている。全経路探索部１０３の処
理については、後に詳述する。次に、経路処理時間算出
部１０４は、各経路の処理時間を累積し、各経路の処理
時間を求める。経路処理時間算出部１０４の処理につい
ても、後に詳述する。待機状態挿入部１０５は、探索し
たすべての経路の中で、最大の処理時間を要する経路を
求め、その最大の処理時間と各経路の処理時間の差分を
算出する。更に、その差分の時間待機する状態を状態遷
移図に挿入し、状態遷移図ＤＢ１１１を更新する。待機
状態挿入部１０５の処理についても、後に詳述する。
形態に基づいて説明する。 実施の形態１．図１に、実施の形態１に係る論理回路設
計装置のブロック図を示す。この構成における基本的動
作について説明する。状態遷移仕様入力部１０１は、状
態遷移回路を入力し、状態遷移図を出力する。状態遷移
図ＤＢ１１１は、出力された状態遷移図をデータベース
として管理する。状態遷移間関係解析部１０２は、複数
の状態遷移間の親子関係を解析する。全経路探索部１０
３は、経路解析条件ファイル１１２の規則に基づき、も
ともとの状態遷移図に記述している遷移条件に関係な
く、実際の回路の動作では起こり得ない経路も含む全経
路の探索を行う。経路解析条件ファイル１１２には、状
態遷移回路に対して、処理開始状態、処理終了状態及び
各状態に要する処理時間と、状態遷移図の閉ループの繰
り返し回数が記述されている。全経路探索部１０３の処
理については、後に詳述する。次に、経路処理時間算出
部１０４は、各経路の処理時間を累積し、各経路の処理
時間を求める。経路処理時間算出部１０４の処理につい
ても、後に詳述する。待機状態挿入部１０５は、探索し
たすべての経路の中で、最大の処理時間を要する経路を
求め、その最大の処理時間と各経路の処理時間の差分を
算出する。更に、その差分の時間待機する状態を状態遷
移図に挿入し、状態遷移図ＤＢ１１１を更新する。待機
状態挿入部１０５の処理についても、後に詳述する。
【００２１】機能記述言語生成部１０６は、状態遷移図
から機能記述言語１１３を生成する。回路合成部１０７
は、機能記述言語１１３からネットリスト１１４とセル
配置指示情報１１５を生成する論理合成を行う。１１４
は、半導体のテクノロジー情報を含むゲートレベルのネ
ットリストであり、セル配置指示情報１１５は、状態遷
移回路の状態遷移機械部と出力信号生成部とを識別する
情報である。半導体レイアウト部１０８は、ネットリス
ト１１４とセル配置指示情報１１５から半導体のレイア
ウトを行う。
から機能記述言語１１３を生成する。回路合成部１０７
は、機能記述言語１１３からネットリスト１１４とセル
配置指示情報１１５を生成する論理合成を行う。１１４
は、半導体のテクノロジー情報を含むゲートレベルのネ
ットリストであり、セル配置指示情報１１５は、状態遷
移回路の状態遷移機械部と出力信号生成部とを識別する
情報である。半導体レイアウト部１０８は、ネットリス
ト１１４とセル配置指示情報１１５から半導体のレイア
ウトを行う。
【００２２】続いて、全経路探索部１０３、経路処理時
間算出部１０４、待機状態挿入部１０５の処理について
詳述する。図２に、待機時間を設定する前の状態遷移図
の例を示す。つまり、この図は、状態遷移間関係解析部
１０２の結果に、経路解析条件ファイル１１２を加えた
ものである。この例では、開始状態・終了状態が共通で
あり、処理時間は、状態Ａが１クロック、状態Ｂが５ク
ロック、状態Ｃが１クロック、状態Ｄが２クロックであ
る。
間算出部１０４、待機状態挿入部１０５の処理について
詳述する。図２に、待機時間を設定する前の状態遷移図
の例を示す。つまり、この図は、状態遷移間関係解析部
１０２の結果に、経路解析条件ファイル１１２を加えた
ものである。この例では、開始状態・終了状態が共通で
あり、処理時間は、状態Ａが１クロック、状態Ｂが５ク
ロック、状態Ｃが１クロック、状態Ｄが２クロックであ
る。
【００２３】全経路探索部１０３の探索により、開始状
態から終了状態までには、全部で２つの経路が存在する
ことが分かる。１つの経路は、開始・終了状態→状態Ａ
（１クロック）→状態Ｂ（５クロック）→開始・終了状
態で、もう１つの経路は、開始・終了状態→状態Ａ（１
クロック）→状態Ｂ（５クロック）→状態Ｃ（１クロッ
ク）→状態Ｄ（２クロック）→開始・終了状態である。
態から終了状態までには、全部で２つの経路が存在する
ことが分かる。１つの経路は、開始・終了状態→状態Ａ
（１クロック）→状態Ｂ（５クロック）→開始・終了状
態で、もう１つの経路は、開始・終了状態→状態Ａ（１
クロック）→状態Ｂ（５クロック）→状態Ｃ（１クロッ
ク）→状態Ｄ（２クロック）→開始・終了状態である。
【００２４】経路処理時間算出部１０４の算出により、
前者が６クロックかかり、後者が９クロックかかること
が分かる。このように、処理の開始状態から終了状態ま
での処理時間が経路によって異なっていると、処理時間
を一定にすることができていない。
前者が６クロックかかり、後者が９クロックかかること
が分かる。このように、処理の開始状態から終了状態ま
での処理時間が経路によって異なっていると、処理時間
を一定にすることができていない。
【００２５】待機状態挿入部１０５は、最大処理時間９
クロックと後者の処理時間の差分３クロックを求め、後
者に３クロック挿入する必要があると判断する。そし
て、状態Ｂ→開始・終了状態の間のポイントに、３クロ
ックの待機状態を挿入する。待機状態を挿入するポイン
トは、基本的に、終了状態の直前である。但し、その他
のポイントに待機状態を設定する場合は、経路解析条件
ファイルに、挿入場所を指定するか、或いは、インター
ラプテイブに設定を行う。図３に、待機時間を設定した
後の状態遷移図の例を示す。つまり、この図は、待機状
態挿入部１０５の出力結果である。上述の処理により、
処理の開始から終了までのどの経路を通っても、処理時
間が一定となる状態遷移図を生成することができる。
クロックと後者の処理時間の差分３クロックを求め、後
者に３クロック挿入する必要があると判断する。そし
て、状態Ｂ→開始・終了状態の間のポイントに、３クロ
ックの待機状態を挿入する。待機状態を挿入するポイン
トは、基本的に、終了状態の直前である。但し、その他
のポイントに待機状態を設定する場合は、経路解析条件
ファイルに、挿入場所を指定するか、或いは、インター
ラプテイブに設定を行う。図３に、待機時間を設定した
後の状態遷移図の例を示す。つまり、この図は、待機状
態挿入部１０５の出力結果である。上述の処理により、
処理の開始から終了までのどの経路を通っても、処理時
間が一定となる状態遷移図を生成することができる。
【００２６】全経路探索部１０３が実際の回路動作では
起こり得ない経路を含む探索を行うのは、入力値である
遷移条件が決まらない場合の経路解析処理を行うときに
は、実際起こり得る経路が分からないので、遷移条件を
無視して、経路情報から得られるすべての経路を検索す
るためである。図４に、実際の回路動作では起こり得な
い経路を含む状態遷移図の例を示す。実際の回路動作で
起こり得る経路は、（１）開始・終了状態→状態Ａ→状
態Ｃ→状態Ｄ→状態Ｅ→開始・終了状態、（２）開始・
終了状態→状態Ｂ→状態Ｃ→開始・終了状態の２経路の
みとすると、ここに示されていない下記の経路、つま
り、（３）開始・終了状態→状態Ａ→状態Ｃ→開始・終
了状態、（４）開始・終了状態→状態Ｂ→状態Ｃ→状態
Ｄ→状態Ｅ→開始・終了状態は、実際の回路動作では起
こり得ない経路である。
起こり得ない経路を含む探索を行うのは、入力値である
遷移条件が決まらない場合の経路解析処理を行うときに
は、実際起こり得る経路が分からないので、遷移条件を
無視して、経路情報から得られるすべての経路を検索す
るためである。図４に、実際の回路動作では起こり得な
い経路を含む状態遷移図の例を示す。実際の回路動作で
起こり得る経路は、（１）開始・終了状態→状態Ａ→状
態Ｃ→状態Ｄ→状態Ｅ→開始・終了状態、（２）開始・
終了状態→状態Ｂ→状態Ｃ→開始・終了状態の２経路の
みとすると、ここに示されていない下記の経路、つま
り、（３）開始・終了状態→状態Ａ→状態Ｃ→開始・終
了状態、（４）開始・終了状態→状態Ｂ→状態Ｃ→状態
Ｄ→状態Ｅ→開始・終了状態は、実際の回路動作では起
こり得ない経路である。
【００２７】以上のように、状態遷移図で記述された制
御回路の各状態に要する処理時間をクロックサイクル数
で定義し、ある状態から次の状態への遷移条件によら
ず、各状態に要する処理時間をクロックサイクル数で規
定した値や閉ループの繰り返し回数を記述した経路解析
条件を用い、処理の開始から終了までのすべての経路探
索を行い、各経路の処理時間と最大処理時間を求める。
すべての経路の中で最大処理時間に満たない経路に対し
て、待機時間を設ける状態を挿入する。これにより、ど
の経路を通過しても処理の開始から終了までの時間が一
定になる。
御回路の各状態に要する処理時間をクロックサイクル数
で定義し、ある状態から次の状態への遷移条件によら
ず、各状態に要する処理時間をクロックサイクル数で規
定した値や閉ループの繰り返し回数を記述した経路解析
条件を用い、処理の開始から終了までのすべての経路探
索を行い、各経路の処理時間と最大処理時間を求める。
すべての経路の中で最大処理時間に満たない経路に対し
て、待機時間を設ける状態を挿入する。これにより、ど
の経路を通過しても処理の開始から終了までの時間が一
定になる。
【００２８】実施の形態２．実施の形態１の説明で用い
た状態遷移回路と異なる状態遷移回路を用いて、本発明
に係る設計回路設計装置について説明する。なお、この
装置の構成は、実施の形態１の場合と同一である。
た状態遷移回路と異なる状態遷移回路を用いて、本発明
に係る設計回路設計装置について説明する。なお、この
装置の構成は、実施の形態１の場合と同一である。
【００２９】図５に、待機時間を設定する前の状態遷移
図の例を示す。図２と同様に、状態遷移間関係解析部１
０２の結果に、経路解析条件ファイル１１２を加えたも
のである。この例では、開始状態・終了状態が共通であ
り、処理時間は、状態Ａが１クロック、状態Ｂが５クロ
ック、状態Ｃが１クロックである。また、閉ループの繰
り返し回数は、図５に示すように、「閉ループ１回の場
合」と「閉ループ２回の場合」がある。なお、「ｌｏｏ
ｐＮ」はループ回数Ｎを表し、「ｌｏｏｐ＿ｄｅｆ」は
「開始状態→ループの途中の状態→．．．．．→終了状
態（＝開始状態）」を表している。
図の例を示す。図２と同様に、状態遷移間関係解析部１
０２の結果に、経路解析条件ファイル１１２を加えたも
のである。この例では、開始状態・終了状態が共通であ
り、処理時間は、状態Ａが１クロック、状態Ｂが５クロ
ック、状態Ｃが１クロックである。また、閉ループの繰
り返し回数は、図５に示すように、「閉ループ１回の場
合」と「閉ループ２回の場合」がある。なお、「ｌｏｏ
ｐＮ」はループ回数Ｎを表し、「ｌｏｏｐ＿ｄｅｆ」は
「開始状態→ループの途中の状態→．．．．．→終了状
態（＝開始状態）」を表している。
【００３０】全経路探索部１０３の検索により開始状態
から終了状態までには、全部で２つの経路が存在するこ
とが分かる。１つの経路は、開始・終了状態→状態Ａ
（１クロック）→状態Ｂ（５クロック）→状態Ｃ（１ク
ロック）→状態Ｂ（５クロック）→開始・終了状態で、
もう１つの経路は、開始・終了状態→状態Ａ（１クロッ
ク）→状態Ｂ（５クロック）→状態Ｃ（１クロック）→
状態Ｂ（５クロック）→状態Ｃ（１クロック）→状態Ｂ
（５クロック）→開始・終了状態である。
から終了状態までには、全部で２つの経路が存在するこ
とが分かる。１つの経路は、開始・終了状態→状態Ａ
（１クロック）→状態Ｂ（５クロック）→状態Ｃ（１ク
ロック）→状態Ｂ（５クロック）→開始・終了状態で、
もう１つの経路は、開始・終了状態→状態Ａ（１クロッ
ク）→状態Ｂ（５クロック）→状態Ｃ（１クロック）→
状態Ｂ（５クロック）→状態Ｃ（１クロック）→状態Ｂ
（５クロック）→開始・終了状態である。
【００３１】経路処理時間算出部１０４の算出により前
者が１２クロックかかり、後者が１８クロックかかるこ
とが分かる。
者が１２クロックかかり、後者が１８クロックかかるこ
とが分かる。
【００３２】待機状態挿入部１０５は、最大処理時間１
２クロックと後者の処理時間の差分６クロックを求め、
後者に６クロック挿入する必要があると判断する。そし
て、閉ループを１回だけまわる条件では、状態Ｂ→開始
・終了状態のポイントに、６クロック待機する状態を挿
入し、閉ループを２回まわる条件では、そのまま状態Ｂ
→開始・終了状態へ戻るようにする。図６に、待機時間
を設定した後の状態遷移図の例を示す。
２クロックと後者の処理時間の差分６クロックを求め、
後者に６クロック挿入する必要があると判断する。そし
て、閉ループを１回だけまわる条件では、状態Ｂ→開始
・終了状態のポイントに、６クロック待機する状態を挿
入し、閉ループを２回まわる条件では、そのまま状態Ｂ
→開始・終了状態へ戻るようにする。図６に、待機時間
を設定した後の状態遷移図の例を示す。
【００３３】これにより、処理の開始から終了までの処
理時間が一定の状態遷移回路による制御回路を生成する
ことができる。
理時間が一定の状態遷移回路による制御回路を生成する
ことができる。
【００３４】実施の形態３．図７に、実施の形態３に係
る論理回路設計装置のブロック図を示す。状態遷移仕様
入力部１０１、状態遷移間関係解析部１０２、経路処理
時間算出部１０４から半導体レイアウト部１０８、状態
遷移図ＤＢ１１１、機能記述言語１１３からセル配置指
示情報１１５は、実施の形態１と同様である。
る論理回路設計装置のブロック図を示す。状態遷移仕様
入力部１０１、状態遷移間関係解析部１０２、経路処理
時間算出部１０４から半導体レイアウト部１０８、状態
遷移図ＤＢ１１１、機能記述言語１１３からセル配置指
示情報１１５は、実施の形態１と同様である。
【００３５】この構成における基本的動作について説明
する。状態遷移仕様入力部１０１及び状態遷移間関係解
析部１０２の動作、経路処理時間算出部１０４から半導
体レイアウト部１０８の動作は、実施の形態１と同様で
ある。
する。状態遷移仕様入力部１０１及び状態遷移間関係解
析部１０２の動作、経路処理時間算出部１０４から半導
体レイアウト部１０８の動作は、実施の形態１と同様で
ある。
【００３６】シミュレーション実行部６００は、状態遷
移回路に対して、入力データ系列によるシミュレーショ
ンを行う。トレース経路探索部６０１は、シミュレーシ
ョンで通過する状態の経路の探索を行う。実施の形態１
の全経路探索部１０３は、状態遷移図だけからの遷移条
件を無視した全経路探索を行うのに対して、トレース経
路探索部６０１は、状態遷移図とシミュレーションデー
タ（６１１の状態遷移回路入力データ）を用いてシミュ
レーションして、状態の遷移をトレースする手法に基づ
く経路探索を行う点で異なる。
移回路に対して、入力データ系列によるシミュレーショ
ンを行う。トレース経路探索部６０１は、シミュレーシ
ョンで通過する状態の経路の探索を行う。実施の形態１
の全経路探索部１０３は、状態遷移図だけからの遷移条
件を無視した全経路探索を行うのに対して、トレース経
路探索部６０１は、状態遷移図とシミュレーションデー
タ（６１１の状態遷移回路入力データ）を用いてシミュ
レーションして、状態の遷移をトレースする手法に基づ
く経路探索を行う点で異なる。
【００３７】上述の処理により、実施の形態１と同様
に、処理の開始から終了までの処理時間が一定の状態遷
移回路による制御回路を生成することができる。実施の
形態１の全経路探索の場合には、実際の回路動作では起
こり得ない経路も検索することがあるのに対して、本実
施の形態では、状態遷移回路に与えられる入力データ系
列によるシミュレーションに基づく経路探索を行うた
め、実際の動作に近い経路に対して処理の開始状態から
終了状態までの経路探索が行われる。これは、入力デー
タ系列がこの回路が実際に使用される環境で与えられる
入力値と非常に近くなるためである。特に、シミュレー
ションに用いる入力データ系列がこの回路を実際に使用
する環境で与えられる入力値と全く同じ場合には、実際
の動作と等しくなる。そのため、無駄な待機状態が含ま
れず、よりゲートサイズの小さな制御回路が生成でき
る。
に、処理の開始から終了までの処理時間が一定の状態遷
移回路による制御回路を生成することができる。実施の
形態１の全経路探索の場合には、実際の回路動作では起
こり得ない経路も検索することがあるのに対して、本実
施の形態では、状態遷移回路に与えられる入力データ系
列によるシミュレーションに基づく経路探索を行うた
め、実際の動作に近い経路に対して処理の開始状態から
終了状態までの経路探索が行われる。これは、入力デー
タ系列がこの回路が実際に使用される環境で与えられる
入力値と非常に近くなるためである。特に、シミュレー
ションに用いる入力データ系列がこの回路を実際に使用
する環境で与えられる入力値と全く同じ場合には、実際
の動作と等しくなる。そのため、無駄な待機状態が含ま
れず、よりゲートサイズの小さな制御回路が生成でき
る。
【００３８】以上のように、本発明は、状態遷移回路と
その周辺回路をシミュレーションする手段をもち、状態
遷移回路に与えられた入力データ系列により、遷移する
すべての経路の処理時間を累積し、処理の開始から終了
までの処理時間と最大処理時間を求め、最大処理時間に
満たない回路に対して、待機時間を設ける状態を挿入す
る。
その周辺回路をシミュレーションする手段をもち、状態
遷移回路に与えられた入力データ系列により、遷移する
すべての経路の処理時間を累積し、処理の開始から終了
までの処理時間と最大処理時間を求め、最大処理時間に
満たない回路に対して、待機時間を設ける状態を挿入す
る。
【００３９】実施の形態４．図８に、状態遷移回路間の
関係解析のフロー図を示す。親子関係のある状態遷移回
路について説明する。親子関係とは、親の状態遷移回路
のある状態の下で、子どもの状態遷移回路が処理を開始
し、その処理が終了した後に、親の状態遷移回路が次の
状態に遷移するように動作する関係のことである。
関係解析のフロー図を示す。親子関係のある状態遷移回
路について説明する。親子関係とは、親の状態遷移回路
のある状態の下で、子どもの状態遷移回路が処理を開始
し、その処理が終了した後に、親の状態遷移回路が次の
状態に遷移するように動作する関係のことである。
【００４０】まず、子どもの状態遷移回路に関して、実
施の形態１の全経路探索部１０３、経路処理時間算出部
１０４、或いは、実施の形態３のシミュレーション実行
部６００、トレース経路探索部６０１、経路処理時間算
出部１０４を用いて、子どもの状態遷移回路の処理開始
状態から終了状態までの各経路の処理時間と最大処理時
間を求める（Ｓ８００）。次に、待機状態挿入部１０５
を用いて子どもの状態遷移図に対して、総処理時間が一
定となるように待機状態を挿入する（Ｓ８０１）。
施の形態１の全経路探索部１０３、経路処理時間算出部
１０４、或いは、実施の形態３のシミュレーション実行
部６００、トレース経路探索部６０１、経路処理時間算
出部１０４を用いて、子どもの状態遷移回路の処理開始
状態から終了状態までの各経路の処理時間と最大処理時
間を求める（Ｓ８００）。次に、待機状態挿入部１０５
を用いて子どもの状態遷移図に対して、総処理時間が一
定となるように待機状態を挿入する（Ｓ８０１）。
【００４１】すべての子どもの状態遷移回路に関して、
上述の処理が完了していなければ、処理を行っていない
子どもの状態遷移回路に関して、上述の処理を行う（Ｓ
８０２）。
上述の処理が完了していなければ、処理を行っていない
子どもの状態遷移回路に関して、上述の処理を行う（Ｓ
８０２）。
【００４２】すべての子どもの状態遷移回路に関して処
理が完了したら、親の状態遷移回路に関して、同様に、
実施の形態１の全経路探索部１０３、経路処理時間算出
部１０４、或いは、実施の形態３のシミュレーション実
行部６００、トレース経路探索部６０１、経路処理時間
算出部１０４を用いて、親の状態遷移回路の処理の開始
状態から終了までの処理時間と最大処理時間を求める
（Ｓ８０３）。待機状態挿入部１０５を用いて、親の状
態遷移回路に対して、最大処理時間に満たない経路に処
理時間が一定になる待機状態を挿入する（Ｓ８０４）。
理が完了したら、親の状態遷移回路に関して、同様に、
実施の形態１の全経路探索部１０３、経路処理時間算出
部１０４、或いは、実施の形態３のシミュレーション実
行部６００、トレース経路探索部６０１、経路処理時間
算出部１０４を用いて、親の状態遷移回路の処理の開始
状態から終了までの処理時間と最大処理時間を求める
（Ｓ８０３）。待機状態挿入部１０５を用いて、親の状
態遷移回路に対して、最大処理時間に満たない経路に処
理時間が一定になる待機状態を挿入する（Ｓ８０４）。
【００４３】なお、状態遷移間関係解析部１０２に対す
る入力データ、出力データは、ともにすべての状態遷移
図（親の状態遷移図と子どもの状態遷移図）である。
る入力データ、出力データは、ともにすべての状態遷移
図（親の状態遷移図と子どもの状態遷移図）である。
【００４４】この処理により、親子関係を持った状態遷
移回路に対して、処理の開始から終了までの処理時間が
どの経路を通っても一定となる制御回路を生成すること
ができる。
移回路に対して、処理の開始から終了までの処理時間が
どの経路を通っても一定となる制御回路を生成すること
ができる。
【００４５】以上のように、本発明は、複数の状態遷移
回路間の関係を解析し、処理時間を一定にするための機
構をもち、複数の状態遷移回路が連動して動作する場合
にも対応する。
回路間の関係を解析し、処理時間を一定にするための機
構をもち、複数の状態遷移回路が連動して動作する場合
にも対応する。
【００４６】実施の形態５．図９に、状態遷移回路間の
関係解析のフロー図を示す。まず、子どもの状態遷移回
路に関して、実施の形態１の全経路探索部１０３、経路
処理時間算出部１０４、或いは、実施の形態３のシミュ
レーション実行部６００、トレース経路探索部６０１、
経路処理時間算出部１０４を用いて、子どもの状態遷移
回路の処理開始状態から終了状態までの各経路の処理時
間と最大処理時間を求める（Ｓ９００）。次に、待機状
態挿入部１０５を用いて、子どもの状態遷移図に対し
て、総処理時間が一定となるように待機状態を挿入する
（Ｓ９０１）。
関係解析のフロー図を示す。まず、子どもの状態遷移回
路に関して、実施の形態１の全経路探索部１０３、経路
処理時間算出部１０４、或いは、実施の形態３のシミュ
レーション実行部６００、トレース経路探索部６０１、
経路処理時間算出部１０４を用いて、子どもの状態遷移
回路の処理開始状態から終了状態までの各経路の処理時
間と最大処理時間を求める（Ｓ９００）。次に、待機状
態挿入部１０５を用いて、子どもの状態遷移図に対し
て、総処理時間が一定となるように待機状態を挿入する
（Ｓ９０１）。
【００４７】すべての子どもの状態遷移回路に関して、
上述の処理が完了していなければ、処理を行っていない
子どもの状態遷移回路に関して、上述の処理を行う（Ｓ
９０２）。
上述の処理が完了していなければ、処理を行っていない
子どもの状態遷移回路に関して、上述の処理を行う（Ｓ
９０２）。
【００４８】すべての子どもの状態遷移回路に関して処
理が完了したら、親の状態遷移回路に関して、同様に、
実施の形態１の全経路探索部１０３、経路処理時間算出
部１０４、或いは、実施の形態３のシミュレーション実
行部６００、トレース経路探索部６０１、経路処理時間
算出部１０４を用いて、親の状態遷移回路の処理の開始
状態から終了までの処理時間と最大処理時間を求める
（Ｓ９０３）。待機状態挿入部１０５を用いて、親の状
態遷移回路に対して、最大処理時間に満たない経路上の
子どもの状態遷移回路に対して、処理時間が一定になる
待機時間を分配する（Ｓ９０４）。
理が完了したら、親の状態遷移回路に関して、同様に、
実施の形態１の全経路探索部１０３、経路処理時間算出
部１０４、或いは、実施の形態３のシミュレーション実
行部６００、トレース経路探索部６０１、経路処理時間
算出部１０４を用いて、親の状態遷移回路の処理の開始
状態から終了までの処理時間と最大処理時間を求める
（Ｓ９０３）。待機状態挿入部１０５を用いて、親の状
態遷移回路に対して、最大処理時間に満たない経路上の
子どもの状態遷移回路に対して、処理時間が一定になる
待機時間を分配する（Ｓ９０４）。
【００４９】待機時間を分配された子どもの状態遷移図
に対して、再度、経路解析を行い（Ｓ９０５）、待機時
間を挿入する（Ｓ９０６）。待機時間を配分された子ど
もの状態遷移回路に対して、Ｓ９０５とＳ９０６の処理
が終了するまで繰り返す（Ｓ９０７）。
に対して、再度、経路解析を行い（Ｓ９０５）、待機時
間を挿入する（Ｓ９０６）。待機時間を配分された子ど
もの状態遷移回路に対して、Ｓ９０５とＳ９０６の処理
が終了するまで繰り返す（Ｓ９０７）。
【００５０】この処理により、親子関係を持った状態遷
移回路に対して、処理の開始から終了までの処理時間が
どの経路を通っても一定となる制御回路を生成すること
ができる。
移回路に対して、処理の開始から終了までの処理時間が
どの経路を通っても一定となる制御回路を生成すること
ができる。
【００５１】実施の形態６．図１０に、共有化カウンタ
の構成図を示す。１００１はカウンタ、１００２はセレ
クタである。待機時間を規定するためにカウンタを用い
てその時間を決定するが、複数の待機状態に対してそれ
ぞれ異なる時間待機する場合に、各状態毎に別々のカウ
ンタをもつのではなく、複数の待機状態の中で最大時間
待機する待機状態用のカウンタで、すべての待機状態の
時間を規定することができる。
の構成図を示す。１００１はカウンタ、１００２はセレ
クタである。待機時間を規定するためにカウンタを用い
てその時間を決定するが、複数の待機状態に対してそれ
ぞれ異なる時間待機する場合に、各状態毎に別々のカウ
ンタをもつのではなく、複数の待機状態の中で最大時間
待機する待機状態用のカウンタで、すべての待機状態の
時間を規定することができる。
【００５２】例えば、図１０のように、ダウンカウンタ
の初期値として各状態で待機する時間を設定する場合
（ダウンカウンタが０で待機終了）、待機状態によっ
て、待機時間をセレクタで選択して設定する。
の初期値として各状態で待機する時間を設定する場合
（ダウンカウンタが０で待機終了）、待機状態によっ
て、待機時間をセレクタで選択して設定する。
【００５３】このように、待機時間設定用のカウンタを
共用化することにより、回路規模を小さくできる。
共用化することにより、回路規模を小さくできる。
【００５４】以上のように、本発明は、挿入された複数
の待機時間を設ける状態を実現する回路として、カウン
タ等の回路資源を共有化した回路の機能記述を変換する
手段とその機能記述を論理合成する手段を提供する。
の待機時間を設ける状態を実現する回路として、カウン
タ等の回路資源を共有化した回路の機能記述を変換する
手段とその機能記述を論理合成する手段を提供する。
【００５５】実施の形態７．本実施の形態では、複数の
待機状態がある場合に、それを１つの状態としてまとめ
る例について説明する。図１１は、複数の待機状態を含
む状態遷移図である。この状態遷移図の複数の待機状態
を１つの待機状態にまとめたものが、図１２に示す状態
遷移図である。
待機状態がある場合に、それを１つの状態としてまとめ
る例について説明する。図１１は、複数の待機状態を含
む状態遷移図である。この状態遷移図の複数の待機状態
を１つの待機状態にまとめたものが、図１２に示す状態
遷移図である。
【００５６】このように、状態数を減らすことにより、
回路規模を小さくすることができる。
回路規模を小さくすることができる。
【００５７】実施の形態８．図１３に、ＬＳＩのレイア
ウト図を示す。一般に、状態遷移回路は、遷移条件によ
り、次の状態を決定する状態機械部１３０２と各状態の
出力値を決定する出力信号生成部１３０３からなる。従
来の論理合成では、これらは、１つのモジュールとして
生成される。本発明では、状態機械部１３０２と出力信
号生成部１３０３を別々のモジュールとして出力し、こ
れらのモジュールをＬＳＩ１３０１のどの領域（位置）
に配置するかといった配置情報を一緒に出力する。
ウト図を示す。一般に、状態遷移回路は、遷移条件によ
り、次の状態を決定する状態機械部１３０２と各状態の
出力値を決定する出力信号生成部１３０３からなる。従
来の論理合成では、これらは、１つのモジュールとして
生成される。本発明では、状態機械部１３０２と出力信
号生成部１３０３を別々のモジュールとして出力し、こ
れらのモジュールをＬＳＩ１３０１のどの領域（位置）
に配置するかといった配置情報を一緒に出力する。
【００５８】このようにして、レイアウト時に状態機械
部と出力信号生成部の回路をグループ化してセル配置で
きる。
部と出力信号生成部の回路をグループ化してセル配置で
きる。
【００５９】以上のように、本発明は、論理合成する状
態遷移回路について、その状態遷移機械部の回路（レジ
スタ等）とその出力信号生成部の回路とであることを示
す識別子を与え、その識別子を元に、半導体のレイアウ
トのセル配置時に、同一の識別子の属性もつセルを近隣
に配置する手段を提供する。特に、状態機械部内のレジ
スタをＬＳＩ内でより近くに配置することができるの
で、レイアウト時のクロックスキューなどの問題が生じ
にくい。
態遷移回路について、その状態遷移機械部の回路（レジ
スタ等）とその出力信号生成部の回路とであることを示
す識別子を与え、その識別子を元に、半導体のレイアウ
トのセル配置時に、同一の識別子の属性もつセルを近隣
に配置する手段を提供する。特に、状態機械部内のレジ
スタをＬＳＩ内でより近くに配置することができるの
で、レイアウト時のクロックスキューなどの問題が生じ
にくい。
【００６０】実施の形態９．本発明は、上述の状態遷移
図による制御回路に対する実施例に限られることなく、
いろいろな分野への応用が可能である。例えば、外部デ
バイス（外部要因）からの割り込みが発生しない単純な
装置に用いられるソフトウエアの開発装置（コンパイ
ラ）において、第１ステップとしてマイクロプロセッサ
に特化したアセンブラ言語に落とす段階において、すべ
ての命令レベルの経路解析を行い、各命令を実行するた
めのクロック数から各経路に要する処理時間を解析す
る。このとき、分岐命令の分岐条件によらず、すべての
経路を探索する。第２ステップとして、各経路に要する
時間が一定になるように、ＮＯＰ命令を挿入する。上記
の処理により、処理時間を一定とするソフトウエアを生
成するという応用もある。
図による制御回路に対する実施例に限られることなく、
いろいろな分野への応用が可能である。例えば、外部デ
バイス（外部要因）からの割り込みが発生しない単純な
装置に用いられるソフトウエアの開発装置（コンパイ
ラ）において、第１ステップとしてマイクロプロセッサ
に特化したアセンブラ言語に落とす段階において、すべ
ての命令レベルの経路解析を行い、各命令を実行するた
めのクロック数から各経路に要する処理時間を解析す
る。このとき、分岐命令の分岐条件によらず、すべての
経路を探索する。第２ステップとして、各経路に要する
時間が一定になるように、ＮＯＰ命令を挿入する。上記
の処理により、処理時間を一定とするソフトウエアを生
成するという応用もある。
【００６１】
【発明の効果】以上説明したように、本発明は、総処理
時間が一定になることが要求される分野の回路設計にお
いて、もともと設計者が作成した状態遷移図に待機状態
を挿入することにより、総処理時間が一定となる制御回
路を生成することができるようになる。従来このような
回路は、設計者自身がすべての考えられる経路に要する
時間を計算して作成する必要があったが、これを自動的
に行うことができるようになった。このため、設計者の
ミスによる動作不良を防ぐことができる。例えば、情報
セキュリティ関係のハードウエア関連の分野では、演算
内容によって処理時間が異なると、それをもとに、解読
される可能性があり、どのような演算を行っても、その
処理時間を一定にすることが求められている。従って、
それを制御するハードウエア（状態遷移回路）は、処理
を一定にするように設計する必要がある。特に、このよ
うな分野の回路設計において、本発明は有効である。
時間が一定になることが要求される分野の回路設計にお
いて、もともと設計者が作成した状態遷移図に待機状態
を挿入することにより、総処理時間が一定となる制御回
路を生成することができるようになる。従来このような
回路は、設計者自身がすべての考えられる経路に要する
時間を計算して作成する必要があったが、これを自動的
に行うことができるようになった。このため、設計者の
ミスによる動作不良を防ぐことができる。例えば、情報
セキュリティ関係のハードウエア関連の分野では、演算
内容によって処理時間が異なると、それをもとに、解読
される可能性があり、どのような演算を行っても、その
処理時間を一定にすることが求められている。従って、
それを制御するハードウエア（状態遷移回路）は、処理
を一定にするように設計する必要がある。特に、このよ
うな分野の回路設計において、本発明は有効である。
【００６２】また、本発明は、このように生成した状態
遷移図から機能記述を生成し、論理合成でネットリスト
に変換することができ、この処理の中で、状態遷移図か
ら一旦、機能記述に変換する段階では、追加挿入した回
路の共有化が行なうことができ、論理合成する回路のゲ
ートサイズ（面積）を小さくすることができる。
遷移図から機能記述を生成し、論理合成でネットリスト
に変換することができ、この処理の中で、状態遷移図か
ら一旦、機能記述に変換する段階では、追加挿入した回
路の共有化が行なうことができ、論理合成する回路のゲ
ートサイズ（面積）を小さくすることができる。
【００６３】更に、レイアウトのセル配置の際に、状態
遷移機械部と出力信号部をグループ化して配置すること
ができるので、制御回路内のタイミング上のクロックス
キューによる問題などが発生を抑えることができる。
遷移機械部と出力信号部をグループ化して配置すること
ができるので、制御回路内のタイミング上のクロックス
キューによる問題などが発生を抑えることができる。
【図１】 実施の形態１に係る論理回路設計装置のブロ
ック図である。
ック図である。
【図２】 実施の形態１に係る待機時間を設定する前の
状態遷移図である。
状態遷移図である。
【図３】 実施の形態１に係る待機時間を設定した後の
状態遷移図である。
状態遷移図である。
【図４】 実際の回路動作では起こり得ない経路を含む
状態遷移図である。
状態遷移図である。
【図５】 実施の形態２に係る待機時間を設定する前の
状態遷移図である。
状態遷移図である。
【図６】 実施の形態２に係る待機時間を設定した後の
状態遷移図である。
状態遷移図である。
【図７】 実施の形態３に係る論理回路設計装置のブロ
ック図である。
ック図である。
【図８】 実施の形態４に係る状態遷移回路間の関係解
析のフロー図である。
析のフロー図である。
【図９】 実施の形態５に係る状態遷移回路間の関係解
析のフロー図である。
析のフロー図である。
【図１０】 共有化カウンタの構成図である。
【図１１】 複数の待機状態を含む状態遷移図である。
【図１２】 複数の待機状態を１つの待機状態にまとめ
た状態遷移図である。
た状態遷移図である。
【図１３】 ＬＳＩのレイアウト図である。
【図１４】 従来技術に係る遅延時間調整方法のフロー
チャート図である。
チャート図である。
【図１５】 従来技術に係る遅延時間調整装置のブロッ
ク図である。
ク図である。
１０１ 状態遷移仕様入力部、１０２ 状態遷移間関係
解析部、１０３ 全経路探索部、１０４ 経路処理時間
算出部、１０５ 待機状態挿入部、１０６ 機能記述言
語生成部、１０７ 回路合成部、１０８ 半導体レイア
ウト部、１１１状態遷移図ＤＢ、１１２ 経路解析条件
ファイル、１１３ 機能記述言語、１１４ ネットリス
ト、１１５ セル配置指示情報、６００ シミュレーシ
ョン実行部、６０１ トレース経路探索部、６１１ 入
力データ系列、１３０１ ＬＳＩ、１３０２ 状態機械
部、１３０３ 出力信号生成部。
解析部、１０３ 全経路探索部、１０４ 経路処理時間
算出部、１０５ 待機状態挿入部、１０６ 機能記述言
語生成部、１０７ 回路合成部、１０８ 半導体レイア
ウト部、１１１状態遷移図ＤＢ、１１２ 経路解析条件
ファイル、１１３ 機能記述言語、１１４ ネットリス
ト、１１５ セル配置指示情報、６００ シミュレーシ
ョン実行部、６０１ トレース経路探索部、６１１ 入
力データ系列、１３０１ ＬＳＩ、１３０２ 状態機械
部、１３０３ 出力信号生成部。
Claims (10)
- 【請求項１】 開始状態から終了状態までの経路を複数
含む状態遷移情報を調整する状態遷移情報調整装置であ
って、以下の要素を有する状態遷移情報調整装置 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索部、（２）探索された複
数の経路について、それぞれの経路処理時間を算出する
経路処理時間算出部、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入部。 - 【請求項２】 経路探索部は、すべての経路を探索する
ことを特徴とする請求項１記載の状態遷移情報調整装
置。 - 【請求項３】 経路探索部は、以下の要素を有すること
を特徴とする請求項１記載の状態遷移情報調整装置 （ａ）シミュレーションに用いるシミュレーション入力
データを記憶するシミュレーション入力データ記憶部、
（ｂ）記憶されているシミュレーション入力データに基
づいてシミュレーションを実行するシミュレーション実
行部、（ｃ）シミュレーションで通過する経路をトレー
スし、経路を探索するトレース経路探索部。 - 【請求項４】 状態遷移情報調整装置は、親の状態遷移
の特定状態で、子の状態遷移が開始し、子の状態遷移が
終了した後に、親の状態遷移がその特定状態から進行す
る親子関係を解析する状態遷移間関係解析部を有し、 経路探索部は、すべての子の状態遷移について、経路を
探索し、 経路処理時間算出部は、すべての子の状態遷移につい
て、経路処理時間を算出し、 待機状態挿入部は、すべての子の状態遷移について、待
機状態を挿入し、 経路探索部は、親の状態遷移について、経路を探索し、 経路処理時間算出部は、親の状態遷移について、経路処
理時間を算出し、 待機状態挿入部は、親の状態遷移について、待機状態を
挿入することを特徴とする請求項１記載の状態遷移情報
調整装置。 - 【請求項５】 待機状態挿入部は、親の状態遷移につい
て、待機状態を挿入する場合に、親の状態遷移の経路上
にある子の状態遷移の状態遷移情報の経路中に、算出し
た待機時間に相当する待機状態を挿入することを特徴と
する請求項４記載の状態遷移情報調整装置。 - 【請求項６】 以下の要素を有する回路設計装置 （Ａ）状態遷移情報を入力する状態遷移情報入力部、
（Ｂ）入力した状態遷移情報を調整する請求項１記載の
状態遷移情報調整装置、（Ｃ）状態遷移情報調整装置に
より調整された状態遷移情報から機能記述言語を生成す
る機能記述言語生成部、（Ｄ）生成された機能記述言語
から論理回路を合成する論理回路合成部。 - 【請求項７】 論理回路合成部は、待機状態を設定する
複数のカウンタとして共用される共用カウンタを用い
て、論理回路を合成することを特徴とする請求項６記載
の回路設計装置。 - 【請求項８】 待機状態挿入部は、状態遷移情報の経路
中に待機状態を挿入する場合に、他の経路中に挿入され
た待機状態を共用することを特徴とする請求項１記載の
状態遷移情報調整装置。 - 【請求項９】 回路設計装置は、更に、合成された論理
回路を半導体にレイアウトする半導体レイアウト部を有
し、 論理回路合成部は、状態機械部回路と出力信号生成部回
路とを有する状態遷移回路を含む論理回路を合成する場
合に、同一の状態遷移回路を構成する状態機械部回路と
出力信号生成部回路とをグループ化するグループ化情報
を生成し、 半導体レイアウト部は、生成されたグループ化情報に基
づいて、同一の状態遷移回路を構成する状態機械部回路
と出力信号生成部回路とを近隣にレイアウトすることを
特徴とする請求項６記載の回路設計装置。 - 【請求項１０】 開始状態から終了状態までの経路を複
数含む状態遷移情報を調整する状態遷移情報調整処理で
あって、以下の要素を有する状態遷移情報調整処理をコ
ンピュータに実行させるためのプログラムを記録したコ
ンピュータ読み取り可能な記録媒体 （１）状態遷移情報から、開始状態から終了状態までの
複数の経路を探索する経路探索処理、（２）探索された
各経路について、それぞれの経路処理時間を算出する経
路処理時間算出処理、（３）算出された経路処理時間の
うちの最大時間を求め、求めた最大時間以上の統一経路
処理時間を設定し、各経路について、統一経路処理時間
から経路処理時間を差し引いた待機時間を算出し、状態
遷移情報の経路中に、算出した待機時間に相当する待機
状態を挿入する待機状態挿入処理。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11113916A JP2000305967A (ja) | 1999-04-21 | 1999-04-21 | 状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11113916A JP2000305967A (ja) | 1999-04-21 | 1999-04-21 | 状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000305967A true JP2000305967A (ja) | 2000-11-02 |
Family
ID=14624413
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11113916A Withdrawn JP2000305967A (ja) | 1999-04-21 | 1999-04-21 | 状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2000305967A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7447617B2 (en) | 2004-02-25 | 2008-11-04 | Fujitsu Limited | Data processing device designing method, data processing device designing apparatus, program and computer readable information recording medium |
| JP2012073759A (ja) * | 2010-09-28 | 2012-04-12 | Toshiba Corp | 設計記述書換装置およびその方法 |
-
1999
- 1999-04-21 JP JP11113916A patent/JP2000305967A/ja not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7447617B2 (en) | 2004-02-25 | 2008-11-04 | Fujitsu Limited | Data processing device designing method, data processing device designing apparatus, program and computer readable information recording medium |
| JP2012073759A (ja) * | 2010-09-28 | 2012-04-12 | Toshiba Corp | 設計記述書換装置およびその方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5764951A (en) | Methods for automatically pipelining loops | |
| US8719742B2 (en) | Conversion of circuit description to an abstract model of the circuit | |
| Gajski et al. | Specification and design of embedded hardware-software systems | |
| US5751596A (en) | Automated system and method for identifying critical timing paths in integrated circuit layouts for use with automated circuit layout system | |
| US8775988B2 (en) | Decentralized dynamically scheduled parallel static timing analysis | |
| US6505339B1 (en) | Behavioral synthesis links to logic synthesis | |
| US7917882B2 (en) | Automated digital circuit design tool that reduces or eliminates adverse timing constraints due to an inherent clock signal skew, and applications thereof | |
| JP3803561B2 (ja) | 論理回路設計方法 | |
| JP2006048525A (ja) | シミュレーション方法 | |
| US9047434B2 (en) | Clustering for processing of circuit design data | |
| Gibiluka et al. | A bundled-data asynchronous circuit synthesis flow using a commercial EDA framework | |
| US7325209B2 (en) | Using patterns for high-level modeling and specification of properties for hardware systems | |
| Raudvere et al. | Application and verification of local nonsemantic-preserving transformations in system design | |
| Wallace et al. | ATV: An abstract timing verifier | |
| JPH113367A (ja) | デジタルシステムのインプリメント可能な記述を生成する設計環境および方法 | |
| Potkonjak et al. | Considering testability at behavioral level: use of transformations for partial scan cost minimization under timing and area constraints | |
| US7111274B1 (en) | Scheduling hardware generated by high level language compilation to preserve functionality of source code design implementations | |
| Coelho Jr et al. | Dynamic scheduling and synchronization synthesis of concurrent digital systems under system-level constraints | |
| Bergamaschi et al. | A system for production use of high-level synthesis | |
| US6532584B1 (en) | Circuit synthesis method | |
| JP2000305967A (ja) | 状態遷移情報調整装置及び回路設計装置及びプログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JP5447547B2 (ja) | マクロ遅延解析装置、マクロ境界パスの遅延解析方法、マクロ境界パスの遅延解析プログラム | |
| Bergamaschi et al. | Observable time windows: Verifying high-level synthesis results | |
| Chang et al. | An optimal clock period selection method based on slack minimization criteria | |
| US8176451B2 (en) | Behavioral synthesis apparatus, behavioral synthesis method, and computer readable recording medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20051011 |
|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20060704 |