(57)【要約】【課題】無駄な配線の使用を抑制可能にした資源再配置装置を提供する。【解決手段】演算機能および配線機能を共有する再構成可能資源を複数備えた装置への機能割当を再配置する資源再配置装置であって、各再構成可能資源について、演算機能のみが割り当てられた第１の状態、配線機能のみが割り当てられた第２の状態、演算機能および配線機能が割り当てられた第３の状態、ならびに演算機能および配線機能のいずれも割り当てられていない空状態のうち、いずれに設定されているかを記憶する記憶手段と、各再構成可能資源の状態を参照し、第２の状態の再構成可能資源が存在する場合、第１または第３の状態の再構成可能資源の演算機能を空状態の再構成可能資源に順次移動させ、第２の状態の再構成可能資源と空状態の再構成可能資源とが連続的に配置されるように構成を変更することにより、第２の状態の再構成可能資源を空状態に変更する機能手段と、を有する。【選択図】図１
2016063463.tif 000002
【特許請求の範囲】
【請求項１】
演算機能および配線機能を共有する再構成可能資源を複数備えた装置に対して、割り当てられた前記演算機能および配線機能を再配置させる資源再配置装置であって、
複数の前記再構成可能資源のそれぞれについて、前記演算機能のみが割り当てられた状態である第１の状態、前記配線機能のみが割り当てられた状態である第２の状態、前記演算機能および配線機能が割り当てられた状態である第３の状態、ならびに前記演算機能および配線機能のいずれも割り当てられていない状態である空状態のうち、いずれの状態に設定されているかを記憶する記憶手段と、
前記記憶手段が記憶する、各再構成可能資源の前記状態を参照し、前記第２の状態の再構成可能資源が存在する場合、前記第１または第３の状態の再構成可能資源の演算機能を前記空状態の再構成可能資源に順次移動させ、前記第２の状態の再構成可能資源と前記空状態の再構成可能資源とが連続的に配置されるように構成を変更することにより、前記第２の状態の再構成可能資源を前記空状態に変更する機能手段と、
を有する資源再配置装置。
【請求項２】
請求項１記載の資源再配置装置において、
前記機能手段は、
前記第１または第３の状態の再構成可能資源のうち、現在の時刻から所定の時間内に前記演算機能が除去される予定である使用終了予定の再構成可能資源がある場合、該使用終了予定の再構成可能資源を、前記演算機能を前記空状態の再構成可能資源に移動させる際の移動元の候補から除外する、資源再配置装置。
【請求項３】
請求項１または２記載の資源再配置装置において、
前記機能手段は、
前記第２の状態の再構成可能資源を前記空状態に順次変更する過程で、所定の機能の資源割り当ての要求がある場合、該所定の機能に必要な再構成可能資源の数よりも前記空状態の再構成可能資源の数が大きくなると、連続的に配置された空状態の再構成可能資源を前記所定の機能に順次割り当てる、資源再配置装置。
【請求項４】
請求項１〜３のいずれか１項記載の資源再配置装置において、
前記機能手段は、
前記第１または第３の状態の再構成可能資源の演算機能を前記空状態の再構成可能資源に順次移動させる際、リング状に配置された複数の再構成可能資源において、連続的に配置された空状態の再構成可能資源の両端のそれぞれから前記リング状にたどって基準点まで前記第２の状態の再構成可能資源の数をカウントし、カウント数が大きい方の前記第１または第３の状態の再構成可能資源を前記演算機能の移動元として選択するルールにしたがって、該移動元を選択する方向を決定する、資源再配置装置。
【請求項５】
請求項４記載の資源再配置装置において、
前記機能手段は、
次の前記移動元を選択する際、前記ルールによって決定された方向の履歴と前記第２の状態の再構成可能資源の配置とに基づいて、次の前記移動元を選択する方向を決定する、資源再配置装置。
【請求項６】
演算機能および配線機能を共有する再構成可能資源を複数備えた装置に対して、割り当てられた前記演算機能および配線機能を再配置させるための資源再配置方法であって、
複数の前記再構成可能資源のそれぞれについて、前記演算機能のみが割り当てられた状態である第１の状態、前記配線機能のみが割り当てられた状態である第２の状態、前記演算機能および配線機能が割り当てられた状態である第３の状態、ならびに前記演算機能および配線機能のいずれも割り当てられていない状態である空状態のうち、いずれの状態に設定されているかを記憶し、
記憶した各再構成可能資源の前記状態を参照し、前記第２の状態の再構成可能資源が存在する場合、前記第１または第３の状態の再構成可能資源の演算機能を前記空状態の再構成可能資源に順次移動させることで、前記第２の状態の再構成可能資源と前記空状態の再構成可能資源とが連続的に配置されるように構成を変更し、
前記空状態の再構成可能資源に隣接する前記第２の状態の再構成可能資源を前記空状態に変更する、資源再配置方法。
【請求項７】
請求項６記載の資源再配置方法において、
前記第１または第３の状態の再構成可能資源のうち、現在の時刻から所定の時間内に前記演算機能が除去される予定である使用終了予定の再構成可能資源がある場合、該使用終了予定の再構成可能資源を、前記演算機能を前記空状態の再構成可能資源に移動させる際の移動元の候補から除外する、資源再配置方法。
【請求項８】
請求項１〜５のいずれか１項記載の資源再配置装置の記憶手段および機能手段としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算機能と配線機能を共用する再構成可能部品（再構成可能資源）を複数組み合わせた装置において、演算機能を変更する際に、配線機能の停止を伴ってしまうような、再構成可能資源に対する演算機能の再配置の技術に関する。
【背景技術】
【０００２】
再構成可能部品（再構成可能資源（以下では、単に「資源」と称する））に演算機能の割り当てを行う場合、従来技術では、複数の資源を組み立てて一つの処理を行うような割り当てを行う際にも、割当を行う資源の配置を事前に連続的に整理することはなく、割当可能な資源が点在している状態であっても、個別に再構成を行っていた（非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Takuya Otsuka et al., "An Image Recognition System for Multiple Video Inputs over a Multi-FPGA System", IEEE 6th Internarional Symposium on Embedded Multicore SoCs, September 20, 2012
【発明の概要】
【発明が解決しようとする課題】
【０００４】
割当を行うことができる資源が連続的に配置されていない状態で、複数の資源を必要とする機能割り当てを行うと、資源間を接続する配線が交差することが多くなり、そのため、配線がより多く必要になってしまい有限の配線を十分に活用できない。この状況を、以下に、図面を参照して説明する。
【０００５】
図１１は本発明に関連する再構成可能装置の構成例を示す図である。再構成可能装置は複数の資源を備えた装置である。図１１に示す再構成可能装置は、固定的な配線の上、例えば、１枚のプリント基板の上に、１つのゲートウェイ（ＧＷ）１０と、複数（Ｎ個）の資源２０とが設けられている。資源２０は、例えば、ＦＰＧＡ（Field Programmable Gate Array）を備えた構成である。図１１において資源２０に記載された１〜Ｎは資源毎に異なる識別番号とし、以下では、Ｎ個の資源を識別番号に対応してＦ1〜ＦNで表す。
隣接する資源間、ＧＷ１０と隣接する資源２０との間、および、ＧＷ１０と他のプリント基板のＧＷとの間のそれぞれに配線が予め設けられ、また、資源２０およびＧＷ１０には隣接する他の資源またはＧＷとの接続／非接続を切り替えるスイッチ（不図示）が予め設けられ、各スイッチのオン／オフおよび各資源の機能割当が制御装置（不図示）によって設定される。その構成例が非特許文献１に開示されているため、ここでは、その詳細な説明を省略する。
資源間は、ＧＷ１０も含めて互いに逆向きの入出力関係で予め配線されており、資源の中で入出間を直結することによって右隣あるいは左隣の資源の出力もしくは伝送信号を、さらに左あるいは右隣に伝送する機能、資源の入力として受け取る、資源からの出力として送出するなどを選べるように構成されている。図１１で説明すると、例えば、資源Ｆ2は、左隣が資源Ｆ1であり、右隣が資源Ｆ3である。資源Ｆ1は、左隣がＧＷ１０であり、右隣が資源Ｆ2である。資源ＦNは、左隣が資源ＦN-1であり、右隣がＧＷ１０である。また、ＧＷ１０には、プリント基板外部からの入力信号を、所定本数ごとに、右隣の資源Ｆ1に伝送するか、他のプリント基板のＧＷに伝送するかを選択する機能、また、右隣の資源Ｆ1もしくは左隣の資源ＦNから伝送もしくは出力された信号を、左隣の資源ＦNもしくは右隣の資源Ｆ1への出力として伝送する仕組みが設けられている。なお、ＧＷ１０の右隣の資源はＦ1に相当し、左隣の資源はＦNに相当する。
【０００６】
資源への機能割当の手順の一例を説明する。図１２〜図１５は図１１に示した装置における資源への機能割当の手順を示す図である。
図１２は各資源の初期状態を示す。初期状態においては、全ての資源は不使用かつ、その資源とＧＷとの配線も、またその資源を通過する配線もない、状態である。それぞれの資源についての、これらの状態を、記号q-（キュー・マイナス）で表すこととする。
図１３は、資源Ｆ1〜ＦNのうち、最も左にある資源Ｆ1に演算機能を割り当てる操作を行ったところを示す図である。機能割当は、上記のように、制御装置（不図示）によって行われる。資源Ｆ1に機能割り当てが行われたが、資源Ｆ1とＧＷ１０との配線が行われていないため、Ｆ1はまだ使用中ではなく、状態q0 に遷移している。その他の全ての資源は、まだq-（不使用かつ無配線）の状態にある。
【０００７】
図１４は、資源Ｆ1〜ＦNのうち、最も左にある資源Ｆ1に発着配線を行い、使用を開始した状態としたところを示す図である。このとき、資源Ｆ1は使用中となるが、通過配線はない状態となる。この状態をq1とする。ここで、発着配線とは、その資源に到着、もしくは、その資源から出発する配線を意味し、図１４に示す５０ａ、５０ｂ は資源Ｆ1にとっての発着配線である。なお、例えば、Ｆ1から出発する配線を、図１４に示す５０ｂではなく、資源Ｆ2〜ＦNを経由してＧＷ１０に戻る配線にすることも考え得るが、ここでは、そのような配線を考えないものとする。すなわち、上記q1の状態をとる資源が必ず存在するものとする。発着配線は、上記のように、制御装置（不図示）によって行われる。
図１５は、資源Ｆ1〜ＦNのうち、最も左にある資源Ｆ1から２番目にある資源Ｆ2に機能の割り当ておよび発着配線を行い、資源Ｆ2の状態もq1にしたところを示す図である。その結果、資源Ｆ1には５０ｃ、５０ｄで示す通過配線が生じ、Ｆ1は状態q3に遷移する。状態q3については後で説明する。ここで、通過配線とは、その資源に有限個数先で隣接する資源、もしくはＧＷ１０に発着点を持つ配線であって、その資源を経由するものとする。
【０００８】
上述のようにして、各資源の状態が遷移していくが、その状態遷移図を図１６に示す。全ての資源は、最初、まったく機能が割り当てられていない状態、q-であるが、機能書込みによって、状態q0に遷移する。状態q0は、通過配線も発着配線も割り当てられておらず、つまり、その資源が使用されていないことを意味し、この状態においてのみ、なんらの制約もなく機能書換が可能である。状態q0の資源に、発着配線を割り当てた場合は、資源は使用中となり、状態q1に遷移する。状態q1は、通過配線はなく、発着配線がある、すなわち資源使用中であることを意味する。この状態では、資源そのものが使用中であるから、即座に機能書換を行うことができない。もし状態q1の資源に機能書換を行った場合、処理に何らかの不具合を生じることになる。同じく状態q0の資源に、通過配線を割り当てた場合は、資源は使用中ではないが、通過配線を担うことを意味する状態q2に遷移する。この状態でも、通過配線が使用中であるから、当該資源の機能書換を行うことはできない。機能書換を行った場合には、処理（通過配線が担う伝送）になんらかの不具合を生じることになる。状態q1の資源にさらに通過配線を割り当てた場合、また、状態q2の資源の機能を発着配線の割り当てによって使用開始した場合、には、状態q3に遷移する。状態q3はその資源自身が使用中であり、かつ、その資源の通過配線も使用中であることを意味する。もちろん、この状態q3においても、機能書換を行うことはできない。
なお、これらの状態遷移は、図１６を見てわかるように、可逆的である。また、状態q0の資源を「空資源」と称する場合もある。各資源は、空資源（実際に機能を書き込んだ後であっても状態がq0）であるときのみ、書き換えが可能である。
【０００９】
図１７および図１８は、図１５に示した状態の後、資源Ｆ2よりも右側の資源にも機能が順次割り当られる様子を示す図である。図１９は、全ての資源が使用されていることを示す図である。その後、資源のうちのいくつかが、使用終了となり、不使用の状態q2あるいはq1に遷移したことを、図２０に示す。不使用となる資源は、外部からの要求によって決まるものであり、かならずしも連続的に配置されるとは限らない。
図２１はいくつかの資源が不使用・通過配線あり（q2）になった場合の一例を示す図である。図２１では、Ｆ4，Ｆ7，ＦN-3の３つの資源が不使用・通過配線あり（q2）となっている。これら３つの資源に機能書換操作を施し、その後、それぞれへの発着配線を行い、q3に遷移させるが、機能書換を行うためには、通過配線のないq0の状態にしなければならない。その具体的な手順を図２２、図２３を参照して説明する。図２２は、資源Ｆ6の配線を迂回させたことを示す。さらに、図２３に示すように迂回を行い、資源Ｆ4の通過配線をなくすことにより、状態q0に遷移させることが可能となる。結果として、この状態のときに、Ｆ4の機能書換を行うことができる。
【００１０】
さて、従来技術では、もし図２２の３つの資源が必要となる機能を構成しようとした場合、前述の手順により、資源Ｆ4の機能を書き換え、続いて、同様の手順によって、資源Ｆ7，ＦN-3の機能書換も行って、最後に、これらそれぞれへの発着配線を行うこと、すなわち、状態をq3にすること、という方法がとられる。その場合、例えば、これら３つの資源からなる構成のために通過配線を負担する資源の個数は、（Ｎ−９）個となる。仮に、これら３つの資源が連続した配置にあった場合には、この個数が０となることを考えると、資源における配線機能の利用が効率的ではないことがわかる。これは、使用した資源の配置が連続（全てが相互に隣接）していなかったことに起因したものである。すなわち、機能を構成しようとする際、空資源の配置が、必要となる個数に対して十分連続していないまま、機能書換を始めてしまうこと、また、そもそも十分な個数の連続した空資源を確保できないこと、が従来技術の持つ課題である。
【００１１】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、無駄な配線の使用を抑制可能にした資源再配置装置、資源再配置方法、および、コンピュータに実行させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するための本発明の資源再配置装置は、演算機能および配線機能を共有する再構成可能資源を複数備えた装置に対して該演算機能および配線機能を再配置させる資源再配置装置であって、
複数の前記再構成可能資源のそれぞれについて、前記演算機能のみが割り当てられた状態である第１の状態、通過配線の前記配線機能のみが割り当てられた状態である第２の状態、前記演算機能および配線機能が割り当てられた状態である第３の状態、ならびに前記演算機能および配線機能のいずれも割り当てられていない状態である空状態のうち、いずれの状態に設定されているかを記憶する記憶手段と、
前記記憶手段が記憶する、各再構成可能資源の前記状態を参照し、前記第２の状態の再構成可能資源が存在する場合、前記第１または第３の状態の再構成可能資源の演算機能を前記空状態の再構成可能資源に順次移動させ、前記第２の状態の再構成可能資源と前記空状態の再構成可能資源とが連続的に配置されるように構成を変更することにより、前記第２の状態の再構成可能資源を前記空状態に変更する機能手段と、
を有する構成である。
【００１３】
また、本発明の資源再配置方法は、演算機能および配線機能を共有する再構成可能資源を複数備えた装置に対して該演算機能および配線機能を再配置させるための資源再配置方法であって、
複数の前記再構成可能資源のそれぞれについて、前記演算機能のみが割り当てられた状態である第１の状態、通過配線の前記配線機能のみが割り当てられた状態である第２の状態、前記演算機能および配線機能が割り当てられた状態である第３の状態、ならびに前記演算機能および配線機能のいずれも割り当てられていない状態である空状態のうち、いずれの状態に設定されているかを記憶し、
記憶した各再構成可能資源の前記状態を参照し、前記第２の状態の再構成可能資源が存在する場合、前記第１または第３の状態の再構成可能資源の演算機能を前記空状態の再構成可能資源に順次移動させることで、前記第２の状態の再構成可能資源と前記空状態の再構成可能資源とが連続的に配置されるように構成を変更し、
前記空状態に隣接する前記第２の状態の再構成可能資源を前記空状態に変更するものである。
【００１４】
さらに、本発明のプログラムは、上記本発明の資源再配置装置の記憶手段および機能手段としてコンピュータを機能させるものである。
【発明の効果】
【００１５】
本発明によれば、配線を無駄に使用することを抑制することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態の資源再配置装置の一構成例を示すブロック図である。
【図２】第１の実施形態の資源再配置方法を説明するための図である。
【図３】第１の実施形態の資源再配置方法の手順を示すフローチャートである。
【図４】第１の実施形態の資源再配置方法を説明するための図である。
【図５】第１の実施形態で説明した空資源回収の過程で使用終了する資源がある場合の一例を示す図である。
【図６】第２の実施形態の資源再配置方法を説明するための図である。
【図７Ａ】第２の実施形態の資源再配置方法の手順を示すフローチャートである。
【図７Ｂ】第２の実施形態の資源再配置方法の手順を示すフローチャートである。
【図８Ａ】第３の実施形態の資源再配置方法の手順を示すフローチャートである。
【図８Ｂ】第３の実施形態の資源再配置方法の手順を示すフローチャートである。
【図８Ｃ】第３の実施形態の資源再配置方法の手順を示すフローチャートである。
【図９Ａ】第４の実施形態の資源再配置方法の手順を示すフローチャートである。
【図９Ｂ】第４の実施形態の資源再配置方法の手順を示すフローチャートである。
【図９Ｃ】第４の実施形態の資源再配置方法の手順を示すフローチャートである。
【図１０】第４の実施形態において、前方決定関数の例を示す図である。
【図１１】本発明に関連する再構成可能装置の構成例を示す図である。
【図１２】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１３】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１４】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１５】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１６】図１１に示した装置における各資源の状態遷移図である。
【図１７】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１８】図１１に示した装置における資源への機能割当の手順を示す図である。
【図１９】図１１に示した資源の全てが使用されていることを示す図である。
【図２０】図１１に示した資源のうち、いくつかの資源が不使用・通過配線あり（q2）になった場合の一例を示す図である。
【図２１】図１１に示した資源のうち、資源Ｆ4、Ｆ7、ＦN-3が不使用・通過配線あり（q2）になった場合を示す図である。
【図２２】図２１に示した場合における、従来技術の機能書換手順を示す図である。
【図２３】図２１に示した場合における、従来技術の機能書換手順を示す図である。
【発明を実施するための形態】
【００１７】
本発明の一実施形態における資源再配置の装置および方法を説明する。図１は本発明の一実施形態における資源再配置装置の一構成例を示すブロック図である。
資源再配置装置３０は、機能手段３１と、手順記憶手段３２と、一次記憶手段３３とを有する。一次記憶手段３３は、各資源に設定された演算機能および配線機能の割当状態を、変数｛q(Fi)｜i=1,…,N｝として記憶する。手順記憶手段３２は、後述の手順、例えば、図３に示す手順が記述されたプログラムを記憶する。機能手段３１は、一次記憶手段３３が記憶する情報を参照し、手順記憶手段３２が記憶するプログラムにしたがって、各資源に設定された演算機能と配線機能を再配置させる制御を実行する。
機能手段３１の制御対象となる再構成可能装置は、図１１を参照して説明した装置と同様な構成であり、その詳細な説明を省略する。
機能手段３１は、例えば、ＣＰＵ（Central Processing Unit）である。図１のブロック図では、手順記憶手段３２と一次記憶手段３３とを別々の構成で示しているが、１つの記憶手段（例えば、フラッシュメモリ）であってもよい。
【００１８】
図１に示した資源再配置装置３０による資源再配置方法を説明する。
本発明の一実施形態における資源再配置方法は、連続配置する空資源を十分な個数になるまで確保するために、資源の状態遷移を利用するものである。具体的には、機能手段３１は、状態q2の資源の通過配線を使用している他の資源であって、状態q1の資源に着目し、その機能を別の状態q0の資源に移動すること（第一の例）、または、状態q2の資源の通過配線を使用している他の資源であって、状態q3の資源に着目し、その機能を状態q0の資源に移動すること（第二の例）、を行う。これにより、状態q2の資源が、第一の例の場合には即座に、第二の例の場合には漸次的に状態q0に遷移し、空資源を回収して連続配置の状態を編成することが可能となる。状態q0を空状態と称する。
以下に、本発明の実施形態を詳しく説明する。
【００１９】
（第１の実施形態）
本発明の一実施形態の資源再配置方法について説明する。なお、本実施形態の資源再配置方法は図１に示した資源再配置装置３０によって実行されるものであり、図１に示した資源再配置装置３０の構成の説明を省略する。
図２は本実施形態の資源再配置方法を説明するための図である。図２を参照して、空資源を連続配置にしていく手順を説明する。
【００２０】
図２の上側は制御対象となる再構成可能資源のブロック図であり、図２の下側の各行はある時刻の各資源の状態を表している。図２のブロック図を参照すると、ＧＷ１０と資源ＦNが配線を介して接続されているため、資源Ｆ1〜ＦNおよびＧＷ１０はリング状に配置されていると言える。図２の下側は、時刻が図の上から下にむかって、t=1,2,3,4…と離散的に進行することを表す。t=1は機能設定後の各資源の初期状態を示し、t=2以降は再配置の手順を示す。図２の下側の図を再配置履歴と称する。時刻t=1においては、図２に示すように、Ｆ2，Ｆ3，Ｆ4が空資源（状態q0）であり、その両外側の資源Ｆ1，Ｆ5が状態q1であるものとする。その他の資源は、それぞれ図に示すように、状態q2あるいは状態q3であるものとする。
t=1の状態から、t=2において、機能手段３１が、Ｆ5の機能をＦ2に書込み、t=3においてＦ6の機能をＦ3に書き込むことで、それぞれ移動させると、Ｆ7は状態q2であったものだが、通過配線がないために状態q0に遷移することになる。これによって、空資源の連続配置の長さが３から４になった。このようにして、連続配置した空資源を回収していくことができる。回収した空資源の連続配置数は、この段階では４であるが、仮に、いま必要な資源数が４以下、例えば、３であった場合、資源Ｆ4，Ｆ5，Ｆ6と必要個数の資源に対して機能書込みを行えばよい。
【００２１】
図３は本実施形態の資源再配置方法の手順を示すフローチャートである。図２および図３を参照して、空資源回収についての手順を説明する。手順の概要は、状態q0 もしくはq1の資源を利用して、状態q1もしくはq3の資源を移動させながら、状態q2の資源をq0の連続配置に加えていくことである。機能手段３１は、次のようにして、条件に応じて『前方』を決定して操作を進めていく。
図３のフローチャートに示す空資源回収手順は、状態q2が存在する場合に意味をもつ。そこで、状態q2の資源が無い場合、機能手段３１は、「開始」に戻って待機する。このとき、全ての資源が、状態q1、q3 もしくは、q0の状態にある。図１９に示した状況がその一例である。
【００２２】
機能手段３１が待機しているうちに、資源のうちのいくつかが使用終了となり、状態q2の資源が発生する（ステップ１０１）。例えば、図２１に示したような状況になる。このとき、状態q0の資源があれば（ステップ１０２）、機能手段３１は、その連続配置の左右の端から、資源を順にたどってＧＷ１０に到達するまで、状態q2の資源の数をカウントし、カウント数が大きい方向、すなわち状態q2の多い方向を『前方』と決定する（ステップ１０５）。ここでは、ＧＷ１０は状態q2の資源数のカウントのための基準点の役目を果たす。図２に示す例では、 t=1において資源Ｆ1は状態q2ではないため、この方向には状態q2の個数は、０である。一方、資源Ｆ5からＦNまでをたどると多くの状態q2が見出されることから、機能手段３１は、図の右側を『前方』に決定する。
そして、前方のq1の資源、この場合は、資源Ｆ5の機能を、機能手段３１は、資源Ｆ5を基準にして状態q0の連続配置Ｆ2，Ｆ3，Ｆ4の中の最後方の資源、すなわちＦ2に割り当て、さらに、ＧＷ１０からＦ2への配線を、後方すなわち、図の左から右方向に行う、という操作を行い（ステップ１０８）、その後、「開始」に戻る。ここで、時刻t=1から時刻t=2まで経過したことになる。図３に示す「開始」に戻るたびに時刻がすすむものとし、機能手段３１は、状態q2 が存在するまでの待機と、『前方』の決定を再度行う。時刻t=2からt=3、時刻t=3からt=4への経過における各資源の状態の更新はこのようにして行われていく。
さて、図３のステップ１０２において、状態q0 の資源がない場合、例えば、図２１に示した例では、機能手段３１は、状態q0ではなくて、状態q1 の資源に着目する（ステップ１０３）。図２１の場合は、状態q1の資源は１つしかなく、該当資源であるところのＦNは、ＧＷ１０と隣接している（ステップ１０４）。そこで、機能手段３１は、ＧＷ１０とq1の資源すなわちＦNの隣接箇所、言い換えれば ＧＷ１０とＦNの境界から見て、状態q1の資源、この場合は、ＦNのある方向、すなわち図の右端から左方向を『前方』と決定する（ステップ１０７）。
【００２３】
次に、図４を参照して、ステップ１０７以降の説明を継続する。図４の時刻t=1において、前方のq1すなわち、この場合は、資源ＦNの配線を、機能手段３１は、資源ＦNを基準とした後方、すなわち、右方向、言い換えれば、ＧＷ１０から割り当てる（ステップ１０９）。これによって、資源ＦN-1は資源ＦNへの配線を担わなくなり、つまり、資源ＦN-1は経由配線がなくなり、状態q3から状態q1に遷移する。ここで、状態q1の資源が２つ生じる状況になった。図４のt=2 のときがその状況を示している。状態q1の資源が２つ生じるが、状態q0の資源がない場合、こうして生じた２つの状態q1の資源はかならず隣接している（ステップ１０３）。そして、t=2では、機能手段３１は、隣接している境界面から見てq2が多くある方向すなわち、左方向を『前方』として（ステップ１０６）、前方のq1の資源、すなわち、ＦN-1の配線を後方すなわち右方向から割り当てる（ステップ１０９）。これによって、当該q1の資源、すなわち、ＦNの、さらに前方にある資源ＦN-1は、ＦN-2への配線を担わなくなる。
これ以降、機能手段３１は、上述した手順を繰り返していくが、図４のt=4 において、ＦN-2への配線を後方、すなわち、右方向から割り当てると（ステップ１０９）、当該q1の資源、すなわち、ＦN-2の、さらに前方にある資源ＦN-3は、もともと、使用中の機能割当がなく、通過配線のみを有する状態q2であったことから、ＦN-2への配線を担わなくなることで、状態q0に遷移し、空資源となる。状態q0がある場合の手順については、既に説明した通りである。
このようにして、本実施形態では、図３に示した手順により空資源の回収を進めることができる。
【００２４】
（第２の実施形態）
本実施形態は、現在から所定の時間内に演算機能が除去される使用終了予定がある資源については機能の移動を行わないようにしたものである。なお、本実施形態の資源再配置方法は図１に示した資源再配置装置３０によって実行されるものであり、ここでは、図１に示した資源再配置装置３０の構成の説明を省略する。
【００２５】
第１の実施形態で説明した手順で空資源の回収を行っている途中で、新たに使用終了となる資源が発生する場合があり、状態q2の資源を全て回収したとは限らない。状態 q1 の資源が 使用終了となった場合、もともと状態 q1 の資源は、状態 q0 の資源があればそれと隣接しているので、そのまま空資源の回収が実現できる。一方、状態 q3 の資源が使用終了となって、状態 q2 に遷移した場合、空資源の回収までにかかる時間が長くなることが考えられる。その一例を図５に示す。図５は、第１の実施形態で説明した空資源回収の過程で使用終了する資源がある場合の一例を示す図である。
図５に示す例では、第１の実施形態で説明した図２と同じ状況を t=1 としているが、本実施形態では、資源Ｆ5およびＦ6がそれぞれt=5 および t=4 に使用終了となる予定を、機能手段３１が別途わかっているものとする。図５の再配置履歴において、資源Ｆ5およびその移動先のＦ2と、資源Ｆ6およびその移動先のＦ3のそれぞれの枠内に記した数値は、使用終了までの時刻のカウントダウン値である。図５は、図３に示した手順によって、空資源の回収を行った場合の状況の変化を示している。結果的に、t=5 以降、Ｆ2，Ｆ3は 状態q2 のまま、しばらくのあいだ、残されることになり、空資源の連続配置の個数に算入することができない。
【００２６】
そこで、本実施形態では、資源の使用終了を機能手段３１に予告可能であることを利用して、空資源回収の手順においても、使用終了予定の資源については機能の移動を行わないようにする。図６にその方法を施した例を示す。図６の再配置履歴に示すように、時刻t=1,t=2 でＦ5，Ｆ6の機能を移動させるのではなく、これらよりもさらに前方、この状況では右方向にある状態 q3 の資源の機能を移動させていく。こうすることによって、後方、この状況では左方向に、状態 q2 の資源が埋もれることが防がれ、図５に示した場合と比べて、図６に示す状況では常に２個分、空資源の連続の個数を大きくとることが可能となる。現在の時刻からＮ程度のちに使用終了となる資源について、このような取扱いを行えば、十分に効果を得ることが可能である。
【００２７】
図７Ａおよび図７Ｂは本実施形態の資源再配置方法の手順を示すフローチャートである。図６、図７Ａおよび図７Ｂを参照して、本実施形態における空資源回収の手順を説明する。なお、図７Ａに示すステップ２０１〜２０７の処理は図３を参照して説明したステップ１０１〜１０７と同様なため、ここでは、その詳細な説明を省略する。
機能手段３１は、図７Ａに示すステップ２０５の処理により『前方』を決定した後、前方のq1の資源に使用終了予定があるか否かを判定し（図７Ｂに示すステップ２０８）、使用終了予定がある場合、ステップ２０９の処理に進み、使用終了予定に該当しない場合、ステップ２１１の処理に進む。図６に示す例では、資源Ｆ5がt=5のときに使用終了予定なので、機能手段３１は、ステップ２０９に進み、前方にq3の資源で終了予定のないものがあるか否かを判定する。図６に示す例では、状態q3の資源Ｆ8は使用終了予定に該当しないため、t=2において、機能手段３１は、該当資源Ｆ8の演算機能を、q0の連続配置の中の最後方の資源Ｆ2に割り当て、ＧＷ１０からの配線を後方、すなわち資源Ｆ1側から資源Ｆ2に割り当てる（ステップ２１０）。ステップ２０８において、前方のq1の資源に終了予定がない場合、機能手段３１は、該当のq1の資源の演算機能を、q0の連続配置の中の最後方の資源に割り当て、その資源にＧＷ１０からの配線を後方から割り当てる（ステップ２１１）。
【００２８】
一方、機能手段３１は、ステップ２０６またはステップ２０７の処理により『前方』を決定した後、前方のq1の資源に使用終了予定があるか否かを判定し（ステップ２１２）、使用終了予定がない場合、該当のq1へのＧＷ１０からの配線を後方から割り当てる（ステップ２１３）。
図３に示した手順との違いは、資源の使用終了予定の有無について、たかだか、現在の時刻からＮ程度のちに終了するかどうかとし、その使用終了予定があるものが、図３の手順であれば機能を移動させる資源であると判断されるようなもの場合には、機能の移動元の候補から除外し、機能の移動元となる資源を、より前方の、したがって、状態 q3 の資源に求める点である。『前方にq3の資源で終了予定無いものがあるか？』が、これを示している。
第１および第２の実施形態において、状態 q0 の資源を連続配置とするための手順、すなわち、空資源の回収の手順を説明した。
【００２９】
（第３の実施形態）
第１および第２の実施形態で説明したように、空資源の連続が十分な個数に達した場合には、それらの資源に、需要に応じた機能の割当を行うことになるが、機能の割当と空資源の回収を、一連の手順として組み合わせることも可能である。本実施形態は、機能の割当と空資源の回収を一連の手順として組み合わせるものである。
なお、本実施形態の資源再配置方法は図１に示した資源再配置装置３０によって実行されるものであり、資源再配置装置３０の構成は後述の関数Ｍ（ｋ）および｛M(k)｜k=1,…,Kall｝の変数が一次記憶手段３３に予め格納されていることを除いて、図１に示した資源再配置装置３０の構成と同様なため、その詳細な説明を省略する。
【００３０】
本実施形態の資源再配置方法を説明する。図８Ａ〜図８Ｃは本実施形態の資源再配置方法の手順を示すフローチャートである。ここでは、図３および図７Ｂを参照して説明した処理と同様な処理については、その説明を省略する。
図８Ａに示すように、識別子ｋで示される機能の割り当て要求があり（ステップ３０１）、その要求のために必要となる資源の個数が別途関数Ｍ（ｋ）で与えられる場合、「Ｍ（ｋ）＜空資源の個数」となったとき（ステップ３０２）、機能手段３１は、連続的に配置された空資源を機能ｋに順次割り当てる（ステップ３０３）。その後、割当の要求がまだあり、かつ、割当が可能な条件のあいだは、機能手段３１は、割当を繰り返し（ステップ３０１〜３０３）、割当ができなくなったところで、第１および第２の実施形態で説明した、空資源の回収の手順（図８Ｂおよび図８Ｃに示すステップ３０４〜３１６）に入る。
本実施形態では、資源割当の際、空資源の連続配置のなかで、後方から資源を割り当てていき、配線も後方から行うことにより、空資源の回収と干渉することなく組み合わせることが可能である。
なお、空資源の回収の手順に入る、図中の４番の端子で示される判断の成立条件については、かならずしも割り当てが行えなくなったとき、だけではなく、空資源の残り個数が一定以下になった場合などの任意性が許容され、システム全体の需要状況に合わせることも可能である。
【００３１】
（第４の実施形態）
第１〜第３の実施形態では、空資源の回収を行う方向を決める『前方』について、説明を簡単にするために『〜からＧＷまでを数えてq2 の資源が多い方向』場合で説明した。
本実施形態は、『前方』の決定方法を、さらに一般化して、『〜からＧＷまでのq2の資源の配置と前回までの決定履歴から前方を決定する』ものである。なお、本実施形態の資源再配置方法は図１に示した資源再配置装置３０によって実行されるものであり、本実施形態では、図１に示した資源再配置装置３０と異なる構成について説明し、同様な構成の説明を省略する。
本実施形態の資源再配置装置３０では、図１に示した一次記憶手段３３は、決定履歴を判断要因として含む前方決定関数およびその変数を記憶する。決定履歴は、『前方』の決定に関する履歴である。機能手段３１は、前方決定関数の変数について、一次記憶手段３３が記憶する値を参照および更新することによって、自律的に判断動作を継続する。
【００３２】
本実施形態の資源再配置方法を説明する。図９Ａ〜図９Ｃは本実施形態の資源再配置方法の手順を示すフローチャートである。ここでは、図３、図７Ｂおよび図８Ａを参照して説明した処理と同様な処理については、その説明を省略する。
図１０は、前方決定関数の例として、例１と例２の２つの例を示す。図１０（ａ）は例１の場合の関数を示し、図１０（ｂ）は例２の場合の関数を示す。｛d(j)｜j=1,…,Jmax｝、｛s(l)｜l=1,…,N｝等の変数は一次記憶手段３３に予め格納されている。
ここで、h(i)はi番目の資源が状態 q2 であるときに１であり、そうでなければ０を値とする関数である。また、s(l) は、l（エル）の値に対して、数表等により予め定めておいた正の値を返す関数である。ＰLおよびＰRは q0 で連続している資源の左右端の位置、もしくは、隣接している２つの q1 である資源のそれぞれ左右端の位置を示す。ＷRおよびＷLは、それぞれ、右あるいは左に、q2 がどの程度多く、どの程度離れたところに存在するかによって値を返す関数となり、これらの値の大小関係から、d(0) を決定する。この d(0) が初回に、前方をどちらにするかを表しており、この例では、０なら右（番号の小さくなる側）、１なら左（番号の大きくなる側）などと定めている。
【００３３】
例１は、d(1) すなわち、２回目以降の前方については、ＷRとＷLの差がそれぞれある閾値以上でなければ大小関係だけでは変わらないという場合である。２つの閾値ＷD0とＷD1の差が大きければ大きいほど、直前の前方の判定結果 d(j) をそのまま継承する傾向が大きくなる。
また、例２に示したｗD0(d(j),…,d(j-j0)) という関数は、例えば、その j0+1個の引数の値の総和が大きいほど、関数値が小さくなっていくように定めるようにしておくと、一定の方向の判定が続くと、徐々に左側（d(j+1)=0 となる側）を選ぶ傾向が大きくなる。
図９Ｂに示すステップ４０８において、機能手段３１は、該当q0の連続の左右端からＧＷ１０までのq2の資源の配置と前回までの決定履歴から前方を決定する。また、図９Ｂに示すステップ４０９において、機能手段３１は、該当の２つのq1の資源の隣接箇所からＧＷ１０までのq2の資源の配置と前回までの決定履歴から前方を決定する。
本実施形態では、上述のように、所望の関数を決定することにより、q2 の配置に応じて手数と効果の比率の大きい手順や、回収方向の変更が少ない手順に収束することができ、これらも、利用される状況に応じて適応させることが可能である。
【００３４】
上述の実施形態で説明したように、本発明の資源再配置方法は、部品間の配線が固定されている再構成可能部品（資源）の、配線と機能の割当状態に着目して、通過配線のみを担っている資源を回収する方法である。通過配線のみを担っている資源を移動させることは不可能だが、配線も機能も担っていない資源を利用して、演算を担っている資源を移動させることができ、これによって、配線も機能も担っていない資源と通過配線のみを担っている資源が連続配置となるように、機能を移動する方法を判定する。また、使用終了予定が既知の資源については、有限時間後に通過配線のみを担う資源となることから、通過配線のみを担っている資源として取り扱うことで、配線も機能も担っていない資源の連続配置の個数をより大きくすることが可能となる。これによって、割当を行うことが可能な資源の配置が連続となり、機能を割り当てた際の配線の無駄を防ぐことができる。
【００３５】
本発明の効果を説明する。演算機能と配線機能を共用する再構成可能部品（資源）を複数組み合わせた装置において、演算機能を変更する際に、配線機能の停止を伴ってしまうような資源に対する演算機能の再配置すなわち、演算機能の割り当てを行う場合、従来技術では、複数の資源を組み立てて一つの処理を行うような割り当てを行う際にも、割当先とすることが可能な資源の配置（空資源の配置）を事前に連続的に整理することはなく、割当可能な資源が点在している状態であっても、個別に再構成を行っていた。そのため、資源間を接続する配線が交差することが多くなり、配線を無駄に使用していたが、本発明によって、割当先とすることが可能な資源の配置（空資源の配置）を予め連続的な配置になるよう整理することが可能となり、配線の無駄を防ぐことができる。
【００３６】
本発明の資源再配置装置はコンピュータとプログラムによっても実現でき、そのプログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【符号の説明】
【００３７】
１０    ゲートウェイ（ＧＷ）
２０    再構成可能資源
３１    機能手段
３２    手順記憶手段
３３    一次記憶手段
【図１】
2016063463.tif 000003
【図３】
2016063463.tif 000004
【図７Ａ】
2016063463.tif 000005
【図７Ｂ】
2016063463.tif 000006
【図８Ａ】
2016063463.tif 000007
【図８Ｂ】
2016063463.tif 000008
【図８Ｃ】
2016063463.tif 000009
【図９Ａ】
2016063463.tif 000010
【図９Ｂ】
2016063463.tif 000011
【図９Ｃ】
2016063463.tif 000012
【図１０】
2016063463.tif 000013
【図１１】
2016063463.tif 000014
【図１６】
2016063463.tif 000015
【図２】
2016063463.tif 000016
【図４】
2016063463.tif 000017
【図５】
2016063463.tif 000018
【図６】
2016063463.tif 000019
【図１２】
2016063463.tif 000020
【図１３】
2016063463.tif 000021
【図１４】
2016063463.tif 000022
【図１５】
2016063463.tif 000023
【図１７】
2016063463.tif 000024
【図１８】
2016063463.tif 000025
【図１９】
2016063463.tif 000026
【図２０】
2016063463.tif 000027
【図２１】
2016063463.tif 000028
【図２２】
2016063463.tif 000029
【図２３】
2016063463.tif 000030