(57)【要約】   【課題】  信号遅延の影響を小さくしつつ、効率的な配置配線の決定を支援する。  【解決手段】  グループ化処理部１４、１６は、記憶装置１２に記憶されたデータフローファイル１００中の処理エレメントおよび接続の情報に基づいて、一定の接続関係を持つ一連の処理エレメントをグループエレメントとして、一連の処理エレメントおよびその間の接続を示すグループ情報ファイル１０２のレコードを生成する。セグメント分割部１８は、グループ情報ファイル１０２のレコード中の情報に基づき、グループエレメントを構成する処理エレメントを、それぞれ、同一のセグメントに配置するように、グループエレメントおよび／または処理エレメントを配置すべきセグメントを決定して、グループエレメントおよび／処理エレメントと、配置すべきセグメントとが関連付けられたセグメント情報ファイル１０４のレコードを生成して、記憶装置１２に記憶する。【選択図】  図１
2007293441.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間の接続の情報を含むデータフローファイルに基づいて、当該データフロー上の処理エレメントを、複数のセグメントのそれぞれに、所定の属性の実際の処理エレメントが所定数だけ配置されているＬＳＩ上に割り当てる配置配線を支援するシステムであって、
前記データフローファイル中の処理エレメントおよび処理エレメント間の接続の情報に基づいて、一連の処理エレメントが、データフローにおいて上流から下流に向けて直列に接続されているような、一連の処理エレメントの群である第１のグループエレメントを見出し、
一連の処理エレメントがループを形成しているような、当該一連の処理エレメントの群である、第２のグループエレメントを見出し、および／または、
前記データフロー中、所定の第１の深さの単一のグループエレメント或いは処理エレメントである開始エレメントから、１以上の下流に向かうパスを経て、所定の第２の深さの単一のグループエレメント或いは処理エレメントである終了エレメントに達する、前記パス上に存在する一連の処理エレメントの群であって、前記１以上のパスの全てが前記終了エレメントに達するような一連の処理エレメントの群である第３のグループエレメントを見出して、
当該第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメント、および、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成して、前記記憶装置に記憶するグループ化手段と、
前記グループ情報ファイルのレコードを参照して、前記レコード中の情報に基づく第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメントを、それぞれ、同一のセグメントに配置するように、前記グループエレメントおよび／または処理エレメントを配置すべきセグメントを決定して、前記グループエレメントおよび／処理エレメントと、配置すべきセグメントとが関連付けられたセグメント情報ファイルのレコードを生成して、前記記憶装置に記憶するセグメント分割手段と、を備えたことを特徴とするシステム。
【請求項２】
前記グループ化手段が、前記第３のグループエレメントを見出すために、
前記グループエレメントおよび／または前記処理エレメントの、前記データフロー中の深さを考慮して、ある深さＤに位置するグループエレメント或いは処理エレメントから、その接続を上流側にたどった１以上の経路において、共通のグループエレメント或いは処理エレメントが存在するような深さＤに位置するグループエレメント或いは処理エレメントであって、その深さＤが、前記データフローにおいて最も下流側であるようなグループエレメント或いは処理エレメントを終了エレメントとして特定して、
前記共通のグループエレメント或いは処理エレメントを開始エレメントとして、当該開始エレメントから、前記終了エレメントに至る全ての経路に存在する一連の処理エレメントの群である、第３のグループエレメントを見出して、当該第３のグループエレメントを構成する処理エレメントと、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成するように構成されたことを特徴とする請求項１に記載のシステム。
【請求項３】
前記セグメント分割手段が、
前記データフロー中の最上流の処理エレメントから最下流の処理エレメントに至る逆流或いはループのないパスであって、全てのパスの集合によって、前記データフロー中の全てのグループエレメントおよび／または処理エレメントがカバーされるような１以上の特徴パスを特定し、当該特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶し、かつ、
前記特徴パス情報に基づいて、前記特徴パスごとに、前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを配置すべきセグメントを決定するように構成されたことを特徴とする請求項１または２に記載のシステム。
【請求項４】
前記セグメント分割手段が、
前記データフローファイルおよびグループ情報ファイルのレコードを参照して、データフロー中、最上流に位置する処理エレメントから直接或いは間接に接続された、グループエレメント或いは処理エレメントが、前記記憶装置に記憶された特徴パス情報により示される特徴ファイルの何れにも属していない場合に、当該最上流の処理エレメントから前記特徴ファイルの何れにも属していないグループエレメント或いは処理エレメントを含むパスを、特徴パスとして特定するように構成されたことを特徴とする請求項３に記載のシステム。
【請求項５】
前記セグメント分割手段が、
前記特徴パス情報およびセグメント情報ファイルのレコードを参照して、前記特徴パス上の両端を除くグループエレメントおよび／または処理エレメントの何れかについて、配置すべきセグメントが決定されている場合には、前記配置すべきセグメントが決定されているグループエレメントおよび／または処理エレメントが両端になるように、前記特徴パスを分割して、分割された特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するように構成されたことを特徴とする請求項４に記載のシステム。
【請求項６】
前記記憶装置に、特徴パス上の両端に位置するグループエレメントおよび／または処理エレメントの最上流側である開始エレメント、並びに、最下流側である終了エレメントのそれぞれについて、前記セグメントを特定するセグメント番号の組ごとに、前記特徴パスが経由する可能性のある経由セグメントを示すセグメント番号を格納した経由セグメントテーブルを有し、
前記セグメント分割手段が、
前記特徴パス情報を参照して、特徴パス上の両端のグループエレメントおよび／または処理エレメントを配置すべきセグメントのセグメント番号を特定し、前記経由セグメントテーブルから、経由セグメントのセグメント番号を取得して、
前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを、前記経由セグメントの何れかに配置した状態における評価関数の関数値を算出し、前記評価関数の関数値がもっとも良好な、グループエレメントおよび／処理エレメントの、前記経由エレメントの配置に基づいて、前記セグメント情報ファイルのレコードを生成するように構成されたことを特徴とする請求項５に記載のシステム。
【請求項７】
前記評価関数が、前記セグメントのぞれぞれにおける、グループエレメント或いは処理エレメントの配置によって、前記セグメントにおいて使用できなくなった処理エレメントを除く、当該セグメント中の処理エレメントの残り数の二乗の総和に基づくことを特徴とする請求項６に記載のシステム。
【請求項８】
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間の接続の情報を含むデータフローファイルに基づいて、当該データフロー上の処理エレメントを、複数のセグメントのそれぞれに、所定の属性の実際の処理エレメントが所定数だけ配置されているＬＳＩ上に割り当てる配置配線を支援するためのプログラムであって、コンピュータに、
前記データフローファイル中の処理エレメントおよび処理エレメント間の接続の情報に基づいて、一連の処理エレメントが、データフローにおいて上流から下流に向けて直列に接続されているような、一連の処理エレメントの群である第１のグループエレメントを見出し、
一連の処理エレメントがループを形成しているような、当該一連の処理エレメントの群である、第２のグループエレメントを見出し、および／または、
前記データフロー中、所定の第１の深さの単一のグループエレメント或いは処理エレメントである開始エレメントから、１以上の下流に向かうパスを経て、所定の第２の深さの単一のグループエレメント或いは処理エレメントである終了エレメントに達する、前記パス上に存在する一連の処理エレメントの群であって、前記１以上のパスの全てが前記終了エレメントに達するような一連の処理エレメントの群である第３のグループエレメントを見出して、
当該第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメント、および、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成して、前記記憶装置に記憶するグループ化ステップと、
前記グループ情報ファイルのレコードを参照して、前記レコード中の情報に基づく第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメントを、それぞれ、同一のセグメントに配置するように、前記グループエレメントおよび／または処理エレメントを配置すべきセグメントを決定して、前記グループエレメントおよび／処理エレメントと、配置すべきセグメントとが関連付けられたセグメント情報ファイルのレコードを生成して、前記記憶装置に記憶するセグメント分割ステップと、を実行させることを特徴とするプログラム。
【請求項９】
前記グループ化ステップにおいて、前記第３のグループエレメントを見出すために、前記コンピュータに、
前記グループエレメントおよび／または前記処理エレメントの、前記データフロー中の深さを考慮して、ある深さＤに位置するグループエレメント或いは処理エレメントから、その接続を上流側にたどった１以上の経路において、共通のグループエレメント或いは処理エレメントが存在するような深さＤに位置するグループエレメント或いは処理エレメントであって、その深さＤが、前記データフローにおいて最も下流側であるようなグループエレメント或いは処理エレメントを終了エレメントとして特定するステップと、
前記共通のグループエレメント或いは処理エレメントを開始エレメントとして、当該開始エレメントから、前記終了エレメントに至る全ての経路に存在する一連の処理エレメントの群である、第３のグループエレメントを見出して、当該第３のグループエレメントを構成する処理エレメントと、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成するステップとを実行させることを特徴とする請求項８に記載のプログラム。
【請求項１０】
前記セグメント分割ステップにおいて、前記コンピュータに、
前記データフロー中の最上流の処理エレメントから最下流の処理エレメントに至る逆流或いはループのないパスであって、全てのパスの集合によって、前記データフロー中の全てのグループエレメントおよび／または処理エレメントがカバーされるような１以上の特徴パスを特定し、当該特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するステップと、
前記特徴パス情報に基づいて、前記特徴パスごとに、前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを配置すべきセグメントを決定するステップと、を実行させることを特徴とする請求項８または９に記載のプログラム。
【請求項１１】
前記セグメント分割ステップにおいて、前記コンピュータに、
前記データフローファイルおよびグループ情報ファイルのレコードを参照して、データフロー中、最上流に位置する処理エレメントから直接或いは間接に接続された、グループエレメント或いは処理エレメントが、前記記憶装置に記憶された特徴パス情報により示される特徴ファイルの何れにも属していない場合に、当該最上流の処理エレメントから前記特徴ファイルの何れにも属していないグループエレメント或いは処理エレメントを含むパスを、特徴パスとして特定するステップを実行させることを特徴とする請求項１０に記載のプログラム。
【請求項１２】
前記セグメント分割ステップにおいて、前記コンピュータに、
前記特徴パス情報およびセグメント情報ファイルのレコードを参照して、前記特徴パス上の両端を除くグループエレメントおよび／または処理エレメントの何れかについて、配置すべきセグメントが決定されている場合には、前記配置すべきセグメントが決定されているグループエレメントおよび／または処理エレメントが両端になるように、前記特徴パスを分割して、分割された特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するステップを実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記記憶装置に、特徴パス上の両端に位置するグループエレメントおよび／または処理エレメントの最上流側である開始エレメント、並びに、最下流側である終了エレメントのそれぞれについて、前記セグメントを特定するセグメント番号の組ごとに、前記特徴パスが経由する可能性のある経由セグメントを示すセグメント番号を格納した経由セグメントテーブルを有し、
前記セグメント分割ステップにおいて、前記コンピュータに、
前記特徴パス情報を参照して、特徴パス上の両端のグループエレメントおよび／または処理エレメントを配置すべきセグメントのセグメント番号を特定し、前記経由セグメントテーブルから、経由セグメントのセグメント番号を取得するステップと、
前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを、前記経由セグメントの何れかに配置した状態における評価関数の関数値を算出し、前記評価関数の関数値がもっとも良好な、グループエレメントおよび／処理エレメントの、前記経由エレメントの配置に基づいて、前記セグメント情報ファイルのレコードを生成するステップと、を実行させることを特徴とする請求項１２に記載のプログラム。
【請求項１４】
前記評価関数が、前記セグメントのぞれぞれにおける、グループエレメント或いは処理エレメントの配置によって、前記セグメントにおいて使用できなくなった処理エレメントを除く、当該セグメント中の処理エレメントの残り数の二乗の総和に基づくことを特徴とする請求項１３に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＳＩにおける配置配線の決定を支援するシステムおよびプログラムに関し、より詳細には、ＬＳＩを構成する回路要素をグループ化して、グループごとにその配置の決定を支援するシステムおよびプログラムに関する。
する。
【背景技術】
【０００２】
近年、ＬＳＩを構成する回路の一部をソフトウェアにより再構成できるハードウェアが提供されている。このようなＬＳＩはリコンフィグラブル（再構成可能）ＬＳＩと称されている。リコンフィグラブルＬＳＩの設計者は、たとえば、Ｃ＋＋に類似するハードウェア記述言語を用いて、ＬＳＩを構成する、それぞれが属性や機能が定義された演算ユニットと、演算ユニット間の接続とを規定したデータフローダイヤグラムを作成し、作成したデータを、ハードディスクなどの記憶装置に記憶する。本明細書において、データフローダイヤグラムのデータを記憶したファイルを、データフローファイルと称する。データフローファイルにおいては、特定の属性や機能を有する演算ユニットおよび演算ユニット間の接続が規定されているのみであり、したがって、データフローファイルにおける演算ユニット（データフロー上の演算ユニット）と、実際のＬＳＩ上の演算ユニットとの間の対応付けや、データフローファイルにおける演算ユニット間の接続（データフロー上の接続）と、実際のＬＳＩ上のバスとの間の対応付けは完了していない。したがって、データフロー上の演算ユニットと実際のＬＳＩ上の演算ユニットとの対応付け、および、データフロー上の接続と、実際のＬＳＩ上のバスとの対応付けを行う配置配線の決定が必要である。
【０００３】
たとえば、特許文献１には、最適配置したい信号（演算ユニット値の接続）に優先順位を付け、対象回路のネットリストに基づき、優先信号順に配置配線を決定する方法が提案されている。特許文献１に開示された方法を適用することにより、クロック信号のディレイが最小となるパスが検索される。
【特許文献１】特開平８−８７５３７号公報
【特許文献２】国際公開ＷＯ０３／００７１５５号公報
【非特許文献１】榊原泰徳、佐藤友美著、「ＤＡＰＤＮＡのデバイスアーキテクチャ」、デザインウェーブマガジン（Design Wave Magazine）２００４年８月号、「特集  動的再構成可能デバイス  その素性と実力  第２章」、ＣＱ出版社、２００４年８月、第３０頁〜第３８頁
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、実際の回路のデータフローにおいては、多数の、一定の演算素子の単位（たとえば、特許文献１における論理ブロック）が接続されており、演算素子の単位を、単に順次割り当てていく手法を採用すると、信号遅延の問題は無視できなくなる場合がある。特に、データフローにおいて隣接する演算素子を、ＬＳＩ上でも近接して配置できないと、信号線が長くなることになり信号遅延の影響が深刻なものとなる。そこで、単に順次割り当てるだけではなく、また、単なる優先順位付けによるのではなく、より効率的な配置配線の決定が望まれている。
【０００５】
さらに、近年、ＬＳＩを構成する回路の一部をソフトウェアによりリアルタイムに再構成できるダイナミック・リコンフィグラブルＬＳＩが提供されている。たとえば、特許文献１には、再構成する基本単位を、ＡＬＵなどのある程度の規模の演算機能を備えた演算ユニットである処理エレメント（ＰＥ）として、それぞれが特定の属性や機能を有する複数種類のＰＥをマトリクス状に配置し、再構成に要する時間を短縮することができるようなダイナミック・リコンフィギュラブルＬＳＩが開示されている。また、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩにおいては、ＬＳＩが複数のセグメントに分割され、各セグメントに決められた属性および機能を有する所定数のＰＥが配置されている。したがって、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩについては、セグメントごとに、データフロー上のＰＥと、実際のセグメント上のＰＥとの対応付けおよびデータフロー上のＰＥ間の接続と、当該セグメント上のバスとの対応付けを行い、この対応付けを示す情報を、配置配線情報として、ハードディスクなどの記憶装置に記憶する。
【０００６】
各セグメント上のＰＥの数には限りがある（たとえば、６４個）。また、セグメント間でＰＥを接続するためには、遅延素子を介する必要がある。データフローを構成するＰＥを多数のセグメントにわたって配置すると、多数の遅延素子を使用することになり、ＬＳＩ上のリソースを無駄に使ってしまうことになる。また、多数の遅延素子が介在することによる信号遅延の問題も生じ得る。したがって、セグメント内にできるだけ効率よくＰＥを配置する必要もある。
【０００７】
本発明は、信号遅延の影響を小さくしつつ、効率的な配置配線の決定を支援するシステムおよびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の目的は、記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間の接続の情報を含むデータフローファイルに基づいて、当該データフロー上の処理エレメントを、複数のセグメントのそれぞれに、所定の属性の実際の処理エレメントが所定数だけ配置されているＬＳＩ上に割り当てる配置配線を支援するシステムであって、
前記データフローファイル中の処理エレメントおよび処理エレメント間の接続の情報に基づいて、一連の処理エレメントが、データフローにおいて上流から下流に向けて直列に接続されているような、一連の処理エレメントの群である第１のグループエレメントを見出し、
一連の処理エレメントがループを形成しているような、当該一連の処理エレメントの群である、第２のグループエレメントを見出し、および／または、
前記データフロー中、所定の第１の深さの単一のグループエレメント或いは処理エレメントである開始エレメントから、１以上の下流に向かうパスを経て、所定の第２の深さの単一のグループエレメント或いは処理エレメントである終了エレメントに達する、前記パス上に存在する一連の処理エレメントの群であって、前記１以上のパスの全てが前記終了エレメントに達するような一連の処理エレメントの群である第３のグループエレメントを見出して、
当該第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメント、および、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成して、前記記憶装置に記憶するグループ化手段と、
前記グループ情報ファイルのレコードを参照して、前記レコード中の情報に基づく第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメントを、それぞれ、同一のセグメントに配置するように、前記グループエレメントおよび／または処理エレメントを配置すべきセグメントを決定して、前記グループエレメントおよび／処理エレメントと、配置すべきセグメントとが関連付けられたセグメント情報ファイルのレコードを生成して、前記記憶装置に記憶するセグメント分割手段と、を備えたことを特徴とするシステムにより達成される。
【０００９】
好ましい実施態様においては、前記グループ化手段が、前記第３のグループエレメントを見出すために、
前記グループエレメントおよび／または前記処理エレメントの、前記データフロー中の深さを考慮して、ある深さＤに位置するグループエレメント或いは処理エレメントから、その接続を上流側にたどった１以上の経路において、共通のグループエレメント或いは処理エレメントが存在するような深さＤに位置するグループエレメント或いは処理エレメントであって、その深さＤが、前記データフローにおいて最も下流側であるようなグループエレメント或いは処理エレメントを終了エレメントとして特定して、
前記共通のグループエレメント或いは処理エレメントを開始エレメントとして、当該開始エレメントから、前記終了エレメントに至る全ての経路に存在する一連の処理エレメントの群である、第３のグループエレメントを見出して、当該第３のグループエレメントを構成する処理エレメントと、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成するように構成されている。
【００１０】
別の好ましい実施態様においては、前記セグメント分割手段が、
前記データフロー中の最上流の処理エレメントから最下流の処理エレメントに至る逆流或いはループのないパスであって、全てのパスの集合によって、前記データフロー中の全てのグループエレメントおよび／または処理エレメントがカバーされるような１以上の特徴パスを特定し、当該特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶し、かつ、
前記特徴パス情報に基づいて、前記特徴パスごとに、前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを配置すべきセグメントを決定するように構成されている。
【００１１】
より好ましい実施態様においては、前記セグメント分割手段が、
前記データフローファイルおよびグループ情報ファイルのレコードを参照して、データフロー中、最上流に位置する処理エレメントから直接或いは間接に接続された、グループエレメント或いは処理エレメントが、前記記憶装置に記憶された特徴パス情報により示される特徴ファイルの何れにも属していない場合に、当該最上流の処理エレメントから前記特徴ファイルの何れにも属していないグループエレメント或いは処理エレメントを含むパスを、特徴パスとして特定するように構成されている。
【００１２】
さらに好ましい実施態様においては、前記セグメント分割手段が、
前記特徴パス情報およびセグメント情報ファイルのレコードを参照して、前記特徴パス上の両端を除くグループエレメントおよび／または処理エレメントの何れかについて、配置すべきセグメントが決定されている場合には、前記配置すべきセグメントが決定されているグループエレメントおよび／または処理エレメントが両端になるように、前記特徴パスを分割して、分割された特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するように構成されている。
【００１３】
また、別の好ましい実施態様においては、前記記憶装置に、特徴パス上の両端に位置するグループエレメントおよび／または処理エレメントの最上流側である開始エレメント、並びに、最下流側である終了エレメントのそれぞれについて、前記セグメントを特定するセグメント番号の組ごとに、前記特徴パスが経由する可能性のある経由セグメントを示すセグメント番号を格納した経由セグメントテーブルを有し、
前記セグメント分割手段が、
前記特徴パス情報を参照して、特徴パス上の両端のグループエレメントおよび／または処理エレメントを配置すべきセグメントのセグメント番号を特定し、前記経由セグメントテーブルから、経由セグメントのセグメント番号を取得して、
前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを、前記経由セグメントの何れかに配置した状態における評価関数の関数値を算出し、前記評価関数の関数値がもっとも良好な、グループエレメントおよび／処理エレメントの、前記経由エレメントの配置に基づいて、前記セグメント情報ファイルのレコードを生成するように構成されている。
【００１４】
たとえば、評価関数は、前記セグメントのぞれぞれにおける、グループエレメント或いは処理エレメントの配置によって、前記セグメントにおいて使用できなくなった処理エレメントを除く、当該セグメント中の処理エレメントの残り数の二乗の総和に基づいている。
【００１５】
また、本発明の目的は、記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間の接続の情報を含むデータフローファイルに基づいて、当該データフロー上の処理エレメントを、複数のセグメントのそれぞれに、所定の属性の実際の処理エレメントが所定数だけ配置されているＬＳＩ上に割り当てる配置配線を支援するためのプログラムであって、コンピュータに、
前記データフローファイル中の処理エレメントおよび処理エレメント間の接続の情報に基づいて、一連の処理エレメントが、データフローにおいて上流から下流に向けて直列に接続されているような、一連の処理エレメントの群である第１のグループエレメントを見出し、
一連の処理エレメントがループを形成しているような、当該一連の処理エレメントの群である、第２のグループエレメントを見出し、および／または、
前記データフロー中、所定の第１の深さの単一のグループエレメント或いは処理エレメントである開始エレメントから、１以上の下流に向かうパスを経て、所定の第２の深さの単一のグループエレメント或いは処理エレメントである終了エレメントに達する、前記パス上に存在する一連の処理エレメントの群であって、前記１以上のパスの全てが前記終了エレメントに達するような一連の処理エレメントの群である第３のグループエレメントを見出して、
当該第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメント、および、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成して、前記記憶装置に記憶するグループ化ステップと、
前記グループ情報ファイルのレコードを参照して、前記レコード中の情報に基づく第１のグループエレメント、第２のグループエレメントおよび／または第３のグループエレメントを構成する処理エレメントを、それぞれ、同一のセグメントに配置するように、前記グループエレメントおよび／または処理エレメントを配置すべきセグメントを決定して、前記グループエレメントおよび／処理エレメントと、配置すべきセグメントとが関連付けられたセグメント情報ファイルのレコードを生成して、前記記憶装置に記憶するセグメント分割ステップと、を実行させることを特徴とするプログラムによっても達成される。
【００１６】
好ましい実施態様においては、前記グループ化ステップにおいて、前記第３のグループエレメントを見出すために、前記コンピュータに、
前記グループエレメントおよび／または前記処理エレメントの、前記データフロー中の深さを考慮して、ある深さＤに位置するグループエレメント或いは処理エレメントから、その接続を上流側にたどった１以上の経路において、共通のグループエレメント或いは処理エレメントが存在するような深さＤに位置するグループエレメント或いは処理エレメントであって、その深さＤが、前記データフローにおいて最も下流側であるようなグループエレメント或いは処理エレメントを終了エレメントとして特定するステップと、
前記共通のグループエレメント或いは処理エレメントを開始エレメントとして、当該開始エレメントから、前記終了エレメントに至る全ての経路に存在する一連の処理エレメントの群である、第３のグループエレメントを見出して、当該第３のグループエレメントを構成する処理エレメントと、当該処理エレメント間の接続を示すグループ情報ファイルのレコードを生成するステップとを実行させる。
【００１７】
別の好ましい実施態様においては、前記セグメント分割ステップにおいて、前記コンピュータに、
前記データフロー中の最上流の処理エレメントから最下流の処理エレメントに至る逆流或いはループのないパスであって、全てのパスの集合によって、前記データフロー中の全てのグループエレメントおよび／または処理エレメントがカバーされるような１以上の特徴パスを特定し、当該特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するステップと、
前記特徴パス情報に基づいて、前記特徴パスごとに、前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを配置すべきセグメントを決定するステップと、を実行させる。
【００１８】
より好ましい実施態様においては、前記セグメント分割ステップにおいて、前記コンピュータに、
前記データフローファイルおよびグループ情報ファイルのレコードを参照して、データフロー中、最上流に位置する処理エレメントから直接或いは間接に接続された、グループエレメント或いは処理エレメントが、前記記憶装置に記憶された特徴パス情報により示される特徴ファイルの何れにも属していない場合に、当該最上流の処理エレメントから前記特徴ファイルの何れにも属していないグループエレメント或いは処理エレメントを含むパスを、特徴パスとして特定するステップを実行させる。
【００１９】
さらに好ましい実施態様においては、前記セグメント分割ステップにおいて、前記コンピュータに、
前記特徴パス情報およびセグメント情報ファイルのレコードを参照して、前記特徴パス上の両端を除くグループエレメントおよび／または処理エレメントの何れかについて、配置すべきセグメントが決定されている場合には、前記配置すべきセグメントが決定されているグループエレメントおよび／または処理エレメントが両端になるように、前記特徴パスを分割して、分割された特徴パス上に存在するグループエレメントおよび／処理エレメント、並びに、その接続を示す特徴パス情報を記憶装置に記憶するステップを実行させる。
【００２０】
また、別の好ましい実施態様においては、前記記憶装置に、特徴パス上の両端に位置するグループエレメントおよび／または処理エレメントの最上流側である開始エレメント、並びに、最下流側である終了エレメントのそれぞれについて、前記セグメントを特定するセグメント番号の組ごとに、前記特徴パスが経由する可能性のある経由セグメントを示すセグメント番号を格納した経由セグメントテーブルを有し、
前記セグメント分割ステップにおいて、前記コンピュータに、
前記特徴パス情報を参照して、特徴パス上の両端のグループエレメントおよび／または処理エレメントを配置すべきセグメントのセグメント番号を特定し、前記経由セグメントテーブルから、経由セグメントのセグメント番号を取得するステップと、
前記特徴パス上に存在するグループエレメントおよび／または処理エレメントを、前記経由セグメントの何れかに配置した状態における評価関数の関数値を算出し、前記評価関数の関数値がもっとも良好な、グループエレメントおよび／処理エレメントの、前記経由エレメントの配置に基づいて、前記セグメント情報ファイルのレコードを生成するステップと、を実行させる。
【００２１】
好ましい実施態様において、前記評価関数は、前記セグメントのぞれぞれにおける、グループエレメント或いは処理エレメントの配置によって、前記セグメントにおいて使用できなくなった処理エレメントを除く、当該セグメント中の処理エレメントの残り数の二乗の総和に基づいている。
【発明の効果】
【００２２】
本発明によれば、信号遅延の影響を小さくしつつ、効率的な配置配線の決定を支援するシステムおよびプログラムを提供することが可能となる。
【発明を実施するための最良の形態】
【００２３】
以下、添付図面を参照して、本発明の実施の形態について説明する。図１は、本実施の形態にかかる配置配線決定システム１０の概略を示すブロックダイヤグラムである。本実施の形態においては、例示的に、特許文献１および非特許文献１に記載された動的再構成可能なＬＳＩにおいて、その配置配線を決定することを考える。しかしながら、本発明は、動的再構成可能なＬＳＩの配置配線に限定されず、任意の種別のＬＳＩの配置配線に適用することができる。
【００２４】
本実施の形態においては、配置配線システム１０の記憶装置１２には、動的再構成可能なＬＳＩ（以下、単に「ＬＳＩ」と称する。）において、配置配線をするための基礎となるデータフローファイル１００が格納されている。非特許文献１に記載され、また、図１２を参照して後述するように、本実施の形態において、配置配線が決定されるＬＳＩは、６つのセグメントに分割され、かつ、それぞれのセグメントには、決められた属性および機能を有する、決められた数の処理エレメント（ＰＥ）が配置されている。
【００２５】
データフローファイル１００には、ＬＳＩ中の基本単位である、ＡＬＵなどの所定の規模の演算機能を備えた演算ユニットである処理エレメント（ＰＥ）の種別や属性を含むＰＥ自体の情報、および、各ＰＥ間の接続情報が含まれる。データフローファイル１００におけるＰＥは、まだ実際のＬＳＩへの割り当てが行われない状態であり、これをＬＳＩ上の実際のＰＥと区別するために「データフロー上のＰＥ」或いは単に「ＰＥ」と称する。つまり、以下の記載で、単にＰＥと記載されている場合には、データフロー上のＰＥを意味する。その一方、ＬＳＩ上の実際のＰＥを、ＬＳＩ上のＰＥと称する。したがって、配置配線とは、データフロー上のＰＥを、ＬＳＩ上のＰＥに割り当て、データフロー上のＰＥと、ＬＳＩ上のＰＥの位置情報とを関連付けたデータを生成することに相当する。
【００２６】
配置配線決定システム１０は、データフローファイル１００を読み出して、データフローファイル中のＰＥ間の接続情報を参照して、第１のグループ化ロジックに基づいて、一定のＰＥを一つのグループとして、当該グループに含まれるＰＥの情報を含むグループ化情報ファイル１０２のレコードを生成して、記憶装置１２に記憶する第１のグループ化処理部１４と、データフローファイル１００およびグループ化情報ファイル１０２を参照して、第２のグループ化ロジックに基づいて、さらに一定のＰＥを一つのグループとして、グループ化情報ファイル１０２のレコードを更新する第２のグループ化処理部１６と、データフローファイル１００およびグループ情報ファイル１０２に基づいて、グループ化されたＰＥ群であるグループエレメント（ＧＥ）やＰＥと、後述するセグメントとを関連付け、セグメント情報ファイル１０４のレコードを生成するセグメント分割処理部１８と、データフローファイル１００、グループ情報ファイル１０２およびセグメント情報ファイル１０４を参照して、データフロー上のＰＥをＬＳＩ上のＰＥに割り当て、データフロー上のＰＥのＬＳＩ上の位置を示す配置情報／接続情報ファイル１０６のレコードを生成して記憶装置１２に記憶する割り当て処理部２０と、を有している。
【００２７】
図２は、データフローの一例を示す図である。この例には、演算用のＰＥである「ＥＸＥ」（符号２０１、２０３、２０４および２０６）と、遅延のためのＰＥである「Ｄｅｌａｙ」（符号２０２、２０５参照）とが含まれる。「ＥＸＥ」は、ＡＬＵを含み、２つのデータ入力（ｄｉｘ、ｄｉｙ）および２つのキャリー入力（ｃｉｘ、ｃｉｙ）と、１つのデータ出力（ｄｏｕｔ）および１つのキャリー出力（ｃｏｕｔ）とを有する。「Ｄｅｌａｙ」は、１入力１出力である。データフローファイル１００には、ＰＥのどの出力とどの入力とが接続されているか（たとえば、「ＥＸＥ  Ｕ１」（符号２０１）のデータ出力が、「Ｄｅｌａｙ  Ｕ３」（符号２０２）のデータ入力と接続されていること）を示す情報が格納される。
【００２８】
図３は、本実施の形態において処理対象となるデータフローの例を示す図である。以下、図３に示すデータフロー上のＰＥをグループ化し、また、セグメントと関連付けることを考える。図３においては、特にＰＥの属性および機能は特に示さない。また、便宜上、それぞれのＰＥに番号をつけ、「＃ｎ（ｎがＰＥの番号）」と示す。第１のグループ化処理部１４は、データフローファイルを参照して、ＰＥのデータフローにおいて、ダイレクト接続と称する接続をなす一群のＰＥ、および、ループ接続と称する接続をなす一群のＰＥを特定し、ＰＥ群の情報を含むグループ情報ファイル１０２のレコードを生成して記憶装置１２に記憶する。また、本明細書において、データフローにおける元ないし源の側（図３における上側）を上流ないし上流側と称し、データが出力されていく側（図３における下側）を下流ないし下流側と称する。
【００２９】
図４は、第１のグループ化処理部１４におけるダイレクト接続の探索処理を示すフローチャートである。ダイレクト接続のＰＥ群とは、それぞれのＰＥが１入力１出力で直列的に接続されたＰＥ群をいう。図４に示すように、第１のグループ化処理部１４は、データフローファイル１００を参照して、データフロー中のＰＥを選択し（ステップ４０１）、当該ＰＥが１入力１出力であるかを判断する（ステップ４０２）。ステップ４０２でイエス(Yes)と判断された場合には、第１のグループ化処理部１４は、データフローファイル１００を参照して、上流から下流に向けて、接続されるＰＥが１入力１出力である限り、ＰＥを順次たぐって、当該接続されるＰＥ群を特定する（ステップ４０３）。そのようなＰＥ群が特定された場合には、第１のグループ化処理部１４は、特定されたＰＥ群を示す情報を含む、グループ情報ファイル１０２のレコードを生成して、記憶装置１２に記憶する（ステップ４０４）。ステップ４０１〜４０４は、処理により何れかのＰＥ群に属すると既に判断されたＰＥを除き、全てのＰＥについて実行される（ステップ４０５参照）。
【００３０】
図５は、図３の例についてダイレクト接続の探索結果を示す図である。図５において、ダイレクト接続の探索により、「ＰＥ＃５」および「ＰＥ＃６」からなるＰＥ群５０１、「ＰＥ＃１３」および「ＰＥ＃１５」からなるＰＥ群５０２、並びに、「ＰＥ＃１７」ないし「ＰＥ＃１９」からなるＰＥ群５０３が、ダイレクト接続のＰＥ群として特定され、これらＰＥ群の情報を含むレコードが、それぞれ、グループ情報ファイル１０２中に生成される。
【００３１】
図６は、第１のグループ化処理部におけるループ接続の探索処理を示すフローチャートである。ループ接続のＰＥ群とは、ある２入力１出力のＰＥの出力をたどっていくと、１入力１出力のＰＥに順次接続され、最終的に、１入力２出力のＰＥからの出力の一方が、さらに、１入力１出力のＰＥに順次接続された後、出力が、前記２入力１出力のＰＥの一方の入力に接続され、或いは、１入力２出力のＰＥの出力の一方が、前記２入力１出力の一方の入力に接続されているようなＰＥ群をいう。つまり、入口のＰＥ（２入力１出力）および出口のＰＥ（１入力１出力）を除き、他のＰＥが１入力１出力で直列的に接続され、その接続がループを描くようなＰＥ群をいう。
【００３２】
図６に示すように、第１のグループ化処理部１４は、データフローファイル１００を参照して、データフロー中のＰＥを選択し（ステップ６０１）、当該ＰＥが２入力１出力であるかを判断する（ステップ６０２）。このステップ６０２で入口のＰＥとなり得るものを選んでいる。ステップ６０２でイエス(Yes)と判断された場合には、第１のグループ化処理部１４は、接続されるＰＥが１入力１出力である限り、ＰＥを順次たぐり、さらに、接続されたＰＥが１入力２出力である場合には、一方の出力に接続されるＰＥをたぐると、最終的に、ステップ６０１で選択されたＰＥに戻るようなＰＥ群を特定する（ステップ６０３）。そのようなＰＥ群が特定できた場合には、第１のグループ化処理部１４は、特定されたＰＥ群を示す情報を含む、グループ化情報ファイル１０２のレコードを生成して、記憶装置１２に記憶する（ステップ６０４）。ステップ６０１〜６０４は、ＰＥ群に属すると既に判断されたＰＥを除き、全てのＰＥについて実行される（ステップ６０５参照）。
【００３３】
図７は、図３の例において、ループ接続の探索結果を示す図である。図７において、ループ接続の探索により、「ＰＥ＃８」、「ＰＥ＃９」および「ＰＥ＃７」からなるＰＥ群７０１が、ループ接続のＰＥ群と判断され、これらＰＥ群の情報を含むレコードが、グループ情報ファイル１０２中に生成される。
【００３４】
図８は、図３に示すデータフローにおいて、第１のグループ化処理により、グループ化されたＰＥ群を、グループエレメント（ＧＥ）として表した図である。図８の例において、「ＧＥ＃１」（符号８０１）は、「ＰＥ＃５」および「ＰＥ＃６」からなり、「ＧＥ＃２」（符号８０２）は、「ＰＥ＃８」、「ＰＥ＃９」および「ＰＥ＃７」からなる。また、「ＧＥ＃３」（符号８０３）は、「ＰＥ＃１３」および「ＰＥ＃１５」からなり、「ＧＥ＃４」（符号８０４）は、「ＰＥ＃１７」ないし「ＰＥ＃１９」からなる。
【００３５】
次に、第２のグループ化処理について説明する。第２のグループ化処理では、データフロー中のＰＥの深さを考慮する。データフロー中のＰＥの深さは、データフローの最上流のＰＥからの段数を表す。本実施の形態では、最上流のＰＥの深さを「Ｄｅｐｔｈ０」として、それ以降、「Ｄｅｐｔｈ１」、「Ｄｅｐｔｈ２」、・・・と表している（図８参照）。また、ダイレクト接続のＧＥの深さは、当該ダイレクト接続を構成するＰＥ群のうち最上流のＰＥの深さと一致するものとする。その一方、ループ接続の深さは、当該ループ接続を構成するＰＥ群のうち、入り口のＰＥ（つまり、２入力１出力のＰＥ）の深さと一致するものとする。無論、ＧＥの深さはこれに限定されず、当該ＧＥを構成するＰＥ群の何れかのＰＥの深さに一致するようにすれば良い。
【００３６】
図９および図１０は、本実施の形態にかかる第２のグループ化処理を示すフローチャートである。第２のグループ化処理部１６は、処理に先立って、データフローファイル１００およびグループ情報ファイル１０２を読み込んでおく。図９に示すように、第２のグループ化処理部１６は、処理対象となるＰＥの深さのパラメータＤを初期化する（ステップ９０１）。あるデータフローファイルについて最初に第２のグループ化処理を施す場合には、Ｄの初期値は「０」である。しかしながら、Ｄの初期値は「０」以外の場合もある。たとえば、深さ「０」から深さ「ｎ」までのＰＥやＧＥがグループ化された場合に、次の第２のグループ化処理では、初期値が「ｎ＋１」となる場合もある。
【００３７】
以下の処理では、第１のグループ化が終了した状態で、データフローファイル１００およびグループ情報ファイル１０２に基づいて、ＰＥやＧＥが選択される。また、第２のグループ化処理において、ＰＥという場合には、ＧＥも含まれる。第２のグループ化処理部１６は、深さＤに位置するＰＥから、グループ化されたＰＥ群における最下流のＰＥの候補となるＰＥ（Ａ）を選択する（ステップ９０２）。
【００３８】
次いで、第２のグループ化処理部１６は、選択されたＰＥ（Ａ）に対して、最上流のＰＥからの経路（パス）を全て見出し、各経路に存在するＰＥを、それぞれ特定する（ステップ９０３）。その後、第２のグループ化処理部１６は、各経路に共通に含まれるＰＥのうち最上流のものＰＥ（Ｂ）を特定する（ステップ９０４）。このＰＥ（Ｂ）は、グループ化されたＰＥ群における最上流のＰＥの候補となる。ステップ９０５でイエス(Yes)と判断された場合には、第２のグループ化処理部１６は、予め定められた他の条件を満たしているか否かを判断する（ステップ９０６）。本実施の形態において、他の条件は、以下に述べる事項である。
（１）ＧＥを構成するＰＥが所定数（たとえば、１４）を超えていないこと。
（２）ユーザが入力装置を操作して予め少なくとも一部のＰＥにセグメント番号を割り当てている場合や、当初から少なくとも一部のＰＥにセグメント番号が割り当てられている場合がある。そこで、ＧＥを構成する２以上のＰＥにセグメント番号が割り当てられている場合、そのセグメント番号が同一であること。
（３）ＰＥに割り振られているＥＩＤが同一であること。ＥＩＤとは、ＬＳＩ上で複数のデータフローを割り当てる場合に、それぞれのデータフローに付与されるＩＤをいう。
（４）グループ化によってループが形成されていないこと。
（５）データフロー中の最上流のＰＥは含まれていないこと。
【００３９】
ステップ９０６でイエス(Yes)と判断された場合には、第２のグループ化処理部１６は、ＰＥ（Ａ）およびＰＥ（Ｂ）を示す情報を記憶装置に記憶する（図１０のステップ１００１）。同じ深さＤに、未処理のＰＥであって、少なくともＰＥ（Ｂ）に接続された他のＰＥが存在する場合には（ステップ１００２でイエス(Yes)）、同様にステップ９０２〜９０６、１００１を実行する。
【００４０】
ステップ１００２でノー(No)と判断された場合には、ＰＥ（Ａ）が最下流に達しているか否かが判断される（ステップ１００３）。ステップ１００３でノー(No)と判断された場合には、深さのパラメータＤを「１」だけ増やして（ステップ１００４）、ステップ９０２に戻る。グループ化により、次の深さにＰＥが存在しない場合は、次のＰＥが存在する深さまでＤの値を増やせばよい。
【００４１】
ステップ９０５でノー(No)と判断された場合、つまり、共通のＰＥ（Ｂ）が存在しない場合、或いは、ステップ９０６でノー(No)と判断された場合、つまり、他の条件が満たされなくなった場合、第２のグループ化処理部１６は、先に実行されたステップ１００１で、その情報が記憶されていたＰＥ（Ａ）を最下流のＰＥとし、また、ＰＥ（Ｂ）を最上流のＰＥとするようなＰＥ群をグループ化して、当該ＰＥ群を示す情報を含む、グループ情報ファイルのレコードを生成して、記憶装置１２に記憶する（ステップ１００５）。また、ステップ１００３でイエス(Yes)と判断された場合にも、同様である（ステップ１００５）。
【００４２】
図８の左側に位置するデータフローでは、図９および図１０に示す処理の結果、ＰＥ（Ａ）＝ＧＥ＃２、ＰＥ（Ｂ）＝ＰＥ＃１であることを示す情報が記憶装置に記憶される。したがって、ＰＥ＃１からＧＥ＃２に至るＰＥ群がグループ化される（図１１の符号１１００参照）。
【００４３】
その一方、図８の右側に位置するデータフローについては、ＰＥ（Ａ）＝ＰＥ＃１４からＰＥ（Ｂ）＝ＰＥ＃１０に至るＰＥ群、ＧＥ＃３を構成するＰＥ群、および、ＰＥ（Ａ）＝ＧＥ＃４からＰＥ（Ｂ）＝ＰＥ＃１６に至るＰＥ群が、それぞれグループ化される（図１０の符号１１０１〜１１０３参照）。したがって、第２のグループ化処理の結果、図８のデータフローは、図１１に示すようになり、グループ情報ファイル１０２には、ＧＥ＃１０（符号１１００）〜ＧＥ＃１３（符号１１０３）のそれぞれを構成するＰＥを示す情報を含むレコード群が格納される。
【００４４】
第２のグループ化処理が終了した後、セグメント分割処理部１８が、グループ化されたＰＥ群であるＧＥを、ＬＳＩ上のどのセグメントに配置すべきかを決定する。図１２は、本実施の形態にかかるＬＳＩにおける。ＬＳＩ上のＰＥおよびセグメントの構成を説明する図である。図１２に示すように、本実施の形態にかかるＬＳＩは、６つのセグメントに分割され、それぞれのセグメントには、６４個（セグメント１、セグメント３〜５）、或いは、６０個（セグメント０、セグメント２）のＰＥ（ＬＳＩ上のＰＥ）が設けられている。各セグメントには、あらかじめ決められた機能を果たすＬＳＩ上のＰＥが決められた位置に配置される。なお、本実施の形態のセグメントにおいて、横方向に、図２における左から第０列、第１列、・・・、と称し、縦方向に図２における上から第０行、第１行、・・・と称する。図１２において、「ＬＤＢ」、「ＲＡＭ」、「ＤＬＥ」などが、それぞれ、定められた属性および機能を有するＬＳＩ上のＰＥである。
【００４５】
たとえば、セグメント０の第０行には、第１行には、ＬＳＩの外部からのデータを受け入れる４つのロードバッファ（ＬＤＢ）が配置される。ロードバッファは、そのサイズから、それぞれ、横方向に２列分のサイズを持つ。セグメント０の第１行には、第０列から、「ＲＡＭ」、４つの「Ｃ１６Ｌ」、２つの「Ｃ１６Ｅ」および「ＤＬＨ」という８つのＰＥが配置されている。たとえば、「ＲＡＭ」は、１６ＫバイトのＬＳＩの内部メモリ、「Ｃ１６Ｌ」や「Ｃ１６Ｅ」は、アドレス生成用のＰＥ、「ＤＬＨ」は、図１２における水平方向に位置する他のセグメントに出力可能な遅延要素である。詳細な説明は省略するが、各セグメントには、それぞれがあらかじめ定められた機能を有するＰＥが決められた場所に配置されている。そのほか、「ＥＸ＊（＊：Ｃ，Ｓ，Ｒ，Ｍ）」は、それぞれ、算術演算、論理演算、比較などの機能を有する演算ユニットである。
【００４６】
本実施の形態においては、グループ分けにより得られた複数のＰＥ群であるＧＥ、および、グループ化できなかったＰＥを、それぞれ、どのセグメントに割り当てるかを決定する処理が実行される。これをセグメント分けと称する。
【００４７】
図１３は、セグメント分割処理部によるセグメント分けの処理の概略を示すフローチャートである。図１３に示すように、セグメント分割処理部１８は、記憶装置１２からデータフローファイル１００およびグループ情報ファイル１０２を読み出し（ステップ１３０１）、これらファイルのデータから、データフローを構成するＧＥおよびＰＥから１以上の特徴パスを生成して、特徴パスを構成するＧＥやＰＥ、および、その接続を示す情報を記憶装置１２に記憶しておく（ステップ１３０２）。
【００４８】
本実施の形態において、特徴パスとは、最上流から最下流にいたる逆流やループのないパスであって、これら全ての特徴パスの集合により、全てのＧＥおよび／またはＰＥがカバーされるようなものをいう。特徴パスを示す情報には、最上流および最下流のＰＥを除き、パス上に存在するＧＥ、ＰＥおよびそれらの間の接続が含まれる。図１１の例では、ＧＥ＃１０がその経路上に存在するパスＡ、ＧＥ＃１１およびＧＥ＃１３がその経路上に存在するパスＢ、並びに、ＧＥ＃１２およびＧＥ＃１３がその経路上に存在するパスＣが、それぞれ特徴パスとなる。
【００４９】
図１４は、本実施の形態にかかる特徴パスの抽出の処理の例を示すフローチャートである。図１４に示すように、特徴パスを特定するために、セグメント分割処理部１８は、たとえば、最上流のＰＥを特定し（ステップ１４０１）、そこからデータフローにおいて接続されたＧＥ或いはＰＥであって、既に何れかの特徴パスに属していないＧＥ或いはＰＥを見出す。接続されたＧＥ或いはＰＥが既に何れかの特徴パスに属している場合に、順次、下流側に向けて接続されたＧＥ或いはＰＥを調べて、最下流に至るまで、全てのＧＥおよび／またはＰＥが既に他の何れかの特徴パスに属していれば（ステップ１４０２でイエス(Yes)）、上記最上流のＰＥに関する処理は終了する。全ての最上流のＰＥについて処理が終了していなければ（ステップ１４０３でノー(No)）、ステップ１４０１に戻る。
【００５０】
その一方、何れかのＧＥ或いはＰＥから下流側に接続されたＧＥ或いはＰＥが、何れの特徴パスにも属していなければ（ステップ１４０２でノー(No)）、最上流から、何れの特徴パスに属していないＧＥ或いはＰＥを含む、ＧＥ或いはＰＥおよびその接続情報が、初期的な特徴パスの情報として記憶装置２１に記憶する（ステップ１４０４）。次いで、セグメント分割処理部１８は、上記何れの特徴パスにも属していないＧＥ或いはＰＥから、下流側に向けて接続をたどり、パス上に存在するＧＥおよび／またはＰＥの情報、並びに、その接続情報を、特徴パスの情報に追加していく（ステップ１４０５）。処理対象が最下流のＰＥにまで達すると（ステップ１４０６でイエス(Yes)）、ある１つの特徴パスの情報のレコードが完成する。
【００５１】
特徴パスの抽出の後、特徴パスごとに、当該特徴パスに属するＧＥおよび／またはＰＥが配置されるセグメントが決定される（ステップ１３０３、１３０４）。その後、セグメント分割処理部１８は、当該特徴パスについて、ＧＥおよび／またはＰＥのそれぞれが配置されるセグメントを示す情報を含むセグメント情報ファイルのレコードが生成され、記憶装置１２に記憶される（ステップ１３０５）。ステップ１３０３〜ステップ１３０５の処理は、記憶装置１２にその情報が記憶された全ての特徴パスについて実行される（ステップ１３０６参照）。
【００５２】
以下、ステップ１３０３におけるＧＥおよびＰＥのセグメントへの配置の処理例についてより詳細に説明する。
【００５３】
図１５は、ステップ１３０３におけるセグメントの配置の際に参照される、記憶装置１２に記憶された経由セグメントテーブルを示す図である。本実施の形態において、データフローにおける最上流のＰＥ或いは最下流のＰＥには、配置すべきセグメントが予め定められているとする。つまり、データフローファイルにおいて、最上流のＰＥおよび最下流のＰＥには、そのセグメントの番号が付加されている。本実施の形態において、基本的には、データフローにおける最上流は、外部からのデータを受け入れるロードバッファ（図１２におけるセグメント０のＬＤＢ）であり、また、最下流は、外部にデータを出力するためのストアバッファ（図１２におけるセグメント２のＳＴＢ）となる。したがって、基本的には、特徴パスにおいて、最上流のＧＥ或いはＰＥを配置すべき位置はセグメント０となり、最下流のＧＥ或いはＰＥを配置すべき位置はセグメント２となる。
【００５４】
さらに、後述するように、処理の過程において、特徴パスに含まれるあるＧＥ或いはＰＥを配置すべきセグメントが既に決定されている場合がある。たとえば、図１６（ａ）に示すようなデータフローを考える。このデータフローには、２つの特徴パスが含まれる（図１６（ｂ）参照）。図１６（ｂ）に示すように、特徴パスＡＡは、最上流のＰＥ＃２０から、ＧＥ＃２０、ＧＥ＃２１、ＧＥ＃２２、ＧＥ＃２３を経て、最下流のＰＥ＃２１に至る。その一方、特徴パスＢＢは、最上流のＰＥ＃２０から、ＧＥ＃３０、ＧＥ＃２１、ＧＥ＃３１、ＧＥ＃３２、ＧＥ＃２３を経て、最下流のＰＥ＃２１に至る。図１６（ａ）、（ｂ）に示すように、複数の特徴パスにおいて、共通するＧＥおよび／またはＰＥ（この例では、ＧＥ＃２１およびＧＥ＃２３）が存在し得る。
【００５５】
たとえば、特徴パスＡＡにおいて、最上流のＰＥ＃２０はセグメント０に配置し、かつ、最下流のＰＥ＃２１はセグメント２に配置すべきであることが予め定められている。また、ＧＥ或いはＰＥ（この例ではＧＥのみ）を配置すべきセグメントが決定され、ＧＥ＃２１は、セグメントａに、ＧＥ＃２３はセグメントｂに配置すべきことになったと考える。ｋの場合には、特徴パスＢＢにおいても、最上流のＰＥ＃２０、最下流のＰＥ＃２１の配置すべきセグメントの他、ＧＥ＃２１、ＧＥ＃２３の配置すべきセグメントも、それぞれ、セグメントａ、セグメントｂと決定される。そこで、特徴パスＢＢを、配置すべきセグメントが決定されたＧＥ或いはＰＥを両端とするような、複数の特徴パスに分割する。
【００５６】
図１６（ｃ）は、特徴パスＢＢを、３つの特徴パスＢＢ−１〜ＢＢ−３に分割した状態を示す図である。図１６（ｂ）および（ｃ）から理解できるように、特徴パスＢＢ−１〜ＢＢ−３既にセグメントの配置が決定されたＧＥ或いはＰＥが両端となるようなものであることが理解できるであろう。
【００５７】
上述したように、特徴パスにおいて、最上流のＧＥ或いはＰＥを配置すべき位置はセグメント０となり、最下流のＧＥ或いはＰＥを配置すべき位置はセグメント２となるが、処理の過程で、その両端が、セグメント０およびセグメント２以外の特徴パスも存在することになる。
【００５８】
そこで、経由セグメントテーブル（図１５）においては、存在しえる全てのセグメント番号の組み合わせごとに、特徴パスの先頭のＧＥ或いはＰＥが配置されるべき開始セグメント、および、特徴パスの末尾のＧＥ或いはＰＥが配置されるべき最終セグメントと、その間の経由セグメントが、優先順位と関連付けられて格納されている。たとえば、開始セグメントがセグメント０であり、最終セグメントがセグメント０であるような場合には、優先順位１〜３までのそれぞれの経由セグメントが格納される（符号１５０１参照）。また、開始セグメントがセグメント０であり、最終セグメントがセグメント１であるような場合にも、優先順位１〜３までのそれぞれの経由セグメントが格納される（符号１５０２参照）。
【００５９】
信号線の長さを短くすることができるため、また、本実施の形態において複数のセグメントを経由する際には、遅延素子（図１２におけるＤＬＸ、ＤＬＶ）を通過させるというルールが存在するため、経由セグメントの数が小さい方が、信号の遅延を少なくすることができる。そこで、経由セグメントテーブルにおいて、開始セグメントおよび最終セグメントが同じもののうち、経由セグメントの数が小さいものが、優先順位が高く（つまり、優先順位の値が小さく）、また、経由セグメントの数が同じであれば、信号線の長さが短くなる方が、優先順位が高くなるようになっている。
【００６０】
図１７および図１８は、図１３のステップ１３０４および１３０５の処理をより詳細に示すフローチャートである。図１７に示すように、まず、セグメント分割処理部１８は、特徴パスの情報のレコード、および、既に、ＧＥやＰＥのセグメント上の配置が終了しているセグメント情報ファイル１０４のレコードを参照して、処理対象となる特徴パスに属するＧＥやＰＥで、既にセグメント上の位置が決定されているものを特定する（ステップ１７０１）。
【００６１】
次いで、処理対象となる特徴パスに属するＧＥ或いはＰＥにおいて、既にセグメントが決定されているものがあれば、セグメント分割処理部１８は、当該ＧＥ或いはＰＥを端部（開始セグメントや最終セグメント）とするように、特徴パスを分割する（ステップ１７０２）。
【００６２】
次いで、セグメント分割処理部１８は、特徴パスの情報或いは上記分割された特徴パスの情報に基づいて、ある特徴パスについて（分割された場合には、分割された特徴パスについて）、開始セグメントおよび最終セグメントを特定する（ステップ１７０３）。開始セグメントは、特徴パスにおける最上流のＧＥ或いはＰＥについて決定されたセグメントであり、最終セグメントは、特徴パスにおける最下流のＧＥ或いはＰＥについて決定されたセグメントである。セグメント分割処理部１８は、経由セグメントテーブルにおいて、ステップ１７０３で特定された開始セグメントおよび最終セグメントと関連付けられているような一連のレコードを特定する（ステップ１７０４）。また、セグメント分割処理部１８は、経由セグメントテーブルのレコードを特定するためのパラメータ「優先順位」を「１」に初期化しておく（ステップ１７０５）。
【００６３】
セグメント分割処理部１８は、パラメータ「優先順位」と同じ値の優先順位であるレコードから経由セグメントを取得する（ステップ１７０６）。次いで、セグメント分割処理部１８は、特徴パスに属するＧＥ、ＰＥのそれぞれをあるセグメント上に配置した状態における評価関数値を算出する（ステップ１７０６）。
【００６４】
本実施の形態においては、たとえば、以下のような評価関数値が適用される。セグメント分割処理部１８は、セグメントにおいて、ＧＥ（を構成するＰＥ）および／またはＰＥを配置したときの、ＰＥの種別ごとの残り数を算出する。次いで、セグメント分割処理部１８は、それぞれの残り数の二乗の、全ての種別の総和を算出する。なお、先に実行された図１３のステップ１３０３〜１３０５の処理によって、ＰＥの残り数は、既にセグメントへの配置が決定されているＧＥおよび／またはＰＥも考慮して算出される。算出された評価関数値は、ＧＥおよび／またはＰＥへのセグメント上への配置を示す情報とともに、記憶装置１２に記憶される。
【００６５】
セグメント分割処理部１８は、ＧＥおよび／またはＰＥを、経由セグメント中の、全ての候補となるセグメントに配置したかどうかを判断し（ステップ１７０８）、まだ異なるセグメントへの配置が可能である場合には（ステップ１７０８でノー(No)）、ステップ１７０７に戻る。
【００６６】
図１１に示すパスＡでは、ＧＥ＃１０のみが存在する。また、開始セグメントがセグメント０、最終セグメントがセグメント２であれば、経由セグメントテーブルにおける一連のレコード群（図１５の符号１５０３参照）が特定される。初期的には、優先順位が「１」である、経由セグメントが、「セグメント０、セグメント１、セグメント２」の順である場合を考える。セグメント分割処理部１８は、ＧＥ＃１０をセグメント０に配置した状態、セグメント１に配置した状態、および、セグメント２に配置したそれぞれの状態について、評価関数値を算出することになる。
【００６７】
ステップ１７０９でイエス(Yes)と判断された場合には、セグメント分割処理部１８は、ステップ１７０７を繰り返すことで得られた評価関数値のうち最善のものを選択する。本実施の形態において適用した評価関数値では、最善のものとして、最も値の大きなものが選択される。次いで、評価関数値が一定の条件を満たすか否か（たとえば、本実施の形態では一定の値より大きいか否か）が判断される（ステップ１８０２）。ステップ１８０２でノー(No)と判断された場合には、セグメント分割処理部１８は、パラメータ「優先順位」を「＋１」して（ステップ１８０３）、次の優先順位の経由セグメントについて、ステップ１７０６〜１８０１の処理を繰り返す。
【００６８】
ステップ１８０２でイエス(Yes)と判断された場合には、セグメント分割処理部１８は、最善の評価関数値を示したＧＥおよび／またはＰＥのセグメントへの配置に基づいて、セグメント情報ファイルのレコードを生成して記憶装置１２に記憶する（ステップ１８０４）。さらに、ステップ１７０２において、特徴パスが複数に分割された場合に、未処理の分割された特徴パスが存在すれば（ステップ１８０５）、ステップ１７０３に戻る。
【００６９】
このようにして、それぞれの特徴パス（分割された特徴パスを含む）のそれぞれについて、当該特徴パスに属するＧＥやＰＥを配置するセグメントの情報を格納したレコードを含むセグメント情報ファイルが完成する。
【００７０】
なお、ＧＥ内のＰＥの数が大きく、ＧＥを構成する全てのＰＥを単一のセグメントに配置させることができない場合には、ＧＥが分割される。たとえば、第１のグループ化処理部１４或いは第２のグループ化処理部１６は、ＧＥを構成するＰＥを参照して、深さ（Ｄｅｐｔｈ）のもっとも大きなＰＥ（つまり最下流に位置するＰＥ）を、当該ＧＥから切り離し（当該ＧＥに属さないものとして）、新たなグループ分けの情報を含むレコードを、グループ情報ファイル１０２に格納すればよい。セグメント分割処理部１８は、ＰＥを切り離したＧＥと、切り離されたＰＥとを含む特徴パスについて、図１３のステップ１３０４、１３０５に示す処理を実行すれば良い。
【００７１】
セグメント情報ファイル１０４が完成すると、割り当て処理部２０が、セグメントごとに、データフローファイル１００中のＰＥ（つまりデータフロー上のＰＥ）を、ＬＳＩ上のＰＥに割り当て、データフロー上のＰＥのＬＳＩ上の位置を示す配置情報／接続情報ファイル１０６を生成する。
【００７２】
図１９は、割り当て処理部２０による割り当て処理（配置配線処理）の例を示すフローチャートである。本実施の形態においては、セグメント情報ファイル１０４に、特徴パスごとに、ＧＥやＰＥが属するセグメントを示す情報を格納したレコードが含まれる。そこで、割り当て処理部２０は、上記セグメント情報ファイル１０４を参照して、セグメントごとに、当該セグメントに含まれるＰＥおよびその接続を見出す。
【００７３】
処理においては、割り当て処理部２０は、処理に用いるパラメータ「セグメント番号」を初期化し（ステップ１９０１）、セグメント情報ファイル１０４を参照して、各レコードにおいて、処理対象となるセグメント番号が関連付けられたＧＥやＰＥの情報を取得する（ステップ１９０２）。
【００７４】
割り当て処理部２０は、グループ情報ファイル１０２を参照して、上記情報が取得されたＧＥを構成するＰＥを特定する（ステップ１９０３）。次いで、割り当て処理部２０は、データフローファイル１００を参照して、処理対象となるセグメントに属するＰＥ間の接続の情報を取得する（ステップ１９０４）。これにより、処理対象となるセグメントに割り当てすべき、ＰＥ（データフロー上のＰＥ）およびＰＥ間の接続の情報が用意される。
【００７５】
その後、割り当て処理部２０は、ＰＥ（データフロー上のＰＥ）およびＰＥ間の接続の情報にしたがって、データフロー上のＰＥを、ＬＳＩ上のＰＥに割り当てて（ステップ１９０５）、それらの対応を示す割り当ての情報を、配置情報／接続情報ファイル１０６のレコードとして記憶する（ステップ１９０６）。割り当て処理部２０は、ステップ１９０２〜ステップ１９０６の処理を、全てのセグメントについて実行する（ステップ１９０７、１９０８参照）。このようにして、各セグメントにおいて、割り当ての情報、つまり、データフロー上のＰＥとＬＳＩ上のＰＥとの対応の情報を得ることが可能となる。
【００７６】
本実施の形態によれば、データフロー上、一定の接続関係を有する一連の処理エレメントをグループエレメントとして、グループエレメントを構成する処理エレメントは、ＬＳＩ上で同一のセグメントに配置することとしている。一定の接続関係を有する一連の処理エレメントが同一のセグメントに配置されることにより、ＬＳＩ上で、多数のセグメントを通るようなパスを少なくすることができる。このため、パスについて、実際のＬＳＩ上の信号線の長さを短くすることができ、信号遅延の影響を小さくすることができる。また、複数のセグメントに渡る接続の際に介在させる遅延素子の数も少なくすることができ、ＬＳＩのリソースの無駄遣いを防止することも可能となる。
【００７７】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００７８】
【図１】図１は、本実施の形態にかかる配置配線決定システムの概略を示すブロックダイヤグラムである。
【図２】図２は、データフローの一例を示す図である。
【図３】図３は、本実施の形態において処理対象となるデータフローの例を示す図である。
【図４】図４は、第１のグループ化処理部におけるダイレクト接続の探索処理を示すフローチャートである。
【図５】図５は、図３の例についてダイレクト接続の探索結果を示す図である。
【図６】図６は、第１のグループ化処理部におけるループ接続の探索処理を示すフローチャートである。
【図７】図７は、図３の例において、ループ接続の探索結果を示す図である。
【図８】図８は、図３に示すデータフローにおいて、第１のグループ化処理により、グループ化されたＰＥ群を、グループエレメント（ＧＥ）として表した図である。
【図９】図９は、本実施の形態にかかる第２のグループ化処理を示すフローチャートである。
【図１０】図１０は、本実施の形態にかかる第２のグループ化処理を示すフローチャートである。
【図１１】図１１は、図３の例についてグループ化された状態を示す図である。
【図１２】図１２は、本実施の形態にかかるＬＳＩにおける。ＬＳＩ上のＰＥおよびセグメントの構成を説明する図である。
【図１３】図１３は、セグメント分割処理部によるセグメント分けの処理の概略を示すフローチャートである。
【図１４】図１４は、本実施の形態にかかる特徴パスの抽出の処理の例を示すフローチャートである。
【図１５】図１５は、ステップ１３０３におけるセグメントの配置の際に参照される、記憶装置に記憶された経由セグメントテーブルを示す図である。
【図１６】図１６（ａ）は、データフローの例、図１６（ｂ）は、データフローに基づく特徴パスの例、図１６（ｃ）は、分割された特徴パスの例を示す図である。
【図１７】図１７は、図１３のステップ１３０４および１３０５の処理をより詳細に示すフローチャートである。
【図１８】図１８は、図１３のステップ１３０４および１３０５の処理をより詳細に示すフローチャートである。
【図１９】図１９は、割り当て処理部による割り当て処理（配置配線処理）の例を示すフローチャートである。
【符号の説明】
【００７９】
１０      配置配線決定システム
１２      記憶装置
１４      第１のグループ化処理部
１６      第２のグループ化処理部
１８      セグメント分割処理部
２０      割り当て処理部
１００    データフローファイル
１０２    グループ情報ファイル
１０４    セグメント情報ファイル
１０６    配線情報／接続情報ファイル
【図１】
2007293441.tif 000003
【図２】
2007293441.tif 000004
【図３】
2007293441.tif 000005
【図４】
2007293441.tif 000006
【図５】
2007293441.tif 000007
【図６】
2007293441.tif 000008
【図７】
2007293441.tif 000009
【図８】
2007293441.tif 000010
【図９】
2007293441.tif 000011
【図１０】
2007293441.tif 000012
【図１１】
2007293441.tif 000013
【図１２】
2007293441.tif 000014
【図１３】
2007293441.tif 000015
【図１４】
2007293441.tif 000016
【図１５】
2007293441.tif 000017
【図１６】
2007293441.tif 000018
【図１７】
2007293441.tif 000019
【図１８】
2007293441.tif 000020
【図１９】
2007293441.tif 000021