(57)【要約】【課題】  複数のクロックに基づいて動作する回路を有するハードウェアに対して、高速なシミュレーションを可能にする。【解決手段】  クロックに基づいて動作するレジスタと組み合わせ回路を基本回路として複数個有するＨＤＬデータ内に存在する複数のクロックの属性である、周期または周波数、位相、およびエッジを決定するステップと、前記決定された属性に基づいて、前記複数のクロックの立ち上がるまたは立ち下がる順番を決定するステップと、決定された順番に基づいて前記複数のクロックに対応するデータフローを並べるステップと、を備えている。【選択図】  図１
2005071028.tif 000002
【特許請求の範囲】
【請求項１】
クロックに基づいて動作するレジスタと組み合わせ回路を基本回路として複数個有するＨＤＬデータ内に存在する複数のクロックの属性である、周期または周波数、位相、およびエッジを決定するステップと、
前記決定された属性に基づいて、前記複数のクロックの立ち上がるまたは立ち下がる順番を決定するステップと、
決定された順番に基づいて前記複数のクロックに対応するデータフローを並べるステップと、
を備えたことを特徴とするデータフロースケジューリング方法。
【請求項２】
前記複数のクロックの立ち上がるまたは立ち下がる順番を決定するステップは、
前記ＨＤＬデータ内に存在する複数のクロックから、最大周期を有するクロックを一つ選択するステップと、
パラメータの初期値を、前記最大周期を有する前記クロックの時間に設定するステップと、
前記パラメータの値となる時間にエッジを有するクロックが前記ＨＤＬデータ内に存在する場合は前記クロックを順序リストに挿入するとともに前記パラメータの値をインクリメントし、存在しない場合は前記パラメータの値をインクリメントする第１ステップと、
前記パラメータの値が、前記最大周期を有する前記クロックの時間と前記前記最大周期を有する前記クロックの周期との和に到達したか否かの判定を行い、到達しない場合に前記第１ステップに戻るステップと、
を備えたことを特徴とする請求項１記載のデータフロースケジューリング方法。  
【請求項３】
前記決定された順番に基づいて前記複数のクロックに対応するデータフローを並べるステップは、
立ち上がるまたは立ち下がる順番が同時のクロックが存在する否かの判定を行うステップと、
順番が同時のクロックが存在するときに、新たなデータフローを生成するか否かの判定を行うステップと、
新たなデータフローを生成する場合には同時であるクロックを同一視してデータフローを新たに生成するステップと、
新たなデータフローを生成しない場合には既存の複数のデータフローを併合するステップと、
決定された順番に従って、データフローを並べるステップと、
を備えたことを特徴とする請求項１または２記載のデータフロースケジューリング方法。
【請求項４】
前記複数のデータフローを併合するステップは、
併合後のデータフローの初期状態を空に設定するステップと、
併合されるべき複数のデータフローから一つのレジスタを選択する第１ステップと、
選択されたレジスタが前記併合後のデータフロー内に存在しているか否かの判定を行い、存在している場合は前記第１ステップに戻り、存在していない場合は前記併合後のデータフローに前記選択したレジスタを挿入する第２ステップと、
前記複数のデータフロー内の全てのレジスタが選択されまで前記第１ステップ及び第２ステップを繰り返し、その後に前記併合後のデータフロー内のレジスタの並べ替えを行うステップと、
併合されるべき複数のデータフローから一つの組み合わせ回路を選択する第３ステップと、
選択された組み合わせ回路が前記併合後のデータフロー内に存在しているか否かの判定を行い、存在している場合は前記第３ステップに戻り、存在していない場合は前記併合後のデータフローに前記選択した組み合わせ回路を挿入する第４ステップと、
前記複数のデータフロー内の全ての組み合わせ回路が選択されまで前記第３ステップ及び第４ステップを繰り返し、その後に前記併合後のデータフロー内の組み合わせ回路の並べ替えを行うステップと、
を備えたことを特徴とする請求項３記載のデータフロースケジューリング方法。
【請求項５】
再スケジューリング用データフローの初期状態を空に設定するステップと、
スケジューリング結果からレジスタを見つけるステップと、
前記見つけたレジスタが前記再スケジューリング用データフローに存在しているか否かの判定を行い、存在している場合に前記レジスタを見つけるステップに戻り、存在していない場合は前記見つけたレジスタを前記再スケジューリング用データフローに挿入するステップと、
前記スケジューリング結果から全てのレジスタを探索したか否かの判定を行い、探索していない場合は前記レジスタを見つけるステップに戻り、探索した場合は前記再スケジューリング用データフロー内のレジスタを並べ替えるステップと、
前記スケジューリング結果から組み合わせ回路を見つけるステップと、
前記見つけた組み合わせ回路が前記再スケジューリング用データフローに存在しているか否かの判定を行い、存在している場合に前記組み合わせ回路を見つけるステップに戻り、存在していない場合は前記見つけた組み合わせ回路を前記再スケジューリング用データフローに挿入するステップと、
前記スケジューリング結果から全ての組み合わせ回路を探索したか否かの判定を行い、探索していない場合は前記組み合わせ回路を見つけるステップに戻り、探索した場合は前記再スケジューリング用データフロー内の組み合わせ回路を並べ替えるステップと、
を備えたことを特徴とするデータフロースケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数クロックに対するデータフロースケジューリング方法に関する。
【背景技術】
【０００２】
クロックに基づいて並列動作するハードウェアの動作を逐次処理する計算機言語（プログラム言語）に書き換えて、シミュレーションすることが行われている。例えば、ＨＤＬソースを入力とし、ハードウェアを構成する回路の実行順序を示す文の集合である「データフロー」を、クロックを起点として生成し、他のコードに変換する技術が本出願人によって既に提案されている（特願２００２−１７８９４５参照）。しかし、この技術は、ハードウェアが単一のクロックに基づいて動作することが前提であり、複数のクロックが存在する場合については言及されていない。
【０００３】
しかし、ハードウェアを構成する回路が複数のクロックに基づいて動作することは実際にはよくある。そして、複数のクロックに基づいて動作する回路を、実行時間に基づいてスケジューリングする技術が知られている（例えば、特許文献１参照）。
【特許文献１】米国特許第５，８６２，３６１号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載の技術は、実行時間に基づいてスケジューリングを行うため、異なる時間にスケジューリングされた演算器同士を利用した最適化を行うことができない。このため、出力となるプログラムには、冗長な演算を含んでいる可能性があり、高速なシミュレーションを行うことができない場合がある。
【０００５】
本発明は上記事情を考慮してなされたものであって、複数のクロックに基づいて動作する回路を有するハードウェアに対して、高速なシミュレーションを可能にするデータフロースケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の第１の態様によるデータフロースケジューリング方法は、クロックに基づいて動作するレジスタと組み合わせ回路を基本回路として複数個有するＨＤＬデータ内に存在する複数のクロックの属性である、周期または周波数、位相、およびエッジを決定するステップと、前記決定された属性に基づいて、前記複数のクロックの立ち上がるまたは立ち下がる順番を決定するステップと、決定された順番に基づいて前記複数のクロックに対応するデータフローを並べるステップと、  を備えたことを特徴とする。
【０００７】
また、本発明の第２の態様によるデータフロースケジューリング方法は、再スケジューリング用データフローの初期状態を空に設定するステップと、スケジューリング結果からレジスタを見つけるステップと、前記見つけたレジスタが前記再スケジューリング用データフローに存在しているか否かの判定を行い、存在している場合に前記レジスタを見つけるステップに戻り、存在していない場合は前記見つけたレジスタを前記再スケジューリング用データフローに挿入するステップと、前記スケジューリング結果から全てのレジスタを探索したか否かの判定を行い、探索していない場合は前記レジスタを見つけるステップに戻り、探索した場合は前記再スケジューリング用データフロー内のレジスタを並べ替えるステップと、前記スケジューリング結果から組み合わせ回路を見つけるステップと、前記見つけた組み合わせ回路が前記再スケジューリング用データフローに存在しているか否かの判定を行い、存在している場合に前記組み合わせ回路を見つけるステップに戻り、存在していない場合は前記見つけた組み合わせ回路を前記再スケジューリング用データフローに挿入するステップと、前記スケジューリング結果から全ての組み合わせ回路を探索したか否かの判定を行い、探索していない場合は前記組み合わせ回路を見つけるステップに戻り、探索した場合は前記再スケジューリング用データフロー内の組み合わせ回路を並べ替えるステップと、を備えたことを特徴とする。
【発明の効果】
【０００８】
本発明は、複数のクロックに基づいて動作する回路を有するハードウェアに対して、高速なシミュレーションを可能にする。
【発明を実施するための最良の形態】
【０００９】
本発明は、ＨＤＬソースの構成要素解析手段、データフロー解析手段、制御構造再構築手段、データフロー再構築手段、制御構造とデータフローの併合手段、目的コード生成手段及び冗長な文の削除手段として機能するコンピュータに対して、処理対象となるＨＤＬソースを入力することにより、コンピュータの各手段が入力されたＨＤＬソースを分析、演算、処理することにより実行される。
【００１０】
本発明の実施形態を説明する前に、本発明による「データフローデータフロースケジューリング方法
」の概要について説明する。
【００１１】
基本的なＨＤＬは、制御部Ａとデータパス部Ｂからなる。制御部Ａはデータパス部Ｂを制御し、データパス部Ｂは演算を行う回路である。例えば図４に示すように構成される。この例で、矢印は信号の流れを表している。
【００１２】
制御部Ａは、状態レジスタＡ１と、組み合わせ回路/ラッチからなる。また制御部Ａの組み合わせ回路/ラッチは、現在の状態や入力により制御信号を出力する制御信号出力部Ａ２と、次の状態を決定する次状態決定部Ａ３などからなる。データパス部Ｂは制御部Ａからの出力に従い動作する。具体的には、制御信号出力部Ａ２より出力される制御信号を入力とするレジスタＢ１が制御信号に従った動作を行い、データパス部Ｂの組み合わせ回路／ラッチＢ２を動作させる。
【００１３】
このような基本的な回路の実行順序を示す文の集合である「データフロー」は、図３に示すように、レジスタと、組み合わせ回路／ラッチとからなっている。例えば、図３（ａ）に示すように、データフローｄ１は、クロックclock1の時刻ｔ０での立ち上がりに基づいて動作するレジスタｒ１と、このレジスタｒ１の出力を受ける組み合わせ回路／ラッチｆ１とからなる。また、図３（ｂ）に示すように、データフローｄ２は、クロックclock2の時刻ｔ０の立ち上がりに基づいて動作するレジスタｒ２と、このレジスタｒ２の出力を受ける組み合わせ回路／ラッチｆ２とからなり、また、データフローｄ２は、クロックclock2の時刻ｔ３（＞ｔ０）のクロックの立ち上がりに基づいて動作するレジスタｒ２と、このレジスタｒ２の出力を受ける組み合わせ回路／ラッチｆ２とからなっている。
【００１４】
本発明のデータフロースケジューリング方法は、
１）複数のクロックの属性、すなわち周期（または周波数）、位相、エッジを決定する。
【００１５】
２）複数のクロックの決定された属性に従って、複数のクロックの立ち上がる（立ち下がる）順番を決定する。
【００１６】
３）決定された順番に従って、クロックに対応するデータフローを並べる。
【００１７】
なお、複数のクロックの立ち上がる（立ち下がる）順番が同時であった場合には、
ａ１）複数のデータフローを併合するか、または
ａ２）複数のクロックを同一視して、データフローを生成する
のいずれかの工程を行う。
【００１８】
例えば、図３（ａ）、（ｂ）に示すデータフローｄ１、ｄ２を、本発明によってスケジューリングする場合は、例えば、図２（ａ）に示すように、まず、データフローｄ１とデータフローｄ２を併合して新たなデータフローｄ３を作成し、その後、図２（ｂ）に示すように、データフローｄ３とデータフローｄ２を並べることによって行うことになる。
【００１９】
なお、本明細書においては、「周期（または周波数）」とは、図５（ａ）に示すように、クロックの立ち上がり（立ち下がり）から次のクロックの立ち上がり（立ち下がり）までの時間を表し、周波数は周期の逆数を表す。また、「位相」は、図５（ｂ）に示すように、起点となるクロックの立ち上がり（立ち下がり）時間からあるクロックの立ち上がり（立ち下がり）時間までのずれを表す。また、「エッジ」とは、図５（ａ）、（ｂ）に示すように、レジスタを起動させるクロックのタイミングが、クロックの立ち上がりなのか、立ち下がりなのか、または両方なのかを表すものである。
【００２０】
なお、ＨＤＬデータから、クロックの立ち上がり、立ち下がりに従って起動するレジスタを見いだすことは可能となる（図５（ｃ）参照）。例えば、Verilog-ＨＤＬでは、次のようになる。
【００２１】
／／例１）  clkのエッジ＝立ち上がり
always@(posedge clk)
／／例２）  clkのエッジ＝立ち下がり
always@(negedge clk)
／／例３）  clkのエッジ＝立ち上がりと立ち下がり
always@(clk)
・・・  
以下、本発明の実施形態を、図面を参照して具体的に説明する。
【００２２】
（第１実施形態）
本発明の第１実施形態によるデータフロースケジューリング方法の処理手順の概要を図１に示す。この第１実施形態によるデータフロースケジューリング方法は、まず、ユーザから、もしくは何らから抽出された情報によって、複数のクロックの属性、すなわち、複数のクロックの周期（または周波数）、位相、エッジを決定する（図１のステップＳ１参照）。
【００２３】
続いて、決定された属性に基づいて、図１のステップＳ２に示すように、複数のクロックの立ち上がる（立ち下がる）順番を決定する。このステップＳ２によって順番が決定されたクロックの例を図６（ａ）、（ｂ）、（ｃ）に示す。図６（ａ）に示すクロックＡが１番で、図６（ｂ）に示すクロックＢが２番で、図６（ｃ）に示すクロックＣが３番である。複数のクロックの立ち上がる（立ち下がる）順番を決定する具体的なステップを、図７を参照して説明する。まず、図７のステップＳ１１に示すように、順番リストの初期状態を空に設定する。
【００２４】
次に、ＨＤＬデータ内に存在するＮ（≧１）個のクロックＣＬＫ０〜ＣＬＫＮ−１から、最大周期を有するクロックを１つ選択し、ＣＬＫｍａｘ−ｃｙｃｌｅとする。クロックＣＬＫｍａｘ−ｃｙｃｌｅのエッジ時間をＴＩＭＥ、周期をＭＡＸ_ＣＹＣＬＥとする。クロックＣＬＫｍａｘ−ｃｙｃｌｅは、図７のステップＳ１２〜ステップＳ１６によって得られる。すなわち、ステップＳ１２において、最大周期ＭＡＸ_ＣＹＣＬＥの値を０とし、ステップＳ１３において、ＨＤＬデータ内の全クロック（Ｎ個のクロック）から一つのクロックを選択する。その後、ステップＳ１４において、選択したクロックの周期がＭＡＸ_ＣＹＣＬＥの値より大きいか否かの判定を行う。大きい場合は、ステップＳ１５に示すように、選択したクロックをＣＬＫｍａｘ−ｃｙｃｌｅ、エッジの時間をＴＩＭＥ、周期をＭＡＸ_ＣＹＣＬＥにし、ステップＳ１６に進む。ステップＳ１４において、大きくない場合は、ステップＳ１６に進む。ステップＳ１６においては、全てのクロックを選択したか否かの判定が行われ、全てのクロックを選択していない場合には、ステップＳ１３に戻り、上述のステップを繰り返す。
【００２５】
ステップＳ１６において、全てのクロックを選択した場合には、図８に示すステップＳ１７に進み、時間ｔｉｍｅの値をＴＩＭＥとする。その後、ステップＳ１８に進み、ＨＤＬデータ内の全クロックから一つのクロックを選択する。そして、ステップＳ１９において、選択されたクロックが時間ｔｉｍｅにエッジを有しているか否かの判定が行われる。選択されたクロックが時間ｔｉｍｅにエッジを有していない場合は、ステップＳ１８に戻り上述のことを繰り返す。選択されたクロックが時間ｔｉｍｅにエッジを有している場合は、ステップＳ２０に進み、選択されたクロックを順番リストに挿入する。その後、ステップ２１に進み、現在のｔｉｍｅにおいて、全てのクロックが選択されたか否かの判定が行われる。全てのクロックが選択されていない場合には、ステップＳ１８に戻り、上述のことを繰り返す。全てのクロックが選択された場合には、ステップＳ２２に進み、ｔｉｍｅをインクリメントする。その後、ステップＳ２３に進み、ｔｉｍｅの値がＴＩＭＥ＋ＭＡＸ_ＣＹＣＬＥの値を超えているか否かの判定が行われる。ｔｉｍｅの値がＴＩＭＥ＋ＭＡＸ_ＣＹＣＬＥの値以上でない場合には、ステップＳ１８に戻り、上述のことを繰り返す。ｔｉｍｅの値がＴＩＭＥ＋ＭＡＸ_ＣＹＣＬＥの値以上の場合には終了する。
【００２６】
このようにして、複数のクロックの立ち上がる（立ち下がる）順番が決定された後は、決定された順番に従って、複数のクロックに対応するデータフローを並べる。このデータフローを並べるステップを以下に説明する。
【００２７】
再び図１に戻り、ステップＳ３に進む。ステップＳ３において、立ち上がる（立ち下がる）順番が同時のクロックが存在するか否かの判定が行われる。立ち上がる（立ち下がる）順番が同時のクロックが存在しない場合にはステップＳ７に進み、決定された順番に従って、それぞれのクロックに対応するデータフローを並べる。例えば、図９に示すように、立ち上がる順番がクロックＡ、クロックＢ、クロックＣであれば、まず、クロックＡの立ち上がりに同期するレジスタからのデータフロー、クロックＢの立ち上がりに同期するレジスタからのデータフロー、クロックＣの立ち上がりに同期するレジスタからのデータフローを取りだし、
クロックＡの立ち上がりに同期するレジスタからのデータフロー、クロックＢの立ち上がりに同期するレジスタからのデータフロー、クロックＣの立ち上がりに同期するレジスタからのデータフローの順番に並べる。なお、図９においては、データフローの中では、左から右へ実行文が並べられているものとする。
【００２８】
ステップＳ３において、立ち上がる（立ち下がる）順番が同時のクロックが存在する場合は、ステップＳ４に進み、新たなデータフローを生成するか否かの判定が行われる。ステップＳ４において、新たなデータフローを生成しない場合は、ステップＳ５に進み、既存の複数のデータフローを併合し、その後ステップＳ７に進み、決定された順番に従って、複数のクロックに対応するデータフローを並べる。ステップＳ４において、新たなデータフローを生成する場合は、ステップＳ６に進み、同時であるクロックを同一視してデータフローを新たに生成し、その後ステップＳ７に進み、決定された順番に従って、複数のクロックに対応するデータフローを並べる。
【００２９】
なお、複数のクロックが同時に立ち上がる例を図１０に示す。この図１０に示す例は分周クロックの場合を示している。例えば、クロックＡの立ち上がり時には、クロックＡの分周クロックであるクロックＢおよびクロックＣも同時に立ち上がり、クロックＢの立ち上がり時には、クロックＢの分周クロックであるクロックＣも同時に立ち上がる。このように、複数のクロックの立ち上がり（立ち下がり）が同時である場合は、対応するデータフロー間に依存関係が生じてしまう。そこで、本発明では、この依存関係を考慮したデータフローを生成するようにしたものである。
【００３０】
次に、図１のステップＳ５に示す複数のデータフローを併合するステップの具体例を図１１および図１２を参照して説明する。図１１は、複数のデータフローの併合のイメージを示す図であり、図１２は、複数のデータフローの併合のステップを示すフローチャートである。複数のデータフローの併合の概要は、図１１に示すように、クロックＢからクロックＢの立ち上がりに同期するレジスタからのデータフローを取りだすとともに、クロックＣからクロックＣの立ち上がりに同期するレジスタからのデータフローを取りだし、クロックＢとＣの立ち上がりに同期するレジスタからのデータフローを作成する。
【００３１】
詳細には、図１２に示すフローチャートに従って行う。まず、図１２のステップＳ３０に示すように、併合するＮ（Ｎ≧１）個のデータフローＤＡＴＡＦＬＯＷ０〜ＤＡＴＡＦＬＯＷＮ−１から、１つのレジスタを選択する。この選択したレジスタが併合後のデータフローとなるＤＡＴＡＦＬＯＷｎｅｗに存在するか否かをステップＳ３１において判定する。存在しない場合は、ステップＳ３２に進み、選択したレジスタをデータフローＤＡＴＡＦＬＯＷｎｅｗに挿入する。なお、併合後のデータフローとなるＤＡＴＡＦＬＯＷｎｅｗは、初期状態では空である。ステップＳ３１において、存在する場合は、ステップＳ３０に戻り、上述のことを繰り返す。
【００３２】
その後、ステップＳ３３に進み、Ｎ個のデータフローＤＡＴＡＦＬＯＷ０〜ＤＡＴＡＦＬＯＷＮ−１内の全てのレジスタを選択したか否かの判定を行う。全てのレジスタが選択されていない場合には、ステップＳ３０に戻り、上述のことを繰り返す。全てのレジスタが選択された場合にはステップＳ３４に進み、データフローＤＡＴＡＦＬＯＷｎｅｗ内のレジスタの並べ替えを行う。続いて、ステップＳ３５に進み、Ｎ個のデータフローＤＡＴＡＦＬＯＷ０〜ＤＡＴＡＦＬＯＷＮ−１から一つの組み合わせ回路／ラッチを選択する。
【００３３】
その後、ステップＳ３６に進み、選択された組み合わせ回路／ラッチがデータフローＤＡＴＡＦＬＯＷｎｅｗ内に存在するか否かの判定を行う。ステップＳ３６において、選択された組み合わせ回路／ラッチがデータフローＤＡＴＡＦＬＯＷｎｅｗ内に存在する場合は、ステップＳ３５に戻り、上述のことを繰り返す。選択された組み合わせ回路／ラッチがデータフローＤＡＴＡＦＬＯＷｎｅｗ内に存在しない場合は、ステップＳ３７に進み、データフローＤＡＴＡＦＬＯＷｎｅｗ内に選択された組み合わせ回路／ラッチを挿入する。
【００３４】
その後、ステップＳ３８に進み、Ｎ個のデータフローＤＡＴＡＦＬＯＷ０〜ＤＡＴＡＦＬＯＷＮ−１内の全ての組み合わせ回路／ラッチを選択したか否かの判定を行う。全ての組み合わせ回路／ラッチが選択されていない場合は、ステップＳ３５に戻り、上述のことを繰り返す。全ての組み合わせ回路／ラッチが選択されている場合は、ステップＳ３９に進み、データフローＤＡＴＡＦＬＯＷｎｅｗ内の組み合わせ回路／ラッチの並べ替えを行う。
【００３５】
以上述べたように、データフローを併合することが可能となる。このデータフローには冗長な演算が含まれていない。なお、図１２に示すステップＳ３４およびステップＳ３９における並べ替えを行う場合は、データフローの前方要素の入力、例えば「組み合わせ回路／ラッチ」の入力が、後方要素の入力とならないような順番にデータフロー内の要素の並べ替えを行う。この並べ替えを行う理由は、このデータフローの順に、計算機上で実行可能なプログラム言語に変換するよう想定しているので、データの流れる順番にデータフローの要素を並べる必要があるからである。
【００３６】
なお、図１のステップＳ６における、同時であるクロックを同一視してデータフローを新たに生成する場合のイメージを図１３に示す。図１３において、クロックＢとクロックＣの立ち上がりが同時であり、これらのクロックＢとクロックＣの立ち上がりに同期するレジスタからのデータフローを生成する。
【００３７】
以上説明したようにして得られたデータフローを用いて、本発明者によって提案されている方法（特願２００２−１７８９４５）を利用することによってプログラム言語への変換を行えば、高速にシミュレーションすることが可能となる。
【００３８】
以上説明したように、本実施形態によれば、複数のクロックに基づいて動作する回路を有するハードウェアに対して、依存関係に基づいてスケジューリングを行うため、冗長な演算を含まない結果を得ることが可能となり、高速なシミュレーションを可能にすることができる。  
（第２実施形態）
次に、本発明の第２実施形態によるデータフロースケジューリング方法を図１４乃至図１７を参照して説明する。
【００３９】
文の実行順序は、出力結果であるプログラム言語が正当な入出力応答を行うのであれば、どのような順序でも構わない。このため、スケジューリングを行った後で、文の順序を入れ替えることも許される。例えば、文の実行順序を変えることでプログラム言語の入出力応答は変わらないが、実行速度が速くなる場合など、文の順番を入れ替えることが必要となる。
【００４０】
しかし、図１４乃至図１５に示すように、時間に基づいてスケジューリングを行った場合、文の実行順序を変えたくても、多くが時間的に入れ替わってしまうため、順序変更はほとんどできない。例えば、図１４（ａ）に示すように、時刻ｔ０でクロックclock1の立ち上がりに基づいてレジスタｒ１が動作し、時刻ｔ２で組み合わせ回路／ラッチｆ１が動作し、図１４（ｂ）に示すように、時刻ｔ０でクロックclock2の立ち上がりに基づいてレジスタｒ２が動作し、時刻ｔ１（ｔ０＜ｔ１＜ｔ２）で組み合わせ回路／ラッチｆ２が動作し、時刻ｔ３（＞ｔ２）でレジスタｒ２が動作し、時刻ｔ４（＞ｔ３）で組み合わせ回路／ラッチｆ２が動作する。すなわち、図１５（ａ）に示すスケジュール表のようになり、このような回路を時間に基づいてスケジューリングすると、図１５（ｂ）に示すようになる。
【００４１】
そこで、本実施形態では、時間に基づいてスケジューリングされた結果や、依存関係に基づいてスケジューリングされた結果を、依存関係に基づいて、再スケジューリングするものである。
【００４２】
本実施形態によるデータフロースケジューリング方法の手順を図１６および図１７に示す。まず、再スケジューリング用の、新たなデータフローを設定する。この新たなデータフローは初期状態では空である。次に、スケジューリング結果からレジスタを見つけ（図１６のステップＳ６０参照）、見つけたレジスタが上記データフローに既に存在しているか否かの判定を行い（ステップＳ６１参照）、存在している場合はステップＳ６０に戻り、再度レジスタを見つける。存在していない場合は見つけたレジスタを上記データフローへ挿入する（ステップＳ６２参照）。その後、スケジューリング結果から全てのレジスタを探索したか否かの判定を行い（ステップＳ６３参照）、全てのレジスタを探索していない場合は、ステップＳ６０に戻り、上述のことを繰り返す。全てのレジスタを探索した場合は、図１７に示すステップＳ６４に進み、データフロー内のレジスタの並べ替えを行う。
【００４３】
その後、スケジューリング結果から組み合わせ回路／ラッチを見つけ（ステップＳ６５）、見つけた組み合わせ回路／ラッチが上記データフロー内に既に存在しているか否かの判定を行い（ステップＳ６６）、存在している場合は、ステップＳ６５に戻り、上述のことを繰り返す。存在していない場合は、ステップＳ６７に進み、見つけた組み合わせ回路／ラッチをデータフローに挿入する。そして、スケジューリング結果から全ての組み合わせ回路／ラッチを探索した否かの判定を行い（ステップＳ６８）、全ての組み合わせ回路／ラッチを探索していない場合は、ステップＳ６５に戻り、上述のことを繰り返す。全ての組み合わせ回路／ラッチを探索した場合は、ステップＳ６９に進み、データフロー内の組み合わせ回路／ラッチの並べ替えを行う。
【００４４】
次に、本実施形態の効果を説明するために、図１４に示すデータフローを、ａ）時間に基づいてスケジューリングした場合と、ｂ）本実施形態によってスケジューリングした場合のそれぞれに対して、スケジューリング後に計算機上で実行可能なプログラム言語として出力された結果を比較する。
【００４５】
ａ）時間に基づいたスケジューリングによるプログラム言語の出力結果は以下の通りとなる。
【００４６】
／／レジスタｒ１（clock1に同期）
ｒ１＝ｂ１；
／／レジスタｒ２（clock2に同期）
ｉｆ（ｓｅｌ）
ｒ２＝ｂ２；
／／組み合わせ回路ｆ２
ｆ２＝ｒ２；
／／レジスタｒ２（clock2に同期）
ｉｆ（ｓｅｌ）
ｒ２＝ｂ２；
／／組み合わせ回路ｆ２
ｆ２＝ｒ２；
／／組み合わせ回路ｆ１
ｆ１＝ｒ１；
ｂ）本実施形態のスケジューリングの途中では、以下のデータフローを得る。
【００４７】
／／レジスタｒ１（clock1に同期）
ｒ１＝ｂ１；
／／組み合わせ回路ｆ１
ｆ１＝ｒ１；
／／レジスタｒ２（clock2に同期）
ｉｆ（ｓｅｌ）
ｒ２＝ｂ２；
／／組み合わせ回路ｆ２
ｆ２＝ｒ２；
／／レジスタｒ２（clock2に同期）
ｉｆ（ｓｅｌ）
ｒ２＝ｂ２；
／／組み合わせ回路ｆ２
ｆ２＝ｒ２；
このデータフローに対して、制御信号
ｓｅｌ＝０；
が与えられられたとすると、冗長な箇所が削除され、
／／レジスタｒ１（clock1に同期）
ｒ１＝ｂ１；
／／組み合わせ回路ｆ１
ｆ１＝ｒ１；
となる。これが本実施形態によってスケジューリングされた結果となる。
【００４８】
上述の時間に基づいたスケジューリングの場合、スケジューリング結果の正当性は、時間でしか判断できない。そのため、異なる時間にスケジューリングされた演算同士で最適化などを行ってしまうと、結果の正当性を判断することができない。このことから、時間に基づいたスケジューリングの場合は、異なる時間にスケジューリングされた演算同士を利用した最適化などは行えない。
【００４９】
これに対して、本実施形態のように、依存関係に基づくスケジューリングの場合、依存関係さえ守られば、大域的に最適化を行うことができる。この結果、図１８に示すように、コード行数の点で見ても、優位性がある。
【図面の簡単な説明】
【００５０】
【図１】本発明の第１実施形態によるデータフロースケジューリング方法の手順を示すフローチャート。
【図２】本発明の一実施形態によってスケジューリングされるデータフローとスケジューリング結果を示す図。
【図３】データフローの例を示す図。
【図４】ＨＤＬの基本的な回路構成を示す図。
【図５】クロックの周期と位相、エッジの例を示す図。
【図６】クロックの立ち上がる（立ち下がる）順番の決定を示す図。
【図７】第１実施形態に係るクロックの立ち上がる（立ち下がる）順番の決定するフローチャート。
【図８】第１実施形態に係るクロックの立ち上がる（立ち下がる）順番の決定するフローチャート。
【図９】データフローの順番の決定を説明する図。
【図１０】複数のクロックが同時に立ち上がる例を示す図。
【図１１】複数のデータフローの併合のイメージを示す図。
【図１２】第１実施形態に係る複数のデータフローの併合の手順を示すフローチャート。
【図１３】立ち上がりが同時のクロックを同一視してデータフローを生成するイメージを示す図。
【図１４】データフローの例を示す図。
【図１５】時間に基づいてスケジューリングしたスケジュールとその結果を示す図。
【図１６】本発明の第２実施形態によるデータフローのスケジューリング方法の手順を示すフローチャート。
【図１７】本発明の第２実施形態によるデータフローのスケジューリング方法の手順を示すフローチャート。
【図１８】第２実施形態の効果を説明する図。
【図１】
2005071028.tif 000003
【図２】
2005071028.tif 000004
【図３】
2005071028.tif 000005
【図４】
2005071028.tif 000006
【図５】
2005071028.tif 000007
【図６】
2005071028.tif 000008
【図７】
2005071028.tif 000009
【図８】
2005071028.tif 000010
【図９】
2005071028.tif 000011
【図１０】
2005071028.tif 000012
【図１１】
2005071028.tif 000013
【図１２】
2005071028.tif 000014
【図１３】
2005071028.tif 000015
【図１４】
2005071028.tif 000016
【図１５】
2005071028.tif 000017
【図１６】
2005071028.tif 000018
【図１７】
2005071028.tif 000019
【図１８】
2005071028.tif 000020