(57)【要約】【課題】ネストした条件分岐における条件節演算の投機実行に関する制約を解消し、ネストした条件分岐における並列分岐の条件相互排他性の正確な表現を可能とするシステムの提供。【解決手段】回路の動作の制御およびデータの流れを表す制御データフローグラフの条件分岐を示す木の葉となっているノードに、一つの成分のみ１があるコードの条件ベクタとして、ある演算ノードが属する外側の条件演算が未確定で、内側の条件演算が確定した場合に設定され、前記内側の確定した条件演算のベクタ成分が１である位置のビットである有効ビット（Valid  Bits）を含む条件ベクタである、一般化条件ベクタ（GCV）を生成し、演算ノードの一般化条件ベクタは、未決定の条件演算の条件ベクタとビット論理和をとり、その際、内側の決定済みの条件の、一般化条件ベクタの有効ビットの成分１のビットを、前記ビット論理和演算では、マスクし、並列IF文を条件の投機実行と同一に扱う。【選択図】図１５
2008090439.tif 000002
【特許請求の範囲】
【請求項１】
動作記述のノードに対して条件ベクタ（Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を作成する手段を備え、
前記条件ベクタを作成する手段は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
前記動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリングを行うスケジュール手段を備えている、ことを特徴とする自動合成装置。
【請求項２】
前記スケジュール手段は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う、ことを特徴とする請求項１記載の自動合成装置。
【請求項３】
前記条件ベクタを作成する手段は、
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項１記載の自動合成装置。
【請求項４】
前記条件ベクタを作成する手段は、
条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）を割付け、
親のノードの基本条件ベクタ（ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる、ことを特徴とする請求項３記載の自動合成装置。
【請求項５】
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項３記載の自動合成装置。
【請求項６】
前記スケジュール手段は、演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する、ことを特徴とする請求項１記載の自動合成装置。
【請求項７】
前記スケジュール手段は、ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする、ことを特徴とする請求項１記載の自動合成装置。
【請求項８】
前記スケジュール手段は、一般化条件ベクタ（ＧＣＶ）における、演算の排他性の判定は、有効ビット以外の成分は０とみなす、ことを特徴とする請求項１記載の自動合成装置。
【請求項９】
前記スケジュール手段は、有効ビット位置が重ならない場合には、同一位置に１が重ならないか否かで排他をチェックする、ことを特徴とする請求項１記載の自動合成装置。
【請求項１０】
前記条件ベクタを作成する手段は、
条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し；
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す、
ことを特徴とする請求項３記載の自動合成装置。
【請求項１１】
前記スケジュール手段は、
一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し；
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ；
上記集合Ｓのそれぞれについて以下の{}の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする；
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し；
有効ビット以外の成分は０として、ベクトル加算し；
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする；
ことを特徴とする請求項３記載の自動合成装置。
【請求項１２】
前記スケジュール手段は、
動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされてなる、ことを特徴とする請求項１記載の自動合成装置。
【請求項１３】
前記スケジュール手段は、
動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする、ことを特徴とする請求項１記載の自動合成装置。
【請求項１４】
前記スケジュール手段は、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、及び/又は、パス長に関して、基本ブロックを超えた大局的な最適化を行う、ことを特徴とする請求項１記載の自動合成装置。
【請求項１５】
前記スケジュール手段において、
前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う、ことを特徴とする請求項１記載の自動合成装置。
【請求項１６】
前記スケジュール手段は、条件分岐を並列化した場合の、制御論理の生成にあたり、
有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する、ことを特徴とする請求項１記載の自動合成装置。
【請求項１７】
前記スケジュール手段は、有効ビット同士が重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、
複数の同期する状態遷移を融合して１つのＦＳＭ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める、ことを特徴とする請求項１６記載の自動合成装置。
【請求項１８】
動作記述のノードに対して条件ベクタを作成する工程を含み、
前記条件ベクタを作成する工程は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリング処理を行うスケジュール工程を含む、
ことを特徴とする自動合成方法。
【請求項１９】
前記スケジュール工程は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２０】
前記条件ベクタを作成する工程は、
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２１】
条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）を割付け、
親のノードの基本条件ベクタ（ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる、ことを特徴とする請求項２０記載の自動合成方法。
【請求項２２】
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項２０記載の自動合成方法。
【請求項２３】
演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２４】
ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２５】
条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し；
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２６】
一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し；
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ；
上記集合Ｓのそれぞれについて以下の処理｛｝内の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする；
処理を繰り返し｝
を繰り返し；
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し；
有効ビット以外の成分は０として、ベクトル加算し；
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする；
ことを特徴とする請求項１８記載の自動合成方法。
【請求項２７】
動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされてなる、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２８】
動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする、ことを特徴とする請求項１８記載の自動合成方法。
【請求項２９】
前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う、ことを特徴とする請求項１８記載の自動合成方法。
【請求項３０】
前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う、ことを特徴とする請求項１８記載の自動合成方法。
【請求項３１】
条件分岐を並列化した場合の、制御論理の生成にあたり、
有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する、ことを特徴とする請求項１８記載の自動合成方法。
【請求項３２】
有効ビット同士が重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、
複数の同期する状態遷移を融合して１つのＦＳＭ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める、ことを特徴とする請求項３１記載の自動合成方法。
【請求項３３】
動作記述のノードに対して条件ベクタを作成する処理を含み、
前記条件ベクタを作成する処理は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリングを行うスケジュール処理を、
コンピュータに実行させるプログラム。
【請求項３４】
請求項３３記載のプログラムにおいて、前記スケジュール処理は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う、ことを特徴とするプログラム。
【請求項３５】
請求項３３記載のプログラムにおいて、前記条件ベクタを作成する工程は、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とするプログラム。
【請求項３６】
請求項３５記載のプログラムにおいて、条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（ＢＣＶ）を割付け、親のノードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｔｒｏｌ  ｖｅｃｔｏｒ；ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる、ことを特徴とするプログラム。
【請求項３７】
請求項３５記載のプログラムにおいて、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とするプログラム。
【請求項３８】
請求項３５記載のプログラムにおいて、条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化する処理；
内側の条件演算ｃｉから外側の条件演算へ以下の処理、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す；
ことを特徴とするプログラム。
【請求項３９】
請求項３５記載のプログラムにおいて、
一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し；
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ；
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする；
処理を繰り返し｝
を繰り返し；
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し；
有効ビット以外の成分は０として、ベクトル加算し；
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする；
ことを特徴とするプログラム。
【請求項４０】
請求項３５記載のプログラムにおいて、動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされてなる、ことを特徴とするプログラム。
【請求項４１】
請求項３３記載のプログラムにおいて、動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする、ことを特徴とするプログラム。
【請求項４２】
請求項３３記載のプログラムにおいて、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う、ことを特徴とするプログラム。
【請求項４３】
請求項３３記載のプログラムにおいて、前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う、ことを特徴とするプログラム。
【請求項４４】
請求項３５記載のプログラムにおいて、条件分岐を並列化した場合の、制御論理の生成にあたり、
有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する、ことを特徴とするプログラム。
【請求項４５】
請求項４４記載のプログラムにおいて、有効ビットの重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、
複数の同期する状態遷移を融合して１つのＦＳＭ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める、ことを特徴とするプログラム。
【請求項４６】
少なくとも演算処理の動作記述を含むソース文を入力して解析し、複数の演算資源を用いて演算を並列実行可能なプロセッサ向けのコードを生成するコンパイラ装置であって、
動作記述のノードに対して条件ベクタを作成する手段を備え、
前記条件ベクタを作成する手段は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
前記動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含む最適化を行うスケジュール手段を備えている、ことを特徴とするコンパイラ装置。
【請求項４７】
前記スケジュール手段は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を含む最適化を行う、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項４８】
前記条件ベクタを作成する手段は、
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項４９】
前記条件ベクタを作成する手段は、
条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（ＢＣＶ）を割付け、親のノードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる、ことを特徴とする請求項４８記載のコンパイラ装置。
【請求項５０】
動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める、ことを特徴とする請求項４８記載のコンパイラ装置。
【請求項５１】
前記スケジュール手段は、演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５２】
前記スケジュール手段は、ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５３】
前記スケジュール手段は、一般化条件ベクタ（ＧＣＶ）における、演算の排他性の判定は、有効ビット以外の成分は０とみなす、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５４】
前記スケジュール手段は、有効ビット位置が重ならない場合には、同一位置に１が重ならないか否かで排他をチェックする、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５５】
前記条件ベクタを作成する手段は、
条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し；
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す、
ことを特徴とする請求項４８記載のコンパイラ装置。
【請求項５６】
前記スケジュール手段は、
一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し；
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ；
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする；
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し、
有効ビット以外の成分は０として、ベクトル加算し、
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする、ことを特徴とする請求項４８記載のコンパイラ装置。
【請求項５７】
前記スケジュール手段は、
動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされてなる、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５８】
前記スケジュール手段は、
動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項５９】
前記スケジュール手段は、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う、ことを特徴とする請求項４６記載のコンパイラ装置。
【請求項６０】
前記スケジュール手段において、
前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う、ことを特徴とする請求項４６記載のコンパイラ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路の自動合成装置、方法に関し、特に、回路の動作の制御およびデータの流れを表す制御データフローグラフを用いて、排他性の解析、各種投機実行等の最適化を行う装置と方法並びにコンパイラ技術に関する。
【背景技術】
【０００２】
本発明に関連した技術について概説しておく。動作合成において条件分岐を含む回路の制御およびデータの流れを表わす制御データフローグラフ（ＣＤＦＧ）からその演算の実行順序を決定し、実行ステップを決定するスケジューリングを行うためには、制御データフローグラフ内の演算の実行の排他性を解析し、同一の演算器を共用できるかどうかを判定する必要がある。このような排他性の解析は、対象となる演算が異なる分岐に属するか否かを、制御データフローグラフを直接検査することで行うことが可能である。
【０００３】
＜単一条件分岐の投機的実行＞
単一条件分岐の投機的実行について説明する。スケジューリングにおいて投機的実行とは、分岐内の演算、条件節の演算を、条件の真偽が確定する前の制御ステップに、スケジューリングすることを意味する。
【０００４】
命令移動（コードモーション）を行う場合は、条件内の演算コードを、実際に、条件文の外へ移動してしまう。
【０００５】
最初に、投機実行の種類について説明する。投機実行には大きく分けて、
・単一条件分岐文に対する投機実行と、
・複数の条件分岐文間の投機実行（条件分岐文同士の並列化）
とがある。
【０００６】
図１に、単一条件分岐に対する投機実行のいくつかの典型的な例を示す。図１において、四角は基本ブロックを示す。Ｔ、Ｆはそれぞれ条件分岐の真（Ｔ）と偽（Ｆ）の分岐を示す。また、基本ボックス間の矢印付き実線は、それらの間の制御依存を示す。
【０００７】
図１（ａ）は、Ｉｎ−ｏｒｄｅｒ、即ち動作記述どおりの順番で実行される場合である。
【０００８】
ｔ＝ｂ＋ｃ（１）；
ｉｆ  （ｃ＞ａ＊ｂ）
｛ｔ１＝ｘ＋ｙ；
ｔ２＝ｔ１＋ｚ；
ｔ３＝ｔ２＋ｕ；
ｏ＝ｔ３＋ｓ；｝
ｅｌｓｅ    
｛  ｔ１＝ｘ＋ｔ；
ｏ＝ｔ１＋３；｝
ｙ＝ｘ＊ｃ；
【０００９】
これを投機実行した例が、図１（ｂ）乃至（ｅ）である。なお、図１（ｂ）乃至（ｅ）では、すべて命令移動（コードモーション）を行ったイメージで描かれている。
【００１０】
図１（ｂ）の”Ｂｒａｎｃｈ  ｎｏｄｅ  ｓｐｅｃｕｌａｔｉｏｎ  ａｎｄ  ｐｕｓｈ  ｄｏｗｎ”は、条件文のＴｈｅｎ節の（２つの）演算（ｔ１＝ｘ＋ｙ；ｔ２＝ｔ１＋ｚ；）を投機実行し、さらに、条件文（ｉｆ  （ｃ＞ａ＊ｂ））の前の演算（図１のｔ＝ｂ＋ｃ；（１））を、ＥＬＳＥ節側に移動した例（”Ｐｕｓｈ−ｄｏｗｎ”）である。これは、変数ｔがＥＬＳＥ節でのみ参照されることを利用し、条件節よりも、（１）の加算演算（ｂ＋ｃ）を、後のサイクルにスケジューリングすることにより、ＥＬＳＥ節のみで実行させる。このコードモーションによって意味は変わらない。この場合は、ブックキーピングと呼ばれるコードの修正は不要である。
【００１１】
図１（ｃ）の”Ｌａｔｅ  ｃｏｎｄｉｔｉｏｎ  ｅｘｅｃｕｔｉｏｎ”は、Ｔｈｅｎ節（｛ｔ１＝ｘ＋ｙ；ｔ２＝ｔ１＋ｚ；ｔ３＝ｔ２＋ｕ；  ｏ＝ｔ３＋ｓ；｝）、Ｅｌｓｅ節｛ｔ１＝ｘ＋ｔ；ｏ＝ｔ１＋３；｝の両方を、条件節演算の前のサイクルで実行する投機実行である。演算器が豊富にあり、条件節の実行が早いサイクルで行えないような場合に、有利な変換となる。
【００１２】
図１（ｄ）の”Ｅａｒｌｙ  ｃｏｎｄｉｔｉｏｎ  ｅｘｅｃｕｔｉｏｎ”は、図１（ｃ）の逆の場合に対応し、条件演算を、条件分岐文の前の文の演算（図では文ｔ＝ｂ＋ｃ；（１））よりも前のサイクルで実行するものである。すなわち、条件演算をできるだけ早く実行する。ｔ＝ｂ＋ｃ；（１）は、ＴＨＥＮ条件、ＥＬＳＥ条件のどちらかで実行されるが、コードモーションで行う場合には、ＴＨＥＮ節とＥＬＳＥ節に、コピーされて、両方に移動されることになる。条件フラグ付き命令などを持つプロセッサの場合、条件分岐の結果を保持しておいて、条件節内の演算は条件フラグ付き命令を実行することでもよい。
【００１３】
図１（ｅ）の”Ｄｕｐｌｉｃａｔｉｏｎ−Ｕｐ”は、条件文の後続の文の演算命令（ｙ＝ｘ＊ｃ；）をＴＨＥＮ、ＥＬＳＥそれぞれの条件節の中にコピーして移動するものである。
【００１４】
図１（ｄ）、図１（ｅ）とも利用の仕方如何で、同一の演算器数で、実行サイクル数を削減することが可能である。
【００１５】
なお、図１では、ＩＦ文（２分岐）の例を示したが、もちろん、言語Cのｓｗｉｔｃｈ文のような多分岐命令でも同様の投機実行を考えることができる。
【００１６】
以上示したように、単一の条件分岐に対しても、様々な投機実行が考えられる。本明細書では、上記した単一の条件分岐に対する投機実行を、「局所的な」投機実行と呼ぶ。
【００１７】
なお、後述されるように、本発明によるスケジューリングでは、投機実行、後の節で述べる投機実行どを、すべて効率的に実行可能とするものである。
【００１８】
＜ＣＤＦＧ＞
次にコントールデータフローグラフ（ＣＤＦＧ）について説明する。ＣＤＦＧは、制御とデータの依存関係を同時に表現するものであり、図２にその一例を示す。以下、動作合成手法が利用するＣＤＦＧについて説明する。従来、多くのＣＤＦＧは基本ブロック内をＤＦＧで持ち、基本ブロック間の制御関係をＣＦＧ（Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ）（基本ブロックノードとした有向グラフ）で持つような形式が多かった（図１等）。
【００１９】
しかしながら、ＣＤＦＧの表現形式では、基本ブロック間の制御依存関係が中心に表現され、基本ブロック間のデータ線が直接つながっていない。大局的なスケジューリングを行うためには、基本ブロック間で、いくつかの演算子を、命令移動（コードモーション）する必要があり、全体として効果のある移動を見つけることは難しかった。
【００２０】
このため、特定のパス（トレース）を別に作成する手法（Ｔｒａｃｅ  ｓｃｈｅｄｕｌｉｎｇ等）がとられていたが、この方法では、すべてのトレースを最適化することはできない。以下に説明するＣＤＦＧは、これらの短所を克服し、大局的なスケジューリングを考慮しやすいデータ表現である。
【００２１】
ＣＤＦＧでは、条件分岐の制御構造は、各データ線毎に与えられる。
【００２２】
図２において、
△（「Ｆｏｒｋノード」と呼ぶ）は、データのＦＯＲＫ、
▽（「Ｊｏｉｎノード」と呼ぶ）は、データのＪＯＩＮ
のように表現される。
【００２３】
変数ａ、ｂ、ｃの値が条件節演算（ａ＞ｂ）の値で２つにわかれ（ＦＯＲＫ）、両方の分岐を計算した後に、条件節演算（ａ＞ｂ）の結果で選択される（ＪＯＩＮ）と考える。
【００２４】
条件演算である「ａ＞ｂ」からＦＯＲＫノード、ＪＯＩＮノードへ入る線を、「条件線」と呼ぶ。データの流れを示す線を、「データ線」と呼ぶ。
【００２５】
従来手法では、基本ブロックが陽に表現されていたが、ＣＤＦＧでは、基本ブロックは陽に表現されておらず、複数の基本ブロック間のデータ依存関係が直接表現されている点に注目されたい。
【００２６】
複数の基本ブロックが１つのＣＤＦＧとして、基本ブロック毎にグループ化されることもなく表現できることで、このＣＤＦＧは、大局的なスケジューリングを行うのに好都合である。
【００２７】
条件節が条件分岐内演算よりも先に確定する（Ｉｎ−ｏｒｄｅｒ）場合には、通常の分岐動作になり、条件節が遅く実行されると（図１（ｃ）のｌａｔｅ  ｃｏｎｄｉｔｉｏｎａｌ  ｅｘｅｃｕｔｉｏｎ）、実際に、Ｆｏｒｋ、Ｊｏｉｎの動作（両方が実行され最後に値を選択する）になる。
【００２８】
これらの様々な投機実行を、ＣＤＦＧは、単一条件分岐文の投機実行をそのままの形状で（コードモーションを行うことなく）表現可能である（実際には、後述する「条件ベクタ」を、各演算ノードにつけることで可能になる）。
【００２９】
＜条件ベクタ＞
条件ベクタは、条件分岐に基づく演算の排他性を検出するために導入されたベクタ表現であり、ＣＤＦＧの演算ノードに条件ベクタを付属させることで、あらゆる投機実行を統一的に表現し、すべてのパスの最適化を目的にしたスケジューリングを効率的に行うことができる。つまり、前述したように、基本ブロックを意識することなく、複数の条件分岐内の演算を、１つの基本ブロック内の演算のように、スケジューラが扱うことができるようになる。
【００３０】
まず、条件ベクタについて説明し、次に、条件ベクタに基づいたスケジューリングについて説明する。
【００３１】
＜基本条件ベクタ＞
条件ベクタ（Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）は、条件分岐（言語ＣのＩＦ文やＳＷＩＴＣＨ文）の実行条件をベクタ形式で表現するものである。図３を用いて説明する。図３（ａ）の左の動作記述は、３階層のネストしたＩＦ文を、疑似Ｃコードで示したものである（特許文献１、２等参照）。
【００３２】
図３（ａ）において、”ａ；”，”ｂ；”等は、等はＣ言語の「文」を意味し、”ｃ１”，”ｃ２”等は、条件節の中の演算を意味する。図３（ｃ）は、この動作記述のＩＦ文の制御構造を、二分木で表現している。
【００３３】
条件ベクタ（ＣＶ）は、以下のようにつけられる。まず右の条件分岐を示す「木」の「葉」となっているノードに、ワンホットエンコード（１つの成分のみ”１”があるコード）のベクタを作成する。
【００３４】
図３(ｃ)の例では、３階層の４分岐であり、ｃ、ｅ，ｆ，ｇが葉（リーフ）ノードであり、それぞれに、例えば
ｃ：［１，０，０，０］、
ｅ：［０，１，０，０］、
ｆ：［０，０，１，０］、
ｇ：［０，０，０，１］、
というベクタを与える。各ベクタは、１つの成分のみが”１”であり、かつ、互いに直交している（任意の２つのベクタの内積＝０；ベクタは１次独立）。
【００３５】
次に、それぞれの親のノードに対して、子供のノードのベクタのビットＯＲ(bitwise OR)の値を与える。例えば、ノードｄの条件ベクタは、ｄの子供ノードであるｅのベクタ：［０，１，０，０］と、ノードｆのベクタ：［０，０，１，０］のビットＯＲ(bitwise OR)で与えられ、
ｄ：［０，１，１，０］となる。
【００３６】
さらに、ノードｂの条件ベクタは、ｃのベクタ：［１，０，０，０］と、ｄのベクタ：［０，１，１，０］のビットＯＲであるから、
ｂ：［１，１，１，０］
となる。
【００３７】
ノードａは、すべてのビットＯＲであり、［１，１，１，１］となる。
【００３８】
条件節ｃ１の条件ベクタは、ａと同じであり、［１，１，１，１］、
条件節ｃ２の条件ベクタは、ｂと同じであり、［１，１，１，０］
である。
【００３９】
図３（ｂ）は、２階層のネストしたＩＦ文（４分岐）と、対応する基本条件ベクタを示した。図３（ａ）と図３（ｂ）は、条件分岐の構造は異なっているが、リーフノード（葉ノード）の数が等しいため、同じ次元数であり、葉ノードの条件ベクタはワンホット符号が同様に付与される。葉ノード以外のノードも子供のＢＣＶのビット論理和で得られている。
【００４０】
ベクタの次元数は、葉の数に等しいから、ＩＦ文のネストの場合、
ベクタの次元数＝「ＩＦ文の条件節の数＋１」
となる。
【００４１】
ＳＷＩＴＣＨ文がある時も同様に定義される。ＩＦ文は２分岐構造であるが、ＳＷＩＴＣＨ文では、多分木になるだけである。ＳＷＩＴＣＨだけの場合の分岐数は、葉の数であるから、「ＳＷＩＴＣＨ文のＣＡＳＥ節の数」と等しくなる。ＳＷＩＴＣＨ文をＩＦ文が重なる場合、ＳＷＩＴＣＨ文が複数重なる場合は、重なる毎に次元数が１小さくなる。注意すべき点は、ＩＦ文の数の指数になることなく、ＩＦ文の数＋１とリニアな次元数であることとである。
【００４２】
また、条件ベクタの各成分が”０”と”１”のバイナリ値であり、通常のｉｎｔ（整数型）の３２ビット（または、６４ビット）で３２次元を表せ、計算のために必要な論理ビットＯＲ演算も高速に（１サイクルで）実現できる。実際のプログラムでは、ＩＦ文とＳＷＩＴＣＨ文で構成される木構造を深さ優先探索（ｔｒｅｅ  ｗａｌｋ）し、葉の数を数える形で実装している。また、深さ優先探索の順番に、上位ビットから順に、１をつけるワンホットエンコードとしている。具体的には、動作記述の上の方にくる葉から順に、［１，０，０，，，］、［０，１，０，，，］と割り付けている。
【００４３】
＜ＢＣＶ＞
このように動作記述の上で定義される条件ベクタを「基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）」と呼ぶ。基本条件ベクタは、ある１つのネストした条件分岐に対して以下のように定義される。
【００４４】
＜基本条件ベクタ（ＢＣＶ）の定義＞：
次元数＝葉の数；
BCV (n) = ワンホットエンコード            （演算ｎが葉にある演算の場合）；
=  BCV (s) or BCV(t) or BCV(u) or BCV(v)    （n が葉以外の場合）；
【００４５】
ただし、
演算s,t,u,v は、nの（分岐の深い方向に）後続する演算、
or はビットワイズの論理和を示す。
【００４６】
条件ベクタの１成分は、演算の実行条件を、葉の条件のＯＲで示していることになる。よって、２つの演算ノードの条件ベクタに関して同じ成分に１が無い場合は、互いに排他にしか実行されないことになる（一方の演算ノードが実行される場合、他方は実行されない）。このような排他性を「条件排他」と呼ぶ。
【００４７】
一方、異なるサイクルで実行される場合の排他性は、「時間排他」と呼ぶ。
【００４８】
条件排他な演算は時間排他の場合と同様に、同時には実行されないことから、同一の演算器を共用（シェア）することが可能である。
【００４９】
そして、条件ベクタを利用すると、２つの演算の排他性を、条件ベクタのビット論理和（ＯＲ）が”０”であることで、直ちに判定可能である（ＣＰＵの一クロック命令で実行できる。）。
【００５０】
分岐命令に基づく条件排他性には、動作記述で異なった分岐にある演算という動作記述に、陽に（explicitly）記述されるもの以外にも、データの依存関係に基づく条件排他性がある。これは、動作記述上に、陽には現れない暗黙的な排他性である。これらを、「データ依存条件排他」または「暗黙的な条件排他」と呼ぶ。
【００５１】
データ依存による排他性は、演算の結果がある分岐で使用されない場合に、その分岐にある演算との間に出現する条件排他性である。例えば、図４（ａ）の動作記述で、”ｔ＝ｂ＋ｃ；”の結果は、後続のＩＦ文のＴＨＥＮ節では使用されず、ＥＬＳＥ節（ｏ＝ｘ＋ｔ；）のみで使用される。つまり、条件節”（ａ＊ｂ＜ｃ）”の結果が偽の場合だけ、変数ｔの値が利用され、条件節の結果が真の場合には、変数ｔの値は利用されない。
【００５２】
この暗黙的な排他性は、図４（ｂ）の命令移動による実現例のように、”ｔ＝ｂ＋ｃ”をＥＬＳＥ節内にコードモーションすることで、動作の意味を変えずに、陽に（explicitly）、条件排他性を出すことができる。しかしながら、コードモーションは必ずしも高速化に有利とは限らず、”ｔ＝ｂ＋ｃ；”を、条件節の前に実行した方が有利な場合には、不利になる。
【００５３】
コードモーションを行うべきかどうかを大局的視点で、スケジューリングに実際に有利なように選択することは、比較的、困難である。
【００５４】
＜ＥＣＶ＞
条件ベクタを、ＣＤＦＧ上で付与することで、このデータ依存排他性を解析する。ＣＤＦＧ上で定義される条件ベクタを拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）と呼ぶ。
【００５５】
拡張条件ベクタの付与の仕方を、図４（ｃ）を用いて説明する。最初に、ＪＯＩＮノードの入力に基本条件ベクタ（ＢＣＶ）を与え、ＪＯＩＮノードに直結している演算ノードのＥＣＶとして、そのＢＣＶを与える（これは、演算ノード自身の持つＢＣＶと同じ値である）。
【００５６】
他の演算ノードのＥＣＶは、データフローの後続の演算のＥＣＶのビットワイズ論理和で求めることができる。
【００５７】
動作記述で求められるＢＣＶは、演算を記述してある位置（例えば木構造の位置）で決定されるのに対し、ＥＣＶでは、ＣＤＦＧ上のデータ線に沿って論理和をとっていくため、データ依存性を考慮した暗黙的な条件排他を検出できる。
【００５８】
図４（ａ）において、先ほどの”ｔ＝ｂ＋ｃ”のＢＣＶは［１，１］であるが、ＥＣＶは、図４（ｃ）に示すように、［０，１］となる。ＥＣＶの［０，１］は、ＥＬＳＥ節だけでこの演算（”ｔ＝ｂ＋ｃ”）の結果”ｔ”が使われていることを示す。
【００５９】
但し、この”ｔ＝ｂ＋ｃ”の加算が、直ちに、ＴＨＥＮ節の加算と実際に演算器を共用できるわけではない。
【００６０】
これは、条件節の結果が真か偽が確定する以前では、ｔの値を計算して保存しておく必要があるからである。すなわち、このデータ依存排他性により、演算器をシェアするためには、条件節”（ａ＊ｂ＜ｃ）”が”ｔ＝ｂ＋ｃ”よりも先に実行される（スケジューリング）されている必要がある。
【００６１】
この関係は、条件排他性が、帰属する条件節が確定したか否かにより、動的に変化することを示している。
【００６２】
ある演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）は以下の通り定義される。
【００６３】
ECV(n) =   [1]   nが終端ノードの直前ノードの場合；
ECV(n) =   BCV(n)   nがJoin ノードの直前ノードまたは、条件演算の場合；
ECV(n) =   ECV(k) or ECV(l) or ... or ECV(m) 上記２つ以外の場合
（ただし、
k,l,m はノードn の後続ノード、
[1]、[0]は、それぞれすべての成分が1 、0 のベクタを示す）
【００６４】
＜ＡＣＶ＞
動的排他性は、条件分岐の条件節の真偽判定が終了しているかどうかによって、動的に決まる排他性である。具体的には、各種の投機実行は、この動的排他性を持ち、この動的排他性を表せるのが動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）である。
【００６５】
図５（ａ）の動作記述を投機実行する場合を考える。ＴＨＥＮ節の”ｘ＋ｙ＋ｚ”の２つの加算だけを、条件節の前に投機実行する場合、命令移動を行うと、図５（ｂ）のようになる。このような命令移動が有効であるどうかは、利用可能な演算器の数等によって変化するため、命令移動を画一的に行うのは得策でない。
【００６６】
一方、動的条件ベクタ（ＡＣＶ）を利用して、このような投機実行を実現できる。
【００６７】
図５（ｃ）は、加算器の数１個の制約で、Ｉｎ−ｏｒｄｅｒでスケジューリングした例を示す。図５（ｄ）は、加算器の数１個の制約で、投機実行を考慮したスケジューリング結果を示している。
【００６８】
図５（ｃ）と図５（ｄ）から、同じ演算器の個数でありながら、最大サイクル数を、「５」から「３」に減少できている。
【００６９】
Ｉｎ−ｏｒｄｅｒ実行では、条件節”（ａ＊ｂ＜ｃ）”が終了してから、その条件テストの結果にそって、ＴＨＥＮ節またはＥＬＳＥ節が実行される。それぞれに必要な実行サイクルは、５サイクル、または、３サイクルである。
【００７０】
条件節が確定している場合には、動的条件ベクタＡＣＶは、拡張条件ベクタＥＣＶと同一の値を持つ。
【００７１】
図５（ｄ）のように、投機実行が行われる場合に、動的条件ベクタＡＣＶのベクタが、投機実行したかどうかに応じて動的に変化する。
【００７２】
これは、投機実行した場合に、実際に実行条件が変化することを、動的条件ベクタＡＣＶが表現していることを示している。
【００７３】
図５（ｄ）において、図５（ａ）のＴＨＥＮ節の最初の加算”ｘ＋ｙ”、および２番目の加算”＋ｚ”は、第１サイクル（以降、スケジューリングされる状態、サイクルのことを「制御ステップ」と呼ぶ）、または、第２サイクルに投機的にスケジューリングされている。
【００７４】
条件節の演算（”ａ＊ｂ＜ｃ”）は、
”＊”が第１制御ステップに、
”＜”が第２制御ステップに、
それぞれスケジューリングされており、
条件演算の真偽が確定していない状態である。
【００７５】
そして、この場合、ＴＨＥＮ節かＥＬＳＥ節のどちらを実行すべきかは不明である。よって、図５（ｄ）において、ＴＨＥＮ節の２つの加算演算は、条件の結果にかかわらず、常に実行しなければならない。つまり、命令移動で実現した例である、図５（ｂ）の動作となる。
【００７６】
すなわち、ある演算が、投機実行により、条件が確定していない制御ステップに、スケジューリングされると、その制御ステップでは、ＴＨＥＮ節とＥＬＳＥ節の条件排他性はなくなるわけである。
【００７７】
図５（ｄ）において、制御ステップ２の加算ノード（＋）の条件ベクタは、［１，０］と未確定条件（（ａ＊ｂ）＜ｃ）の条件ベクタ［１，１］のビットＯＲにより、［１，１］となる。
【００７８】
このような、条件節の確定、未確定に応じて変換する排他性を表現するのが、動的条件ベクタＡＣＶである。
【００７９】
演算ノードの動的条件ベクタＡＣＶは、自ノードの帰属する条件節の未確定の条件演算の拡張条件ベクタＥＣＶとの論理和で計算できる。図５（ｄ）において、制御ステップ１、２に投機実行された２つの加算（ｓ＝ｘ＋ｙ＋ｚの２つの加算）のＥＣＶは、両方とも［１，０］であるが、演算の帰属する条件節の未確定条件の演算”＞”のＥＣＶ［１，１］との論理和をとるため、２つの加算のＡＣＶはともに［１，１］となる。
【００８０】
この意味は、２つの加算（ｓ＝ｘ＋ｙ＋ｚの２つの加算）は、もともと、ＴＨＥＮ節の中にあることから、そのＡＣＶは［１，０］であったが、投機実行され、条件が確定していない制御ステップにスケジューリングされると、ＴＨＥＮ節、ＥＬＳＥ節の両方の条件で実行しなければならなくなったため、［１，１］のベクタになったと考えればよい。
【００８１】
即ち、動的条件ベクタＡＣＶは、未確定の条件演算のＥＣＶとの論理和という簡単な（ＣＰＵの一サイクル命令で実行可能な）演算によって計算することができ、投機実行の際の条件排他性を正しく表現できる。
【００８２】
このとき、実際にＣＤＦＧの形状やトポロジ（接続関係）には変化が無く、演算ノードについた条件ベクタの値が変化するだけで表現できている点が重要である。
【００８３】
ＡＣＶは、演算ノードがスケジューリングされる時に一回計算されるだけであるから、何度も計算をしなおす必要がある訳ではない。つまり、ＡＣＶの計算量は、非常に小さい（条件節の数（通常２〜７程度）に比例）。
【００８４】
図５では、利用可能な加算器は１つという演算器制約の下でスケジューリングを行ったが、図５（ｃ）では、制御ステップ３で、［１，０］のベクタと、［０，１］のベクタを持つ加算器が互いに排他なことを利用している（同一成分に１が無いから排他）。
【００８５】
図５（ｄ）では、制御ステップ３で［１，０］と［０，１］が１つの加算器をシェアしている。一方、制御ステップ１、２では、加算は常に実行されるため、演算器のシェアは行えない。
【００８６】
ＡＣＶは、これらの動的に変化するシェアの可能性も考えた上で、必要な演算器数を簡易に計算できるなどの特徴ももっている。これらについては、後述する。
【００８７】
＜演算ノードｎに対する動的条件ベクタＡＣＶ（ｎ）の定義＞：
ACV(n) = ECV(n) or ECV(Ci) or ECV (Cj) or .. or ECV(Ck) 
【００８８】
ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノード（条件の真偽を決定する演算）であって、ＡＣＶを求めるその制御ステップで未確定（スケジューリングされていない）なものである。
【００８９】
図６（ａ）に、動作記述
１：ｔ＝ｂ＋ｃ；  
２：ｉｆ  （ａ＊ｂ＜ｃ）  ／＊ｃ１＊／
３：ｏ＝ｘ＋ｙ＋ｚ＋ｓ＋ｕ；
４：ｅｌｓｅ
５：ｏ＝ｘ＋ｔ；
に対する基本条件ベクタＢＣＶ、拡張条件ベクタＥＣＶ、動的条件ベクタＡＣＶを示す。但し、ＡＣＶは条件”ｃ１”が未確定の時の値を示している。
【００９０】
一行目の加算（”ｔ＝ｂ＋ｃ”、「演算１」という）のＢＣＶは（１，１）、ＥＣＶは（０，１）であり、データ依存排他があることを示している。
【００９１】
この動作記述に対し、ＴＨＥＮ節の加算２つ（ｖ＝ｘ＋ｙ＋ｚ；を構成する２つの加算演算）の投機実行と、演算１（ｔ＝ｂ＋ｃ；）のＥＬＳＥ節へのｐｕｓｈ−ｄｏｗｎを命令移動（コードモーション）で行った例を、図６（ｂ）に示す。このような命令移動を、全体の最適化を目指して行うことは困難といえる。
【００９２】
図６（ｃ）、図６（ｄ）は、条件ベクタを用いた手法で、演算器制約として加算器１個の制約のもとで、スケジューリングした結果である。
【００９３】
図６（ｃ）は、ｉｎ−ｏｒｄｅｒのスケジューリング、図６（ｄ）がＴＨＥＮ節の投機実行とＥＬＳＥ節へのｐｕｓｈ−ｄｏｗｎを行ったスケジューリングの例を示す図である。
【００９４】
図６（ｃ）のＩｎ−ｏｒｄｅｒ実行では、最大６サイクル必要であるが、図６（ｄ）のＯｕｔ−ｏｆ−ｏｒｄｅｒ実行では、最大４サイクルに改善されている（但し、この場合、最小サイクルは、３サイクルから４サイクルへと増加している）。
【００９５】
図６（ｃ）では、演算１が条件”ｃ１”が確定する前に実行されるため、ＡＣＶが［１，１］となっている。
【００９６】
一方、図６（ｄ）では、ｏｕｔ−ｏｆ−ｏｒｄｅｒスケジューリングが実行されており、ＴＨＥＮ節の２つの加算（ｖ＝ｘ＋ｙ＋ｚの２つの加算）が制御ステップＳ１、Ｓ２に割り当てられ、そのＡＣＶは、［１，１］となる。一方、演算１（ｔ＝ｂ＋ｃ；）は条件演算”ｃ１”の後の制御ステップ３にスケジューリングされたため、ＡＣＶが［０，１］となり、データ依存排他性を有用に利用できている。
【００９７】
条件ベクタを用いたスケジューリングでは、制御依存を陽に意識する必要はなく、ＡＣＶを用いて、必要演算器数の算出、管理を行えばよい。
【００９８】
様々な投機実行を行った場合、命令移動をする方式では、動作の同一性を保証するために、ブックキーピング（Ｂｏｏｋ  Ｋｅｅｐｉｎｇ）と呼ばれる操作が必要になるが、条件ベクタを用いた場合、コンパイラのＢｏｏｋ  Ｋｅｅｐｉｎｇに相当するコード修正（補償）は不要とされ、最後に制御論理を生成する時に、スケジューリングされたＡＣＶやＡＣＶの加算結果（後述）を利用して、規則的にすべての実行パスを最適化した制御を正しく生成できる。
【００９９】
スケジューリングは、演算器の遅延時間と、クロック周期を比較して、いくつの逐次な演算を１つの制御ステップに割り当てるか考慮して行われる。よって、条件演算と分岐内演算が同一サイクルにスケジューリングされた場合には、条件演算が確定したか、確定していないかは、演算の遅延時間を考慮した上で決定する。
【０１００】
図７に、演算遅延とクロック周期と動的条件ベクタＡＣＶと合成されるデータパス（回路構成）の関係を示す。最上段の欄に動作記述、その下に対応するＣＤＦＧ、最下段にデータパスを示す。
【０１０１】
図７（ａ）と、図７（ｂ）は、条件演算（（a＞b）と、（a&&c））のそれぞれの遅延が５ｎｓと０．５ｎｓと異なる以外は、同型のＣＤＦＧとなっている。
【０１０２】
図７において、クロック周期を７ｎｓ、加算器の遅延を５ｎｓとする。このとき、図７（ａ）の場合は、条件節演算ａ＞ｂの遅延と、加算の遅延５ｎｓの算術和が１０ｎｓとなり、クロック周期の７ｎｓを超えてしまう。よって、逐次に実行することはできず、並列に実行することになる。従って、条件節ａ＞ｂの演算は、加算演算を実行する場合には確定していないことになる。よって、加算器の動的条件ベクタＡＣＶは、条件演算のＥＣＶ［１，１］と論理和をとり、［１，１］となる。
【０１０３】
一方、図７（ｂ）の例は、条件演算＆＆の遅延と加算の遅延の和が、クロック周期の７ｎｓ以下である。よって、条件を確定した後で、変数ａ、ｃをセレクトして加算することが、一クロック以内で可能である（実際のスケジューリング時には、セレクタ（マルチプレクサ）の遅延も考慮してスケジューリングするが、ここでは、簡単のため、セレクタ遅延について言及しない）。加算ノードの動的条件ベクタＡＣＶは、条件ａ＆＆ｃが確定しているため、［１，０］、［０，１］のままである。
【０１０４】
それぞれのデータパス（回路図）は、図７（ａ）、図７（ｂ）の最下段に示したようなものになる。図７（ａ）では、加算器が２つ必要となり、図７（ｂ）では、加算器の共用が可能であり、加算器は１つで実現できる。演算の遅延がクロック周期に収まるようになっている。
【０１０５】
図７（ａ）の構成は、一クロック内の投機実行を行っていることを意味している。加算演算（ａ＋ｂとｂ＋ｃ）を投機実行し、条件演算の結果により、セレクタ（ＭＵＸ）で一方を選択している。これらのデータパスも、動的条件ベクタＡＣＶから、簡単に構成できる。
【０１０６】
また、図７（ａ）の場合でも、クロック周期が１３ｎｓ等と、比較器と加算器の遅延の和よりも大きい場合には、比較演算確定後に加算を開始することが可能であるため、そのような場合には、加算演算のＡＣＶも［１，０］、［０，１］のままであり、加算器１つでも実現可能である。ただし、クロック周期が大きい時でも、加算器を２つ利用し、演算器をシェアしない方がよい場合もある。
【０１０７】
すなわち、ＡＣＶはシェア可能であることを示しているだけであり、ＡＣＶがシェア可能であることを示しているからといって、必ずしも、シェアする必要はない。
【０１０８】
以上のように、ＡＣＶは、１制御ステップ内でも、条件演算と分岐内演算の遅延とクロック周期の関係をみた上で、条件演算が確定であるか／未確定かによって決定される。
【０１０９】
スケジューラは、１制御ステップ内でも、遅延をみて、様々なスケジューリングを試す構成とされているが、ＡＣＶを利用すれば、そのような場合の排他性は、正確に表現可能である。
【０１１０】
この条件排他の判定は、算術演算等の演算のほか、配列アクセスや信号の入出力も含むすべての演算に適用可能である。ＣＤＦＧのすべての演算ノードに条件ベクタを付与し、様々な処理を効率的に処理している。
【０１１１】
次に、スケジューリングされた各制御ステップでの最低限必要な演算器数を条件ベクタを利用して算出する方法を説明する。
【０１１２】
図８は、図３（ｃ）の例に、動作記述で利用されるある演算ｆ（ｆｕｎｃｔｉｏｎ）の数を示したものである。例えば、演算ノードｃの上に２個と書いてあるが、この位置にある演算ｆが２つ存在することを示している。他のノードも同様であり、演算の数を示す数字が付されていないノードには、演算ｆは存在しないことを示す。
【０１１３】
条件ｃ１、ｃ２、ｃ３のすべてが確定しているある制御ステップに、図８のｃ：２個、ｄ：１個、ｅ：２個、ｆ；１個、ｇ；３個の演算ｆが、スケジューリングされた場合、演算ｆを割り当てる演算器はいくつ必要であるかを計算する手法を以下に説明する。
【０１１４】
ｃとｄ、ｅ、ｆ、ｇは排他であるが、ｄとｅ、ｆは排他ではない等を考慮して、最低限必要な演算器の数を求める必要がある。条件ベクタを用いることで、この計算を、容易、かつ、効率的に求めることができる。
【０１１５】
基本的には、まず、ある演算ｆのすべてのノードの条件ベクタのベクトル和を求める。和ベクトルは、各リーフ条件毎に必要な演算器数を表しているから、その最大成分が必要最低数の演算器数を示すことになる。
【０１１６】
図８（ｂ）に、和ベクタの計算状況を示した。例えばｃが２個であるので、ｃ：［１，０，０，０］が２つで、ベクタは、［２，０，０，０］となる。
【０１１７】
さらに、ｃ：２個、ｄ：１個、ｅ：２個、ｆ：１個、ｇ：３個のベクタをすべてベクタ加算すると、［２，３，２，３］となる。
【０１１８】
つまり、リーフ条件ｅとｇで、演算ｆが３個必要で、リーフ条件ｃ、ｆで演算ｆが２個必要なことを示す。従って、最低３個用意すればよいことがわかる。
【０１１９】
＜ＦＵＶ＞
ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタを、ＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）と呼ぶ。図８の例は、基本条件ベクタＢＣＶであるが、ＦＵＶを用いた必要な演算器数の算出方法は、動的条件ベクタＡＣＶを用いた場合でも、全く同様に扱うことができる。
【０１２０】
従って、投棄実行の場合でも、必要演算器数は、ＦＵＶを同様に求めるだけで算出が可能である。
【０１２１】
なお、ＦＵＶは演算器だけでなく、変数の割り付け先としてのレジスタや、配列の割り付け先としてのメモリ、入出力変数の割り付け先としての入出力ポートでも同様に定義され、利用される。これらのＦＵＶの成分の最大値を求めることで、レジスタやメモリ、入出力ポートの最大値も算出が可能である。
＜ＦＵＶの定義＞：
ＦＵＶ（ｆ）（ｉ）  ＝  ΣＡＣＶ（ｆ）（ｉ）    
【０１２２】
ただし、ＦＵＶ（ｆ）は、ある制御ステップｉで、演算器ｆに割り付けられる演算ノードのＦＵＶである。ＡＣＶ（ｆ）は、ある制御ステップｉにスケジューリングされた演算ノードのＡＣＶである。
【０１２３】
＜ＦＵＶａｌｌ＞
特に、ある制御ステップｉにスケジューリングされたすべてのＣＤＦＧの演算ノードのＡＣＶのベクトル和を、ＦＵＶａｌｌ（ｉ）と表記する。
【０１２４】
ＦＵＶａｌｌは、スケジューリングされた回路の制御論理（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）を生成する際等に利用される。その詳細は、制御論理生成（図１０参照）に関連して説明される。
【０１２５】
必要最低限の演算器数は、以下のように算出される：  
【０１２６】
「演算器ｆの必要演算器数」  ＝  ＦＵＶ（ｆ）（ｉ）の成分の最大値
【０１２７】
各制御ステップにおいて、ＦＵＶ（ｆ）の成分の最大値が、その制御ステップで必要な演算数の最大値。全制御ステップの中で、その最大値を求めれば、全体での必要演算器数となる。
【０１２８】
＜演算ノード分割と演算器使用ベクタ・必要な制御サイクル数＞
図１に様々な投機実行の例を示したが、図１（ｂ）から図１（ｄ）の投機実行（ｏｕｔ−ｏｆ−ｏｒｄｅｒ実行）については、動的条件ベクタＡＣＶで表現できる。
【０１２９】
しかし、図１（ｅ）の”Ｄｕｐｌｉｃａｔｉｏｎ−ｕｐ”は、ＡＣＶの表現だけでは実現できない。
【０１３０】
また、図１（ｂ）の”Ｐｕｓｈ−ｄｏｗｎ”も、この場合は、演算（１）がＥＬＳＥ節に入るだけだったので、ＡＣＶで実現できたが、もし、ＴＨＥＮ節とＥＬＳＥ節の両方にコピーされて入る場合（Ｄｕｐｌｉｃａｔｉｏｎ−ｄｏｗｎ）は、やはりＡＣＶでは実現できない。
【０１３１】
そこで、このＤｕｐｌｉｃａｔｉｏｎ−ｕｐ、Ｄｕｐｌｉｃａｔｉｏｎ−ｄｏｗｎに相当する部分は、条件ベクタの性質を利用したスケジューリング手法で対応する。
【０１３２】
条件ベクタの”１”の成分の数が２以上の演算は、もとの動作を変更することなく、二
つ以上の演算ノードに分割が可能である。
【０１３３】
例えば、条件ベクタ［１，１，０，１］は、
［１，０，０，０］と［０，１，０，１］、または、
［１，０，０，０］と［０，１，０，０］と［０，０，０，１］
などのように分解できる。
【０１３４】
この分解は、そのまま、Ｄｕｐｌｉｃａｔｉｏｎ−ｕｐ、Ｄｕｐｌｉｃａｔｉｏｎ−ｄｏｗｎを意味している。
【０１３５】
例えば、［１，０，０，０］等、ベクタの”１”の成分が１つしかないノードに分割した場合は、リーフノードに分割したことに対応している。
【０１３６】
また［１，１，０，０］と分解すれば、リーフノードより上の階層にノード分割したことに対応する。
【０１３７】
スケジューリングに先立って、このノード分割をしてしまうと、スケジューリング時にＣＤＦＧの演算ノードをコードモーションしないという主義にやや反することになるが、スケジューリングアルゴリズムでは、このノード分割を「仮想的」に行い、条件ベクタの１の成分毎に、最適なスケジューリングを行い、有利と判断した場合だけ、ノード分割を行う。
【０１３８】
ノード分割は、条件ベクタの”１”の成分毎に、異なった制御ステップに、スケジューリングできることになるから、各パスに応じたスケジューリングが可能となり、すべてのパスの高速化を図ることができる。
【０１３９】
図９に、ノード分割と、それを利用したスケジューリングの例を示す。
【０１４０】
図９（ａ）の動作記述：
ｉｆ  （ｃ１）  ｘ＝ａ＋ｂ−ｃ＋ｄ；
ｅｌｓｅ  ｉｆ  （ｃ２）  ｘ＝ｙ＋ｚ＋ｕ−ｖ；
ｓ＝ｓ＋５；／＊ｎ１＊／
の最後の行ｓ＝ｓ＋５；の加算（ｎ１）を、上の３分岐の条件分岐に分割する例を、図９（ｃ）に示す。
【０１４１】
図９（ａ）の加算ｓ＝ｓ＋５；（ｎ１）は、分岐外にあるため、常に実行され、条件ベクタは［１］である（ただし、［１］は全ての成分が１のベクタ）。
【０１４２】
加算演算（ｎ１）を、３分岐の条件分岐に分割する。即ち、［１，０，０］，［０，１，０］，［０，０，１］の３つのノードに分割する。
【０１４３】
図９（ｂ）は、図９（ａ）の動作記述を、加算器１個，減算器１個の制約の下でスケジューリングした結果である。Ｓ１からＳ３の制御ステップで、加算器を１つ使用してしまうので、加算（ｎ１）は、制御ステップＳ４に割り当てるほかない。
【０１４４】
加算ｎ１のＡＣＶベクタ［１，１，１］は、制御ステップＳ１からＳ３のどの制御ステップにおいても、加算器のＦＵＶ＋（演算器利用度ベクタ）の最大成分が「２」となってしまうためである。なお、ＦＵＶ＋の「＋」は加算器のＦＵＶであることを示す。
【０１４５】
ところが、図９（ｃ）のように、３つのノードに分割すると、加算に対する演算器使用度ベクタＦＵＶ＋の”０”の成分（加算を実行しない条件）のある制御サイクルに、ばらばらにスケジューリングすることにより、ＦＵＶ＋の最大成分を”１”に保ったまま、制御ステップＳ１からＳ３に割り当てられる。３つの分割ノード（ACVはそれぞれ［０，０，１］、［１，０，０］、［０，１，０］）は、制御ステップＳ１からＳ３に割り当てられ、それぞれのＦＵＶ＋は、［１，１，１］、［１，０，０］、［１，１，０］となる。３つの制御ステップＳ１、Ｓ２、Ｓ３にスケジューリング可能となる。
【０１４６】
すなわち、動作記述の上の分岐において、すべての状態ですべての条件で加算器が利用されているわけではなく、図９（ｃ）に示したように、ある状態のある条件で利用していない部分を利用してスケジューリングすることで、実行サイクル数を削減できたわけである。
【０１４７】
ＦＵＶは、条件毎に必要な演算器数を示しているため、この例のような条件毎のスケジューリングの最適化を行い易い。
【０１４８】
図９（ｂ）、図９（ｃ）の右端のＦＵＶａｌｌは、その制御ステップにスケジューリングされたすべての演算ノードのＡＣＶの総ベクタ和である。
【０１４９】
例えば、図９（ｂ）の制御ステップＳ２では、［１，０，０］の減算と、［０，１，０］の加算があることから、ＦＵＶａｌｌ（Ｓ２）は、
これらのベクタ和［１，０，０］＋［０，１，０］で与えられ、
ＦＵＶａｌｌ（Ｓ２）＝［１，１，０］
となる。他も同様である。
【０１５０】
ここで、ＦＵＶａｌｌの成分が”０”の意味を考える。ＦＵＶａｌｌではすべての演算の条件ベクタを積算しているから、例えば、この制御ステップＳ２で、”０”の成分のリーフ条件では、演算が何も行われないことを示している。即ち、そのリーフ条件で、その制御ステップはスキップしてよいことを示している。
【０１５１】
よって、ＦＵＶａｌｌの非零成分の数を、すべての制御ステップに対して加算したベクタであるパス長ベクタは、条件ベクタのリーフ条件毎の必要ステップ数を示すことになる。
【０１５２】
パス長ベクタは、図９（ｂ）では、［４，４，１］、図９（ｃ）では、［３，３，１］である。
【０１５３】
これは、図９（ｂ）では、リーフ条件毎に、それぞれ４サイクル、４サイクル、１サイクル必要であったところ、図９（ｃ）では、３サイクル、３サイクル、１サイクルに削減したことを示している。
【０１５４】
あるスケジューリング結果から得られたＦＵＶａｌｌから、ＦＵＶａｌｌの零成分をスキップして、制御回路のＦＳＭ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ）の状態遷移（Ｓｔａｔｅ  Ｔｒａｎｓｉｔｉｏｎ）を生成する例を。図１０に示す。図１０（ａ）はスケジューリング結果に対するＦＵＶａｌｌ、（ｂ）は生成される制御用ＦＳＭの状態遷移を示す図である。
【０１５５】
単一の（ネストした）条件分岐に対する制御論理生成アルゴリズムは、以下のステップ１）から５）よりなる。
【０１５６】
１）第１制御ステップを第１状態とする。
【０１５７】
２）  Ｃｕｒｒｅｎｔ＿Ｓｔｅｐ＝第１状態
【０１５８】
３）  Ｃｕｒｒｅｎｔ＿Ｓｔｅｐの条件ベクタの各リーフ条件毎に”０”以外のＦＵＶａｌｌ成分が見つかる制御ステップをみつけ、ｎｅｘｔ＿ｓｔｅｐへ入れる。Ｃｕｒｒｅｎｔ＿ｓｔｅｐから各リーフ条件毎の次状態が求まる。
【０１５９】
４）  ｃｕｒｒｅｎｔ＿ｓｔｅｐ＝ｃｕｒｒｅｎｔ＿ｓｔｅｐ＋１；
５）もし、ｃｕｒｒｅｎｔ＿ｓｔｅｐが最後のステップならば終了する、最後のステップでなければ、ステップ３）へ移行する。
【０１６０】
図１０の例では、初期状態をＳ１とする。また、条件ベクタの各リーフ条件を順に、ｃ１、ｃ、２、ｃ３と表記する。
【０１６１】
初期状態Ｓ１（ＦＵＶａｌｌは［１，２，３］）の次状態遷移先は、条件ベクタのビットの順番にＳ２、Ｓ４、Ｓ３である。
【０１６２】
状態Ｓ２からの遷移先は、状態Ｓ３のみである。
【０１６３】
状態Ｓ３からは、条件ｃ１、ｃ３ともに状態Ｓ４への遷移である。よって、以下の状態遷移が得られる。
【０１６４】
ｓｗｉｔｃｈ  （ＳＴ）  ｛  
ｃａｓｅ  Ｓ１：  ｉｆ  （ｃ１）  ｇｏｔｏ  Ｓ２；
ｉｆ  （ｃ２）  ｇｏｔｏ  Ｓ４；
ｉｆ  （ｃ３）  ｇｏｔｏ  Ｓ３；
ｃａｓｅ  Ｓ２  ：  ｇｏｔｏ  Ｓ３；
ｃａｓｅ  Ｓ３  ：  ｇｏｔｏ  Ｓ４
ｃａｓｅ  Ｓ４：  終了して、次の条件文へ
｝  
【０１６５】
ただし、ここで、
ＳＴは状態レジスタを示しており、ｇｏｔｏ  Ｓ２は、Ｓ２へ遷移を示す。
【０１６６】
この例は、１つのトップレベルの条件分岐に対する制御論理生成方法を示している（後に述べるように、本発明は、複数のトップレベル条件分岐を並列化する手法を提案している）。
【０１６７】
なお、ＦＵＶ、ＦＵＶａｌｌについては、非特許文献１等の記載も参照される。
【０１６８】
【特許文献１】特開平５−３３４４６６号公報
【特許文献２】特開平５−３３４３９１号公報
【非特許文献１】Kazutoshi Wakabayashi and Hiroshi Tanaka, " Global Scheduling Independent of Control Dependencies based on Condition Vectors," Proc. of 29th ACM/IEEE Design Automation Conference,  pp112-115, 1992, 6
【発明の開示】
【発明が解決しようとする課題】
【０１６９】
上記したように、ＦＵＶやＦＵＶａｌｌをみるだけで、様々な投機実行を行った場合でも演算器数や各パスの実行サイクル数がすぐに計算できるため、全体のサイクルが削減できる見通しをもった状態で、効率的な計算量で、スケジューリングが行える。この点も条件ベクタの重要な特徴の１つである。
【０１７０】
トップレベルのＩＦ文を並列化させない場合、すべての演算のＡＣＶの和ベクタＦＵＶａｌｌの０成分をスキップすることだけで、最適な状態遷移を生成することができる。このように、条件ベクタは、条件多重相互排他と投機を扱うことができるが、ネストした条件分岐には２つの制限がある。
【０１７１】
ネストした条件分岐における条件節演算の投機実行に関する制約である。
【０１７２】
ネストした条件分岐における並列分岐の条件相互排他性の正確な表現が行えないことである。
【０１７３】
したがって、本発明の目的は、上記課題を確定するための自動合成装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【０１７４】
本願で開示される発明は、前記課題を解決するため、概略以下の構成とされる。
【０１７５】
本発明に係る装置は、動作記述のノードに対して条件ベクタ（Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を作成する手段を備え、前記条件ベクタを作成する手段は、前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
前記動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリングを行うスケジュール手段を備えている。
【０１７６】
本発明に係る装置において、前記スケジュール手段は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う。
【０１７７】
本発明に係る装置において、前記条件ベクタを作成する手段は、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める。
【０１７８】
本発明に係る装置において、前記条件ベクタを作成する手段は、条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）を割付け、
親のノードの基本条件ベクタ（ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる。
【０１７９】
本発明に係る装置において、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める。
【０１８０】
本発明に係る装置において、前記スケジュール手段は、演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する。本発明に係る装置において、前記スケジュール手段は、ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする。本発明に係る装置において、前記スケジュール手段は、一般化条件ベクタ（ＧＣＶ）における、演算の排他性の判定は、有効ビット以外の成分は０とみなす。本発明に係る装置において、前記スケジュール手段は、有効ビット位置が重ならない場合には、同一位置に１が重ならないか否かで排他をチェックする。
【０１８１】
本発明に係る装置において、前記条件ベクタを作成する手段は、条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し、
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す、
ことを特徴とする。
【０１８２】
本発明に係る装置において、前記スケジュール手段は、一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し、
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ、
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し、
有効ビット以外の成分は０として、ベクトル加算し、
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする。
【０１８３】
本発明に係る装置において、前記スケジュール手段は、動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされる。
【０１８４】
本発明に係る装置において、前記スケジュール手段は、動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする。
【０１８５】
本発明に係る装置において、前記スケジュール手段は、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、及び/又は、パス長に関して、基本ブロックを超えた大局的な最適化を行う。
【０１８６】
本発明に係る装置において、前記スケジュール手段において、前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離（最大距離、確率距離）に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う。
【０１８７】
本発明に係る装置において、前記スケジュール手段は、条件分岐を並列化した場合の、制御論理の生成にあたり、有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する。
【０１８８】
本発明に係る装置において、前記スケジュール手段は、有効ビット同士が重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、複数の同期する状態遷移を融合して１つのＦＳＭ（有限状態機械）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める。
【０１８９】
本発明の他のアスペクトに係る方法は、動作記述のノードに対して条件ベクタを作成する工程を含み、前記条件ベクタを作成する工程は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリング処理を行うスケジュール工程を含む。
【０１９０】
本発明に係る方法において、前記スケジュール工程は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う。
【０１９１】
本発明に係る方法において、前記条件ベクタを作成する工程は、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める。
【０１９２】
本発明に係る方法において、条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）を割付け、
親のノードの基本条件ベクタ（ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる。
【０１９３】
本発明に係る方法において、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める。
【０１９４】
本発明に係る方法において、演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する。ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする。
【０１９５】
本発明に係る方法において、条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し、
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す。
【０１９６】
本発明に係る方法において、一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し、
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ、
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し、
有効ビット以外の成分は０として、ベクトル加算し、
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする。
【０１９７】
本発明に係る方法において、動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされる。
【０１９８】
本発明に係る方法において、動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする。
【０１９９】
本発明に係る方法において、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う。
【０２００】
本発明に係る方法において、前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う。
【０２０１】
本発明に係る方法において、条件分岐を並列化した場合の、制御論理の生成にあたり、
有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する。
【０２０２】
本発明に係る方法において、有効ビット同士が重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、複数の同期する状態遷移を融合して１つのＦＳＭ（有限状態機械）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める。
【０２０３】
本発明の他のアスペクトに係るコンピュータプログラムは、動作記述のノードに対して条件ベクタを作成する処理を含み、前記条件ベクタを作成する処理は、
前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含むスケジューリングを行うスケジュール処理を、コンピュータに実行させるプログラムよりなる。
【０２０４】
本発明に係るコンピュータプログラムにおいて、前記スケジュール処理は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を行う。
【０２０５】
本発明に係るコンピュータプログラムにおいて、前記条件ベクタを作成する工程は、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める。
【０２０６】
本発明に係るコンピュータプログラムにおいて、条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（ＢＣＶ）を割付け、親のノードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｔｒｏｌ  ｖｅｃｔｏｒ；ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる。
【０２０７】
本発明に係るコンピュータプログラムにおいて、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める。
【０２０８】
本発明に係るコンピュータプログラムにおいて、条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化する処理；
内側の条件演算ｃｉから外側の条件演算へ以下の処理、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す、プログラムよりなる。
【０２０９】
本発明に係るコンピュータプログラムにおいて、一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し、
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ、
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し、
有効ビット以外の成分は０として、ベクトル加算し、
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする、プログラムよりなる。
【０２１０】
本発明に係るコンピュータプログラムにおいて、動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされる。
【０２１１】
本発明に係るコンピュータプログラムにおいて、動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする。
【０２１２】
本発明に係るコンピュータプログラムにおいて、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う。
【０２１３】
本発明に係るコンピュータプログラムにおいて、前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う。
【０２１４】
本発明に係るコンピュータプログラムにおいて、条件分岐を並列化した場合の、制御論理の生成にあたり、
有効ビットが重なっているもの毎に一般化ベクタ（ＧＣＶ）に関するＦＵＶａｌｌを求め（ただし、ある制御ステップにスケジューリングされたすべての制御データフローグラフの演算ノードの動的条件ベクタ（Ａｃｔｉｖｅ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＡＣＶ）のベクトル和であるＦＵＶａｌｌ（ただし、演算ノードｎに対する動的条件ベクタＡＣＶは、 ECV(n) or ECV(Ci) or ECV (Cj) or・・・or ECV(Ck) で与えられる。ただし、Ci、Cj、・・・Ckは、ノードnの属する条件分岐文の条件節の最終ノードであって、ＡＣＶを求めるその制御ステップで未確定なものである）
条件分岐のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成する。
【０２１５】
本発明に係るコンピュータプログラムにおいて、有効ビットの重ならない一般化ベクタ（ＧＣＶ）のノードの状態遷移は、並列な条件分岐文として扱い、
複数の同期する状態遷移を融合して１つのＦＳＭ（有限状態機械）にするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求める。
【０２１６】
本発明の他のアスペクトに係る装置は、ソース文を入力し複数の演算資源を用いて演算を並列実行可能なプロセッサ向けのコードを生成するコンパイラ装置であって、
動作記述のノードに対して条件ベクタを作成する手段を備え、
前記条件ベクタを作成する手段は、前記動作記述における一の演算ノードに対して、前記一の演算ノードが属する外側の条件演算が未確定であり、且つ、内側の条件演算が確定している場合に、ベクタの一部の連続部分に設定され、前記内側の確定した条件演算の拡張条件ベクタ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＥＣＶ）の成分が１である位置のビットである、有効ビット（Ｖａｌｉｄ  Ｂｉｔｓ）を含む一般化条件ベクタ（Ｇｅｒｅｒａｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＧＣＶ）を生成し、
前記動作記述に対応する制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）に基づき、演算のサイクルへの割付処理を含む最適化を行うスケジュール手段を備えている。
【０２１７】
本発明に係るコンパイラ装置において、前記スケジュール手段は、条件分岐における条件節演算の投機実行、及び／又は、複数条件文の並列化を含む最適化を行う。
【０２１８】
本発明に係るコンパイラ装置において、前記条件ベクタを作成する手段は、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）と、前記一の演算ノードが属する外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）とのビット論理和を、前記内側の決定済みの条件の有効ビットの成分１でマスクして行うことで、一般化条件ベクタ（ＧＣＶ）を求める。
【０２１９】
本発明に係るコンパイラ装置において、前記条件ベクタを作成する手段は、条件分岐の葉ノードに、次元数が葉の数に等しく、１つの成分にのみ１を有し、互いに１次独立のコードの基本条件ベクタ（ＢＣＶ）を割付け、親のノードの基本条件ベクタ（Ｂａｓｉｃ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ；ＢＣＶ）は、子供のノードの基本条件ベクタ（ＢＣＶ）のビット論理和で与えられ、
拡張条件ベクタ（ＥＣＶ）は、次元数が葉の数に等しく、前記制御データフローグラフのジョインノードの直前のノードの拡張条件ベクタ（ＥＣＶ）は、前記ジョインノードの直前のノードの基本条件ベクタ（ＢＣＶ）で与えられ、他の演算ノードの拡張条件ベクタ（ＥＣＶ）は、データフローの後続の演算の拡張条件ベクタ（ＥＣＶ）のビット論理和で求められる。
【０２２０】
本発明に係るコンパイラ装置において、動作記述における一の演算ノードの拡張条件ベクタ（ＥＣＶ）をＥＣＶ（演算ノード）、
前記外側の未決定の条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（外側の未決定の条件）、
前記内側の決定済みの条件演算の拡張条件ベクタ（ＥＣＶ）をＥＣＶ（内側の決定済みの条件）としたとき、
ＥＣＶ（演算ノード）｜｛（〜ＥＣＶ（内側の決定済みの条件））＆ＥＣＶ（外側の未決定の条件）｝
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）にて、前記一の演算ノードの一般化条件ベクタ（ＧＣＶ）を求める。
【０２２１】
本発明に係るコンパイラ装置において、前記スケジュール手段は、演算ノード間での演算器のシェア可能性の有無を、対応する有効ビットの同一成分に１を持たないか否かで判定する。前記スケジュール手段は、ノードの有効ビット間の同一ビット位置に１を持たない場合に、排他とし、同一ビット位置に１を持つ場合、非排他とする。前記スケジュール手段は、一般化条件ベクタ（ＧＣＶ）における、演算の排他性の判定は、有効ビット以外の成分は０とみなす。前記スケジュール手段は、有効ビット位置が重ならない場合には、同一位置に１が重ならないか否かで排他をチェックする。
【０２２２】
本発明に係るコンパイラ装置において、前記条件ベクタを作成する手段は、条件演算の投機実行時の一般化条件ベクトル（ＧＣＶ）を求めるにあたり、
前記ビット論理和においてマスクを行うガードベクタの成分を０に初期化し、
次に、内側の条件演算ｃｉから外側の条件演算へのループ処理として、
演算ノードｎの拡張条件ベクタＥＣＶ（ｎ）を、演算ノードの一般化ベクタＧＣＶ（ｎ）に代入する；
条件演算ｃｉ（ｃｉはノードｎが属している条件分岐の自分より上位の条件）が確定している場合、条件演算ｃｉの拡張条件ベクタＥＣＶ（ｃｉ）をガードベクタとして有効ビットをセットする；
条件演算ｃｉが未確定の場合
ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））をＧＣＶ（ｎ）とする
（ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す）；
を繰り返す。
【０２２３】
本発明に係るコンパイラ装置において、前記スケジュール手段は、一般化ベクタ（ＧＣＶ）を用いて、ある演算器に割り当てられるすべての演算ノードの条件ベクタの和ベクタであるＦＵＶ（Ｆｕｎｃｔｉｏｎ  ｕｎｉｔ  Ｕｔｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ）を求めるにあたり、
有効ビットが互いに重なる一般化ベクタ（ＧＣＶ）の集合Ｓを作成し、
有効ビットの無いものはすべて１つの集合Ｓ０にまとめ、
上記集合Ｓのそれぞれについて以下の｛｝の処理、
｛集合Ｓの中のＧＣＶについて、
ＦＵＶ（ｓ）とＧＣＶのベクタ加算結果をＦＵＶ（ｓ）とする、
処理を繰り返し｝
を繰り返し、
ＦＵＶを、すべてのＳとＳ０のＦＵＶを通常のベクタ加算し、
有効ビット以外の成分は０として、ベクトル加算し、
加算後、有効ビットの中で最大の成分の値を有効ビット部分以外にセットする。
【０２２４】
本発明に係るコンパイラ装置において、前記スケジュール手段は、
動作記述において分岐内に並列配置された、少なくとも第１、第２の条件文を、
前記第１、第２の条件文の前に、投機実行され、条件演算が未確定の条件節の分岐に、それぞれ前記第１、第２の条件文を置いた制御構造と同一の制御構造として扱い、
分岐内の並列条件文と、条件節の投機実行とが、有効ビットを持つ一般化ベクタ（ＧＣＶ）により統一的に表現自在とされる。
【０２２５】
本発明に係るコンパイラ装置において、前記スケジュール手段は、動作記述においてトップレベルに並んだ複数の条件分岐文に対して、異なるトップレベルの条件分岐に属する演算が仮想的に統一的な一般化条件ベクタ（ＧＣＶ）を有するものとして扱い、スケジューリング時に、前記異なるトップレベルの条件分岐に属する演算を、１つの基本ブロックにある演算のように扱い、前記異なるトップレベルの条件分岐に属する演算ノードを任意の順にスケジューリングする。
【０２２６】
本発明に係るコンパイラ装置において、前記スケジュール手段は、前記制御データフローグラフの演算ノードに付与された一般化条件ベクタ（ＧＣＶ）を利用して、投機実行、パス長に関して、基本ブロックを超えた大局的な最適化を行う。
【０２２７】
本発明に係るコンパイラ装置において、前記スケジュール手段において、前記一般化条件ベクタ（ＧＣＶ）を利用し、複数の条件分岐の間の演算間でも、距離に関する所定のプライオリィティ関数に基づき、スケジュール自在とされ、複数の条件分岐を並列化する大局的な投機実行を行う。
【発明の効果】
【０２２８】
本発明によれば、あらゆるタイプの条件分岐に関係する投機実行を表現可能な一般化条件ベクタを導入したことにより、ネストした条件分岐における条件節演算の投機実行を行うことができる。
【０２２９】
本発明によれば、ネストした条件分岐における並列分岐の条件相互排他性の正確な表現が可能である。
【０２３０】
本発明によれば、一般化された条件ベクタＧＣＶを基に、前述した複数の条件分岐分の並列化を行うにあたり、複数の条件分岐の間の演算間でも、必要演算器数は算出可能となるから、属する条件分岐は気にせずに、プライオリィティ関数の大きい順にスケジュール可能となり、あらゆる意味で、条件分岐の制御依存関係は取り払われ、データ依存関係だけで並列化することが可能となる。かかる本発明によれば、スケジューラから見た場合、ＧＣＶを付与された演算ノードが、あたかもすべて基本ブロックの中にあるように扱ってよく、基本ブロック向けに開発された様々な（局所的）スケジューリングアルゴリズムを、大局的スケジューリングに応用可能となる。
【発明を実施するための最良の形態】
【０２３１】
以下、本発明を実施するための最良の形態、及び具体的な実施例を以下に説明する。
【０２３２】
＜一般化条件ベクタ＞
条件ベクタＡＣＶは、データ依存による暗黙的な排他性、投機実行における動的排他性を考慮できるが、ベクタでネストした条件分岐を表現する際の限界として、２つのケースの扱いに問題があった。
【０２３３】
１つは、ネストした条件分岐における複数の条件節演算の間の投機実行の扱いである。いままで、分岐のＴＨＥＮ節やＥＬＳＥ節の演算が条件分岐演算より先にスケジューリングされるような投機実行を主に考慮していた。
【０２３４】
（A）しかし、ネストした条件分岐の内側の条件分岐演算が、外側の条件分岐演算よりも先にスケジューリングされるような投機実行を行う際の演算間の排他性の正確に表現できない。
【０２３５】
（B）ネストした条件文のある分岐の中に、複数の条件文が逐次に（並列に）並ぶ場合を陽に表現できない。
【０２３６】
そこで、本発明は、ＡＣＶのこれらの課題を解決し、あらゆるタイプの条件分岐に関係する投機実行を表現可能な、一般化条件ベクタ（Ｇｅｎｅｒａｌｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ：  ＧＣＶ）を導入する。
【０２３７】
＜ネストした条件分岐文の内側の条件演算のＯｕｔ−ｏｆ−ｏｒｄｅｒ実行＞
ネストした条件分岐文の条件分岐演算のＯｕｔ−ｏｆ−ｏｒｄｅｒ実行と、その条件ベクタでの表現について、図１１を用いて説明する。なお、図１１では、ベクタの成分間のカンマを省略して表現している。例えば、［１，０，０］を［１００］と表現している。以後、スペースの関係で、誤解の無い場合は、図の中のベクタのカンマを省略することがある。
【０２３８】
図１１の１）の動作記述の条件演算（ａ＊ｂ＜ｃ））／＊ｃ１＊／、（ｂ＞ｃ））／＊ｃ２＊／のみをスケジューリングした結果を、図１１の２）と３）に示す。
【０２３９】
図１１の２）は動作記述順通り（Ｉｎ−ｏｒｄｅｒ）実行である。
【０２４０】
図１１の３）は、内側の条件演算（ｂ＞ｃ）／＊ｃ２＊／が、外側の条件演算（ａ＊ｂ＜ｃ）／＊ｃ１＊／よりも先に決定してしいる（Ｏｕｔ−ｏｆ−ｏｒｄｅｒ）。この場合、制御ステップ３の位置では、内側の条件ｃ２は確定しているが、外側の条件ｃ１が未確定である。動的条件ベクタＡＣＶでは、条件演算がこのような場合に、分岐の演算の排他性を完全には表現できない。
【０２４１】
図１１の１）に制御ステップ１、２、３それぞれにおけるＡＣＶとＧＣＶを示す。
【０２４２】
制御ステップ１は、すべての条件（ｃ１、ｃ２）が確定している。
【０２４３】
制御ステップ２では、外側の条件ｃ１が確定し、内側の条件ｃ２だけが未確定である。
【０２４４】
これらのＡＣＶは、図１１の１）に示す通りであり、厳密に条件排他性を示している。例えば、ｃ１が確定、ｃ２が未確定な場合、３行目の演算［１，０，０］と５行目の演算［０，１，１］とは、ｃ１が確定しているため排他判定可能で、ベクタもその排他性を正しく表現している。
【０２４５】
逆に、５行目と６行目の加算は、動作記述上は排他であるが、条件ｃ２が未確定なので条件排他ではない。
【０２４６】
ＡＣＶは両演算とも、［０，１，１］と［０，１，１］となり、条件排他で無いことを正しく表現できている。もちろん、必要演算器数も正しく表現できている。
【０２４７】
一方、制御ステップ３の条件では、ＡＣＶは、図１１に示すようにすべて、［１，１，１］になってしまう。
【０２４８】
ＡＣＶの計算では、関連する条件演算の中で未確定な条件演算のＥＣＶとのビット論理和をとるため、この場合は、ｃ１のＥＣＶである［１，１，１］とのビット論理和ですべて［１，１，１］になってしまう。
【０２４９】
つまり、内側の条件演算ｃ２が確定している状態を表現できていない。
【０２５０】
すなわち、外側の条件ｃ１が未確定なため、３行目の演算と５行目（または６行目）の演算は、条件排他性がない（演算器の共用できない）が、ｃ２が確定しているため、５行目と６行目の演算は条件排他である。
【０２５１】
このように、ＡＣＶは、外側の条件が未確定な場合に、内側の条件分岐の確定性を十分に表現できていない。
【０２５２】
この問題を解決するために、本発明は、全く新規な概念である一般化条件ベクタ（Ｇｅｎｅｒａｌｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ：  ＧＣＶ）を導入する。
【０２５３】
ＧＣＶは、単純なベクタ表現でなく、ベクタの一部の連続成分に、「有効ビット（ｖａｌｉｄ  ｂｉｔｓ）」を持つ。
【０２５４】
図１１の１）では、有効ビットに下線を付した。
【０２５５】
有効ビットは、外側の条件演算が未確定で、内側の条件演算が確定した場合に設定され、その設定部分は、内側の確定した条件演算のＥＣＶの成分が”１”である位置のビットである。
【０２５６】
この例では、内側の条件ｃ２（ｉｆ（ｂ＞ｃ））のＥＣＶが［０，１，１］であり、成分が”１”の部分、すなわち第２〜第３ビットが、有効ビットである。
【０２５７】
条件演算のＥＣＶ（ＢＣＶと同一）の”１”成分は、定義より、必ず連続して一カ所にあるから有効ビットも連続した一カ所の範囲である。そして、有効ビットを持つ条件ベクタを、「ＧＣＶ」と呼ぶ。
【０２５８】
ＧＣＶでは、演算の条件排他性の判定は、有効ビット間で同一成分に”１”を持たなければ排他と判定できる。有効ビット以外は、０と考えて排他性を考えてよい。
【０２５９】
そして、ＧＣＶにおいて、有効ビットが重ならない場合には、通常の条件ベクタ同士と同じ判定でよい。
【０２６０】
ＧＣＶを用いた必要演算器数の算出方法等の詳細は後述する。
【０２６１】
ＧＣＶの厳密な条件排他性を利用した図１１の１）の動作記述を、加算器１個の制約で、スケジューリングした結果を、図１１の（ａ）、（ｂ）に示す。
【０２６２】
図１１（ａ）は、ＡＣＶを利用したスケジューリング結果、図１１（ｂ）は、ＧＣＶを利用したスケジューリング結果である。
【０２６３】
図１１（ａ）、図１１（ｂ）とも、制御ステップＳ２で、外側条件ｃ１が未確定、内側条件ｃ２が確定した状態で、ＧＣＶの有効ビットが利用される。
【０２６４】
この制御ステップのＡＣＶ、ＧＣＶは、図１１の１）の制御ステップ３の部分のＡＣＶ、ＧＣＶである。
【０２６５】
図１１（ａ）は、制御ステップＳ２でのノードｎ１（加算「ｓ＋ｕ」）（ＥＣＶは［０，１，０］）のＡＣＶが［１，１，１］となってしまうため、ほかのどの加算とも、加算器をシェアできない。
【０２６６】
一方、図１１（ｂ）のＧＣＶでは、制御ステップＳ２のノードｎ１（加算「ｓ＋ｕ」）のＧＣＶが［１，１，０］となり、ＣＤＦＧの中のノードｎ２（加算「ｘ＋ｕ」）のＧＣＶが［１，０，１］とされる。
【０２６７】
ノードｎ１のＧＣＶ［１，１，０］とノードｎ２のＧＣＶ［１，０，１］は、有効ビット間で、同一成分に、”１”を持たないことから、排他になり、１つの加算器をシェアできる。
【０２６８】
このため、加算演算（ノード）ｎ１とｎ２を、制御ステップＳ２にスケジューリングできる。
【０２６９】
よって、全体に必要なサイクル数は、図１１（ａ）、図１１（ｂ）では、それぞれ、最大４と、最大３となる。
【０２７０】
ノードｎ１とｎ２の排他性が抽出できたかどうかで、したがって、制御ステップＳ２に２つの加算演算を、１つの加算器をシェアするように割り当てられたかどうかで、必要サイクル数が異なっている。
【０２７１】
図１１の１）の元の動作記述でみると、図１１（ｂ）の制御ステップＳ２で、ｃ１未確定、ｃ２確定の状態で演算ｎ１と演算ｎ２（６行目の最初の加算「ｘ＋ｕ」）がシェアされていることになる。
【０２７２】
このようなことを考えた上で、命令移動（ネストした条件分岐における複数の条件節演算の間の投機実行）により、このような演算器のシェアをシステマティックに発見することは困難である（ＡＣＶを用いて行うことは困難である）。
【０２７３】
本発明のスケジューリングアルゴリズムは、このようなＧＣＶの排他性を、大局的に（全体への貢献を）考慮した上で、効率的にスケジューリングを行う。
【０２７４】
＜一般化条件ベクタＧＣＶの計算方法＞
次に、ネストした条件文の演算が、ｏｕｔ−ｏｆ−ｏｒｄｅｒ実行された場合のＧＣＶの計算方法について説明する。
【０２７５】
ＧＣＶは、分岐内の並列条件文も同一形式で表現できる。
【０２７６】
図１２は、ある動作記述：
ｉｆ  （ａ）  
ｉｆ  （ｂ）  
ｉｆ  （ｃ）
ｉｆ  （ｄ）            （１）
ｅｌｓｅ                （２）
ｅｌｓｅ                    （３）
ｅｌｓｅ                      （４）
ｅｌｓｅ  ｉｆ  （ｅ）          （５）
ｅｌｓｅ              （６）
に対して，一部の条件演算だけが未決定（ｕｎｒｅｓｏｌｖｅｄ）の場合のＧＣＶの値を示している。
【０２７７】
図１２において、”ａ：ｎｏｔ”は、条件”ａ”が未決定を意味する。
【０２７８】
図１２において、”ｂ：ｄｏｎｅ”は、条件”ａ”が決定済み（ｒｅｓｏｌｖｅｄ）を意味する。つまり、図１２の例では、条件ａ、ｃが未決定で、条件ｂ、ｄ、ｅが決定している。
【０２７９】
図１２において、動作記述の上の欄の、２行目の［］で示されたベクタ（ａ：ｎｏｔ，ｂ：ｄｏｎｅ，ｃ：ｎｏｔ，ｄ：ｄｏｎｅの下のベクタ）は、各条件演算のＧＣＶを示している。動作記述の上の欄の３行目の（）で示されたベクタは、各条件演算のＥＣＶを示している。
【０２８０】
条件ｅは、決定済みで、一番下の行にＥＣＶ：（００００  １１）、ＧＣＶ：［１１１１  １１］を示した。
【０２８１】
図１２の右のＥＣＶの列は、動作記述の葉（リーフ）の位置に記述された演算の持つＥＣＶを示しているが、これは、すべての条件ａ、ｂ、ｃ、ｄ、ｅが決定済みの時（条件演算が、対象演算より前の制御ステップにスケジューリングされた時）のＡＣＶ、ＧＣＶの値と等価である。
【０２８２】
一方、図１２のように、条件ａ、ｃが未決定な場合、最外郭の条件演算ａが未決定なため、すべての演算のＡＣＶは、最外郭の条件演算のＥＣＶである［１，１，１，１，１，１］とのビット論理和となり、［１，１，１，１，１，１］となる。
【０２８３】
一方、ＧＣＶは、図１２のＧＣＶの列に示したように、決定済みの条件ｂ、ｄだけで得られる排他性を正確に示すことができる。
【０２８４】
動作記述のリーフ（１）にある演算（「演算１」と呼ぶ）のＥＣＶは、（１，０，０，０，０，０）である。図１７の中でベクタの中のスペースは最外郭の条件分岐の境界を見やすくしているだけである。成分間のカンマは省略してある。
【０２８５】
この演算１のＡＣＶの値は、ＥＣＶに未決定の条件ａ、ｃのＥＣＶ（［１，１，１，１，１，１］と［１，１，１，０，０，０］）をビット論理和することにより得られるから、［１，１，１，１，１，１］となり、条件ｂ、ｄによる排他性を利用できていない。
【０２８６】
演算１のＧＣＶは、未決定の条件演算のＥＣＶとビット論理和をとるのは、ＡＣＶと同じであるが、内側の決定済みの条件のＥＣＶで、そのビット論理和演算を、マスク（ガード）する。内側の決定済み条件演算の条件ベクタを、「ガードベクタ」と呼ぶ。
【０２８７】
演算１のＧＣＶは、以下の通り、内側の条件から順に計算していく。
【０２８８】
まず、条件ｄが確定しているから、条件ｄのＥＣＶである（１，１，０，０，０，０）をガードベクタとする。
【０２８９】
次の外側の条件ｃは未決定であるから、演算１の葉（リーフ）のＥＣＶ（１，０，０，０，０，０）と、条件ｃのＥＣＶである（１，１，１，０，０，０）とのビット論理和を、条件ｄのガードベクタ（１，１，０，０，０，０）でマスク（ガード）して行い、結果は［１，０，１，０，０，０］となる。条件ｃのＥＣＶである（１，１，１，０，０，０）をガードベクタでマスクしたベクタ（０，０，１，０，０，０）と、ＥＣＶ（１，０，０，０，０，０）とのビット論理和をとり、ＧＣＶ［１，０，１，０，０，０］が得られる。これは、ベクタ間のビット演算表現として、
ＥＣＶ（演算１の葉）｜｛（〜ＥＣＶ（条件ｄ））＆ＥＣＶ（条件ｃ）｝
と表すことができる。ただし、〜、｜、＆は、ビット反転演算、ビットワイズ論理和、ビットワイズ論理積を表す。
【０２９０】
次の条件ｂは決定済みであり、その次の条件ａは、未決定であるから、同様にして、［１，０，１，０，０，０］に、ｂのガード条件（１，１，１，１，０，０）のもとで、ａのＥＣＶ（１，１，１，１，１，１）とビット論理和をとると、［１，０，１，０，１，１］となる。
【０２９１】
ガードされた部分（ガードベクタの成分が１のビット）が、有効ビットである。２回以上ガードされた場合には、最初のガード条件（短いビット長のガード条件）を有効ビットとする。
【０２９２】
ＧＣＶにおいて、有効ビットは下線を引いて示す。プログラムでの実装では、有効ビットはビット開始位置とビット幅で保持される。つまり、ＧＣＶは通常の条件ベクタ表現と、有効ビット表現の２つの構造体として保持する。例えば、［１，０，１，０，１，１］は、［１，０，１，０，１，１］というベクタ表現と、（０：２）という有効ビット表現で表される。ベクタ表現は、プロセッサの通常のワードで表現でき、ビット論理和、ビット論理積などが一クロック命令で実行できるため、高速に処理可能である。
【０２９３】
演算1 のGCV の計算：
GCV ＝ ECV（演算１）|(~ECV（条件d） & ECV(c)) | (~ECV(b) & ECV(a)) 
= (1000 00) | (~(1100 00) & (1110 00)) | (~(1111 00) & (1111 11)) 
= [1010 11] 
【０２９４】
ただし、
ＥＣＶ（ｘ）は、演算ｘのＥＣＶ、
〜は、ビット反転演算、
｜は、ビットワイズ論理和、
＆は、ビットワイズ論理積
を示す。
【０２９５】
ほかの演算も同様に計算できる。図１２の（３）の演算（演算３）のＧＣＶは、条件ｃが未確定であるから、まず、「ＥＣＶ（演算３）：（００１０  ００）｜ＥＣＶ（ｃ）：（１１１０  ００）」により、（１１１０  ００）となる。
【０２９６】
次にガード条件ｂのもとで、未確定条件ａのＥＣＶとのビット論理和を取るから、「（１１１０  ００）｜（〜ＥＣＶ（ｂ）：（１１１１  ００）  ＆ＥＣＶ（ａ）：［１１１１  １１］）」より、［１１１０  １１］となる。
【０２９７】
演算３のＧＣＶの計算には、条件ｄは無関係である。演算３よりも内側の条件分岐であり、演算３の排他性には影響がないからである。リーフ（５）の位置の演算５は、ガード条件（０００１１）でガードして、未確定条件ａとのビット論理和をとるから、［１，１，１，１，１，０］となる。
【０２９８】
＜排他性の判定＞：
ＧＣＶにおいて、条件排他性は、有効ビットが重なる場合には、有効ビットの部分だけで、従来どおりの排他性チェックを行う。即ち、
同一ビット位置に”１”がない場合が、排他、
同一ビット位置に”１”がある場合は、非排他である。
【０２９９】
有効ビットのビット長が異なる場合は、長い方のビット長で計算する。ただし、実際には、短いビット長で計算しても、排他性の判定結果は同じになる。
【０３００】
有効ビット位置が重ならない場合は、ＡＣＶと同様に同一位置に”１”が重ならないかチェックすればよい。
【０３０１】
例えば、図１２において、（１）と（３）は条件ｃが未決定（未確定）であるから、排他でない（［１０１０  １１  ］と［１１１０  １１］）。
【０３０２】
図１２の（１）と（４）はｂが決定（確定）しているから、排他である。（［１０１０  １１］と［０００１  １１］）  
【０３０３】
ＧＣＶの計算方法（条件演算のｏｕｔ−ｏｆ−ｏｒｄｅｒ実行時）は、以下の手続きで与えられる。
【０３０４】
ステップ１：
ガード条件ベクタ＝［０］；（ａｌｌ  ｃｏｍｐｏｎｅｎｔｓ  ａｒｅ  “０”）
【０３０５】
ステップ２：  以下のｆｏｒループ
ｆｏｒ  （内側の条件テスト演算ｃｉから外側の条件演算へ）  ｛
ＧＣＶ（ｎ）＝ＥＣＶ（ｎ）；
ｉｆ  （ｃｉ＝＝確定）
ガードベクタ＝ＥＣＶ（ｃｉ）；有効ビットのセット；
ｉｆ  （ｃｉ＝＝未確定）
ＧＣＶ（ｎ）＝ＧＣＶ（ｎｉ）｜（〜ガードベクタ＆ＥＣＶ（ｃｉ））；
｝  
【０３０６】
ここで、
ｎはある演算ノード、
ｃｉはノードｎが属している条件分岐の自分より上位の条件、
ＧＣＶ（ｎ）はｎのＧＣＶ、
ＥＣＶ（ｃ）はｃのＥＣＶを示す。
【０３０７】
図１３には、図１２の動作記述のリーフである（１）から（６）の位置の演算のＧＣＶを、条件演算が「未決定」と「決定」の様々な組み合わせに対して示されている。上の行の左端の列は、条件演算名とそのＥＣＶを示す。”ｄｏｎｅ”は条件が決定（確定）したことを示し、”ｎｏｔ”は条件が未決定（未確定）であることを示す。”ｇｕａｒｄ”は、決定（確定）した条件で、ガード条件（ガードベクタはそのＥＣＶである）となったことを示す。下の（１）から（６）の行は、それぞれのリーフ位置でのＧＣＶを列の条件毎に表示してある。
【０３０８】
＜必要演算器数の算出＞
ＡＣＶを用いた必要演算器数算出方法を、ＧＣＶ用に拡張する方法を説明する。ＡＣＶを用いた演算器数算出方法は、ある演算器種に割り当てられるすべての演算のＡＣＶのベクトル和ＦＵＶを求め、その最大成分を必要演算器数とすることで求められた。
【０３０９】
しかし、ＧＣＶでは、有効ビットを持つため、各成分が完全には、独立でなく、計算方法に修正が必要である。以下に、ＧＣＶを用いたＦＵＶの計算方法を示す。
【０３１０】
ＧＣＶに対するＦＵＶと演算器数の計算方法：
【０３１１】
有効ビットが重なるＧＣＶの集合Ｓを作成する。
有効ビットの無いものは、すべて１つの集合Ｓ０へ入れる。
【０３１２】
ｆｏｒ（集合Ｓのそれぞれについて）｛  
ｆｏｒ  （集合Ｓの中のＧＣＶ）｛
ＦＵＶ（ｓ）＝  ＦＵＶ（ｓ）＋ＧＣＶ；  
（ただし、＋はＧＣＶのベクタ加算）  
｝
｝
ＦＵＶ  ＝ΣＦＵＶ（すべてのＳとＳ０のＦＵＶを通常のベクタ加算）  
（ただし、ＦＵＶ（ｓ）＋ＧＣＶにおける＋は、ＧＣＶのベクタ加算を示す。）
【０３１３】
有効ビット以外の成分は”０”として、ベクトル加算する。
【０３１４】
加算後、有効ビットの中で最大の成分の値を、有効ビット部分以外にセットする。
【０３１５】
この手順を図１２の例を用いて説明する。図１２の（１）から（６）までのリーフに、それぞれ()内の数字と同じ数の加算が存在すると仮定する。つまり、リーフ（１）に加算が1 個、リーフ（２）に加算が２個、リーフ（６）に加算が６個あるとする。
【０３１６】
この場合、ＧＣＶを加算して得られるＦＵＶの値を求める。加算がそれぞれリーフ番号の数だけあるから、それぞれのリーフの中のＦＵＶは、図１２の右端の欄に示したようになる。
【０３１７】
例えば、図１２のリーフ（２）では、
［０，１，１，０，１，１］＋［０，１，１，０，１，１］
→［０，１，０，０，０，０］＋［０，１，０，０，０，０］
＝［０，２，０，０，０，０］  （有効ビット以外を０にして加算）
→［０，２，２，２，２，２］  （有効ビット以外を最大値にする）
【０３１８】
他のリーフ（１）、（３）〜（６）についても、同様に計算すると、図１２の右端のＦＵＶの列の値になる。
【０３１９】
次にこれらを加算する。有効ビットの重なる上４行（リーフ（１）〜（４）のＦＵＶ）の加算結果は、上記と同様に行うと、
［１，０，１，０，１，１］＋［０，２，２，２，２，２］＋［３，３，３，０，３，３］＋［０，０，０，０，４，４，４］
＝［４，５，３，４，５，５］
となる。
【０３２０】
もう１つの集合は、下２行（リーフ（５）、（６）のＦＵＶ）の加算結果は、
［５，５，５，５，５，０］＋［６，６，６，６，０，６］
＝［６，６，６，６，５，６］となる。
【０３２１】
最後に、有効ビットが重ならないＧＣＶの和は、通常のベクタ加算でよいから、最終的なＦＵＶ＋（加算器のＦＵＶ）は、
［４，５，３，４，５，５］＋［６，６，６，６，５，６］
＝［１０，１１，９，１０，１０，１１］
となる。
【０３２２】
よって、最大成分である１１が、このケースで必要な加算器の最小数となる。
【０３２３】
この場合、ＡＣＶを用いたＦＵＶの計算を行うと、ＡＣＶがすべて［１］になってしまうため、ＦＵＶは［２１，２１，２１，２１，２１，２１］となり、２１個の加算器が必要となる。
【０３２４】
ネストした条件分岐の一部だけが決定（確定）している場合にその条件排他性を厳密に適用することで、必要演算器数が約半数（２１対１１）に減少できたことを意味する。参考として、すべての条件分岐が確定していた場合のＦＵＶは［１，２，３，４，５，６  ］となるから、最小で６つの加算器が必要である。
【０３２５】
＜並列な条件分岐の表現＞
ＡＣＶのもう１つの表現力不足は、条件分岐の中に並列な条件分岐文が複数並ぶ場合でる。
【０３２６】
図１４（ａ）に示すように、並列ＩＦ文がない場合、全分岐が排他である。
【０３２７】
しかし、ＡＣＶでは、ネスト内の並列ＩＦ文が表現できない。例えば、ネスト内の並列ＩＦ文の動作記述：
ｉｆ  （ａ）      
ｅｌｓｅ  ｉｆ  （ｂ）
ｅｌｓｅ  
ｉｆ  （ｃ）
ｅｌｓｅ    
は、図１４(ｂ)に示すように、ＡＣＶでは、並列ＩＦ文のｉｆ  （ｃ）  ｅｌｓｅが表現できない（図１４（ｂ）の？？で示す）。
【０３２８】
そこで、図１４（ｃ）に示すように、ＩＦ文を命令移動し全リーフノードを排他とする。
【０３２９】
しかし、命令移動、分岐数の増大（計算量の増大）という問題が生じる。さらに詳細に説明する。図１５（ａ）に示すように、有効ビット（２ビット）を用いて、並列ＩＦ文を表現することができる。図１５（ｃ）、図１５（ｄ）に示すように、並列ＩＦ文は、条件ｘが未確定な場合の投機実行と等価な表現となる。図１５（ｄ）に示すように、まず、各リーフノードにワンホット符号をつける（この場合、ベクタの成分数は５）。条件ａのＴＨＥＮ節ノード（１）に［１，０，０，０，０］、条件ｂのＴＨＥＮ節ノード（２）に［０，１，０，０，０］、条件ｂのＥＬＳＥ節ノード（３）に［０，０，１，０，０］、条件ｃのＴＨＥＮ節ノード（４）に［０，０，０，１，０］、条件ｃのＥＬＳＥ節ノード（５）に［０，０，０，０，１］を割り付ける。次に、並列ＩＦ文になっている部分で、自ノードの直近の条件演算で区別がつく範囲を有効ビットとする。ノード（２）、（３）では、条件ｂで排他判定ができる、第２、第３ビットが、条件ｂによる有効ビットとなる。ノード（４）、（５）では、条件ｃで排他判定ができる、第４、第５ビットが、条件ｃによる有効ビットとなる。１と２又は３、１と６、１と｛４または５｝、２と３、４と５は排他である。２と４、２と５、６と２等は非排他である。すなわち、条件ｘが未確定な場合、条件分岐ｂ、ｃとの間の排他性はなくなる。この点について以下に詳述する。
【０３３０】
図１６（ａ）に、条件ａ（ｉｆ  （ａ））のＴＨＥＮ節の中に３つの条件文（ｂ、ｃ、ｄ）が並んだ例を示す。基本条件ベクタＢＣＶは、各リーフが互いに排他である必要がある。各リーフが排他なため、それぞれにワンホット符号を与えたときに、排他な演算は互いに同じ位置に”１”を持たない等の性質が満足される。
【０３３１】
ところが、図１５（ａ）の場合、ｉｆ（ｂ）のｔｈｅｎ節とｅｌｓｅ節は排他であるが、ｉｆ（ｂ）と、ｉｆ（ｃ）、ｉｆ（ｄ）の間にはなんらの排他関係もない。
【０３３２】
よって、ＢＣＶでこのような制御構造をもつ動作記述を表現するためには、図１６（ｂ）のように、条件分岐を、ＢＣＶで表現可能な形式（すべてのリーフが排他）に等価変換する必要がある。
【０３３３】
この変換は、ｉｆ（ｄ）を、ｉｆ（ｃ）のｔｈｅｎ節とｅｌｓｅ節の両方にそれぞれコピーし、さらに、ｉｆ（ｂ）のｔｈｅｎ節，ｅｌｓｅ節にコピーする。
【０３３４】
この変換（ツリーコピー）により、すべてのリーフが排他となり、図１６（ａ）と等価な動作記述である図１６（ｂ）が得られる。
【０３３５】
しかしながら、この方法は、変換後のリーフの数が、並列にならぶ条件分岐数の指数乗で増えていくため、ある程度以上の並列条件文があると、条件ベクタの次数が非常に大きくなり現実的ではない。また、スケジューリング対象の演算ノードが指数乗で増大するため、スケジューリング処理の計算効率が低下する。
【０３３６】
図１６（ｂ）の動作記述（ツリーコピー）のリーフのＢＣＶを、図１６（ｂ）の右端に示す。
【０３３７】
分岐数を低減するために、図１６（ｃ）のように、条件分岐を、トップレベルで分割する方法もある。
【０３３８】
図１６（ｃ）において、ＢＣＶは、トップレベルの条件文毎に定義されている。従って、図１６（ｃ）では、３つの独立なＢＣＶが記載されている。
【０３３９】
しかしながら、このツリー分割は厳密には等価変換とはいえず、スケジューリング結果のサイクル数や必要演算器数に悪影響があることもある。
【０３４０】
ＧＣＶは、これらの問題点を改良し、分岐内の並列条件文を直接表現する。興味深いことに、ネストした条件節の投機実行を示すために導入した「有効ビット」を用いて、分岐内並列条件文を表現することができる。
【０３４１】
＜分岐内並列条件文のＧＣＶ計算方法＞
図１６（ａ）の動作記述の右側に、ＧＣＶを示す。分岐内並列条件分岐文を含む動作記述へのＧＣＶの計算方法は、以下のとおりである。次元数は、ＢＣＶ同様、リーフの数である。
【０３４２】
まず、各リーフノードにワンホット符号をつける（この場合、ベクタの成分数は７）。［１００００００］から［００００００１］が条件ｂのｔｈｅｎ節から条件ａのｅｌｓｅ節に割り当てられる。
【０３４３】
次に、並列条件文になっている部分で、自ノードの直近の条件演算で区別がつく範囲を有効ビットとする。
【０３４４】
例えば、条件ｂで排他判定ができる上位２ビットが、条件ｂによる有効ビットとなる。条件ｃ、ｄによる有効ビットは、図に示すとおりである。
【０３４５】
次に、自分以外の並列条件文の有効ビットの成分をすべて”１”にする。リーフ以外の演算のＧＣＶは、自分の後続演算のＧＣＶのビット論理和である。なお、有効ビットも、後続演算の有効ビットのＯＲで得られる。
【０３４６】
より一般的な動作例と、ＧＣＶを、図１８に示す。上記に示した方法でそれぞれのＧＣＶが計算できる。ここで得られたＧＣＶは、いままで議論してきた排他性判定、必要演算器数算出方法等がすべてそのまま適用可能である。
【０３４７】
分岐内並列条件文と、条件演算のｏｕｔ−ｏｆ−ｏｒｄｅｒ実行の時のＧＣＶが同じ形式で表される。注意しなければならないことは、後者（条件演算のｏｕｔ−ｏｆ−ｏｒｄｅｒ実行）では、一部の条件演算が未確定な場合だけ有効ビットが出現したが、前者（分岐内並列条件文）の場合には、すべての条件が確定していても、有効ビットが存在する点である。
【０３４８】
分岐内並列条件文の中の一部の条件が未確定になった場合も、前記した計算方法がそのまま利用できる。
【０３４９】
例えば、図１６（ａ）で条件ｂが未確定になった場合は、条件ｂのＥＣＶ（１，１，０，０，０，０，０）とのビット論理和をとればよい。
【０３５０】
条件ａだけが未確定になった場合は、ｂ、ｃ、ｄをガード条件とすればよい。この結果、例えば、先頭のＧＣＶは［１０１１１１１］となり、最後のＧＣＶは、［１１１１１１１］となる。
【０３５１】
以上のように、分岐内並列条件文がｏｕｔ−ｏｆ−ｏｒｄｅｒ実行しても、矛盾なく、ＧＣＶの値を計算可能である。
【０３５２】
＜分岐内並列条件文と条件演算のｏｕｔ−ｏｆ−ｏｒｄｅｒ実行のＧＣＶの同一性＞
図１７（ａ）に、分岐内並列分岐文（並列ＩＦ文）のＧＣＶの一例、図１７（ｂ）に、ネストした条件分岐の条件節の投機実行において、ある条件（ｂ）が未確定の場合のＧＣＶを示す。
【０３５３】
分岐内並列分岐文は、
ｉｆ（ａ）  ｉｆ（ｃ）
ｅｌｓｅ
ｉｆ（ｄ）
ｅｌｓｅ
ｅｌｓｅ  
【０３５４】
ネストした条件分岐の条件節の投機実行の動作記述は、
ｉｆ（ａ）  ｉｆ（ｂ）  ｉｆ（ｃ）
ｅｌｓｅ
ｅｌｓｅ    ｉｆ  （ｄ）
ｅｌｓｅ
ｅｌｓｅ  
【０３５５】
図１７（ａ）と図１７（ｂ）に示すように、両者のＧＣＶが完全に一致している。これは、条件排他を考える際に、この２つは、全く同じであることを示唆している。
【０３５６】
これが正しい理由を考察する。図１７（ｂ）をみると、条件ｂが未確定であった場合、該条件ｂの後続条件文であ条件ｃと条件ｄの２つの間の条件排他性が無くなることがわかる。つまり、これら２つのＩＦ文（ｉｆ（ｃ）、ｉｆ（ｄ））は、並列に存在するのと等価になる。従って、条件ｂが未確定の場合、図１７（ａ）の分岐内並列条件文と、条件排他性の意味で等価なことがわかる。以上の考察は、一般のケースに容易に拡張できる。
【０３５７】
以上より、ＧＣＶは、トップレベルのある１つの条件分岐に起因する排他性、投機実行のすべてのケースを統一的に表現可能である。
【０３５８】
次に、トップレベルの条件分岐も統一的に表現できることを示し、ＧＣＶがすべての条件排他、投機実行を表現可能なことを示す。
【０３５９】
＜トップレベルの条件分岐＞
前述した、ネスト分岐内の並列条件文を、有効ビットを持つＧＣＶで表現する方法は、トップレベルに並んだ条件分岐文にも適用できる。
【０３６０】
また、トップレベルにＳＷＩＴＣＨ文が存在し、そのＳＷＩＴＣＨ  文の条件が未確定と考えても、有効ビットを持つＧＣＶで表現できることがわかる。
【０３６１】
図１９は、Ｔ１とＴ２という２つのトップレベルの条件分岐が並んでいる例をＧＣＶで表現したものである（ループのボディにある場合等も同様に考えられる）。
【０３６２】
しかしながら、このようなトップレベルの条件分岐にＧＣＶを与えると、トップレベルの分岐の部分のベクタに、有効ビットがつき、その他は、すべて”１”となる、長大なＧＣＶとなってしまい、現実的ではない。プログラム実装では属する分岐名とそれぞれのトップレベル条件分岐毎のＧＣＶを持つ等の形式となる。
【０３６３】
重要な点は、異なるトップレベルの条件分岐に属する演算が、仮想的に統一的なＧＣＶを持っていると考えることである。
【０３６４】
トップレベルの条件分岐毎にスケジューリングするのではなく、異なるトップレベルの条件分岐に属する演算ノードを、任意の順にスケジューリングすることが可能となる。
【０３６５】
即ち、異なるトップレベル条件文に属する演算を、スケジューリング時は、１つの基本ブロックにある演算のように扱うことが可能になるのである。これらについては、スケジューリングアルゴリズムでも説明する。
【０３６６】
＜スケジューリング手法＞
ＣＤＦＧの演算ノードに付与された条件ベクタ（ＧＣＶ）を利用したスケジューリング手法について説明する。大規模回路にも適用可能なリストスケジューリングに基づいており、Ｃｏｎｄｉｔｉｏｎ−Ｖｅｃｔｏｒ−Ｂａｓｅｄ  Ｌｉｓｔ  Ｓｃｈｅｄｕｌｉｎｇ  （ＣＶＬＳ）法と呼んでいる。スケジューリング手法は、基本ブロック内の局所的なスケジューリング手法ではなく、制御依存性を超えて（基本ブロックを超えて）、最適化を行う大局的スケジューリング手法である。大局的スケジューリング手法としてのＣＶＬＳ法の特徴は、以下の２点である。
【０３６７】
１）すべてのタイプの投機実行を大局的な見地から判断して適用でき、スケジューリング処理自体が効率的である。
【０３６８】
２）最長パスだけでなくすべてのパスの最適化を試みる。
【０３６９】
演算器制約、時間制約それぞれに対応可能であり、両者を混在した運用が必要であるが、演算器制約の下で、最短サイクルでスケジューリングする演算資源制約スケジューリング手法を議論する。
【０３７０】
＜プライオリィティ関数＞
リストスケジューリングでは、データ依存関係を解析し、ある制御ステップにスケジュール可能になった集合（以下、「割り当て可能リスト」、または、「Ready リスト」と呼ぶ）を作成し、その集合の中から、スケジュールする候補をあるプライオリティ関数に基づいて作成する。このプライオリティ関数の善し悪しで、リストスケジューリングの初期スケジューリング結果の良否が決定される。基本ブロックに対する局所的なリストスケジューリングの典型的なプライオリティ関数は、ＣＤＦＧの最終段のノード（「ＥＮＤノード」と呼ぶ）からそのノードまでの長さ（演算器の段数）である。本実施例では、プライオリティ関数はオプションや動作記述の性質によって切り替えることができるようになっているが、基本的には、同様にＥＮＤノードからの距離を利用している。但し、大局的スケジューリングであり複数の基本ブロック間にまたがるスケジューリングを行っている点、演算器の実遅延（演算のチェーン効果）を考慮する必要性、時間制約を扱う点等で、改良を施している。
【０３７１】
（ａ）  確率付き距離：
ＣＶＬＳでは、条件ベクタの必要演算器数算出手法等を利用して、複数の基本ブロックをまたぐスケジューリングを行える。このため、プライオリティ関数として、単純なＥＮＤノードからの距離は利用できない。なぜなら、条件分岐がある場合に距離は一意に定まらないからである。
【０３７２】
本発明では、最大距離と、確率的距離の２つのプライオリティ関数を選択できるようにしている。デフォルトでは確率的距離を利用しており、すべてのパスの最小化をはかっている。
【０３７３】
また、距離は、演算の段数（個数）ではなく、演算の実遅延を用いる。
【０３７４】
確率的な距離は、分岐のそれぞれのＥＮＤノードからの距離をその分岐の成立確率付き平均をとったものである。より成立確率の高いパスを最適化するとともに、他の短いパスの最適化も評価関数に含めることができる。提案するプライオリティ関数は以下に示すように、確率ベクタと距離ベクタの内積で定義される。条件分岐がない場合は、プライオリティ関数は、ＥＮＤノードへの最長距離に等しくなる。
【０３７５】
確率ベクタp ：演算ノードn が属する条件分岐条件ベクタの各ビット（即ちリーフの条件）の生起確率
【０３７６】
シミュレーションを実行したプロファイルを利用できる場合は、その生起確率を利用する。プロファイルを利用できない場合は、各条件の成立確率から、各ビットの生起確率を計算する。例えば、以下の動作記述でａ、ｂ、ｃの成立確率がそれぞれ５０％である場合は、それぞれのビットの生起確率は、［１／４，１／８，１／８，１／２］となる。
【０３７７】
if (a) if (b) x;                [1,0,0,0]
else if (c) esle y;     [0,1,0,0]
else z;             [0,0,1,0] 
else                            [0,0,0,1] 
【０３７８】
（ｂ）距離ベクタ：
距離ベクタは、演算ノードｎからＥＮＤノードまでのパスに存在する演算のＥＣＶの和である。実際には、ＥＮＤノードから情報へ向かって順にＥＣＶを加えていく。ファンアウトがあった場合やＪＯＩＮノードがあった場合は、同じ位置の成分の最大値を取る。このように一回フローを流すことで、ＣＤＦＧのすべてのノードの距離ベクタを求められる。条件ノードの場合は、ＪＯＩＮノードやＦＯＲＫノードからの条件線もパスに含める。ノード間に時間制約が張られている場合（例えば、ある演算とある演算の間は０サイクル）、時間制約も距離ベクタの計算で考慮する。具体的には、時間制約の線をそのサイクル分の距離として計算する。
【０３７９】
また、これまで説明では、距離ベクタは、ＥＣＶの和、即ち、通過する演算の個数としていたが、実際の距離ベクタの計算には、各演算の遅延時間を利用する。例えば、ＥＣＶが［１，０，１］の演算の遅延が４ｎｓの場合、距離ベクタに［１，０，１］を加算する。代わりに、［４，０，４］を加える。サイクル数で与えられる時間制約等は、クロック周期を利して実時間に置き換える。
【０３８０】
プライオリティ関数は、各条件分岐毎に上記確率ベクタと距離ベクタの内積を取った
ものの総和であり、以下のように定義される。
【０３８１】
（ｃ）プライオリティ関数ｐｆ（ｎ）
【０３８２】
pf (n) = ΣＴ (p,d)= ΣＴΣＴｉ（ pi * di ） 
【０３８３】
ここで、
ｐは確率ベクタ、
ｄは距離ベクタ、
（ｐ，ｄ）はｐとｄの内積、
ｐｉ，ｄｉは各ベクタの要素、
Ｔは、ノードからＥＮＤノードまでの間の条件分岐の集合、
ｉはベクタの各成分を示すインデックス、
である。
【０３８４】
プライオリィティ関数は、本来は、クロック周期と演算器の遅延の相対関係を考慮す
る必要がある。本実施例の演算器制約スケジューリングアルゴリズムでの目標は、平均必要ステップ数の最小化となる。
【０３８５】
（ｄ）目的関数：
「平均必要ステップ数」＝（パス長ベクタ，確率ベクタ）
【０３８６】
ここで、パス長ベクタは、ＦＵＶａｌｌの０成分をスキップするとして計算した、リーフ条件毎のパス長。確率ベクタは、各リーフ条件の生起確率。平均必要ステップ数は、パス長を生起確率付きで平均した必要サイクル数となる。
【０３８７】
＜演算ノードのリスケジューリング＞
ノード分割して、演算ノードのスケジューリング位置をバラバラに割り当てる方法を説明したが、このときキーとなるのは、演算器制約を守りながら、必要ステップ数を短くすること、即ちＦＵＶａｌｌｌの０成分の数を増加するという考え方である。この考え方自体はスケジューリング全体に広く利用可能である。
【０３８８】
本発明のスケジューリング手法でも、一旦スケジューリングが終了した後に、演算ノードの分割をするしないに関わらず、ノードのスケジューリング位置を可能な範囲で順次変更し、必要サイクル数を減少することを行う。初期的なスケジューリングの後の逐次的な反復改良スケジューリング手法をとっている。
【０３８９】
次に、複数の条件分岐を並列化するような投機実行（「大局的な投機実行」）の例を図２０に示す。図２０（ｃ）の動作記述は、２つのトップレベルの条件文（ＩＦ文）をもった記述例である（Ｃ言語を拡張したＢＤＬ言語にしたがって記述されている）。
【０３９０】
この動作記述を記述順通り（ｉｎ−ｏｒｄｅｒ）にスケジューリングしたのが、図２０（ａ）である。それぞれの条件の真偽により、実行に必要なサイクル数は異なるが、両方の条件が真の場合に４サイクル必要である。
【０３９１】
一方、これらトップレベルの条件分岐同士の並列化を許した場合が、図２０（ｂ）である。
【０３９２】
２つのＩＦ文には、変数Ｒ１のデータ依存関係があるが、条件依存関係の制約を取り払えば、図２０（ｂ）のように、並列化が可能である、最大でも（２つの条件節が真の場合でも）、２サイクルでスケジューリング可能となる。
【０３９３】
図２０（ｂ）の例においては、それぞれの条件文が局所的な投機実行を行い、さらにこの大局的な投機実行を行うようにしてもよいことは勿論である。
【０３９４】
図２０（ｂ）に示したような、大局的な投機実行を陽にあつかった動作合成のスケジューリング手法は、本発明が最初であると考えている。コンパイラの分野においても、最初と考える。
【０３９５】
＜複数の条件分岐文の並列化手法（より大局的なスケジューリング）＞
基本ブロック内のスケジューラという局所的なスケジューリングに対して、基本ブロックを超えた大局的な（グローバルな）スケジューリングを条件ベクタで行う手法を議論してきた。
【０３９６】
これらは、１つのネストした条件分岐に対して、非常に様々なｏｕｔ−ｏｆ−ｏｒｄｅｒ実行を行う手法であった。
【０３９７】
図２１に示すように、複数のトップレベルの条件分岐文同士を並列化する手法について説明する。並列化は、従来の分岐演算の確定よりも、分岐内演算を先に行うという基本的な投機実行とは異なり、必ずしも条件演算より分岐内演算が先行してスケジューリングされる必要はなく、複数の条件分岐が並列化さえる点が重要である。
【０３９８】
また、各条件分岐で投機実行が行われていて、さらに並列化することは、当然考慮する。
【０３９９】
ｏｕｔ−ｏｆ−ｏｒｄｅｒ実行と投機実行をほぼ同等の意味で使用している。よって、このようなグローバルな並列化を、局所的な投機実行が行われていなくても、グローバルな投機実行と呼んでいる。
【０４００】
＜複数の条件分岐文の並列化手法＞
【０４０１】
（ａ）  ＡＣＶに基づく逐次的並列化：
１つのトップレベルの条件文（ＩＦ文やＳＷＩＴＣＨ文）中の演算は相互排他であり、演算器の共用が可能である。
【０４０２】
また、一度に実行される分岐パスは一本だけである。
【０４０３】
一方、異なるトップレベルの条件文にある演算はお互いに条件排他ではなく、演算器の共用もできない。
【０４０４】
また、トップレベルの条件文を並列化した場合、同時に複数の（並列化されたトップレベル条件文と等しい数の）分岐パスが実行される。よって、前述した１つの条件分岐への制御論理生成手法もそのままでは適用できない。
【０４０５】
図２１（ａ）に、２つのトップレベルのＩＦ文（ＣＴ１、ＣＴ２）の例を示す。ＣＴ１、ＣＴ２それぞれに条件ベクタ（ＡＣＶ）が与えられる。ＧＣＶの下はＧＣＶ値である。。条件Ｃ１、Ｃ２、Ｃ３はすべて確定しているとする。ＣＴ１とＣＴ２の２つのトップレベルＩＦ文を加算器２個減算器１個の制約で並列化することを考える。ＣＴ１、ＣＴ２内の加算，減算は相互に条件排他関係にあるが、Ｔ１とＴ２の加算の間には排他関係は無い。並列化を逐次的に行う方法として、まず、分岐ＣＴ１をＣＶＬＳ法でスケジューリングし、各制御ステップでの演算器の残りを計算し、それを新たな演算器制約として、次にＣＴ２  をスケジューリングすれば２つの条件分岐を並列化できる。このときもちろん、ＣＴ１とＣＴ２の間のデータ依存関係は満たすようにスケジューリングは実行する。図２１では、変数ｘが分岐間のデータ依存となっている。
【０４０６】
図２１（ｂ）において、ＦＵＶ＋、ＦＵＶ−は加算器、減算器それぞれの演算度使用度ベクタであり、ＣＴ１ではその成分の最大値がそれぞれ２と１を超えなければよい。
【０４０７】
Ｒ１は、各制御ステップで使わずに残っている演算器の数である。ＣＴ２のスケジューリングは、このＲ１を演算器制約としてスケジューリングされる。つまり、ＦＵＶ＋、ＦＵＶ−の最大成分が、各制御ステップでＲ１を超えないようにスケジューリングすればよい。但し、この方法は、演算をスケジューリングする順番を動作記述に条件分岐文（ｓｗｉｔｃｈ  文が）記述された順番どおりにしており、明らかに最適性が損なわれる。なお、この手法はＡＣＶでは、異なるトップレベルＩＦ文間で演算器数を算出できないために考案された手法である。次に、ＧＣＶを用いることで改良した手法を説明する。
【０４０８】
（ｂ）  ＧＣＶを利用した並列化：
一般化された条件ベクタＧＣＶを基に、前述した複数の条件分岐分の並列化を行うことを考える。ＧＣＶを利用すれば、複数の条件分岐の間の演算間でも、必要演算器数は算出可能となるから、属する条件分岐は気にせずに、プライオリィティ関数の大きい順にスケジュール可能となる。
【０４０９】
つまり、あらゆる意味で、条件分岐の制御依存関係は取り払われ、データ依存関係だけで並列化することが可能となる。言い換えれば、スケジューラから見た場合、ＧＣＶを付与された演算ノードが、あたかもすべて基本ブロックの中にあるように扱ってよい。よって、基本ブロック向けに開発された様々な（局所的）スケジューリングアルゴリズムを、大局的スケジューリングに応用可能となる。
【０４１０】
前記ＡＣＶに基づく逐次的並列化のＧＣＶを用いた改良方法は非常に簡単であり、基本的にＧＣＶを利用して、ＦＵＶをＧＣＶに基づいて計算するだけである。トップレベルのすべての演算に統一的にＧＣＶを（仮想的に）考えることができる。従って、ＧＣＶに基づいたＦＵＶの計算方法で必要演算器数を計算していれば、属する条件分岐に関係無く、任意の順序でスケジューリングが可能となる。
【０４１１】
図２１の例を参照して説明する。例えば、ＣＴ１の［１，０，１，１，１］を制御ステップＳ１  に割り当て、次に、ＣＴ２の［１，１，１，０，０］と［１，１，０，１，１］を制御ステップＳ１に割り当てるとする。このとき、ＦＵＶ＋は、［１，０，１，１，１］＋［１，１，１，０，０］＋［１，１，０，１，１］で得られるから、［１，０，１，１，１］＋［１，１，１，１，１］で、加算器は２つ必要であることがわかる。
【０４１２】
次に、加算［０，１，１，１，１］を割り当てても同様の計算で、加算器２個の制約を守れることが即座に判定できる。ＧＣＶに基づいたＦＵＶ＋、ＦＵＶ−を図２１（ｂ）の右端に示す。
【０４１３】
このように、ＧＣＶを利用することで、ＣＴ１の演算をすべてスケジューリングし、次にＣＴ２をスケジューリングするというように、動作記述の制御構造・制御依存性にとらわれる必要はなく、上記のようにＧＣＶに、基づいたＦＵＶを利用して、全体が１つの基本ブロックと同様にスケジューリングすれば良い。
【０４１４】
以上の考察から、本発明で提案するＣＶＬＳ手法は、あらゆるタイプ条件分岐の制御依存に制約されずに並列化でき、また、おそらくすべてのタイプのｏｕｔ−ｏｆ−ｏｒｄｅｒを統一的に実現できる優れた手法と思料される。なお、この分野の専門家である本発明者の知る限り、このような性質を持つスケジューリング手法は提案されていない。
【０４１５】
＜制御用ステートマシン（ＦＳＭ）生成＞
単一の条件分岐に対する制御論理生成手法については、図１０を参照して説明した。しかしながら、この方法では、条件分岐を並列化した場合の対応が示されていない（トップレベルの条件分岐に限らず、ＧＣＶで分岐内の複数の条件分岐を並列化した時も同様である。
【０４１６】
条件分岐を並列化した場合の、制御論理生成方法を、図２１を参照して説明した並列化したスケジューリング結果を用いて説明する。
【０４１７】
この制御論理生成手法は、スケジューリング手法は、逐次的な並列化でも、ＧＣＶを使った並列化にも同様に利用可能である。図２１の条件分岐ＣＴ１、ＣＴ２のそれぞれに対して、ＦＵＶａｌｌの０をスキップするように制御回路を生成すると、図２２（ａ）に示す状態遷移となる。
【０４１８】
この２つの状態遷移をそれぞれ独立なＦＳＭとして合成してしまうと、正しく動作しない。これは、２つの状態遷移は独立ではなく、それぞれ依存関係があるためである。
【０４１９】
１）２つの分岐間には、データの依存関係がある。
【０４２０】
２）必要な演算器数は、分岐ＣＴ１、ＣＴ２で、各制御ステップで異なるから、演算器制約を満たせないような状態の組み合わせがある。
【０４２１】
例えば、制御ステップＳ１から、ＣＴ１が、Ｓ２−１へ、ＣＴ２がＳ３−２へ遷移した場合、データ依存性も、演算器制約も満たせなくなる。
【０４２２】
つまり、２つの状態遷移は、同期して常に同じ制御ステップにいるようにしなければならない。
【０４２３】
複数のＦＳＭを作成して同期させる方法もあるが、ハードウェア資源が多く必要になるので、２つの同期する状態遷移を実現する１つのＦＳＭを生成すればよい。
【０４２４】
複数の同期する状態遷移を融合して１つのＦＳＭにするには、それぞれの状態遷移のすべての分岐で、ジャンプ可能なジャンプ先とその条件を求めればよい。
【０４２５】
例えば、図２２の例で、一番近傍に遷移するものから順に求めると考える。
【０４２６】
ＣＴ１は、「ｃ１’」でＳ２−１へ遷移（「ｃ１’」はｃ１の相補（反転）値）。ＣＴ２はＳ２への遷移はない。
【０４２７】
よって、まず、条件「ｃ１’」でＳ２へ遷移する論理を生成する。それ以外の条件で、「ｃ２＊ｃ３’」の場合は、Ｓ３へ遷移、さらにそれ以外では、最終状態へ遷移すれば良いことがわかる。
【０４２８】
以上の制御論理生成方法をＧＣＶとして説明すると、有効ビットの重ならないＧＣＶノードの状態遷移は、上記した並列な条件分岐文と考え、上記の遷移生成ルールを適用する。
【０４２９】
つまり、有効ビットが重なっているもの毎にＦＵＶａｌｌを求め、それぞれについて状態遷移を求める。有効ビットが重なるということは、上記の例では同じ条件分岐に属するということを意味する。
【０４３０】
次に、それぞれの状態遷移を上に示した方法で、融合して１つのＦＳＭを生成すれば良い。上記に例で示した制御論理生成方法を一般化すると、以下の手順となる。
【０４３１】
＜条件分岐を並列化した場合の状態遷移生成の手続き＞：
【０４３２】
現状態＝先頭の制御ステップ；
【０４３３】
ステップ1: 
ｐｒｅｃｏｎｄ＝１（ｔｒｕｅ）
【０４３４】
各分岐（または、ＧＣＶの「有効ビットが重なる集合」のそれぞれ）の「現状態」から直接の遷移先の中で最も遠い遷移先をそれぞれ求め、その中で最も近い遷移先Ｊｍａｘを求める。
【０４３５】
ステップ2: 
各分岐からのすべての遷移先で、Ｊｍａｘより近いものを近いもの順にソートし、結果を遷移先リストＪｌｉｓｔへ。
【０４３６】
ステップ3: 
Ｊｌｉｓｔ  の遷移先への遷移条件を求める。Ｊｌｉｓｔの先頭から同じ遷移先のものを取り出し、それぞれの遷移条件の論理和をＣとする。
合成ステートマシンの遷移条件は、
ＣＯＮＤ＝ｐｒｅｃｏｎｄ＊Ｃ  
Ｊｌｉｓｔから取り出したジャンプ先を削除。
【０４３７】
ステップ4: 
Ｊｌｉｓｔが空であれば現状態からの遷移生成は終了し、現状態を次の状態にして、ステップ１へ。
そうでなければ、ｐｒｅｃｏｎｄ＝ｐｒｅｃｏｎｄ＊！ＣＯＮＤとしてステップ３へ。
（ただし！ＣＯＮＤはＣＯＮＤの否定、つまりＣＯＮＤ条件以外の場合）  
終わり：  
【０４３８】
図２２の例で、上の手続きを説明すると以下の通りである。
【０４３９】
各条件分岐のＳ１からの状態遷移は以下のとおりである。
【０４４０】
CT1: if (c1) -> S5           -(1)
else > S2              -(2)
CT2: if (c2) -> S3           -(3)
else if (c3) -> S3     -(4)
else -> S5        -(5)
【０４４１】
よって、上記アルゴリズムを適用すると以下のようになる。
【０４４２】
Jmax ＝ S5;
Jlist = {S2, S3}
S2 への遷移条件CONDは、!c1.
S3 への遷移条件は(c2|| !c2*c3)*!(!c1).
S5 への遷移条件は,! ((c2||c3)*!(!c1))
【０４４３】
合成されたＦＳＭのＳ１からの遷移条件は以下のようになる。
【０４４４】
S1: if(!c1)                 ->S2 :if(2))
Else if(c2||!c2*c3)     ->S3 :elseif(3,4)
else               -> S5 :else
【０４４５】
また、Ｓ２  、Ｓ３  からの状態遷移は同様にして以下のように求められる。
【０４４６】
S2:if (c2||!c2*c3)        ->S3
else                  ->S5
S3: if (!c2*c3)           ->S4
else                    ->S5
S4:                       ->S5
【０４４７】
＜スケジューリングアルゴリズム＞
動作合成全体の基本フローを以下に示す。
【０４４８】
１）  ＣＤＦＧを作成；
２）  言語レベル最適化（ループマージ、ループ展開、定数伝搬、共通項抽出、デッドコ
ード削除、関数展開、関数演算子化、配列、構造体の実現、ポインタ解析等）；
３）  アロケーション（利用可能な演算器のセットを決定）；
４）  リソース制約スケジューリング（演算をサイクルに割付る）；
４’）  ループのパイプライン化（モジュロスケジューリング＋時間制約）；
５）  バインディング（CDFGの演算を実行する演算器を決定）；
６）  シェアドメモリ等のインターフェース生成；
７）  制御論理生成；
８）  論理合成可能なＲＴＬ（Ｖｅｒｉｌｏｇ−ＨＤＬ，  ＶＨＤＬ  ）生成；
【０４４９】
４’）のモジュロスケジューリングは、パイプラインのＤａｔａ  Ｉｎｉｔｉａｌ  Ｉｎｔｅｒｖａｌ（ＤＩＩ：ループの本体をパイプライン化（フォールディング）した時に、データを何サイクル毎にいれられるか）に併せて、行うスケジューリングである。例えばＤＩＩ＝３  なら、あまりが０，１，２のそれぞれで必要演算器数を算出し、演算器制約を満たすようにすること、また、フィードバック変数について、書き込みと読み込みの間がＤＩＩ  以内にスケジューリングされること、等の制約を満たすスケジューリングが必要）。
【０４５０】
上記の４）のリソース制約スケジューリングのアルゴリズム詳細を以下に示す。前節までに説明してきた、条件ベクタを利用した動作合成手法の手順をアルゴリズム的に記述したものである。今まで述べてきた一般化条件ベクタの性質を利用した方法であるため、「Ｇｅｎｅｒａｌｉｚｅｄ  Ｃｏｎｄｉｔｉｏｎ  Ｖｅｃｔｏｒ  ｂａｓｅｄ  Ｌｉｓｔ  Ｓｃｈｅｄｕｌｉｎｇ法」と呼んでいる。
【０４５１】
リストスケジューリングは、基本的な処理が簡素であるため、演算器制約や資源制約という複数の制約をとったり、演算チェーン、マルチサイクル演算、パイプライン演算器、パイプラインメモリ等演算ノードの多種なバリエーションに対応するようなアルゴリズム拡張が容易である。
【０４５２】
実用に供する動作合成システムとして、このようなアルゴリズムの後からの拡張性は非常に重要である。提案システムは、商用チップの設計に利用されているため、他にも、クロックの逆相の利用、ラッチの利用、複数クロックドメインへの適用などを実現するため、スケジューリングアルゴリズムにも様々な拡張を施している。
【０４５３】
これらの拡張のうち、演算チェーン、マルチサイクル演算、マルチプレクサ遅延等の考慮を含ませたアルゴリズムを以下に記述する。以下で、演算ノードとしているものは、加算等の算術演算だけでなく、配列アクセスや、入出力アクセス等、スケジューリング対象となるすべての処理のことである。「演算器制約」という言葉も、算術演算器の種類、ビット幅や数を表しているだけでなく、メモリの種類やポート数（リードポート、ライトポート数）、入出力のポート数も含んでいる。演算器制約を満たすという表現で、上記のメモリのポート数等を満たすことも意味している。
【０４５４】
このアルゴリズムは、広域（大局的な）スケジューリング手法であり、複数のトップ条件分岐文や、複数の基本ブロックを一度にスケジューリングする手法である。それにもかかわらず、アルゴリズムに基本ブロックや条件分岐の投機実行に関する陽な扱いを行っている部分がなく、単一の基本ブロックの演算器制約型リストスケジューリングとほぼ同様に見えるのに注意が必要である。（上記手順には、遅延の扱いやノード分割などを記したため、記述が煩雑になっているが、基本の流れは、基本ブロックのリストスケジューリングと同様である）。
【０４５５】
これは、ＣＤＦＧ上のノードに付与された条件ベクタを用いることで、基本ブロック向けのスケジューリング手順で、投機実行を含む様々な探索可能なことを示している（前節までに述べてきたすべてのタイプのｏｕｔ−ｏｆ−ｏｒｄｅｒ実行が可能である）。ＧＣＶの各種演算（ＦＵＶによる必要演算器数算出等）は属する条件文の分岐数に比例する程度の計算量でしかないから、本発明で提案したスケジューリング手法そのものも基本ブロックのリストスケジューリング並の計算量（ｎｌｏｇ（ｎ））で行えることを意味している。これは、従来のＰａｔｈ−ｂａｓｅｄスケジューリングなど指数オーダーの手法と比べ、より効率的な計算量である。
【０４５６】
上記アルゴリズムでは触れていないが、単一分岐への投機実行（局所的な投機実行）を行わないスケジューリングをする機能を持たせている。ＣＤＦＧのｆｏｒｋノードへの条件線をデータ依存のように扱うことで容易に実現できる。各分岐毎にこの投機実行を行わないモードでのスケジューリングも行い、必要な制御ステップ数が変わらず、レジスタ数等で有利になれば、こちらを採用するようにしている。投機実行は、レジスタ数をより多く利用する性質があるため（利用しない可能性のある変数も保持するから）、分岐毎にスケジューリングを単一分岐への投機実行を２回行う戦略をとっている。条件文の並列化等は常に行っている。
【０４５７】
次に、２５ｍａｈａの結果をグラフにしたものを、図２３に示す。図２３には、演算器制約を加算器、減算器の組として、（１，１）→（２，３）→（５，５）と増加させた時に、”Ｂｏｔｈ”、”Ｌｏｃａｌ  ＳＰ”、”Ｉｎ−ｏｒｄｅｒ”の手法に対して必要ステップ数の最大値と平均ステップをグラフ化して示されている。これらのグラフは、本発明で提案したｏｕｔ−ｏｆ−ｏｒｄｅｒスケジューリングが、本データに対しきわめて理想的に働いていることを示している。
【０４５８】
まず、同じ演算器制約数内でみると、ｉｎ−ｏｒｄｅｒから、ｌｏｃａｌ投機実行、ｇｌｏｂａｌ並列化を順に適用することで、大きくサイクル数を下げられていることがわかる。特に、演算器数が大きい時に、この傾向が顕著である。
【０４５９】
次に、演算器制約を３段階に増加した場合を考察する。Ｉｎ−ｏｒｄｅｒ実行では、合計演算器数を２個、５個、１０個と増加していっても、あまりサイクル数は減っていない（１８０→１５７→１５３）。
【０４６０】
次にｌｏｃａｌな投機実行を行ったスケジューリングでは、演算器を増加すると、１５６（２個）→１０７（５個）→１０２（１０個）と、合計演算器が２個から５個に増えるまでは大きくステップ数が減少しているが、５個から１０個に増えても、あまり減少していない。これは、プロセッサでよく言われる、「たとえスーパースカラにしても、コンパイラが頑張らない限り、ＡＬＵは４つ以上に増やしてもそれほど並列度はあがらない」という経験則にあっている。人の書くＣ記述は、条件分岐やループ等が数行おきにはいり、基本ブロックだけで何十行も続くことが非常に少ないからである。
【０４６１】
最後にｇｌｏｂａｌなｏｕｔ−ｏｆ−ｏｒｄｅｒ実行を行うと、演算器を増加するのに比例するイメージで必要ステップ数が１２５→６５→３２と減少している。
【０４６２】
これは、本発明で提案したｇｌｏｂａｌなｏｕｔｏｆ−ｏｒｄｅｒ実行とｌｏｃａｌな投機実行を両方行えば、制御依存による並列性阻害はなくなり、純粋にデータの依存関係だけで並列化が行われていることを示していると考えられる。
【０４６３】
即ち、複雑で多数の条件分岐のある、多数の基本ブロックからなる動作記述に対しても、本発明の手法は、基本ブロックと同様の並列化能力をもっていることを示せている。全体で考えると、ｉｎ−ｏｒｄｅｒで１８０ステップあった動作を、演算器を５倍に増加して、提案した並列化技法を加えることで、３２ステップにできており、これは、ほぼ、１／６である。したがって、ほぼ、理想的に並列化が行えているものとみなしてよい。
【０４６４】
演算器の増加倍率より、ステップの削減率が低く見えるが、これは並列化技法を用いない例と比較したからである。並列化技法を利用した場合同士では、演算器を５倍にすると、ステップ数は、１２５から３２であるから、１／４に低下しており、リーゾナブルな値といえる。
【０４６５】
プロセッサと異なり、動作合成で合成されるハードウェアは高速性が何より重要であるから、提案した手法の並列化能力の高さは、実用化のために非常に重要である。
【０４６６】
図２４は、ＧＣＶの分岐内の並列条件分岐文のスケジューリング結果を示す。「本発明」は、ＧＣＶを利用した方法で、「従来」は、このような分岐内の並列条件文間の排他性を厳密に見ることができない手法（ＡＣＶだけの場合）である。これら３つすべての例で、ＧＣＶ  を用いた本発明の手法は、従来手法に比べ、同じ演算器制約数の元で状態数を削減することができた。（これら３つのデザインでは状態数が実行ステップ数と等価である。）これは、ＧＣＶの厳密な排他性解析がステップ数削減にも効果があることを示している。また、動作合成後の予測面積・遅延が、動作合成されたＲＴＬ  を論理合成した後の回路の面積・遅延と非常に近く、提案した動作合成の予測手法の誤差が小さくことを示している。動作合成内ではこの見積もり面積・遅延を元に最適化をかけているため、この精度は重要である。
【０４６７】
なお、これら３つのデザインに対し同じ演算器制約で本発明の手法と従来手法は合成をかけているので、演算器の使用数は同じである。Ｆｉｌｔｅｒの例で、本発明の手法の方が面積が下がっているのは、本発明の手法では、スケジューラだけでなくバインディングアルゴリズムもＧＣＶ対応しており、より厳密に排他性を抽出できるようになり、レジスタ数やマルチプレクサ数が削減した点があげられるが、本発明の方は、バインドアルゴリズム自体の改良（特にマルチプレクサの最適化）も施しており、その効果も入ってしまっている。ＧＣＶの効果だけで面積が低減した訳ではない。本発明と従来技術でプログラム全体が改良されており、本発明の実験時にマルチプレクサの最適化等の効果を取り除くことができなかったためである。
【０４６８】
図２５は、パイプライン化とトップレベルの条件分岐文を並列化した場合（ｇｌｏｂａｌ  並列化）の効果を実験したものである。用いた設計例は、１００回反復するループ内に、トップレベルの２つのＩＦ文を持つ小規模な記述例である。ｇｌｏｂａｌ並列化により従来７ステップ必要だったループボディの実行が５ステップになり、全体の実行レイテンシは７００サイクルから、５００サイクルに３０％削減できている。次にループをパイプライン化（フォールディング）した結果を示す。ＩＩは、Ｉｎｉｔｉａｌ  Ｉｎｔｅｒｖａｌの略で、ループを反復する間隔（インターバル）のサイクル数を示す。ｇｌｏｂａｌ並列化無しでは、ＩＩが４でしか合成できないのに対し、ｇｌｏｂａｌ並列化を施すとＩＩ＝２  でスケジューリング可能となり、全体の実行レイテンシは、４０３サイクルから２０３サイクルと５０％の減少が可能となる。
【０４６９】
ループをパイプライン化する場合にＩＩを小さくするのを阻害する要因は、
１）資源競合と
２）ＷＡＲ（Ｗｒｉｔｅ−Ａｆｔｅｒ−Ｒｅａｄ）
の依存性である。
【０４７０】
ｇｌｏｂａｌ並列化により、ループボディの並列度の自由度が増え、これらの阻害要因をクリアしつつ、ＩＩを最小化することができている。
【０４７１】
本発明で提案した条件ベクタに基づく並列化技法は、通常の合成時に比べ、ループパイプラインの場合にさらにその効果が増幅されることがわかる。画像・音声などの信号処理系のハードウェア設計ではパイプライン回路は非常に重要である。本発明で提案した広域スケジューリング手法は、動作記述からのハードウェアの自動合成で本質的に重要な役割を果たすことを示している。
【０４７２】
大局的なｏｕｔ−ｏｆ−ｏｒｄｅｒ実行、局所的なｏｕｔ−ｏｆ−ｏｒｄｅｒ実行どを統一的に表現しできる条件ベクタと呼ぶ概念を導入し、それ利用したスケジューリング手法ＣＶＬＳやバインド手法、制御論理生成手法からなる動作合成手法を述べた。本手法は、データ依存解析により発見できる暗黙的な条件排他性の抽出、各種投機実行を行った場合の演算器数解析等を効率的に行い、すべての実行パスの最適化を行える等の優れた特徴を持っている。
【０４７３】
一般化条件ベクタは，本発明者の想定できる限りの条件分岐に関連するｏｕｔ−ｏｆ−ｏｒｄｅｒ実行のバリエーションを統一的に表現できている。条件ベクタは、ＣＤＦＧの構造を変えることなく、条件排他性や各種投機実行を表現できるため、基本ブック向けのスケジューリング手法向けに開発された様々なスケジューリングアルゴリズムに適用することが可能である。条件ベクタの各種計算（排他性解析や必要演算器数算出、制御論理生成等）は計算量が小さい（分岐数に比例）ため、基本ブロック向け（局所）スケジューリングアルゴリズムの計算効率を落とすことなく、広域スケジューリングを可能にする。実験結果に、これらの並列化により、高性能な回路が合成できることを示した。
【０４７４】
また、本発明で提案した資源制約のＣＶＬＳ法は、ＶＬＩＷやスーパースカラ等の多数のＡＬＵを持つプロセッサ向けのコンパイラに、比較的容易に拡張可能である。
【０４７５】
具体的には、レジスタとデータ転送路（バス）の資源制約をいれ、レジスタ数が足りなくなった場合はスピルコードを導入する等の変更を施せばよい。
【０４７６】
図２６は、上記した本発明の一実施例の自動合成装置１の要部構成を説明する図である。制御データフローグラフ作成部２は、動作記述（C等の高水準言語）を入力し解析を行って、制御データフローグラフを作成し、条件ベクタ生成装置３は、制御データフローグラフに対して上記したＧＣＶ（あるいは、ＧＣＶのほかに、ＥＣＶ、ＡＣＶ等）を生成し、スケジュール部４は、前述したスケジューリング手法にしたがって、例えばＧＣＶを用いて上記した大域的なスケジューリングを行う（前記した複数ＩＦ文の並列化、状態遷移の合成等も含む）。そして、データパスのバインディング等を行い、制御回路を生成し、論理合成可能なＲＴＬ（Ｖｅｒｉｌｏｇ−ＨＤＬ，ＶＨＤＬ）生成する。これらの処理は、自動合成装置を構成するコンピュータで実行されるプログラムで実現するようにしてもよいことは勿論である。また、ＶＬＩＷやスーパースカラ等の多数のＡＬＵを持つプロセッサ向けのコンパイラでは、ＲＴＬの代わりに、ＶＬＩＷやスーパースカラ等の多数のＡＬＵを持つプロセッサ向けのインストラクションコードを生成する。
【０４７７】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図面の簡単な説明】
【０４７８】
【図１】局所投機実行：単一条件分岐に対する投機実行の例を示す図である。
【図２】コントロールデータフローグラフ（ＣＤＦＧ）の例を示す図である。
【図３】基本条件ベクタの例を示す図である。
【図４】拡張条件ベクタの例を示す図である。
【図５】動作条件ベクタと投機実行を説明する図である。
【図６】投機実行とＥＣＶ、ＡＣＶを説明する図である。
【図７】演算遅延とクロック周期とＡＣＶの関係を説明する図である。
【図８】必要演算器数算出方法とＦＵＶの関係をを説明する図である。
【図９】演算ノード分割の例を説明する図である。
【図１０】制御論理生成の例を説明する図である。
【図１１】ネストした条件文の内側条件の投機実行とＧＣＶを説明する図である。
【図１２】部分的に未決定条件があるネストした条件文とＧＣＶを説明する図である。
【図１３】図１２の例でさまざまな条件を未決定にした場合のＧＣＶを一覧で示した図である。
【図１４】ネストした分岐内の並列ＩＦ文のＡＣＶによる扱いを説明する図である。
【図１５】ＧＣＶの拡張として、ネストした分岐内の並列ＩＦ文の扱いを説明する図である。
【図１６】分岐の中の複数の並列条件文とＧＣＶ、ツリーコピー、ツリー分割を説明する図である。
【図１７】分岐内並列条件文と一部条件未確定上条件文の同一性を説明する図である。
【図１８】分岐内並列条件文と対応するＧＣＶの例を示す図である。
【図１９】トップレベルの条件分岐とＧＣＶの例を示す図である。
【図２０】大局的投機実行：複数の条件分岐に対する投機実行の例を示す図である。
【図２１】トップレベルの並列IF文の並列化の一例を説明する図である。
【図２２】複数の並列分岐を制御するFSMの合成を説明する図である。
【図２３】グローバルとローカルのＯｕｔ−ｏｆ−ｏｒｄｅｒスケジューリング結果を説明する図である。
【図２４】本発明と従来技術による分岐内並列条件分岐のスケジューリング結果を比較して示す図である。
【図２５】本発明と従来技術によるループパイプラインを比較して示す図である。。
【図２６】本発明の一実施例の構成を示す図である。
【符号の説明】
【０４７９】
１  自動合成装置
２  制御データフローグラフ作成部
３  条件ベクタ生成部
４  スケジュール部
【図１】
2008090439.tif 000003
【図２】
2008090439.tif 000004
【図３】
2008090439.tif 000005
【図４】
2008090439.tif 000006
【図５】
2008090439.tif 000007
【図６】
2008090439.tif 000008
【図７】
2008090439.tif 000009
【図８】
2008090439.tif 000010
【図９】
2008090439.tif 000011
【図１０】
2008090439.tif 000012
【図１１】
2008090439.tif 000013
【図１２】
2008090439.tif 000014
【図１３】
2008090439.tif 000015
【図１４】
2008090439.tif 000016
【図１５】
2008090439.tif 000017
【図１６】
2008090439.tif 000018
【図１７】
2008090439.tif 000019
【図１８】
2008090439.tif 000020
【図１９】
2008090439.tif 000021
【図２０】
2008090439.tif 000022
【図２１】
2008090439.tif 000023
【図２２】
2008090439.tif 000024
【図２３】
2008090439.tif 000025
【図２４】
2008090439.tif 000026
【図２５】
2008090439.tif 000027
【図２６】
2008090439.tif 000028