JP5157514B2

JP5157514B2 - 構成情報生成装置、構成情報生成制御方法、及びプログラム

Info

Publication number: JP5157514B2
Application number: JP2008039872A
Authority: JP
Inventors: 亨粟島
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2008-02-21
Filing date: 2008-02-21
Publication date: 2013-03-06
Anticipated expiration: 2028-02-21
Also published as: US8032853B2; JP2009200779A; US20090212817A1

Description

本発明は、論理的構成を変更する機能を有する論理回路装置に対し、書き込み処理をする情報の総量を圧縮するのに好適な構成情報生成装置、構成情報生成制御方法、及び、これらをコンピュータにて実現するためのプログラムに関する。

論理的構成を変更する（再構成可能な）機能を有する論理回路装置として、ＦＰＧＡ（Field Programmable Gate Array）が知られている。ＦＰＧＡのなかには、連長圧縮法を用いてデータを圧縮することにより、高速な入出力動作を実現しているものがある（例えば、特許文献１参照）。

また、構成情報（フレーム）に含まれる繰り返し部分の情報を省略することにより、情報を圧縮しているものがある（例えば、特許文献２参照）。構成情報の一部を省略することにより、書き込み処理をする情報の総量を圧縮している。
特開２００３−３４７９２７号公報特開２００１−２８５３６号公報（図２）

しかしながら、特許文献１及び２に開示されている構成では、構成情報内に繰り返し部分がある必要があった。また、異なる複数の構成情報間にまたがって情報が繰り返されている場合、情報を圧縮することができなかった。従って、複数の構成情報を備える場合に、当該構成情報の書き込み総量を圧縮するのに好適な新たな方法が求められている。

本発明は、上記問題に鑑みてなされたものであり、論理的構成を変更する機能を有する論理回路装置に対し、書き込み処理をする情報の総量を圧縮するのに好適な構成情報生成装置、構成情報生成制御方法、及び、これらをコンピュータにて実現するためのプログラムを提供することを目的とする。

上記の目的を達成するため、本発明の第１の観点に係る論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有する構成情報生成装置は、
前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶される記憶部と、
前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出部と、
前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成部と、
前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成部と、を備える。

上記の目的を達成するため、本発明の第２の観点に係る記憶部と、差分情報抽出部と、グラフ生成部と、順序情報生成部と、を有する論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有する構成情報生成装置が実行する構成情報生成制御方法は、
前記記憶部には、前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶され、
前記情報抽出部が、前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出工程と、
前記グラフ生成部が、前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成工程と、
前記順序情報生成部が、前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成工程と、を備える。

上記の目的を達成するため、本発明の第３の観点に係るプログラムは、
論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有するコンピュータを、
前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶される記憶部と、
前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出部と、
前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成部と、
前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成部と、として機能させる。

本発明によれば、論理的構成を変更する機能を有する論理回路装置に対し、書き込み処理をする情報の総量を圧縮することができる。

以下では、本発明の構成情報生成装置の実施形態の一つについて説明するが、当該実施形態は本発明の原理の理解を容易にするためのものであり、本発明の範囲は、下記の実施形態に限られるものではなく、当業者が以下の実施形態の構成を適宜置換した他の実施形態も、本発明の範囲に含まれる。

（実施形態１）
まず、論理的構成を変更する（再構成可能な）機能を有する論理回路装置に対し、構成情報を書き込むための前提となる基本的性質を、図３から図５を参照して説明する。
図３（ａ）及び（ｂ）は、当該論理回路装置が有する構成情報の一例である。構成情報は、一般的に構成情報メモリのアドレスとデータとの組で表現される。図３から図５に示す構成情報は５ワードで構成され、各ワードは１６ビットのビット幅を有する。

図３（ａ）及び（ｂ）に示す構成情報Ａ及びＢは、共通な構成情報を有している。この場合、図３（ｃ）においてハッチングを施した構成情報が、構成情報Ａ及びＢの共通データであり、２ワード存在する。
当該共通データが存在する場合、共通データ以外のデータ（差分データ）が構成情報に書き込まれる。

共通データについては書き込みを行わずに、構成情報Ａから構成情報Ｂに書き換える方法を、図４を参照して説明する。図４（ａ）に示す構成情報Ａに、図４（ｂ）に示す構成情報Ｂ１が含む差分データとなる３ワードを書き込むことにより、図４（ｃ）に示す構成情報Ｂを生成することができる。
上記と同様にして、構成情報Ｂから構成情報Ａに書き換える方法を、図５を参照して説明する。図５（ａ）に示す構成情報Ｂに、図５（ｂ）に示す構成情報Ａ１が含む差分データとなる３ワードを書き込むことにより、図５（ｃ）に示す構成情報Ａを生成することができる。
以上説明したように、共通データ以外のデータ（差分データ）について構成情報を書き換えることにより、構成情報の書き込み総量を圧縮することができる。
以下、これらの構成情報の書き込み方法を前提とする。

本発明の第１の実施形態に係る構成情報生成装置について図１を参照して説明する。構成情報生成装置は、当該装置が生成した構成情報を論理回路装置に書き込む。

本実施形態の構成情報生成装置１００は、図１に示すように、入出力部１１０と、処理部１２０と、差分情報抽出部１２１と、差分関係グラフ生成部１２２と、書込順序情報生成部１２３と、書込情報生成部１２４と、記憶部１３０と、差分情報記憶部１３１と、差分関係グラフ記憶部１３２と、書込順序情報生成部１３３と、を備える。

入出力部１１０は、外部装置（図示せず）から複数の構成情報を読み込み、当該構成情報を後述する処理部１２０に渡す。また、入出力部１１０は、処理部１２０の処理が完了した後、構成情報の書き込み総量を圧縮するための書き込み順序と差分情報とを外部装置に渡す。

処理部１２０は、差分情報抽出部１２１と、差分関係グラフ生成部１２２と、書込順序情報生成部１２３と、書込情報生成部１２４と、を備える。また、ここでは図示しないが、処理部１２０は、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）等を備える。

差分情報抽出部１２１は、図３（ｃ）に示すように、入出力部１１０から入力された構成情報の全ての組について差分情報を抽出する。また、差分情報抽出部１２１は、当該差分情報を差分情報記憶部１３１に格納する。

差分関係グラフ生成部１２２は、差分情報記憶部１３１に格納された差分情報を参照し、全構成情報に対する差分関係グラフを作成する。また、差分関係グラフ生成手段１２２は、当該差分関係グラフを差分関係グラフ記憶部１３２に格納する。

ここで、差分関係グラフとは、図６（ａ）及び（ｂ）に示すように、各構成情報の関係を、ノード２０１と、エッジ２０２と、エッジの重み２０３と、で表現したグラフである。エッジ２０２は全てのノード２０１間に作成される。また、各エッジ２０２は、エッジ２０２の一方の構成情報から他方の構成情報に再構成される場合、書き込みが必要となる構成情報のワード数に基づいて重み付けされる。

書込順序情報生成部１２３は、差分関係グラフ記憶部１３２に格納された差分関係グラフ情報を参照し、書き込む構成情報の総量が最小となるような書き込み順序を生成する。また、書込順序情報生成部１２３は、当該書き込み順序方法を書込順序情報記憶部１３３に格納する。

当該書き込み順序を生成する処理は、差分関係グラフ上で全てのノード２０１を１回ずつ通過し、かつ通過するエッジの重み２０３の総和が最小となるような巡回路を求める問題に帰着できる。この問題は、「巡回セールスマン問題」の解法を利用して解くことができる（ＵＲＬ：http://en.wikipedia.org/wiki/Traveling_salesman_problem）。

書込情報生成部１２４は、書込順序情報記憶部１３３に格納された順序情報を参照し、書き込む構成情報の総量が最小となるような差分書き込み用の構成情報を生成する。

次に、本実施形態に係る構成情報生成装置１００の動作について、図２、図６及び図７を参照して説明する。

まず、入出力部１１０から与えられた複数の構成情報は、差分情報抽出部１２１に供給される。差分情報抽出部１２１は、例えば図３（ａ）及び（ｂ）に示す全ての構成情報の組について差分情報を抽出し、差分情報記憶部１３１に格納する（ステップＳ１１）。

ここで差分情報記憶部１３１に格納される差分情報とは、図４及び図５に示すように、１組の構成情報である構成情報Ａ及び構成情報Ｂについて、構成情報Ａから構成情報Ｂに再構成するときに書き込みが必要な最小の構成情報Ｂ１とそのワード数、及び、構成情報Ｂから構成情報Ａに再構成するときに必要な最小の構成情報Ａ１とそのワード数を含む。

次に、差分関係グラフ生成部１２２は、差分情報記憶部１３１に格納された差分情報を参照し、構成情報の差分関係グラフを作成する。また、差分関係グラフ生成部１２２は、当該差分関係グラフを差分関係グラフ記憶部１３２に格納する（ステップＳ１２）。

ここで、差分関係グラフとは、図６（ａ）及び（ｂ）に示すように、各構成情報をノード２０１で、構成情報間の関係をエッジ２０２で、表現したグラフである。エッジ２０２は全てのノード２０１間に作成される。また、各エッジ２０２は、エッジ２０２の一方の構成情報から他方の構成情報に再構成される場合、書き込みが必要となる構成情報のワード数に基づいて重み付けがなされる。

次に、書込順序情報生成部１２３は、差分関係グラフ記憶部１３２に格納された差分関係グラフを参照し、再構成のために書き込みが必要な構成情報の総量を最小化する書込順序情報を生成する。また、書込順序情報生成部１２３は、当該書込順序情報を書込順序情報記憶部１３３に格納する（ステップＳ１３）。

ステップＳ１３において、図７（ａ）に示すように、差分関係グラフ上で全てのノード２０１を１回ずつ通過し、かつ通過するエッジの重み２０３の総和が最小となるような巡回路２０４を求める問題に帰着できる。この問題は、「巡回セールスマン問題」の解法を利用して解くことができる。ここでは、重みの総和が１５で最小となる巡回路２０４が求められ，この巡回路２０４に基づいて構成情報の書込順序情報が生成される。

本実施形態では、構成情報生成装置１００上で複数の回路構成を任意の順序で繰り返し実行する場合を扱っており，構成情報の書込順序生成部１２３によって求められる書込順序情報は，始点と終点とを定めない巡回順序となる。

また、図４及び図５に示すように、構成情報Ａから構成情報Ｂ、また構成情報Ｂから構成情報Ａ、というように書き換えの向きが変わっても差分のワード数に変化はない。このため、結果として求められる書き込み順序は、図７（ｂ）及び（ｃ）に示すように、正順と逆順の２通りの巡回順序となる。

最後に、書込情報生成部１２４は、差分情報記憶部１３１と書込順序情報記憶部１３３とに格納された差分情報と書込順序情報とを参照して、再構成可能な構成情報生成装置１００上で複数の回路構成を任意の順序で繰り返し実行する場合に必要となる構成情報の総量が最小となる差分書込用の構成情報を生成する。また、書込情報生成部１２４は、当該構成情報を入出力部１１０に出力し、処理を終了する（ステップＳ１４）。

ステップＳ１４において、ステップＳ１３で求められた２通りの巡回順序のどちらを選択するか、またどの構成情報を始点と定めるかは、入出力部１１０から与えるか、または差分書込用の構成情報生成手段１２４が適切な指標に基づいて自動的に決定される。

以上説明したように、本発明によれば、全ての構成情報の組に対して差分情報を抽出し、これに基づいた差分関係グラフに基づいて処理を行うというように構成されているため、複数（２つ以上）の構成情報について、差分書込用の構成情報を生成することができる。
また、差分関係グラフ上で重みの総和が最小となる巡回路を求めることで、書き込み順序を求めるというように構成されているため、書き込み総量が最小となるような差分書込用の構成情報を生成することができる。

（実施形態２）
次に、第２の実施形態に係る構成情報生成装置１００について図８を参照して説明する。実施形態２の構成情報生成装置１００は、図１に示した構成情報生成装置１００の処理部１２０に差分関係グラフ補正部１２５を追加した構成となる。本実施形態は、構成情報生成装置１００上で複数の回路構成を任意の順序で１回だけ実行するものである。

差分関係グラフ補正部１２５は、差分関係グラフ記憶部１３２に格納された差分関係グラフを参照し、図１０（ｂ）に示す１つのダミーノード２０５を差分関係グラフに挿入する。また、差分関係グラフ補正部１２５は、差分関係グラフ記憶部１３２に差分関係グラフを再び格納する。

次に、本実施形態に係る構成情報生成装置１００の動作について、図９から図１１を参照して説明する。なお、ステップＳ２１及びステップＳ２２においては、ステップＳ１１及びステップ１２と同様の処理がなされる。またステップＳ２５においては、ステップＳ１４と同様の処理がなされる。

差分関係グラフ補正部１２６は、差分関係グラフ記憶部１３２に格納された差分関係グラフを参照し、図１０（ｂ）に示すように、１つのダミーノード２０５を差分関係グラフに挿入する。また、差分関係グラフ補正部１２５は、差分関係グラフ記憶部１３２に差分関係グラフを再び格納する。さらに、差分関係グラフ補正部１２６は、図１０（ｂ）に示すように、挿入したダミーノード２０５とそれ以外の全てのノード２０１との間に新たにダミーエッジ２０６を設け、エッジの重み２０３を「０」で初期化する（ステップＳ２３）。

次に、書込順序情報生成部１２３は、差分関係グラフ記憶部１３２に再び格納された差分関係グラフを参照し、再構成のために書き込みが必要な構成情報の総量を最小化する書込順序情報を生成する。また、書込順序情報生成部１２３は、当該書込順序情報を書込順序情報記憶部１３３に格納する（ステップＳ２４）。

ステップＳ２４において、図１１（ａ）に示すように、差分関係グラフ上で全てのノード２０１を１回ずつ通過し、かつ通過するエッジの重み２０３の総和が最小となるような巡回路２０４を求める問題に帰着できる。結果として求められる書き込み順序は、図１１（ｂ）及び（ｃ）に示すように、正順と逆順の２通りの巡回順序となる。

ステップＳ２４では、１つのダミーノード２０５を挿入して差分関係グラフを補正している。その結果、ステップＳ２４で求められるエッジの重み２０３の総和最小の巡回路２０４は必ずダミーノード２０５を含む。巡回路上でダミーノード２０５の前後のダミーエッジ２０６の重み２０３は０で初期化されており、巡回路２０４のエッジの重み総和に影響を与えていない。したがって、求められた巡回路２０４から、ダミーノード２０５を取り除くことで、エッジの重みの総和が最小であって、始点と終点を有する構成情報書き込み順序が生成できる。

なお、本発明は上記実施の形態に限定されず、種々の変形及び応用が可能である。

構成情報の数は、２つに限定されず、２以上で任意である。
構成情報のデータは、５ワードに限定されず、任意である。また、各ワードのビット幅は、１６ビットに限定されず、任意である。

巡回路を求める方法は、線形計画法、焼きなまし法、遺伝的アルゴリズム等、任意である。

本発明の実施形態１に係る構成情報生成装置の構成を示すブロック図である。実施形態１に係る構成情報生成装置の動作を説明するフローチャートである。構成情報例を示す図である。構成情報を書き換える方法を説明する図である。（ａ）は書き換える前の構成情報を示し、（ｂ）は差分データを含む構成情報を示し、（ｃ）は書き換えた後の構成情報を示す図である。構成情報を書き換える方法を説明する図である。（ａ）は書き換える前の構成情報を示し、（ｂ）は差分データを含む構成情報を示し、（ｃ）は書き換えた後の構成情報を示す図である。（ａ）は実施形態１に係る差分関係グラフを示し、（ｂ）は重み付けのある差分関係グラフを示す図である。（ａ）は実施形態１に係る書き込み巡回路を示す図であり、（ｂ）は正順の巡回路を示し、（ｃ）は逆順の巡回路を示す図である。本発明の実施形態２に係る構成情報生成装置の構成を示すブロック図である。実施形態２に係る構成情報生成装置の動作を説明するフローチャートである。（ａ）は実施形態２に係る差分関係グラフを示し、（ｂ）は重み付けのある差分関係グラフを示す図である。（ａ）は実施形態２に係る書き込み巡回路を示す図であり、（ｂ）は正順の巡回路を示し、（ｃ）は逆順の巡回路を示す図である。

符号の説明

１００構成情報生成装置
１１０入出力部
１２０処理部
１２１差分情報抽出部
１２２差分関係グラフ生成部
１２３書込順序情報生成部
１２４書込情報生成部
１２５差分関係グラフ補正部
１３０記憶部
１３１差分情報記憶部
１３２差分関係グラフ記憶部
１３３書込順序情報記憶部

Claims

論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有する構成情報生成装置において、
前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶される記憶部と、
前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出部と、
前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成部と、
前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成部と、
を備えることを特徴とする構成情報生成装置。
前記グラフ生成部は、前記構成情報に基づき、ノードと、当該ノードに接続されるエッジと、当該エッジの重みと、からなる関係グラフを生成する、
ことを特徴とする請求項１に記載の構成情報生成装置。
前記順序情報生成部は、巡回セールスマン問題として、前記エッジの重みの総和が最小となるような巡回路情報を生成する、
ことを特徴とする請求項１又は２に記載の構成情報生成装置。
前記関係グラフを補正するグラフ補正部と、をさらに備え、
前記グラフ補正部は、ノードを新たに生成し、当該ノードに接続されるエッジの重みを「０」とすることにより、前記関係グラフを補正する、
ことを特徴とする請求項１乃至３のいずれか１項に記載の構成情報生成装置。
記憶部と、差分情報抽出部と、グラフ生成部と、順序情報生成部と、を有する論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有する構成情報生成装置が実行する構成情報生成制御方法であって、
前記記憶部には、前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶され、
前記情報抽出部が、前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出工程と、
前記グラフ生成部が、前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成工程と、
前記順序情報生成部が、前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成工程と、
を備えることを特徴とする構成情報生成制御方法。
論理的構成を変更する機能を有する論理回路装置に対し、書き込み機能を有するコンピュータを、
前記論理的構成を定義する複数の構成情報と、差分情報と、関係グラフと、順序情報と、が記憶される記憶部と、
前記記憶部に記憶された前記複数の構成情報間との差分情報を抽出する差分情報抽出部と、
前記差分情報抽出部により抽出された差分情報に基づいて、前記構成情報間のつながりを示す関係グラフを生成するグラフ生成部と、
前記グラフ生成部により生成された前記関係グラフを巡回する順序情報を生成する順序情報生成部と、
として機能させることを特徴とするプログラム。