(57)【要約】【課題】この発明は、例えば映像系を主体とする多くのアルゴリズム記述の自動的なパイプライン化を可能とし、所望の性能を達成する回路を生成する確率を大幅に向上させ得るパイプライン高位合成システム及び方法を提供することを目的としている。【解決手段】高位記述を受理し、そのループ記述部分に対してパイプライン高位合成を行なうことにより、直列に配された複数の組み合わせロジック部分の各相互間をそれぞれパイプラインレジスタで区切った形態の、パイプライン化された回路を生成する。この生成された回路について、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせる。【選択図】    図１
2007272797.tif 000002
【特許請求の範囲】
【請求項１】
高位記述を受理し、そのループ記述部分に対してパイプライン高位合成を行なうことにより、直列に配された複数の組み合わせロジック部分の各相互間をそれぞれパイプラインレジスタで区切った形態の、パイプライン化された回路を生成する第１の手段と、
前記第１の手段によって生成された回路について、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせる第２の手段とを具備することを特徴とするパイプライン高位合成システム。
【請求項２】
前記第２の手段は、前記ループ記述部分に記述された各配列アクセス箇所の添字、前記ループ記述部分に記述されたループ変数のステップ数、メモリアクセスを含む複数の組み合わせロジック部分の相互間におけるパイプライン段数差、パイプラインサイクル数に基づいて、前記シフトレジスタのサイズを設定することを特徴とする請求項１記載のパイプライン高位合成システム。
【請求項３】
前記第２の手段は、
メモリアクセスに衝突が生じる２つの配列アクセス箇所の添字のうちループ変数に対して加算される値をCy，Cxとし、前記ループ記述部分に記述されたループ変数のステップ数をｓとし、メモリアクセスに衝突が生じる２つの組み合わせロジック部分の相互間におけるパイプライン段数差をｎ<Cx−Cy>とし、パイプラインサイクル数をｍとした場合、
｜Cy−Cx−(ｎ<Cx−Cy>／ｍ)×ｓ｜＋１
なる演算により、前記シフトレジスタのサイズを算出することを特徴とする請求項２記載のパイプライン高位合成システム。
【請求項４】
前記第２の手段は、前記ループ記述部分に記述された各配列アクセス箇所の添字、前記ループ記述部分に記述されたループ変数のステップ数、メモリアクセスを含む複数の組み合わせロジック部分の相互間におけるパイプライン段数差、パイプラインサイクル数に基づいて、前記シフトレジスタのサイズと、前記シフトレジスタの前記メモリアクセスを含む複数の組み合わせロジック部分に接続される位置とを設定することを特徴とする請求項１記載のパイプライン高位合成システム。
【請求項５】
前記第２の手段は、
メモリアクセスに衝突が生じる２つの配列アクセス箇所の添字のうちループ変数に対して加算される値をCy，Cxとし、前記ループ記述部分に記述されたループ変数のステップ数をｓとし、メモリアクセスに衝突が生じる２つの組み合わせロジック部分の相互間におけるパイプライン段数差をｎ<Cx−Cy>とし、パイプラインサイクル数をｍとした場合、
｜Cy−Cx−(ｎ<Cx−Cy>／ｍ)×ｓ｜＋１
なる演算により、前記シフトレジスタのサイズを算出し、
ループ内で最後のメモリアクセスを行なう配列アクセス箇所の添字のうちループ変数に対して加算される値をClastとし、メモリアクセスを行なう配列アクセス箇所の添字のうち前記シフトレジスタへの接続位置を計算したい添字のループ変数に対して加算される値をCpとし、ループ内で最後のメモリアクセスを行なう組み合わせロジック部分と前記シフトレジスタへの接続位置を計算したい組み合わせロジック部分との間のパイプライン段数差をｎ<Cp−Clast>とした場合、
Clast−Cp−(ｎ<Cp−Clast>／ｍ)×ｓ
なる演算結果に基づいて、前記シフトレジスタの前記メモリアクセスを含む複数の組み合わせロジック部分に接続される位置を算出することを特徴とする請求項４記載のパイプライン高位合成システム。
【請求項６】
高位記述を受理し、そのループ記述部分に対してパイプライン高位合成を行なうことにより、直列に配された複数の組み合わせロジック部分の各相互間をそれぞれパイプラインレジスタで区切った形態の、パイプライン化された回路を生成する第１の工程と、
前記第１の工程によって生成された回路について、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせる第２の工程とを具備することを特徴とするパイプライン高位合成方法。
【請求項７】
前記第２の工程は、前記ループ記述部分に記述された各配列アクセス箇所の添字、前記ループ記述部分に記述されたループ変数のステップ数、メモリアクセスを含む複数の組み合わせロジック部分の相互間におけるパイプライン段数差、パイプラインサイクル数に基づいて、前記シフトレジスタのサイズを設定することを特徴とする請求項６記載のパイプライン高位合成方法。
【請求項８】
前記第２の工程は、
メモリアクセスに衝突が生じる２つの配列アクセス箇所の添字のうちループ変数に対して加算される値をCy，Cxとし、前記ループ記述部分に記述されたループ変数のステップ数をｓとし、メモリアクセスに衝突が生じる２つの組み合わせロジック部分の相互間におけるパイプライン段数差をｎ<Cx−Cy>とし、パイプラインサイクル数をｍとした場合、
｜Cy−Cx−(ｎ<Cx−Cy>／ｍ)×ｓ｜＋１
なる演算により、前記シフトレジスタのサイズを算出することを特徴とする請求項７記載のパイプライン高位合成方法。
【請求項９】
前記第２の工程は、前記ループ記述部分に記述された各配列アクセス箇所の添字、前記ループ記述部分に記述されたループ変数のステップ数、メモリアクセスを含む複数の組み合わせロジック部分の相互間におけるパイプライン段数差、パイプラインサイクル数に基づいて、前記シフトレジスタのサイズと、前記シフトレジスタの前記メモリアクセスを含む複数の組み合わせロジック部分に接続される位置とを設定することを特徴とする請求項６記載のパイプライン高位合成方法。
【請求項１０】
前記第２の工程は、
メモリアクセスに衝突が生じる２つの配列アクセス箇所の添字のうちループ変数に対して加算される値をCy，Cxとし、前記ループ記述部分に記述されたループ変数のステップ数をｓとし、メモリアクセスに衝突が生じる２つの組み合わせロジック部分の相互間におけるパイプライン段数差をｎ<Cx−Cy>とし、パイプラインサイクル数をｍとした場合、
｜Cy−Cx−(ｎ<Cx−Cy>／ｍ)×ｓ｜＋１
なる演算により、前記シフトレジスタのサイズを算出し、
ループ内で最後のメモリアクセスを行なう配列アクセス箇所の添字のうちループ変数に対して加算される値をClastとし、メモリアクセスを行なう配列アクセス箇所の添字のうち前記シフトレジスタへの接続位置を計算したい添字のループ変数に対して加算される値をCpとし、ループ内で最後のメモリアクセスを行なう組み合わせロジック部分と前記シフトレジスタへの接続位置を計算したい組み合わせロジック部分との間のパイプライン段数差をｎ<Cp−Clast>とした場合、
Clast−Cp−(ｎ<Cp−Clast>／ｍ)×ｓ
なる演算結果に基づいて、前記シフトレジスタの前記メモリアクセスを含む複数の組み合わせロジック部分に接続される位置を算出することを特徴とする請求項９記載のパイプライン高位合成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、高位記述を入力してパイプライン化された回路を生成するためのパイプライン高位合成システム及び方法に関する。
【背景技術】
【０００２】
周知のように、首記の如き現在の高位合成ツールは、ループ内に同一配列に対して２回以上のアクセスが発生すると、基本的にパイプライン合成ができなくなる。このようになると、ほとんどの場合性能未達となり、高位設計を諦めるか、多大なコストをかけて高位合成の入力となる記述を書き換えていく作業を行なう必要が生じる。特に、映像系の処理においては、このような課題が顕著である。
【０００３】
特許文献１には、並列に動作する複数のスレッドから共有メモリに対して同時にアクセスが行なわれたとき、スレッド間でアクセスの競合が起こらないようにする技術が開示されている。しかしながら、この特許文献１は、回路をパイプライン化することにより所望の性能を達成させることに対して何らの記述もなく、１サイクルパイプライン化を達成するという技術的思想は全く開示されていないものである。
【特許文献１】特開２００３−３０２６１
【発明の開示】
【発明が解決しようとする課題】
【０００４】
そこで、この発明は上記事情を考慮してなされたもので、例えば映像系を主体とする多くのアルゴリズム記述の自動的なパイプライン化を可能とし、所望の性能を達成する回路を生成する確率を大幅に向上させ得るパイプライン高位合成システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係るパイプライン高位合成システムは、高位記述を受理し、そのループ記述部分に対してパイプライン高位合成を行なうことにより、直列に配された複数の組み合わせロジック部分の各相互間をそれぞれパイプラインレジスタで区切った形態の、パイプライン化された回路を生成する第１の手段と、この第１の手段によって生成された回路について、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせる第２の手段とを備えるようにしたものである。
【０００６】
また、この発明に係るパイプライン高位合成方法は、高位記述を受理し、そのループ記述部分に対してパイプライン高位合成を行なうことにより、直列に配された複数の組み合わせロジック部分の各相互間をそれぞれパイプラインレジスタで区切った形態の、パイプライン化された回路を生成する第１の工程と、この第１の工程によって生成された回路について、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせる第２の工程とを備えるようにしたものである。
【発明の効果】
【０００７】
上記した発明によれば、メモリアクセスを含む複数の組み合わせロジック部分によりメモリへのアクセスに衝突が生じた場合、衝突が生じた複数の組み合わせロジック部分を、その複数の組み合わせロジック部分に対応して設定されたサイズのシフトレジスタを介してメモリにアクセスさせるようにしたので、例えば映像系を主体とする多くのアルゴリズム記述の自動的なパイプライン化を可能とし、所望の性能を達成する回路を生成する確率を大幅に向上させることができる。
【発明を実施するための最良の形態】
【０００８】
以下、この発明の実施の形態について図面を参照して詳細に説明する。図１は、この実施の形態で説明するパイプライン高位合成システムを示している。すなわち、高位合成システム１０１は、高位記述１１３（多くの場合ＣまたはSystemＣ等の言語で記述されている）を入力として、パイプライン化されたスループットの高い回路［ＲＴＬ（register transfer level）記述］１１４を生成するものである。
【０００９】
このような動作を実現するための構成要素として、高位合成システム１０１には、配列アクセス抽出部１０２、配列アクセス添字判定部１０３、ループステップ抽出・記憶部１０４、配列アクセス添字式記憶部１０５、高位合成エンジン部１０６、パイプラインサイクル数記憶部１０７、パイプライン段数取得・記憶部１０８、バッファレジスタサイズ計算部１０９、接続位置計算部１１０、接続回路生成部１１１、全体制御回路生成部１１２等が存在している。
【００１０】
このうち、配列アクセス抽出部１０２は、パイプライン化の対象となるループ記述内の配列アクセスを抽出している。配列アクセス添字判定部１０３は、抽出した配列アクセス部分の添字を判定している。ループステップ抽出・記憶部１０４は、ループ記述のループ変数の増分あるいは減分ステップ数を抽出して記憶している。配列アクセス添字式記憶部１０５は、配列アクセス箇所の添字の数式を記憶している。
【００１１】
また、高位合成エンジン部１０６は、メモリアクセスの衝突を無視する以外は一般の高位合成と同様の処理で高位合成を行なうものである。パイプラインサイクル数記憶部１０７は、ユーザから指定されたか、または、自動的に計算したパイプラインサイクル数を記憶しておくものである。パイプライン段数取得・記憶部１０８は、メモリアクセスの衝突を一旦無視して合成した回路中のメモリアクセス間パイプライン段数差を全て取得して記憶している。
【００１２】
さらに、バッファレジスタサイズ計算部１０９は、得られた情報に基づき必要なバッファレジスタサイズを計算している。接続位置計算部１１０は、パイプライン回路内のロジックとバッファレジスタとの接続位置を計算している。接続回路生成部１１１は、接続位置計算結果とメモリアクセスがリードかライトかとに応じて接続回路を生成している。全体制御回路生成部１１２は、以上の処理で作成されたパイプライン回路とバッファレジスタとメモリとを含む回路全体が正しく動作するように処理順序等を制御する回路を生成している。
【００１３】
次に、図２を用いて高位合成システム１０１の処理動作について説明する。この説明においては、結果的に、図１に示した各構成要素の働きについて解説することにもなる。また、説明の必要に応じて図３〜図５も活用する。
【００１４】
すなわち、処理が開始（ステップＳ１１）されると、高位合成システム１０１は、ステップＳ１２で、Ｃ言語等で記述された高位記述を受理し、ループ記述部分について配列アクセスを行なっている箇所を抽出する。
【００１５】
なお、図２には示していないが、一般に、高位合成システム１０１は、要素数の多い配列をメモリとして扱い、要素数の少ない配列はレジスタとして扱うことが多い。これは、レジスタを用いると回路のサイズが非常に大きくなるためである。その代わり、レジスタを用いると、複数の配列要素に同時にアクセスできる利点がある。
【００１６】
したがって、この時点で抽出された配列の要素が少なく、レジスタとして扱っても問題にならない場合は、以下の処理を行なう必要はなく、しかもレジスタなのでパイプライン化も問題なく行なえるはずである。つまり、以下のステップは、配列の要素数が多く、メモリに割り当てざるを得ない場合における処理ということになる。
【００１７】
なお、ループとは、図３に示されているように、Ｃ言語の例におけるforループのような記述のことを称している。なお、forループだけではなく、whileループやdo〜whileループ等を受理してもよい。
【００１８】
次に、高位合成システム１０１は、ステップＳ１３で、ループ内における、同一の配列のアクセスを行なっている全ての箇所において、添字の表現がループ変数の１次式で、かつ、ループ変数にかかる係数が１であるか否かを調べる。
【００１９】
ここで、ループ変数の１次式でないものが混じっていたり、ループ変数にかかる係数が１でないものが混じっていたりした場合（ＮＯ）は、以下のステップの処理を適用できないので、この実施の形態の方式によるパイプライン化を諦め、従来の方法で可能か否かの処理に移る。つまり、この実施の形態の処理としては終了（ステップＳ２５）する。
【００２０】
ステップＳ１３でＹＥＳの場合、高位合成システム１０１は、ステップＳ１４で、ループ変数のステップ数ｓを抽出して記憶する。ループ変数のステップ数ｓとは、例えばforループであれば、
「for（int i＝0； i＜100； i++）」
といった記述が書かれているはずで、この場合はループ毎にループ変数iの値が１増えるのでステップ数ｓは１となる。
【００２１】
同様に
「for（int i＝100； i＞0； i--）」
等と書かれていれば、ステップ数ｓは−１であり、
「for（int i＝100； i＞0； i-＝5）」
と書かれていれば、ステップ数ｓは−５である。
【００２２】
次に、高位合成システム１０１は、ステップＳ１５で、各配列アクセス部分の添字の式を抽出し、記憶しておく。例えば、配列変数名をＡとしたとき、
「Ａ［ｉ＋３］」
という表現があれば、添字の式とは「ｉ＋３」のことである。これをループ内の全ての配列アクセスの箇所から抽出する。
【００２３】
次に、高位合成システム１０１は、ステップＳ１６で、同一サイクルでメモリアクセスを同時に複数回行なえるという仮定に基づいて、パイプライン化高位合成を実施する。パイプライン回路については、図４を利用して説明する。すなわち、ループ内の論理を複数個のパイプラインレジスタで区切り、ループ変数ｉの値が０のときの入力、１のときの入力、２のときの入力、というように左側から次々にデータを流し込む。
【００２４】
このようにすることにより、ループ１回分の計算に要する時間（レイテンシー）は変わらないが、次々に計算をオーバーラップして行なえるため、計算全体の処理能力（スループット）は向上する。これがパイプライン化の目的である。
【００２５】
しかしながら、通常、１つのメモリデバイスは、同一サイクルで１回しかアクセスできないため、一般にはパイプライン化ができないことが多い。デュアルポートメモリを使えば、同一サイクルに２回までアクセスが可能ではあるが、ループ内で同一配列に対するアクセスが３箇所あれば、やはり衝突となり、通常の高位合成ツールはパイプライン化を諦める。
【００２６】
これに対し、この実施の形態の処理においては、同一サイクルにおいて同一のメモリに対するアクセスを複数回行なってもよいという仮定のもとに、一旦パイプライン化高位合成を実行する。メモリアクセスの衝突については、通常、図５のように表わされる。ボックスが横に６個並んだものが１個ずつ右にずれる形で階段状に並んでいる。メモリアクセスのある箇所がボックスの中に配列アクセスの形で描かれている。縦の列に２個以上同じ配列に対するアクセスが現われれば、それはメモリアクセスの衝突となる。
【００２７】
次に、高位合成システム１０１は、ステップＳ１７で、メモリアクセスに衝突があるか否かを判定する。衝突が無い場合（ＮＯ）は、従来の高位合成方法によってパイプライン化することが可能ということになるので、わざわざこの実施の形態の手法を適用する必要は無く、従来の手法によってパイプライン化を行なえばよいため、この実施の形態の処理としては終了（ステップＳ２５）する。
【００２８】
衝突がある場合（ＹＥＳ）、高位合成システム１０１は、次のステップＳ１８に進み、パイプラインサイクル数ｍを記憶する。回路の性能（スループット）を最大にする場合は、もちろんパイプラインサイクル数は１を設定することになるが、一般に回路性能を高くしようとすれば回路面積が増加するというトレードオフの関係があるため、パイプラインサイクル数を増やして性能を落とす代わりに、回路面積を小さくする方針を採用する場合がある。そのため、ここではパイプラインサイクル数を一般にｍとして、以下のステップの処理を実行する。
【００２９】
次に、高位合成システム１０１は、ステップＳ１９で、各メモリアクセス間のパイプライン段数の差を全て抽出して記憶する。ここでいうパイプライン段数の差について、図４を用いて説明する。図４の例では、ループ内に配列アクセス、つまり、メモリアクセスが２箇所ある（この例の場合はいずれもメモリリードとなる）。
【００３０】
すなわち、Ａ［ｉ］へのアクセスとＡ［ｉ＋５］へのアクセスとがパイプライン回路中に割り付けられた状態を示してある。この例の場合は、２つのアクセスの間にパイプラインレジスタ（四角の箱）が３個入っている。したがって、この場合のパイプライン段数差は３となる。この段数差は、高位合成ツールがスケジューリングや演算器の割り付け等を考慮して決めるものであり、高位合成ツールの利用者である設計者はこの段数を制御できないのが普通である。
【００３１】
次に、高位合成システム１０１は、ステップＳ２０で、以上の情報をもとに、必要となるバッファレジスタサイズを計算する。バッファレジスタサイズの計算式は、
｜Cy−Cx−(ｎ<Cx−Cy>／ｍ)×ｓ｜＋１  個  ……  （１）
となる。
【００３２】
この（１）式について解説する。CxとCyとは、それぞれ配列アクセスの添字のループ変数に対して加算される値、つまり、定数項である。例えばforループ内に配列アクセスＡ［ｉ＋Cx］、Ａ［ｉ＋Cy］が現われたとする。また、出現順はこの順であったとする。そして高位合成の結果、これがパイプライン回路に割り当てられたときの、２つのメモリアクセス間のパイプライン段数差をｎ<Cx−Cy>と表記している（<と>とは単に表記として使っており、大小関係を表わしているのではない）。
【００３３】
mはパイプラインサイクル数で、sはループ変数のステップ数である。このとき、２つのメモリアクセスをバッファレジスタを用いて衝突回避しようとすれば、バッファレジスタのサイズとして上記（１）式で示されるサイズだけが必要となる。Cx、Cy、sは負の値をとることがあり得る。これに対して、ｎ<Cx−Cy>は段数差であり、mはパイプラインサイクル数なので、いずれも正の数である。式中に現れる縦棒（｜）で囲まれた部分は絶対値を表わしている。
【００３４】
次に、高位合成システム１０１は、ステップＳ２１で、前のステップＳ２０の計算をメモリアクセスの全ての２点間について実行する。実際に必要となるバッファレジスタサイズは、その中の最大のものなので、得られた複数のバッファレジスタサイズのうち、最大値のものをサイズとして採用する。
【００３５】
次に、高位合成システム１０１は、ステップＳ２２で、パイプラインレジスタ間のメモリアクセスを含む組み合わせロジック部分とバッファレジスタとの接続を行なうにあたって、各組み合わせロジック部分内のメモリアクセス部分を、バッファレジスタのどの位置に接続するかを計算する。その計算式は、
Clast−Cp−(ｎ<Cp−Clast>／ｍ)×ｓ  ……  （２）
となる。
【００３６】
（２）式において、表記の意味は（１）式とほとんど同じであるが、Clastはループ内の最後のメモリアクセスに対する添字の定数項部分である。Cpは接続位置を計算したいメモリアクセスの添字の定数項部分である。ｎ<Cp−Clast>はループ内最後のメモリアクセスと接続位置を計算したいメモリアクセスとを含むそれぞれの組み合わせロジック部分間のパイプライン段数差である。ｍとｓとは（１）式と同じ意味である。したがって、ループ内最後のメモリアクセスに対しては、この値は常にゼロとなる。
【００３７】
これを全メモリアクセス部分に対して計算し、その中の最小の値（負の値もあり得る）に対する差（したがって、これは常にゼロ以上の値となる）を各組み合わせロジック部分に関連付けて記憶する。
【００３８】
次に、高位合成システム１０１は、ステップＳ２３で、バッファレジスタの各要素に番号を付ける。ループ変数のステップ数sが正の値であれば、バッファレジスタの先頭から末尾に向かって０，１，２，……と番号を付ける。sが負の値であれば、バッファレジスタの末尾から先頭に向かって０，１，２，……と番号を付ける。
【００３９】
そして、前ステップＳ２２で計算した接続位置に対して、各組み合わせロジックを結線する。各メモリアクセスがリードならバッファレジスタから組み合わせロジックに向かってデータが流れるように結線し、各メモリアクセスがライトなら組み合わせロジックからバッファレジスタに向かってデータが流れるように結線する。
【００４０】
次に、高位合成システム１０１は、ステップＳ２４で、全体の制御回路を生成して、処理を終了（ステップＳ２５）する。すなわち、前のステップまでに作り上げた回路に加えて必要なものは、メモリからバッファレジスタに各サイクル毎にデータを読み出してシフトインしていく回路（毎サイクル、読み出すアドレスをインクリメントまたはデクリメントしていく。ループ変数のステップ数が正ならインクリメントであり、ループ変数のステップ数が負ならデクリメントである）、バッファレジスタから各サイクル毎にシフトアウトされたデータをメモリに書き込む回路、これらの開始と終了のタイミングを調整するための回路等である。
【００４１】
なお、ループ内に配列からの読み出し（つまりメモリリード）しか無ければ、バッファレジスタからメモリにデータを書き込む回路は不要であり、同様にループ内にメモリライトしか無ければ、メモリからデータを読み出してバッファレジスタにシフトインする回路は不要である。ところで、ループ内で同一の配列に対して読み書き両方がある場合には、メモリからの読み出しと書き込みを同一サイクル内で実行する必要があることから、デュアルポートメモリの採用が必須となる。そうでなければデュアルポートメモリを採用する必要はない。
【００４２】
以上に一般的な処理動作を述べたが、以下に具体的な例を説明する。これまでに説明した数式が、どのような回路を構築するのかを具体的に説明する。
【００４３】
図６は、第１の具体例を説明している。すなわち、図６（ａ）に示すように、ループ内には２箇所、同一の配列からの読み出しがある。これを１サイクルパイプライン化しようとすると、図６（ｂ）に示されるようにメモリアクセスの衝突が発生する。
【００４４】
ここで、上記した（１）式及び（２）式の値を計算する。この計算結果は、図６（ｃ）にも示している。すなわち、C2−C1の値は５である。ｎ<C1−C2>の値は３である。mは１であり、sも１である。したがって、バッファレジスタのサイズは３であり、接続位置はそれぞれ２番目と０番目である。ステップ数が正の値なので、バッファレジスタの先頭から０，１，２と番号を付け、図６（ｄ）に示すように回路を接続する。
【００４５】
メモリから毎サイクル値が読み出されてバッファレジスタにシフトインしていく様子を図６（ｅ）に示している。すなわち、パイプライン回路のＡ［ｉ］の位置に計算すべきデータの先頭（ｉ＝０のときの計算）が到達したときは、バッファレジスタの２，１，０番目にそれぞれＡ［０］、Ａ［１］、Ａ［２］の値が入っており、接続の具合から、Ａ［ｉ］の組み合わせロジック部分は、確かにＡ［０］の値を用いて計算を行なえることがわかる。
【００４６】
それから３サイクル後にはＡ［ｉ＋５］の箇所に計算すべきデータの先頭（ｉ＝０のときの計算）が到達する。このとき、Ａ［ｉ］の箇所には、ｉ＝３のときの計算すべきデータが到達している。図を見ると、Ａ［ｉ］はＡ［３］の値を読み出せるようになっており、Ａ［ｉ＋５］はＡ［５］の値を読み出せるようになっている。以下、このまま推移するので、開始と終了を適切に制御すれば、１サイクルパイプライン化が可能であることがわかる。
【００４７】
図７は、第２の具体例を示している。この第２の具体例は、図６と同様に配列からの読み出ししかない例であるが、今度は、図７（ａ）に示すように配列アクセスが３箇所になっている。これを１サイクルパイプライン化する場合、図７（ｂ）の階段状の図を見てわかるように、メモリアクセスが衝突している。
【００４８】
ここで、上記した（１）式及び（２）式の値を計算する。この計算結果は、図７（ｃ）にも示している。すなわち、C2−C1の値は−５であり、C3−C1の値は−２であり、C3−C2の値は３である。ｎ<C1−C2>の値は３であり、ｎ<C1−C3>の値は５であり、ｎ<C2−C3>の値は２である。mは１であり、sは１である。
【００４９】
このため、バッファレジスタのサイズを３通り計算すると、それぞれ９，８，２となるので、その最大値をとってバッファレジスタのサイズは９となる。また、接続位置を計算すると、（２）式の通りだとそれぞれ−７，１，０となるので、最小値の−７に対する差分で表わし、それぞれ０，８，７番目となる。これにより、接続関係は、図７（ｄ）に示すように、Ａ［ｉ＋５］，Ａ［ｉ＋３］，Ａ［ｉ］がバッファレジスタの０番目、７番目、８番目にそれぞれ接続される。
【００５０】
メモリから毎サイクル値が読み出されてバッファレジスタにシフトインしていく様子を図７（ｅ）に示している。すなわち、パイプライン回路のＡ［ｉ＋５］の位置に計算すべきデータの先頭（ｉ＝０のときの計算）が到達したときは、バッファレジスタの０番目の位置に丁度Ａ［５］の値が入っており、Ａ［ｉ＋５］の箇所はＡ［５］の値を用いて計算を行なえる。
【００５１】
それから３サイクル後には、Ａ［ｉ］の位置にＡ［０］の値が供給され、このときＡ［ｉ＋５］の位置にＡ［８］の値が供給されることになるが、Ａ［ｉ］はｉ＝０のときのＡ［ｉ］を使うことになるので正しく、またこのときＡ［ｉ＋５］はｉ＝３のときの計算に入るので、Ａ［８］を使うということも正しい。
【００５２】
さらに２サイクル後には、Ａ［ｉ＋３］の箇所にｉ＝０のときの計算が到達し、このときバッファレジスタの該当箇所にはＡ［３］が格納されており、同様に利用するデータは正しい。以下、このまま推移するので、開始と終了を適切に制御すれば、１サイクルパイプライン化が可能であることがわかる。
【００５３】
図８は、第３の具体例を示している。この第３の具体例はかなり複雑な例である。図８（ａ），（ｂ）に示すように、配列アクセスは４箇所で、しかも読み出しと書き込みが混在している。ループ変数のステップ数は−２である。そしてここでの設定として、パイプラインサイクル数を２とした。
【００５４】
計算された値は全て図８（ｃ）に示している。すなわち、バッファレジスタサイズは結果的に２２になり、接続位置は２０，２１，８，０番目となる。これにより、図８（ｄ）に示すように、Ａ［ｉ＋２］，Ａ［ｉ−１］，Ａ［ｉ＋６］，Ａ［ｉ＋８］がバッファレジスタの２０，２１，８，０番目に接続される。なお、ループ変数のステップ数が負の値であるため、バッファレジスタの番号を図６、図７とは逆に付けている。
【００５５】
また、メモリリードとメモリライトとが発生するため、この場合のメモリはデュアルポートメモリとなり、メモリから読み出してバッファレジスタにシフトインすると同時に、バッファレジスタからシフトアウトされたデータをメモリの該当するアドレスに書き込むことになる。
【００５６】
バッファレジスタ内の値の推移を図８（ｅ）に示している。すなわち、Ａ［ｉ＋２］の接続された位置にＡ［１０２］の値がシフトされて到達する時点から計算が始まる。このとき、Ａ［ｉ＋２］は書き込みなので、メモリから読み出されてきたＡ［１０２］の値をバッファレジスタ上で書き換えることになる。
【００５７】
それから２サイクル後には、Ａ［ｉ−１］の部分に計算の流れが到達する。このとき、Ａ［ｉ−１］はＡ［９９］の値を読み出すことになると同時に、Ａ［ｉ＋２］の部分はＡ［１００］の値を書き込むことになる。以下、推移を追うと、Ａ［ｉ＋６］の位置に計算の流れが到達するとき、Ａ［ｉ＋６］はＡ［１０６］の値を上書きすることになり、このサイクルではＡ［ｉ−１］はＡ［９３］の値を利用した計算であり、Ａ［ｉ＋２］はＡ［９４］の値を上書きすることになる。以下、さらに推移を追っていけば、配列要素の上書きや読み出しがすべて正しく行なわれることがわかる。しかも、２サイクルパイプラインということで、２サイクル毎に意味のある計算結果が出てくる回路となる。
【００５８】
ここで、図６〜図８に示した具体例では、パイプラインサイクル数とループ変数ステップ数との比が１なので、バッファレジスタには毎サイクル、メモリからのデータをシフトイン、あるいは毎サイクルデータをシフトアウトしていくことで実現できる。ところが、この比が１でない場合については制御が少々異なる。バッファレジスタ量や接続位置は、これまでに説明してきた方法をそのまま採用すればよいので問題無いが、バッファレジスタのシフト方法などについて少し工夫が必要となる。これについて、図９に示す第４の具体例として説明する。
【００５９】
この第４の具体例は、図９（ａ），（ｂ）に示すように、ループ変数のステップ数が２、パイプラインサイクル数を３にした例である。図９（ｃ）に計算結果、図９（ｄ）に接続関係、図９（ｅ）にバッファレジスタへのデータの埋まり具合を示している。図９（ｅ）に示した階段状の部分を見るとわかる通り、Ａ［ｉ］の位置にＡ［０］を必要とする計算が到達した後、３サイクル後にＡ［ｉ］の位置にＡ［２］が必要でかつＡ［ｉ＋５］の位置にＡ［５］を必要とする計算が到達する。しかしながら、バッファレジスタは、この２つの状態の間は２サイクルとなっている。このため、３サイクルの間にバッファレジスタを２つ分シフトするという制御回路を作る必要がある。
【００６０】
ここで、上記した実施の形態において、バッファレジスタのサイズを計算できるということは、バッファレジスタのサイズがなるべく小さくなるようにパイプラインステージのスケジュールを制御すれば、スループットを高く保ったままで回路面積をより小さくすることが可能となる。
【００６１】
また、バッファレジスタのサイズ計算式は、実は（１）式に示したものよりも１小さくてもよい。これは、複数個所で、同一サイクルで同一のメモリから読み出す場合、アドレスが同じなのでバッファを介さなくても衝突にならない場合であることを示している。実施の形態においては、このような特殊な場合もメモリアクセスの衝突として扱い、必ずバッファレジスタを生成することにしたため１を加えた計算式を示してあるが、アドレスが同じならば実際には衝突ではない。その代わり、このような場合にバッファレジスタを生成しないことにすると、図２のステップＳ２４における全体の制御回路の生成が複雑になる。実際に高位合成ＣＡＤツールとして実現する場合は、ツールの作りやすさと生成する回路の構成等の要素とをいろいろ考慮して決めることになる。
【００６２】
上記した実施の形態によれば、メモリとパイプライン回路との間にバッファレジスタを自動的に挟むことで、メモリアクセスの競合を防いで、例えば映像系を主体とする多くのアルゴリズム記述を自動的にパイプライン回路に高位合成することができる。このため、所望の性能を達成する回路を生成する確率を大幅に向上させルことができる。また、この実施の形態の手法が成功するためには、配列アクセスの添字に一定の制限がかかるが、多くの映像系アルゴリズムでは十分に許容範囲内である。しかも、パイプライン化がなされる場合は、間違いなく１サイクルパイプライン化が可能である。
【００６３】
なお、この発明は上記した実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を種々変形して具体化することができる。また、上記した実施の形態に開示されている複数の構成要素を適宜に組み合わせることにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素から幾つかの構成要素を削除しても良いものである。さらに、異なる実施の形態に係る構成要素を適宜組み合わせても良いものである。
【図面の簡単な説明】
【００６４】
【図１】この発明の実施の形態を示すもので、パイプライン高位合成システムを説明するために示すブロック構成図。
【図２】同実施の形態における高位合成システムの処理動作を説明するために示すフローチャート。
【図３】同実施の形態における高位合成システムが受理するループ記述部分の一例を説明するために示す図。
【図４】同実施の形態における高位合成システムがパイプライン化高位合成を実施して得られるパイプライン回路の一例を説明するために示す図。
【図５】同実施の形態における高位合成システムがパイプライン化高位合成を実施する際のメモリアクセスの衝突を説明するために示す図。
【図６】同実施の形態における高位合成システムが実施するパイプライン化高位合成処理の第１の具体例を説明するために示す図。
【図７】同実施の形態における高位合成システムが実施するパイプライン化高位合成処理の第２の具体例を説明するために示す図。
【図８】同実施の形態における高位合成システムが実施するパイプライン化高位合成処理の第３の具体例を説明するために示す図。
【図９】同実施の形態における高位合成システムが実施するパイプライン化高位合成処理の第４の具体例を説明するために示す図。
【符号の説明】
【００６５】
１０１…高位合成システム、１０２…配列アクセス抽出部、１０３…配列アクセス添字判定部、１０４…ループステップ抽出・記憶部、１０５…配列アクセス添字式記憶部、１０６…高位合成エンジン部、１０７…パイプラインサイクル数記憶部、１０８…パイプライン段数取得・記憶部、１０９…バッファレジスタサイズ計算部、１１０…接続位置計算部、１１１…接続回路生成部、１１２…全体制御回路生成部、１１３…高位記述、１１４…パイプライン化ＲＴＬ記述。
【図１】
2007272797.tif 000003
【図２】
2007272797.tif 000004
【図３】
2007272797.tif 000005
【図４】
2007272797.tif 000006
【図５】
2007272797.tif 000007
【図６】
2007272797.tif 000008
【図７】
2007272797.tif 000009
【図８】
2007272797.tif 000010
【図９】
2007272797.tif 000011
【手続補正書】
【提出日】平成18年4月13日(2006.4.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
さらに、バッファレジスタサイズ計算部１０９は、得られた情報に基づき必要なバッファレジスタサイズを計算している。接続位置計算部１１０は、パイプライン回路内のロジックとバッファレジスタとの接続位置を計算している。接続回路生成部１１１は、接続位置計算結果とメモリアクセスがリードかライトかに応じて接続回路を生成している。全体制御回路生成部１１２は、以上の処理で作成されたパイプライン回路とバッファレジスタとメモリとを含む回路全体が正しく動作するように処理順序等を制御する回路を生成している。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
上記した実施の形態によれば、メモリとパイプライン回路との間にバッファレジスタを自動的に挟むことで、メモリアクセスの競合を防いで、例えば映像系を主体とする多くのアルゴリズム記述を自動的にパイプライン回路に高位合成することができる。このため、所望の性能を達成する回路を生成する確率を大幅に向上させることができる。また、この実施の形態の手法が成功するためには、配列アクセスの添字に一定の制限がかかるが、多くの映像系アルゴリズムでは十分に許容範囲内である。しかも、パイプライン化がなされる場合は、間違いなく１サイクルパイプライン化が可能である。