(57)【特許請求の範囲】
【請求項１】
コントロールフローグラフの各ノードが各スケジューリング候補に割り当てられる確率をタイムステップ毎に合計し、その合計の最大値で面積を見積もって、見積もられた面積を最小化するようにスケジューリングを行う高位合成装置であって、
前記確率の合計が最大となるタイムステップにスケジューリング候補を持つ各ノードのそれぞれを該スケジューリング候補に仮割当した状態におけるそれぞれの面積を見積もる面積見積もり手段と、
該面積見積もり手段による見積もりの結果、見積もり面積が最大となる仮割当のノードとスケジューリング候補との組合せを求める組合せ算出手段と、
該組合せ算出手段によって求められた仮割当のノードとスケジューリング候補との組合せにおけるスケジューリング候補を、該組合せにおけるノードに対するスケジューリング候補から除外することによりスケジューリング候補を絞り込む絞り込み手段とを備え、
該絞り込み手段によってスケジューリング候補が絞り込まれた状態で、前記面積見積もり手段と、前記組合せ算出手段と、前記絞り込み手段とによる前記スケジューリング候補の絞り込みを、前記ノードおよびスケジューリング候補の組合せが１になるまで繰り返して、１になったノードとスケジューリング候補との組合せに基づいて該ノードのスケジューリングを行なうことを特徴とする高位合成装置。
【請求項２】
前記スケジューリング候補を絞り込む絞り込み手段は、前記組合せ算出手段によって求められた前記ノードとスケジューリング候補の組合せが複数ある場合に、各組みあわせ毎に、ノードを引数とする評価関数を計算して、計算された該評価関数の値が最大となるノードとスケジューリング候補の組合せを除外して、前記組合せを絞り込む、請求項１に記載の高位合成装置。
【請求項３】
前記評価関数が、（（ノードの入力ビット数の総和）−（ノードの出力ビット数の総和））×（スケジューリング候補のタイムステップ）である、請求項２に記載の高位合成装置。
【請求項４】
請求項１に記載の高位合成装置によって実施される高位合成方法であって、
前記面積見積もり手段によって、前記確率の合計が最大となるタイムステップにスケジューリング候補を持つ各ノードのそれぞれを対応するスケジューリング候補に仮割当した状態におけるそれぞれの面積を見積もる面積見積もりステップと、
前記組合せ算出手段によって、前記面積見積もりステップでの面積の見積もり結果から、見積もり面積が最大となる仮割当のノードとスケジューリング候補との組合せを求める組合せ算出ステップと、
前記絞り込み手段によって、該組合せ算出ステップで求められた仮割当のノードとスケジューリング候補との組合せにおけるスケジューリング候補を、該組合せにおけるノードに対するスケジューリング候補から除外することによりスケジューリング候補を絞り込む絞り込みステップと、
該絞り込みステップによってスケジューリング候補を絞り込んだ状態で、前記面積見積もりステップと、前記組合せ算出ステップと、前記絞り込みステップとを、前記ノードとスケジューリング候補との組合せが１になるまで繰り返して、１になったノードとスケジューリング候補との組合せに基づいて該ノードのスケジューリングを行なうステップと、
を包含することを特徴とする高位合成方法。
【請求項５】
前記スケジューリング候補を絞り込む絞り込みステップは、前記組合せ算出ステップによって求められた前記ノードとスケジューリング候補との組合せが複数ある場合に、各組みあわせ毎に、ノードを引数とする評価関数をそれぞれ計算して、計算された評価関数の値が最大となる前記ノードとスケジューリング候補の組合せを除外して、前記組合せを絞り込む、請求項４に記載の高位合成方法。
【請求項６】
前記評価関数が、（（ノードの入力ビット数の総和）−（ノードの出力ビット数の総和））×（スケジューリング候補のタイムステップ）である、請求項５に記載の高位合成方法。
【請求項７】
請求項４から６のいずれかに記載の高位合成方法を実行する高位合成プログラムが記録されているコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動作記述によって表現された回路を合成する高位合成方法に関し、特に、コントロールフローグラフの各ノードをタイムステップに割り当てるスケジューリング方法に関する。
【０００２】
【従来の技術】
従来技術として、コントロールフローグラフの各ノードが各スケジューリング侯補に割り当てられる確率をタイムステップ毎に合計し、その最大値で回路面積（以下、単に「面積」とする。）を見積もり、面積を最小化するようにスケジューリングを行うフォースディレクティッドスケジューリングが「ＨＩＧＨ−ＬＥＶＥＬ  ＳＹＮＴＨＥＳＩＳ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ（Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ）１９９２」に記載されている。
【０００３】
さらに、上記のフォースディレクティッドスケジューリングを改良した技術として、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つ各ノード（Ｂ）に対し、ノード（Ｂ）を候補（Ａ）から除外した状態で面積を見積もり、面積が最小となるノード（Ｃ）と候補（Ｄ）の組合せを求め、候補（Ｄ）をノード（Ｃ）の候補から除外することにより、徐々にスケジューリング候補を絞り込む方法が、特開平９−８１６０５号公報に記載されている。この特開平９−８１６０５号公報に記載の技術は、フォースディレクティッドスケジューリングにおいて、ノードをタイムステップに一度に割り当ててしまうことにより最適なタイムステップをスケジューリング候補から除外してしまい、局所解に陥るのを防ぐために、スケジューリング候補を徐々に絞り込むことにより、より良いスケジューリング結果を得ようとするものである。
【０００４】
【発明が解決しようとする課題】
上記の特開平９−８１６０５号公報の記載によれば、各ノードがスケジューリング候補に割り当てられる確率をタイムステップ毎に合計したものが最大となるタイムステップにスケジューリング候補（Ａ）を持つノード（Ｂ）に対し、ノード（Ｂ）を候補（Ａ）から除外した状態で面積を見積もっている。そのため、見積もり値の正確さが十分ではなく、最適なタイムステップをスケジューリング候補から除外してしまい局所解に陥る可能性が高い。
【０００５】
また、特開平９−８１６０５号公報の記載においては、レジスタの面積を考慮していないため、演算器の面積が小さくなってもレジスタの面積が大きくなり、全体の回路の面積が大きくなる可能性が高い。
【０００６】
上記の問題点を解決すべく、本発明は、高速かつ有効な面積の見積もりを行う高位合成のスケジューリング方法、および、レジスタの面積を考慮した高速な高位合成のスケジューリング方法を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明の高位合成装置は、コントロールフローグラフの各ノードが各スケジューリング候補に割り当てられる確率をタイムステップ毎に合計し、その合計の最大値で面積を見積もって、見積もられた面積を最小化するようにスケジューリングを行う高位合成装置であって、前記確率の合計が最大となるタイムステップにスケジューリング候補を持つ各ノードのそれぞれを該スケジューリング候補に仮割当した状態におけるそれぞれの面積を見積もる面積見積もり手段と、該面積見積もり手段による見積もりの結果、見積もり面積が最大となる仮割当のノードとスケジューリング候補との組合せを求める組合せ算出手段と、
該組合せ算出手段によって求められた仮割当のノードとスケジューリング候補との組合せにおけるスケジューリング候補を、該組合せにおけるノードに対するスケジューリング候補から除外することによりスケジューリング候補を絞り込む絞り込み手段とを備え、該絞り込み手段によってスケジューリング候補が絞り込まれた状態で、前記面積見積もり手段と、前記組合せ算出手段と、前記絞り込み手段とによる前記スケジューリング候補の絞り込みを、前記ノードおよびスケジューリング候補の組合せが１になるまで繰り返して、１になったノードとスケジューリング候補との組合せに基づいて該ノードのスケジューリングを行なうことを特徴とする。
前記スケジューリング候補を絞り込む絞り込み手段は、前記組合せ算出手段によって求められた前記ノードとスケジューリング候補の組合せが複数ある場合に、各組みあわせ毎に、ノードを引数とする評価関数を計算して、計算された該評価関数の値が最大となるノードとスケジューリング候補の組合せを除外して、前記組合せを絞り込む構成であってもよい。
前記評価関数が、（（ノードの入力ビット数の総和）−（ノードの出力ビット数の総和））×（スケジューリング候補のタイムステップ）であってもよい。
本発明の高位合成方法は、前記高位合成装置によって実施される高位合成方法であって、前記面積見積もり手段によって、前記確率の合計が最大となるタイムステップにスケジューリング候補を持つ各ノードのそれぞれを対応するスケジューリング候補に仮割当した状態におけるそれぞれの面積を見積もる面積見積もりステップと、前記組合せ算出手段によって、前記面積見積もりステップでの面積の見積もり結果から、見積もり面積が最大となる仮割当のノードとスケジューリング候補との組合せを求める組合せ算出ステップと、前記絞り込み手段によって、該組合せ算出ステップで求められた仮割当のノードとスケジューリング候補との組合せにおけるスケジューリング候補を、該組合せにおけるノードに対するスケジューリング候補から除外することによりスケジューリング候補を絞り込む絞り込みステップと、該絞り込みステップによってスケジューリング候補を絞り込んだ状態で、前記面積見積もりステップと、前記組合せ算出ステップと、前記絞り込みステップとを、前記ノードとスケジューリング候補との組合せが１になるまで繰り返して、１になったノードとスケジューリング候補との組合せに基づいて該ノードのスケジューリングを行なうステップと、を包含することを特徴とする。
【０００８】
前記スケジューリング候補を絞り込む絞り込みステップは、前記組合せ算出ステップによって求められた前記ノードとスケジューリング候補との組合せが複数ある場合に、各組みあわせ毎に、ノードを引数とする評価関数をそれぞれ計算して、計算された評価関数の値が最大となる前記ノードとスケジューリング候補の組合せを除外して、前記組合せを絞り込んでもよい。
【０００９】
前記評価関数が、（（ノードの入力ビット数の総和）−（ノードの出力ビット数の総和））×（スケジューリング候補のタイムステップ）であってもよい。
【００１０】
本発明の記録媒体は、前記高位合成方法を実行する高位合成プログラムが記録されているコンピュータ読み取り可能な記録媒体である。
【００１１】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
【００１２】
図１は、本発明の実施の形態におけるスケジューリング方法のフローチャートである。図１に示されるフローチャートの各ステップについて説明する。
【００１３】
ＡＳＡＰスケジューリング（１）においては、各ノードを依存関係を満たす範囲でできるだけ早いタイムステップに割り当てる。ＡＳＡＰスケジューリング結果の例を図２に示す。図２において、各タイムステップには早い順に丸数字の１〜５の番号が付けられ、各ノードには四角数字の１〜５の番号が付けられている。図２に示す例では、ノード２，５が最も早いタイムステップ１に割り当てられ、ノード１，３がタイムステップ２に割り当てられ、ノード４がタイムステップ３に割り当てられている。
【００１４】
次に、ＡＬＡＰスケジューリング（２）においては、各ノードを依存関係を満たす範囲でできるだけ遅いタイムステップに割り当てる。ＡＬＡＰスケジューリング結果の例を図３に示す。図３に示す例では、ノード１，４が最も遅いタイムステップ５に割り当てられ、ノード３，５がタイムステップ４に割り当てられ、ノード２がタイムステップ３に割り当てられている。
【００１５】
ＡＳＡＰスケジューリングとＡＬＡＰスケジューリングの結果、各ノードの最初のスケジューリング候補が定まる。図４は、最初のスケジューリング候補を示す。例えば、ノード１はＡＳＡＰスケジューリングではタイムステップ２に割り当てられ、ＡＬＡＰスケジューリングではタイムステップ５に割り当てられている。そのため、図４の黒四角記号によって示されるように、ノード１は、タイムステップ２から５のいずれかに割り当てられる可能性がある。図４は、ノード２〜５についても同様に最初のスケジューリング候補を示している。
【００１６】
次に、各ノードの確率の算出（３）においては、各ノードが各タイムステップに割り当てられる確率を算出する。図４において、例えばノード１は４つのタイムステップ２〜５のいずれかに割り当てられる可能牲があるため、それぞれ確率１／４が与えられる。図５は、このようにして算出した各ノードの確率例を示す。
【００１７】
次に、タイムステップ毎の確率の合計の算出（４）においては、前記各ノードの確率をタイムステップ毎に合計する。図６は、タイムステップ毎の確率の合計の算出例を示す。例えば、タイムステップ１について考えると、ノード２がタイムステップ１に割り当てられる確率は１／３であり、ノード５がタイムステップ１に割り当てられる確率は１／４であるから、タイムステップ１の確率の合計は、１／３＋１／４＝０．５８となる。図６には、同様に算出した各タイムステップについての確率の合計が示されている。
【００１８】
次に、確率の合計の最大値の算出（５）においては、前記タイムステップ毎の確率の合計の最大値を算出する。図６の例においては、０．５８、１．１６、１．５、１．１６、０．５８の最大値は１．５であるため、確率の合計の最大値は１．５となる。図６においては、タイムステップ３の確率の合計値１．５を丸で囲むことにより、これを示している。
【００１９】
次に、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つノード（Ｂ）と候補（Ａ）の組合せの検索（６）においては、前記確率の合計の最大値を与えるタイムステップにスケジューリング候補を持つノードを検索し、ノードとステップの組合せを求める。
【００２０】
図７は、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つノード（Ｂ）と候補（Ａ）の組合せの検索例を示す。上述の例においては、確率の合計が最大となるのはタイムステップ３であるため、タイムステップ３にスケジューリング候補を持つノード（ノード１から５全て）が検索される。その結果、組合せ（ノード１、タイムステップ３）、（ノード２、タイムステップ３）、（ノード３、タイムステップ３）、（ノード４、タイムステップ３）、（ノード５、タイムステップ３）が得られる。
【００２１】
次に、各組合せに対する、ノード（Ｂ）の候補（Ａ）への仮割当と、面積の見積もり（７）においては、前記各組合せに対し、ノードを候補へ仮割当して面積を見積もる。
【００２２】
図８は、ノード１をタイムステップ３に仮割当する例を示す。仮割当の結果、ノード１がタイムステップ２、４、５、ノード２がタイムステップ３に割り当てられる可能性がなくなるため、これらを一時的にスケジューリング候補から除外し、面積を見積もる。なお、同様に、ノード２をタイムステップ３に仮割当する例を図１６に、ノード３をタイムステップ３に仮割当する例を図１７に、ノード４をタイムステップ３に仮割当する例を図１８に、ノード５をタイムステップ３に仮割当する例を図１９に示す。
【００２３】
図９は、面積見積もりのフローチャートを示す。図９のフローチャートで、仮割当後の各ノードの確率の算出（１３）においては、仮割当を行い、一時的にスケジューリング候補を絞り込んだ状態で各ノードの確率を算出する。次に、タイムステップ毎の確率の合計の算出（１４）においては、仮割当後の各ノードの確率をタイムステップ毎に合計する。次に、確率の合計の最大値の算出（１５）においては、合計した確率の最大値を算出する。この最大値が、面積の見積もり値となる。
【００２４】
図１０は、ノード１をタイムステップ３に仮割当した場合の面積見積もりの例を示す。上述の例においては、面積の見積もり値は１．９１となる。なお、同様に、ノード２をタイムステップ３に仮割当した場合の面積見積もりの例を図２０に、ノード３をタイムステップ３に仮割当した場合の面積見積もりの例を図２１に、ノード４をタイムステップ３に仮割当した場合の面積見積もりの例を図２２に、ノード５をタイムステップ３に仮割当した場合の面積見積もりの例を図２３に示す。
【００２５】
図１のフローチャートに戻って、最も面積が大きくなるノードと候補の組合せの検索（８）においては、前記仮割当および面積見積もりの結果、最も面積が大きくなるものを検索し、その最大値を与える仮割当のノードとスケジューリング候補を検索する。図７においては、ノード１をタイムステップ３に割り当てた時と、ノード５をタイムステップ３に割り当てた時の見積もり面積が最大（１．９１）となるため、検索結果は（ノード１、タイムステップ３）、（ノード５、タイムステップ３）となる。
【００２６】
次に、前記最も面積が大きくなるノードと候補の組合せの検索（８）において検索された組合せが複数あるか否かの判定（１７）を行う。組合せが複数ある場合には、各組合せに対する評価関数の算出（９）に進み、組合せが１つである場合には、候補（Ｄ）の、ノード（Ｃ）のスケジューリング候補からの除外（１１）に進む。
【００２７】
各組合せに対する評価関数の算出（９）においては、複数の組合せが検索された場合に各組合せに対して評価関数を算出する。
【００２８】
各組合せに対する評価関数の算出（９）について、図７の例で説明する。上記のように、ノード１をタイムステップ３に仮割当した場合（図１０）と、ノード５をタイムステップ３に仮割当した場合（図２３）とでは、見積もり面積結果は等しくなる（１．９１）ため、前記最も面積が大きくなるノードと候補の組合せの検索（８）において２つの組合せが検索される。そこで、各組合せに対して評価関数を算出する。ここでは評価関数を、
（（ノードの入力数）−（ノードの出力数））×（候補のタイムステップ）
とする。図２（又は図３）に示すように、ノード１の入力数は１、出力数は１であり、ノード５の入力数は２、出力数は１である。ノード１をタイムステップ３に仮割当した場合の評価関数の値は、（１−１）×３＝０となる。ノード５をタイムステップ３に仮割当した場合の評価関数の値は、（２−１）×３＝３となる。なお、評価関数の算出については、図１１を参照してさらに後述する。
【００２９】
次に、評価関数の値が最も大きくなるノード（Ｃ）と侯補（Ｄ）の組合せの検索（１０）においては、前記各組合せに対する評価関数の算出（９）で算出した評価関数の値の最大値を求め、その最大値を与えるノードと候補の組合せを求める。図７の例においては、ノード５をタイムステップ３に仮割当した場合の評価関数の値３が最大となるため、検索結果は（ノード５、タイムステップ３）となる。
【００３０】
前記各組合せに対する評価関数の算出（９）および前記評価関数の値が最も大きくなるノード（Ｃ）と候補（Ｄ）の組合せの検索（１０）は、前記最も面積が大きくなるノードと候補の組合せの検索（８）において複数の組合せが検索された場合にのみ実行される。
【００３１】
次に、候補（Ｄ）の、ノード（Ｃ）のスケジューリング候補からの除外（１１）においては、上述した仮割当および評価関数による検索により最終的に求められた、ノード（Ｃ）とスケジューリング候補（Ｄ）の組合せに対し、候補（Ｄ）をノード（Ｃ）のスケジューリング候補から除外する。図１２は、ノード５のタイムステップ３への割当てが除外された例を示す。
【００３２】
前記（３）から（１１）を、各ノードのスケジューリング侯補数が１となり、全てのノードのスケジューリングが決定されるまで繰り返す。図１３に、全てのノードのスケジューリング侯補数が１となった状態の例を示す。図１４に、最終的なスケジューリング結果の例を示す。
【００３３】
次に、本発明におけるレジスタ面積の考慮方法を説明する。
【００３４】
図１５は、レジスタを考慮したスケジューリングのための説明図である。図１５の例において、（Ａ）の加算ノードが、（Ｂ）のようにコントロールステップ２にスケジューリングされる場合、加算ノードの入力に接続された２つの枝のライフタイムはタイムステップの１から２までを占め、加算ノードの出力に接続された１つの枝のライフタイムはタイムステップの２から６までを占める。（Ａ）の加算ノードが、（Ｃ）のようにコントロールステップ５にスケジューリングされる場合、加算ノードの入力に接続された２つの枝のライフタイムはタイムステップの１から５までを占め、加算ノードの出力に接続された１つの枝のライフタイムはタイムステップの５から６までを占める。
【００３５】
すなわち、（Ｂ）のスケジューリングでは２つのライフタイムが１ステップの区間を占め、１つのライフタイムが４ステップの区間を占めるが、（Ｃ）のスケジューリングでは２つのライフタイムが４ステップの区間を占め、１つのライフタイムが１ステップの区間を占める。よって、（Ｂ）のスケジューリングの方が、（Ｃ）のスケジューリングよりもレジスタの数が少なくなる可能性が高い。
【００３６】
図１１は、評価関数算出のための説明図である。スケジューリングの過程において、図１１に示すようにノード１をタイムステップ４に仮割当した場合と、ノード１をタイムステップ５に仮割当した場合と、ノード４をタイムステップ４に仮割当した場合と、ノード４をタイムステップ５に仮割当した場合とで、見積もり面積が等しくなったとする。その場合、各組合せに対し評価関数を算出する。ノード１をタイムステップ４に仮割当した場合の評価関数の値は、（１−１）×４＝０となる。ノード１をタイムステップ５に仮割当した場合の評価関数の値は、（１−１）×５＝０となる。ノード４をタイムステップ４に仮割当した場合の評価関数の値は、（２−１）×４＝４となる。ノード４をタイムステップ５に仮割当した場合の評価関数の値は、（２−１）×５＝５となる。
【００３７】
評価関数の値が最も大きくなるノード（Ｃ）と候補（Ｄ）の組合せの検索（１０）において、評価関数の最大値を与えるノードと候補の組合せを求め、候補（Ｄ）をノード（Ｃ）のスケジューリング候補から除外する。図１１の例では、ノード４の、タイムステップ５への割当が除外される。これにより、入力数が出力数より多いノード４は、入力数と出力数が等しいノード１に比べて早いタイムステップに割り当てられる。
【００３８】
このように、本発明によれば、ノードの入力ビット数の総和が出力ビット数の総和より小さい場合は、面積が同じ場合、より遅いタイムステップにスケジューリングされ、ノードの入力ビット数の総和が出力ビット数の総和より大きい場合は、面積が同じ場合、より早いタイムステップにスケジューリングされる。これにより、必要となるレジスタ数が少なくなる可能性が高くなり、レジスタを考慮したスケジューリングを行うことができる。
【００３９】
以上に説明した本発明の高位合成方法を実行するプログラムは、磁気ディスク、光ディスク等の任意の記録媒体に記録され得る。
【００４０】
最後に、本発明と従来技術との違いを、図１６、図２０、図２４、図２５を参照して説明する。ここでは、従来技術の例として特開平９−８１６０５号公報に記載の技術との違いを説明する。
【００４１】
本発明においては、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つ各ノード（Ｂ）に対し、ノード（Ｂ）を候補（Ａ）に仮割当した状態で面積を見積もる。図１６は、ノード２をタイムステップ３へ仮割当した状態でのスケジューリング候補を示す。図２０は、ノード２をタイムステップ３へ仮割当した状態での面積見積もりを示す。
【００４２】
一方、特開平９−８１６０５号公報に記載されている技術によれば、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つ各ノード（Ｂ）に対し、ノード（Ｂ）を候補（Ａ）から除外した状態で面積を見積もる。図２４は、ノード２のタイムステップ３への割当てを除外した状態でのスケジューリング候補を示す。図２５は、ノード２のタイムステップ３への割当てを除外した状態での面積見積もりを示す。
【００４３】
図２４と図１６とを比較すると、図１６の方がトータルのスケジューリング候補数が少なくなっている。これは、図１６の方が、より、最終的なスケジューリング結果（図１３）に近いことを示す。これにより、本発明は、特開平９−８１６０５に記載されている発明と比較して、より正確な面積見積もりを行うことができ、より良いスケジューリング結果を得られる可能性が高いと言える。
【００４４】
また、特開平９−８１６０５に記載されている技術によれば、レジスタの面積を考慮したスケジューリングを行うことができないが、上述したように、本発明によれば、レジスタの面積を考慮したスケジューリングを行うことができる。
【００４５】
【発明の効果】
本発明の高位合成方法および高位合成プログラムを記録した記録媒体によれば、コントロールフローグラフの各ノードが各スケジューリング候補に割り当てられる確率をタイムステップ毎に合計し、確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つ各ノード（Ｂ）に対し、ノード（Ｂ）を候補（Ａ）に仮割当した状態で面積を見積もることにより、より最終的なスケジューリング結果に近い状態で面積を見積もることができ、最適なタイムステップをスケジューリング候補から除外してしまい局所解に陥る可能性を低くすることができる。
【００４６】
また、本発明の高位合成方法によれば、見積もり面積が最大となるノードとスケジューリング候補の組合せが複数ある場合、各ノードを引数とする評価関数を計算し、評価値が最大となるノード（Ｅ）と候補（Ｆ）の組合せを検索して、候補（Ｆ）をノード（Ｅ）の候補から除外することにより、最終的に面積が同じになる複数のスケジューリング結果のうち、評価関数にしたがってより目的に近いスケジューリング結果が得られる。
【００４７】
さらに、本発明の高位合成方法によれば、ノードの入力ビット数の総和が出力ビット数の総和より小さい場合は、面積が同じ場合、より遅いタイムステップにスケジューリングされ、ノードの入力ビット数の総和が出力ビット数の総和より大きい場合は、面積が同じ場合、より早いタイムステップにスケジューリングされる。これにより、必要となるレジスタ数が少なくなる可能性が高くなり、レジスタを考慮したスケジューリングを高速に行うことができる。
【図面の簡単な説明】
【図１】本発明の実施の形態におけるスケジューリング方法のフローチャートである。
【図２】ＡＳＡＰスケジューリング結果の例を示す図である。
【図３】ＡＬＡＰスケジューリング結果の例を示す図である。
【図４】ＡＳＡＰ、ＡＬＡＰスケジューリング結果定まった、最初のスケジューリング候補の例を示す図である。
【図５】各ノードが各タイムステップに割り当てられる確率の算出例を示す図である。
【図６】タイムステップ毎の確率の合計と、その最大値の算出例を示す図である。
【図７】確率の合計が最大となるタイムステップにスケジューリング候補（Ａ）を持つノード（Ｂ）と候補（Ａ）の組合せの検索例を示す図である。
【図８】各ノードの各タイムステップヘの仮割当の例を示す図である。
【図９】面積見積もりのフローチャートである。
【図１０】仮割当後の面積見積もり結果の例を示す図である。
【図１１】評価関数算出のための説明図である、
【図１２】スケジューリング候補の除外例を示す図である。
【図１３】全てのノードのスケジューリング候補数が１となった状態の例を示す図である。
【図１４】最終的なスケジューリング結果の例を示す図である。
【図１５】レジスタを考慮したスケジューリングのための説明図である。
【図１６】各ノードの各タイムステップヘの仮割当の例を示す図である。
【図１７】各ノードの各タイムステップヘの仮割当の例を示す図である。
【図１８】各ノードの各タイムステップヘの仮割当の例を示す図である。
【図１９】各ノードの各タイムステップヘの仮割当の例を示す図である。
【図２０】仮割当後の面積見積もり結果の例を示す図である。
【図２１】仮割当後の面積見積もり結果の例を示す図である。
【図２２】仮割当後の面積見積もり結果の例を示す図である。
【図２３】仮割当後の面積見積もり結果の例を示す図である。
【図２４】従来技術における、ノードのタイムステップヘの割当てを除外した状態でのスケジューリング候補を示す図である。
【図２５】従来技術における、ノードのタイムステップヘの割当てを除外した状態での面積見積もりの例を示す図である。
【符号の説明】
１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１７  ステップ
【図１】
0003717144.tif 000002
【図２】
0003717144.tif 000003
【図３】
0003717144.tif 000004
【図４】
0003717144.tif 000005
【図５】
0003717144.tif 000006
【図６】
0003717144.tif 000007
【図７】
0003717144.tif 000008
【図８】
0003717144.tif 000009
【図９】
0003717144.tif 000010
【図１０】
0003717144.tif 000011
【図１１】
0003717144.tif 000012
【図１２】
0003717144.tif 000013
【図１３】
0003717144.tif 000014
【図１４】
0003717144.tif 000015
【図１５】
0003717144.tif 000016
【図１６】
0003717144.tif 000017
【図１７】
0003717144.tif 000018
【図１８】
0003717144.tif 000019
【図１９】
0003717144.tif 000020
【図２０】
0003717144.tif 000021
【図２１】
0003717144.tif 000022
【図２２】
0003717144.tif 000023
【図２３】
0003717144.tif 000024
【図２４】
0003717144.tif 000025
【図２５】
0003717144.tif 000026