(57)【要約】【課題】リソースアクセスに競合が生じないように、動作合成のループ処理をパイプライン化する。【解決手段】動作記述からＲＴＬ記述を自動生成する動作合成装置１０は、動作記述中のループ処理内に同一リソースへのアクセスが複数含まれる場合に、そのループ処理がパイプライン化されても、そのリソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理するリソースアクセス調停手段１２を有している。このリソースアクセス調停手段１２は、ループ処理内の同一リソースへの複数アクセスに対して、それらのアクセスの実行サイクルを変数として求める線形計画問題について、その制約条件として変数間の制約式を与えるかまたは、それらのアクセスの処理手順を表す制約グラフについて、その制約条件として節点間の制約枝を与える。【選択図】図１
2009025973.tif 000002
【特許請求の範囲】
【請求項１】
ハードウェアの構造に関する情報を含まず、処理手順のアルゴリズムのみが記述された動作記述から回路の動作合成を行ってＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ）記述情報を自動生成する動作合成装置において、
該動作記述中のループ処理内に同一リソースへのアクセスが複数含まれる場合に、該ループ処理がパイプライン化されても、該同一リソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理するリソースアクセス調停手段を有する動作合成装置。
【請求項２】
前記リソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を与える請求項１に記載の動作合成装置。
【請求項３】
前記リソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの演算が節点で表され、該複数アクセスの演算を実行する時間制約が枝で表された制約グラフについて、前記制約条件として当該節点間の制約枝を与える請求項１に記載の動作合成装置。
【請求項４】
前記制約条件は、前記同一リソースにアクセスする複数のリソースアクセス節点のうち、時間的に隣接するリソースアクセス節点は１サイクルまたは２サイクル以上時間を空けて実行されるように設定され、かつ、パイプライン化後にリソースアクセスの競合が生じないように該リソースアクセス節点は複数、同一サイクルで実行しないように設定される請求項１〜３のいずれかに記載の動作合成装置。
【請求項５】
前記リソースアクセス調停手段は、ＡＳＡＰ（Ａｓ  Ｓｏｏｎ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングおよびＡＬＡＰ（Ａｓ  Ｌａｔｅ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングを用いて、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理手段と、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のうち、所定の複数節点よりなるリソースアクセス組を選択するリソースアクセス組選択処理手段と、求めたスケジューリング可能範囲を用い、該リソースアクセス組として選択された所定の複数リソースアクセス節点に対して、リソースアクセスの競合が起きないようにするための前記制約条件を線形計画問題により取り扱い可能な制約条件として制約式に変換する制約式決定処理手段とを有する請求項１〜４のいずれかに記載の動作合成装置。
【請求項６】
前記所定の複数節点よりなるリソースアクセス組は、２つのリソースアクセス節点の組である請求項５に記載の動作合成装置。
【請求項７】
前記制約式決定処理手段による制約式の決定後、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点全てのリソースアクセス節点の組が選択されたか否かを判断し、該全てのリソースアクセス節点の組が選択された場合に制約式決定処理を終了し、該全てのリソースアクセス節点の組が選択されていない場合には、前記リソースアクセス組選択処理手段および前記制約式決定処理手段による各処理を再び実行させる繰り返し手段を更に有する請求項５に記載の動作合成装置。
【請求項８】
前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、
前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、前記条件式として該第１制約式および第２制約式に基づいて調停処理を行う請求項７に記載の動作合成装置。
【請求項９】
前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、
前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃ，Ｄがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、
該繰り返し手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂ，Ｃの他にリソースアクセス節点Ｄがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｃ，Ｄを選択し、該制約式決定処理手段により該２つのリソースアクセス節点Ｃ，Ｄに対して第３制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式、第２制約式および第３制約式に基づいて調停処理を行う請求項７に記載の動作合成装置。
【請求項１０】
前記制約式決定処理手段は、前記同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２について、パイプライン化前の実行サイクルをＳ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｔｐはスループットの値、ｎは整数）
を線形計画問題により取り扱い可能なように、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋ｔｐ×ｍ＋１（定数ｍは整数）
Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１
に変換してこれを前記制約式とする請求項５および７〜９のいずれかに記載の動作合成装置。
【請求項１１】
前記定数ｍを、
ｍ＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ）
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝（Ｓ＿ａｌａｐ（Ｒ２）＋Ｓ＿ａｓａｐ（Ｒ２））／２−（Ｓ＿ａｌａｐ（Ｒ１）＋Ｓ＿ａｓａｐ（Ｒ１））／２
により求める請求項１０に記載の動作合成装置。
但し、ｉｎｔ；引数の値を越えない整数を返す関数
Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の平均値
【請求項１２】
前記定数ｍを、
（Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＋１）／ｔｐ−１≦ｍ≦（Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）−１）／ｔｐ
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＝Ｓ＿ａｓａｐ（Ｒ２）−Ｓ＿ａｌａｐ（Ｒ１）
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）＝Ｓ＿ａｌａｐ（Ｒ２）−Ｓ＿ａｓａｐ（Ｒ１）
により求める請求項１０に記載の動作合成装置。
但し、Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最小値
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最大値
【請求項１３】
前記リソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を満たすように、最長経路法によりスケジューリングを求める請求項２に記載の動作合成装置。
【請求項１４】
前記リソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの処理手順を示す制約グラフを用いて最長経路法によりスケジューリングを求める請求項３に記載の動作合成装置。
【請求項１５】
前記動作記述から、データが枝で表され、演算が節点で表されたデータフローグラフを生成するデータフローグラフ生成手段と、
前記リソースアクセス調停手段によるリソースアクセス調停処理結果を用いて、複数のリソースアクセス節点を含むデータフローグラフ中の各節点をいつ実行するかを決定するスケジューリング手段と、
該データフローグラフ中の各枝で表されるデータを格納するためのレジスタを決定すると共に、該データフローグラフ中の節点で表される演算をどの演算器を用いて行うかを決定するアロケーション手段と、
スケジューリング結果とアロケーション結果を元に、演算器とレジスタを挿入し、必要に応じてセレクタを挿入してデータパスを生成するデータパス生成手段と、
該スケジューリング結果と該アロケーション結果を元に、データパス中に含まれるレジスタと必要に応じて挿入されるセレクタを制御するステートマシンを生成するコントローラ生成手段とを有する請求項１に記載の動作合成装置。
【請求項１６】
請求項１〜１５のいずれかに記載の動作合成装置によりリソースアクセス調停処理が施された論理回路を設計し、設計された論理回路情報によりパターニングされたレジストパターンを用いて、半導体基板上または基板に設けられた半導体層上に半導体集積回路を形成する半導体集積回路の製造方法。
【請求項１７】
ハードウェアの構造に関する情報が含まれず、処理手順のアルゴリズムのみが記述された動作記述から回路の動作合成を行ってＲＴＬ（（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ））記述情報を自動生成する動作合成方法において、
該動作記述中のループ内に同一リソースへのアクセスが複数含まれる場合に、該ループ処理がパイプライン化されても、リソースアクセス調停手段が、該同一リソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理するリソースアクセス調停工程を有する動作合成方法。
【請求項１８】
前記リソースアクセス調停工程において、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を与える請求項１７に記載の動作合成方法。
【請求項１９】
前記リソースアクセス調停工程において、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの演算が節点で表され、該複数アクセスの演算を実行する時間制約が枝で表された制約グラフについて、前記制約条件として当該節点間の制約枝を与える請求項１７に記載の動作合成方法。
【請求項２０】
前記制約条件としてとして、前記同一リソースにアクセスする複数のリソースアクセス節点のうち、時間的に隣接するリソースアクセス節点は１サイクルまたは２サイクル以上時間を空けて実行されるように設定し、かつ、パイプライン化後にリソースアクセスの競合が生じないように該リソースアクセス節点は複数、同一サイクルで実行しないように設定する請求項１７〜１９のいずれかに記載の動作合成方法。
【請求項２１】
前記リソースアクセス調停工程は、ＡＳＡＰ・ＡＬＡＰスケジューリング処理手段が、ＡＳＡＰスケジューリングおよびＡＬＡＰスケジューリングを用いて、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理工程と、リソースアクセス組選択処理手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のうち、所定の複数節点よりなるリソースアクセス組を選択するリソースアクセス組選択処理工程と、制約式決定処理手段が、求めたスケジューリング可能範囲を用い、該リソースアクセス組として選択された所定の複数リソースアクセス節点に対して、リソースアクセスの競合が起きないようにするための前記制約条件を線形計画問題により取り扱い可能な制約条件として制約式に変換する制約式決定処理工程とを有する請求項１７〜２０のいずれかに記載の動作合成方法。
【請求項２２】
前記制約式決定処理工程における制約式の決定後、繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点全てのリソースアクセス節点の組が選択されたか否かを判断し、該全てのリソースアクセス節点の組が選択された場合に制約式決定処理を終了し、該全てのリソースアクセス節点の組が選択されていない場合には、前記リソースアクセス組選択処理工程および前記制約式決定処理工程による各処理を再び実行させる繰り返し工程を更に有する請求項２１に記載の動作合成方法。
【請求項２３】
前記リソースアクセス組選択処理工程において、前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、
前記繰り返し工程において、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式および第２制約式に基づいて調停処理を行う請求項２２に記載の動作合成方法。
【請求項２４】
前記リソースアクセス組選択処理工程において、前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、
前記繰り返し工程において、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃ，Ｄがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、
該繰り返し工程において、該繰り返し手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂ，Ｃの他にリソースアクセス節点Ｄがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｃ，Ｄを選択し、該制約式決定処理工程において、該制約式決定処理手段により該２つのリソースアクセス節点Ｃ，Ｄに対して第３制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式、第２制約式および第３制約式に基づいて調停処理を行う請求項２２に記載の動作合成方法。
【請求項２５】
前記制約式決定処理工程は、前記同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２について、パイプライン化前の実行サイクルをＳ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｔｐはスループットの値、ｎは整数）
を線形計画問題により取り扱い可能なように、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋ｔｐ×ｍ＋１（定数ｍは整数）
Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１
に変換してこれを前記制約式とする請求項２１〜２４のいずれかに記載の動作合成方法。
【請求項２６】
前記定数ｍを、
ｍ＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ）
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝（Ｓ＿ａｌａｐ（Ｒ２）＋Ｓ＿ａｓａｐ（Ｒ２））／２−（Ｓ＿ａｌａｐ（Ｒ１）＋Ｓ＿ａｓａｐ（Ｒ１））／２
により求める請求項２５に記載の動作合成方法。
但し、ｉｎｔ；引数の値を越えない整数を返す関数
Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の平均値
【請求項２７】
前記定数ｍを、
（Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＋１）／ｔｐ−１≦ｍ≦（Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）−１）／ｔｐ
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＝Ｓ＿ａｓａｐ（Ｒ２）−Ｓ＿ａｌａｐ（Ｒ１）
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）＝Ｓ＿ａｌａｐ（Ｒ２）−Ｓ＿ａｓａｐ（Ｒ１）
により求める請求項２５に記載の動作合成方法。
但し、Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最小値
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最大値
【請求項２８】
前記リソースアクセス調停工程は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を満たすように、最長経路法によりスケジューリングを求める請求項１８に記載の動作合成方法。
【請求項２９】
前記リソースアクセス調停工程は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの処理手順を示す制約グラフを用いて最長経路法によりスケジューリングを求める請求項１９に記載の動作合成方法。
【請求項３０】
データフローグラフ生成手段が、前記動作記述から、データが枝で表され、演算が節点で表されたデータフローグラフを生成するデータフローグラフ生成工程と、
スケジューリング手段が、前記リソースアクセス調停工程により得たリソースアクセス調停処理結果を用いて、複数のリソースアクセス節点を含むデータフローグラフ中の各節点をいつ実行するかを決定するスケジューリング工程と、
アロケーション手段が、該データフローグラフ中の各枝で表されるデータを格納するためのレジスタを決定すると共に、該データフローグラフ中の節点で表される演算をどの演算器を用いて行うかを決定するアロケーション工程と、
データパス生成手段が、スケジューリング結果とアロケーション結果を元に、演算器とレジスタを挿入し、必要に応じてセレクタを挿入してデータパスを生成するデータパス生成工程と、
コントローラ生成手段が、該スケジューリング結果と該アロケーション結果を元に、データパス中に含まれるレジスタと必要に応じて挿入されるセレクタを制御するステートマシンを生成するコントローラ生成工程とを有する請求項１７に記載の動作合成方法。
【請求項３１】
請求項１７〜３０のいずれかに記載の動作合成方法を計算機上で実行するための各処理手順が記述された動作合成制御プログラム。
【請求項３２】
請求項３１に記載の動作合成制御プログラムが記録されたコンピュータ読み取り可能な可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理回路などの設計に用いられ、動作記述から論理回路を自動合成する動作合成装置、この動作合成装置を用いた半導体集積回路の製造方法、この動作合成装置を用いた動作合成方法、この動作合成方法の各処理をコンピュータに実行させるための動作合成制御プログラムおよびこの動作合成制御プログラムが記録されたコンピュータ読み取り可能な可読記録媒体に関する。
【背景技術】
【０００２】
システムＬＳＩなどのような大規模回路の設計においては、回路の動作記述からＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ）記述を生成する動作合成が行なわれている。この動作合成は、高位合成とも呼ばれている。
【０００３】
この動作合成では、ハードウェアの構造に関する情報が含まれず、動作合成方法の各処理のアルゴリズムのみが記述された回路の動作記述から、ハードウェアが自動的に回路合成される。
【０００４】
以下に、従来の動作合成技術を用いて、動作記述から回路を自動的に合成する過程について、図９を用いて簡単に説明する。
【０００５】
図９は、従来の動作合成方法の各処理手順を説明するためのフローチャートである。
【０００６】
この従来の動作合成方法は、以下のような処理手順で行なわれる。
【０００７】
まず、図９に示すように、ステップＳ１のデータフローグラフ生成処理では、アルゴリズム記述（動作記述）におけるデータの流れが解析されて、データフローグラフと呼ばれるモデルが作成される。このデータフローグラフは、節点と枝とにより構成されており、動作記述中のデータが枝で表され、各演算がそれぞれ節点で表されている。各節点は、入力枝と出力枝とによって接続され、入力枝は演算に与えられるデータ、出力枝は演算結果のデータを表している。また、各節点には、演算の種類に関する情報も含まれている。
【０００８】
例えば、以下のＣ言語で記述された動作記述は、その一例として、図１０に示すデータフローグラフのように表すことができる。このデータフローグラフは、次の式でも表すことができる。
【０００９】
ｘ＝ａ×ｂ＋ｂ×ｃ；
図１０に示すデータフローグラフは、２つの乗算処理を表す節点１０１および１０２と、これらの後段の１つの加算処理を表す節点１０３とを含み、入力データａ，ｂを乗算した結果と、入力データｂ，ｃを乗算した結果とを加算して、その加算結果を出力データとしてｘに出力するということを表している。
【００１０】
このデータフローグラフは、計算機（コンピュータ）上では、例えば図１１に示すようなデータ構造としても表すことができる。
【００１１】
図１１において、節点はＮｏｄｅ構造体（Ｓｔｒｕｃｔ  Ｎｏｄｅ）により表され、各節点固有の節点番号ｎｏｄｅ＿ｉｄを有する。また、ｉｎ＿ｅｄｇｅ，ｏｕｔ＿ｅｄｇｅ配列には、入力枝と出力枝の枝番号が複数記憶される。図１１の事例の場合には、節点は２入力１出力の演算であり、ｉｎ＿ｅｄｇｅは２つの要素、ｏｕｔ＿ｅｄｇｅは１つの要素を有する。さらに、ｏｐ＿ｔｙｐｅには、加算、減算や乗算などのような演算の具体的な種類を表す番号が記憶される。枝はＥｄｇｅ構造体（ｓｔｒｕｃｔ  Ｅｄｇｅ）により表され、各枝固有の枝番号ｅｄｇｅ＿ｉｄを有する。また、ｆｒｏｍ＿ｎｏｄｅ，ｔｏ＿ｎｏｄｅには、その枝が接続された節点の節点番号が格納される。
【００１２】
これらのデータ構造により、計算機のメモリ上にデータフローグラフにおける各節点間の接続が記憶される。また、データフローグラフ上で、節点を接続する場合や、ある節点の入出力につながる別の節点を見つける場合には、データベースの各要素に節点や枝の番号を登録したり、参照したりすることができる。
【００１３】
以下では、説明を分かり易くするために、データフローグラフを視覚的に表した図１０のような図を用いて、節点を枝で接続したり、節点の上下につながる節点を見つけたりすることにより各処理を説明する。
【００１４】
次に、図９に示すように、ステップＳ１で生成されたデータフローグラフに対して、ステップＳ２のスケジューリング処理、さらにステップＳ３のアロケーション処理が行なわれる。
【００１５】
スケジューリング処理では、データフローグラフ中の各節点をいつ実行するのかその実行タイミングが決定される。これに続くアロケーション処理はバインディングとも呼ばれ、データフローグラフ中の枝が表すデータを格納するレジスタを決定する処理、データフローグラフの節点が表す演算をどの演算器を用いて行なうかを決定する処理が行われる。動作合成方法によっては、アロケーション処理がスケジューリング処理の前に行なわれる場合もある。
【００１６】
その後、ステップＳ４に示すデータパス生成処理では、スケジューリング結果およびアロケーション結果を元に、演算器およびレジスタ、必要に応じてセレクタが挿入されて互いに接続され、データパスが生成される。
【００１７】
さらに、ステップＳ５のコントローラ生成処理では、スケジューリング結果およびアロケーション結果を元に、データパス中のレジスタやセレクタを制御するステートマシン（コントローラ）が生成される。このデータパス生成およびコントローラ生成は、いずれが先に行われてもよい。最後にデータパスとコントローラとが接続されて、所望のハードウェア（回路構成）が得られる。
【００１８】
このように、データフローグラフから回路構成を得る動作合成処理の詳細例は、例えば特許文献１に開示されている。
【００１９】
ところで、実際の論理回路などの回路構成では、動作記述中にループ処理が含まれていることが多い。この動作記述中のループ処理は、多数回、繰り返して実行されるため、回路全体の処理時間のうちの多くは、このループ処理によって占められることになる。よって、回路の各処理を高速化させたい場合には、このループ処理を高速化させることが効果的である。画像処理や音声処理などのように、ある一定の時間内に処理を終える必要がある高速性が要求されるデータ処理回路の場合には、このような高速化は必須である。
【００２０】
この問題を解決するための方法の一つとして、ループ処理をパイプライン化する方法が挙げられる。このループ処理のパイプライン化とは、ループ本体の複数回の実行を並行して行うものである。従来のループ処理のパイプライン化方法の一例が、例えば特許文献２の示されている。
【００２１】
以下に、この特許文献２の示されている従来のループ処理のパイプライン化方法について、簡単に説明する。
【００２２】
例えば、図１２に示すようなループ処理を含む動作記述について考える。このループ処理では、演算（関数）Ｆ（ｉ）、Ｇ（ｉ）、Ｈ（ｉ）およびＫ（ｉ）が、変数ｉをｉ＝１から１ずつインクリメントさせながら例えばｉ＝１０まで行われる。
【００２３】
図１３は、図１２に示す動作記述について、ループ処理をパイプライン化しない場合のデータフローグラフを示す図である。
【００２４】
図１３に示すように、矩形１１０の範囲内の各処理はループ処理を表しており、矩形１１０内のデータフローグラフが繰り返し実行されることを意味している。この矩形１１０の上端と下端にある丸印１１１および１１２はそれぞれ、ループ処理の入力ポートと出力ポートをそれぞれ表しており、図１２の変数ｉに対応している。入力ポートを示す丸印１１１に格納された変数ｉの値がインクリメント演算節点１１３でインクリメントされて変化し、出力ポートを示す丸印１１２に至る。これらの各丸印１１１および１１２は同じ変数を表し、出力ポートの丸印１１２に至ったデータは、次の繰り返しで再び入力ポートの丸印１１１から始められて使用される。図１２に示す動作記述では、変数ｉのみがループ処理内で繰り返し使用されているが、２個以上の変数がループ処理内で繰り返し使用される場合には、入力ポート（丸印１１１）と出力ポート（丸印１１２）の対が、変数の個数分だけそれぞれ必要とされる。
【００２５】
インクリメント演算節点１１３の後段の節点１１４では、終了条件（ｉ＝１０かどうか）の比較が行なわれ、「真」であれば”１”、「偽」であれば”０”が出力される。その後段の節点１１５は、ループ処理の終了を制御するための特別な演算節点であり、節点１１４からの入力が”１”の場合に、コントローラに対してループ処理を終了して次の状態に移行するように指示が行われる。
【００２６】
また、各節点１１６、１１７、１１８および１１９ではそれぞれ、図１２に示す動作記述中の関数演算Ｆ，Ｇ，ＨおよびＫの各処理が行なわれる。それぞれの演算節点には、ｉの値が入力されている。図１３に示すように、各節点１１６、１１７、１１８および１１９それぞれ、上から順に、関数演算Ｆ，Ｇ，ＨおよびＫに順次対応するようにサイクル１，２，３および４にスケジューリングされている。
【００２７】
ループ処理の矩形１１０の外部の節点１２０は、定数を出力する節点であり、まず、変数ｉの初期値が入力ポートの丸印１１１に与えられる。
【００２８】
図１３の事例では、１クロックサイクル目において、１回目のループ処理におけるサイクル１の関数演算Ｆ、即ちＦ（１）が実行される。次に、２クロックサイクル目において、１回目のループ処理におけるサイクル２の関数演算Ｇ、即ちＧ（１）が実行される。さらに、３クロックサイクル目において、１回目のループ処理におけるサイクル３の関数演算Ｈ、即ちＨ（１）が実行される。これに続いて、４クロックサイクル目において、１回目のループ処理におけるサイクル４の関数演算Ｋ、即ちＫ（１）が実行される。
【００２９】
次に、一連の５，６，７および８クロックサイクル目において、２回目のループ処理におけるサイクル１，２，３および４にある、関数演算Ｆ（２），Ｇ（２），Ｈ（２），およびＫ（２）がそれぞれこの順に順次実行される。これによって、最終までの１０回の繰り返し処理を行うためには、４×１０回＝４０クロックサイクルが必要である。この場合、入力に対して、４サイクルに１回データを与えることが可能であり、即ち、本ループ処理のスループットは”４”である。また、１つの入力データを処理するために４サイクルが必要であり、即ち、本ループ処理のレイテンシは”４”である。
【００３０】
このデータフローグラフによりループ処理を表す方法には定まった形式がなく、各文献毎に様々な表記が為されており、図１３の表記もその一例である。
【００３１】
ここで、図１２に示す動作記述のループ処理をパイプライン化する場合について説明する。
【００３２】
ここでは、ループ処理のスループットが”２”、即ちループ処理に対して２サイクルに１回入力が与えられるものとする。パイプライン化されない場合のループ処理のスループットは”４”であるため、２サイクルに１回データを処理するためには、ループ処理のパイプライン段数を２段とする必要がある。よって、ループ処理を１回繰り返すときの処理を２ステージに分けることになる。ここで、ステージとはパイプライン動作する処理の一つのまとまりのことである。
【００３３】
図１２に示す動作記述のループ処理は、パイプライン化されない場合には１回の繰り返し当たりに４サイクルが必要とされるため、２ステージに分けるためには、ループ処理の例えば１サイクル目と２サイクル目を１ステージ、３サイクル目と４サイクル目を２ステージに割り当てればよい。
【００３４】
このループ処理がパイプライン化された論理回路などの回路では、図１４に示すように１０回の繰り返しのループ処理が順次行われる。
【００３５】
まず、サイクル１および２において、関数演算Ｆ（１）と関数演算Ｇ（１）とが順次実行される。
【００３６】
次に、サイクル３では、関数演算Ｈ（１）が実行されるのと同時に、２回目のループ処理の繰り返しが開始されて、最初の段の関数演算Ｆ（２）が実行される。
【００３７】
さらに、サイクル４では、関数演算Ｋ（１）が実行されて１回目のループ処理の繰り返しが終了すると同時に、２回目のループ処理の繰り返しにおける関数演算Ｇ（２）が実行される。
【００３８】
以降、サイクル２ｎ＋１（２＜＝ｎ＜＝９）では、関数演算Ｆ（ｎ＋１）と関数演算Ｈ（ｎ）が同時に実行され、サイクル２ｎ＋２では関数演算Ｇ（ｎ＋１）と関数演算Ｋ（ｎ）が同時に実行される。最後に、サイクル２１において関数演算Ｈ（１０）が、サイクル２２において関数演算Ｋ（１０）が実行されて、この１０回の繰り返しのループ処理は全て終了する。
【００３９】
図１２に示す動作記述を実行する際に、１０回の繰り返しのループ処理がパイプライン化されない場合には、４×１０回＝４０クロックサイクルが必要とされていたが、ループ処理が２段にパイプライン化された場合には、図１４に示すようにサイクル１〜２２の２２クロックサイクルでよい。この場合のスループットは”２”で、レイテンシは”４”である。
【００４０】
図１５は、図１２に示す動作記述のループ処理を従来の方法によりパイプライン化させた場合のデータフローグラフの一例を示す図である。
【００４１】
図１５に示すように、まず、サイクル１で、演算節点１２６によって関数演算Ｆ（１）が実行され、さらにサイクル２で、演算節点１２７によって関数演算Ｇ（１）が実行される。
【００４２】
次に、ループ処理が進められる。このループ処理内部では、２サイクルで１回の処理が行われ、２クロックサイクルに１回入力を受けることができる。ループ処理内には、各ステージの処理が並列に配置されている。サイクル３で、１回目のループ処理の節点１２８と、２回目のループ処理の節点１３６とによって、関数演算Ｈ（１）と関数演算Ｆ（２）とが実行される。これに続いて、サイクル４で、１回目のループ処理の節点１２９と、２回目のループ処理の節点１３７とによって関数演算Ｋ（１）と演算Ｇ（２）が同時に実行される。
【００４３】
このとき、関数演算Ｈ（１）と関数演算Ｋ（１）は、図１２に示す動作記述ではｉ＝１のときの後半部分であり、関数演算Ｆ（２）と関数演算Ｇ（２）はｉ＝２のときの前半部分である。これらの各処理が同時に実行される。このため、ループ処理には、節点１２０および節点１３０によって、関数演算Ｈおよび関数演算Ｋには初期値「１」が、関数演算Ｆおよび関数演算Ｇには初期値「２」が与えられる。
【００４４】
これと同様に、２回目のループ処理では、サイクル５で関数演算Ｈ（２）と関数演算Ｆ（３）、およびサイクル６で関数演算Ｋ（２）と関数演算Ｇ（３）がそれぞれ同時に実行される。
【００４５】
さらに、３回目から８回目の各ループ処理が順次実行された後、９回目および１０回目のループ処理では、サイクル１９で関数演算Ｈ（９）と関数演算Ｆ（１０）、さらに、サイクル２０で演算Ｋ（９）と演算Ｇ（１０）がそれぞれ同時に実行される。節点１１４での比較によってｉ＝１０となって、１０回繰り返しのループ処理が終了して、ループ処理外のサイクル２１へ処理が進められる。
【００４６】
サイクル２１では、演算演算Ｈ（１０）が実行され、さらに、サイクル２２では、演算Ｋ（１０）が実行される。
【００４７】
図１５に示すデータフローグラフ中のループ処理本体（サイクル３〜２０）に対して、その前に実行される部分（サイクル１およびサイクル２）はプロローグ部、その後に実行される部分（サイクル２１およびサイクル２２）はエピローグ部と呼ばれている。
【００４８】
このようなデータフローグラフを作成することによって、ループ処理がパイプライン化されて、高速処理することが可能となる。
【００４９】
さらに、例えば特許文献３には、上記プロローグ部とエピローグ部をなくしてこれをループ処理部内に含めることによって、回路規模を削減することができるループ処理のパイプライン化方法が開示されているが、基本的な動作は上記した場合と同様である。
【特許文献１】特開２００１−２２９２１７号公報
【特許文献２】特開２００１−１４２９３７号公報（図３）
【特許文献３】特開２００４−３２６４６３号公報
【発明の開示】
【発明が解決しようとする課題】
【００５０】
しかしながら、上記各従来技術には、以下のような問題がある。
【００５１】
ループ中の処理に、ＲＡＭやＲＯＭ、レジスタファイル、外部ポートなどのリソースに対するアクセスが含まれる場合、従来のループ処理のパイプライン化方法では、リソースアクセスに衝突（競合）が発生してしまう虞がある。
【００５２】
例えば、図１２に示す回路の動作記述において、関数演算Ｆと関数演算Ｈに同一のＲＡＭからデータを読み書きする記述が含まれるような場合、パイプライン化されない図１３のデータフローグラフでは、ＲＡＭへのアクセスに競合は生じないが、パイプライン化された図１５のデータフローグラフでは、関数演算Ｈと関数演算Ｆとの間で同時に実行されるために、同一のＲＡＭに対して同時に読み書きが行われてリソースアクセスに競合が生じてしまう。
【００５３】
このようなリソースアクセスの競合が発生すると、両方のリソースアクセスを同時に正しく動作させることができず、回路を正しく動作させることができなくなってしまう。
【００５４】
内部に複数のアドレスデコーダを有し、２つ以上のアクセスを同時に受け付けることが可能なマルチポートＲＡＭを用いることにより、リソースアクセスに競合が生じても回路を正しく動作させることができるが、マルチポートＲＡＭは半導体チップ上の占有面積が大きいため、回路の製造コストが高くなってしまう。
【００５５】
本発明は、上記従来の問題を解決するもので、動作記述中のループ処理内に同一リソースへのアクセスが複数含まれる場合に、リソースアクセスに競合が生じないように、ループ処理をパイプライン化させることができる動作合成装置、この動作合成装置を用いた半導体集積回路の製造方法、この動作合成装置を用いた動作合成方法、この動作合成方法の各処理をコンピュータに実行させるための動作合成制御プログラムおよびこの動作合成制御プログラムが記録されたコンピュータ読み取り可能な可読記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００５６】
本発明の動作合成装置は、ハードウェアの構造に関する情報を含まず、処理手順のアルゴリズムのみが記述された動作記述から回路の動作合成を行ってＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ）記述情報を自動生成する動作合成装置において、  該動作記述中のループ処理内に同一リソースへのアクセスが複数含まれる場合に、該ループ処理がパイプライン化されても、該同一リソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理するリソースアクセス調停手段を有するものであり、そのことにより上記目的が達成される。
【００５７】
また、好ましくは、本発明の動作合成装置におけるリソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を与える。
【００５８】
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの演算が節点で表され、該複数アクセスの演算を実行する時間制約が枝で表された制約グラフについて、前記制約条件として当該節点間の制約枝を与える。
【００５９】
さらに、好ましくは、本発明の動作合成装置における制約条件は、前記同一リソースにアクセスする複数のリソースアクセス節点のうち、時間的に隣接するリソースアクセス節点は１サイクルまたは２サイクル以上時間を空けて実行されるように設定され、かつ、パイプライン化後にリソースアクセスの競合が生じないように該リソースアクセス節点は複数、同一サイクルで実行しないように設定される。
【００６０】
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス調停手段は、ＡＳＡＰ（Ａｓ  Ｓｏｏｎ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングおよびＡＬＡＰ（Ａｓ  Ｌａｔｅ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングを用いて、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理手段と、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のうち、所定の複数節点よりなるリソースアクセス組を選択するリソースアクセス組選択処理手段と、求めたスケジューリング可能範囲を用い、該リソースアクセス組として選択された所定の複数リソースアクセス節点に対して、リソースアクセスの競合が起きないようにするための前記制約条件を線形計画問題により取り扱い可能な制約条件として制約式に変換する制約式決定処理手段とを有する。
【００６１】
さらに、好ましくは、本発明の動作合成装置における所定の複数節点よりなるリソースアクセス組は、２つのリソースアクセス節点の組である。
【００６２】
さらに、好ましくは、本発明の動作合成装置において、前記制約式決定処理手段による制約式の決定後、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点全てのリソースアクセス節点の組が選択されたか否かを判断し、該全てのリソースアクセス節点の組が選択された場合に制約式決定処理を終了し、該全てのリソースアクセス節点の組が選択されていない場合には、前記リソースアクセス組選択処理手段および前記制約式決定処理手段による各処理を再び実行させる繰り返し手段を更に有する。
【００６３】
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、さらに、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、前記条件式として該第１制約式および第２制約式に基づいて調停処理を行う。
【００６４】
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、さらに、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃ，Ｄがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、さらに、該繰り返し手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂ，Ｃの他にリソースアクセス節点Ｄがあると判断した場合には、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｃ，Ｄを選択し、該制約式決定処理手段により該２つのリソースアクセス節点Ｃ，Ｄに対して第３制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式、第２制約式および第３制約式に基づいて調停処理を行う。
【００６５】
さらに、好ましくは、本発明の動作合成装置における制約式決定処理手段は、前記同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２について、パイプライン化前の実行サイクルをＳ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｔｐはスループットの値、ｎは整数）
を線形計画問題により取り扱い可能なように、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋ｔｐ×ｍ＋１（定数ｍは整数）
Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１
に変換してこれを前記制約式とする。
【００６６】
さらに、好ましくは、本発明の動作合成装置における定数ｍを、
ｍ＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ）
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝（Ｓ＿ａｌａｐ（Ｒ２）＋Ｓ＿ａｓａｐ（Ｒ２））／２−（Ｓ＿ａｌａｐ（Ｒ１）＋Ｓ＿ａｓａｐ（Ｒ１））／２
により求める。
【００６７】
但し、ｉｎｔ；引数の値を越えない整数を返す関数
Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の平均値
さらに、好ましくは、本発明の動作合成装置における定数ｍを、
（Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＋１）／ｔｐ−１≦ｍ≦（Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）−１）／ｔｐ
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＝Ｓ＿ａｓａｐ（Ｒ２）−Ｓ＿ａｌａｐ（Ｒ１）
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）＝Ｓ＿ａｌａｐ（Ｒ２）−Ｓ＿ａｓａｐ（Ｒ１）
により求める。
【００６８】
但し、Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最小値
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最大値
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を満たすように、最長経路法によりスケジューリングを求める。
【００６９】
さらに、好ましくは、本発明の動作合成装置におけるリソースアクセス調停手段は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの処理手順を示す制約グラフを用いて最長経路法によりスケジューリングを求める。
【００７０】
さらに、好ましくは、本発明の動作合成装置において、前記動作記述から、データが枝で表され、演算が節点で表されたデータフローグラフを生成するデータフローグラフ生成手段と、前記リソースアクセス調停手段によるリソースアクセス調停処理結果を用いて、複数のリソースアクセス節点を含むデータフローグラフ中の各節点をいつ実行するかを決定するスケジューリング手段と、該データフローグラフ中の各枝で表されるデータを格納するためのレジスタを決定すると共に、該データフローグラフ中の節点で表される演算をどの演算器を用いて行うかを決定するアロケーション手段と、スケジューリング結果とアロケーション結果を元に、演算器とレジスタを挿入し、必要に応じてセレクタを挿入してデータパスを生成するデータパス生成手段と、該スケジューリング結果と該アロケーション結果を元に、データパス中に含まれるレジスタと必要に応じて挿入されるセレクタを制御するステートマシンを生成するコントローラ生成手段とを有する。
【００７１】
本発明の半導体集積回路の製造方法は、本発明の上記動作合成装置によりリソースアクセス調停処理が施された論理回路を設計し、設計された論理回路情報によりパターニングされたレジストパターンを用いて、半導体基板上または基板に設けられた半導体層上に半導体集積回路を形成するものであり、そのことにより上記目的が達成される。
【００７２】
本発明の動作合成方法は、ハードウェアの構造に関する情報が含まれず、処理手順のアルゴリズムのみが記述された動作記述から回路の動作合成を行ってＲＴＬ（（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ））記述情報を自動生成する動作合成方法において、該動作記述中のループ内に同一リソースへのアクセスが複数含まれる場合に、該ループ処理がパイプライン化されても、リソースアクセス調停手段が、該同一リソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理するリソースアクセス調停工程を有するものであり、そのことにより上記目的が達成される。
【００７３】
また、好ましくは、本発明の動作合成方法におけるリソースアクセス調停工程において、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を与える。
【００７４】
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス調停工程において、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの演算が節点で表され、該複数アクセスの演算を実行する時間制約が枝で表された制約グラフについて、前記制約条件として当該節点間の制約枝を与える。
【００７５】
さらに、好ましくは、本発明の動作合成方法における制約条件としてとして、前記同一リソースにアクセスする複数のリソースアクセス節点のうち、時間的に隣接するリソースアクセス節点は１サイクルまたは２サイクル以上時間を空けて実行されるように設定し、かつ、パイプライン化後にリソースアクセスの競合が生じないように該リソースアクセス節点は複数、同一サイクルで実行しないように設定する。
【００７６】
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス調停工程は、ＡＳＡＰ・ＡＬＡＰスケジューリング処理手段が、ＡＳＡＰスケジューリングおよびＡＬＡＰスケジューリングを用いて、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理工程と、リソースアクセス組選択処理手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のうち、所定の複数節点よりなるリソースアクセス組を選択するリソースアクセス組選択処理工程と、制約式決定処理手段が、求めたスケジューリング可能範囲を用い、該リソースアクセス組として選択された所定の複数リソースアクセス節点に対して、リソースアクセスの競合が起きないようにするための前記制約条件を線形計画問題により取り扱い可能な制約条件として制約式に変換する制約式決定処理工程とを有する。
【００７７】
さらに、好ましくは、本発明の動作合成方法において、前記制約式決定処理工程における制約式の決定後、繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点全てのリソースアクセス節点の組が選択されたか否かを判断し、該全てのリソースアクセス節点の組が選択された場合に制約式決定処理を終了し、該全てのリソースアクセス節点の組が選択されていない場合には、前記リソースアクセス組選択処理工程および前記制約式決定処理工程による各処理を再び実行させる繰り返し工程を更に有する。
【００７８】
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス組選択処理工程において、前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、さらに、前記繰り返し工程において、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式および第２制約式に基づいて調停処理を行う。
【００７９】
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス組選択処理工程において、前記リソースアクセス組選択処理手段が、前記複数節点よりなるリソースアクセス組が２つのリソースアクセス節点Ａ，Ｂを選択した場合に、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、さらに、前記繰り返し工程において、前記繰り返し手段が、前記データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点Ｃ，Ｄがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｂ，Ｃを選択し、前記制約式決定処理工程において、前記制約式決定処理手段により該２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、さらに、該繰り返し工程において、該繰り返し手段が、該データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、該リソースアクセス節点Ａ，Ｂ，Ｃの他にリソースアクセス節点Ｄがあると判断した場合には、該リソースアクセス組選択処理工程において、該リソースアクセス組選択処理手段が、２つのリソースアクセス節点Ｃ，Ｄを選択し、該制約式決定処理工程において、該制約式決定処理手段により該２つのリソースアクセス節点Ｃ，Ｄに対して第３制約式を決定する制約式決定処理を行って、前記条件式として該第１制約式、第２制約式および第３制約式に基づいて調停処理を行う。
【００８０】
さらに、好ましくは、本発明の動作合成方法における制約式決定処理工程は、前記同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２について、パイプライン化前の実行サイクルをＳ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｔｐはスループットの値、ｎは整数）
を線形計画問題により取り扱い可能なように、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋ｔｐ×ｍ＋１（定数ｍは整数）
Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１
に変換してこれを前記制約式とする。
【００８１】
さらに、好ましくは、本発明の動作合成方法における定数ｍを、
ｍ＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ）
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝（Ｓ＿ａｌａｐ（Ｒ２）＋Ｓ＿ａｓａｐ（Ｒ２））／２−（Ｓ＿ａｌａｐ（Ｒ１）＋Ｓ＿ａｓａｐ（Ｒ１））／２
により求める。
【００８２】
但し、ｉｎｔ；引数の値を越えない整数を返す関数
Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の平均値
さらに、好ましくは、本発明の動作合成方法における定数ｍを、
（Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＋１）／ｔｐ−１≦ｍ≦（Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）−１）／ｔｐ
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＝Ｓ＿ａｓａｐ（Ｒ２）−Ｓ＿ａｌａｐ（Ｒ１）
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）＝Ｓ＿ａｌａｐ（Ｒ２）−Ｓ＿ａｓａｐ（Ｒ１）
により求める。
【００８３】
但し、Ｓ＿ａｓａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクル
Ｓ＿ａｌａｐ（Ｒｎ）；同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＬＡＰスケジューリングにより求められるＲｎのサイクル
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最小値
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）；節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最大値
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス調停工程は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの実行サイクルを変数として求める線形計画問題について、前記制約条件として当該変数間の制約式を満たすように、最長経路法によりスケジューリングを求める。
【００８４】
さらに、好ましくは、本発明の動作合成方法におけるリソースアクセス調停工程は、前記ループ処理内の同一リソースへの複数アクセスに対して、該複数アクセスの処理手順を示す制約グラフを用いて最長経路法によりスケジューリングを求める。
【００８５】
さらに、好ましくは、本発明の動作合成方法において、データフローグラフ生成手段が、前記動作記述から、データが枝で表され、演算が節点で表されたデータフローグラフを生成するデータフローグラフ生成工程と、スケジューリング手段が、前記リソースアクセス調停工程により得たリソースアクセス調停処理結果を用いて、前記複数のリソースアクセス節点を含むデータフローグラフ中の各節点をいつ実行するかを決定するスケジューリング工程と、アロケーション手段が、該データフローグラフ中の各枝で表されるデータを格納するためのレジスタを決定すると共に、該データフローグラフ中の節点で表される演算をどの演算器を用いて行うかを決定するアロケーション工程と、データパス生成手段が、スケジューリング結果とアロケーション結果を元に、演算器とレジスタを挿入し、必要に応じてセレクタを挿入してデータパスを生成するデータパス生成工程と、コントローラ生成手段が、該スケジューリング結果と該アロケーション結果を元に、データパス中に含まれるレジスタと必要に応じて挿入されるセレクタを制御するステートマシンを生成するコントローラ生成工程とを有する。
【００８６】
本発明の動作合成制御プログラムは、本発明の上記動作合成方法を計算機上で実行するための各処理手順が記述されたものであり、そのことにより上記目的が達成される。
【００８７】
本発明の可読記録媒体は、本発明の上記動作合成制御プログラムが記録されたコンピュータ読み取り可能なものであり、そのことにより上記目的が達成される。
【００８８】
上記構成により、以下に、本発明の作用について説明する。
【００８９】
本発明にあっては、ループ処理を表すデータフローグラフをパイプライン化して、高速に動作可能なループ処理のデータフローグラフを生成する際に、そのループ処理に同一リソースへのアクセスが複数含まれる場合に、パイプライン化後にリソースアクセスの競合が生じないように、制約条件を考慮してパイプライン化前のデータフローグラフをスケジューリングする。
【００９０】
例えば、リソースアクセス調停手段によって、ループ処理内の同一リソースへの複数アクセスに対して、それらの複数アクセスの実行サイクルを変数として求める線形計画問題として取り扱えるように、制約条件としてその変数間の制約式を与える。
【００９１】
また、リソースアクセス調停手段によって、ループ処理内の同一リソースへの複数アクセスに対して、それらの複数アクセスの演算が節点で表され、この複数アクセスの演算を実行する時間制約が枝で表された制約グラフ上で取り扱えるように、制約条件としてその節点間の制約枝を与える。
【００９２】
これらの制約式や制約枝で表される制約条件を満足させるように最長経路法や線形計画法などによりスケジューリングを行うことによって、ループ処理がパイプライン化されても同一リソースへのアクセスの競合が生じないようにすることができる。
【発明の効果】
【００９３】
以上により、本発明によれば、ループ処理の１回の繰り返し中に、同一のリソースに対して複数のアクセスが含まれる場合に、そのループ処理がパイプライン化されても、同一リソースへのアクセスの競合が生じないように制約条件（または線形制約条件）に基づいて調停処理を行って複数のリソースアクセス節点を良好かつ確実にスケジューリングすることができる。
【発明を実施するための最良の形態】
【００９４】
以下に、本発明の動作合成装置およびこれを用いた動作合成方法の実施形態について、図面を参照しながら詳細に説明する。
【００９５】
本発明の動作合成装置およびこれを用いた動作合成方法にあっては、動作記述中のループ処理内に、ＲＡＭやＲＯＭ、レジスタファイル、外部ポートなどの同一リソースへのアクセスが複数含まれる場合に、リソースアクセスに競合が生じないように、ループ処理をパイプライン化させる場合について説明する。
【００９６】
図１（ａ）は、あるループ処理手順の一例を示す図である。
【００９７】
図１（ａ）に示すように、このループ処理は、パイプライン化されておらず、一つのデータを処理するために６サイクルが必要であり、即ち、スループットとレイテンシは共に”６”である。図１（ａ）中の関数演算Ａ〜Ｆは、それぞれサイクル１からサイクル６に順次スケジューリングされた各処理を表している。
【００９８】
図１（ｂ）は、同じループ処理をスループットが”３”となるように、２段にパイプライン化したときの処理手順を表す図である。
【００９９】
図１（ｂ）に示すように、このループ処理は、サイクル１で、関数演算Ａと、関数演算Ｄとが同時に実行されている。これに続く次のサイクル２では、関数演算Ｂと、関数演算Ｅが同時に実行されている。更にその次のサイクル３では、関数演算Ｃと、関数演算Ｆが同時に実行されている。このように、２種類の関数演算処理が同じサイクルで同時に行われる。
【０１００】
図１（ｃ）は、同じループ処理をスループットが”２”となるように、３段にパイプライン化したときの処理手順を表す図である。
【０１０１】
図１（ｃ）に示すように、このループ処理は、サイクル１では、関数演算Ａと関数演算Ｃと関数演算Ｅとが同時に実行されている。これに続く次のサイクル２では、関数演算Ｂと関数演算Ｄと関数演算Ｆとが同時に実行されている。このように、３種類の関数演算処理が同じサイクルで同時に行われる。
【０１０２】
ここで、１回のループ処理中に、ある同一のリソースに対して２回アクセスが行なわれ、それらが２サイクル（１サイクルでもよい）以上時間を空けて実行される必要がある場合について考える。それら２回のリソースアクセスをそれぞれＲ１およびＲ２とすると、パイプライン化されない図１（ａ）の場合には、リソースアクセスＲ１とＲ２の２つは、２サイクル以上、間が空いている限り、どのサイクルで実行されてもよい。即ち、リソースアクセスＲ１とＲ２の実行ステップをＳ（Ｒ１）とＳ（Ｒ２）とすると、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋２  −−−（式１）
の制約条件を満たせばよい。これを線形計画問題の制約条件として、他の演算の間の制約条件と共に線形計画法を用いて解くと、間が２サイクル以上空いている組合せであるから、｛Ｓ（Ｒ１），Ｓ（Ｒ２）｝は、｛１，４｝，｛１，５｝，｛１，６｝，｛２，５｝，｛２，６｝，｛３，６｝のうちのいずれかの組み合せという結果が得られる。
【０１０３】
実際には、データフローグラフ中のデータ依存関係からも上記（式１）と同等の制約式が得られ、線形計画問題の解はこれらの制約式も満たす必要があるため、Ｓ（Ｒ１）とＳ（Ｒ２）の組み合わせとしては、これらのうち、全ての制約条件式を満たすいずれかとなる。
【０１０４】
線形計画問題の制約条件は、ＸとＹを変数、ａ，ｂ，ｃを定数として、
ａＸ≧ｂＹ＋ｃ  または  ａＸ≦ｂＹ＋ｃ  −−−（式２）
として表される。
【０１０５】
上記（式１）は線形計画法により解くことができる。また、上記（式２）において、ａとｂが”１”である場合には、グラフ理論の手法の一つである、ダイクストラの最長（最短）経路法を適用することが可能となり、線形計画法と同様の結果を高速に得ることもできる。
【０１０６】
図２（ａ）は、線形計画問題の一例を示す図であり、図２（ｂ）は、それに対応する制約グラフの一例を示す図である。
【０１０７】
図２（ｂ）では、図２（ａ）に示す線形計画問題の制約式が制約グラフの枝の重みとして表されている。ここで、ｓとｔは特別な節点であり、それぞれソース節点およびシンク節点と呼ばれ、グラフ全体の上端と下端を表している。図２（ａ）でも、同様に、上端と下端を表す変数ｓとｔが導入されている。
【０１０８】
図２（ｂ）に示す制約グラフ上でソース節点ｓから各節点への最長経路を求めたときの各節点の位置は、対応する線形計画問題の解の一つである。例えば制約グラフにおいて節点ｓから節点Ｚへの最長経路は”３”（ｓからＸとＹを通ってＺに至る経路）であり、節点ｓの位置を”０”としたときのＺの位置は”３”となる。これは、線形計画問題においてｓの値を”０”としたときのＺの最小値”３”と一致する。
【０１０９】
制約グラフは、データフローグラフとは異なるものである。データフローグラフでは節点により演算が表され、枝により各演算間のデータの流れが表されているのに対して、制約グラフでは、節点により同じく演算が表されているが、枝により演算を実行する時間制約（図２（ｂ）の例えばＸからＺに至る枝では「２」）が表されている。よって、データフローグラフ中のデータ依存関係に対応して、制約グラフの節点間にも制約枝を設ける必要がある。さらに、リソースアクセスのタイミング制約のように、時間制約のみがあり、データの流れは存在しない場合にも、データフローグラフには枝は存在しないが、制約グラフには制約枝を設ける必要がある。
【０１１０】
次に、スループットが”６”である図１（ａ）のループ処理を、図１（ｂ）のようにスループットが”３”となるようにパイプライン化する場合について考える。
【０１１１】
リソースアクセスＲ１とＲ２のパイプライン化前の実行ステップをＳ（Ｒ１）とＳ（Ｒ２）とする。即ち、１≦Ｓ（Ｒ１）≦６，１≦Ｓ（Ｒ２）≦６である。パイプライン化されない場合と同様に、２つのリソースアクセスの間には２サイクル以上空ける必要があるため、上記式（１）の制約条件が必要である。さらに、パイプライン化後にリソースアクセスの競合が生じないようにするためには、
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋３ｎ  （ｎは整数）  −−−（式３）
という制約条件が必要である。これらの制約条件を満たすリソースアクセスＲ１とＲ２のパイプライン化前の実行ステップ｛Ｓ（Ｒ１），Ｓ（Ｒ２）｝は、｛１，５｝，｛１，６｝，｛２，６｝のいずれかの組み合せとなる。
【０１１２】
スループットが”６”である図１（ａ）のループを、図１（ｃ）のようにスループットが”２”となるようにパイプライン化させる場合には、同様に、
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋２ｎ（ｎは整数）  −−−（式４）
という制約条件が必要となる。これらの制約条件を満たすリソースアクセスＲ１とＲ２のパイプライン化前の実行ステップ｛Ｓ（Ｒ１），Ｓ（Ｒ２）｝は、｛１，４｝，｛１，６｝，｛２，５｝，｛３，６｝のいずれかの組み合せとなる。
【０１１３】
一般には、リソースアクセスの競合が起きないようにするための制約条件は、スループットの値をｔｐとして、
Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｎは整数）  −−−（式５）
と表される。
【０１１４】
しかしながら、上記（式３）〜（式５）の制約条件では、Ｓ（Ｒ１）とＳ（Ｒ２）の関係が線形でなくなるため、上記（式２）の形式とすることができない。このため、リソースアクセスＲ１とＲ２の実行ステップを求める問題を、線形計画問題に定式化させることができず、整数計画問題となってしまう。線形計画問題については高速に解く方法が知られているが、整数計画問題はＮＰ完全問題であり、これを解くためには変数の個数の指数関数に比例する処理時間が必要となる。このため、１０００個以上の節点を含むこともある実際の回路においては、高速な計算機を用いたとしても、実用的な処理時間でスケジューリングを行なうことができない。
【０１１５】
そこで、本発明では、上記（式３）〜（式５）の制約条件を線形計画問題の制約として取り扱うことができる形式（変数間の制約式）に変換して線形計画問題を解いたり、また、制約グラフ上で取り扱うことができる制約条件（節点間の制約枝）に変換したりして最長経路法を適用するなどの方法により、リソースアクセスの調停を行う。これにより、上記（式３）〜上記式（５）の制約条件を満足させることができるリソースアクセスの実行サイクルを、実用的な処理時間により求めることが可能となる。
【０１１６】
以下に、上記した本発明の原理を踏まえて、本発明の実施形態に係る動作合成装置およびこれを用いた動作合成方法について、更に詳細に説明する。
【０１１７】
図３は、本発明の実施形態に係る動作合成装置が搭載された計算機システムの要部構成例を示すブロック図である。
【０１１８】
図３において、本実施形態の計算機システム１は、回路設計用の動作合成装置１０とデータベースとしての記憶装置２０とが搭載された計算機３０と、この計算機３０にインターフェイスを介して接続された操作入力手段としてのキーボードやマウスなどの入力装置４０と、この計算機３０にインターフェイスを介して接続されたディスプレイ（表示装置）や記録媒体に情報記録するかまたは、この記録媒体から情報読み出す情報記録・再生装置などの出力装置５０とを有している。
【０１１９】
動作合成装置１０では、記憶装置２０から供給された回路の動作記述から回路の動作合成が自動的に行われてＲＴＬレベル記述情報が生成され、この生成されたＲＴＬレベル記述情報は記憶装置２０に記憶される。
【０１２０】
記憶装置２０には、ハードウェアの構造に関する情報が含まれず、処理手順のアルゴリズムのみが記述された回路の動作記述が記憶されており、その回路の動作記述が動作合成装置１０に供給される。
【０１２１】
計算機３０は、ここでは図示していないが、全体的な制御を行う制御手段としてのＣＰＵ（中央演算処理装置）と、このＣＰＵの起動時にワークメモリとして働く一時記憶手段としてのＲＡＭと、ＣＰＵを動作させるための動作合成制御プログラムおよびこれに用いる各種データなどが記録されたコンピュータ読み取り可能な可読記録媒体（記憶手段）としてのＲＯＭとを有している。ＲＡＭは、ＣＰＵによる制御中に中間データとして生成される情報などの各種データを、その都度格納すると共に、必要に応じてこれらを参照可能としている。
【０１２２】
ＲＯＭは、ハードディスク、光ディスク、磁気ディスクおよびＩＣメモリなどの可読記録媒体（記憶手段）で構成されている。この動作合成制御プログラムおよびこれに用いる各種データは、携帯自在な光ディスク、磁気ディスク（出力装置５０）およびＩＣメモリなどから計算機３０内のＲＯＭにダウンロードされてもよいし、計算機３０内のＲＯＭであるコンピュータハードディスクから別のＲＯＭにダウンロードされてもよいし、無線または有線、インターネットなどを介して計算機３０内のＲＯＭにダウンロードされてもよい。
【０１２３】
この動作合成装置１０は、動作合成制御プログラムに基づいてＣＰＵが、データフローグラフ生成手段１１と、リソースアクセス調停手段１２と、スケジューリング手段１３と、アロケーション手段１４と、データパス生成手段１５と、コントローラ生成手段１６とを実行することにより、回路の動作記述からＲＴＬレベル記述情報として論理回路などの回路構成を自動合成するものである。
【０１２４】
データフローグラフ生成手段１１では、記憶装置２０から供給された回路の動作記述から、データが枝で表され、演算が節点で表されたデータフローグラフが生成される。
【０１２５】
リソースアクセス調停手段１２では、記憶装置２０からの動作記述中のループ処理内に同一リソースへのアクセスが複数含まれる場合に、このループ処理がパイプライン化されても、同一リソースに対してアクセスの競合が起きないように制約条件に基づいて調停処理を行う。このリソースアクセスの調停処理は、ループ処理内の同一リソースへの複数アクセスに対して、複数アクセスの実行サイクルを変数として求める線形計画問題について、制約条件として変数間の制約式を与えることにより行うかまたは、複数アクセスの演算が節点で表され、複数アクセスの演算を実行する時間制約が枝で表された制約グラフについて、制約条件として節点間の制約枝を与えることにより行う。
【０１２６】
リソースアクセス調停手段１２は、ＡＳＡＰスケジューリングおよびＡＬＡＰスケジューリングを用い、リソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理手段１２１と、データフローグラフ中にある同一リソースにアクセスするリソースアクセス節点のうち、所定の数（ここでは二つとしている）の節点よりなる組（所定の複数節点よりなるリソースアクセス組）を選択するリソースアクセス組選択処理手段１２２と、求めたスケジューリング可能範囲を用い、同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２（リソースアクセス組として選択された所定の複数リソースアクセス節点）に対して、パイプライン化前の実行ステップをＳ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件を線形計画問題により取り扱い可能な制約条件として制約式に変換する制約式決定処理手段１２３と、制約式決定処理手段１２３による制約式の決定後、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点全てのリソースアクセス節点の組が選択されたか否かを判断し、全てのリソースアクセス節点の組が選択された場合に制約式決定処理を終了し、全てのリソースアクセス節点の組が選択されていない場合には、リソースアクセス組選択処理手段１２２および制約式決定処理手段１２３による各処理を再び実行させる繰り返し手段（図示せず）とを有している。
【０１２７】
スケジューリング手段１３では、データフローグラフ中の各節点をいつどのタイミングで実行するかが決定される。
【０１２８】
アロケーション手段１４では、データフローグラフ中の各枝で表されるデータを格納するためのレジスタが決定されると共に、データフローグラフ中の節点で表される演算をどの演算器を用いて行うかが決定される。
【０１２９】
データパス生成手段１５では、スケジューリング結果とアロケーション結果を元に、演算器とレジスタが接続され、また、必要に応じて演算器とレジスタとの間などにセレクタが挿入されて接続されて、データパスが生成される。
【０１３０】
コントローラ生成手段１６では、スケジューリング結果とアロケーション結果を元に、データパス中に含まれるレジスタと必要に応じて挿入されたセレクタを制御するステートマシン（コントローラ）が生成される。このステートマシン（コントローラ）とデータパスが接続されて、ハードウェア情報（ＲＴＬレベル記述情報）の論理回路などの回路構成が生成される。
【０１３１】
本実施形態の動作合成装置１０において、データフローグラフ生成手段１１と、スケジューリング手段１３と、アロケーション手段１４と、データパス生成手段１５と、コントローラ生成手段１６との動作については、従来技術と同様であるため、ここではその詳細な説明は省略し、以下では、本発明の特徴構成であるリソースアクセス調停手段１２の動作を中心として詳細に説明する。
【０１３２】
図４は、図３の動作合成装置１０において、リソースアクセス調停手段１２によるリソースアクセス調停工程の各処理手順について説明するためのフローチャートである。
【０１３３】
図４に示すように、まず、ステップＳ１１では、ＡＳＡＰ・ＡＬＡＰスケジューリング処理手段１２１により、パイプライン化前の元のデータフローグラフについて、ＡＳＡＰ（Ａｓ  Ｓｏｏｎ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングおよびＡＬＡＰ（Ａｓ  Ｌａｔｅ  Ａｓ  Ｐｏｓｓｉｂｌｅ）スケジューリングを用い、リソースアクセス節点のスケジューリング可能範囲を求めるＡＳＡＰ・ＡＬＡＰスケジューリング処理が行われる。このとき、同一リソースにアクセスする節点Ｒｎ（ｎ＝１，２，．．．）に対して、ＡＳＡＰスケジューリングにより求められるＲｎのサイクルをＳ＿ａｓａｐ（Ｒｎ）、ＡＬＡＰスケジューリングにより求められるＲｎのサイクルをＳ＿ａｌａｐ（Ｒｎ）とする。
【０１３４】
ここで、ＡＳＡＰスケジューリングは、全ての処理が可能な限り早く実行されるようにスケジューリングする方法であり、最も単純なスケジューリング方法の１つで、制約グラフを最長経路法で解くことにより簡単に求めることができる。
【０１３５】
一方、ＡＬＡＰスケジューリングは、全ての処理が可能な限り遅く実行されるようにスケジューリングする方法である。ＡＬＡＰスケジューリングは、ＡＳＡＰスケジューリングのときと制約枝を逆向きにして、シンク点からソース点に向けて最長経路法を適用することによって、ＡＳＡＰスケジューリングの場合と同様に、簡単に求めることができる。
【０１３６】
図５（ａ）および図５（ｂ）にそれぞれ、ＡＳＡＰスケジューリングとＡＬＡＰスケジューリングをそれぞれ行ったデータフローグラフの事例を挙げている。
【０１３７】
図５（ａ）のＡＳＡＰスケジューリングでは、２サイクル目で処理されている演算Ａと、４サイクル目で処理されている演算Ｂが、図５（ｂ）のＡＬＡＰスケジューリングでは、５サイクル目と６サイクル目で処理されている。データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点のスケジューリング可能範囲は、例えば演算Ａでは、２〜５サイクル目の範囲であり、例えば演算Ｂでは、４〜６サイクル目の範囲となる。
【０１３８】
なお、図５の事例では、簡単のために、演算の遅延は考慮されておらず、１サイクルで逐次的には１つの節点のみしか実行することができないものとして記載されているが、演算の遅延を考慮して、１サイクルで複数の演算を逐次的に処理（チェイニング）するスケジューリングとすることもできる。
【０１３９】
リソースアクセス調停は、同一リソースにアクセスする節点の組み合わせ全てに対して行う必要がある。そこで、図４のステップＳ１２では、リソースアクセス組選択処理手段１２２により、データフローグラフ中にある同一リソースにアクセスするリソースアクセス節点のうち、２つの節点よりなる組（リソースアクセス組）が選択されて、ステップＳ１３で、制約式決定処理手段１２３により、求めたスケジューリング可能範囲を用い、リソースアクセス組として選択された所定の複数リソースアクセス節点（ここでは２つの節点）に対して制約式決定処理が行われる。
【０１４０】
その後、ステップＳ１４で、繰り返し手段（図示せず）によって、全てのリソースアクセス節点の組が選択されたか否かが判断され、まだ終わっていない場合（ｎｏ）には再びステップＳ１２のリソースアクセス組選択処理に戻ってステップＳ１４の制約式決定処理が繰り返される。リソースアクセスの組を選択する順序は、その結果に影響しないため、どのような順番であってもよい。
【０１４１】
繰り返し手段（図示せず）による繰り返し処理について説明する。
【０１４２】
リソースアクセス組選択処理手段１２２が、複数節点よりなるリソースアクセス組が２つのリソースアクセス節点として例えばＡ，Ｂを選択した場合に、制約式決定処理手段１２３により２つのリソースアクセス節点Ａ，Ｂに対して第１制約式を決定する制約式決定処理を行い、繰り返し手段（図示せず）が、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、リソースアクセス節点Ａ，Ｂの他にリソースアクセス節点として例えばＣ，Ｄがあると判断した場合には、リソースアクセス組選択処理手段１２２が、２つのリソースアクセス節点Ｂ，Ｃを選択し、制約式決定処理手段１２３により２つのリソースアクセス節点Ｂ，Ｃに対して第２制約式を決定する制約式決定処理を行い、さらに、繰り返し手段（図示せず）が、データフローグラフ中にある同一リソースにアクセスする複数のリソースアクセス節点として、リソースアクセス節点Ａ，Ｂ，Ｃの他にリソースアクセス節点として例えばＤがあると判断した場合には、リソースアクセス組選択処理手段１２２が、２つのリソースアクセス節点Ｃ，Ｄを選択し、制約式決定処理手段１２３により２つのリソースアクセス節点Ｃ，Ｄに対して第３制約式を決定する制約式決定処理を行って、条件式として第１制約式、第２制約式および第３制約式に基づいて調停処理を行うものである。
【０１４３】
次に、図４のステップＳ１３の制約式決定処理についてさらに詳細に説明する。
【０１４４】
ここでは、線形計画問題の制約とすることができる上記（式２）の形式の制約条件式のうち、パイプライン化時にリソース競合が起きないようにするために、上記（式５）の制約条件を満たすものを求める。
【０１４５】
上記（式５）は、Ｓ（Ｒ２）≠Ｓ（Ｒ１）＋ｔｐ×ｎ（ｎは整数）であり、
Ｓ（Ｒ１）＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ−１  または
Ｓ（Ｒ１）＋ｔｐ＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×２−１  または
Ｓ（Ｒ１）＋ｔｐ×２＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×３−１  または
Ｓ（Ｒ１）＋ｔｐ×３＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×４−１  または
…  または
Ｓ（Ｒ１）−ｔｐ＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）−ｔｐ×２−１  または
Ｓ（Ｒ１）−ｔｐ×２＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）−ｔｐ×３−１  または
Ｓ（Ｒ１）−ｔｐ×３＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）−ｔｐ×４−１  または
…  と同じである。
【０１４６】
よって、
Ｓ（Ｒ１）＋ｔｐ×ｍ＋１≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１（ｍは整数）  −−−（式６）
と表すと、任意のｍに対して（式６）は上記（式５）を満たす。また、（式６）は、
Ｓ（Ｒ２）≧Ｓ（Ｒ１）＋ｔｐ×ｍ＋１  −−−（式７）
Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋ｔｐ×（ｍ＋１）−１  −−−（式８）
と変形することができるが、ここで（式７）と（式８）は（式２）の形式となっているため、これらの（式７）と（式８）は線形計画問題の制約式とすることができる。
【０１４７】
即ち、この制約式決定処理は、同一リソースにアクセスするリソースアクセス節点Ｒ１およびＲ２について、パイプライン化前の実行ステップを変数Ｓ（Ｒ１）およびＳ（Ｒ２）として、リソースアクセスの競合が起きないようにするための制約条件の（式２）を線形計画問題により取り扱い可能なように、上記（式７）および（式８）に変換して制約式とする。
【０１４８】
さらに、変数Ｓ（Ｒ１）およびＳ（Ｒ２）の係数が”１”であるため、最長経路法も用いることができる。即ち、上記（式６）の定数ｍを適切に決めることによって、リソース競合が起きないスケジューリングを、線形計画法や最長経路法によって高速に求めることができる。
【０１４９】
上記定数ｍを決定するためには、データフローグラフ中にある同一リソースにアクセスするリソースアクセス節点Ｒ１とＲ２のＡＳＡＰスケジューリングおよびＡＬＡＰスケジューリング結果を用いる。これらのスケジューリング結果から、
Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＝Ｓ＿ａｓａｐ（Ｒ２）−Ｓ＿ａｌａｐ（Ｒ１）  −−−（式９）
Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）＝Ｓ＿ａｌａｐ（Ｒ２）−Ｓ＿ａｓａｐ（Ｒ１）  −−−（式１０）
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝（Ｓ＿ａｌａｐ（Ｒ２）＋Ｓ＿ａｓａｐ（Ｒ２））／２−（Ｓ＿ａｌａｐ（Ｒ１）＋Ｓ＿ａｓａｐ（Ｒ１））／２  −−−（式１１）
となる。
【０１５０】
ここで、Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）は、リソースアクセス節点Ｒ２がリソースアクセス節点Ｒ１の何ステップ後に実行されるかという値の最小値であり、Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）は、節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の最大値であり、Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）は、節点Ｒ２が節点Ｒ１の何ステップ後に実行されるかという値の平均値である。それぞれの値は負の数となってもよく、その場合には節点Ｒ２が節点Ｒ１よりも前で実行されることを表す。
【０１５１】
一方、上記（式６）において、定数ｍをある値に決定したときに、（式６）を満たすＳ（Ｒ２）とＳ（Ｒ１）は、差の平均値が
［｛ｔｐ×ｍ＋１｝＋｛ｔｐ×（ｍ＋１）−１｝］／２＝ｔｐ×（ｍ＋１／２）
となる。よって、この値がＤｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）に近い値となるように、ｍを決定することが最も有効である。その値をｍ＿ａｖｅ（Ｒ２，Ｒ１）とすると、
ｔｐ×（ｍ＿ａｖｅ（Ｒ２，Ｒ１）＋１／２）≒Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）
より、
ｍ＿ａｖｅ（Ｒ２，Ｒ１）≒Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ−１／２
となる。ｍ＿ａｖｅは整数であるので四捨五入すると、
ｍ＿ａｖｅ（Ｒ２，Ｒ１）＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ−１／２＋１／２）＝ｉｎｔ（Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）／ｔｐ）  −−−（式１２）
となる。ここで、ｉｎｔは引数の値を越えない整数を返す関数である。
【０１５２】
上記（式１２）を上記（式７）と上記（式８）に代入すると、リソースアクセスの衝突（競合）が起きない制約条件で、線形計画問題の制約とすることが可能な制約式が得られる。
【０１５３】
さらに、上記（式８）は、
Ｓ（Ｒ１）≧Ｓ（Ｒ２）−ｔｐ×（ｍ＋１）＋１  −−−（式１３）
であるため、上記（式７）と（式１３）の制約式をデータフローグラフ上の制約とすると、図６のように表すことができる。
【０１５４】
図６（ａ）は、Ｓ（Ｒ１）とＳ（Ｒ２）を求める線形計画問題の制約式（式７）および（式１３）を示しており、図６（ｂ）は、その制約式を制約枝に付けた制約グラフの制約枝を示している。この制約条件を、他の制約条件と共に最長経路法で解くことにより、Ｒ１およびＲ２のスケジューリングを求めることができる。
【０１５５】
上記方法により、同一リソースへのアクセスが２個である場合には、必ず解が求められる制約を得ることができる。また、同一リソースへのアクセスが３個以上の場合でも、解が求められる制約が得られる可能性が高い。ただし、上記（式１２）で得られるｍ＿ａｖｅが代入された（式６）は、リソースアクセスの衝突を回避するための元々の制約条件である（式５）の一部分しか表していない。即ち、（式６）は（式５）よりも厳しい制約となっている。このため、同一リソースへのアクセスが３個以上の場合、各アクセスの組み合わせに対する制約の間に矛盾が生じて、全ての制約条件を満たすことができなくなる虞がある。このような場合には、上記（式６）の定数ｍの値を、ｍ＿ａｖｅ以外の値とする必要がある。そこで、以下では、（式５）の全ての解を網羅することができる定数ｍの範囲を考える。
【０１５６】
上記（式９）から、
Ｓ（Ｒ２）≧Ｓ＿ａｓａｐ（Ｒ２）＝Ｓ＿ａｌａｐ（Ｒ１）＋Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）≧Ｓ（Ｒ１）＋Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）
である。また、上記（式１０）より、
Ｓ（Ｒ２）≦Ｓ＿ａｌａｐ（Ｒ２）＝Ｓ＿ａｓａｐ（Ｒ１）＋Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）≦Ｓ（Ｒ１）＋Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）
である。よって、Ｓ（Ｒ１）とＳ（Ｒ２）の組み合せは、必ず、下記（式１４）を満たすことになる。
【０１５７】
Ｓ（Ｒ１）＋Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）≦Ｓ（Ｒ２）≦Ｓ（Ｒ１）＋Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）  −−−（式１４）
このため、（式６）を満たすＳ（Ｒ１）とＳ（Ｒ２）の組み合せの少なくとも一つは（式１４）を満足させる必要がある。
【０１５８】
ｔｐ×（ｍ＋１）−１≧Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）  かつ  ｔｐ×ｍ＋１≦Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）
のときに、上記（式６）と（式１４）は共通解を持ち得るため、定数ｍの値の範囲は、
（Ｄｉｆｆ＿ｍｉｎ（Ｒ２，Ｒ１）＋１）／ｔｐ−１≦ｍ≦（Ｄｉｆｆ＿ｍａｘ（Ｒ２，Ｒ１）−１）／ｔｐ  −−−（式１５）
となる。
【０１５９】
よって、上記（式１２）により得られたｍ＿ａｖｅを用いた制約条件では解が求められない場合には、（式１５）の範囲でｍを適宜変化させて、再度、線形計画法や最長経路法により解を求めればよい。なお、（式１５）の範囲の全てのｍにより解が求められなかった場合には、上記（式５）のリソースアクセスの衝突（競合）を回避する制約を満たす解は存在しないことが分かる。
【０１６０】
さらに、本実施形態の動作合成装置１０におけるリソースアクセス調停手段１２によるリソースアクセス調停処理工程について、具体的な数値を用いて説明する。
【０１６１】
図７（ａ）は、あるデータフローグラフのデータ依存関係から生成された制約グラフの一例を示す図である。
【０１６２】
図７（ａ）において、節点Ｒ１，Ｒ２，Ｒ３は、同一リソースに対するアクセスを示しているものとする。
【０１６３】
図７（ｂ）は、図７（ａ）の制約グラフをＡＳＡＰ・ＡＬＡＰスケジューリングして得られる各リソースアクセス節点のスケジューリング可能範囲である。即ち、
Ｓ＿ａｓａｐ（Ｒ１）＝１，Ｓ＿ａｌａｐ（Ｒ１）＝４，Ｓ＿ａｓａｐ（Ｒ２）＝４，Ｓ＿ａｌａｐ（Ｒ２）＝６，Ｓ＿ａｓａｐ（Ｒ３）＝６，Ｓ＿ａｌａｐ（Ｒ３）＝９
を図示したものである。
【０１６４】
上記式（１１）から、
Ｄｉｆｆ＿ａｖｅ（Ｒ２，Ｒ１）＝２．５，
Ｄｉｆｆ＿ａｖｅ（Ｒ３，Ｒ２）＝２．５，
Ｄｉｆｆ＿ａｖｅ（Ｒ３，Ｒ１）＝５
となるため、スループットｔｐ＝３となるようにパイプライン化させる場合、上記式（１２）から、
ｍ＿ａｖｅ（Ｒ２，Ｒ１）＝０，
ｍ＿ａｖｅ（Ｒ３，Ｒ２）＝０，
ｍ＿ａｖｅ（Ｒ３，Ｒ１）＝１
となる。
【０１６５】
これに従って、図６に示すように制約グラフの制約枝を加えると、図７（ｃ）に示すような制約グラフになる。
【０１６６】
次に、この制約グラフを最長経路法により解くと、図８（ａ）に示すような結果が得られる。ここで、矩形中の数字は、各節点の実行サイクルを表している。節点ｓは処理の開始を表しているので、このサイクルＳ（ｓ）を”１”とすると、図８（ａ）に示す通り、節点Ｒ１，Ｒ２，Ｒ３への最長経路は、それぞれ、
Ｓ（Ｒ１）＝２
Ｓ（Ｒ２）＝４
Ｓ（Ｒ３）＝６
となる。例えば節点Ｒ２への経路は、節点ｓからと節点Ｒ１からと節点Ｒ３からの３通りがあるが、その中の最長経路がＳ（Ｒ２）であるので、
Ｓ（Ｒ２）＝ｍａｘ（Ｓ（ｓ）＋３，Ｓ（Ｒ１）＋１，Ｓ（Ｒ３）−２）＝ｍａｘ（１＋３，２＋１，６−２）＝ｍａｘ（４，３，４）＝４
となり、Ｓ（Ｒ２）＝４は最長経路長である。Ｓ（Ｒ１），Ｓ（Ｒ３）についても同様に、最長経路となっている。
【０１６７】
図８（ｂ）は、図８（ａ）の制約グラフから得られるスケジューリング結果を図示したものである。この図８（ｂ）から、処理Ｒ１，Ｒ２，Ｒ３の全てが矢印で示すスケジューリング可能範囲内にスケジューリングされていることが確認できる。
【０１６８】
また、Ｓ（Ｒ１），Ｓ（Ｒ２），Ｓ（Ｒ３）は、上記式（５）を満たすように求められている。よって、図８（ｃ）に示すように、図８（ｂ）のスケジューリング結果を３段にパイプライン化させて、スループットを”３”とした場合にも、処理Ｒ１，Ｒ２，Ｒ３が同じサイクルで実行されることはなく、同一リソースに対してアクセスの競合が起こることはない。
【０１６９】
以上のように、本実施形態の動作合成装置１０およびこれを用いた動作合成方法によれば、ループ処理を表すデータフローグラフをパイプライン化させて、高速に動作可能なループ処理のデータフローグラフを生成する際に、そのループ処理に同一リソースへのアクセスが複数含まれる場合に、パイプライン化後にリソースアクセスの競合が生じないように、制約条件を考慮してパイプライン化前のデータフローグラフをスケジューリングすることができる。リソースアクセス調停手段１２によって、ループ処理内の同一リソースへの複数アクセスに対して、それらのアクセスの実行サイクルを変数として求める線形計画問題として取り扱えるように、変数間の制約式を与え、ループ処理内の同一リソースへの複数アクセスに対して、制約グラフ上で取り扱えるように、当該節点間の制約枝を与えるため、リソース競合が生じないスケジューリングを、線形計画法や最長経路法などによって高速に求めることができる。
【０１７０】
なお、上記実施形態では、本発明の動作合成方法を計算機３０上で実行するための処理手順が記述された動作合成制御プログラムおよびそのデータが記録されたコンピュータ読み取り可能なＲＯＭなどの可読記録媒体を用いて、コンピュータなどの計算機システム１により本発明の動作合成方法を実行させるリソースアクセス調停手段１２を備えた動作合成装置１０を計算機３０上に搭載させたが、これに限らず、リソースアクセス調停手段１２をハードウェアとして回路構成することもできる。
【０１７１】
また、上記実施形態では、特に説明しなかったが、半導体集積回路の製造方法として、本実施形態の動作合成装置１０のリソースアクセス調停手段１２によってリソースアクセス調停処理が施された論理回路を設計し、設計された論理回路情報に基づいてパターニングされたレジストパターンを用いて、半導体基板上または基板に設けられた半導体層上に半導体集積回路を形成することができる。これによって、ループ処理の１回の繰り返し中に、同一のリソースに対して複数のアクセスが含まれる場合に、そのループ処理がパイプライン化されても、同一リソースへのアクセスの競合が全く生じない論理回路を含むＬＳＩなどの半導体集積回路を容易かつ確実に製造することができる。
【０１７２】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
【産業上の利用可能性】
【０１７３】
本発明は、論理回路などの設計に用いられ、動作記述から論理回路を自動合成する動作合成装置、この動作合成装置を用いた半導体集積回路の製造方法、この動作合成装置を用いた動作合成方法、この動作合成方法の各処理をコンピュータに実行させるための動作合成制御プログラムおよびこの動作合成制御プログラムが記録されたコンピュータ読み取り可能な可読記録媒体の分野において、ループ処理の１回の繰り返し中に、同一のリソースに対して複数のアクセスが含まれる場合に、そのループ処理がパイプライン化されても、同一リソースへのアクセスの競合が生じないように制約条件（または線形制約条件）に基づいて調停処理を行って複数のリソースアクセス節点を良好かつ確実にスケジューリングすることができる。
【図面の簡単な説明】
【０１７４】
【図１】（ａ）は、あるループ処理の手順の一例を示す図であり、（ｂ）は、（ａ）と同じループ処理をスループットが”３”となるように、２段にパイプライン化したときの処理手順を示す図であり、（ｃ）は、（ａ）と同じループ処理をスループットが”２”となるように、３段にパイプライン化させたときの処理手順を示す図である。
【図２】（ａ）は、線形計画問題の一例を示す図であり、（ｂ）はそれに対応する制約グラフの一例を示す図である。
【図３】本発明の実施形態に係る動作合成装置が搭載された計算機システムの要部構成例を示すブロック図である。
【図４】図３のリソースアクセス調停手段によるリソースアクセス調停工程の処理手順について説明するためのフローチャートである。
【図５】（ａ）および（ｂ）はそれぞれ、ＡＳＡＰスケジューリングとＡＬＡＰスケジューリングを行ったデータフローグラフの各一例をそれぞれ示す図である。
【図６】（ａ）は、Ｓ（Ｒ１）とＳ（Ｒ２）を求める線形計画問題の制約式を示し、（ｂ）は、その制約式を制約枝に付けた制約グラフの制約枝を示す図である。
【図７】（ａ）は、あるデータフローグラフのデータ依存関係から生成された制約グラフの一例を示す図であり、（ｂ）は、（ａ）の制約グラフをＡＳＡＰ・ＡＬＡＰスケジューリングして得られる、各節点のスケジューリング可能範囲を示す図であり、（ｃ）は、制約枝を加えた制約グラフを示す図である。
【図８】（ａ）は、制約グラフを最長経路法により解いて得られる各節点の実行サイクルを表す図であり、（ｂ）は、（ａ）の制約グラフから得られるスケジューリング結果を示す図であり、（ｃ）は、（ｂ）のスケジューリング結果を３段にパイプライン化した一例を示す図である。
【図９】従来の動作合成方法の各処理手順を説明するためのフローチャートである。
【図１０】データフローグラフの一例を示す図である。
【図１１】データフローグラフのデータ構造を示す図である。
【図１２】ループ処理を含む動作記述の一例を示す図である。
【図１３】図１２に示す動作記述について、ループ処理をパイプライン化しない場合のデータフローグラフを示す図である。
【図１４】ループ処理がパイプライン化された回路動作を説明するための図である。
【図１５】図１２に示す動作記述のループ処理を従来の方法によりパイプライン化した場合のデータフローグラフの一例を示す図である。
【符号の説明】
【０１７５】
１  計算機システム
１０  動作合成装置
１１  データフローグラフ生成手段
１２  リソースアクセス調停手段
１２１    ＡＳＡＰ・ＡＬＡＰスケジューリング処理手段
１２２  リソースアクセス組選択処理手段
１２３  制約式決定処理手段
１３  スケジューリング手段
１４  アロケーション手段
１５  データパス生成手段
１６  コントローラ生成手段
２０  記憶装置
３０  計算機
４０  入力装置
５０  出力装置
【図１】
2009025973.tif 000003
【図２】
2009025973.tif 000004
【図３】
2009025973.tif 000005
【図４】
2009025973.tif 000006
【図５】
2009025973.tif 000007
【図６】
2009025973.tif 000008
【図７】
2009025973.tif 000009
【図８】
2009025973.tif 000010
【図９】
2009025973.tif 000011
【図１０】
2009025973.tif 000012
【図１１】
2009025973.tif 000013
【図１２】
2009025973.tif 000014
【図１３】
2009025973.tif 000015
【図１４】
2009025973.tif 000016
【図１５】
2009025973.tif 000017