(57)【要約】【課題】高級言語で記述されたループ記述をパイプライン動作させる実用的な規模の回路記述を自動で生成すること。【解決手段】パイプライン動作へ遷移する際に高級言語で記述されたスキップ文が割りあてられた状態番号と、ユーザ指定もしくはシステムが自動設定した１回のループをパイプラインに投入する際に必要なサイクル数とを基に、パイプライン動作可能なループ制御部、ループ脱出制御部を持つ状態遷移を自動で生成するパイプライン構成生成手段１５０を備える。【選択図】図１
2008071089.tif 000002
【特許請求の範囲】
【請求項１】
パイプライン動作へ遷移する際に高級言語で記述されたスキップ文が割りあてられた状態番号と、ユーザ指定もしくはシステムが自動設定した１回のループをパイプラインに投入する際に必要なサイクル数とを基に、パイプライン動作可能なループ制御部、ループ脱出制御部を持つ状態遷移を自動で生成するパイプライン構成生成手段を備えることを特徴とする動作合成システム。
【請求項２】
前記スキップ文に代えて繰り返し文が割りあてられた状態番号を基にすることを特徴とする請求項１記載の動作合成システム。
【請求項３】
前記パイプライン動作可能なループ制御手段とループ脱出制御手段は、生成するパイプライン構成の各ステージを制御するためのステージフラグを有し、該ステージフラグと、前記繰り返し文から生成された第１の制御フラグと、前記スキップ文から生成された第２の制御フラグとを用いて前記パイプライン動作可能なループ制御手段とループ脱出制御手段を構成することを特徴とする請求項１または２記載の動作合成システム。
【請求項４】
パイプライン動作へ遷移する際に高級言語で記述されたスキップ文が割りあてられた状態番号と、ユーザ指定もしくはシステムが自動設定した１回のループをパイプラインに投入する際に必要なサイクル数とを基に、パイプライン動作可能なループ制御部、ループ脱出制御部を持つ状態遷移を自動で生成するパイプライン構成生成ステップを有することを特徴とする動作合成方法。
【請求項５】
前記スキップ文に代えて繰り返し文が割りあてられた状態番号を基にすることを特徴とする請求項４記載の動作合成方法。
【請求項６】
前記パイプライン動作可能なループ制御手段とループ脱出制御手段は、生成するパイプライン構成の各ステージを制御するためのステージフラグを有し、該ステージフラグと、前記繰り返し文から生成された第１の制御フラグと、前記スキップ文から生成された第２の制御フラグとを用いて前記パイプライン動作可能なループ制御手段とループ脱出制御手段を構成することを特徴とする請求項４または５記載の動作合成方法。
【請求項７】
コンピュータに請求項１から３のいずれか１項に記載の機能を実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特にＣ言語プログラム等の高級言語で記述された動作から、その動作を実現するハードウェア記述を自動で生成する動作合成システムに関する。
【背景技術】
【０００２】
従来の動作合成システムの一例が、特許文献１に開示されている。この従来の動作合成システムは、ＣＤＦＧ生成手段と、スケジューリング手段と、アロケーション手段、データパス生成手段と、コントローラ生成手段から構成されている。
【０００３】
このような構成を有する従来の動作合成システムは、ループ部をパイプライン化するにあたり、次のように動作する。
【０００４】
すなわち、ループ処理、および非ループ処理を含むＣ言語プログラム等の動作記述から、コントロールデータフローグラフを生成するＣＤＦＧ生成手段は、ループ部と非ループ部を識別し、ループ部については、ループ制御部により制御を可能とする。ループ制御部には、パイプラインのステージ段数と同じビット数のシフトレジスタ機能を有しており、ループ回数が合成時に確定しないループ処理を可能とする。
【特許文献１】特開２００４−３２６４６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述の従来技術では、Ｃ言語等で記述されたｂｒｅａｋ文や、ｄｏ−ｗｈｉｌｅ文を含むループ処理をパイプライン化することが困難であった。
【０００６】
このような記述を含むループに対しては、従来は、ｂｒｅａｋ文や、ｄｏ−ｗｈｉｌｅ文を含まないループ記述に書き換えることで、パイプライン化し、並列動作させていたが、アルゴリズムまでも変更する必要が生じ、記述の変更に伴う工数は、膨大になっていた。
【０００７】
ｂｒｅａｋ文や、ｄｏ−ｗｈｉｌｅ文を含むループ処理をパイプライン化することが困難である理由は、ループ部をパイプライン化し並列動作させることにより、ループ脱出動作や、ループ動作の一部もしくは全部を停止させ別の処理をする制御が複雑になるためである。
【０００８】
また、Ｃ言語等で記述されたループ回数がコンパイル時に確定するループ記述を高速に動作させる場合、パイプライン化して高速化する手法がとることが困難であった。なぜなら、ループ回数がプログラム記述からは確定しないループをパイプライン化して並列動作させる制御が複雑になり、高速化を阻害するからである。
【０００９】
例えば、動作合成の分野では、従来技術では、ループ回数がコンパイル時に決まらないループ記述をシフトレジスタで実現する手法がとられているが、シフトレジスタという具体化されたハードウェアを利用するため、並列化コンパイラに応用することが困難になっていた。
【００１０】
本発明は、以上説明した問題点を解決するためになされたものである。その目的は、時間当たりの処理能力(スループット)を高めるべく、高級言語で記述されたループ記述をパイプライン動作させる実用的な規模の回路記述を自動で生成し、ユーザが自らその記述を変更することを不要とすることにある。このループ記述の中には、ループを途中で脱出する記述や、ループ途中にループの一部、もしくは全部の動作を停止させ、別の処理を実行する記述が含まれる。
【課題を解決するための手段】
【００１１】
上記課題を解決するために、本発明は、パイプライン動作へ遷移する際に高級言語で記述されたスキップ文が割りあてられた状態番号と、ユーザ指定もしくはシステムが自動設定した１回のループをパイプラインに投入する際に必要なサイクル数とを基に、パイプライン動作可能なループ制御部、ループ脱出制御部を持つ状態遷移を自動で生成するパイプライン構成生成手段を備える動作合成システムを提供する。
【００１２】
また、本発明は、パイプライン動作へ遷移する際に高級言語で記述されたスキップ文が割りあてられた状態番号と、ユーザ指定もしくはシステムが自動設定した１回のループをパイプラインに投入する際に必要なサイクル数とを基に、パイプライン動作可能なループ制御部、ループ脱出制御部を持つ状態遷移を自動で生成するパイプライン構成生成ステップを有する動作合成方法を提供する。
【発明の効果】
【００１３】
本発明によれば、時間当たりの処理能力(スループット)を高めるべく、高級言語で記述されたループ記述をパイプライン動作させる実用的な規模の回路記述を自動で生成し、ユーザが自らその記述を変更することを不要とすることができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の第１の実施の形態について図面を参照して詳細に説明する。
図１を参照すると、本実施の形態における動作合成システムでは、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）１００が、ＣＤＦＧ生成手段１１０と、スケジューリング手段１２０と、アロケーション手段１３０と、状態遷移生成手段１４０と、パイプライン構成生成手段１５０と、ＲＴＬ生成手段１６０から構成されている。
【００１５】
ＣＤＦＧ生成手段１１０は、ループ記述であることを識別する情報を埋め込んだＣＤＦＧを生成する。このループ情報には、ユーザが指定したパイプライン化する／しないに関する指定も含まれる。同時に、ループ中に記述されたｇｏｔｏ文や、ｄｏ−ｗｈｉｌｅ文についても、それを識別可能なＣＤＦＧとして生成する。
【００１６】
スケジューリング手段１２０、アロケーション手段１３０および状態遷移生成手段１４０は、パイプライン化を意識しなくとも実現が可能である。
【００１７】
パイプライン構成生成手段１５０は、パイプライン化する場合には、ユーザが指定したＤｌｌ、もしくは、システムが自動で判定したＤｌｌと、状態遷移生成手段で生成されたｇｏｔｏ文、ｄｏ−ｗｈｉｌｅ文の状態番号に従って、パイプライン化した状態遷移と、ステージフラグ制御部、ループ脱出制御部をあわせて生成する。
【００１８】
ＲＴＬ生成手段１６０は、生成した状態遷移からＲＴＬ記述を生成する。
【００１９】
次に、図２のフローチャートを参照して本実施の形態の全体の動作について説明する。
【００２０】
まず、ユーザの記述したＣ言語等のプログラム言語を入力し、ＣＤＦＧ生成手段１１０によりＣＤＦＧを生成する（ステップＡ１）。
【００２１】
次に、スケジューリング手段１２０によりスケジューリングし（ステップＡ２）、アロケーション手段１３０によりレジスタや演算器を割り当てる（ステップＡ３）。
【００２２】
そして、状態遷移生成手段１４０により状態遷移を生成する（ステップＡ４）。
【００２３】
次に、パイプライン構成生成手段１５０では、状態遷移生成手段２４０で生成された状態遷移構成をパイプライン動作可能な状態遷移構成に組み替える（ステップＡ５）。
【００２４】
最後にＲＴＬ生成手段１６０によりＲＴＬ言語記述を生成する（ステップＡ６）。
【００２５】
したがって、本実施の形態では、ループ中にあるスキップ文であるｂｒｅａｋ文や繰り返し文であるｄｏ−ｗｈｉｌｅ文をスケジューリングし、状態遷移生成手段１４０で、パイプライン動作しない状態遷移を生成し、また、状態遷移生成手段１４０での状態番号とユーザもしくはシステムが自動で生成したＤＩＩとを利用してパイプライン動作可能な制御部に再構成するため、ｂｒｅａｋ文やｄｏ−ｗｈｉｌｅ文をパイプライン動作可能なＲＴＬに変換することができる。
【００２６】
以下で、さらに詳細に本実施の形態について述べる。
まず、コンピュータ１００は、入力となるループ記述、ループ脱出記述、ループ停止記述を内部で識別可能な形で保持する。ここで、ループ記述については、例えば、Ｃ言語プログラムの場合、ｗｈｉｌｅ文、ｆｏｒ文、ｄｏ−ｗｈｉｌｅ文で記述する。これらを内部表現に変換する際に、ループであることを識別できる識別子を付加する。
【００２７】
ループの脱出については、例えば、Ｃ言語プログラムの場合、ｂｒｅａｋ文、ｇｏｔｏ文で記述される。このループ脱出相当の記述も、ｂｒｅａｋ文をｇｏｔｏ文で一般的に表現し、ｇｏｔｏ文を識別する内部表現に変換する。
【００２８】
また、例えば、Ｃ言語プログラムにおいて、ループ処理の一部、もしくは全部を一時停止させて、停止中に別の処理を実行する機能は、ｄｏ−ｗｈｉｌｅ文で記述する。ｄｏ−ｗｈｉｌｅ文で記述したループ処理については、ｄｏ−ｗｈｉｌｅ文のループ条件とｂｏｄｙ部を識別する内部表現に変換する。
【００２９】
パイプライン構成生成手段１５０では、状態遷移生成手段１４０で生成されたループ記述の状態遷移に対してパイプライン化指定がある場合、パイプライン動作可能な状態遷移に変換する。このとき、ｇｏｔｏ文、ｄｏ−ｗｈｉｌｅ文のｂｏｄｙ部に対して、もとの状態遷移中の状態番号を利用して、ステージフラグ制御部とループ脱出制御部を追加した、ループの途中脱出可能、かつ、ループの一部、もしくは、全部を一時停止させることが可能なパイプライン動作の状態遷移を生成する。
【００３０】
パイプライン構成は、一般的に、規模が大きいが高速に処理できる回路から、処理速度が落ちるが回路規模が小さくなる回路まで、段階的に変化させることが可能である。本システムが合成するｇｏｔｏ文、ｄｏ−ｗｈｉｌｅ文を有するループ記述においても、このパイプライン構成のバリエーションをユーザが指定することができ、ユーザの所望に従ったパイプライン構成を生成する。
【００３１】
この処理速度を変えるパイプライン構成のパラメタとして、ループをパイプライン化する際、１回の繰り返しをパイプラインに投入するサイクル数をＤｌｌ(Data Initiation Interval)と表現する。
【００３２】
パイプライン構成の状態遷移は、ループの先頭の状態からＤｌｌ毎に状態を区切る。このＤｌｌ状態のグループをステージと呼ぶ。
【００３３】
ループの先頭のＤｌｌ状態をまとめたグループから第１ステージ、第２ステージと順に番号付ける。
【００３４】
この各ステージの切れ目で状態を折りたたみ、ステージ内の状態を重ねていくことで、基本的なパイプライン構成ができる。
【００３５】
ただし、各ステージの実行は、ステージごとにステージフラグを作成し、そのステージフラグがたった場合にのみ実行するという制御を追加する。
【００３６】
こうして構成されたパイプライン構成のループに対して、ループの各状態にステージフラグ制御部を追加し、ループの脱出状態にパイプラインループ脱出制御部を追加することで生成できる。
【００３７】
この基本変換を図３に示す。図３の右上の構成がＤｌｌ＝１と指定した最高速のパイプライン動作をする構成である。右下は、Ｄｌｌ＝２と指定した速度を落としたパイプライン動作をする構成である。基本構成のステージフラグ制御部は、小さい番号のステージフラグの値を、１つ大きい番号のステージフラグに代入する動作から構成される。また、基本構成のパイプラインループ脱出制御部は、全ステージフラグが０になったときにループを脱出する動作で構成される。
【００３８】
それぞれの制御部の構成について、Ｄｌｌ＝１の場合を図４に、Ｄｌｌ＝２の場合を図５に示す。
【００３９】
ｇｏｔｏ文がある場合のループ動作を、パイプライン動作可能な構成で生成するには、基本構成に加えて、以下の手順を追加する。
【００４０】
１．パイプライン構成を生成する際に、各ｇｏｔｏ文に対応するフラグを生成する。
【００４１】
２．ｇｏｔｏ文は、そのフラグのセット動作に変更する。
【００４２】
３．ｇｏｔｏ文がスケジューリングされた状態番号から算出したステージ番号と、パイプライン構成時の状態番号、ｇｏｔｏ文から生成したフラグ名を記録する。
【００４３】
４．フラグ制御部の生成時、ステージフラグの基本構成に対して、ｇｏｔｏ文のステージ番号より小さいステージ番号のステージフラグを作成する式に対して、ｇｏｔｏのフラグを＆する制御を追加する。
【００４４】
５．パイプライン化ループ脱出制御部は、基本構成と同じものを生成する。
【００４５】
上記操作に従って生成するＤｌｌ＝１のパイプライン構成を図６に示す。また、Ｄｌｌ＝２の場合のパイプライン構成を図７に示す。
【００４６】
ｄｏ−ｗｈｉｌｅ文がある場合のループ動作を、パイプライン動作可能な構成で生成するには、基本構成に加えて、以下の手順を追加する。
【００４７】
１．パイプライン構成を生成する際に、各ｄｏ−ｗｈｉｌｅ文に対応するフラグを生成する。
【００４８】
２．ｄｏ−ｗｈｉｌｅ文は、その条件式の評価値を生成したフラグに代入する。
【００４９】
３．ｄｏ−ｗｈｉｌｅ文がスケジューリングされた状態番号からステージ番号とパイプライン化後の状態番号、ｄｏ−ｗｈｉｌｅ文から生成したフラグ名を記録する。
【００５０】
４．上記記録したｄｏ−ｗｈｉｌｅのステージ番号より小さい番号のステージ実行部を生成する際、ステージ実行制御にステージフラグが１であるだけでなく、ｄｏ−ｗｈｉｌｅフラグが０であるという条件を追加する。
【００５１】
５．フラグ制御部の生成時、ｄｏ−ｗｈｉｌｅのステージ番号以下のステージフラグ値作成を、ｄｏ−ｗｈｉｌｅフラグが０の場合のみに限定する制御を追加する。
【００５２】
６．フラグ制御部の生成時、ｄｏ−ｗｈｉｌｅのステージ番号より大きいステージフラグ値作成で、ｄｏ−ｗｈｉｌｅフラグが０の場合、ステージフラグ値が０になるように制御を追加する。
【００５３】
７．パイプライン化ループ脱出制御部は、基本構成と同じものを生成する。
【００５４】
上記操作に従って生成するＤｌｌ＝１のパイプライン構成を図８に示す。また、Ｄｌｌ＝２の場合のパイプライン構成を図９に示す。
【００５５】
以上説明した本実施の形態によれば、ループ脱出や、ループの一時停止記述を含むプログラム記述を、従来技術よりも少ない工数で、高速処理が可能となる。その理由は、従来の方式では、ループ脱出やループの一部、もしくは全部の一時停止記述を含む記述を高速に処理させる必要が発生した場合、記述を修正してパイプライン処理をさせるか、場合によっては、アルゴリズム自体を修正してパイプライン処理させるなどの対応が必要であったからである。
【００５６】
また、ループ脱出や、ループの一時停止記述を含むプログラム記述を変更することなくパイプライン化する回路が生成できるので、パイプライン化する際のパラメタを変更するだけで、同一の記述から、処理速度や、消費するハードウェアリソースの量などを変えたパイプライン処理記述を生成できる。その理由は、従来のシステムでは、ループ脱出やループの一部、もしくは全部の一時停止記述を含む記述は、自動でパイプライン化することが不可能であり、ＲＴＬ回路記述を得る場合には、ＲＴＬ記述によりパイプライン処理を作成する必要があり、ＲＴＬ回路記述でパイプライン化する場合、処理速度やハードウェアリソースの量を変更するためにはパラメタ変更にはとどまらず、記述を大幅に書き換える必要があったためである。
【００５７】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
図１０を参照すると、本実施の形態における動作合成システムでは、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）２００が、ＣＤＦＧ生成手段２１０と、スケジューリング手段２２０と、アロケーション手段２３０と、状態遷移生成手段２４０と、ＲＴＬ生成手段２５０から構成されている。
【００５８】
ＣＤＦＧ生成手段２１０は、ループ記述であることを識別する情報を埋め込んだＣＤＦＧを生成する。このループ情報には、ユーザが指定したパイプライン化する／しないに関する指定も含まれる。同時に、ループ中に記述されたｇｏｔｏ文や、ｄｏ−ｗｈｉｌｅ文についても、それを識別可能なＣＤＦＧとして生成する。
【００５９】
スケジューリング手段２２０とアロケーション手段２３０は、パイプライン化を意識しなくとも実現が可能である。
【００６０】
状態遷移生成手段２４０は、スケジューリング時の情報を利用して、状態遷移を生成する。パイプライン化する場合には、ユーザ指定のＤｌｌ、もしくは、システムが自動で設定したＤｌｌと、ｇｏｔｏ文、ｄｏ−ｗｈｉｌｅ文のスケジューリング時の情報に従って、パイプライン化した状態遷移と、ステージフラグ制御部、ループ脱出制御部をあわせて生成する。ＲＴＬ生成手段２５０は、生成した状態遷移からＲＴＬ記述を生成する。
【００６１】
次に、図１１のフローチャートを参照して本実施の形態の全体の動作について説明する。
【００６２】
まず、ユーザの記述したＣ言語等のプログラム言語を入力し、ＣＤＦＧ生成手段２１０によりＣＤＦＧを生成する（ステップＢ１）。
【００６３】
次に、スケジューリング手段２２０によりスケジューリングする（ステップＢ２）。
【００６４】
さらに、アロケーション手段２３０によりレジスタや演算器を割り当てる（ステップＢ３）。
【００６５】
そして、状態遷移生成手段２４０により状態遷移を生成する（ステップＢ４）。
【００６６】
最後に、ＲＴＬ生成手段２５０によりＲＴＬ言語記述を生成する（ステップＢ５）。
【００６７】
上記の本実施の形態では、ループ中にあるｂｒｅａｋ文やｄｏ−ｗｈｉｌｅ文をスケジューリングし、状態遷移生成手段２４０で、その結果得られる状態番号とユーザ設定、もしくはシステムが自動設定したＤＩＩとを利用してパイプライン動作可能な制御部を生成するため、ｂｒｅａｋ文やｄｏ−ｗｈｉｌｅ文をパイプライン動作可能なＲＴＬに変換することができる。
【００６８】
なお、上述する各実施の形態は、本発明の好適な実施の形態であり、本発明の要旨を逸脱しない範囲内において種々変更実施が可能である。例えば、コンピュータ１００、２００の機能を実現するためのプログラムを装置に読込ませて実行することにより装置の機能を実現する処理を行ってもよい。さらに、そのプログラムは、コンピュータ読み取り可能な記録媒体であるＣＤ−ＲＯＭまたは光磁気ディスクなどを介して、または伝送媒体であるインターネット、電話回線などを介して伝送波により他のコンピュータシステムに伝送されてもよい。
【００６９】
また、本発明は、これまでＣ言語等で記述されたプログラムを自動で高速な回路記述に変換する動作合成システムに適用できる。また、Ｃ言語等で記述されたプログラムを並列処理可能なプロセッサのアセンブラに置換する自動並列化コンパイラ等にも適用可能である。
【図面の簡単な説明】
【００７０】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】本発明の第１の実施の形態におけるループ記述から生成される通常の状態遷移と、パイプライン構成の状態遷移(ＤＩＩ＝１,２)である。
【図４】本発明の第１の実施の形態におけるループ記述から生成されるＤＩＩ＝１の基本パイプライン構成の詳細を示す図である。
【図５】本発明の第１の実施の形態におけるループ記述から生成されるＤＩＩ＝２の基本パイプライン構成の詳細を示す図である。
【図６】本発明の第１の実施の形態におけるｂｒｅａｋを含むループ記述から生成されるＤＩＩ＝１のパイプライン構成の詳細を示す図である。
【図７】本発明の第１の実施の形態におけるｂｒｅａｋを含むループ記述から生成されるＤＩＩ＝２のパイプライン構成の詳細を示す図である。
【図８】本発明の第１の実施の形態におけるｄｏ−ｗｈｉｌｅを含むループ記述から生成されるＤＩＩ＝１のパイプライン構成の詳細を示す図である。
【図９】本発明の第１の実施の形態におけるｄｏ−ｗｈｉｌｅを含むループ記述から生成されるＤＩＩ＝２のパイプライン構成の詳細を示す図である。
【図１０】本発明の第２の実施の形態の構成を示すブロック図である。
【図１１】本発明の第２の実施の形態の動作を示す流れ図である。
【符号の説明】
【００７１】
１００，２００    コンピュータ（中央処理装置；プロセッサ；データ処理装置）
１１０，２１０    ＣＤＦＧ生成手段
１２０，２２０    スケジューリング手段
１３０，２３０    アロケーション手段
１４０，２４０    状態遷移生成手段
１５０，２６０    ＲＴＬ生成手段
２５０    パイプライン構成生成手段
【図１】
2008071089.tif 000003
【図２】
2008071089.tif 000004
【図３】
2008071089.tif 000005
【図４】
2008071089.tif 000006
【図５】
2008071089.tif 000007
【図６】
2008071089.tif 000008
【図７】
2008071089.tif 000009
【図８】
2008071089.tif 000010
【図９】
2008071089.tif 000011
【図１０】
2008071089.tif 000012
【図１１】
2008071089.tif 000013