ＬＳＩの配置配線の決定方法および決定プログラム
【課題】 ＬＳＩの処理エレメントの入出力の制限を考慮して、適切に、データフロー上の処理エレメントを、ＬＳＩ上の処理エレメントに割り当てる。
【解決手段】 データフロー上の処理エレメントの属性、および、処理エレメント間を接続する信号線の情報を含むデータフローファイル１００を記憶装置１２から読み出して、データフローファイル１００中の信号線の情報を参照して、信号線ごとに、信号線に出力するデータフロー上の処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントとを特定して、信号線ごとに、特定された処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップ１０１を、記憶装置１２中に生成する。
【解決手段】 データフロー上の処理エレメントの属性、および、処理エレメント間を接続する信号線の情報を含むデータフローファイル１００を記憶装置１２から読み出して、データフローファイル１００中の信号線の情報を参照して、信号線ごとに、信号線に出力するデータフロー上の処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントとを特定して、信号線ごとに、特定された処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップ１０１を、記憶装置１２中に生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リコンフィグラブルＬＳＩにおける配置配線の決定方法および配置配線の決定プログラムに関する。
【背景技術】
【０００２】
近年、ＬＳＩを構成する回路の一部をソフトウェアにより再構成できるハードウェアが提供されている。このようなＬＳＩはリコンフィグラブル（再構成可能）ＬＳＩと称されている。リコンフィグラブルＬＳＩの設計者は、たとえば、Ｃ＋＋に類似するハードウェア記述言語を用いて、ＬＳＩを構成する、それぞれが属性や機能が定義された演算ユニットと、演算ユニット間の接続とを規定したデータフローダイヤグラムを作成し、作成したデータを、ハードディスクなどの記憶装置に記憶する。本明細書において、データフローダイヤグラムのデータを記憶したファイルを、データフローファイルと称する。データフローファイルにおいては、特定の属性や機能を有する演算ユニットおよび演算ユニット間の接続が規定されているのみであり、したがって、データフローファイルにおける演算ユニット（データフロー上の演算ユニット）と、実際のＬＳＩ上の演算ユニットとの間の対応付けや、データフローファイルにおける演算ユニット間の接続（データフロー上の接続）と、実際のＬＳＩ上のバスとの間の対応付けは完了していない。したがって、データフロー上の演算ユニットと実際のＬＳＩ上の演算ユニットとの対応付け、および、データフロー上の接続と、実際のＬＳＩ上のバスとの対応付けを行う配置配線の決定が必要である。
【０００３】
たとえば、特許文献１には、最適配置したい信号（演算ユニット値の接続）に優先順位を付け、対象回路のネットリストに基づき、優先信号順に配置配線を決定する方法が提案されている。
【特許文献１】特開平８−８７５３７号公報
【特許文献２】国際公開ＷＯ０３／００７１５５号公報
【非特許文献１】榊原泰徳、佐藤友美著、「ＤＡＰＤＮＡのデバイスアーキテクチャ」、デザインウェーブマガジン（Design Wave Magazine）２００４年８月号、「特集 動的再構成可能デバイス その素性と実力 第２章」、ＣＱ出版社、２００４年８月、第３０頁〜第３８頁
【発明の開示】
【発明が解決しようとする課題】
【０００４】
さらに、近年、ＬＳＩを構成する回路の一部をソフトウェアによりリアルタイムに再構成できるダイナミック・リコンフィグラブルＬＳＩが提供されている。たとえば、特許文献１には、再構成する基本単位を、ＡＬＵなどのある程度の規模の演算機能を備えた演算ユニットである処理エレメント（ＰＥ）として、それぞれが特定の属性や機能を有する複数種類のＰＥをマトリクス状に配置し、再構成に要する時間を短縮することができるようなダイナミック・リコンフィギュラブルＬＳＩが開示されている。また、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩにおいては、ＬＳＩが複数のセグメントに分割され、各セグメントに決められた属性および機能を有する所定数のＰＥが配置されている。したがって、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩについては、セグメントごとに、データフロー上のＰＥと、実際のセグメント上のＰＥとの対応付けおよびデータフロー上のＰＥ間の接続と、当該セグメント上のバスとの対応付けを行い、この対応付けを示す情報を、配置配線情報として、ハードディスクなどの記憶装置に記憶する。
【０００５】
各セグメント上のＰＥの数には限りがあり（たとえば、６４個）かつ、セグメント上のバスの数にも限りがある（たとえば、Ｘ入出力のために６４本）。さらに、各ＰＥに入力として接続可能なバスおよびＰＥから出力として接続可能なバスも限られている。したがって、限られたＬＳＩ上のＰＥやバスのリソースに、データフロー上のＰＥや接続を適切に割り当てる配置配線の決定が求められる。
【０００６】
本発明は、リコンフィグラブルＬＳＩの処理エレメントの入出力の制限を考慮して、適切に、データフロー上の処理エレメントを、ＬＳＩ上の処理エレメントに割り当て、かつ、データフロー上の処理エレメント間の接続を、ＬＳＩ上のバスに割り当てることができる配置配線の決定方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の目的は、２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援する方法であって、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を備えたことを特徴とする方法により達成される。
【０００８】
好ましい実施態様においては、前記バスリソースリクエストマップを生成するステップが、前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を含む。
【０００９】
より好ましい実施態様においては、前記バスリソースリクエストマップを作成するステップが、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを含む。
【００１０】
好ましい実施態様において、前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造である。
【００１１】
別の好ましい実施態様においては、さらに、前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを備えている。
【００１２】
また、本発明の目的は、上述したようなバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定する方法であって、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を備えたことを特徴とする方法によっても達成される。
【００１３】
好ましい実施態様においては、前記バスリソースを更新するステップが、前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含む。
【００１４】
また、好ましい実施態様においては、前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップを備え、前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力する。
【００１５】
別の好ましい実施態様においては、前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含む。
【００１６】
また、本発明の目的は、２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援するために、コンピュータにより読み出し可能なプログラムであって、
前記コンピュータに、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を実行させることを特徴とするプログラムにより達成される。
【００１７】
好ましい実施態様においては、前記バスリソースリクエストマップを生成するステップにおいて、前記コンピュータに、
前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を実行させる。
【００１８】
より好ましい実施態様においては、前記バスリソースリクエストマップを作成するステップにおいて、前記コンピュータに、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを実行させる。
【００１９】
好ましい実施態様において、前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造である。
【００２０】
別の好ましい実施態様においては、さらに、前記コンピュータに、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを実行させる。
【００２１】
また、本発明の目的は、上述したバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定するために、コンピュータにより読み出し可能なプログラムであって、前記コンピュータに、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を実行させることを特徴とするプログラムによっても達成される。
【００２２】
好ましい実施態様においては、前記バスリソースを更新するステップにおいて、前記コンピュータに、
前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させる。
【００２３】
また、好ましい実施態様においては、前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップと、
前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力するステップと、を実行させる。
【００２４】
別の好ましい実施態様においては、前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させる。
【発明の効果】
【００２５】
本発明によれば、リコンフィグラブルＬＳＩの処理エレメントの入出力の制限を考慮して、適切に、データフロー上の処理エレメントを、ＬＳＩ上の処理エレメントに割り当て、かつ、データフロー上の処理エレメント間の接続を、ＬＳＩ上のバスに割り当てることができる配置配線の決定方法およびプログラムを提供することが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、添付図面を参照して、本発明の実施の形態について説明する。図１は、本実施の形態にかかる配置配線決定システム１０の概略を示すブロックダイヤグラムである。本実施の形態においては、記憶装置１２には、後述するように、特許文献１および非特許文献２に記載された、動的再構成可能なＬＳＩ（以下、単に「ＬＳＩ」と称する）において、配置配線をするための基礎となるデータフローファイル１００が設けられている。非特許文献１に記載されるように、本実施の形態において、配置配線が決定されるＬＳＩは、６つのセグメントに分割され、かつ、それぞれのセグメントには、決められた属性および機能を有する、決められた数の処理エレメント（ＰＥ）が配置されている。
【００２７】
また、配置配線決定システム１０は、データフローファイル１００中の、セグメントごとのコンフィギュレーションデータを参照して、記憶装置１２中にバスリソースリクエストマップ１０１を作成するマップ作成部１４と、所定のルールに基づいてバスリソースリクエストマップ１０１を更新するマップ更新部１６とを備えている。さらに、本実施の形態にかかる配置配線決定システム１０は、コンフィギュレーションデータに含まれるデータフロー上の処理エレメント（ＰＥ）を、パーティション内に配置されたＬＳＩ上の処理エレメントのうち、所定の位置にあるものに割り当てると仮定して、さらに他の所定のルールに基づいて、コンフィギュレーションデータに含まれるデータフロー上のＰＥの、セグメント中の具体的な位置を決定し、かつ、データフロー上のＰＥ間の信号線を、ＬＳＩ上の実際のバスに割り当て、データフロー上のＰＥのＬＳＩ上の位置およびデータフロー上の信号線に割り当てられたバスの位置を含む配置情報／接続情報ファイル１０２を記憶装置１２中に生成し、かつ、バスリソースリクエストマップ１０１を更新する配置処理部１８を備えている。なお、本実施の形態において、処理エレメントとはＬＳＩの演算単位である。
【００２８】
バスリソースリクエストマップ１０１、および、配置処理部１８による処理により得られる、コンフィギュレーションデータにおける演算回路の、セグメント中の具体的なＰＥの位置の情報（配置情報）およびＰＥ間の接続情報を含む配置情報／接続情報ファイル１０２は、記憶装置１２に記憶される。さらに、記憶装置１２には、マップ作成部１４によりバスリソースリクエストマップが作成される際に参照されるソースＰＥ・デスティネーションＰＥファイル１０３が記憶される。このソースＰＥ・デスティネーションＰＥファイル１０３については後述する。
【００２９】
本実施の形態にかかるＬＳＩは、複数のセグメントに分割されている。図２は、本実施の形態にかかるＬＳＩの６つのセグメントの例を示す図である。図２に示すように、それぞれのセグメントには、６４個（セグメント１、セグメント３〜５）、或いは、６０個（セグメント０、セグメント２）のＰＥが設けられている。各セグメントには、あらかじめ決められた機能を果たすＰＥが決められた位置に配置される。なお、本実施の形態のセグメントにおいて、横方向に、図２における左から第０列、第１列、・・・、と称し、縦方向に図２における上から第０行、第１行、・・・と称する。図２において、「ＬＤＢ」、「ＲＡＭ」、「ＤＬＥ」などが、それぞれ、定められた属性および機能を有するＰＥである。
【００３０】
たとえば、セグメント０の第０行には、第１行には、ＬＳＩの外部からのデータを受け入れる４つのロードバッファ（ＬＤＢ）が配置される。ロードバッファは、そのサイズから、それぞれ、横方向に２列分のサイズを持つ。セグメント０の第１行には、第０列から、「ＲＡＭ」、４つの「Ｃ１６Ｌ」、２つの「Ｃ１６Ｅ」および「ＤＬＨ」という８つのＰＥが配置されている。たとえば、「ＲＡＭ」は、１６ＫバイトのＬＳＩの内部メモリ、「Ｃ１６Ｌ」や「Ｃ１６Ｅ」は、アドレス生成用のＰＥ、「ＤＬＨ」は、図２における水平方向に位置する他のセグメントに出力可能な遅延要素である。詳細な説明は省略するが、各セグメントには、それぞれがあらかじめ定められた機能を有するＰＥが決められた場所に配置されている。そのほか、「ＥＸ＊（＊：Ｃ，Ｓ，Ｒ，Ｍ）」は、それぞれ、算術演算、論理演算、比較などの機能を有する演算ユニットである。
【００３１】
ＰＥの間を接続するためには、４種類のデータバスが存在する。本実施の形態においては、ＰＥは、図３に示すように、Ｘ入力およびＹ入力の２つのデータ入力（ｄｉｘおよびｄｉｙ）、ＣＸ入力およびＣＹ入力の２つのキャリー入力（ｃｉｘおよびｃｉｙ）、Ｘ出力およびＹ出力の２つのデータ出力（ｄｏｘおよびｄｏｙ）、並びに、ＣＸ出力およびＣＹ出力の２つのキャリー出力（ｃｏｘおよびｃｏｙ）が可能である。あるＰＥのＸ出力、Ｙ出力は、それぞれ、１以上の他のＰＥのＸ入力、Ｙ入力に接続され得る。同様に、ＰＥのＣＸ出力、ＣＹ出力は、それぞれ、１以上の他のＰＥのＣＸ入力、ＣＹ入力に接続され得る。Ｘ出力とＸ入力とを接続するバスを、Ｘデータバス、Ｙ出力とＹ入力とを接続するバスをＹデータバス、ＣＸ出力とＣＸ入力とを接続するバスをＸキャリーバス、ＣＹ出力とＣＹ出力とを接続するバスを、Ｙキャリーバスと称する。
【００３２】
図４は、ＸデータバスおよびＹデータバスを模式的に示す図、図５は、ＸキャリーバスおよびＹキャリーバスを模式的に示す図である。図４に示すように、本実施の形態においては、第０列、第１列、・・・のＰＥ群の両側に、その列のＸデータバスおよびＹデータバスが設けられている。たとえば、左端の第０列のＰＥ群（符号４０１、４０２、・・・参照）の（図４における）左側には、８つのラインからなる第０列のＸデータバス（符号４１１参照）が配置され、ＰＥ群の（図４における）右側には、８つのラインからなる第０列のＹデータバスが配置されている（符号４１２参照）。他の列（第ｎ列）のＰＥ群についても、その両側に、それぞれ８ラインからなる第ｎ列のＸデータバスおよびＹデータバスが配置される。図５に示すように、キャリーバスも同様に、第ｎ列のＰＥ群（たとえば符号５０１、５０２、・・・参照）について、（図５における）左側には８つのラインからなる第ｎ列のＸキャリーバスが配置され（たとえば符号５１１参照）、（図５における）右側には８つのラインからなる第ｎ列のＹキャリーバスが配置される（たとえば符号５１２参照）。
【００３３】
図６は、ＬＳＩ上の実際のＰＥにおけるバスの入出力の制限を説明する図である。本実施の形態においては、ＰＥ６０３は、データバスとの接続のために、ＰＥコンフィギュレーション部６００およびマルチプレクサコンフィギュレーション部６１０を有する。
【００３４】
図６に示すように、Ｘデータバスの各ラインは、セレクタ６０１を介して、ＰＥ６０３のＸ入力（ｄｉｘ）に接続される。また、Ｙデータバスの各ラインは、セレクタ６０２を介して、ＰＥ６０３のＹ入力（ｄｉｙ）に接続される。ＰＥ６０３のＸ入力（ｄｉｘ）は、同じ列のＸデータバスの何れかのラインに限られ、また、ＰＥ６０３のＹ入力（ｙｉｘ）も、同じ列のＹデータバスの何れかのラインに限られる。その一方、図６には明瞭に示されていないが、本実施の形態においては、ＰＥ６０３のＸ出力（ｄｉｘ）およびＹ出力（ｄｉｙ）は、それぞれ、マルチプレクサ６１１、６１２を介して、Ｘデータバス、Ｙデータバスの、ＰＥが位置する行、或いは、予め定められた隣接する行に位置する他のＰＥに接続可能なラインに接続され得る。つまり、第ｎ列のＰＥは、各列のデータバスの第ｎラインと、第（ｎ−１）ライン或いは第（ｎ＋１）ラインに接続可能である。ここで、バスの番号を示すライン番号は、行番号と等価である。
【００３５】
図６における符号６１３、６１４は、それぞれ、他のＰＥからのＸ出力およびＹ出力を示している。
【００３６】
本実施の形態においては、ＰＥの出力については以下のように定められている。
【００３７】
第０行のＰＥ：第０ライン、第１ライン
第１行のＰＥ：第０ライン、第１ライン
第２行のＰＥ：第２ライン、第３ライン
第３行のＰＥ：第２ライン、第３ライン
第４行のＰＥ：第４ライン、第５ライン
第５行のＰＥ：第４ライン、第５ライン
第６行のＰＥ：第６ライン、第７ライン
第７行のＰＥ：第６ライン、第７ライン
図示はしないが、キャリーバスについても、同様にＰＥの入出力の制限がある。
【００３８】
ＰＥの入出力という観点からは、上述したような接続の制限がある。その一方、データバスの各ラインについても、ＰＥの入出力の制限から、当該ラインに出力することができるＰＥ或いは当該ラインから入力することができるＰＥを決めることができる。
【００３９】
以下、セグメント１を例にして、第ｎ列第ｍラインのバスに接続可能なＰＥを説明する。第ｎ列第ｍラインのバスには、当該バスにデータを出力するＰＥ（これを、「ソースＰＥ」と称する。）と、当該バスからのデータを入力するＰＥ（これを、「デスティネーションＰＥ」と称する。）とが存在し得る。前述したように、第ｍ行のＰＥは、ｍが偶数であれば、第ｍラインおよび第（ｍ＋１）ラインに出力することができ、ｍが奇数であれば、第（ｍ−１）ラインおよび第ｍラインに出力することができる。
【００４０】
したがって、第ｍラインにおけるソースＰＥは、
第ｍラインおよび第（ｍ＋１）ラインに位置するＰＥ（ｍ：偶数）
第（ｍ−１）ラインおよび第ｍラインに位置するＰＥ（ｍ：奇数）
となる。
【００４１】
その一方、第ｎ列のＰＥは、第ｎ列のバスにのみ接続することができる。そこで、第ｎ列のそれぞれのラインにおけるデスティネーションＰＥは、第ｎ列のＰＥとなる。
【００４２】
たとえば、第６列第２ラインのバスを考える。図７（ａ）において、デスティネーションＰＥとなり得るＰＥ群を符号７０１で示し、ソースＰＥとなり得るＰＥ群を符号７０２で示す。つまり、基本的には、第６列第２ラインのバスについて、ソースＰＥとなり得るＰＥは、第２列および第３列のＰＥであり、また、デスティネーションＰＥとなり得るＰＥは、第６列のＰＥである。なお、ソースＰＥ中、第７列第３行のＤＬＨ（水平方向への外部出力のための遅延素子）が除外されているのは、本実施の形態において、ＰＥが、ＤＬＨおよびＤＬＸからのデータを入力する場合には、同じ行のＤＬＨ或いはＤＬＸからに限られるという制約があるからである。
【００４３】
また、第０列第０ラインのバスを考える。図７（ｂ）において、デスティネーションＰＥとなり得るＰＥ群を符号７１１で示し、ソースＰＥとなり得るＰＥ群を符号７１２で示す。基本的には、第０列第０ラインのバスについて、ソースＰＥとなり得るＰＥは、第０行および第１行のＰＥであり、また、デスティネーションＰＥとなり得るＰＥは、第０列のＰＥである。ただし、第０列第０行のＤＬＶは、垂直方向に外部からのデータ入力のための遅延要素であるため、そもそもデスティネーションＰＥとなることができないので除外される。
【００４４】
本実施の形態においては、あらかじめ、各セグメントについて、第ｎ列第ｍライン（ｎ：０〜７、ｍ：０〜７）のそれぞれにおけるソースＰＥとデスティネーションＰＥのリストであるソースＰＥ・デスティネーションＰＥファイルを記憶装置１２に記憶しておく。ソースＰＥ・デスティネーションＰＥファイル１０３においては、図８に示すように、第ｎ列第ｍラインにおいて候補となり得るＰＥの名称が格納されている。
【００４５】
以下、本実施の形態にかかる配置配線決定システム１０において実行される処理について説明する。図９は、本実施の形態にかかる配置配線決定システムにおける配置配線処理の概略を示すフローチャートである。図９に示すように、配置配線決定システム１０のマップ作成部１４は、あるセグメントに割り当てるべきパーティションのコンフィギュレーションデータを、記憶装置１２から読み出す。コンフィギュレーションデータは、パーティションを構成する、データフロー上のＰＥの各々の属性および機能、並びに、それぞれのＰＥ間の接続を示す特定する情報を含む。図１０は、あるコンフィギュレーションデータに基づくデータフローを示す図である。図１０に示すように、このコンフィギュレーションデータに基づくと、データフローにおいて、ソースＰＥであるＤＬＶのＸ出力とデスティネーションＰＥであるＲＡＭのＸ入力との間は接続され、その信号線はＸ１と名付けられている。また、ソースＰＥである同じＤＬＶのＹ出力とデスティネーションＰＥであるＥＸＲのＹ入力との間が接続され、その信号線はＹ１と名付けられている。このように、コンフィグレーションデータにおいては、ＰＥを特定する情報（たとえば、ＰＥに付されたＩＤなど）と、ＰＥ間を接続する信号線名（Ｘｎ、Ｙｎ（ｎ＝１、２、・・・）が含まれる。なお、図１０の例では、ＰＥ間のＸ出力／Ｘ入力およびＹ出力／Ｙ入力について示したが、コンフィギュレーションデータには、キャリーＸ（ＣＸ）出力／ＣＸ入力、キャリーＹ（ＣＹ）出力／ＣＹ入力の信号線についての情報も含まれる。
【００４６】
マップ作成部１４は、記憶装置１２に記憶されたソースＰＥ・デスティネーションＰＥファイル１０３を参照して、信号線Ｘｎ、Ｙｎごとに、信号線が割り当てられる可能性のある、バスのラインにビット「１」をセットするようなバスリソースリクエストマップを作成する（ステップ９０２）。また、マップ作成部１４は、キャリーの信号線ＣＸｎ、ＣＹｎについても同様にバスリソースリクエストマップを作成する。作成されたバスリソースリクエストマップ１０１は、記憶装置１２中に記憶される。
【００４７】
図１１（ａ）、（ｂ）は、それぞれ、図１０のデータフローの例において、信号線Ｘｎ、Ｙｎについてのバスリソースリクエストマップを示す図である。図１１（ａ）、（ｂ）に示すように、図１０に示すデータフローにかかるバスリソースリクエストマップは、信号線Ｘ１〜Ｘ５および信号線Ｙ１〜Ｙ５のそれぞれが、第０列〜第７列のバスのラインを使用可能であれば、当該ラインに相当するビットに「１」がセットされる。たとえば、図１１（ａ）を参照すると、信号線Ｘ１は、第０列の第０ラインおよび第１ラインを使用可能であることがわかる。また、他の列（第１列〜第７列）までは使用不能であることがわかる。同様に、信号線Ｘ２は、第１列〜第６列の第０ラインおよび第１ラインを使用可能であることがわかる。
【００４８】
以下、マップ作成部１４によるマップ作成についてより詳細に説明する。マップ作成部１４は、初期的なバスリソースリクエストマップを作成して、全てのビットに「０」をセットする（ステップ１２００）。コンフィギュレーションデータ中の、ある信号線（たとえば、Ｘ１を考える。）のデータフロー上のソースＰＥ（ＤＬＶ）およびデスティネーションＰＥ（ＲＡＭ）を特定する（ステップ１２０１）、次いで、マップ作成部１４は、パラメータを初期化した後に（ステップ１２０２）、ソースＰＥ・デスティネーションＰＥファイル１０３を参照して、ステップ１２０１で特定されたデータフロー上のソースＰＥおよびデスティネーションＰＥが、第ｎ列第ｍ行のソースＰＥおよびデスティネーションＰＥのリストに存在するか否かを判断する（ステップ１２０３、１２０４）。リスト中にソースＰＥおよびデスティネーションＰＥの双方が存在する場合には（ステップ１２０４でイエス(Yes)）、バスリソースリクエストマップ中、第ｎ列第ｍラインのビットに「１」をセットする（ステップ１２０５）。マップ作成部１４は、第０列第０行から第７列第７行の全てについて、ステップ１２０３、１２０４の判断を行う（ステップ１２０５〜ステップ１２０９参照）。マップ作成部１４は、ステップ１２０１〜ステップ１２１０の処理を、全ての信号線（Ｘ、Ｙ、ＣＸおよびＣＹ）について実行する（ステップ１２１０、１２１１参照）。
【００４９】
たとえば、信号線Ｘ１について、データフロー上のソースＰＥはＤＬＶであり、デスティネーションＰＥはＲＡＭである。ソースＰＥ・デスティネーションＰＥファイル１０３を参照すると、第０列第０行には、ソースＰＥとしてＤＬＶがリストされ、かつ、デスティネーションＰＥとしてＲＡＭがリストされている。したがって、バスリソースリクエストマップファイル中、第０列第０ラインに対応するビットが「１」にセットされる。また、第０列第１行にも、ソースＰＥとしてＤＬＶがリストされ、かつ、デスティネーションＰＥとしてＲＡＭがリストされている。したがって、バスリソースリクエストマップファイル中、第０列第１ラインに対応するビットが「１」にセットされる。
【００５０】
バスリソースリクエストマップ１０１が出来上がると、マップ更新部１６は、以下に詳細に説明する複数のルールを用いて、バスリソースリクエストマップファイル１０１を更新し、また、その更新にともなって、信号線のバスへの割り当てを決定していく。まず、マップ更新部１６は、バスリソースリクエストマップ１０１を参照して、第１のルールを適用する（ステップ９０３）。第１のルールとは、バスリソースリクエストマップ中、ある信号線について、第０列〜第７列の全てのラインに関するビットが「０」である場合に、その信号線が配置不可能であることである。たとえば、図１３の例において、信号線Ｘ３について、全ての列のラインに関するビットが「０」となっている（符号１３０１参照）。これは、信号線Ｘ３を、実際のＬＳＩ中の何れかの列のラインに割り当てることが不可能であることを示している。
【００５１】
したがって、マップ更新部１６は、それぞれの信号線について、全ての列のラインに対応するビットが「０」であるか否かを判断し、何れかの信号線について、全てのビットが「０」であれば、ステップ９０４でイエス(Yes)と判断され、処理は終了する。処理の終了に際して、データフロー上のＰＥのＬＳＩ上のＰＥへの割り当て、および、データフロー上の信号線のＬＳＩ上のバスへの割り当てが不可能であることを示す情報を出力する。この情報は、たとえば、配置配線決定システム１０の表示装置（図示せず）の画面上に表示される。このように、配置配線が不可能であると判断された場合には、パーティションのコンフィグレーションのデータ自体の変更が必要となる。
【００５２】
ステップ９０４でノー(No)と判断された場合には、マップ更新部１６は、第２のルールを適用して、必要に応じて、バスリソースリクエストマップを更新する（ステップ９０５）。第２のルールとは、バスリソースリクエストマップ中、ある信号線について、列０〜７のラインに対応するビットが１つだけ「１」であるときには、その信号線は、ビットが「１」となったラインに割り当てるというものである。図１４に示すように、マップ更新部１６は、バスリソースリクエストマップ中、ある信号線についてのビットを参照して（ステップ１４０１）、「１」がセットされているビットが１つだけの場合には（ステップ１４０２でイエス(Yes)）、そのビットの値を更新不可能であることを示す情報を、当該ビットに付加する（ステップ１４０３）。この情報として、たとえば、各ビットに対応付けられた更新不可能を表すフラグ（更新不可能フラグ）を利用することができ、記憶装置中に設けられたフラグ領域において、該当するフラグを「１」にセットすればよい。
【００５３】
次いで、マップ更新部１６は、バスリソースリクエストマップを参照して、そのビットと、同一列で同一ラインのビットでその値が「１」であるものを探す（ステップ１４０４）。値が「１」であるビットが見出され（ステップ１４０５でイエス(Yes)）、かつ、そのビットについて、更新不可能フラグがセットされていない場合には（ステップ１４０６でノー(No)）、マップ更新部１６は、そのビットの値を「０」にする（ステップ１４０７）。
【００５４】
なお、ステップ１４０４でイエス(Yes)と判断され、かつ、そのビットについて更新不可能フラグがセットされている場合（ステップ１４０６でイエス(Yes)）には、１つのバスを複数の信号線が使用せざるを得ないという、現実に配線不可能な状態となるため、処理を終了して、パーティションのコンフィギュレーションデータ自体の作成に戻る。また、マップ更新部１６は更新後のバスリソースリクエストマップについて、第１のルールを適用して、それぞれの信号線について、全ての列のラインに対応するビットが「０」であるか否かを判断し（ステップ１４０８）、何れかの信号線について、全てのビットが「０」であれば（ステップ１４０９でイエス（Yes））、同様に現実に配線不可能な状態となるため、処理を終了して、パーティションのコンフィギュレーションデータ自体の作成に戻る。この場合にも、配線が不可能であることを、たとえば、表示装置の画面上に表示する。以下、配線が不可能であると判断された場合には、同様の処理が実行されるが、説明は省略する。マップ更新部１６は、ステップ１４０１〜ステップ１４０９の処理を、全ての信号線について実行する（ステップ１４１０、１４１１参照）。
【００５５】
図１５（ａ）に示す例において、信号線Ｙ４については、バスリソースリクエストマップにおいて、第３列第４ラインのビットのみが「１」となっている（符号１５０１参照）。したがって、信号線Ｙ４の第３列第４ラインには更新不可能フラグがセットされる。また、図１５（ｂ）に示すように、他の信号線について、バスリソースリクエストマップ中、同一列同一ラインで「１」となっているビットがあれば、このビットの値が「０」となる（符号１５０２参照）。
【００５６】
なお、バスリソースリクエストマップにおいて、たとえば、第ｎ列第ｍラインに沿ってビットの値を参照した場合に、１つの信号線についてのみ、値が「１」であったとする。この場合には、この信号線には、第ｎ列第ｍラインのバスを割り当てても良いことを意味している。
【００５７】
次に、マップ更新部１６は、第３のルールを適用して、バスリソースリクエストマップを更新する（ステップ９０６）。第３のルールにおいては、パーティションのコンフィグレーションデータに示されるそれぞれのＰＥについて、その入力の信号線に着目して、バスリソースリクエストマップ中、各信号線の何れかについて、第ｎ列のビットの値が全て「０」である場合には、その列にＰＥを配置できないと判断される。
【００５８】
より詳細には、図１６に示すように、マップ更新部１６は、あるＰＥに着目して、そのＰＥのＸ入力、Ｙ入力、ＣＸ入力およびＣＹ入力となる信号線について、バスリソースリクエストマップの部分を取得する（ステップ１６０１）。次いで、処理用のパラメータの初期化（ステップ１６０２）の後、マップ更新部は、取得したバスリソースリクエストマップの部分中、信号線の何れかについて、第ｎ列のビットがすべて「０」であるか否かを判断する（ステップ１６０３）。何れかの信号線について第ｎ列のビットの全てが「０」である場合には（ステップ１６０４でイエス(Yes)）、他の信号線についても、第ｎ列のビットを全て「０」にする（ステップ１６０５）。ここでも、更新不可能フラグが「１」であるようなビットが存在すれば（ステップ１６０７でイエス(Yes)）、配線が不可能な状態であるため、パーティションのコンフィギュレーションデータ自体の再度作成が必要となる。ステップ１６０４〜ステップ１６０６については、第０列から第７列の全てについて実行される（ステップ１６０７、１６０８参照）。
【００５９】
その後、マップ更新部１６は、再度第１のルールを適用して（ステップ１６０９）、全てのビットが「０」であるような信号線が存在するかどうかを判断する（ステップ１６１０）。ステップ１６０９でイエス(Yes)と判断された場合にも、配線が不可能な状態であるため、パーティションのコンフィギュレーションデータ自体の再度作成が必要となる。マップ更新部１６は、ステップ１６０１〜１６１０の処理を、すべてのＰＥについて実行する（ステップ１６１１、１６１２参照）。
【００６０】
たとえば、図１７（ａ）に示す例において、あるＰＥのＸ入力、Ｙ入力、ＣＸ入力およびＣＹ入力として、それぞれ、信号線Ｘ３、Ｙ２、ＣＸ６、および、ＣＹ５が与えられ、かつ、バスリソースリクエストマップの各信号線に関する部分が、図１７（ｂ）に示すようなものであったとする。この例では、キャリー入力ＣＸ６の第２列、および、Ｘ入力Ｘ３の第4列のビットが全て「０」である。したがって、図１７（ｃ）に示すように、バスリソースリクエストマップの部分において、第２列のビットおよび第４列のビットが「０」にされる。
【００６１】
次いで、配置配線処理部１８は、記憶装置１２に記憶されたパーティションのコンフィグレーションデータから、データフロー上のＰＥの情報を取得し、また、取得したＰＥの属性および機能を参照して、データフロー上のＰＥを、実際のＬＳＩのセグメント上の候補位置に配置する（つまり、データフロー上のＰＥを、当該候補位置のＬＳＩ上のＰＥに配置する）と仮定して、当該位置を示す情報（列番号および行番号）を記憶装置１２に一時的に記憶する（ステップ９０８）。たとえば、コンフィグレーションデータ中のデータフロー上のＰＥがＥＸＭであれば、当該ＥＸＭは、第１列ないし第５列の、第２行または第６行、或いは、第６列の第１行、第２行、第５行或いは第６行の何れかを候補位置とすることができる。本実施の形態においては、候補位置は、列番号の小さい順でかつ行番号が小さい順に決められる。ついで、マップ更新部１６は、第４のルールを適用して、必要に応じて、バスリソースリクエストマップを更新する（ステップ９０８）。
【００６２】
図１８および図１９は、第４のルールの適用処理をより詳細に示すフローチャートである。図１８に示すように、マップ更新部１６は、ＰＥの候補位置の列番号および行番号に基づいて、入力側の信号線が割り当てられるバスの列番号、および、出力側の信号線が割り当てられるバスのライン番号を特定する（ステップ１８０１）。
【００６３】
たとえば、図２０（ａ）に示すように、処理対象となったデータフロー上のＰＥが、ＥＸＭであり、かつ、そのＬＳＩ上の候補位置が、第１列第１行であると考える。この場合には、入力側の信号線が割り当てられるバスの列番号は「１（第１列）」であり、また、出力側の信号線が割り当てられるバスのライン番号は、「０または１（第０ラインおよび第１ライン）」となる。つまり、バスリソースリクエストマップにおいて、ＰＥに入力する信号線であるＸ２は、第１列の何れかのラインに限定される。また、ＰＥから出力する信号線であるＸ３は、ソースＰＥ・ディスティネーションＰＥから判断することにより、各列の第０ライン或いは第１ラインに限定される。図７、図８等を参照して説明したように、ＰＥについては、それぞれ、入力として接続可能なバスが位置する列が決定され、かつ、出力として接続可能なバスが位置するラインが決定される。したがって、第４のルールを適用する際にも、ＰＥの候補位置によって、入力する信号線の列と出力する信号線のラインが限定される。
【００６４】
そこで、マップ更新部１６は、バスリソースリクエストマップにおいて、ＰＥに入力する信号線に割り当て可能な列のビットを参照して、バスを割り当て可能なライン（つまり、ビットの値が「１」であるライン）を特定する（ステップ１８０２）。たとえば、上述したようにＥＸＭを第１列第１行に配置した場合の、入力する信号線であるＸ２についで、バスリソースリクエストマップ中、第１列の８つのラインの値は「０１００００００」である。したがって、Ｘ２については、第１ラインに対応するビットのみが「１」であるため、Ｘ２の信号線は、第１列第１ラインのバスに割り当てられる。
【００６５】
その一方、ある信号線について、バスリソースリクエストマップ中、ＰＥの配置された列について複数のビットの値が「１」である場合（たとえば、８つのラインの値が「１１００００００」である場合）には、第０ライン或いは第１ラインの何れかが選択される。複数のビットの値が「１」である場合には、マップ更新部１６は、選択したビット以外のビットを「０」とするように、バスリソースリクエストマップを更新する。
【００６６】
次いで、マップ更新部１６は、バスリソースリクエストマップを参照して、ＰＥに割り当て可能なバスの列番号に基づいて、入力する信号線が割り当てられる列以外の列のビットを「０」に変更するとともに（ステップ１８０３）、出力する信号線が割り当てられるライン以外のラインのビットを「０」に変更する（ステップ１８０４）。
【００６７】
図２０（ａ）の例について、バスリソースリクエストマップを参照すると、ＰＥに入力する信号線Ｘ２については、図２０（ｂ）に示すように、第１列を除く、第０列、第２列〜第７列のビット（符号２００１およびアンダーライン参照）が「０」にされる。また、ＰＥから出力する信号線Ｘ３については、それぞれの列において、第０ラインおよび第１ラインを除く、第２ライン〜第７ラインのビット（符号２００２およびアンダーライン参照）が「０」にされる。図２０（ａ）は、ステップ１８０３、１８０４において、必要な列およびラインのビットを「０」に変更した状態を示す図である。図２０（ａ）において、アンダーラインを引いたビットについて、値が「１」から「０」に変更される。
【００６８】
第４のルール適用処理において、値を「１」から「０」に変更すべきビットについて、更新不可能フラグが「１」である場合（ステップ１８０５でイエス(Yes)）には、配置配線処理部１８は、ＰＥの配置された列において、信号線として他のラインのバスを割り当て可能であるか否かを判断する。バスリソースリクエストマップの信号線を割り当てるべき列のビットにおいて、もともと複数のビットに「１」が存在していた場合には（ステップ１８０６でイエス(Yes)）、バスリソースリクエストマップにおいて、値を「１」に残しておくビットを変更して、ステップ１８０３に戻る。たとえば、もともと、バスリソースリクエストマップ中、入力側の信号線を割り当てるべき列において、８つのラインの値が「１１００００００」であり、第０ラインを選択して、第１ラインのビットの値を「０」に変更した上で、処理を進め、ステップ１８０５においてノー(No)と判断された場合には、第１ラインを「１」として、８つのラインの値を「０１００００００」と変更した上で、再度、同様の処理を施す。
【００６９】
また、入力側の信号線を割り当てる列において、他のビットについても処理を実行したが、他のビットのすべてについて更新不可能フラグが存在していた場合には、ステップ１８０６でイエス(Yes)と判断される。この場合には、ＰＥの候補位置を変更可能であれば（ステップ１８０７でイエス(Yes)）、配置配線処理部１８は、ＰＥの候補位置を変更して（ステップ１８０８）、再度、新たな候補位置に関して、信号線が割り当て可能なバス番号およびライン番号を特定して、それに基づいて、バスリソースリクエストマップを更新する。
【００７０】
また、ステップ１８０５でノー(No)と判断された場合には、図１９に示すように、マップ更新部１６は、第１のルールを適用して（ステップ１９０１）、全てのビットが「０」であるような信号線があるか否かを判断する（ステップ１９０２）。ステップ１９０２でイエス(Yes)と判断された場合には、ステップ１８０６と同様に、バスリソースリクエストマップ中、入力側の信号線を割り当てる列において、もともと「１」であるような他のビットが存在するか否かを判断する（ステップ１８０６）。ステップ１８０６でイエス(Yes)と判断された場合には、マップ更新部１６は、バスリソースリクエストマップを変更した上で、ステップ１８０３に戻る。
【００７１】
ステップ１８０６でノー(No)と判断された場合には、ステップ１８０７と同様に、ＰＥの候補位置を変更可能であれば（ステップ１９０４でイエス(Yes)）であれば、配置配線処理部１８は、ＰＥの候補位置を変更して（ステップ１８０８）、再度、新たな候補位置に関して、信号線が割り当て可能なバス番号およびライン番号を特定して、それに基づいて、バスリソースリクエストマップを更新する。たとえば、図２１（ｂ）に示すように、バスリソースリクエストマップの更新に伴って、信号線Ｘ４については、全ての列のバスのビットが「０」となってしまう（符号２１１１参照）。このような場合には、ＰＥを次の候補位置に移動させて、再度同様の処理を実行する。
【００７２】
ステップ１８０７においてノー(No)と判断されたとき、或いは、ステップ１９０４でノー(No)と判断されたときには、パーティションのコンフィグレーションデータを再度作成する必要があると判断される。
【００７３】
第１のルールの適用の結果、バスリソースリクエストマップにおいて、全てのビットが「０」となるような信号線が存在しなければ（ステップ１９０２でノー(No)）、配置配線処理部１８は、ＰＥの候補位置、および、バスリソースリクエストマップ中、ＰＥの入力側の信号線についてビットが「１」となっている位置（列およびライン）を、記憶装置１２中の配線情報／接続情報ファイル１０２に追加する（ステップ１９０５）。また、マップ更新部１６は、バスリソースリクエストマップ中、上記ＰＥの入力側の信号線について「１」となっているビットに更新不可能フラグを付加する（ステップ１９０６）。
【００７４】
さらに、マップ更新部１６は、バスリソースリクエストマップにおいて、他の信号線についても、１つのビットのみが「１」となっているものがあれば、そのビットに更新不可能フラグを付加する（ステップ１９０７）。データフローファイル中に、まだ位置が決められていないＰＥが存在すれば（ステップ１９０８）、ステップ９０９に戻る。このような処理を繰り返すことにより、ＰＥの位置（列および行）およびバスの位置（列およびライン）を決定することができる。
【００７５】
本実施の形態においては、ＰＥを候補位置に配置し、少なくともその入力側のバスを選択し、候補位置および入力側のバスの位置を記憶しておく。その後、バスリソースリクエストマップにおいて、ＰＥの位置からは使用される可能性の無いバスについて、ビットを「０」とした上で、配線不可能となる他の信号線が存在しなければ、ＰＥの候補位置および入力側のバスの位置を確定させて、これらの情報を配置情報／接続情報ファイルに追加する。このように、ＰＥごとに候補位置の決定や入力側のバスの選択、バスリソースリクエストマップの更新、配置不可能な他の信号線の有無の判断、位置の確定を繰り返すことにより、順次、ＰＥのＬＳＩ上の位置および信号線に対応するＬＳＩ上のバスの位置が、配置情報／接続情報ファイル１０２に追加されていく。
【００７６】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【００７７】
たとえば、前記実施の形態においては、ＬＳＩ上のＰＥは、その列の何れかのＰＥをソースＰＥとすることができ（つまり、同じ列のＰＥからの出力を入力とするようなせつぞくが可能であり）、また、同じライン或いは隣接する１つのラインのＰＥをデスティネーションＰＥとすることができる（つまり、同じラインあるいは隣接する１つのラインのＰＥに出力できるようなバスの接続が可能である）。しかしながら、このような構成に限定されることはなく、本発明は、ＬＳＩにおけるＰＥ間に他の接続の制限があった場合にも適用が可能である。
【図面の簡単な説明】
【００７８】
【図１】。図１は、本実施の形態にかかる配置配線決定システム１０の概略を示すブロックダイヤグラムである。
【図２】図２は、本実施の形態にかかるＬＳＩの６つのセグメントの例を示す図である。
【図３】図３は、本実施の形態にかかるＰＥの入出力を説明する図である。
【図４】図４は、本実施の形態にかかるＸデータバスおよびＹデータバスを模式的に示す図である。
【図５】図５は、本実施の形態にかかるＸキャリーバスおよびＹキャリーバスを模式的に示す図である。
【図６】図６は、本実施の形態にかかるＰＥにおけるバスの入出力の制限を説明する図である。
【図７】図７（ａ）、（ｃ）は、それぞれ、第６列第２ライン、および、第０列第０ラインの信号線について、ソースＰＥおよびデスティネーションＰＥとなり得るＰＥを説明する図である。
【図８】図８は、本実施の形態にかかるソースＰＥ・デスティネーションＰＥファイルのデータ構成の例を説明する図である。
【図９】図９は、本実施の形態にかかる配置配線決定システムにおける配置配線処理の概略を示すフローチャートである。
【図１０】図１０は、あるコンフィギュレーションデータを、データフローとして描いた図である。
【図１１】図１１（ａ）、（ｂ）は、それぞれ、図１０のデータフローの例において、信号線Ｘｎ、Ｙｎについてのバスリソースリクエストマップを示す図である。
【図１２】図１２は、本実施の形態にかかるバスリソースリクエストマップの作成処理の例を示すフローチャートである。
【図１３】図１３は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図１４】図１４は、本実施の形態にかかる第２のルール適用処理の例を示すフローチャートである。
【図１５】図１５（ａ）、（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図１６】図１６は、本実施の形態にかかる第３のルール適用処理の例を示すフローチャートである。
【図１７】図１７（ａ）は、データフローにおけるあるＰＥの入力を説明する図、図１７（ｂ）、（ｃ）は、バスリソースリクエストマップの該当部分を示す図である。
【図１８】図１８は、本実施の形態にかかる第４のルール適用処理の例を示すフローチャートである。
【図１９】図１８は、本実施の形態にかかる第４のルール適用処理の例を示すフローチャートである。
【図２０】図２０（ａ）は、本実施の形態にかかるあるＰＥのＸ入出力およびＹ入出力を示す図、図２０（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図２１】図２１（ａ）、（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【符号の説明】
【００７９】
１０ 配置配線決定システム
１２ 記憶装置
１４ マップ作成部
１６ マップ更新部
１８ 配置配線処理部
１００ データフローファイル
１０１ バスリソースリクエストマップ
１０２ 配置情報／接続情報ファイル
１０３ ソースＰＥ・デスティネーションＰＥファイル
【技術分野】
【０００１】
本発明は、リコンフィグラブルＬＳＩにおける配置配線の決定方法および配置配線の決定プログラムに関する。
【背景技術】
【０００２】
近年、ＬＳＩを構成する回路の一部をソフトウェアにより再構成できるハードウェアが提供されている。このようなＬＳＩはリコンフィグラブル（再構成可能）ＬＳＩと称されている。リコンフィグラブルＬＳＩの設計者は、たとえば、Ｃ＋＋に類似するハードウェア記述言語を用いて、ＬＳＩを構成する、それぞれが属性や機能が定義された演算ユニットと、演算ユニット間の接続とを規定したデータフローダイヤグラムを作成し、作成したデータを、ハードディスクなどの記憶装置に記憶する。本明細書において、データフローダイヤグラムのデータを記憶したファイルを、データフローファイルと称する。データフローファイルにおいては、特定の属性や機能を有する演算ユニットおよび演算ユニット間の接続が規定されているのみであり、したがって、データフローファイルにおける演算ユニット（データフロー上の演算ユニット）と、実際のＬＳＩ上の演算ユニットとの間の対応付けや、データフローファイルにおける演算ユニット間の接続（データフロー上の接続）と、実際のＬＳＩ上のバスとの間の対応付けは完了していない。したがって、データフロー上の演算ユニットと実際のＬＳＩ上の演算ユニットとの対応付け、および、データフロー上の接続と、実際のＬＳＩ上のバスとの対応付けを行う配置配線の決定が必要である。
【０００３】
たとえば、特許文献１には、最適配置したい信号（演算ユニット値の接続）に優先順位を付け、対象回路のネットリストに基づき、優先信号順に配置配線を決定する方法が提案されている。
【特許文献１】特開平８−８７５３７号公報
【特許文献２】国際公開ＷＯ０３／００７１５５号公報
【非特許文献１】榊原泰徳、佐藤友美著、「ＤＡＰＤＮＡのデバイスアーキテクチャ」、デザインウェーブマガジン（Design Wave Magazine）２００４年８月号、「特集 動的再構成可能デバイス その素性と実力 第２章」、ＣＱ出版社、２００４年８月、第３０頁〜第３８頁
【発明の開示】
【発明が解決しようとする課題】
【０００４】
さらに、近年、ＬＳＩを構成する回路の一部をソフトウェアによりリアルタイムに再構成できるダイナミック・リコンフィグラブルＬＳＩが提供されている。たとえば、特許文献１には、再構成する基本単位を、ＡＬＵなどのある程度の規模の演算機能を備えた演算ユニットである処理エレメント（ＰＥ）として、それぞれが特定の属性や機能を有する複数種類のＰＥをマトリクス状に配置し、再構成に要する時間を短縮することができるようなダイナミック・リコンフィギュラブルＬＳＩが開示されている。また、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩにおいては、ＬＳＩが複数のセグメントに分割され、各セグメントに決められた属性および機能を有する所定数のＰＥが配置されている。したがって、非特許文献１に開示されたダイナミック・リコンフィギュラブルＬＳＩについては、セグメントごとに、データフロー上のＰＥと、実際のセグメント上のＰＥとの対応付けおよびデータフロー上のＰＥ間の接続と、当該セグメント上のバスとの対応付けを行い、この対応付けを示す情報を、配置配線情報として、ハードディスクなどの記憶装置に記憶する。
【０００５】
各セグメント上のＰＥの数には限りがあり（たとえば、６４個）かつ、セグメント上のバスの数にも限りがある（たとえば、Ｘ入出力のために６４本）。さらに、各ＰＥに入力として接続可能なバスおよびＰＥから出力として接続可能なバスも限られている。したがって、限られたＬＳＩ上のＰＥやバスのリソースに、データフロー上のＰＥや接続を適切に割り当てる配置配線の決定が求められる。
【０００６】
本発明は、リコンフィグラブルＬＳＩの処理エレメントの入出力の制限を考慮して、適切に、データフロー上の処理エレメントを、ＬＳＩ上の処理エレメントに割り当て、かつ、データフロー上の処理エレメント間の接続を、ＬＳＩ上のバスに割り当てることができる配置配線の決定方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の目的は、２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援する方法であって、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を備えたことを特徴とする方法により達成される。
【０００８】
好ましい実施態様においては、前記バスリソースリクエストマップを生成するステップが、前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を含む。
【０００９】
より好ましい実施態様においては、前記バスリソースリクエストマップを作成するステップが、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを含む。
【００１０】
好ましい実施態様において、前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造である。
【００１１】
別の好ましい実施態様においては、さらに、前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを備えている。
【００１２】
また、本発明の目的は、上述したようなバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定する方法であって、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を備えたことを特徴とする方法によっても達成される。
【００１３】
好ましい実施態様においては、前記バスリソースを更新するステップが、前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含む。
【００１４】
また、好ましい実施態様においては、前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップを備え、前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力する。
【００１５】
別の好ましい実施態様においては、前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含む。
【００１６】
また、本発明の目的は、２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援するために、コンピュータにより読み出し可能なプログラムであって、
前記コンピュータに、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を実行させることを特徴とするプログラムにより達成される。
【００１７】
好ましい実施態様においては、前記バスリソースリクエストマップを生成するステップにおいて、前記コンピュータに、
前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を実行させる。
【００１８】
より好ましい実施態様においては、前記バスリソースリクエストマップを作成するステップにおいて、前記コンピュータに、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを実行させる。
【００１９】
好ましい実施態様において、前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造である。
【００２０】
別の好ましい実施態様においては、さらに、前記コンピュータに、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを実行させる。
【００２１】
また、本発明の目的は、上述したバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定するために、コンピュータにより読み出し可能なプログラムであって、前記コンピュータに、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を実行させることを特徴とするプログラムによっても達成される。
【００２２】
好ましい実施態様においては、前記バスリソースを更新するステップにおいて、前記コンピュータに、
前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させる。
【００２３】
また、好ましい実施態様においては、前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップと、
前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力するステップと、を実行させる。
【００２４】
別の好ましい実施態様においては、前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させる。
【発明の効果】
【００２５】
本発明によれば、リコンフィグラブルＬＳＩの処理エレメントの入出力の制限を考慮して、適切に、データフロー上の処理エレメントを、ＬＳＩ上の処理エレメントに割り当て、かつ、データフロー上の処理エレメント間の接続を、ＬＳＩ上のバスに割り当てることができる配置配線の決定方法およびプログラムを提供することが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、添付図面を参照して、本発明の実施の形態について説明する。図１は、本実施の形態にかかる配置配線決定システム１０の概略を示すブロックダイヤグラムである。本実施の形態においては、記憶装置１２には、後述するように、特許文献１および非特許文献２に記載された、動的再構成可能なＬＳＩ（以下、単に「ＬＳＩ」と称する）において、配置配線をするための基礎となるデータフローファイル１００が設けられている。非特許文献１に記載されるように、本実施の形態において、配置配線が決定されるＬＳＩは、６つのセグメントに分割され、かつ、それぞれのセグメントには、決められた属性および機能を有する、決められた数の処理エレメント（ＰＥ）が配置されている。
【００２７】
また、配置配線決定システム１０は、データフローファイル１００中の、セグメントごとのコンフィギュレーションデータを参照して、記憶装置１２中にバスリソースリクエストマップ１０１を作成するマップ作成部１４と、所定のルールに基づいてバスリソースリクエストマップ１０１を更新するマップ更新部１６とを備えている。さらに、本実施の形態にかかる配置配線決定システム１０は、コンフィギュレーションデータに含まれるデータフロー上の処理エレメント（ＰＥ）を、パーティション内に配置されたＬＳＩ上の処理エレメントのうち、所定の位置にあるものに割り当てると仮定して、さらに他の所定のルールに基づいて、コンフィギュレーションデータに含まれるデータフロー上のＰＥの、セグメント中の具体的な位置を決定し、かつ、データフロー上のＰＥ間の信号線を、ＬＳＩ上の実際のバスに割り当て、データフロー上のＰＥのＬＳＩ上の位置およびデータフロー上の信号線に割り当てられたバスの位置を含む配置情報／接続情報ファイル１０２を記憶装置１２中に生成し、かつ、バスリソースリクエストマップ１０１を更新する配置処理部１８を備えている。なお、本実施の形態において、処理エレメントとはＬＳＩの演算単位である。
【００２８】
バスリソースリクエストマップ１０１、および、配置処理部１８による処理により得られる、コンフィギュレーションデータにおける演算回路の、セグメント中の具体的なＰＥの位置の情報（配置情報）およびＰＥ間の接続情報を含む配置情報／接続情報ファイル１０２は、記憶装置１２に記憶される。さらに、記憶装置１２には、マップ作成部１４によりバスリソースリクエストマップが作成される際に参照されるソースＰＥ・デスティネーションＰＥファイル１０３が記憶される。このソースＰＥ・デスティネーションＰＥファイル１０３については後述する。
【００２９】
本実施の形態にかかるＬＳＩは、複数のセグメントに分割されている。図２は、本実施の形態にかかるＬＳＩの６つのセグメントの例を示す図である。図２に示すように、それぞれのセグメントには、６４個（セグメント１、セグメント３〜５）、或いは、６０個（セグメント０、セグメント２）のＰＥが設けられている。各セグメントには、あらかじめ決められた機能を果たすＰＥが決められた位置に配置される。なお、本実施の形態のセグメントにおいて、横方向に、図２における左から第０列、第１列、・・・、と称し、縦方向に図２における上から第０行、第１行、・・・と称する。図２において、「ＬＤＢ」、「ＲＡＭ」、「ＤＬＥ」などが、それぞれ、定められた属性および機能を有するＰＥである。
【００３０】
たとえば、セグメント０の第０行には、第１行には、ＬＳＩの外部からのデータを受け入れる４つのロードバッファ（ＬＤＢ）が配置される。ロードバッファは、そのサイズから、それぞれ、横方向に２列分のサイズを持つ。セグメント０の第１行には、第０列から、「ＲＡＭ」、４つの「Ｃ１６Ｌ」、２つの「Ｃ１６Ｅ」および「ＤＬＨ」という８つのＰＥが配置されている。たとえば、「ＲＡＭ」は、１６ＫバイトのＬＳＩの内部メモリ、「Ｃ１６Ｌ」や「Ｃ１６Ｅ」は、アドレス生成用のＰＥ、「ＤＬＨ」は、図２における水平方向に位置する他のセグメントに出力可能な遅延要素である。詳細な説明は省略するが、各セグメントには、それぞれがあらかじめ定められた機能を有するＰＥが決められた場所に配置されている。そのほか、「ＥＸ＊（＊：Ｃ，Ｓ，Ｒ，Ｍ）」は、それぞれ、算術演算、論理演算、比較などの機能を有する演算ユニットである。
【００３１】
ＰＥの間を接続するためには、４種類のデータバスが存在する。本実施の形態においては、ＰＥは、図３に示すように、Ｘ入力およびＹ入力の２つのデータ入力（ｄｉｘおよびｄｉｙ）、ＣＸ入力およびＣＹ入力の２つのキャリー入力（ｃｉｘおよびｃｉｙ）、Ｘ出力およびＹ出力の２つのデータ出力（ｄｏｘおよびｄｏｙ）、並びに、ＣＸ出力およびＣＹ出力の２つのキャリー出力（ｃｏｘおよびｃｏｙ）が可能である。あるＰＥのＸ出力、Ｙ出力は、それぞれ、１以上の他のＰＥのＸ入力、Ｙ入力に接続され得る。同様に、ＰＥのＣＸ出力、ＣＹ出力は、それぞれ、１以上の他のＰＥのＣＸ入力、ＣＹ入力に接続され得る。Ｘ出力とＸ入力とを接続するバスを、Ｘデータバス、Ｙ出力とＹ入力とを接続するバスをＹデータバス、ＣＸ出力とＣＸ入力とを接続するバスをＸキャリーバス、ＣＹ出力とＣＹ出力とを接続するバスを、Ｙキャリーバスと称する。
【００３２】
図４は、ＸデータバスおよびＹデータバスを模式的に示す図、図５は、ＸキャリーバスおよびＹキャリーバスを模式的に示す図である。図４に示すように、本実施の形態においては、第０列、第１列、・・・のＰＥ群の両側に、その列のＸデータバスおよびＹデータバスが設けられている。たとえば、左端の第０列のＰＥ群（符号４０１、４０２、・・・参照）の（図４における）左側には、８つのラインからなる第０列のＸデータバス（符号４１１参照）が配置され、ＰＥ群の（図４における）右側には、８つのラインからなる第０列のＹデータバスが配置されている（符号４１２参照）。他の列（第ｎ列）のＰＥ群についても、その両側に、それぞれ８ラインからなる第ｎ列のＸデータバスおよびＹデータバスが配置される。図５に示すように、キャリーバスも同様に、第ｎ列のＰＥ群（たとえば符号５０１、５０２、・・・参照）について、（図５における）左側には８つのラインからなる第ｎ列のＸキャリーバスが配置され（たとえば符号５１１参照）、（図５における）右側には８つのラインからなる第ｎ列のＹキャリーバスが配置される（たとえば符号５１２参照）。
【００３３】
図６は、ＬＳＩ上の実際のＰＥにおけるバスの入出力の制限を説明する図である。本実施の形態においては、ＰＥ６０３は、データバスとの接続のために、ＰＥコンフィギュレーション部６００およびマルチプレクサコンフィギュレーション部６１０を有する。
【００３４】
図６に示すように、Ｘデータバスの各ラインは、セレクタ６０１を介して、ＰＥ６０３のＸ入力（ｄｉｘ）に接続される。また、Ｙデータバスの各ラインは、セレクタ６０２を介して、ＰＥ６０３のＹ入力（ｄｉｙ）に接続される。ＰＥ６０３のＸ入力（ｄｉｘ）は、同じ列のＸデータバスの何れかのラインに限られ、また、ＰＥ６０３のＹ入力（ｙｉｘ）も、同じ列のＹデータバスの何れかのラインに限られる。その一方、図６には明瞭に示されていないが、本実施の形態においては、ＰＥ６０３のＸ出力（ｄｉｘ）およびＹ出力（ｄｉｙ）は、それぞれ、マルチプレクサ６１１、６１２を介して、Ｘデータバス、Ｙデータバスの、ＰＥが位置する行、或いは、予め定められた隣接する行に位置する他のＰＥに接続可能なラインに接続され得る。つまり、第ｎ列のＰＥは、各列のデータバスの第ｎラインと、第（ｎ−１）ライン或いは第（ｎ＋１）ラインに接続可能である。ここで、バスの番号を示すライン番号は、行番号と等価である。
【００３５】
図６における符号６１３、６１４は、それぞれ、他のＰＥからのＸ出力およびＹ出力を示している。
【００３６】
本実施の形態においては、ＰＥの出力については以下のように定められている。
【００３７】
第０行のＰＥ：第０ライン、第１ライン
第１行のＰＥ：第０ライン、第１ライン
第２行のＰＥ：第２ライン、第３ライン
第３行のＰＥ：第２ライン、第３ライン
第４行のＰＥ：第４ライン、第５ライン
第５行のＰＥ：第４ライン、第５ライン
第６行のＰＥ：第６ライン、第７ライン
第７行のＰＥ：第６ライン、第７ライン
図示はしないが、キャリーバスについても、同様にＰＥの入出力の制限がある。
【００３８】
ＰＥの入出力という観点からは、上述したような接続の制限がある。その一方、データバスの各ラインについても、ＰＥの入出力の制限から、当該ラインに出力することができるＰＥ或いは当該ラインから入力することができるＰＥを決めることができる。
【００３９】
以下、セグメント１を例にして、第ｎ列第ｍラインのバスに接続可能なＰＥを説明する。第ｎ列第ｍラインのバスには、当該バスにデータを出力するＰＥ（これを、「ソースＰＥ」と称する。）と、当該バスからのデータを入力するＰＥ（これを、「デスティネーションＰＥ」と称する。）とが存在し得る。前述したように、第ｍ行のＰＥは、ｍが偶数であれば、第ｍラインおよび第（ｍ＋１）ラインに出力することができ、ｍが奇数であれば、第（ｍ−１）ラインおよび第ｍラインに出力することができる。
【００４０】
したがって、第ｍラインにおけるソースＰＥは、
第ｍラインおよび第（ｍ＋１）ラインに位置するＰＥ（ｍ：偶数）
第（ｍ−１）ラインおよび第ｍラインに位置するＰＥ（ｍ：奇数）
となる。
【００４１】
その一方、第ｎ列のＰＥは、第ｎ列のバスにのみ接続することができる。そこで、第ｎ列のそれぞれのラインにおけるデスティネーションＰＥは、第ｎ列のＰＥとなる。
【００４２】
たとえば、第６列第２ラインのバスを考える。図７（ａ）において、デスティネーションＰＥとなり得るＰＥ群を符号７０１で示し、ソースＰＥとなり得るＰＥ群を符号７０２で示す。つまり、基本的には、第６列第２ラインのバスについて、ソースＰＥとなり得るＰＥは、第２列および第３列のＰＥであり、また、デスティネーションＰＥとなり得るＰＥは、第６列のＰＥである。なお、ソースＰＥ中、第７列第３行のＤＬＨ（水平方向への外部出力のための遅延素子）が除外されているのは、本実施の形態において、ＰＥが、ＤＬＨおよびＤＬＸからのデータを入力する場合には、同じ行のＤＬＨ或いはＤＬＸからに限られるという制約があるからである。
【００４３】
また、第０列第０ラインのバスを考える。図７（ｂ）において、デスティネーションＰＥとなり得るＰＥ群を符号７１１で示し、ソースＰＥとなり得るＰＥ群を符号７１２で示す。基本的には、第０列第０ラインのバスについて、ソースＰＥとなり得るＰＥは、第０行および第１行のＰＥであり、また、デスティネーションＰＥとなり得るＰＥは、第０列のＰＥである。ただし、第０列第０行のＤＬＶは、垂直方向に外部からのデータ入力のための遅延要素であるため、そもそもデスティネーションＰＥとなることができないので除外される。
【００４４】
本実施の形態においては、あらかじめ、各セグメントについて、第ｎ列第ｍライン（ｎ：０〜７、ｍ：０〜７）のそれぞれにおけるソースＰＥとデスティネーションＰＥのリストであるソースＰＥ・デスティネーションＰＥファイルを記憶装置１２に記憶しておく。ソースＰＥ・デスティネーションＰＥファイル１０３においては、図８に示すように、第ｎ列第ｍラインにおいて候補となり得るＰＥの名称が格納されている。
【００４５】
以下、本実施の形態にかかる配置配線決定システム１０において実行される処理について説明する。図９は、本実施の形態にかかる配置配線決定システムにおける配置配線処理の概略を示すフローチャートである。図９に示すように、配置配線決定システム１０のマップ作成部１４は、あるセグメントに割り当てるべきパーティションのコンフィギュレーションデータを、記憶装置１２から読み出す。コンフィギュレーションデータは、パーティションを構成する、データフロー上のＰＥの各々の属性および機能、並びに、それぞれのＰＥ間の接続を示す特定する情報を含む。図１０は、あるコンフィギュレーションデータに基づくデータフローを示す図である。図１０に示すように、このコンフィギュレーションデータに基づくと、データフローにおいて、ソースＰＥであるＤＬＶのＸ出力とデスティネーションＰＥであるＲＡＭのＸ入力との間は接続され、その信号線はＸ１と名付けられている。また、ソースＰＥである同じＤＬＶのＹ出力とデスティネーションＰＥであるＥＸＲのＹ入力との間が接続され、その信号線はＹ１と名付けられている。このように、コンフィグレーションデータにおいては、ＰＥを特定する情報（たとえば、ＰＥに付されたＩＤなど）と、ＰＥ間を接続する信号線名（Ｘｎ、Ｙｎ（ｎ＝１、２、・・・）が含まれる。なお、図１０の例では、ＰＥ間のＸ出力／Ｘ入力およびＹ出力／Ｙ入力について示したが、コンフィギュレーションデータには、キャリーＸ（ＣＸ）出力／ＣＸ入力、キャリーＹ（ＣＹ）出力／ＣＹ入力の信号線についての情報も含まれる。
【００４６】
マップ作成部１４は、記憶装置１２に記憶されたソースＰＥ・デスティネーションＰＥファイル１０３を参照して、信号線Ｘｎ、Ｙｎごとに、信号線が割り当てられる可能性のある、バスのラインにビット「１」をセットするようなバスリソースリクエストマップを作成する（ステップ９０２）。また、マップ作成部１４は、キャリーの信号線ＣＸｎ、ＣＹｎについても同様にバスリソースリクエストマップを作成する。作成されたバスリソースリクエストマップ１０１は、記憶装置１２中に記憶される。
【００４７】
図１１（ａ）、（ｂ）は、それぞれ、図１０のデータフローの例において、信号線Ｘｎ、Ｙｎについてのバスリソースリクエストマップを示す図である。図１１（ａ）、（ｂ）に示すように、図１０に示すデータフローにかかるバスリソースリクエストマップは、信号線Ｘ１〜Ｘ５および信号線Ｙ１〜Ｙ５のそれぞれが、第０列〜第７列のバスのラインを使用可能であれば、当該ラインに相当するビットに「１」がセットされる。たとえば、図１１（ａ）を参照すると、信号線Ｘ１は、第０列の第０ラインおよび第１ラインを使用可能であることがわかる。また、他の列（第１列〜第７列）までは使用不能であることがわかる。同様に、信号線Ｘ２は、第１列〜第６列の第０ラインおよび第１ラインを使用可能であることがわかる。
【００４８】
以下、マップ作成部１４によるマップ作成についてより詳細に説明する。マップ作成部１４は、初期的なバスリソースリクエストマップを作成して、全てのビットに「０」をセットする（ステップ１２００）。コンフィギュレーションデータ中の、ある信号線（たとえば、Ｘ１を考える。）のデータフロー上のソースＰＥ（ＤＬＶ）およびデスティネーションＰＥ（ＲＡＭ）を特定する（ステップ１２０１）、次いで、マップ作成部１４は、パラメータを初期化した後に（ステップ１２０２）、ソースＰＥ・デスティネーションＰＥファイル１０３を参照して、ステップ１２０１で特定されたデータフロー上のソースＰＥおよびデスティネーションＰＥが、第ｎ列第ｍ行のソースＰＥおよびデスティネーションＰＥのリストに存在するか否かを判断する（ステップ１２０３、１２０４）。リスト中にソースＰＥおよびデスティネーションＰＥの双方が存在する場合には（ステップ１２０４でイエス(Yes)）、バスリソースリクエストマップ中、第ｎ列第ｍラインのビットに「１」をセットする（ステップ１２０５）。マップ作成部１４は、第０列第０行から第７列第７行の全てについて、ステップ１２０３、１２０４の判断を行う（ステップ１２０５〜ステップ１２０９参照）。マップ作成部１４は、ステップ１２０１〜ステップ１２１０の処理を、全ての信号線（Ｘ、Ｙ、ＣＸおよびＣＹ）について実行する（ステップ１２１０、１２１１参照）。
【００４９】
たとえば、信号線Ｘ１について、データフロー上のソースＰＥはＤＬＶであり、デスティネーションＰＥはＲＡＭである。ソースＰＥ・デスティネーションＰＥファイル１０３を参照すると、第０列第０行には、ソースＰＥとしてＤＬＶがリストされ、かつ、デスティネーションＰＥとしてＲＡＭがリストされている。したがって、バスリソースリクエストマップファイル中、第０列第０ラインに対応するビットが「１」にセットされる。また、第０列第１行にも、ソースＰＥとしてＤＬＶがリストされ、かつ、デスティネーションＰＥとしてＲＡＭがリストされている。したがって、バスリソースリクエストマップファイル中、第０列第１ラインに対応するビットが「１」にセットされる。
【００５０】
バスリソースリクエストマップ１０１が出来上がると、マップ更新部１６は、以下に詳細に説明する複数のルールを用いて、バスリソースリクエストマップファイル１０１を更新し、また、その更新にともなって、信号線のバスへの割り当てを決定していく。まず、マップ更新部１６は、バスリソースリクエストマップ１０１を参照して、第１のルールを適用する（ステップ９０３）。第１のルールとは、バスリソースリクエストマップ中、ある信号線について、第０列〜第７列の全てのラインに関するビットが「０」である場合に、その信号線が配置不可能であることである。たとえば、図１３の例において、信号線Ｘ３について、全ての列のラインに関するビットが「０」となっている（符号１３０１参照）。これは、信号線Ｘ３を、実際のＬＳＩ中の何れかの列のラインに割り当てることが不可能であることを示している。
【００５１】
したがって、マップ更新部１６は、それぞれの信号線について、全ての列のラインに対応するビットが「０」であるか否かを判断し、何れかの信号線について、全てのビットが「０」であれば、ステップ９０４でイエス(Yes)と判断され、処理は終了する。処理の終了に際して、データフロー上のＰＥのＬＳＩ上のＰＥへの割り当て、および、データフロー上の信号線のＬＳＩ上のバスへの割り当てが不可能であることを示す情報を出力する。この情報は、たとえば、配置配線決定システム１０の表示装置（図示せず）の画面上に表示される。このように、配置配線が不可能であると判断された場合には、パーティションのコンフィグレーションのデータ自体の変更が必要となる。
【００５２】
ステップ９０４でノー(No)と判断された場合には、マップ更新部１６は、第２のルールを適用して、必要に応じて、バスリソースリクエストマップを更新する（ステップ９０５）。第２のルールとは、バスリソースリクエストマップ中、ある信号線について、列０〜７のラインに対応するビットが１つだけ「１」であるときには、その信号線は、ビットが「１」となったラインに割り当てるというものである。図１４に示すように、マップ更新部１６は、バスリソースリクエストマップ中、ある信号線についてのビットを参照して（ステップ１４０１）、「１」がセットされているビットが１つだけの場合には（ステップ１４０２でイエス(Yes)）、そのビットの値を更新不可能であることを示す情報を、当該ビットに付加する（ステップ１４０３）。この情報として、たとえば、各ビットに対応付けられた更新不可能を表すフラグ（更新不可能フラグ）を利用することができ、記憶装置中に設けられたフラグ領域において、該当するフラグを「１」にセットすればよい。
【００５３】
次いで、マップ更新部１６は、バスリソースリクエストマップを参照して、そのビットと、同一列で同一ラインのビットでその値が「１」であるものを探す（ステップ１４０４）。値が「１」であるビットが見出され（ステップ１４０５でイエス(Yes)）、かつ、そのビットについて、更新不可能フラグがセットされていない場合には（ステップ１４０６でノー(No)）、マップ更新部１６は、そのビットの値を「０」にする（ステップ１４０７）。
【００５４】
なお、ステップ１４０４でイエス(Yes)と判断され、かつ、そのビットについて更新不可能フラグがセットされている場合（ステップ１４０６でイエス(Yes)）には、１つのバスを複数の信号線が使用せざるを得ないという、現実に配線不可能な状態となるため、処理を終了して、パーティションのコンフィギュレーションデータ自体の作成に戻る。また、マップ更新部１６は更新後のバスリソースリクエストマップについて、第１のルールを適用して、それぞれの信号線について、全ての列のラインに対応するビットが「０」であるか否かを判断し（ステップ１４０８）、何れかの信号線について、全てのビットが「０」であれば（ステップ１４０９でイエス（Yes））、同様に現実に配線不可能な状態となるため、処理を終了して、パーティションのコンフィギュレーションデータ自体の作成に戻る。この場合にも、配線が不可能であることを、たとえば、表示装置の画面上に表示する。以下、配線が不可能であると判断された場合には、同様の処理が実行されるが、説明は省略する。マップ更新部１６は、ステップ１４０１〜ステップ１４０９の処理を、全ての信号線について実行する（ステップ１４１０、１４１１参照）。
【００５５】
図１５（ａ）に示す例において、信号線Ｙ４については、バスリソースリクエストマップにおいて、第３列第４ラインのビットのみが「１」となっている（符号１５０１参照）。したがって、信号線Ｙ４の第３列第４ラインには更新不可能フラグがセットされる。また、図１５（ｂ）に示すように、他の信号線について、バスリソースリクエストマップ中、同一列同一ラインで「１」となっているビットがあれば、このビットの値が「０」となる（符号１５０２参照）。
【００５６】
なお、バスリソースリクエストマップにおいて、たとえば、第ｎ列第ｍラインに沿ってビットの値を参照した場合に、１つの信号線についてのみ、値が「１」であったとする。この場合には、この信号線には、第ｎ列第ｍラインのバスを割り当てても良いことを意味している。
【００５７】
次に、マップ更新部１６は、第３のルールを適用して、バスリソースリクエストマップを更新する（ステップ９０６）。第３のルールにおいては、パーティションのコンフィグレーションデータに示されるそれぞれのＰＥについて、その入力の信号線に着目して、バスリソースリクエストマップ中、各信号線の何れかについて、第ｎ列のビットの値が全て「０」である場合には、その列にＰＥを配置できないと判断される。
【００５８】
より詳細には、図１６に示すように、マップ更新部１６は、あるＰＥに着目して、そのＰＥのＸ入力、Ｙ入力、ＣＸ入力およびＣＹ入力となる信号線について、バスリソースリクエストマップの部分を取得する（ステップ１６０１）。次いで、処理用のパラメータの初期化（ステップ１６０２）の後、マップ更新部は、取得したバスリソースリクエストマップの部分中、信号線の何れかについて、第ｎ列のビットがすべて「０」であるか否かを判断する（ステップ１６０３）。何れかの信号線について第ｎ列のビットの全てが「０」である場合には（ステップ１６０４でイエス(Yes)）、他の信号線についても、第ｎ列のビットを全て「０」にする（ステップ１６０５）。ここでも、更新不可能フラグが「１」であるようなビットが存在すれば（ステップ１６０７でイエス(Yes)）、配線が不可能な状態であるため、パーティションのコンフィギュレーションデータ自体の再度作成が必要となる。ステップ１６０４〜ステップ１６０６については、第０列から第７列の全てについて実行される（ステップ１６０７、１６０８参照）。
【００５９】
その後、マップ更新部１６は、再度第１のルールを適用して（ステップ１６０９）、全てのビットが「０」であるような信号線が存在するかどうかを判断する（ステップ１６１０）。ステップ１６０９でイエス(Yes)と判断された場合にも、配線が不可能な状態であるため、パーティションのコンフィギュレーションデータ自体の再度作成が必要となる。マップ更新部１６は、ステップ１６０１〜１６１０の処理を、すべてのＰＥについて実行する（ステップ１６１１、１６１２参照）。
【００６０】
たとえば、図１７（ａ）に示す例において、あるＰＥのＸ入力、Ｙ入力、ＣＸ入力およびＣＹ入力として、それぞれ、信号線Ｘ３、Ｙ２、ＣＸ６、および、ＣＹ５が与えられ、かつ、バスリソースリクエストマップの各信号線に関する部分が、図１７（ｂ）に示すようなものであったとする。この例では、キャリー入力ＣＸ６の第２列、および、Ｘ入力Ｘ３の第4列のビットが全て「０」である。したがって、図１７（ｃ）に示すように、バスリソースリクエストマップの部分において、第２列のビットおよび第４列のビットが「０」にされる。
【００６１】
次いで、配置配線処理部１８は、記憶装置１２に記憶されたパーティションのコンフィグレーションデータから、データフロー上のＰＥの情報を取得し、また、取得したＰＥの属性および機能を参照して、データフロー上のＰＥを、実際のＬＳＩのセグメント上の候補位置に配置する（つまり、データフロー上のＰＥを、当該候補位置のＬＳＩ上のＰＥに配置する）と仮定して、当該位置を示す情報（列番号および行番号）を記憶装置１２に一時的に記憶する（ステップ９０８）。たとえば、コンフィグレーションデータ中のデータフロー上のＰＥがＥＸＭであれば、当該ＥＸＭは、第１列ないし第５列の、第２行または第６行、或いは、第６列の第１行、第２行、第５行或いは第６行の何れかを候補位置とすることができる。本実施の形態においては、候補位置は、列番号の小さい順でかつ行番号が小さい順に決められる。ついで、マップ更新部１６は、第４のルールを適用して、必要に応じて、バスリソースリクエストマップを更新する（ステップ９０８）。
【００６２】
図１８および図１９は、第４のルールの適用処理をより詳細に示すフローチャートである。図１８に示すように、マップ更新部１６は、ＰＥの候補位置の列番号および行番号に基づいて、入力側の信号線が割り当てられるバスの列番号、および、出力側の信号線が割り当てられるバスのライン番号を特定する（ステップ１８０１）。
【００６３】
たとえば、図２０（ａ）に示すように、処理対象となったデータフロー上のＰＥが、ＥＸＭであり、かつ、そのＬＳＩ上の候補位置が、第１列第１行であると考える。この場合には、入力側の信号線が割り当てられるバスの列番号は「１（第１列）」であり、また、出力側の信号線が割り当てられるバスのライン番号は、「０または１（第０ラインおよび第１ライン）」となる。つまり、バスリソースリクエストマップにおいて、ＰＥに入力する信号線であるＸ２は、第１列の何れかのラインに限定される。また、ＰＥから出力する信号線であるＸ３は、ソースＰＥ・ディスティネーションＰＥから判断することにより、各列の第０ライン或いは第１ラインに限定される。図７、図８等を参照して説明したように、ＰＥについては、それぞれ、入力として接続可能なバスが位置する列が決定され、かつ、出力として接続可能なバスが位置するラインが決定される。したがって、第４のルールを適用する際にも、ＰＥの候補位置によって、入力する信号線の列と出力する信号線のラインが限定される。
【００６４】
そこで、マップ更新部１６は、バスリソースリクエストマップにおいて、ＰＥに入力する信号線に割り当て可能な列のビットを参照して、バスを割り当て可能なライン（つまり、ビットの値が「１」であるライン）を特定する（ステップ１８０２）。たとえば、上述したようにＥＸＭを第１列第１行に配置した場合の、入力する信号線であるＸ２についで、バスリソースリクエストマップ中、第１列の８つのラインの値は「０１００００００」である。したがって、Ｘ２については、第１ラインに対応するビットのみが「１」であるため、Ｘ２の信号線は、第１列第１ラインのバスに割り当てられる。
【００６５】
その一方、ある信号線について、バスリソースリクエストマップ中、ＰＥの配置された列について複数のビットの値が「１」である場合（たとえば、８つのラインの値が「１１００００００」である場合）には、第０ライン或いは第１ラインの何れかが選択される。複数のビットの値が「１」である場合には、マップ更新部１６は、選択したビット以外のビットを「０」とするように、バスリソースリクエストマップを更新する。
【００６６】
次いで、マップ更新部１６は、バスリソースリクエストマップを参照して、ＰＥに割り当て可能なバスの列番号に基づいて、入力する信号線が割り当てられる列以外の列のビットを「０」に変更するとともに（ステップ１８０３）、出力する信号線が割り当てられるライン以外のラインのビットを「０」に変更する（ステップ１８０４）。
【００６７】
図２０（ａ）の例について、バスリソースリクエストマップを参照すると、ＰＥに入力する信号線Ｘ２については、図２０（ｂ）に示すように、第１列を除く、第０列、第２列〜第７列のビット（符号２００１およびアンダーライン参照）が「０」にされる。また、ＰＥから出力する信号線Ｘ３については、それぞれの列において、第０ラインおよび第１ラインを除く、第２ライン〜第７ラインのビット（符号２００２およびアンダーライン参照）が「０」にされる。図２０（ａ）は、ステップ１８０３、１８０４において、必要な列およびラインのビットを「０」に変更した状態を示す図である。図２０（ａ）において、アンダーラインを引いたビットについて、値が「１」から「０」に変更される。
【００６８】
第４のルール適用処理において、値を「１」から「０」に変更すべきビットについて、更新不可能フラグが「１」である場合（ステップ１８０５でイエス(Yes)）には、配置配線処理部１８は、ＰＥの配置された列において、信号線として他のラインのバスを割り当て可能であるか否かを判断する。バスリソースリクエストマップの信号線を割り当てるべき列のビットにおいて、もともと複数のビットに「１」が存在していた場合には（ステップ１８０６でイエス(Yes)）、バスリソースリクエストマップにおいて、値を「１」に残しておくビットを変更して、ステップ１８０３に戻る。たとえば、もともと、バスリソースリクエストマップ中、入力側の信号線を割り当てるべき列において、８つのラインの値が「１１００００００」であり、第０ラインを選択して、第１ラインのビットの値を「０」に変更した上で、処理を進め、ステップ１８０５においてノー(No)と判断された場合には、第１ラインを「１」として、８つのラインの値を「０１００００００」と変更した上で、再度、同様の処理を施す。
【００６９】
また、入力側の信号線を割り当てる列において、他のビットについても処理を実行したが、他のビットのすべてについて更新不可能フラグが存在していた場合には、ステップ１８０６でイエス(Yes)と判断される。この場合には、ＰＥの候補位置を変更可能であれば（ステップ１８０７でイエス(Yes)）、配置配線処理部１８は、ＰＥの候補位置を変更して（ステップ１８０８）、再度、新たな候補位置に関して、信号線が割り当て可能なバス番号およびライン番号を特定して、それに基づいて、バスリソースリクエストマップを更新する。
【００７０】
また、ステップ１８０５でノー(No)と判断された場合には、図１９に示すように、マップ更新部１６は、第１のルールを適用して（ステップ１９０１）、全てのビットが「０」であるような信号線があるか否かを判断する（ステップ１９０２）。ステップ１９０２でイエス(Yes)と判断された場合には、ステップ１８０６と同様に、バスリソースリクエストマップ中、入力側の信号線を割り当てる列において、もともと「１」であるような他のビットが存在するか否かを判断する（ステップ１８０６）。ステップ１８０６でイエス(Yes)と判断された場合には、マップ更新部１６は、バスリソースリクエストマップを変更した上で、ステップ１８０３に戻る。
【００７１】
ステップ１８０６でノー(No)と判断された場合には、ステップ１８０７と同様に、ＰＥの候補位置を変更可能であれば（ステップ１９０４でイエス(Yes)）であれば、配置配線処理部１８は、ＰＥの候補位置を変更して（ステップ１８０８）、再度、新たな候補位置に関して、信号線が割り当て可能なバス番号およびライン番号を特定して、それに基づいて、バスリソースリクエストマップを更新する。たとえば、図２１（ｂ）に示すように、バスリソースリクエストマップの更新に伴って、信号線Ｘ４については、全ての列のバスのビットが「０」となってしまう（符号２１１１参照）。このような場合には、ＰＥを次の候補位置に移動させて、再度同様の処理を実行する。
【００７２】
ステップ１８０７においてノー(No)と判断されたとき、或いは、ステップ１９０４でノー(No)と判断されたときには、パーティションのコンフィグレーションデータを再度作成する必要があると判断される。
【００７３】
第１のルールの適用の結果、バスリソースリクエストマップにおいて、全てのビットが「０」となるような信号線が存在しなければ（ステップ１９０２でノー(No)）、配置配線処理部１８は、ＰＥの候補位置、および、バスリソースリクエストマップ中、ＰＥの入力側の信号線についてビットが「１」となっている位置（列およびライン）を、記憶装置１２中の配線情報／接続情報ファイル１０２に追加する（ステップ１９０５）。また、マップ更新部１６は、バスリソースリクエストマップ中、上記ＰＥの入力側の信号線について「１」となっているビットに更新不可能フラグを付加する（ステップ１９０６）。
【００７４】
さらに、マップ更新部１６は、バスリソースリクエストマップにおいて、他の信号線についても、１つのビットのみが「１」となっているものがあれば、そのビットに更新不可能フラグを付加する（ステップ１９０７）。データフローファイル中に、まだ位置が決められていないＰＥが存在すれば（ステップ１９０８）、ステップ９０９に戻る。このような処理を繰り返すことにより、ＰＥの位置（列および行）およびバスの位置（列およびライン）を決定することができる。
【００７５】
本実施の形態においては、ＰＥを候補位置に配置し、少なくともその入力側のバスを選択し、候補位置および入力側のバスの位置を記憶しておく。その後、バスリソースリクエストマップにおいて、ＰＥの位置からは使用される可能性の無いバスについて、ビットを「０」とした上で、配線不可能となる他の信号線が存在しなければ、ＰＥの候補位置および入力側のバスの位置を確定させて、これらの情報を配置情報／接続情報ファイルに追加する。このように、ＰＥごとに候補位置の決定や入力側のバスの選択、バスリソースリクエストマップの更新、配置不可能な他の信号線の有無の判断、位置の確定を繰り返すことにより、順次、ＰＥのＬＳＩ上の位置および信号線に対応するＬＳＩ上のバスの位置が、配置情報／接続情報ファイル１０２に追加されていく。
【００７６】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【００７７】
たとえば、前記実施の形態においては、ＬＳＩ上のＰＥは、その列の何れかのＰＥをソースＰＥとすることができ（つまり、同じ列のＰＥからの出力を入力とするようなせつぞくが可能であり）、また、同じライン或いは隣接する１つのラインのＰＥをデスティネーションＰＥとすることができる（つまり、同じラインあるいは隣接する１つのラインのＰＥに出力できるようなバスの接続が可能である）。しかしながら、このような構成に限定されることはなく、本発明は、ＬＳＩにおけるＰＥ間に他の接続の制限があった場合にも適用が可能である。
【図面の簡単な説明】
【００７８】
【図１】。図１は、本実施の形態にかかる配置配線決定システム１０の概略を示すブロックダイヤグラムである。
【図２】図２は、本実施の形態にかかるＬＳＩの６つのセグメントの例を示す図である。
【図３】図３は、本実施の形態にかかるＰＥの入出力を説明する図である。
【図４】図４は、本実施の形態にかかるＸデータバスおよびＹデータバスを模式的に示す図である。
【図５】図５は、本実施の形態にかかるＸキャリーバスおよびＹキャリーバスを模式的に示す図である。
【図６】図６は、本実施の形態にかかるＰＥにおけるバスの入出力の制限を説明する図である。
【図７】図７（ａ）、（ｃ）は、それぞれ、第６列第２ライン、および、第０列第０ラインの信号線について、ソースＰＥおよびデスティネーションＰＥとなり得るＰＥを説明する図である。
【図８】図８は、本実施の形態にかかるソースＰＥ・デスティネーションＰＥファイルのデータ構成の例を説明する図である。
【図９】図９は、本実施の形態にかかる配置配線決定システムにおける配置配線処理の概略を示すフローチャートである。
【図１０】図１０は、あるコンフィギュレーションデータを、データフローとして描いた図である。
【図１１】図１１（ａ）、（ｂ）は、それぞれ、図１０のデータフローの例において、信号線Ｘｎ、Ｙｎについてのバスリソースリクエストマップを示す図である。
【図１２】図１２は、本実施の形態にかかるバスリソースリクエストマップの作成処理の例を示すフローチャートである。
【図１３】図１３は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図１４】図１４は、本実施の形態にかかる第２のルール適用処理の例を示すフローチャートである。
【図１５】図１５（ａ）、（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図１６】図１６は、本実施の形態にかかる第３のルール適用処理の例を示すフローチャートである。
【図１７】図１７（ａ）は、データフローにおけるあるＰＥの入力を説明する図、図１７（ｂ）、（ｃ）は、バスリソースリクエストマップの該当部分を示す図である。
【図１８】図１８は、本実施の形態にかかる第４のルール適用処理の例を示すフローチャートである。
【図１９】図１８は、本実施の形態にかかる第４のルール適用処理の例を示すフローチャートである。
【図２０】図２０（ａ）は、本実施の形態にかかるあるＰＥのＸ入出力およびＹ入出力を示す図、図２０（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【図２１】図２１（ａ）、（ｂ）は、本実施の形態にかかるバスリソースリクエストマップの例を示す図である。
【符号の説明】
【００７９】
１０ 配置配線決定システム
１２ 記憶装置
１４ マップ作成部
１６ マップ更新部
１８ 配置配線処理部
１００ データフローファイル
１０１ バスリソースリクエストマップ
１０２ 配置情報／接続情報ファイル
１０３ ソースＰＥ・デスティネーションＰＥファイル
【特許請求の範囲】
【請求項１】
２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援する方法であって、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を備えたことを特徴とする方法。
【請求項２】
前記バスリソースリクエストマップを生成するステップが、前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記バスリソースリクエストマップを作成するステップが、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造であることを特徴とする請求項１ないし３の何れか一項に記載の方法。
【請求項５】
さらに、前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを備えたことを特徴とする請求項１ないし４の何れか一項に記載の方法。
【請求項６】
請求項１ないし４の何れか一項に記載のバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定する方法であって、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を備えたことを特徴とする方法。
【請求項７】
前記バスリソースを更新するステップが、前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップを備え、前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力することを特徴とする請求項６または７に記載の方法。
【請求項９】
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含むことを特徴とする請求項６ないし８の何れか一項に記載の方法。
【請求項１０】
２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援するために、コンピュータにより読み出し可能なプログラムであって、
前記コンピュータに、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を実行させることを特徴とするプログラム。
【請求項１１】
前記バスリソースリクエストマップを生成するステップにおいて、前記コンピュータに、
前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を実行させることを特徴とする請求項１０に記載のプログラム。
【請求項１２】
前記バスリソースリクエストマップを作成するステップにおいて、前記コンピュータに、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造であることを特徴とする請求項１０ないし１２の何れか一項に記載のプログラム。
【請求項１４】
さらに、前記コンピュータに、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを実行させることを特徴とする請求項１０ないし１３の何れか一項に記載の方法。
【請求項１５】
請求項１０ないし１３の何れか一項に記載のバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定するために、コンピュータにより読み出し可能なプログラムであって、前記コンピュータに、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を実行させることを特徴とするプログラム。
【請求項１６】
前記バスリソースを更新するステップにおいて、前記コンピュータに、
前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させることを特徴とする請求項１５に記載のプログラム。
【請求項１７】
前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップと、
前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力するステップと、を実行させることを特徴とする請求項１４または１５に記載のプログラム。
【請求項１８】
前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させることを特徴とする請求項１４ないし１７の何れか一項に記載のプログラム。
【請求項１】
２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援する方法であって、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を備えたことを特徴とする方法。
【請求項２】
前記バスリソースリクエストマップを生成するステップが、前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記バスリソースリクエストマップを作成するステップが、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造であることを特徴とする請求項１ないし３の何れか一項に記載の方法。
【請求項５】
さらに、前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを備えたことを特徴とする請求項１ないし４の何れか一項に記載の方法。
【請求項６】
請求項１ないし４の何れか一項に記載のバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定する方法であって、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を備えたことを特徴とする方法。
【請求項７】
前記バスリソースを更新するステップが、前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップを備え、前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力することを特徴とする請求項６または７に記載の方法。
【請求項９】
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを含むことを特徴とする請求項６ないし８の何れか一項に記載の方法。
【請求項１０】
２次元アレイ構造の処理エレメント間の接続を変更することで、そのコンフィギュレーションを変更可能な再構成可能ＬＳＩであって、当該ＬＳＩ上のそれぞれの処理エレメントの入力と接続可能なバス、および、当該処理エレメントの出力と接続可能なバスが定められているＬＳＩにおいて、当該処理エレメントの配置および処理エレメント間の配線の決定を支援するために、コンピュータにより読み出し可能なプログラムであって、
前記コンピュータに、
記憶装置に記憶された、データフロー上の処理エレメントの属性、および、特定の属性を有する複数の処理エレメント間を接続する信号線の情報を含む、データフローファイルを読み出すステップと、
前記データフローファイル中の信号線の情報を参照して、信号線ごとに、当該信号線に出力するデータフロー上の処理エレメントであるソース処理エレメントと、当該信号線を入力するデータフロー上の処理エレメントであるデスティネーション処理エレメントを特定するステップと、
前記信号線ごとに、特定されたソース処理エレメントおよびデスティネーション処理エレメントに対応する、ＬＳＩ上の処理エレメントのそれぞれに接続可能なバスについて、当該信号線についてのバスとして使用可能であることを示す情報を含むバスリソースリクエストマップを、前記記憶装置中に生成するステップと、を実行させることを特徴とするプログラム。
【請求項１１】
前記バスリソースリクエストマップを生成するステップにおいて、前記コンピュータに、
前記信号線ごとに、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記ソース処理エレメントと同一の属性を有するＬＳＩ上の処理エレメントの出力と接続可能であるかを判断するステップと、
前記ＬＳＩ上の処理エレメントが配置される位置に、前記デスティネーションエレメントと同一の属性を有するＬＳＩ上の処理エレメントの入力と接続可能であるかを判断するステップと、を実行させることを特徴とする請求項１０に記載のプログラム。
【請求項１２】
前記バスリソースリクエストマップを作成するステップにおいて、前記コンピュータに、
前記記憶装置に記憶された、前記ＬＳＩ上の処理エレメントが配置される位置のそれぞれについて、その出力と接続可能な他の位置の処理エレメントの属性、および、その入力と接続可能な他の位置の処理エレメントの属性を含むソース処理エレメント・デスティネーション処理エレメントファイルを参照するステップを実行させることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記ＬＳＩは、複数の処理エレメントがマトリクス状に配置された構造であり、前記ＬＳＩ上の処理エレメントを接続するバスは、ある列および行に位置する処理エレメントの入力が、特定の１以上の列或いは行の何れかに一方に位置する処理エレメントと接続可能であり、かつ、ある列および行に位置する処理エレメントの出力が、特定の１以上の列或いは行の何れか他方に位置する処理エレメントと接続可能であるような構造であることを特徴とする請求項１０ないし１２の何れか一項に記載のプログラム。
【請求項１４】
さらに、前記コンピュータに、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントに、前記ＬＳＩ上の処理エレメントを割り当てるとともに、前記データフロー上の信号線に、前記ＬＳＩ上のバスを割り当てて、前記データフロー上の処理エレメントに割り当てられた前記ＬＳＩ上の処理エレメントの位置、および、前記データフロー上の信号線に割り当てられたバスの位置を、前記記憶装置に記憶するステップを実行させることを特徴とする請求項１０ないし１３の何れか一項に記載の方法。
【請求項１５】
請求項１０ないし１３の何れか一項に記載のバスリソースリクエストマップを使用して、処理エレメントの配置および処理エレメント間の配線を決定するために、コンピュータにより読み出し可能なプログラムであって、前記コンピュータに、
前記データフロー上の処理エレメントを、前記ＬＳＩ上の処理エレメントの候補位置に配置し、当該候補位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとソース処理エレメントとを接続する第１の信号線について、前記ＬＳＩ上の処理エレメントの入力と接続可能な１以上の第１のバスを特定し、特定された第１のバスのなかから所定の１つを選択して、当該バスの位置の情報を記憶装置に記憶するステップと、
前記バスリソースリクエストマップを参照して、前記データフロー上の処理エレメントとデスティネーション処理エレメントを接続する第２の信号線について、前記候補位置において、前記ＬＳＩ上の処理エレメントの出力と接続可能な１以上の第２のバスを特定するステップと、
前記バスリソースリクエストマップにおいて、前記第１の信号線について、前記第１のバスから選択された１つのバスを除き、接続可能であることを示す情報を削除するとともに、前記第２の信号線について、前記第２のバスを除き、接続可能であることを示す情報を削除するように、前記バスリソースリクエストマップを更新するステップと、を実行させることを特徴とするプログラム。
【請求項１６】
前記バスリソースを更新するステップにおいて、前記コンピュータに、
前記第１の信号線について、前記選択されたバスにおいて、接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させることを特徴とする請求項１５に記載のプログラム。
【請求項１７】
前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、全てのバスにおいて接続可能であることを示す情報が存在しないことを判断するステップと、
前記情報が存在しないと判断した場合に、データフロー上の処理エレメントおよび信号線を、ＬＳＩ上の処理エレメントおよびバスに割り当て不可能であることを示す情報を出力するステップと、を実行させることを特徴とする請求項１４または１５に記載のプログラム。
【請求項１８】
前記コンピュータに、
前記バスリソースリクエストマップにおいて、何れかの信号線について、１つのバスにおいてのみ接続可能であることを示す情報が存在する場合に、当該バスの接続可能であることを示す情報の削除を禁止する更新不可能フラグを付加するステップを実行させることを特徴とする請求項１４ないし１７の何れか一項に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２００７−１４０７３２（Ｐ２００７−１４０７３２Ａ）
【公開日】平成１９年６月７日（２００７．６．７）
【国際特許分類】
【出願番号】特願２００５−３３１２９８（Ｐ２００５−３３１２９８）
【出願日】平成１７年１１月１６日（２００５．１１．１６）
【出願人】（５００２３８７８９）アイピーフレックス株式会社 (15)
【Ｆターム（参考）】
【公開日】平成１９年６月７日（２００７．６．７）
【国際特許分類】
【出願日】平成１７年１１月１６日（２００５．１１．１６）
【出願人】（５００２３８７８９）アイピーフレックス株式会社 (15)
【Ｆターム（参考）】
[ Back to top ]