(57)【要約】  セグメント化された再構成可能なデバイスに回路デザインを実装するためのコンフィグレーションデータを生成するシステムを提供する。配置配線支援システム（３０）は、それぞれのセグメントに含まれるＰＥｓのデータと、第１レベルおよび第２レベルのルーティングマトリクスのデータとを含むハードウエア情報（８９）を格納するためのデータベース（３１）と、回路デザインをＰＥｓにマッピングする装置（３３）を含む。このマッピング装置（３３）は、ハードウエア情報（８９）に基づき、コストファンクションを最小化する反復アルゴリズムを実行することにより回路デザインをＰＥｓにマッピングする。コストファンクションは、セグメント間を接続する第２レベルのルーティングマトリクス（２２）の使用を最小にする項目を含む。
2008026731.tif 000002
【特許請求の範囲】
【請求項１】
再構成可能なデバイスを再構成するためのコンフィグレーションデータを生成するシステムであって、
前記デバイスは、複数の処理エレメントと、それら複数の処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
当該システムは、
前記それぞれのグループに含まれる前記複数の処理エレメントのディフィニションデータと、前記ルーティングマトリクスのディフィニションデータとを含むハードウエア情報を格納するためのデータベースと、
前記コンフィグレーションデータにより前記デバイスに実装される回路デザインを前記複数の処理エレメントにマッピングする装置とを有し、
前記マッピングする装置は、前記ハードウエア情報に基づき、コストファンクションを最小化する反復アルゴリズムを実行することにより前記回路デザインを前記複数の処理エレメントにマッピングし、前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含む、システム。
【請求項２】
請求項１において、前記回路デザインは、前記デバイスに実装する機能が、前記複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、前記複数の機能ブロックの接続とにより示されたデータフローグラムを含み、
前記マッピングする装置は、前記複数の機能ブロックを、前記複数のグループに区分けされた前記複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てる機能ユニットと、
前記反復アルゴリズムを用いて、前記複数の処理エレメントに対する前記複数の機能ブロックの割り当てを変える機能ユニットとを含み、
前記割り当てを変える機能ユニットは、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントを接続するルートに基づき前記コストファンクションの値を求める機能を含む、システム。
【請求項３】
請求項２において、前記マッピングする装置は、前記データフローグラムを解析して前記複数の機能ブロックに対するデータの入力および／または出力のタイミングをメモリに保存する機能ユニットと、
前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントの接続を、前記第２レベルのルーティングマトリクスを介するための遅延を含めて解析し、前記メモリに保存された前記タイミングを実現するための遅延を前記複数の処理エレメントのいずれかに割り当てる機能ユニットとをさらに含む、システム。
【請求項４】
請求項２において、前記複数の機能ブロックは、複数種類の機能ブロックを含み、
前記複数の処理エレメントは、前記複数種類の機能ブロックの内の限られた種類の機能ブロックに対応するようにそれぞれ構成可能な複数種類の処理エレメントを含み、
前記暫定的に割り当てる機能ユニットは、前記複数種類の処理エレメントの内、前記複数の処理エレメントに含まれる数の少ない種類の処理エレメントに対して優先的に前記複数の機能ブロックを割り当て、その際に、第１の種類の複数の処理エレメントに割り当て可能な前記複数の機能ブロックを前記第１の種類の複数の処理エレメントのいずれかにランダムに割り当てる機能を含む、システム。
【請求項５】
請求項４において、前記暫定的に割り当てる機能ユニットは、前記第１の種類の複数の処理エレメントのいずれかにランダムに割り当てる前に、前記複数の機能ブロックに含まれる第１の特定の機能ブロックを、前記複数のグループの内の特定のグループの複数の処理エレメントのいずれかにランダムに割り当てる機能をさらに含み、
前記割り当てを変える機能ユニットは、前記第１の特定の機能ブロックを、前記特定のグループの前記複数の処理エレメントのいずれかに割り当てる機能をさらに含む、システム。
【請求項６】
請求項５において、前記暫定的に割り当てる機能ユニットは、前記特定のグループの前記複数の処理エレメントのいずれかにランダムに割り当てる前に、前記複数の機能ブロックに含まれる第２の特定の機能ブロックを、前記複数の処理エレメントの特定の処理エレメントに割り当てる機能をさらに含み、
前記割り当てを変える機能ユニットは、前記第２の特定の機能ブロックの割り当ては変えない機能をさらに含む、システム。
【請求項７】
再構成可能なデバイスを再構成するためのコンフィグレーションデータにより前記デバイスに実装される回路デザインを前記デバイスの複数の処理エレメントにマッピングする装置であって、
前記デバイスは、前記複数の処理エレメントと、それら複数の処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
当該マッピングする装置は、前記それぞれのグループに含まれる前記複数の処理エレメントのディフィニションデータと、前記ルーティングマトリクスのディフィニションデータとを含むハードウエア情報に基づき、コストファンクションを最小化する反復アルゴリズムを実行することにより前記回路デザインを前記複数の処理エレメントにマッピングし、前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含む、マッピングする装置。
【請求項８】
再構成可能なデバイスを再構成するためのコンフィグレーションデータを生成する方法であって、
前記デバイスは、複数の処理エレメントと、それらの処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
当該方法は、
前記それぞれのグループに含まれる前記複数の処理エレメントのディフィニションデータと、前記ルーティングマトリクスのディフィニションデータとを含むハードウエア情報をコンピュータによりアクセス可能なデータベースに用意することと、
前記コンフィグレーションデータにより前記デバイスに実装される回路デザインを、コストファンクションを最小化する反復アルゴリズムを前記コンピュータにより実行することにより前記複数の処理エレメントにマッピングすることとを有し、
前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含む、方法。
【請求項９】
請求項８において、前記回路デザインは、前記デバイスに実装する機能が、前記複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、前記複数の機能ブロックの接続とにより示されたデータフローグラムを含み、
前記マッピングする工程は、前記複数の機能ブロックを、前記複数のグループに区分けされた前記複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、
前記反復アルゴリズムを用いて、前記複数の処理エレメントに対する前記複数の機能ブロックの割り当てを変えることとを含み、
前記割り当てを変える工程は、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントを接続するルートに基づき前記コストファンクションの値を求めることを含む、方法。
【請求項１０】
請求項９において、前記マッピングする工程は、前記データフローグラムを解析して前記複数の機能ブロックに対するデータの入力および／または出力のタイミングをメモリに保存することと、
前記割り当てを変える工程の後に、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントの接続を、前記第２レベルのルーティングマトリクスを介するための遅延を含めて解析し、前記メモリに保存された前記タイミングを実現するための遅延を前記複数の処理エレメントのいずれかに割り当てることとをさらに含む、方法。
【請求項１１】
請求項９において、前記複数の機能ブロックは、複数種類の機能ブロックを含み、
前記複数の処理エレメントは、前記複数種類の機能ブロックの内の限られた種類の機能ブロックに対応するようにそれぞれ構成可能な複数種類の処理エレメントを含み、
前記暫定的に割り当てる工程は、前記複数種類の処理エレメントの内、前記複数の処理エレメントに含まれる数の少ない種類の処理エレメントに対して優先的に前記複数の機能ブロックを割り当て、その際に、第１の種類の複数の処理エレメントに割り当て可能な前記複数の機能ブロックを前記第１の種類の複数の処理エレメントのいずれかにランダムに割り当てることをさらに含む、方法。
【請求項１２】
請求項１１において、前記暫定的に割り当てる工程は、前記第１の種類の複数の処理エレメントのいずれかにランダムに割り当てる工程に優先して、前記複数の機能ブロックに含まれる第１の特定の機能ブロックを、前記複数のグループの内の特定のグループの複数の処理エレメントのいずれかにランダムに割り当てることをさらに含み、
前記割り当てを変える工程は、前記第１の特定の機能ブロックを、前記特定のグループの前記複数の処理エレメントのいずれかに割り当てることをさらに含む、方法。
【請求項１３】
請求項１２において、前記暫定的に割り当てる工程は、前記特定のグループの前記複数の処理エレメントのいずれかにランダムに割り当てる工程に優先して、前記複数の機能ブロックに含まれる第２の特定の機能ブロックを、前記複数の処理エレメントの特定の処理エレメントに割り当てることをさらに含み、
前記割り当てを変える工程は、前記第２の特定の機能ブロックの割り当ては変えないことをさらに含む、方法。
【請求項１４】
再構成可能なデバイスに回路デザインをマッピングすることを含む方法であって、
前記デバイスは、複数の処理エレメントと、それらの処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
前記回路デザインは、前記デバイスに実装する機能が、前記複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、前記複数の機能ブロックの接続とにより示されたデータフローグラムを含み、
前記マッピングすることは、
前記複数の機能ブロックを、前記複数のグループに区分けされた前記複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、
コストファンクションを最小化する反復アルゴリズムを用いて、前記複数の処理エレメントに対する前記複数の機能ブロックの割り当てを変えることとを含み、
前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含み、前記割り当てを変えることは、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントの接続から前記コストファンクションの値を求めることを含む、方法。
【請求項１５】
コンピュータにより、再構成可能なデバイスを構成するためのコンフィグレーションデータを生成するためのプログラムであって、
前記デバイスは、複数の処理エレメントと、それらの処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
当該プログラムは、
前記それぞれのグループに含まれる前記複数の処理エレメントのディフィニションデータと、前記ルーティングマトリクスのディフィニションデータとを含むハードウエア情報を前記コンピュータによりアクセス可能なデータベースに用意することと、
前記コンフィグレーションデータにより前記デバイスに実装される回路デザインを、前記コンピュータにより、コストファンクションを最小化する反復アルゴリズムを実行することにより前記複数の処理エレメントにマッピングすることとを含み、
前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含む、プログラム。
【請求項１６】
請求項１５において、前記回路デザインは、前記デバイスに実装する機能が、前記複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、前記複数の機能ブロックの接続とにより示されたデータフローグラムを含み、
前記マッピングすることは、前記複数の機能ブロックを、前記複数のグループに区分けされた前記複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、
前記反復アルゴリズムを用いて、前記複数の処理エレメントに対する前記複数の機能ブロックの割り当てを変え、その際に、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントを接続するルートに基づき前記コストファンクションの値を求めることとを含む、プログラム。
【請求項１７】
請求項１６において、
前記マッピングすることは、さらに、前記データフローグラムを解析して前記複数の機能ブロックに対するデータの入力および／または出力のタイミングを前記コンピュータのメモリに格納することと、
前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントの接続を、前記第２レベルのルーティングマトリクスを介するための遅延を含めて解析し、前記メモリに格納された前記タイミングを実現するための遅延を前記複数の処理エレメントのいずれかに割り当てることとをさらに含む、プログラム。
【請求項１８】
コンピュータにより、再構成可能なデバイスに回路デザインをマッピングするためのプログラムであって、
前記デバイスは、複数の処理エレメントと、それらの処理エレメントを接続するためのルーティングマトリクスとを有し、前記複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成され、
前記複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、前記ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、前記第１の遅延とは異なる遅延で接続され、
前記回路デザインは、前記デバイスに実装する機能が、前記複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、前記複数の機能ブロックの接続とにより示されたデータフローグラムを含み、
当該プログラムは、
前記複数の機能ブロックを、前記複数のグループに区分けされた前記複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、
コストファンクションを最小化する反復アルゴリズムを用いて、前記複数の処理エレメントに対する前記複数の機能ブロックの割り当てを変えることとを含み、
前記コストファンクションは、前記第２レベルのルーティングマトリクスの使用を最小にする項目を含み、前記割り当てを変えることは、前記複数の機能ブロックがそれぞれ割り当てられた前記複数の処理エレメントの接続から前記コストファンクションの値を求めることを含む、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路を再構成可能なデバイスに所望の回路デザインを実装するための方法およびシステムに関するものである。
【背景技術】
【０００２】
日本国特許公開公報２０００−２００２９８号には、部品リストとネットリストからなる回路データとその配置データをデータベースに記憶し、新規回路データとデータベース中の回路データとをノードとエッジとからなるグラフにそれぞれ変換し、変換されたグラフ間のマッチングを行い、マッチング度の高い回路データを検索し、検索した回路データの対となる配置データに沿って、新規回路データを配置することを特徴とする自動配置方法が記述されている。また、検索した回路データの対となる配置データに沿って新規回路を配置する際に、シミュレーテッドアニーリング法、ニューラルネット、平均場アニーリングまたは遺伝的アルゴリズムを用いることが記述されている。また、検索した回路データの対となる配置データに沿って新規回路データを配置する際に、回路データの部品と新規回路データの部品とを対応づけ、少なくともその対応関係と配置データを用いて新規回路データに対しての配置を評価するコスト関数を生成し、コスト関数を最小化することが記述されている。また、コスト関数の最小化を行なう際に、少なくとも初期配置を生成し、部品または部品群を移動または回転させることにより配置を更新することが記述されている。【０００３】
米国特許公報６，０９９，５８３号には、ロジックオペレーションをプログラマブルロジックデバイス（ＰＬＤ）に実装するためにＰＬＤをプログラミングする方法が記述されている。ＰＬＤは、複数の構成可能な論理ブロック（ＣＬＢ）を含み、ロジックオペレーションは複数のコアにより定義され、それぞれのコアは、複数の相互に関連のある論理部分を含むことが記述されている。この方法は、さらに、複数のＣＬＢサイトを含むコンフィグラブルデータテーブルを設けることが記述されている。それぞれのＣＬＢサイトは、関連する１または複数のＣＬＢに対応するメモリロケーションを含むものである。この方法は、さらに、複数のコアのそれぞれ１つのリザーブされた論理部分のみをコンフィグラブルデータテーブルに配置して、コンフィグラブルデータテーブルに第１のプレイスメントアレンジメントを形成し、複数のコアそれぞれの他のノンリザーブの論理部分は第１のプレイスメントアレンジメントから除かれ、第１のコアの第１のリザーブされた論理部分が第１のＣＬＢサイトに割り当てられ、第１のコアの第１のリザーブされた論理部分を第１のＣＬＢサイトから第２のＣＬＢサイトに移動させることにより第１のプレイスメントアレンジメントをアニーリングし、コンフィグラブルデータテーブルに第２のプレイスメントアレンジメントを作ることが記述されている。この方法は、さらに、複数のコアそれぞれの１または複数のノンリザーブの論理部分をコンフィブラブルデータテーブルに配置し、第１のコアの第１のノンリザーブ部分を第３のＣＬＢサイトに割り当てることが記述されている。【０００４】
米国特許公報６，８１３，７５４号には、ＰＬＤの複数のＣＬＢに複数の回路要素をコンピュータを用いてマッピングする方法が記述されている。この公報では、回路デザインの複数の回路要素を１つのＣＬＢに対応するブロックにそれぞれパッキングし、そのブロックをＰＬＤのＣＬＢに割り当てることによりマッピングを生成すること、その際に、シミュレーテッドアニーリングを用いることが記述されている。さらに、そのマッピングに対応するＰＬＤ内のクリティカルパスを選択し、そのクリティカルパスはＰＬＤの第１のＣＬＢの第１のノードを含み、この第１のＣＬＢは１または複数の他のノードを含み、他のノードの割り当てを変えずに、第１のノードを現在のロケーションから他のロケーションに割り当て、それにより回路性能を変更することが記述されている。第１のノードはターミナルノードであり、他のロケーションは現在のロケーションの近傍であって、コネクションノードを中心としたサークルであり、ターミナルノードとコネクションノードの距離に対応する半径をもったものである。【０００５】
ＦＰＧＡ（フィールドプログラマブルゲートアレイ）などのＰＬＤを含む再構成可能なデバイスにおいて、多数の部品からなる回路の配置を決定する際に、デバイスに実装可能な全ての接続を検討するためには膨大な時間を要する。分子の加熱時のかく乱による状態遷移の原理を利用したシミュレーテッドアニーリング法を含む反復アルゴリズムを用いた自動配置方法は、ランダム要因を利用して短時間に最適配置あるいは最適配置に近い解を得ることができる。デバイスの配置配線を検討する際に、デバイスに実装される回路の性能を改善することも重要である。例えば、タイミング収束および／またはクリティカルパスを改善することが重要である。自動配置方法により選択された配置を、回路性能を改善するために大幅に変更することが必要になると自動配置のメリットは薄れる。一方、ランダム要因を利用して選択された仮配置のそれぞれに対してクリティカルパスを選択してその改善を検討していたのでは、自動配置に要する時間が増加する。
【発明の開示】
【０００６】
本発明の一態様は、再構成可能なデバイスに回路デザインを実装するためのコンフィグレーションデータを生成する方法である。デバイスは、複数の処理エレメントと、それらの処理エレメントを接続するためのルーティングマトリクスとを有し、複数の処理エレメントのそれぞれの処理エレメントの機能を変更すること、および／または、前記ルーティングマトリクスの少なくとも一部の接続を変更すること、により再構成される。デバイスにおいて、複数の処理エレメントは複数のグループに区分けされ、それぞれのグループに含まれる複数の処理エレメントは、ルーティングマトリクスに含まれる第１レベルのルーティングマトリクスにより第１の遅延の範囲内で接続され、異なるグループに含まれる複数の処理エレメントは、ルーティングマトリクスに含まれる第２レベルのルーティングマトリクスを介することにより、第１の遅延とは異なる遅延で接続される。
【０００７】
コンフィグレーションデータを生成する方法は、それぞれのグループに含まれる複数の処理エレメントのディフィニションデータと、ルーティングマトリクスのディフィニションデータとを含むハードウエア情報をコンピュータによりアクセス可能なデータベースに用意することと、コンフィグレーションデータにより上記デバイスに実装される回路デザインを、コストファンクションを最小化する反復アルゴリズムをコンピュータにより実行することにより複数の処理エレメントにマッピングすることとを含む。コストファンクションは、第２レベルのルーティングマトリクスの使用を最小にする項目（項）を含む。第２レベルのルーティングマトリクスを介して接続される処理エレメントの間の信号の遅延は、第１レベルのルーティングマトリクスのみにより接続される処理エレメントの間の信号の遅延（第１の遅延）より大きくなる。この方法では、第２レベルのルーティングマトリクスの使用を少なくする割り当て（配置）が選択される。したがって、反復アルゴリズムにより、回路デザインをデバイスにマッピングする際に処理エレメントの間の遅延が小さくなる割り当て選択され、回路性能を改善できる。反復アルゴリズムには、シミュレーテッドアニーリング法、平均場アニーリングまたは遺伝的アルゴリズムが含まれる。
【０００８】
回路デザインは、デバイスに実装する機能が、複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、複数の機能ブロックの接続とにより示されたデータフローグラムを含むことが望ましい。マッピングする工程は、複数の機能ブロックを、複数のグループに区分けされた複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、反復アルゴリズムを用いて、複数の処理エレメントに対する複数の機能ブロックの割り当てを変えることとを含むことが望ましい。割り当てを変える工程は、複数の機能ブロックがそれぞれ割り当てられた複数の処理エレメントを接続するルートに基づきコストファンクションの値を求めることを含む。
【０００９】
マッピングする工程は、データフローグラムを解析して複数の機能ブロックに対するデータの入力および／または出力のタイミングをメモリに保存することと、割り当てを変える工程の後に、複数の機能ブロックがそれぞれ割り当てられた複数の処理エレメントの接続を、第２レベルのルーティングマトリクスを介するための遅延を含めて解析し、メモリに保存されたタイミングを実現するための遅延を複数の処理エレメントのいずれかに割り当てることとを含むことが望ましい。
【００１０】
シミュレーテッドアニーリング法を含む反復アルゴリズムにより複数の処理エレメントに対する複数の機能ブロックの割り当てを変える処理の間は、コストファンクションを最小化するための割り当て（マッピング、配置）を選択することにより、性能の高いマッピングが選択され、クリティカルパスを求めたり、タイミングを検証する必要はない。グループに含まれる複数の処理エレメントは、第１レベルのルーティングマトリクスにより第１の遅延、例えば１サイクルの範囲内で接続されるので、タイミングは担保され、クリティカルパスの改善は不要である。異なるグループに含まれる複数の処理エレメントの接続は、コストファンクションを最小化することにより最小化される。このため、割り当てを変える工程の後に第２レベルのルーティングマトリクスを含めたタイミングを検証することによりマッピングの計算に要する時間を短縮できる。
【００１１】
データフローグラムを構成する複数の機能ブロックは、複数種類の機能ブロックを含む。デバイスは、それら複数種類の機能ブロックの全てに対応するように構成可能な処理エレメントを含むものであっても良い。デバイスの他の例は、複数の処理エレメントが、複数種類の機能ブロックの内の限られた種類の機能ブロックに対応するようにそれぞれ構成可能な複数種類の処理エレメントを含むものである。このようなデバイスにマッピングする際は、暫定的に割り当てる工程は、複数種類の処理エレメントの内、複数の処理エレメントに含まれる数の少ない種類の処理エレメントに対して優先的に複数の機能ブロックを割り当て、その際に、ある種類（第１の種類）の複数の処理エレメントに割り当て可能な複数の機能ブロックを、その種類の複数の処理エレメントのいずれかにランダムに割り当てることを含むことがさらに望ましい。ランダムに割り当てることは、乱数を発生し、その乱数に従い、第１の種類の複数の処理エレメントに割り当て可能な複数の機能ブロックを、第１の種類の複数の処理エレメントのいずれかに割り当てることを含む。マッピングの初期の、暫定的に割り当てる工程において、数の少ない種類の処理エレメントに対する割り当てを優先することにより、処理エレメントの利用効率を向上できる。このため、必要とする処理エレメントの数の多い回路デザインを再構成可能なデバイスにマッピングするための情報を生成できる。また、複数の回路デザインを、再構成可能なデバイスに同時期にマッピングするための情報を生成できる。
【００１２】
暫定的に割り当てる工程は、ある種類の複数の処理エレメントのいずれかにランダムに割り当てる工程に優先して、複数の機能ブロックに含まれる第１の特定の機能ブロックを、複数のグループの内の特定のグループの複数の処理エレメントのいずれかにランダムに割り当てることをさらに含むことが望ましい。割り当てを変える工程は、第１の特定の機能ブロックを、特定のグループの複数の処理エレメントのいずれかに割り当てることをさらに含むことが望ましい。
【００１３】
暫定的に割り当てる工程は、特定のグループの複数の処理エレメントのいずれかにランダムに割り当てる工程に優先して、複数の機能ブロックに含まれる第２の特定の機能ブロックを、複数の処理エレメントの特定の処理エレメントに割り当てることをさらに含むことが望ましい。割り当てを変える工程は、第２の特定の機能ブロックの割り当ては変えられずフィックスすることをさらに含むことが望ましい。
【００１４】
本発明の異なる態様の１つは、再構成可能なデバイスに回路デザインをマッピングすることを含む方法である。回路デザインは、デバイスに実装する機能が、複数の処理エレメントのいずれかにそれぞれ実装できる複数の機能ブロックと、複数の機能ブロックの接続とにより示されたデータフローグラムを含む。マッピングする工程は、複数の機能ブロックを、複数のグループに区分けされた複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てることと、コストファンクションを最小化する反復アルゴリズムを用いて、複数の処理エレメントに対する複数の機能ブロックの割り当てを変えることとを含む。コストファンクションは、第２レベルのルーティングマトリクスの使用を最小にする項目を含む。また、この割り当てを変える工程は、複数の機能ブロックがそれぞれ割り当てられた複数の処理エレメントの接続からコストファンクションの値を求めることを含む。
【００１５】
本発明のさらに異なる態様の１つは、再構成可能なデバイスを再構成するためのコンフィグレーションデータを生成するシステムである。このシステムは、それぞれのグループに含まれる複数の処理エレメントのディフィニションデータと、ルーティングマトリクスのディフィニションデータとを含むハードウエア情報を格納するためのデータベースを含む。さらに、このシステムは、コンフィグレーションデータによりデバイスに実装される回路デザインを複数の処理エレメントにマッピングする装置を含む。このマッピングする装置は、ハードウエア情報に基づき、コストファンクションを最小化する反復アルゴリズムを実行することにより回路デザインを複数の処理エレメントにマッピングする。コストファンクションは、第２レベルのルーティングマトリクスの使用を最小にする項目（項）を含むものである。
【００１６】
さらに、上述したデータフローグラムに対応し、マッピングする装置（マッピング装置）は、複数の機能ブロックを、複数のグループに区分けされた複数の処理エレメントのいずれかにそれぞれ暫定的に割り当てる機能ユニットと、反復アルゴリズムを用いて、複数の処理エレメントに対する複数の機能ブロックの割り当てを変える機能ユニットとを含むことが望ましい。割り当てを変える機能ユニットは、複数の機能ブロックがそれぞれ割り当てられた複数の処理エレメントの接続からコストファンクションの値を求めることを含む。
【００１７】
また、マッピングする装置は、データフローグラムを解析して複数の機能ブロックに対するデータの入力および／または出力のタイミングをメモリに保存する機能ユニットと、複数の機能ブロックがそれぞれ割り当てられた複数の処理エレメントの接続を、第２レベルのルーティングマトリクスを介するための遅延を含めて解析し、メモリに保存されたタイミングを実現するための遅延を複数の処理エレメントのいずれかに割り当てる機能ユニットとをさらに有することが望ましい。
【００１８】
本発明のさらに異なる態様の１つは、再構成可能なデバイスを再構成するためのコンフィグレーションデータにより、再構成可能なデバイスに実装される回路デザインを、再構成可能なデバイスの複数の処理エレメントにマッピングする装置である。
【００１９】
本発明のさらに異なる態様の１つは、コンピュータにより、再構成可能なデバイスを再構成するためのコンフィグレーションデータを生成するためのプログラムである。このプログラムは、それぞれのグループに含まれる複数の処理エレメントのディフィニションデータと、ルーティングマトリクスのディフィニションデータとを含むハードウエア情報をコンピュータによりアクセス可能なデータベースに用意することを含む。さらに、このプログラムは、コンフィグレーションデータによりデバイスに実装される回路デザインを、コンピュータにより、コストファンクションを最小化する反復アルゴリズムを実行することにより複数の処理エレメントにマッピングすることを含む。コストファンクションは、第２レベルのルーティングマトリクスの使用を最小にする項目を含む。このプログラムまたはプログラム製品は、コンピュータに読み取り可能な適当な媒体に記録して提供できる。また、プログラムまたはプログラム製品は、インターネットなどのコンピュータネットワークを介して提供できる。
【発明の実施の形態】
【００２０】
図１（ａ）に、再構成可能なデバイスの一例を示している。このデバイス１は、本願出願人が開発したＤＡＰＤＮＡと称する半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ（Dynamic Reconfigurable Data-flow Accelerator）３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、ＤＮＡ３のダイレクト入出力用のインターフェイス４と、ＰＣＩインターフェイス５と、ＳＤＲＡＭインターフェイス６と、ＤＭＡコントローラ７と、その他の周辺デバイス８と、これらを接続するための高速スイッチングバス９とを含む。ＤＡＰ２は、デバッグインターフェイス２ａと、ＲＩＳＣコア２ｂと、命令キャッシュ２ｃと、データキャッシュ２ｄとを含む。ＤＮＡ３は、３７６個の処理エレメントＰＥ（以降では単にＰＥまたはＰＥｓと呼ぶことがある）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれる複数の処理エレメントＰＥ（ＰＥｓ）の機能および／または接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。
【００２１】
コンフィグレーションメモリ１９は、複数バンクの構成になっている。例えば、図１（ｂ）に示すように、ＰＥマトリクス１０には、フォアグラウンドバンクに格納されるコンフィグレーションデータ１８により第１の機能（データフロー、回路デザイン）１７ａが構成される。また、異なるバックグラウンドバンクにそれぞれ格納されるコンフィグレーションデータにより、第２の機能１７ｂおよび第３の機能１７ｃがそれぞれ構成される。メモリ１９のバンクを切り替えることにより、ＰＥマトリクス１０には、第１の機能１７ａに変わって第２の機能１７ｂまたは第３の機能１７ｃが再構成される。ＰＥマトリクス１０の再構成は、例えば、１サイクル（１クロック）でダイナミックに行なわれる。
【００２２】
再構成可能なデバイス（ダイナミックリコンフィグラブルデバイス）１に、図１（ｃ）に示すように、ＭＰＥＧデコーダなどの、あるアプリケーションを時分割した複数の機能（サブファンクション）を実現するように、ＰＥマトリクス１０を時分割で再構成（動的再構成）できる。このような使用により、デバイス１を用いて、多くのハードウエア資源を必要とするアプリケーションを、少ないハードウエア資源で実行できる。
【００２３】
また、図１（ｄ）に示すように、再生方式が異なるアプリケーションを実行するために、複数の機能をそれぞれ実現するようにＰＥマトリクス１０を再構成できる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。このデバイス１は、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能（マルチファンクション）を切り換えて実装できるので、専用のハードウエアに匹敵する速度で処理を行うことができる。
【００２４】
図２に、ＰＥマトリクス１０の配列を拡大して示している。ＰＥｓは、全体として、１６×２４のマトリクスを構成するように配置されている。なお、図３に示すように、ＰＥのいくつかは、２個分のＰＥのスペースを占め、全体として３７６個のＰＥがＰＥマトリクス１０に実際には配置されているが、図２には反映していない。これらのＰＥｓは、さらに、それぞれ８×８のＰＥｓからなる６つのグループに区分けされている。これらのグループをセグメントＳと称し、ＰＥマトリクス１０の左上から右下に向かって順番にセグメント０（Ｓ０）からセグメント５（Ｓ５）が配置されている。各々のセグメントＳ０〜Ｓ５に含まれるＰＥは、１サイクルの遅延の範囲内でデータを送受信可能なイントラセグメントコネクション（セグメント内接続）で接続されている。また、セグメントＳ０〜Ｓ５の内、隣接するセグメントは、後述するディレイエレメントを介してインターセグメントコネクション（セグメント関接続）２２により接続されている。
【００２５】
図３に、ＰＥマトリクス１０に含まれるＰＥｓの具体的な配置例を示している。図３に示したＰＥのうち、「ＥＸ」で始まるＰＥは、ＥＸＥエレメントと呼ばれる算術演算、論理演算および２入力の比較機能を含む。さらに、「ＥＸＣ」は、バイト比較を行うＣＭＰＳＢ命令を搭載し、「ＥＸＦ」は、ＦＦ１（ファインドファースト１）命令を搭載し、「ＥＸＭ」は、乗算命令を搭載し、「ＥＸＲ」はビットリバースを行うＢＲＥＶ命令を搭載し、「ＥＸＳ」は、バイトスワップを行うＢＳＷＡＰ命令を搭載するというように、タイプ毎に固有の演算機能も含んでいる。
【００２６】
「ＤＬ」で始まるＰＥは、ディレイエレメントであり、１−８クロックの間の遅延をそれぞれ設定できる。「ＤＬＥ」は、セグメント内のデータ遅延用であり、「ＤＬＶ」は縦方向のセグメント間のデータ送受信用であり、「ＤＬＨ」は横方向のセグメント間のデータ送受信用であり、「ＤＬＸ」は縦横方向のセグメント間のデータ送受信用のエレメントである。
【００２７】
ＰＥマトリクス１０には、さらに、ＤＮＡの内部メモリである「ＲＡＭ」、データ入力用のＤＮＡ内部バッファである「ＬＤＢ」、データ出力用のＤＮＡ内部バッファである「ＳＴＢ」、ＤＮＡ内部バッファに対するアドレス生成エレメントである「Ｃ１６Ｅ」、外部メモリ空間に対するアドレス生成エレメントである「Ｃ３２Ｅ」、ＤＮＡダイレクトＩ／Ｏからのデータ入力用エレメントである「ＬＤＸ」、ＤＮＡダイレクトＩ／Ｏへのデータ出力用エレメントである「ＳＴＸ」が配置されている。
【００２８】
図４に、ＰＥの一例として、ＡＬＵ１１ａと、ＭＵＬ（１６×１６）１１ｂと、ＦＦ１１ｃなどを含む、ＥＸＥエレメント（「ＥＸＭ」）の概略構成を示している。このＥＸＭは、ＤＮＡ３のコンフィグレーションメモリ１９に格納されたコンフィグレーションデータ１８により、算術演算、論理演算、２入力の比較機能、さらには、乗算のいずれか、またはそれらのいずれかが複合した命令を実行するように構成できる。また、複数のＦＦ１１ｃを内蔵しているので、エレメントＰＥに対するデータの入力から出力までのレイテンシを制御することが可能であり、ディレイエレメント（ＤＬＥ）の数が不足する構成では、ディレイエレメントとしての機能をセットすることも可能である。
【００２９】
ＰＥマトリクス１０は、複数のＰＥと、それらを接続するためのルーティングマトリクス（配線群）２０を含む。ルーティングマトリクス２０は、それぞれのセグメント内（図４ではＳ０およびＳ１のそれぞれ）のＰＥを接続するための第１レベルの配線群（第１レベルのルーティングマトリクス、イントラコネクト、セグメント内部接続）２１と、ディレイエレメントを介して隣接するセグメントの間（図４ではＳ０とＳ１との間）を接続するための第２レベルの配線群（第２レベルのルーティングマトリクス、インターコネクト、セグメント間接続）２２とを含む。ルーティングマトリクス２０によるＰＥｓの接続はコンフィグレーションデータ１８により制御できる。したがって、ＰＥマトリクス１０には、コンフィグレーションデータ１８により、複数のＰＥのそれぞれの機能を変更すること、および／または、ルーティングマトリクス２０の少なくとも一部の接続を変更することにより、異なる回路（データパス、データフロー）を再構成できる。
【００３０】
図５に、セグメントの内部（図５はＳ０を例示）のＰＥｓを接続するための第１レベルの配線群２１の構成の一例を示している。第１レベルのルーティングマトリクス２１は、セグメント０（Ｓ０）に含まれる８×８個のＰＥｓを接続するための、１２８の縦方向のバス２３と、６４の横方向のバス２４とを含む。縦方向のバス２３は、１６のグループに分けられ、それぞれ８のバスを含む２つのＶ−バス２３ｘおよび２３ｙがペアとなり、ＰＥｓの縦の列（コラム）に沿って、その列の両側に配置されている。横方向のバス２４は８のグループに分けられ、それぞれ８のバスを含むＨ−バス２４がＰＥの横方向の行（ライン）に沿って配置されている。Ｖ−バス２３ｘおよび２３ｙには、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２５がそれぞれのＰＥに対応して設けられており、それぞれのＰＥに対してデータの入力を可能としている。
【００３１】
Ｈ−バス２４には、Ｈ−バス２４とＶ−バス２３ｘおよび２３ｙのそれぞれの交差に対応して、８−１（８対１）のバスセレクタ（マルチプレクサ、ＭＵＸ）２６が設けられている。したがって、１つのＨ−バス２４から１つのデータセットを、そのＨ−バス２４と交差している１つのＶ−バス２３ｘまたは２３ｙに出力できる。逆も可能である。Ｈ−バス２４に含まれるバスのそれぞれには、そのラインのＰＥｓの出力が接続される。したがって、Ｖ−バス２３ｘおよび２３ｙと、Ｈ−バス２４とを介することにより、セグメントに含まれるＰＥｓを接続できる。これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により接続できる範囲、すなわち、各セグメント０〜５（Ｓ０〜Ｓ５）内のＰＥの間では１サイクル（１クロック）以内にデータを送受信できる。したがって、タイミング的には、例えば、セグメントＳ０に含まれるＰＥｓは、いずれも等価である。このため、同一セグメント内であれば、回路を構成するために、いずれのＰＥを選択して機能を割り付けても、タイミングの検討は不要であり、タイミング的には、あるセグメント内のＰＥｓを用いて、所定の回路を自由に配置および配線できる。
【００３２】
図６に、上記と異なる第１レベルのルーティングマトリクス２１の構成を示している。この例では、１６−１（１６対１）の２つのＭＵＸ２６ａおよび２６ｂを用いて、２つのＨ−バス２４から１つのＶ−バス２３ｘまたは２３ｙへデータを入出力できるようになっている。したがって、１つのＨ−バス２４から、そのＨ−バス２４と交差している１つのＶ−バス２３ｘまたは２３ｙに対して、最大で２つのデータセットを出力できる。その逆も可能である。このため、第１レベルのルーティングマトリクス２１の接続のフレキシビリティが増加する。
【００３３】
図７に、第２レベルのルーティングマトリクス２２の構成を示している。図７では、第２レベルのルーティングマトリクス２２により、隣接するセグメント（図７ではＳ１およびＳ４）にそれぞれ含まれている接続用のエレメントＤＬＨを接続している。図７に拡大して示したそれぞれのＤＬＨは、それぞれのセグメントＳ１およびＳ４の内部の第１レベルのルーティングマトリクス（intra-segment interconnect）２１に接続している。したがって、セグメントＳ１に含まれるＰＥと、セグメントＳ４に含まれるＰＥとを第２レベルのルーティングマトリクス（inter-segment interconnect）２２を介して接続することができる。接続用のディレイエレメントＤＬＨは、第１レベルのルーティングマトリクス２１に含まれるバスのインターフェイスとして機能する。したがって、第１レベルのルーティングマトリクス２１に含まれるバスを、セグメント毎に独立して使用できる。一方、セグメント間でデータを入出力する必要があるときは、接続用のディレイエレメントＤＬＨに含まれる複数のＦＦを介してデータを入出力する必要があり、クロックに同期した２サイクル以上の遅延が新たに加わる。
【００３４】
このように、第１レベルのルーティングマトリクス２１のみを用いてＰＥを接続する場合、ＰＥｓの間は１サイクル（第１の遅延）の範囲内で接続されることが保証され、タイミングの検証は不用である。これに対し、第２レベルのルーティングマトリクス２２を介してＰＥを接続する場合は、２サイクル以上の遅延が加わる。第２レベルのルーティングマトリクス２２を介して接続する場合の遅延は、ディレイエレメントＤＬＨの設定に依存する。例えば、ＤＬＨの遅延量を制御することにより、第２のルーティングマトリクス２２を２回使用する信号と、第２のルーティングマトリクス２２を１回使用する信号とをシンクロナイズできる。他の接続用のディレイエレメントＤＬＶおよびＤＬＸを介して隣接するセグメントＳ０〜Ｓ５を接続するときも同様である。
【００３５】
このため、セグメントＳ０〜Ｓ５のうちの、複数のセグメントに分散する回路、すなわち、セグメントを跨ぐ回路は、配置配線の間あるいは終了した後に、タイミングの調整あるいは再検討が必要となる。その結果、遅延エレメントを追加したり、遅延エレメントの遅延を調整したりすることが要求される可能性がある。回路をＰＥマトリクス１０に配置および配線するときは、第２レベルのルーティングマトリクス２２の使用を最小限にすることが好ましい。
【００３６】
図８に、与えられた回路デザインからコンフィグレーションデータを生成する過程を示している。まず、Ｃ言語などのプログラムあるいはデータフローグラムなどの状態で与えられた仕様（回路デザイン）８１をＤＮＡコンパイラ８５によりＰＥネットリスト８２に変換する。ＤＮＡコンパイラ８５は、仕様８１を解析し、デバイス１に実装する機能を、ＰＥのいずれかにそれぞれ実装できる複数の機能ブロックＦＢ（以降では単にＦＢと表示することがある）と、それら複数の機能ブロックＦＢの接続とにより示したデータフローグラムをＰＥネットリスト８２として生成する。この過程で、ＤＮＡコンパイラ８５は、データセットの順番を規定するためのディレイだけではなく、各ＦＢが割り当てられるＰＥにおけるレイテンシを含めて検討し、各ＦＢへのデータ入力のタイミングを検討する。そして、ＰＥネットリスト８２に適当な遅延を含むＦＢを挿入する。
【００３７】
次に、ＰＥネットリスト８２に基づき、配置配線支援システム３０により配置配線情報を含むコンフィグレーションデータ１８を生成する。生成されたコンフィグレーションデータ１８に基づきＰＥマトリクス１０を再構成することにより、ＰＥマトリクス１０を含むデバイス１に、回路デザイン８１を実現するための機能を実装できる。
【００３８】
図９に、配置配線支援システム３０の概要を示している。このシステム３０は、ハードディスクデバイスなどの適当な格納デバイスと、メモリと、ＣＰＵを含めた演算処理機能とを含む、通常のコンピュータ１００として提供されるハードウエア資源を用いて構成される。配置配線支援システム３０は、上述した再構成可能なデバイス１を構成するためのコンフィグレーションデータ１８を生成するためのシステムである。このシステム３０は、ハードウエア情報８９を格納するための第１のデータベース３１と、データフローグラムタイプのＰＥネットリスト（以降ではＤＦＧ）８２を格納するための第２のデータベース（ＤＦＧ格納部）３２と、ＤＦＧ８２をデバイス１にマッピングするための装置（マッピング装置）３３と、マッピングデータ８３とＤＦＧ８２とを元に、初期値設定などを含めたコンフィグレーションデータ１８を生成するための装置３４とを含む。
【００３９】
ハードウエア情報８９は、デバイスの種類毎に生成されるチップディフィニションデータである。上記のデバイス１であれば、ハードウェア情報８９には、ＰＥのディフィニションデータ（セグメント情報、それぞれのセグメントに含まれるＰＥの種類、数、配置など）、それらＰＥを接続するための第１および第２のルーティングマトリクスを含む配線のディフィニションデータなどが含まれる。マッピング装置３３を含むシステム３０は、マッピングしようとするデバイスのハードウエア情報８９を変えることにより、種々のタイプのデバイスに対してマッピングすることができる。また、動作周波数などの条件により、セグメントの範囲および／または境界が変更できるようなデバイスであれば、それらの条件の異なるハードウエア情報８９を用いて、マッピング装置３３によりマッピングするための前提条件を変えることができる。
【００４０】
マッピング装置３３は、ＤＦＧ８２に含まれる複数の機能ブロック（ＦＢｓ）を複数のＰＥにマッピングし、マッピングデータ８３を生成する。マッピングデータ８３を用いることにより、ＤＦＧ８２により供給される回路デザインをデバイス１に実装することが可能となる。本明細書においてマッピングとは、ＤＦＧ８２に含まれるＦＢｓをデバイス１に含まれるＰＥｓのいずれかに割り当てる（配置する）こと、および／または割り当てた情報を生成することを含むものである。
【００４１】
マッピング装置３３は、データベース３２からＤＦＧ８２を読み出して解析する機能ユニット３８と、ＤＦＧ８２に含まれるＦＢｓを、セグメントに区分けされたＰＥｓのいずれかにそれぞれ暫定的に割り当てる機能ユニット３５と、ハードウエア情報８９に基づき、コストファンクションＣＦを最小化する反復アルゴリズムを実行することによりＰＥに対するＦＢの割り当てを適宜変えてＤＦＧ８２をＰＥｓにマッピングする機能ユニット３６と、タイミングを検証する機能ユニット３７とを含む。マッピング機能ユニット３６は、ＰＥマトリクス１０のＰＥｓのアレンジメントをコンピュータ１００のメモリに仮想的に展開したプレースメントテーブル（配置用テーブル）３６ａと、シミュレーテッドアニーリング法（以降ではＳＡ）にしたがってＰＥｓの割当てを変更する機能３６ｂと、コストファンクション（以降ではＣＦ）を計算する機能３６ｃと、ＳＡの条件を判断する機能３６ｄと、マッピングデータ８３を更新する機能３６ｅとを備えている。詳しくは後述するように、ＳＡ３６ｂは、プレースメントテーブル３６ａのＰＥｓの割り当てを少しずつ変えて（perturb, perturbation）、ＣＦの計算を繰り返させる。
【００４２】
ＣＦを計算する機能３６ｃは、プレースメントテーブル３６ａのＰＥｓであって、ＳＡによりＦＢｓが割り当てられたＰＥｓを接続するためのルートを求め、そのルートを形成するためのルーティングマトリクス２１および２２の使用状況から以下の式（１）によりＣＦを計算する。
ＣＦ  ＝  Ｃ１・Ｆ（Ｗ−intra）＋Ｃ２・Ｆ（Ｗ−inter）      ・・・（１）
Ｆ（Ｗ−intra）は、第１レベルのルーティングマトリクス２１の使用に対応し、セグメントを跨がない配線に関するコストを求めるための関数（項目、項）である。Ｆ（Ｗ−inter）は、第２レベルのルーティングマトリクスの使用に対応し、セグメントを跨ぐための配線に関するコストを求めるための関数（項目、項）である。Ｃ１およびＣ２は係数であり、ＣＦは、第２項、すなわち、Ｃ２・Ｆ（Ｗ−inter）の値の変動が大きく反映されるようになっている。したがって、マッピング機能３６は、第２レベルのルーティングマトリクス２２の使用を最小にするようにマッピングする。
【００４３】
シミュレーテッドアニーリング法（ＳＡ）は、ＣＦを最小化するような配置を得るための反復アルゴリズムとして公知のものの１つである。また、ＳＡは、様々な組合せ最適化問題で使用されており、特に回路設計問題に成功しているアルゴリズムの１つである。ＳＡは、多粒子系の状態の数式化を実現するためのモンテカルロ法を一般化したものである。オリジナルのメトロポリス（メトロポリス・モンテカルロ）は熱力学系初期状態がエネルギーＥと温度Ｔで選ばれ、温度Ｔを一定に保ち、初期設定を乱し、エネルギーの変化ｄＥを計算することであり、乱数発生により作った新しい状態を採択するか否かを変化ｄＥにより採択するか否かを決定する。変化ｄＥがゼロ以下であれば、新しい状態を確率「１」で採択し、変化ｄＥが１より大きければ確率「ＥＸＰ（−βｄＥ）」で採択する。ただし、βはボルツマン定数である。ＣＦを最小にするような配置を求める処理では、ＳＡのエネルギーＥは、コストファンクションＣＦに置き換えられ、エネルギーの変化ｄＥは、コストファンクションＣＦの変化ｄＣＦに置き換えられる。
【００４４】
ＳＡは、高温においてメトロポリス・モンテカルロシミュレーションにより最適化することから始まる。このことは、乱数発生による状態変化のうち、エネルギーの増加につながるような状態変化を比較的高い割合で認めることを意味する。モンテカルロステップを十分な数だけ反復すると、または、試みると、温度Ｔを減少させる。そして、温度Ｔを下げながらメトロポリス・モンテカルロシミュレーションが続けられ、終りの温度Ｔに達するまで、このプロセスは繰り返される。ＳＡプログラムは１組のネストされたＤＯループを含む。最も外側のループが温度をセットし、最も内側のループがその温度におけるメトロポリス・モンテカルロシミュレーションを実行する。温度Ｔを下げる方法はクーリングスケジュールとして知られている。典型的には、２つの異なったクーリングスケジュールが主に使用される。１つは、リニア・クーリングスケジュール（Ｔnew＝Ｔold−ｄＴ）である。他の１つは、プロポーショナル・クーリングスケジュール（Ｔnew＝Ｃ×Ｔold，Ｃ＜０）である。
【００４５】
暫定的に割り当てる機能ユニット３５は、ハードウエア情報８９とＤＦＧ８２とを解析して、割付（配置）の優先順位を決める（生成する）解析機能３５ａと、その結果を保持する優先順位格納部（プライオリティバケット）３５ｂと、優先順位に沿って、乱数に基づきＤＦＧ８２に含まれるＦＢｓをＰＥｓに暫定的にランダムに割り付けて仮配置（暫定割り付け）を得る初期配置機能３５ｃと、ＤＦＧ８２より配置を固定する必要があるＦＢを固定セルとして所定の場所のＰＥに設定する機能３５ｄとを備えている。解析機能３５ａは、ＰＥマトリクス１０に配置された複数種類のＰＥｓのうち、数の少ないＰＥにしか割当てできないＦＢを優先させるように優先順位を生成し、それをプライオリティバケット３５ｂとする。
【００４６】
初期配置機能３５ｃは、ＤＦＧ８２に含まれるＦＢｓを、マトリクス１０のＰＥｓに、基本的には、セグメントＳ０〜Ｓ５を無視してランダムに割り付ける。また、初期配置機能３５ｃは、特定のＦＢを特定のセグメントのＰＥｓにランダムに配置する機能を含む。この特定のＦＢについては、ＳＡ３６ｂも、同様に、特定のセグメントのＰＥに割り付ける。さらに、機能３５ｄは、特定のＦＢを所定の位置のＰＥに割り付け、ＳＡ３６ｂは、所定の位置のＰＥに対する割り付けを変えない。
【００４７】
タイミングを検証する機能３７は、ＰＥｓに届く（到達する）様々な信号を同期させるためのものである。タイミング検証機能３７は、ＰＥｓに届く信号のタイミングを解析するタイミング解析機能（シンクロ機能）３７ａと、ＤＦＧ８２のタイミングを解析した結果を格納しておくためのメモリ３７ｂと、遅延エレメント（ＤＬ）を追加する機能３７ｃとを含む。遅延エレメントを追加する機能３７ｃは、マッピング機能３６により得られたマッピングデータ８３により構成される回路を解析機能３７ａにより解析した結果と、メモリ３７ｂに格納されたＤＦＧ８２との結果とを比較する。そして、ＤＦＧ８２により与えられたデータフローと同じ結果が得られるように、ＰＥｓに入力される信号を同期させるために適当なディレイエレメントをマッピングデータ８３に追加する。
【００４８】
この再構成可能デバイス１のＰＥマトリクス１０に構成されるデータフロー（データパス）は、クロック同期（サイクル同期）型のデータフローである。したがって、それぞれのＰＥにおいて所定の処理が行われるように、必要に応じて遅延エレメントをデータフローに挿入し、ＰＥに届く信号（データセット）を同期させる。本明細書においては、このことをデータ同期と呼ぶ。データ同期は、ＰＥにおけるレイテンシの相違、Ｚ変換演算の要否などにより必要になり、データ同期のための遅延量はケースバイケースである。パイプライン化された回路を同期化する際にディレイバッファの数を最小にすることはディレイエレメントの消費量を少なくするために好ましい。
【００４９】
例えば、「Minimizing the number of delay Buffers in the Synchronization of pipelined System（DAC'91in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.13, No.12, December 1994, pp.1441−1449）」にＬＰ（Linear Programming）テクニックのシンプレックスメソッドを使用することが記述されている。入力アプリケーション（別名回路）が経路の長さと経路遅延の両方に関して正しく表されるならば、ＬＰは、データ同期の要求を解決するためのシステマチックな手段であり、最適な解を得ることができる。シンプレックスアルゴリズムは多項式時間における性能を保証しないが、一般に、それは整数線形計画法がアプローチするよりはるかに良い性能を示す。このデバイス１においては、セグメント内の配線については、ＰＥｓを接続する経路の遅延が無視できる。また、セグメントを跨ぐ配線については、遅延をサイクル単位で規定できる。したがって、この方法は、このデバイス１のデータ同期の解析に適している。
【００５０】
このタイミング解析機能３７ａでは、ＤＦＧ８２からシグナルフローグラフ（ＳＦＧ）を生成し、線形方程式を生成する。必要であればダミーノードを挿入した後、その線形方程式を、シンプレックスアルゴリズムを用いてＬＰ問題を解くためのアプリケーションプログラムに投入し、解を得る。アプリケーションプログラムの一例は「ＬＰＳＯＬＶＥＲ」と呼ばれるものである。アプリケーションプログラムの解を保存し、また、解に従ってディレイエレメントを挿入することができる。
【００５１】
図１０に、この配置配線支援システム３０における処理の流れを示している。ステップ４１において、デバイス１に関するハードウエア情報８９を格納した第１のデータベース３１を、システム３０を構成するコンピュータ１００が使用できる状態にする。ハードウエア情報８９は、それぞれのセグメントＳ０〜Ｓ５に含まれる複数のＰＥｓのデータ（ディフィニションデータ）と、第１および第２のルーティングマトリクス２１および２２のデータ（ディフィニションデータ）とを含むものである。ステップ４２において、マッピングデータ８３を生成し、ステップ４３において、マッピングデータ８３を含む、および／またはマッピングデータ８３に基づくコンフィグレーションデータ１８を生成する。
【００５２】
図１１に、マッピングデータを生成する処理４２のさらに詳しい流れを示している。これらの処理は、マッピングシステム３３として動作するコンピュータ１００により実行される。また、図１１に示した処理は、プログラムあるいはプログラム製品として、適当なメディア（ＣＤ、ＤＶＤなど）に記録して提供できる。また、インターネットなどのコンピュータネットワークを介して提供できる。
【００５３】
まず、ステップ４５において、第２のデータベース３２からマッピングするＤＦＧ８２を読み込み、解析する。このＤＦＧ８２は、生成しようとしているコンフィグレーションデータ（config.data）によりデバイス１に実装しようとしている（実装される）回路デザインである。ステップ４６において、上述したタイミング解析機能３７ａを用いてデータ同期を確認し（Synchronization）、ステップ４７において、その結果（タイミング条件（１）、timing cond.(1)）をメモリ３７ｂに格納する。
【００５４】
ステップ４８において、暫定的に割り当てる機能３５を用いて、ＰＥｓの暫定的な割付け（暫定的マッピング、仮配置（Provisional Placement））を行う。ＰＥマトリクス１０におけるＰＥｓの配置自体は固定されたものであり、マッピングあるいは以降における配置・配線における配置とは、それらのＰＥｓの１または複数に割り当てる機能（ＦＢｓ）を変えることを意味する。また、ＰＥの機能と、それに割り当てる機能ＦＢとは対応したものであり、以降では、しばしばＰＥを入れ替える、などのＰＥが移動可能であることを示す表現が含まれている。それらの表現は、ＰＥの機能をコンフィグレーションデータにより再構成することを含み、ＰＥに対応するＦＢの割当てを入れ替える、あるいは入れ替えるための処理を行うことを意味する。このデバイス１の配置配線支援において、配置とは、物理的にＰＥを配置することではなく、ＤＦＧ８２を実現するための複数の機能（ＦＢｓ）をＰＥマトリクス１０に配置または設定することを意味する。
【００５５】
図１２〜図１７に、マッピングの処理の簡単な例を示している。以降では、図１１に示したフローチャートを、これらの例を参照して説明する。図１２は、ＰＥマトリクス１０の簡易な例であり、セグメントは１つである。図１３は、図１２のＰＥマトリクス１０に含まれるＰＥに関するハードウエア情報８９の一例である。ハードウエア情報８９としては、ＰＥマトリクス１０のアレンジメントに加え、含まれているＰＥのタイプ８９ａ、各タイプのＰＥに実装可能な命令８９ｂ、タイプ毎の数８９ｃが含まれる。配置の優先順位８９ｄは、ハードウエア情報８９に含まれていても良いし、マッピングシステム３３において加えても良い。
【００５６】
図１４に、ＤＦＧ８２の一例を示している。配置配線を行うＤＦＧ８２がユーザから与えられ、ＤＦＧ格納部であるデータベース３２に格納される。このＤＦＧ８２において、ＦＢｓは、それぞれのＦＢに対応した機能のＰＥ（ＰＥ１〜ＰＥ７）により示されている。解析機能３８は、与えられたＤＦＧ８２から、ＰＥに対応するＦＢを抽出し、そのタイプ・属性を抽出する。さらに、ＤＦＧ８２に含まれる複数のＦＢｓのうち、特定のＰＥｓの配置によりＰＥマトリクス１０にマッピングすることが望ましいグループ（固定化された配列グループＦＡＧ、Fixed Arranging Group）を抽出する。
【００５７】
図１５（ａ）および（ｂ）に、ＤＦＧ８２が解析された結果の一例を示している。解析結果の一例は、命令種リスト８８と、接続関係リスト８７である。これらのリスト８８および８７では、ＦＢｓは、ＰＥｓに対応してＰＥ１〜ＰＥ７により示されている。この抽出された命令種が、配置されるべきＰＥアレイ１０のどのＰＥに割当て可能かを示す指標となる。本例において、図１３に示すように、マッピングするハードウエアはＡ１，Ａ２，Ａ３，Ｂの４種のタイプのＰＥを含み、タイプによりＰＥに実装可能な命令は異なる命令を含む。
【００５８】
ここで、図１４のＤＦＧ８２に含まれるＰＥ２−ＰＥ３（配置可能なＰＥでは「Ａ２−Ｂ」に対応）の演算組合せについては、ハードウエア上の「Ｂ−Ａ２」が縦に連続するパターンでしかマッピングできないとする。このようなグループがＦＡＧに対応し、ＦＡＧ化すべきＰＥの構成はハードウエア情報８９に含まれる。図１２に示したＰＥマトリクス１０では、このＦＡＧは３箇所にしか割り当てることができない。したがって、この段階では、ＤＦＧ８２を解析して得られたＦＡＧは、最優先にマッピングする項目となる。
【００５９】
ステップ４８の暫定的マッピングを決めるプロセスでは、プライオリティバケット（Priority Bucket）３５ｂを作成する。この段階での優先度（Priority）は、ハードウエア上のＰＥにＦＢを割当てていく際の順番を意味し、プライオリティバケット３５ｂはそのリストである。優先度は、マッピング装置３３の内部で定義され、ハードウエア上の、ある種類に対応するＰＥの数の少なさが、そのＰＥの種類の優先度を増大させる。本例のマッピング装置３３においては、ハードウエア情報８９をサーチし、図１３に示したように、ハードウエアのＰＥの種類ごとに数をカウントし、その少ないものから順にリストアップする。そのリストに対して上から順が優先度（Priority）の順序となる。
【００６０】
さらに、ステップ４８では、フィクシドセル（固定セル、Fixed Cell（機能が固定化されたＰＥ））に機能を割り当てることも判断する。固定セルは、ハードウエアのアーキテクチャによりマッピングする場所（ＰＥ）が限定された、またはユーザにより特定のＦＢを割り当てるＰＥについてハードウエア（ＰＥマトリクス）上の位置を限定したものが相当する。
【００６１】
図１６に、プライオリティバケット３５ｄの一例を示している。このバケット３５ｄにおいては、ユーザによりＰＥ７が固定セルとして指定され、割り当てられるＰＥは、ハードウエア上の行４列１（図１２の座標（ｘ，ｙ）＝（４，１））の位置に限定されている。可動セル（ムーバブルセル、Movable Cell）は、ハードウエア上の取りうる位置が複数あるものである。したがって、ＳＡのプロセスにおいて、ＰＥマトリクス１０のＰＥにマッピングできる配置内で順次ランダムに割当てを変化させるＦＢ（ＰＥに対応する機能）に相当する。上記例においては、ＰＥ７以外は全て可動セル（ムーバブルセル）に相当する。
【００６２】
この他に、複数のセグメントを有するデバイスに対しては、割り当てるセグメントを固定することが可能である。セグメント固定のＦＢは、ＳＡのプロセスにおいて、ＰＥマトリクス１０の特定のセグメントのＰＥにマッピングできる配置内で、順次ランダムに割当てを変化させるＦＢ（ＰＥに対応する機能）である。
【００６３】
図１６に示したプライオリティバケット３５ｄでは、可動セルはマッピングする優先順に並べてリスト化している。優先順の最も上位に挙げられるのがＦＡＧである。ＦＡＧは、その構成要素となるＰＥの数により割当ての優先順の大小が決定される。本例においては、ＦＡＧはグループ１のひとつだけである。したがって、マッピングの優先順の最大のものとしてはグループ１がリストアップされ、次には各ＰＥに割り付けるＦＢ（Ｐ１、４−６）がリストアップされている。
【００６４】
ステップ４８においては、まず、固定セルをハードウエア１０のＰＥに割り当てる。本例の場合、図１７（ａ）に示すように、ＰＥ７を、マトリクス１０の図１７（ａ）に示したＸ−Ｙ座標（４，１）に配置する。さらに、可動セルをプライオリティバケット３５ｄの優先度に従い順番にハードウエア１０上のＰＥｓに割り当てる。この割当ては、割り当てるＦＢとしての機能を実装できる（配置可能な）ＰＥをランダムに選択することにより行う。ランダムな配置は、乱数を発生させ、ＦＢを割当て可能なＰＥの間から割り当てるＰＥを等しい確率により決定する。なお、ＰＥに対し、先にＦＢが割り当てられている場合には、その位置のＰＥは割付けの対象には含まれない。
【００６５】
図１６のプライオリティバケット３５ｄに従うと、次に、ＦＡＧのグループ１をＰＥマトリクス１０に配置する。それぞれのＦＡＧの配置（マッピングする座標）はベースセルの位置により決定する。この例において、ＦＡＧのベースセルは、左上のセルの座標により代表される。このグループ１は、ＰＥ「Ｂ」とＰＥ「Ａ２」とが縦一列に配置されるＦＡＧである。このため、ＰＥ「Ｂ」をベースセルとし、ＰＥ「Ｂ」の位置によりグループの配置が代表して決定される。このグループ１をマッピングできるパターンは、ベースセルで表すと座標（２，２）、（２，３）、（２，４）の３つである。この３つのマッピング可能な位置（パターン）から、乱数により等しい確率で１つのパターンを選択する。ベースセルが座標（２，３）に割付けられたとする。この決定により、ハードウエア１０の座標（２，２）のＰＥにＰＥ３が割当てられ、座標（３，２）にＰＥ２が割り当てられたことになる。これらの位置のＰＥには、以降の操作で他のＦＢが割り当てられることはない。
【００６６】
次に、その次の優先度のＦＢであるＰＥ５を同様の操作で配置する。ＰＥ５はＰＥ「Ａ１」にのみ割当て可能なＦＢである。したがって、ハードウエア１０では３つの割当て可能なＰＥ（ＰＥのポジション）がある。これらのＰＥｓから、１つ乱数により割り当てられるＰＥの位置が決定される。図１７（ａ）では、ＰＥ５は、座標（１，４）のＰＥに割付けられる。次に、第３順位のＦＢであるＰＥ４が適当なＰＥに割り当てられる。最後に、最後の順位のＦＢであるＰＥ１およびＰＥ６が配置される。ＦＢｓのうち、ＰＥ１、ＰＥ６およびＰＥ７は、それぞれＰＥ「Ａ１」、ＰＥ「Ａ２」およびＰＥ「Ａ３」のいずれにも配置可能である。ＰＥ７は、固定セルであり、既に座標（４，１）のＰＥ「Ａ３」に割り当てられている。したがって、固定セルとともに、上記において割り当てられたＰＥを除いた、ＰＥ「Ａ１」、ＰＥ「Ａ２」およびＰＥ「Ａ３」の中から、ランダムにＰＥ１およびＰＥ６を割り当てるＰＥが選択される。この操作で、暫定的に決定されたマッピングは、一旦メモリに格納される。
【００６７】
ＤＦＧ８２に含まれる全てのＦＢｓが、ＰＥマトリクス１０のＰＥｓを用いて暫定的であれ、割付できなければ、ＤＦＧ８２をマッピングするための、ＰＥマトリクス１０のハードウエアリソースが不足していることを意味する。したがって、ＳＡを行うまでもなく、ＤＦＧ８２はデバイス１にマッピングができないという結論になる。割付けの方法により、ＤＦＧ８２がデバイス１にマッピングできるか否かが決定される可能性がある。ＦＢを割付け可能なＰＥの数が余っていても、特定の命令を行うＦＢを割付けるＰＥが消費されてしまえば、ＤＦＧ８２をデバイス１にマッピングできないからである。このため、上記のように割付けの優先度を決め、割付けるためにクリティカルとなると予想される条件を予め求めて、ＰＥマトリクス１０に用意されたハードウエアリソースの使用効率を向上しようとしている。
【００６８】
優先度の決め方の１つは、上記のように、ＰＥマトリクス１０に用意された各タイプのＰＥの数によることである。この例において、この優先度は、ＦＢにより示される命令タイプ毎の、ＰＥマトリクス１０に実装可能な数に対応している。ＤＦＧ８２に含まれるＦＢｓのタイプ毎の数のいずれかが、ＰＥマトリクス１０に用意されたＰＥｓにより実装可能な数を超えている場合は、そのタイプのＦＢを他のタイプのＦＢｓの組み合わせに変更するようにＤＦＧ８２を変更することが可能である。また、ケースによっては、ＰＥマトリクス１０に用意されたＰＥのいずれかを本来の機能ではない機能にコンバートすることにより、ハードウエア不足を補うことができる。
【００６９】
デバイス１では、算術演算／論理演算用の「ＥＸ＊」で表されるＰＥは、ディレイのみを実現するＤＬＥとして機能させることができる。ステップ４８において、暫定的マッピングが失敗した場合は、ステップ４９において、要因がＤＬＥの不足であるか確認し、ＤＬＥの不足であれば、ステップ５０において、余っているＥＸ＊をＤＬＥとして利用できるようにする。そして、ステップ４８をやり直す。暫定的マッピングの失敗の要因がＤＬＥの不足でない場合は、マッピング失敗（配置失敗）となり、その要因をさらに解析してＤＦＧ８２を再生成するなどの処理を行う。
【００７０】
暫定的マッピングが得られると、ステップ５１において、そのマッピングに含まれるＰＥｓを接続するルートをチェックし、ステップ５２において、そのルートにしたがって式（１）のコストファンクションＣＦを計算する。図１２に示したハードウエア（ＰＥマトリクス）はセグメントが１つなので、第１レベルのルーティングマトリクス２１の使用に関するコストだけが計算される。第１レベルのルーティングマトリクス２１の使用によるコストは、図５または図６に示したＭＵＸ２５または２６の使用に着目して求めることができる。
【００７１】
このため、以下では、ＣＦをＣＦαとして式（２）のようにして説明する。
ＣＦα  ＝  Ｆ（ＭＵＸ）    ・・・（２）
ＭＵＸにより、バスを１本占有する場合、Ｆ（ＭＵＸ）は値４をとるとする。ＭＵＸは配線使用に関するペナルティを示す。配線リソースは制限されているので、ＣＦαは小さいことが望ましい。特に、縦配線２３ｘ、２３ｙから、横配線２４への接続が限られているようなケース、例えば縦配線２３ｘ、２３ｙから横配線２４へ接続することができるのは２本のみであるような場合は、ＭＵＸの場所と条件により、Ｆ（ＭＵＸ）は無限大の値となるよう非常に大きな値を設定することが望ましい。
【００７２】
一方、ＰＥから出力された同一のデータが、同一の縦配線２３ｘまたは２３ｙに接続された２つのＰＥにインプットする場合、２つのＰＥの入力のために占有されるバスは１本となる。したがって、ルーティングマトリクス２１の使用量は減る。このようなマッピングが行われている場合は、Ｆ（ＭＵＸ）が減ることが望ましい。例えば、Ｆ（ＭＵＸ）の値は、（４×１／２）となる。
【００７３】
ステップ５２において、図１７（ａ）のマッピングのコストＣＦαを計算する。接続（接続するルート）は、ＰＥ１−ＰＥ２、ＰＥ１−ＰＥ４、ＰＥ１−ＰＥ５、ＰＥ２−ＰＥ３、ＰＥ４−ＰＥ６、ＰＥ５−ＰＥ６、ＰＥ３−ＰＥ７、ＰＥ６−ＰＥ７の８つであり、それぞれ一本ずつ配線を占有する。したがって、ＣＦαは３２（４×８）である。この値を、マッピング装置３３として機能するコンピュータ１００のＲＡＭに記憶し、次のステップに進む。
【００７４】
ステップ５３において、ＳＡによる最適化を開始する。ＳＡは上記のランダムに割付けた暫定的なマッピングの割り当てを順々に変更していくことでコストファンクションの最小値を求めることにより行われる。ＳＡの基本的なフローは公知であり、例えば、「Chen, Tao,”Multi-FPGA Partitioning Using Simulated Annealin” UNIVERSITY OF CINCINNATI, 2003」などを参照できる。
【００７５】
ＣＦを最小化するような反復アルゴリズムは、ＳＡに限定されない。平均場アニーリングまたは遺伝的アルゴリズムを含む反復アルゴリズムを用いることができる。例えば、最も簡易なヒューリスティックな方法としては、温度のクーリングレートや一定確率でのコストファンクションの上昇の許容等を考慮せず、ひたすらランダム配置を繰り返し、コストファンクションが最小となるようにマッピングを求めることである。図１７（ｂ）〜図１７（ｅ）は、そのような方法でマッピングしたときのＣＦαの変化を説明するためのものである。また、これらの処理は、一定確率でＣＦの上昇を許容する点を除くと、ＳＡにおける同一温度の処理と共通である。
【００７６】
図１７（ｂ）〜図１７（ｅ）は、プライオリティバケット３５ｄから再度、同一条件で、図１２のハードウエア（ＰＥマトリクス）１０にマッピングした例を示している。これらのマッピングは、図１７（ａ）と同じ条件、すなわち、同じ優先度で割付けが行われる。しかしながら、個々の割付けについては、固定セルを除き、乱数によりランダム配置されることから、一般に前回のマッピングとは異なるマッピングが得られる。
【００７７】
図１７（ｂ）のマッピングのＣＦαは２６である。ＰＥ２を含むＧ１とＰＥ４が同一列内に配置されているために、ＰＥ１−ＰＥ２およびＰＥ１−ＰＥ４が同一配線を使うことができる。よって、ＣＦαは（２＋４×６）となる。
【００７８】
ここで、前回のマッピングと今回のマッピングのコストとを比較し、ＣＦα（前回）＞ＣＦα（今回）の場合にはＣＦαの値を今回のものに変更し、今回のマッピングをＲＡＭに保存する。一方、ＣＦα（前回）＜ＣＦα（今回）の場合には、ＣＦαはもとの値のままとし、マッピングについても前回マッピングを保持し、アップデートしない。図１７（ｂ）のマッピングについては、ＣＦα（前回）＞ＣＦα（今回）が成立する。したがって、ＣＦαの値を更新し、マッピングをＲＡＭに保存し、ＣＦα（Best Solution）として次のマッピングとの比較に用いる。
【００７９】
ＳＡでは、クーリングスケジュールにしたがって、この作業を温度毎に所定回数繰り返し、ＳＡのコンディションにしたがってマッピングを更新する。コストファクションについては、図１７（ｃ）、（ｄ）そして（ｅ）のようにマッピングを繰り返し、その都度計算する。図１７（ｃ）のときは、ＣＦαの値が２６から３２に上昇するためＣＦα（Best Solution）は変化しない。図１７（ｄ）のときは、ＣＦαの値が２２になるためＣＦα（Best Solution）を更新する。さらに図１７（ｅ）のときは、ＣＦαの値が２６に上昇するためＣＦα（Best Solution）は変化しない。この処理を一定回数繰り返し、できるだけ小さな値になるようにする。
【００８０】
図１１に戻って、ＳＡを開始するステップ５３において、全てのＰＥｓの割当てを再度ランダムにやり直す代わりに、限定された数（典型的には選択された１つのＰＥとそれに対応するＰＥ）のＰＥをスワップする（入れ替える）。そのために、ランダムにＰＥを選択し、そのＰＥに割り当てられたＦＢを、次に、ランダムに選択したＰＥに割当て、そのＰＥにＦＢが割り当てられていれば、その割り当てられたＦＢと入れ替える処理を行う。複数のセグメントを有するデバイス１では、この入れ替えの処理により、セグメント間の移動が許可されている可動セル（ムーバブルセル）については、セグメントを跨いだ移動（割り当ての変化）が含まれる。
【００８１】
ステップ５４において、ルーティング（接続ルート）をチェックし、ステップ５５においてコストファンクションＣＦ（ＣＦｎｅｗ）を計算する。ルーティングをチェックする段階（ステップ５４）では、セグメントを跨ぐルートについては、インターセグメントコネクション２２を担当するＤＬＶおよびＤＬＨが自動的に割り当てられる。
【００８２】
ステップ５６において、新たなマッピングがＳＡコンディションを満足する場合はステップ５８においてＣＦの値が更新され（ＣＦｂｅｓｔがＣＦｎｅｗに更新）、ステップ５９において、コンフィグレーションデータの基となるマッピング（マッピングデータ）が更新される。一方、新たなマッピングが、ＳＡコンディションを満足しない場合は、ステップ５７において、元のマッピングが選択され、ステップ５３に戻って、ＰＥｓの割当ての入れ替えを行う。
【００８３】
ＳＡコンディションの１つは、ＣＦの変化ｄＣＦが０より大きければ、新しいマッピングを採用することである。ＳＡコンディションの他の１つは、変化ｄＣＦが０以下であれば、アクセプタブルプロパビリティ（ＡＰ）として「ｅｘｐ（−ｄＣＦ／ｔｅｍｐ）」を計算し、そのときに発生された乱数よりも、ＡＰの値が大きければ、新しいマッピングを採用することである。マッピングの変化をより促進させるオプションが採用されている場合は、温度ファクタを除き、ＡＰは「ｅｘｐ（−ｄＣＦ）」により計算される。
【００８４】
ＳＡは、ステップ６０において終了条件が成立するまで繰り返される。終了条件は、温度が所定の値に達し、その温度でのマッピングの繰り返しが終了したことである。クーリングスケジュールの一例は、初期温度Ｔ０が１００００、終了温度Ｔｎが０．１であり、終了温度Ｔｎに達したｎ番目のサイクル（ｎサイクル、ｎは整数）が最後のサイクルとなる。ｎサイクル中のｉサイクルの温度Ｔｉは以下の式で与えられる。
Ｔｉ  ＝Ｔ０（Ｔｎ／Ｔ０）１／ｎ  ・・・（３）
各サイクルにおいてマッピングの変更を繰り返す数は、徐々に増加する。例えば、０サイクルは１０であり、サイクル毎に１．２倍になる。
【００８５】
ＳＡによる最適化が終了すると、ステップ６１において、最適化されたマッピングのデータ同期をタイミング解析機能３７ａにより解析する。ステップ６２において、メモリ３７ｂに格納されたＤＦＧ８２のデータ同期と比較する。ステップ６３において、データ同期に必要なＤＬＥを挿入する。ＤＬＥの残存数が十分にあり、ＤＬＥの挿入が成功すればＳＡによるマッピングの最適化は終了する。ＤＬＥが不足している場合は、ステップ４８に戻り、暫定的なマッピングの生成からやり直す。ランダムプロセスなので、異なる結果が得られる可能性があるからである。ＰＥの不足が明瞭であれば、ＤＦＧ８２の再生成から繰り返すことも可能である。
【００８６】
図１８〜図２３に、デバイス１にマッピングする例を示している。図１８は、マッピングするＤＦＧ８２を示す。このＤＦＧ８２は、ＰＥｓに割り当てるＵ１からＵ１４の１４個のＦＢを含んでいる。ＤＦＧ８２の中の接続ｄｉ、ｄｏはデータのインプット、アウトプットを示す。接続ｃｉ、ｃｏはキャリー信号のインプット、アウトプットを示す。さらに、接続ｎｘ、ｎｙは図のようなハードウエア上の隣接するＰＥ同士を接続ｎｙ→ｎｘの方向へ信号を入出力するアウトプット、インプットを示す。上記した様に、接続ｎｙと接続ｎｘが接続されたＰＥｓは、ハードウエア上で横一列に接続されなければならない。このため、プライオリティバケットにおいて、ＦＡＧに選択されるグループは、接続ｎｙ→ｎｘで接続されたＰＥｓである。
【００８７】
このＤＦＧ８２は、ＦＡＧとなるグループ１と、グループ２とを含んでいる。各グループのベースセルは、ハードウエア上で最も左側に位置する接続ｎｘへのインプット接続がなく、接続ｎｙへのアウトプット接続があるＰＥと定義する。グループ１は、Ｕ５、Ｕ６およびＵ７を含み、Ｕ５がベースセルである。グループ２は、Ｕ８およびＵ９を含み、Ｕ８がベースセルである。
【００８８】
さらに、各ＰＥに割り当てられるＦＢ（Ｕ５〜Ｕ１０）に設定された命令は全てＣＭＰＳＢであり、この命令を割り当て可能なＰＥは「ＥＸＣ」のみである。
【００８９】
図１９に、図１８のＤＦＧ８２に対応して生成されたプライオリティバケット３５ｂを示している。この例では、優先度は、ＰＥマトリクス１０に含まれるＰＥｓのタイプ毎の数による順位付けだけではなく、ＦＡＧのベースセルであることによるアップグレードを行なう。例えば、ＥＸＣに対するＰＥのタイプ毎の優先度が「３」であれば、ＥＸＣがベースセルであるＦＡＧの優先度は「６」になる。ＰＥのタイプ毎の優先度は、ＰＥマトリクスに用意されている数が少ない方が優先度は高い。他のタイプのＰＥであって、ＰＥマトリクス１０に用意されている数が多いタイプのＰＥに対する優先度は、ＥＸＣより低く、優先度が例えば「２」であれば、そのタイプのＰＥをベースセルとするＦＡＧの優先度は「４」になる。
【００９０】
ＰＥｓの内、ＬＤＢ、Ｃ１６Ｌ、Ｃ３２Ｌ、ＳＴＢ、Ｃ１６Ｓ，Ｃ３２ＳのＰＥに割り当てるＦＢ、すなわち、Ｕ１、Ｕ３、Ｕ４、Ｕ１１、Ｕ１３およびＵ１４は固定セルとして取り扱われる。したがって、残りのＦＢは、可動セルとして取り扱われる。
【００９１】
図２０に、図１９のプライオリティバケットを暫定的にマッピングした結果を示している。式（１）に示したＣＦにおいて、Ｃ１・Ｆ（Ｗ−intra）については１つのＭＵＸの消費に対する値を４、Ｃ２・Ｆ（Ｗ−inter）については１つのセグメントを跨ぐ配線の消費に対する値を６と定義する、このマッピングに対するＣＦは、１項目のセグメント内コスト（Intra segment cost）が（４×７）であり、２項目のセグメント間コスト（Inter segment cost）が（６×７）であり、以下の通り７０となる。
ＣＦ  ＝  （４×７）＋（６×７）
【００９２】
上述したように、セグメント構造を採用したデバイス１においては、各セグメントを跨ぐ配線については、セグメントの境界に配置されたディレイエレメントにより信号のタイミングを保障する構造になっている。したがって、セグメント境界を超えて配線するより、セグメント内で配線する方が遅延数は少なく、ディレイエレメントの消費も少ない。このため、インターセグメントの配線、すなわち、第２レベルのルーティングマトリクス２２の使用に対して、ＣＦにおけるペナルティが大きくなるようにしている。
【００９３】
具体的には図２０のマッピングにおいて、ＬＤＢからはじめの３つのＰＥからなるＥＸＣのグループ１へは同一セグメント内において２つの配線を使用する。次に、３つのＰＥからなるグループ１から２つのＰＥからなるグループ２へは、グループ１からの出力がセグメント内配線（２つ）であり、グループ２へ至る配線が２箇所でセグメントを跨ぐ配線（２つ）となる。グループ２から１つのＥＸＣへは、グループ２からの出力がセグメント内配線（２つ）であり、１つのＥＸＣへ至る配線が１箇所でセグメントを跨ぐ配線（２つ）となる。さらに、１つのＥＸＣからＳＴＢへの配線は、ＥＸＣからの出力がセグメント内配線（１つ）であり、ＳＴＢへ至る配線が１箇所でセグメントを跨ぐ配線（１つ）となる。
【００９４】
図２１から図２３に示したマッピングは、ＳＡの過程で表れる可能性のあるマッピングの幾つかの例である。図２１に示したマッピングのＣＦは１１２と増加するので、ＣＦの上昇が許容される確率に入らない限り、このマッピングは採用されない。一方、図２２または図２３に示したマッピングはＣＦが減少するので、この順番に現れたときには採用される。
【００９５】
デバイス１は、ＰＥマトリクス１０に配置されたＰＥｓが複数のセグメントＳ０〜Ｓ５に区分けされており、それぞれのセグメント内のＰＥｓは第１レベルのルーティングマトリクス（配線マトリクスあるいは配線群）により、信号が１サイクル以内に到達するように接続される。したがって、セグメント内の配置（割り当て）については、セグメント内の配線によるディレイあるいはタイミングのずれを考慮する必要はない。一方、セグメント間は、ディレイエレメント（ＤＬＶ、ＤＬＨまたはＤＬＸ）を含む第２レベルのルーティングマトリクス２２により接続される。このため、セグメント間の配線についての遅延は発生するが、遅延量はディレイエレメントにより制御され、その範囲で信号のタイミングは保証される。
【００９６】
デバイス１では、セグメント内のＰＥを接続する第１レベルのルーティングマトリクスの範囲内では、信号のタイミングは保証されるので、ランダムプロセスにより発生される新しいマッピングについて、新しいマッピングが発生される都度、信号のタイミングを検証する必要はない。また、第２レベルのルーティングマトリクスの範囲内では、遅延は増加するもののタイミングは所定の範囲に保証されるので、タイミングの調整はディレイを追加するか否かで解決できる範囲内である。このため、マッピングが最適化された後に、ディレイの追加の要否を検討するだけで足りる。したがって、第２レベルのルーティングを考慮しても、新しいマッピングについて、その都度、タイミングを検証したり、クリティカルパスを検証したりする必要はない。このため、ＳＡの反復するプロセスにおいては、コストファンクションを得るためにルーティングを検討する必要はあるが、タイミングの検証は不要であり、ＳＡを用いたマッピングの最適化に要する時間が短縮される。
【００９７】
さらに、最適化されたマッピングのタイミング収束を検討する過程において、マッピングに含まれるエレメントを再配置しないといけないような事態になると、ＳＡによりマッピングを最適化した効果は薄れる。上記のプロセスにおいては、最適化されたマッピングに対して、データ同期のために必要であればディレイエレメントを追加する処理が行われるだけであり、エレメントの再配置は不要である。さらに、ＤＦＧとのタイミング調整は、基本的にセグメントを跨ぐルーティングにより発生するものであり、セグメントを跨ぐ信号の遅延量の調整が、第２レベルのルーティングマトリクスに含まれるＤＬＶ、ＤＬＨまたはＤＬＸの遅延量を調整により完了すれば、新たなＤＬＥの割り当てを必要としない。
【００９８】
また、セグメントを跨ぐルーティングは、ＳＡによりマッピングを最適化する過程においては、第２レベルのルーティングマトリクス２２の使用を最小化するので第２レベルのルーティングマトリクスを使用することにより遅延量の増加を抑制できる。なお、最小化とは、ＣＦに含まれる第２レベルのルーティングマトリクスの使用を反映する項（上記の式（１）では第２項）の値が小さくなるようなマッピングを選択することである。ＳＡを含めた反復アルゴリズムは、マッピングを最適化するためのヒューリスティック（heuristic）な手法であり、ＰＥマトリクスに実装可能な全てのマッピングの中で第２レベルのルーティングマトリクスの使用が必ず最小になるマッピングが発見されることは意味しない。しかしながら、第２レベルのルーティングマトリクスの使用が最小または最小に近いマッピングが発見される可能性は十分に高い。
【００９９】
さらに、ＣＦは第１レベルのルーティングマトリクス２１の使用を抑える項も含んでいる。したがって、上記のＳＡの過程においては、第１レベルのルーティングマトリクス２１の使用も抑制され、ＰＥマトリクスに含まれるルーティングに関わるハードウエア資源の使用効率を向上できる。
【０１００】
セグメント化は、上述したように、セグメントの範囲内での配置配線の自由度を向上するのに適している。さらに、セグメント化により、信号を送受信するためのバス（ルーティングマトリクス）をセグメント毎に独立して使用することが可能となり、配線の使用効率を向上できるというメリットも含んでいる。ＰＥをセグメント化する構成は、ＡＬＵなどの機能を含む、均一な、あるいは均一に近い複数のＰＥあるいは論理ブロック（ＬＣＢ）が配置された再構成可能なデバイスにおいても導入できるであろう。また、縦横配線の繰り返しなどの均一な構成のルーティングマトリクスを備えたデバイスであっても、高抵抗の素子を導入したり、スイッチングなどの方法によりルーティングマトリクスをセグメント化できるデバイスにおいては、仮想的に第１レベルのルーティングマトリクスと第２レベルのルーティングマトリクスとを定義することにより、上記のようなマッピング方法を適用できるであろう。また、上述したマッピングに関する方法は、電気電子的な方法により信号を伝達するルーティングマトリクスに限らず、光を含めた他の情報伝達方式が適用されるルーティングマトリクスであっても良い。また、ＰＥｓの配置は、２次元の縦横の規則的な配列に限定されない。３方あるいは６方などに規則的にＰＥｓを配置することも可能である。さらに、多層化などの方法により、ＰＥｓを３次元に配置することも可能である。
【図面の簡単な説明】
【０１０１】
【図１】図１（ａ）は、再構成可能なデバイスの一例の概略構成を示し、図１（ｂ）は、ＰＥマトリクスの概略を示し、図１（ｃ）および図１（ｄ）は、ＰＥマトリクスを動的に再構成する様子を示す。
【図２】ＰＥマトリクスの配列を示す。
【図３】ＰＥマトリクスに配置されたＰＥｓのタイプを示す。
【図４】ＰＥマトリクスの配置を拡大して示す。
【図５】セグメント内の配線（イントラセグメント配線）を示す。
【図６】セグメント内の配線の異なる例を示す。
【図７】セグメント間の配線（インターセグメント配線）を示す。
【図８】回路デザインをデバイスにマッピングする過程を示す。
【図９】配置配線支援システムの概略構成を示す。
【図１０】配置配線支援システムの処理の概要を示すフローチャート。
【図１１】マッピングの処理の概要を示すフローチャート。
【図１２】マッピングを説明するためのハードウエア（デイバス）の簡易な例を示す。
【図１３】ハードウエア情報の一例を示す。
【図１４】ＤＦＧの一例を示す。
【図１５】図１５（ａ）は、ＤＦＧの機能を解析した例、図１５（ｃ）は、ＤＦＧの接続を解析した例を示す。
【図１６】プライオリティバケットの一例を示す。
【図１７】図１７（ａ）〜図１７（ｅ）は、図１２に示したデバイスに対し、図１６に示したプライオリティバケットにしたがって、図１４に示したＤＦＧをマッピングした幾つかの例を示す。
【図１８】ＤＦＧの異なる例を示す。
【図１９】プライオリティバケットの異なる例を示す。
【図２０】図３に示したＰＥマトリクスに対し、図１９に示したプライオリティバケットにしたがって、図１８に示したＤＦＧを暫定的にマッピングした例を示す。
【図２１】ＳＡの過程で得られるマッピングの一例を示す。
【図２２】ＳＡの過程で得られるマッピングの異なる例を示す。
【図２３】ＳＡの過程で得られるマッピングのさらに異なる例を示す。
【図１】
2008026731.tif 000003
【図２】
2008026731.tif 000004
【図３】
2008026731.tif 000005
【図４】
2008026731.tif 000006
【図５】
2008026731.tif 000007
【図６】
2008026731.tif 000008
【図７】
2008026731.tif 000009
【図８】
2008026731.tif 000010
【図９】
2008026731.tif 000011
【図１０】
2008026731.tif 000012
【図１１】
2008026731.tif 000013
【図１２】
2008026731.tif 000014
【図１３】
2008026731.tif 000015
【図１４】
2008026731.tif 000016
【図１５】
2008026731.tif 000017
【図１６】
2008026731.tif 000018
【図１７】
2008026731.tif 000019
【図１８】
2008026731.tif 000020
【図１９】
2008026731.tif 000021
【図２０】
2008026731.tif 000022
【図２１】
2008026731.tif 000023
【図２２】
2008026731.tif 000024
【図２３】
2008026731.tif 000025
【国際調査報告】
2008026731.tif 000026
2008026731.tif 000027