(57)【特許請求の範囲】
【請求項１】
並列に動作するスレッド間の同期通信を含む動作記述を入力し、該動作記述に基づいて回路を合成する高位合成装置であって、
入力された動作記述を解析して、前記同期通信においてデータ送信命令またはデータ受信命令が連続する場合に、連続するデータ送信命令または連続するデータ受信命令を抽出する抽出部と、
該抽出部によって抽出された前記連続するデータ送信命令または前記連続するデータ受信命令を１つの演算としてまとめて取り扱い、前記各スレッド毎のスケジューリングを行うスケジューリング部と、
該スケジューリング部のスケジューリング結果に基づいて、１つにまとめられた前記データ送信命令または前記データ受信命令が、ハンドシェークによりクロック信号に同期して同時に開始できるように回路を生成する回路生成部と
を少なくとも有する高位合成装置。
【請求項２】
前記回路生成部は、
前記スケジューリング部のスケジューリング結果に基づいて、データパスを構成するために必要な回路素子を選択して割り当てる素子割り当て部と、
該素子割り当て部にて割り当てられた素子の各入出力ポートにハンドシェーク回路を付加するハンドシェーク回路付加部と、
前記スケジューリング部のスケジューリング結果に待ち状態を付加する待ち状態生成部と、
該待ち状態生成部によって待ち状態が付加されたスケジューリング結果に基づいて制御を行う制御回路を生成する制御回路生成部と
を少なくとも有する請求項１に記載の高位合成装置。
【請求項３】
請求項１に記載の高位合成装置を使用した高位合成方法であって、
前記抽出部により、入力された動作記述を解析して、前記同期通信においてデータ送信命令またはデータ受信命令が連続する場合に、連続するデータ送信命令または連続するデータ受信命令を抽出する抽出工程と、
前記スケジューリング部により、該抽出工程にて抽出された前記連続するデータ送信命令または前記連続するデータ受信命令を１つの演算としてまとめて取り扱い、スレッド毎のスケジューリングを行うスケジューリング工程と、
前記回路生成部により、該スケジューリング工程のスケジューリング結果に基づいて、１つにまとめられた前記データ送信命令または前記データ受信命令が、ハンドシェークによりクロック信号に同期して同時に開始できるように回路を生成する回路生成工程と、
を包含する高位合成方法。
【請求項４】
請求項３に記載の高位合成方法を行うためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＬＳＩの論理回路設計において、命令、関数や手続き等の動作記述によって動作が表された回路を合成するための高位合成装置および高位合成方法並びにそれに用いられる記録媒体に関する。
【０００２】
【従来の技術】
従来、並列に動作するスレッドの動作と、それらのスレッド間の同期データ通信を表現可能な動作記述から回路を合成する方法としては、本願出願人が特開平１０−１１６３０２号公報において提案しているようなものがある。
【０００３】
この従来の合成方法を、図１１に示す。まず、動作記述３９を読み込んで、スケジューリング装置４０により演算の実行順序を決定する。そして、回路素子割り当て装置４１により、演算器やレジスタ等のデータパス内の素子に演算等を割り当て、それらがスケジューリング装置４０によって決定された順序通りに実行されるように制御回路を生成して、回路４２を合成する。
【０００４】
この従来の合成方法では、２つのスレッド間のデータを同期して転送する、つまり、データを送る側およびデータを受け取る側は両側が転送できる状態になって初めて転送を行うことができるという通信手順（プロトコル）を定義した命令（ｓｅｎｄ、ｒｅｃｉｅｖｅ）を入力言語に用意することにより、単にデータを送る（ｓｅｎｄ）という命令とデータを受け取る（ｒｅｃｉｅｖｅ）という命令を記述する。そして、回路を合成する際には、このような同期データ通信のために各スレッドの回路に対してハンドシェークを行う回路を生成し、スレッド間での同期通信が確実に行われる回路を合成していた。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述した従来の合成方法により合成した回路では、連続した通信命令がある場合に１つ１つの通信が順番に実行されるため、通信速度が遅くなるという問題があった。
【０００６】
例えば、図３に示すような動作記述が入力された場合に、スレッド１５の中の２つのＳＥＮＤという同期通信命令を考えてみる。この場合、従来の合成方法により合成した回路では、ＳＥＮＤ（ＣＨ２，Ｄ２）はＳＥＮＤ（ＣＨ１，Ｄ１）が終了した後にしか通信できない。このため、クロックに同期したハンドシェーク通信を行うと、例えば図１２に示すように４クロックが必要となる。
【０００７】
本発明は、このような従来技術の課題を解決すべくなされたものであり、同期通信を含む動作記述に基づいて、従来よりも動作速度が速い回路を合成することができる高位合成装置および高位合成方法並びにそれに用いられる記録媒体を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明の高位合成装置は、並列に動作するスレッド間の同期通信を含む動作記述を入力し、該動作記述に基づいて回路を合成する高位合成装置であって、入力された動作記述を解析して、前記同期通信においてデータ送信命令またはデータ受信命令が連続する場合に、連続するデータ送信命令または連続するデータ受信命令を抽出する抽出部と、該抽出部によって抽出された前記連続するデータ送信命令または前記連続するデータ受信命令を１つの演算としてまとめて取り扱い、前記各スレッド毎のスケジューリングを行うスケジューリング部と、該スケジューリング部のスケジューリング結果に基づいて、１つにまとめられた前記データ送信命令または前記データ受信命令が、ハンドシェークによりクロック信号に同期して同時に開始できるように回路を生成する回路生成部とを少なくとも有し、そのことにより上記目的が達成される。
【０００９】
前記回路生成部は、前記スケジューリング部のスケジューリング結果に基づいて、データパスを構成するために必要な回路素子を選択して割り当てる素子割り当て部と、
該素子割り当て部にて割り当てられた素子の各入出力ポートにハンドシェーク回路を付加するハンドシェーク回路付加部と、前記スケジューリング部のスケジューリング結果に待ち状態を付加する待ち状態生成部と、該待ち状態生成部によって待ち状態が付加されたスケジューリング結果に基づいて制御を行う制御回路を生成する制御回路生成部とを少なくとも有する構成としてもよい。
【００１０】
本発明の高位合成方法は、請求項１に記載の高位合成装置を使用した高位合成方法であって、前記抽出部により、入力された動作記述を解析して、前記同期通信においてデータ送信命令またはデータ受信命令が連続する場合に、連続するデータ送信命令または連続するデータ受信命令を抽出する抽出工程と、前記スケジューリング部により、該抽出工程にて抽出された前記連続するデータ送信命令または前記連続するデータ受信命令を１つの演算としてまとめて取り扱い、スレッド毎のスケジューリングを行うスケジューリング工程と、前記回路生成部により、該スケジューリング工程のスケジューリング結果に基づいて、１つにまとめられた前記データ送信命令または前記データ受信命令が、ハンドシェークによりクロック信号に同期して同時に開始できるように回路を生成する回路生成工程とを包含し、そのことにより上記目的が達成される。
【００１１】
本発明の記録媒体は、コンピュータ読み取り可能であって、前記高位合成方法を行うためのプログラムが記録され、そのことにより上記目的が達成される。
【００１２】
以下、本発明の作用について説明する。
【００１３】
本発明にあっては、並列に動作するスレッド間の同期通信を含む動作記述を回析して、連続し、かつ、種類が同じである同期通信を抽出し、抽出された同期通信を１つの演算としてまとめて取り扱ってスレッド毎のスケジューリングを行う。そしてハンドシェーク回路により同期通信を行う際に、そのスケジューリング結果に基づいて、１つにまとめられた同期通信を同じ優先順位で開始可能な回路を生成するので、それらを逐次実行する場合に比べて、動作速度が速い回路が得られる。
【００１４】
例えば、上述した図３の動作記述において、連続する同じ種類の同期通信命令ＳＥＮＤ（ＣＨ１，Ｄ１）およびＳＥＮＤ（ＣＨ２，Ｄ２）は、データの依存関係が無いので、後述する実施形態において図９に示すように、同時に２つの通信を開始して２クロックで通信を完了することが可能である。ここで、「データ依存関係がある」とは、図３の動作記述に対応する図４のコントロールデータフローグラフ（ＣＤＦＧ）を用いて説明すると、ある節点Ａからある節点Ｂまで矢印に沿って辿ることにより到達できる場合のことを称する。図３の動作記述において、ＳＥＮＤ（ＣＨ１，Ｄ１）は図４の「ＣＨ１Ｗ」に対応し、ＳＥＮＤ（ＣＨ２，Ｄ２）は図４の「ＣＨ２Ｗ」に対応しており、この２つの節点は矢印を辿って到達できる関係ではないため、データの依存関係が無いと称している。
【００１５】
なお、同じ種類の同期通信命令の間に同期通信命令ではない処理が記述されている場合でも、それらの同期通信命令を「連続する同じ種類の同期通信命令」として１つにまとめることができる。但し、同じ種類の同期通信命令の間に異なる種類の同期通信命令がある場合、例えばＲＥＣＥＩＶＥ（ＲＥＣＶ）、ＳＥＮＤ、ＲＥＣＥＩＶＥ（ＲＥＣＶ）の順に同期通信命令が記述されているような場合には、２つのＲＥＣＥＩＶＥ（ＲＥＣＶ）を「連続する同じ種類の同期通信命令」として１つにまとめることはできない。
【００１６】
上記回路生成部は、スケジューリング結果に基づいてデータパスを構成するために必要な回路素子を選択して割り当て、各入出力ポートにハンドシェーク回路を付加することにより、同期通信演算をハンドシェーク回路にマッピングする。そして、スケジューリング結果に待ち状態を付加し、それに基づいて制御回路を生成することにより、スケジューリング通りに通信動作を制御する制御回路が生成される。
【００１７】
本発明の記録媒体から読み出された高位合成のためのプログラムがコンピュータにより実行されると、連続する同じ種類の同期通信命令を抽出し、スレッド毎にスケジューリングを行い、１つにまとめられた同期通信を同じ優先順位で開始可能な回路を生成する高位合成装置を実現可能である。
【００１８】
【発明の実施の形態】
以下に、本発明の実施の形態について、図面を参照しながら説明する。なお、ここでは、図３に示す動作記述を用いて説明を行うが、動作記述のための高位言語としては、命令、関数や手続き等を用いて、並列に動作するスレッドの動作とスレッド間の同期データ通信を表現することが可能なものであれば、いずれも用いることができる。例えば、Ｏｃｃａｍ、Ｃ、Ｃ＋＋等が挙げられる。
【００１９】
図３の動作記述においては、１２、１３、１４に示す文が逐次実行される。１３はＰＡＲ文と呼ばれる構文により複数の文が並列に実行されることを示しており、この図３では１５、１６、１７が並列に実行されるスレッドとなる。ＳＥＮＤは同期通信でデータを送るための文であり、ＲＥＣＶは同期通信でデータを受け取るための文である。従って、図３の１２はＩＮと称される通信路（以下チャネル：ＣＨと称する）を介してデータを読み込み、変数ＩＮＤに格納することを示しており、１４は変数ＯＵＴＤのデータをチャネルＯＵＴを介して送り出すことを示している。図３の１５、１６、１７についても同様である。
【００２０】
図１は本発明の一実施形態である高位合成装置の構成を示す図である。この高位合成装置は、連続する同じ種類の同期通信命令を抽出する抽出装置部２、スレッド毎のスケジューリングを行うスケジューリング装置部３および回路素子（回路要素）を割り当てて回路を生成する回路素子割り当て装置部（回路生成部）４を有しており、入力された動作記述に基づいて回路５を合成する。
【００２１】
抽出装置部２は、入力された動作記述１から連続する同じ種類の同期通信命令を抽出し、それを１つのノード（節点）にまとめたコントロールデータフローグラフ（ＣＤＦＧ）と称されるグラフに変換する。このＣＤＦＧは、入力された動作記述を実行する制御の流れ（コントロールフロー）とデータの流れ（データフロー）とを表す。このＣＤＦＧにおいて、データの入出力、演算や制御の分岐をノードで表し、ノード間のデータの流れ（依存関係）や制御の流れ（依存関係）を枝で表す。本実施形態の高位合成において、動作記述をＣＤＦＧに変換する理由は、ＣＤＦＧは動作記述に記述された動作を保証した上で、生成されるハードウェアの並列化の余地を残した動作表現であるからである。
【００２２】
上記抽出装置部２における手続きは一般的なものであり、例えばＤａｎｉｅｌＧａｊｓｋｉ他著「Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ」  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ出版等に記載されているのもを用いることができる。
【００２３】
なお、同期通信命令にはデータを送るｓｅｎｄとデータを受け取るｒｅｃｅｉｖｅとがあり、同じ種類の同期通信命令とは、ｓｅｎｄとｓｅｎｄ、またはｒｅｃｅｉｖｅとｒｅｃｅｉｖｅとのことを言う。
【００２４】
例えば、図３に示した動作記述では、１５の中の２つのＳＥＮＤ、および１７の中の２つのＲＥＣＥＩＶＥ（ＲＥＣＶ）が連続する同じ種類の同期通信命令である。この図３の動作記述は、ＣＤＦＧでは図４に示すように表現され、抽出装置部２により抽出された同期通信命令を１つのノードにまとめることにより、図５に示すＣＤＦＧが作成される。なお、図４の１８、１９、２０および図５の２１、２２、２３は各々図３の１５、１６、１７に対応する。
【００２５】
次に、スケジューリング装置部３では、ＣＤＦＧに対してスケジューリングを行う。すなわち、ＣＤＦＧで表される依存関係に基づき、ノードに対応するデータの入出力、演算や制御の分岐が実行される相対的な時間を決定する。
【００２６】
なお、このスケジューリング方法は一般的なものであり、上述した「Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ」等に記載されているのもを用いることができる。
【００２７】
図６に、図３のスレッド１５、１６、１７について、スケジューリング装置部３により行われたスケジューリング結果の一例を示す。なお、図６の２４、２５、２６は各々図３の１５、１６、１７に対応する。図６の２４を例にとって説明すると、コントロールステップ１において変数ＩＮＤと５の和を取り（＋と記載されたノードに対応）、変数Ｄ１に代入すると同時にＣＨ１に対して書き込む（ＣＨ１-２Ｗノード）。また、変数Ｄ１と変数ＩＮＤの差を取り（−ノード）、変数Ｄ２に代入すると同時にＣＨ２に対して書き込む（ＣＨ１-２Ｗノード）。そして、コントロールステップ２において、ＣＨ３から読み込み（ＣＨ３Ｒノード）、変数ＯＵＴＤに書き込みを行う。このような一連の動作を１サイクルで実行するように動作合成されている。この図において、ＣＨ１-２ＷノードはＣＨ１とＣＨ２への書き込みを１つのノードで表している。
【００２８】
なお、図１１に示した従来のスケジューリング装置４０でスケジューリングを行った場合には、図１３に示すようなＣＤＦＧが得られる。なお、図１３の１０４、１０５、１０６は各々図３の１５、１６、１７に対応する。図１３の１０４を例にとって説明すると、コントロールステップ１において変数ＩＮＤと５の和を取り（＋と記載されたノードに対応）、変数Ｄ１に代入すると同時にＣＨ１に対して書き込む（ＣＨ１Ｗノード）。また、変数Ｄ１と変数ＩＮＤの差を取り（−ノード）、変数Ｄ２に代入する。そして、コントロールステップ２においてＣＨ２に対して書き込む（ＣＨ２Ｗノード）。その後、コントロールステップ３において、ＣＨ３から読み込み（ＣＨ３Ｒノード）、変数ＯＵＴＤに書き込みを行う。このように、コントロールステップが図６の場合に比べて多くなる。
【００２９】
次に、回路素子割り当て装置部４の構成を図２に示す。この回路素子割り当て装置部４は、データパス素子割り当て装置部８、ハンドシェーク回路付加装置部９、待ち状態生成装置部１０、制御回路生成装置部１１から構成されている。
【００３０】
データパス素子割り当て装置部８は、スケジューリング装置部３によるスケジューリング結果に基づいて、演算に割り当てられる演算器や、データ選択のためのセレクタ、データ記憶のためのレジスタ等、データパスを構成するために必要な回路要素（素子）を選択して接続する。
【００３１】
上記データパス素子割り当て装置部８における手続きは一般的なものであり、上述した「Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ」等に記載されているのもを用いることができる。
【００３２】
図８の３０はこのようにして生成されたデータパスを示す。
【００３３】
次に、ハンドシェーク回路付加装置部９によって、データパス３０の各入出力ポートにハンドシェーク回路を付加する。
【００３４】
図８の３１、３２および３３は、スレッド間での同期通信が確実に行われるようにするために、各々、図３の出力ポートＣＨ１-Ｗ、ＣＨ２-Ｗ、ＣＨ３-Ｒに付加されたハンドシェーク回路である。
【００３５】
このハンドシェーク回路は、例えば、図１０に示すような回路構成とすることができる。そして、例えば図８では、ハンドシェーク回路３１、３２は、制御回路３４からの開始信号３５によって、図９に示すようなクロック信号ＣＫに同期したハンドシェーク通信を開始し、ハンドシェーク通信が終了すると終了信号３６、３７を出力する。
【００３６】
なお、図８のＣＨ１、ＣＨ２およびＣＨ３は動作記述中のＣＨ１、ＣＨ２およびＣＨ３の各データを送るための信号線である。また、ＣＨ１-ＲＥＱ、ＣＨ２-ＲＥＱおよびＣＨ３-ＲＥＱは、ＣＨ１、ＣＨ２およびＣＨ３の各データが有効である期間にＨｉｇｈとなる信号線であり、ＣＨ１、ＣＨ２およびＣＨ３の各データが入力される側から信号が出力される。また、ＣＨ１-ＡＣＫ、ＣＨ２-ＡＣＫおよびＣＨ３-ＡＣＫは、ＣＨ１、ＣＨ２およびＣＨ３を受け取ったときにＨｉｇｈとなる信号線であり、ＣＨ１、ＣＨ２およびＣＨ３の各データが入力される側から信号が出力される。
【００３７】
さらに、図８の５０は、回路全体を制御している制御回路がデータ演算を実行するデータパス中の回路素子（演算器、レジスタ、セレクタ等を制御するための制御線である。上記制御回路は、現在の制御回路の状態、回路素子の状態およびハンドシェーク回路の状態に基づいて、次の状態や制御線５０に出力する信号を決定する。図８の５１は、データパス中の回路素子の状態を制御回路３４に送るための信号線である。また、図８の５２は、回路全体を制御している制御回路がハンドシェーク回路中の回路素子を制御するための制御線である。また、図８の５３はハンドシェーク回路の状態を制御回路に送るための信号線である。
【００３８】
次に、待ち状態生成装置部１０は、スケジューリング装置部３による同期通信が割り当てられたコントロールステップの次に、待ち状態のための新たなコントロールステップを付加する。さらに詳しくは、待ち状態生成装置部１０は、挿入される待ち状態以降にスケジューリング装置で決定された各演算のコントロールステップに１を加えると共に、その状態が待ち状態であるという情報を記憶中に蓄える。例えば図７の２７では、ＣＨ１-２Ｗが割り当てられたコントロールステップ１の次に新たなコントロールステップ１’を生成する。
【００３９】
最後に、制御回路生成装置部１１によって、待ち状態を付加したスケジューリング結果を制御可能な制御回路３４を生成する。この制御回路３４では、図８に示すように、両方のハンドシェークによる通信が終了したことを示す完了信号３８が有効になるまで図７に示したコントロールステップ１’を繰り返すようにする。
【００４０】
上記制御回路生成装置部１１における手続きは一般的なものであり、上述した「Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ」等に記載されているのもを用いることができる。
【００４１】
このようにして合成された回路５は、図３の１５の中の２つのＳＥＮＤ命令をハンドシェークにより同じ優先順位で開始可能であり、図９に示すように２クロックで２つのＳＥＮＤ命令を実行することができる。同様に、図３の１７の中の２つのＲＥＣＶ命令についても、ハンドシェークにより同じ優先順位で同期通信を開始可能な回路を合成することができる。あるいは３以上の同期通信命令であっても、ハンドシェークにより同じ優先順位で開始して動作速度を速くすることが可能である。
【００４２】
【発明の効果】
以上詳述したように、本発明によれば、スレッド間の同期通信を含む動作記述から、ハンドシェークにより同じ優先順位で複数の同期通信を開始可能な回路を生成することができる。従って、ＬＳＩの論理回路設計において、従来のように複数の同期通信を逐次実行する場合に比べて、動作速度が速く、処理能力が高い回路を実現することができる。
【００４３】
さらに、本発明の記録媒体を用いることにより、汎用の計算機からこの記録媒体に記録された高位合成プログラムを読み込むことによって、高位合成装置を実現することができる。従って、本発明の高位合成方法をＬＳＩの論理回路設計およびその後に続くＬＳＩの製造工程に幅広く適用することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態である高位合成装置の構成を説明するための図である。
【図２】本発明の一実施形態である高位合成装置において、同期通信演算をハンドシェーク回路にマッピングして制御回路を生成するための装置部を説明するための図である。
【図３】実施形態において用いられる動作記述の例を示す図である。
【図４】図３の動作記述について、コントロールデータフローグラフの例を示す図である。
【図５】図３の動作記述から同期通信命令抽出装置部によって生成されるコントロールデータフローグラフの例を示す図である。
【図６】図３の動作記述からスケジューリング装置部によってスケジューリングされたコントロールデータフローグラフの例を示す図である。
【図７】図３の動作記述から待ち状態生成装置部によって待ち状態が付加されたコントロールデータフローグラフの例を示す図である。
【図８】実施形態において、図３の動作記述中の１５から合成される回路の構成を示す図である。
【図９】実施形態により得られる回路によって、図３の動作記述中の同期通信を同時処理した場合のタイミングチャートの例を示す図である。
【図１０】本発明の一実施形態である高位合成装置において、ハンドシェーク回路の構成の一例を示す図である。
【図１１】従来の高位合成装置の構成を説明するための図である。
【図１２】従来技術により得られる回路によって、図３の動作記述中の同期通信を逐次処理した場合のタイミングチャートの例を示す図である。
【図１３】従来技術により得られる回路によって、図３の動作記述から生成されるコントロールデータフローグラフの例を示す図である。
【符号の説明】
１  動作記述
２  同期通信命令抽出装置部
３  スレッド毎のスケジューリング装置部
４  回路素子割り当て装置部
５  回路
８  データパス素子割り当て装置部
９  ハンドシェーク回路付加装置部
１０  待ち状態生成装置部
１１  制御回路生成装置部
【図１】
0003716967.tif 000002
【図２】
0003716967.tif 000003
【図３】
0003716967.tif 000004
【図４】
0003716967.tif 000005
【図５】
0003716967.tif 000006
【図６】
0003716967.tif 000007
【図７】
0003716967.tif 000008
【図８】
0003716967.tif 000009
【図９】
0003716967.tif 000010
【図１０】
0003716967.tif 000011
【図１１】
0003716967.tif 000012
【図１２】
0003716967.tif 000013
【図１３】
0003716967.tif 000014