情報処理装置および割当方法
【課題】頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理したい。
【解決手段】設定条件保持部１０は、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する。第１演算部４０は、設定条件保持部１０により保持される情報を参照して、同一の割当対象の割り当てが制限される被割当対象の数が複数の割当対象の数より少ない被割当対象を少なくとも一つ選択し、選択した被割当対象に対して設定条件にしたがい割当対象を割り当てる第１アルゴリズムを実行する。第２演算部５０は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、設定条件にしたがい割当対象を割り当てる、第１アルゴリズムと異なる第２アルゴリズムを実行する。
【解決手段】設定条件保持部１０は、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する。第１演算部４０は、設定条件保持部１０により保持される情報を参照して、同一の割当対象の割り当てが制限される被割当対象の数が複数の割当対象の数より少ない被割当対象を少なくとも一つ選択し、選択した被割当対象に対して設定条件にしたがい割当対象を割り当てる第１アルゴリズムを実行する。第２演算部５０は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、設定条件にしたがい割当対象を割り当てる、第１アルゴリズムと異なる第２アルゴリズムを実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、いわゆる頂点彩色の問題を解くための情報処理装置および割当方法に関する。
【背景技術】
【０００２】
頂点彩色とは、頂点と、頂点間を結ぶ辺で構成されるグラフにおいて、各頂点を、辺によって結ばれる頂点同士は異なる色で彩色するといった規則に基づき全ての頂点を彩色する問題である。なお、頂点の次数とは、その頂点に繋がる辺の数を言う。頂点彩色は、様々な分野に応用することができる。たとえば、リコンフィギュラブル回路を備えたプロセッサにおいて（特許文献１参照）、複数の変数を複数のＲＡＭに割り当てる際に用いることができる。
【０００３】
特許文献２は、資源割当装置を開示する。この装置は、高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象を複数個生成し、生成した割付対象に順次レジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける。
【特許文献１】特開２００５−１８２６５４号公報
【特許文献２】特開平８−３１４７２７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
頂点彩色の問題を解くためのアルゴリズムは複数存在する。それらの中には近似アルゴリズムおよび厳密アルゴリズムが含まれる。近似アルゴリズムは高速処理が可能であるが、解への到達確率が厳密アルゴリズムより低くなってしまう。一方、厳密アルゴリズムは解への到達確率が厳密アルゴリズムより高いが、低速処理となってしまう。このように、近似アルゴリズムおよび厳密アルゴリズムはトレードオフの関係にある。なお、近似アルゴリズムおよび厳密アルゴリズムの具体例は後述する。
【０００５】
本発明はこうした状況に鑑みなされたものであり、その目的は、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる情報処理装置および割当方法を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様の情報処理装置は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を少なくとも一つ選択し、選択した被割当対象に対して設定条件にしたがい割当対象を割り当てる第１アルゴリズムを実行する第１演算部と、複数の被割当対象のうち第１演算部により選択されていない被割当対象に対して、設定条件にしたがい割当対象を割り当てる、第１アルゴリズムと異なる第２アルゴリズムを実行する第２演算部と、を備える。
【０００７】
本発明の別の態様もまた、情報処理装置である。この装置は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、既に割り当てられた、被割当対象と割当対象との対応関係を保持する対応関係保持部と、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象のうち、同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象から順に選択する選択部と、選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部と、選択部により選択された被割当対象に対して、対応関係保持部に保持される対応関係を参照して、順番保持部に保持される順番と逆の順番で割当対象を割り当てていく割当部と、を備える。
【０００８】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【０００９】
本発明によれば、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の実施の形態に係る情報処理装置１００の構成を示すブロック図である。
情報処理装置１００は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる。ここで、被割当対象および割当対象の一例としてつぎのものが挙げられる。すなわち、前者が所定のプログラムなどに規定される変数、後者がその変数を格納するレジズタまたはメモリである。
【００１１】
情報処理装置１００は、設定条件保持部１０、対応関係保持部２０、演算部３０および制御部６０を備える。演算部３０は、第１演算部４０および第２演算部５０を有する。第１演算部４０は、選択部４１、順番保持部４２、第１割当部４３、第１登録部４４および判定部４５を含む。第２演算部５０は、第２割当部５３および第２登録部５４を含む。
【００１２】
これらの構成は、ハードウェア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００１３】
設定条件保持部１０は、上記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する。ここで、「同一の割当対象の割り当てが制限される被割当対象」とは「同一の割当対象の割り当てが禁止される被割当対象」であってもよい。それ以外の被割当対象との関係では同一の割当対象を割り当てることが禁止されない。上記設定条件はいわゆる頂点彩色の問題を解く際の前提として、ユーザ操作などに起因してあらかじめ設定条件保持部１０に設定される。
【００１４】
対応関係保持部２０は、第１演算部４０または第２演算部５０により既に割り当てられた、被割当対象と割当対象との対応関係を保持する。割り当てが開始される段階では割り当てが完了した被割当対象は存在しないが、割り当てが開始されると割り当てが完了した被割当対象の数が順次増えていく。最終的にはすべての被割当対象に割当対象が割り当てられることになる。
【００１５】
第１演算部４０は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを実行する。なお、前者の数が後者の数より少ない被割当対象のすべてを必ずしも選択する必要はない。第２演算部５０は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、上記設定条件にしたがい割当対象を割り当てる第２アルゴリズムを実行する。
【００１６】
ここで、第２アルゴリズムが厳密アルゴリズムであってもよい。なお、第１アルゴリズムおよび第２アルゴリズムは、両方とも近似アルゴリズムであってもよい。その場合、解への到達確率が同程度の、異なる近似アルゴリズムであってもよい。なお、第１アルゴリズムおよび第２アルゴリズムはコンピュータプログラムで実現されてもよい。
【００１７】
本実施の形態おいて、近似アルゴリズムとは、複数の被割当対象のすべてに対して上記設定条件にしたがう割当対象の割り当てが客観的に可能な場合でも、その割り当てに必ずしも到達しないアルゴリズムである。一方、厳密アルゴリズムとは、複数の被割当対象のすべてに対して上記設定条件にしたがう割当対象の割り当てが客観的に可能な場合、必ず割り当てできるアルゴリズムである。
【００１８】
以下、第１演算部４０の構成を具体的に説明する。
選択部４１は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を選択する。前者の数が後者の数より少ない被割当対象をすべて選択してもよい。選択部４１は、この条件を満たす被割当対象を一括して選択してもよいし、一つずつ順に選択してもよい。順に選択する場合、その順番は任意であってよいし、所定の規則にしたがった選択でもよい。所定の規則にしたがった選択としてつぎのような選択手法がある。選択部４１は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除する。その際、選択部４１は、各選択時点において同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象のうち、同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象を選択してもよい。
【００１９】
順番保持部４２は、選択部４１により選択された被割当対象とその順番とを対応付けて保持する。選択部４１が前記所定の規則にしたがった選択を行う場合、必須の構成要素である。
【００２０】
第１割当部４３は、選択部４１により選択された被割当対象に対して、対応関係保持部２０に保持される対応関係を参照して、上記設定条件にしたがい上記割当対象を順次割り当てる。ここで、選択部４１が前記所定の規則にしたがった選択を行った場合、第１割当部４３は、順番保持部４２に保持される順番と逆の順番で上記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させる。
【００２１】
第１登録部４４は、第１割当部４３による割り当て結果を対応関係保持部２０に登録する。具体的には、どの被割当対象にどの割当対象が割り当てられたかを特定するための情報を対応関係保持部２０に登録する。
判定部４５は、複数の被割当対象のすべてが選択部４１により選択できたか否かを判定し、その判定結果を制御部６０に供給する。
【００２２】
つぎに、第２演算部５０の構成を具体的に説明する。
第２割当部５３は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、対応関係保持部２０に保持される対応関係を参照して、上記割当対象を順次割り当てる。第１登録部４４は、第１割当部による割り当て結果を対応関係保持部２０に登録する。
【００２３】
制御部６０は、第１演算部４０および第２演算部５０の演算処理を制御する。具体的には、判定部４５による判定の結果、複数の被割当対象のすべてが選択部４１により選択できなかったとき、先に、その選択できなかった被割当対象に対して割当対象を割り当てるよう第２割当部を制御し、その後に、選択部４１により選択できた被割当対象に対して割当対象を割り当てるよう第１割当部を制御する。一方、判定部４５による判定の結果、複数の被割当対象のすべてが選択部４１により選択できたとき、すべての被割当対象に対して割当対象を割り当てるよう第１割当部を制御する。この場合、第２演算部５０の処理は必要ない。
【００２４】
図２は、近似アルゴリズムの一例を説明するための図である。この近似アルゴリズムは以下の手順にしたがう。
手順１．与えられたグラフＧｎ中で次数（図では辺で表される）が彩色する色の数より少ない頂点を一つ選び、その頂点をｘとし、頂点ｘと頂点ｘから出ている辺を取り除き、グラフＧ（ｎ＋１）を得る。
手順２．グラフＧ（ｎ＋１）をグラフＧｎとおいて上記作業を繰り返すと、（１）空なグラフが得られるか、（２）すべての頂点の次数が彩色する色の数以上であるようなグラフが残る。（１）の場合、後述する手順3を実行し、（２）の場合、本手法では彩色できない。
手順３．つぎのように手順1の繰り返しを逆にたどる。G’ｎの彩色結果に、頂点ｘと頂点ｘから出ていた辺を加え、頂点ｘに「頂点ｘから辺で結ばれている頂点と異なる色」を塗って、G’（ｎ−１）の彩色を得ることを繰り返す。
【００２５】
図２の例では、四つの頂点（頂点１〜頂点４）を三色（赤、緑、青）で塗り分けるものである。以下、図において緑を縦線、赤を横線、青を斜線で示す。図２の上段では、上記手順1を繰り返してグラフＧ４を得ている。すなわち、頂点１→頂点２→頂点３→頂点４の順番で、頂点とその頂点から出ている辺をすべて取り除いている。図２の下段では、上記手順3を行って彩色している。
【００２６】
具体的には、まず頂点４を赤に塗る。つぎに頂点３とそれと頂点４を結ぶ辺を加え、頂点３を緑で塗る。つぎに頂点２と、それと頂点３、４をそれぞれ結ぶ辺を加え、頂点２を青で塗る。最後に、頂点１と、それと頂点２を結ぶ辺を加え、頂点１を赤で塗る。
【００２７】
このように、この近似アルゴリズムは高速に解が求められるといった特徴がある。なぜなら、次数が彩色する色の数より少ない頂点はどのような順番で彩色しても確実に彩色可能である頂点であるためである。しかしながら、彩色可能なグラフを彩色できない場合があるといった問題がある。
【００２８】
図３は、上記近似アルゴリズムで彩色できないグラフの一例を示す図である。
図３に示すグラフは五つの頂点を持ち、それらを二色で彩色可能なものである。しかしながら、上記近似アルゴリズムはそれらを二色で彩色することができない。
【００２９】
図４は、設定条件保持部１０、対応関係保持部２０および順番保持部４２を一つのテーブル７０で構成した例を示す図である。
このテーブル７０は図２に示した割り当て処理例に使用したデータに則している。テーブル７０は、項目として被割当対象、設定条件、順番および割当結果を持つ。被割当対象は頂点１〜４である。設定条件は各頂点１〜４ごとに、辺で結ばれた頂点を保持する。順番は除去された順番である。彩色する際はその逆の順番で彩色される。割当結果は各頂点１〜４ごとに、割り当てられた色を保持する。第１演算部４０は、テーブル７０を参照して被割当対象を選択することができる。また、被割当対象に割当対象を割り当てることができる。なお、第１演算部４０は被割当対象を選択する際、このテーブル７０ではなく他のテーブルを参照して選択してもよい。たとえば、項目として被割当対象、その被割当対象と接続されている他の被割当対象の数、を持つテーブルを参照して被割当対象を選択してもよい。
【００３０】
つぎに、厳密アルゴリズムの一例を説明する。この厳密アルゴリズムは彩色可能なグラフは必ず彩色できるアルゴリズムである。
手順１．彩色されていない頂点の中で、隣接頂点に割り当てられた異なる色の数が最大である頂点を選ぶ。そのような頂点が複数ある場合には、その中で色が割り当てられていない頂点集合により構成された誘導部分グラフ中、次数が最大のものを選ぶ。
手順２．選んだ頂点に彩色可能な色を一つ選び、彩色する。
手順３．手順１と手順２を繰り返す。手順２で割り当てる色がなくなった場合には、一つ前の頂点に戻り、別の色で彩色して再度手順１と手順２を繰り返す。
【００３１】
つぎに、本実施の形態に係る情報処理装置１００の動作について説明する。
図５は、実施の形態に係る情報処理装置１００の動作例１を説明するためのフローチャートである。
第１演算部４０は上述した近似アルゴリズムを実行する。選択部４１はグラフの中において次数が彩色数より小さい頂点が存在するか否か判断する（Ｓ１０）。存在する場合（Ｓ１０のＹ）、選択部４１はその一つ以上の頂点の中から任意の頂点を選択する（Ｓ１１）。そして、選択した頂点とその頂点に接続する辺をグラフから削除する（Ｓ１２）。その後、ステップＳ１０に遷移する。
【００３２】
判定部４５はステップＳ１０にて次数が彩色数より小さい頂点が存在しない場合（Ｓ１０のＮ）、グラフが空であるか否か判断する（Ｓ１３）。その判断結果を制御部６０に通知する。空でない場合（Ｓ１３のＮ）、第２演算部５０は制御部６０の指示にしたがい、当該近似アルゴリズムと異なる別のアルゴリズムを用いて、グラフ内の残りの頂点を彩色する（Ｓ１４）。そのアルゴリズムとして、上述した厳密アルゴリズムを用いることができる。ステップＳ１３にてグラフが空である場合（Ｓ１３のＹ）、ステップＳ１４をスキップする。
【００３３】
つぎに、制御部６０はグラフが初期状態であるか否か判断する（Ｓ１５）。初期状態である場合（Ｓ１５のＹ）、処理を終了する。ステップＳ１４にて厳密アルゴリズムによりすべての頂点が彩色された場合、および後述するステップＳ１６〜Ｓ１８の処理が繰り返されてすべての頂点が彩色された場合などが該当する。
【００３４】
ステップＳ１５にてグラフが初期状態でない場合（Ｓ１５のＮ）、第１割当部４３はステップＳ１２にて削除した順番と逆順に頂点を選択し（Ｓ１６）、その頂点とその頂点に接続していた辺をグラフ内に戻す（Ｓ１７）。その際、その頂点を、その頂点と辺で繋がる頂点と異なる色で彩色する（Ｓ１８）。その後、ステップＳ１５に遷移する。
【００３５】
図６は、実施の形態に係る情報処理装置１００の動作例２を説明するためのフローチャートである。動作例２に係る図６のフローチャートは、動作例１に係る図５のフローチャートと基本部分は同じである。以下、相違点および追加点について説明する。
図５のステップＳ１１の代わりに図６ではつぎの処理を行う。すなわち、選択部４１はグラフの中において次数が彩色数より小さい頂点のうち、最小の頂点を選択する（Ｓ１１’）。
【００３６】
また、ステップＳ１８にて彩色する際の色を、色別の頂点の数を斟酌して選択してもよい。たとえば、色別の頂点数に上限がある場合、各色の残り頂点数が多い色を優先的に選択してもよい。または、色別の頂点数を平均化したい場合、色別の頂点数が少ない色を優先的に選択してもよい。
【００３７】
つぎに、実施の形態に係る情報処理装置１００の適用例について説明する。
まず、適用例１として複数のＲＡＭに複数の変数を割り当てるＲＡＭ割り当てについて説明する。適用例１では上記割当対象がＲＡＭ、上記被割当対象が変数である。
【００３８】
図７は、実施の形態に係る情報処理装置１００の適用例１に係るプロセッサシステムを示す図である。
このプロセッサシステムは六個の演算器１〜６と四個のＲＡＭ１〜４を備える。各演算器１〜６は演算結果を任意のＲＡＭ１〜４に書き込むことができる。また、任意のＲＡＭ１〜４のデータを参照することもできる。このプロセッサシステムにおいて、特定のＲＡＭに対して同時に複数の演算器から値を書き込むことはできない。また、特定のＲＡＭから異なるデータを同時に複数の演算器に供給することもできない。
【００３９】
図８は、図７に示した適用例１に係るプロセッサシステムで利用される変数の一例を示す図である。より具体的には、図８は各タイミングにおいて各演算器１〜６が使用する変数を示す表である。
タイミング1では、変数aと変数bが同時に利用されるため、それらを一つのＲＡＭに格納することはできず、異なる二つのＲＡＭに割り当てられる。また、変数ｂと変数ｃは同時に利用されることがないため、同じＲＡＭに割り当ててもよい。
【００４０】
図９は、図８に示した表の変数ａ〜ｅの関係をグラフ化した図である。
変数ａ〜ｅを頂点とし、同じＲＡＭに割り当てられることができない変数同士を辺で結んだものである。このようにして生成されたグラフに対して、頂点彩色を行う。この場合、頂点に塗られる色がそれぞれのＲＡＭに対応し、ＲＡＭの数が彩色数となる。
【００４１】
同じ色で塗られた頂点は同じＲＡＭに格納される。単に塗り分けるだけでは特定のＲＡＭにだけ変数が集まってしまい、そのＲＡＭのサイズを超えてしまう可能性が高い。これを回避するため、複数のＲＡＭに割り当てられる変数を、残りのＲＡＭ容量を考慮して割り当てるとよい。すなわち、残りのＲＡＭ容量が多いＲＡＭに割り当てるとよい。これにより、ＲＡＭ容量に収められる可能性を高めることができる。なお、割り当てることが可能なＲＡＭの候補数が多いほど、よりＲＡＭ容量に収まる可能性が高くなる。
【００４２】
つぎに、適用例２として複数のレジスタに複数の変数を割り当てるレジスタ割り当てについて説明する。適用例２では上記割当対象がレジスタ、上記被割当対象が変数である。適用例２は適用例１と異なり、各レジスタは一単位のデータしか格納することがきない。
【００４３】
図１０は、実施の形態に係る情報処理装置１００の適用例２に係る、複数の変数ａ〜ｅの生存区間を示す図である。
ある変数に値が設定されその値が最後に読み出されるまで、その変数は一つのレジスタを占有する。この区間を生存区間と呼ぶ。図１０において、各線の開始位置がその線に対応する変数に値が設定される開始時間を示し、各線の終了位置が最後に読み出される終了時間を示す。この図では、変数ａと変数ｂは生存区間が重なっているが、変数ａと変数ｃは生存区間が重なっていない。二つの変数の生存区間が重ならない場合、同一のレジスタに割り当てることができるが、重なる場合、異なるレジスタに割り当てる必要がある。
【００４４】
図１１は、図１０に示した変数ａ〜ｅの生存区間の関係をグラフ化した図である。
変数ａ〜ｅを頂点とし、生存区間が重なる変数同士を辺で結んだものである。このようにして生成されたグラフに対して、頂点彩色を行う。この場合、頂点に塗られる色がそれぞれのレジスタに対応し、レジスタの数が彩色数となる。
【００４５】
つぎに、適用例３として複数の町に複数の色を割り当てる地図彩色について説明する。適用例３では上記割当対象が色、上記被割当対象が町である。すなわち、地図を見やすくするため、隣同士の町を異なる色で塗り分ける。
【００４６】
図１２は、実施の形態に係る情報処理装置１００の適用例３に係る、複数の町ａ〜ｉを含む地図を示す図である。この地図上において隣接する町を異なる色で塗る。
図１３は、図１２に示した複数の町ａ〜ｉの関係をグラフ化した図である。町ａ〜ｉを頂点とし、隣接する町を辺で結んだものである。
【００４７】
以上説明したように実施の形態によれば、近似アルゴリズムで解が求まらなかった問題に対して、厳密アルゴリズムを組み合わせることにより、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる。厳密アルゴリズムのみを適用する場合に比べ、探索範囲を狭めて厳密アルゴリズムを適用することができるため、より高速に解を求めることができる。
【００４８】
また、次数がより少ない頂点を先に取り除くことにより、頂点を戻して彩色する際に、より後の段階で彩色の自由度を高めることができる。このような、次数がより少ない頂点を先に取り除く手法をＲＡＭ割り当てに適用した場合、各ＲＡＭのサイズに応じた変数の割り当てを容易にすることができる。取り除く頂点の順序を考慮しないと、後の彩色で特定の色の頂点だけが多くなってしまうケースが発生し得る。これは色別の数が重要となる分野でとくに問題となる。上述したＲＡＭ割り当てでは、色別の数がＲＡＭのサイズによって制限されるため、特定の色の頂点が多いとＲＡＭに入りきらないという問題が起きる。
【００４９】
たとえば、ＲＡＭのサイズを五とし、ＲＡＭ１にもＲＡＭ２にも割り当てることができる五つの変数を先に彩色し、ＲＡＭ１にしか割り当てることがきない五つの変数を後で彩色した場合を考える。先の五つの変数をすべてＲＡＭ１に割り当ててしまうと、残りの五つの変数を割り当てられなくなってしまう。上述した方式では、ＲＡＭ１とＲＡＭ２に割り当てられる変数が後に彩色されるため、最初にＲＡＭ１にのみ割り当てる変数を割り当てた後、残りの五つの変数を残ったＲＡＭ２に割り当てることができる。
【００５０】
以上、本発明をいくつかの実施形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５１】
図５、６に示したフローチャートのステップＳ１０では、彩色数より少ない次数が存在する間、ステップＳ１３には遷移しないが、所定数の頂点を選択したらステップＳ１３に遷移するように処理してもよい。
【図面の簡単な説明】
【００５２】
【図１】本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図２】近似アルゴリズムの一例を説明するための図である。
【図３】近似アルゴリズムで彩色できないグラフの一例を示す図である。
【図４】設定条件保持部、対応関係保持部および順番保持部を一つのテーブルで構成した例を示す図である。
【図５】実施の形態に係る情報処理装置の動作例１を説明するためのフローチャートである。
【図６】実施の形態に係る情報処理装置の動作例２を説明するためのフローチャートである。
【図７】実施の形態に係る情報処理装置の適用例１に係るプロセッサシステムを示す図である。
【図８】図７に示した適用例１に係るプロセッサシステムで利用される変数の一例を示す図である。
【図９】図８に示した表の変数ａ〜ｅの関係をグラフ化した図である。
【図１０】実施の形態に係る情報処理装置の適用例２に係る、複数の変数ａ〜ｅの生存区間を示す図である。
【図１１】図１０に示した変数ａ〜ｅの生存区間の関係をグラフ化した図である。
【図１２】実施の形態に係る情報処理装置の適用例３に係る、複数の町ａ〜ｉを含む地図を示す図である。
【図１３】図１２に示した複数の町ａ〜ｉの関係をグラフ化した図である。
【符号の説明】
【００５３】
１０ 設定条件保持部、 ２０ 対応関係保持部、 ３０ 演算部、 ４０ 第１演算部、 ４１ 選択部、 ４２ 順番保持部、 ４３ 第１割当部、 ４４ 第１登録部、 ４５ 判定部、 ５０ 第２演算部、 ５３ 第２割当部、 ５４ 第２登録部、 ６０ 制御部、 ７０ テーブル、 １００ 情報処理装置。
【技術分野】
【０００１】
本発明は、いわゆる頂点彩色の問題を解くための情報処理装置および割当方法に関する。
【背景技術】
【０００２】
頂点彩色とは、頂点と、頂点間を結ぶ辺で構成されるグラフにおいて、各頂点を、辺によって結ばれる頂点同士は異なる色で彩色するといった規則に基づき全ての頂点を彩色する問題である。なお、頂点の次数とは、その頂点に繋がる辺の数を言う。頂点彩色は、様々な分野に応用することができる。たとえば、リコンフィギュラブル回路を備えたプロセッサにおいて（特許文献１参照）、複数の変数を複数のＲＡＭに割り当てる際に用いることができる。
【０００３】
特許文献２は、資源割当装置を開示する。この装置は、高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象を複数個生成し、生成した割付対象に順次レジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける。
【特許文献１】特開２００５−１８２６５４号公報
【特許文献２】特開平８−３１４７２７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
頂点彩色の問題を解くためのアルゴリズムは複数存在する。それらの中には近似アルゴリズムおよび厳密アルゴリズムが含まれる。近似アルゴリズムは高速処理が可能であるが、解への到達確率が厳密アルゴリズムより低くなってしまう。一方、厳密アルゴリズムは解への到達確率が厳密アルゴリズムより高いが、低速処理となってしまう。このように、近似アルゴリズムおよび厳密アルゴリズムはトレードオフの関係にある。なお、近似アルゴリズムおよび厳密アルゴリズムの具体例は後述する。
【０００５】
本発明はこうした状況に鑑みなされたものであり、その目的は、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる情報処理装置および割当方法を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様の情報処理装置は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を少なくとも一つ選択し、選択した被割当対象に対して設定条件にしたがい割当対象を割り当てる第１アルゴリズムを実行する第１演算部と、複数の被割当対象のうち第１演算部により選択されていない被割当対象に対して、設定条件にしたがい割当対象を割り当てる、第１アルゴリズムと異なる第２アルゴリズムを実行する第２演算部と、を備える。
【０００７】
本発明の別の態様もまた、情報処理装置である。この装置は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、既に割り当てられた、被割当対象と割当対象との対応関係を保持する対応関係保持部と、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象のうち、同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象から順に選択する選択部と、選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部と、選択部により選択された被割当対象に対して、対応関係保持部に保持される対応関係を参照して、順番保持部に保持される順番と逆の順番で割当対象を割り当てていく割当部と、を備える。
【０００８】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【０００９】
本発明によれば、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の実施の形態に係る情報処理装置１００の構成を示すブロック図である。
情報処理装置１００は、複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる。ここで、被割当対象および割当対象の一例としてつぎのものが挙げられる。すなわち、前者が所定のプログラムなどに規定される変数、後者がその変数を格納するレジズタまたはメモリである。
【００１１】
情報処理装置１００は、設定条件保持部１０、対応関係保持部２０、演算部３０および制御部６０を備える。演算部３０は、第１演算部４０および第２演算部５０を有する。第１演算部４０は、選択部４１、順番保持部４２、第１割当部４３、第１登録部４４および判定部４５を含む。第２演算部５０は、第２割当部５３および第２登録部５４を含む。
【００１２】
これらの構成は、ハードウェア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００１３】
設定条件保持部１０は、上記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する。ここで、「同一の割当対象の割り当てが制限される被割当対象」とは「同一の割当対象の割り当てが禁止される被割当対象」であってもよい。それ以外の被割当対象との関係では同一の割当対象を割り当てることが禁止されない。上記設定条件はいわゆる頂点彩色の問題を解く際の前提として、ユーザ操作などに起因してあらかじめ設定条件保持部１０に設定される。
【００１４】
対応関係保持部２０は、第１演算部４０または第２演算部５０により既に割り当てられた、被割当対象と割当対象との対応関係を保持する。割り当てが開始される段階では割り当てが完了した被割当対象は存在しないが、割り当てが開始されると割り当てが完了した被割当対象の数が順次増えていく。最終的にはすべての被割当対象に割当対象が割り当てられることになる。
【００１５】
第１演算部４０は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを実行する。なお、前者の数が後者の数より少ない被割当対象のすべてを必ずしも選択する必要はない。第２演算部５０は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、上記設定条件にしたがい割当対象を割り当てる第２アルゴリズムを実行する。
【００１６】
ここで、第２アルゴリズムが厳密アルゴリズムであってもよい。なお、第１アルゴリズムおよび第２アルゴリズムは、両方とも近似アルゴリズムであってもよい。その場合、解への到達確率が同程度の、異なる近似アルゴリズムであってもよい。なお、第１アルゴリズムおよび第２アルゴリズムはコンピュータプログラムで実現されてもよい。
【００１７】
本実施の形態おいて、近似アルゴリズムとは、複数の被割当対象のすべてに対して上記設定条件にしたがう割当対象の割り当てが客観的に可能な場合でも、その割り当てに必ずしも到達しないアルゴリズムである。一方、厳密アルゴリズムとは、複数の被割当対象のすべてに対して上記設定条件にしたがう割当対象の割り当てが客観的に可能な場合、必ず割り当てできるアルゴリズムである。
【００１８】
以下、第１演算部４０の構成を具体的に説明する。
選択部４１は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を選択する。前者の数が後者の数より少ない被割当対象をすべて選択してもよい。選択部４１は、この条件を満たす被割当対象を一括して選択してもよいし、一つずつ順に選択してもよい。順に選択する場合、その順番は任意であってよいし、所定の規則にしたがった選択でもよい。所定の規則にしたがった選択としてつぎのような選択手法がある。選択部４１は、同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除する。その際、選択部４１は、各選択時点において同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な複数の割当対象の数より少ない被割当対象のうち、同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象を選択してもよい。
【００１９】
順番保持部４２は、選択部４１により選択された被割当対象とその順番とを対応付けて保持する。選択部４１が前記所定の規則にしたがった選択を行う場合、必須の構成要素である。
【００２０】
第１割当部４３は、選択部４１により選択された被割当対象に対して、対応関係保持部２０に保持される対応関係を参照して、上記設定条件にしたがい上記割当対象を順次割り当てる。ここで、選択部４１が前記所定の規則にしたがった選択を行った場合、第１割当部４３は、順番保持部４２に保持される順番と逆の順番で上記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させる。
【００２１】
第１登録部４４は、第１割当部４３による割り当て結果を対応関係保持部２０に登録する。具体的には、どの被割当対象にどの割当対象が割り当てられたかを特定するための情報を対応関係保持部２０に登録する。
判定部４５は、複数の被割当対象のすべてが選択部４１により選択できたか否かを判定し、その判定結果を制御部６０に供給する。
【００２２】
つぎに、第２演算部５０の構成を具体的に説明する。
第２割当部５３は、複数の被割当対象のうち第１演算部４０により選択されていない被割当対象に対して、対応関係保持部２０に保持される対応関係を参照して、上記割当対象を順次割り当てる。第１登録部４４は、第１割当部による割り当て結果を対応関係保持部２０に登録する。
【００２３】
制御部６０は、第１演算部４０および第２演算部５０の演算処理を制御する。具体的には、判定部４５による判定の結果、複数の被割当対象のすべてが選択部４１により選択できなかったとき、先に、その選択できなかった被割当対象に対して割当対象を割り当てるよう第２割当部を制御し、その後に、選択部４１により選択できた被割当対象に対して割当対象を割り当てるよう第１割当部を制御する。一方、判定部４５による判定の結果、複数の被割当対象のすべてが選択部４１により選択できたとき、すべての被割当対象に対して割当対象を割り当てるよう第１割当部を制御する。この場合、第２演算部５０の処理は必要ない。
【００２４】
図２は、近似アルゴリズムの一例を説明するための図である。この近似アルゴリズムは以下の手順にしたがう。
手順１．与えられたグラフＧｎ中で次数（図では辺で表される）が彩色する色の数より少ない頂点を一つ選び、その頂点をｘとし、頂点ｘと頂点ｘから出ている辺を取り除き、グラフＧ（ｎ＋１）を得る。
手順２．グラフＧ（ｎ＋１）をグラフＧｎとおいて上記作業を繰り返すと、（１）空なグラフが得られるか、（２）すべての頂点の次数が彩色する色の数以上であるようなグラフが残る。（１）の場合、後述する手順3を実行し、（２）の場合、本手法では彩色できない。
手順３．つぎのように手順1の繰り返しを逆にたどる。G’ｎの彩色結果に、頂点ｘと頂点ｘから出ていた辺を加え、頂点ｘに「頂点ｘから辺で結ばれている頂点と異なる色」を塗って、G’（ｎ−１）の彩色を得ることを繰り返す。
【００２５】
図２の例では、四つの頂点（頂点１〜頂点４）を三色（赤、緑、青）で塗り分けるものである。以下、図において緑を縦線、赤を横線、青を斜線で示す。図２の上段では、上記手順1を繰り返してグラフＧ４を得ている。すなわち、頂点１→頂点２→頂点３→頂点４の順番で、頂点とその頂点から出ている辺をすべて取り除いている。図２の下段では、上記手順3を行って彩色している。
【００２６】
具体的には、まず頂点４を赤に塗る。つぎに頂点３とそれと頂点４を結ぶ辺を加え、頂点３を緑で塗る。つぎに頂点２と、それと頂点３、４をそれぞれ結ぶ辺を加え、頂点２を青で塗る。最後に、頂点１と、それと頂点２を結ぶ辺を加え、頂点１を赤で塗る。
【００２７】
このように、この近似アルゴリズムは高速に解が求められるといった特徴がある。なぜなら、次数が彩色する色の数より少ない頂点はどのような順番で彩色しても確実に彩色可能である頂点であるためである。しかしながら、彩色可能なグラフを彩色できない場合があるといった問題がある。
【００２８】
図３は、上記近似アルゴリズムで彩色できないグラフの一例を示す図である。
図３に示すグラフは五つの頂点を持ち、それらを二色で彩色可能なものである。しかしながら、上記近似アルゴリズムはそれらを二色で彩色することができない。
【００２９】
図４は、設定条件保持部１０、対応関係保持部２０および順番保持部４２を一つのテーブル７０で構成した例を示す図である。
このテーブル７０は図２に示した割り当て処理例に使用したデータに則している。テーブル７０は、項目として被割当対象、設定条件、順番および割当結果を持つ。被割当対象は頂点１〜４である。設定条件は各頂点１〜４ごとに、辺で結ばれた頂点を保持する。順番は除去された順番である。彩色する際はその逆の順番で彩色される。割当結果は各頂点１〜４ごとに、割り当てられた色を保持する。第１演算部４０は、テーブル７０を参照して被割当対象を選択することができる。また、被割当対象に割当対象を割り当てることができる。なお、第１演算部４０は被割当対象を選択する際、このテーブル７０ではなく他のテーブルを参照して選択してもよい。たとえば、項目として被割当対象、その被割当対象と接続されている他の被割当対象の数、を持つテーブルを参照して被割当対象を選択してもよい。
【００３０】
つぎに、厳密アルゴリズムの一例を説明する。この厳密アルゴリズムは彩色可能なグラフは必ず彩色できるアルゴリズムである。
手順１．彩色されていない頂点の中で、隣接頂点に割り当てられた異なる色の数が最大である頂点を選ぶ。そのような頂点が複数ある場合には、その中で色が割り当てられていない頂点集合により構成された誘導部分グラフ中、次数が最大のものを選ぶ。
手順２．選んだ頂点に彩色可能な色を一つ選び、彩色する。
手順３．手順１と手順２を繰り返す。手順２で割り当てる色がなくなった場合には、一つ前の頂点に戻り、別の色で彩色して再度手順１と手順２を繰り返す。
【００３１】
つぎに、本実施の形態に係る情報処理装置１００の動作について説明する。
図５は、実施の形態に係る情報処理装置１００の動作例１を説明するためのフローチャートである。
第１演算部４０は上述した近似アルゴリズムを実行する。選択部４１はグラフの中において次数が彩色数より小さい頂点が存在するか否か判断する（Ｓ１０）。存在する場合（Ｓ１０のＹ）、選択部４１はその一つ以上の頂点の中から任意の頂点を選択する（Ｓ１１）。そして、選択した頂点とその頂点に接続する辺をグラフから削除する（Ｓ１２）。その後、ステップＳ１０に遷移する。
【００３２】
判定部４５はステップＳ１０にて次数が彩色数より小さい頂点が存在しない場合（Ｓ１０のＮ）、グラフが空であるか否か判断する（Ｓ１３）。その判断結果を制御部６０に通知する。空でない場合（Ｓ１３のＮ）、第２演算部５０は制御部６０の指示にしたがい、当該近似アルゴリズムと異なる別のアルゴリズムを用いて、グラフ内の残りの頂点を彩色する（Ｓ１４）。そのアルゴリズムとして、上述した厳密アルゴリズムを用いることができる。ステップＳ１３にてグラフが空である場合（Ｓ１３のＹ）、ステップＳ１４をスキップする。
【００３３】
つぎに、制御部６０はグラフが初期状態であるか否か判断する（Ｓ１５）。初期状態である場合（Ｓ１５のＹ）、処理を終了する。ステップＳ１４にて厳密アルゴリズムによりすべての頂点が彩色された場合、および後述するステップＳ１６〜Ｓ１８の処理が繰り返されてすべての頂点が彩色された場合などが該当する。
【００３４】
ステップＳ１５にてグラフが初期状態でない場合（Ｓ１５のＮ）、第１割当部４３はステップＳ１２にて削除した順番と逆順に頂点を選択し（Ｓ１６）、その頂点とその頂点に接続していた辺をグラフ内に戻す（Ｓ１７）。その際、その頂点を、その頂点と辺で繋がる頂点と異なる色で彩色する（Ｓ１８）。その後、ステップＳ１５に遷移する。
【００３５】
図６は、実施の形態に係る情報処理装置１００の動作例２を説明するためのフローチャートである。動作例２に係る図６のフローチャートは、動作例１に係る図５のフローチャートと基本部分は同じである。以下、相違点および追加点について説明する。
図５のステップＳ１１の代わりに図６ではつぎの処理を行う。すなわち、選択部４１はグラフの中において次数が彩色数より小さい頂点のうち、最小の頂点を選択する（Ｓ１１’）。
【００３６】
また、ステップＳ１８にて彩色する際の色を、色別の頂点の数を斟酌して選択してもよい。たとえば、色別の頂点数に上限がある場合、各色の残り頂点数が多い色を優先的に選択してもよい。または、色別の頂点数を平均化したい場合、色別の頂点数が少ない色を優先的に選択してもよい。
【００３７】
つぎに、実施の形態に係る情報処理装置１００の適用例について説明する。
まず、適用例１として複数のＲＡＭに複数の変数を割り当てるＲＡＭ割り当てについて説明する。適用例１では上記割当対象がＲＡＭ、上記被割当対象が変数である。
【００３８】
図７は、実施の形態に係る情報処理装置１００の適用例１に係るプロセッサシステムを示す図である。
このプロセッサシステムは六個の演算器１〜６と四個のＲＡＭ１〜４を備える。各演算器１〜６は演算結果を任意のＲＡＭ１〜４に書き込むことができる。また、任意のＲＡＭ１〜４のデータを参照することもできる。このプロセッサシステムにおいて、特定のＲＡＭに対して同時に複数の演算器から値を書き込むことはできない。また、特定のＲＡＭから異なるデータを同時に複数の演算器に供給することもできない。
【００３９】
図８は、図７に示した適用例１に係るプロセッサシステムで利用される変数の一例を示す図である。より具体的には、図８は各タイミングにおいて各演算器１〜６が使用する変数を示す表である。
タイミング1では、変数aと変数bが同時に利用されるため、それらを一つのＲＡＭに格納することはできず、異なる二つのＲＡＭに割り当てられる。また、変数ｂと変数ｃは同時に利用されることがないため、同じＲＡＭに割り当ててもよい。
【００４０】
図９は、図８に示した表の変数ａ〜ｅの関係をグラフ化した図である。
変数ａ〜ｅを頂点とし、同じＲＡＭに割り当てられることができない変数同士を辺で結んだものである。このようにして生成されたグラフに対して、頂点彩色を行う。この場合、頂点に塗られる色がそれぞれのＲＡＭに対応し、ＲＡＭの数が彩色数となる。
【００４１】
同じ色で塗られた頂点は同じＲＡＭに格納される。単に塗り分けるだけでは特定のＲＡＭにだけ変数が集まってしまい、そのＲＡＭのサイズを超えてしまう可能性が高い。これを回避するため、複数のＲＡＭに割り当てられる変数を、残りのＲＡＭ容量を考慮して割り当てるとよい。すなわち、残りのＲＡＭ容量が多いＲＡＭに割り当てるとよい。これにより、ＲＡＭ容量に収められる可能性を高めることができる。なお、割り当てることが可能なＲＡＭの候補数が多いほど、よりＲＡＭ容量に収まる可能性が高くなる。
【００４２】
つぎに、適用例２として複数のレジスタに複数の変数を割り当てるレジスタ割り当てについて説明する。適用例２では上記割当対象がレジスタ、上記被割当対象が変数である。適用例２は適用例１と異なり、各レジスタは一単位のデータしか格納することがきない。
【００４３】
図１０は、実施の形態に係る情報処理装置１００の適用例２に係る、複数の変数ａ〜ｅの生存区間を示す図である。
ある変数に値が設定されその値が最後に読み出されるまで、その変数は一つのレジスタを占有する。この区間を生存区間と呼ぶ。図１０において、各線の開始位置がその線に対応する変数に値が設定される開始時間を示し、各線の終了位置が最後に読み出される終了時間を示す。この図では、変数ａと変数ｂは生存区間が重なっているが、変数ａと変数ｃは生存区間が重なっていない。二つの変数の生存区間が重ならない場合、同一のレジスタに割り当てることができるが、重なる場合、異なるレジスタに割り当てる必要がある。
【００４４】
図１１は、図１０に示した変数ａ〜ｅの生存区間の関係をグラフ化した図である。
変数ａ〜ｅを頂点とし、生存区間が重なる変数同士を辺で結んだものである。このようにして生成されたグラフに対して、頂点彩色を行う。この場合、頂点に塗られる色がそれぞれのレジスタに対応し、レジスタの数が彩色数となる。
【００４５】
つぎに、適用例３として複数の町に複数の色を割り当てる地図彩色について説明する。適用例３では上記割当対象が色、上記被割当対象が町である。すなわち、地図を見やすくするため、隣同士の町を異なる色で塗り分ける。
【００４６】
図１２は、実施の形態に係る情報処理装置１００の適用例３に係る、複数の町ａ〜ｉを含む地図を示す図である。この地図上において隣接する町を異なる色で塗る。
図１３は、図１２に示した複数の町ａ〜ｉの関係をグラフ化した図である。町ａ〜ｉを頂点とし、隣接する町を辺で結んだものである。
【００４７】
以上説明したように実施の形態によれば、近似アルゴリズムで解が求まらなかった問題に対して、厳密アルゴリズムを組み合わせることにより、頂点彩色の問題を、解への到達確率を高く維持しつつ高速処理することができる。厳密アルゴリズムのみを適用する場合に比べ、探索範囲を狭めて厳密アルゴリズムを適用することができるため、より高速に解を求めることができる。
【００４８】
また、次数がより少ない頂点を先に取り除くことにより、頂点を戻して彩色する際に、より後の段階で彩色の自由度を高めることができる。このような、次数がより少ない頂点を先に取り除く手法をＲＡＭ割り当てに適用した場合、各ＲＡＭのサイズに応じた変数の割り当てを容易にすることができる。取り除く頂点の順序を考慮しないと、後の彩色で特定の色の頂点だけが多くなってしまうケースが発生し得る。これは色別の数が重要となる分野でとくに問題となる。上述したＲＡＭ割り当てでは、色別の数がＲＡＭのサイズによって制限されるため、特定の色の頂点が多いとＲＡＭに入りきらないという問題が起きる。
【００４９】
たとえば、ＲＡＭのサイズを五とし、ＲＡＭ１にもＲＡＭ２にも割り当てることができる五つの変数を先に彩色し、ＲＡＭ１にしか割り当てることがきない五つの変数を後で彩色した場合を考える。先の五つの変数をすべてＲＡＭ１に割り当ててしまうと、残りの五つの変数を割り当てられなくなってしまう。上述した方式では、ＲＡＭ１とＲＡＭ２に割り当てられる変数が後に彩色されるため、最初にＲＡＭ１にのみ割り当てる変数を割り当てた後、残りの五つの変数を残ったＲＡＭ２に割り当てることができる。
【００５０】
以上、本発明をいくつかの実施形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５１】
図５、６に示したフローチャートのステップＳ１０では、彩色数より少ない次数が存在する間、ステップＳ１３には遷移しないが、所定数の頂点を選択したらステップＳ１３に遷移するように処理してもよい。
【図面の簡単な説明】
【００５２】
【図１】本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図２】近似アルゴリズムの一例を説明するための図である。
【図３】近似アルゴリズムで彩色できないグラフの一例を示す図である。
【図４】設定条件保持部、対応関係保持部および順番保持部を一つのテーブルで構成した例を示す図である。
【図５】実施の形態に係る情報処理装置の動作例１を説明するためのフローチャートである。
【図６】実施の形態に係る情報処理装置の動作例２を説明するためのフローチャートである。
【図７】実施の形態に係る情報処理装置の適用例１に係るプロセッサシステムを示す図である。
【図８】図７に示した適用例１に係るプロセッサシステムで利用される変数の一例を示す図である。
【図９】図８に示した表の変数ａ〜ｅの関係をグラフ化した図である。
【図１０】実施の形態に係る情報処理装置の適用例２に係る、複数の変数ａ〜ｅの生存区間を示す図である。
【図１１】図１０に示した変数ａ〜ｅの生存区間の関係をグラフ化した図である。
【図１２】実施の形態に係る情報処理装置の適用例３に係る、複数の町ａ〜ｉを含む地図を示す図である。
【図１３】図１２に示した複数の町ａ〜ｉの関係をグラフ化した図である。
【符号の説明】
【００５３】
１０ 設定条件保持部、 ２０ 対応関係保持部、 ３０ 演算部、 ４０ 第１演算部、 ４１ 選択部、 ４２ 順番保持部、 ４３ 第１割当部、 ４４ 第１登録部、 ４５ 判定部、 ５０ 第２演算部、 ５３ 第２割当部、 ５４ 第２登録部、 ６０ 制御部、 ７０ テーブル、 １００ 情報処理装置。
【特許請求の範囲】
【請求項１】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを実行する第１演算部と、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件にしたがい前記割当対象を割り当てる、前記第１アルゴリズムと異なる第２アルゴリズムを実行する第２演算部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記第１演算部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記第１演算部は、選択した順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記第１演算部または前記第２演算部により既に割り当てられた、前記被割当対象と前記割当対象との対応関係を保持する対応関係保持部をさらに備え、
前記第１演算部は、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択する選択部と、
前記選択部により選択された被割当対象に対して、前記設定条件保持部により保持される設定条件および前記対応関係保持部に保持される対応関係を参照して、前記割当対象を順次割り当てる第１割当部と、
前記第１割当部による割り当て結果を前記対応関係保持部に登録する第１登録部と、
前記複数の被割当対象のすべてが前記選択部により選択できたか否かを判定する判定部と、を含み、
前記第２演算部は、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件保持部により保持される設定条件および前記対応関係保持部に保持される対応関係を参照して、前記割当対象を割り当てる第２割当部と、
前記第２割当部による割り当て結果を前記対応関係保持部に登録する第２登録部と、を含むことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記第１演算部および前記第２演算部の演算処理を制御する制御部をさらに備え、
前記制御部は、前記判定部による判定の結果、前記複数の被割当対象のすべてが前記選択部により選択できなかったとき、先に、その選択できなかった被割当対象に対して前記割当対象を割り当てるよう前記第２割当部を制御し、その後に、前記選択部により選択できた被割当対象に対して前記割当対象を割り当てるよう前記第１割当部を制御し、
前記制御部は、前記判定部による判定の結果、前記複数の被割当対象のすべてが前記選択部により選択できたとき、すべての被割当対象に対して前記割当対象を割り当てるよう前記第１割当部を制御することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記第１演算部は、
前記選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部をさらに含み、
前記選択部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記第１割当部は、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項３または４に記載の情報処理装置。
【請求項６】
前記選択部は、各選択時点において前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象のうち、前記同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象を選択することを特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記第２アルゴリズムは、前記複数の被割当対象のすべてに対して前記設定条件にしたがう前記割当対象の割り当てが可能な場合、必ず割り当てできるアルゴリズムであることを特徴とする請求項１から６のいずれかに記載の情報処理装置。
【請求項８】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、
既に割り当てられた、前記被割当対象と前記割当対象との対応関係を保持する対応関係保持部と、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象のうち、前記同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象から順に選択する選択部と、
前記選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部と、
前記選択部により選択された被割当対象に対して、前記対応関係保持部に保持される前記対応関係を参照して、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていく割当部と、
を備えることを特徴とする情報処理装置。
【請求項９】
前記選択部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記割当部は、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
前記被割当対象は、所定の変数であり、
前記割当対象は、前記変数を格納する、レジスタまたはメモリであることを特徴とする請求項１から９のいずれかに記載の情報処理装置。
【請求項１１】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる割当方法であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を設定条件保持部に保持する第１ステップと、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを第１演算部に実行させる第２ステップと、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件にしたがい前記割当対象を割り当てる、前記第１アルゴリズムと異なる第２アルゴリズムを第２演算部に実行させる第３ステップと、
を備えることを特徴とする割当方法。
【請求項１２】
前記第２ステップは、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
第４ステップとして、選択した順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項１１に記載の割当方法。
【請求項１】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを実行する第１演算部と、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件にしたがい前記割当対象を割り当てる、前記第１アルゴリズムと異なる第２アルゴリズムを実行する第２演算部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記第１演算部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記第１演算部は、選択した順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記第１演算部または前記第２演算部により既に割り当てられた、前記被割当対象と前記割当対象との対応関係を保持する対応関係保持部をさらに備え、
前記第１演算部は、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択する選択部と、
前記選択部により選択された被割当対象に対して、前記設定条件保持部により保持される設定条件および前記対応関係保持部に保持される対応関係を参照して、前記割当対象を順次割り当てる第１割当部と、
前記第１割当部による割り当て結果を前記対応関係保持部に登録する第１登録部と、
前記複数の被割当対象のすべてが前記選択部により選択できたか否かを判定する判定部と、を含み、
前記第２演算部は、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件保持部により保持される設定条件および前記対応関係保持部に保持される対応関係を参照して、前記割当対象を割り当てる第２割当部と、
前記第２割当部による割り当て結果を前記対応関係保持部に登録する第２登録部と、を含むことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記第１演算部および前記第２演算部の演算処理を制御する制御部をさらに備え、
前記制御部は、前記判定部による判定の結果、前記複数の被割当対象のすべてが前記選択部により選択できなかったとき、先に、その選択できなかった被割当対象に対して前記割当対象を割り当てるよう前記第２割当部を制御し、その後に、前記選択部により選択できた被割当対象に対して前記割当対象を割り当てるよう前記第１割当部を制御し、
前記制御部は、前記判定部による判定の結果、前記複数の被割当対象のすべてが前記選択部により選択できたとき、すべての被割当対象に対して前記割当対象を割り当てるよう前記第１割当部を制御することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記第１演算部は、
前記選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部をさらに含み、
前記選択部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記第１割当部は、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項３または４に記載の情報処理装置。
【請求項６】
前記選択部は、各選択時点において前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象のうち、前記同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象を選択することを特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記第２アルゴリズムは、前記複数の被割当対象のすべてに対して前記設定条件にしたがう前記割当対象の割り当てが可能な場合、必ず割り当てできるアルゴリズムであることを特徴とする請求項１から６のいずれかに記載の情報処理装置。
【請求項８】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる情報処理装置であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を保持する設定条件保持部と、
既に割り当てられた、前記被割当対象と前記割当対象との対応関係を保持する対応関係保持部と、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象のうち、前記同一の割当対象の割り当てが制限される被割当対象の数が最も小さい被割当対象から順に選択する選択部と、
前記選択部により選択された被割当対象とその順番とを対応付けて保持する順番保持部と、
前記選択部により選択された被割当対象に対して、前記対応関係保持部に保持される前記対応関係を参照して、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていく割当部と、
を備えることを特徴とする情報処理装置。
【請求項９】
前記選択部は、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
前記割当部は、前記順番保持部に保持される順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
前記被割当対象は、所定の変数であり、
前記割当対象は、前記変数を格納する、レジスタまたはメモリであることを特徴とする請求項１から９のいずれかに記載の情報処理装置。
【請求項１１】
複数の被割当対象のそれぞれに、あらかじめ定められた設定条件にしたがい、それぞれ異なる複数の割当対象から一つを選択して割り当てる割当方法であって、
前記設定条件として、各被割当対象ごとに自己以外の被割当対象のうち同一の割当対象の割り当てが制限される被割当対象を特定する情報を設定条件保持部に保持する第１ステップと、
前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を少なくとも一つ選択する第１アルゴリズムを第１演算部に実行させる第２ステップと、
前記複数の被割当対象のうち前記第１演算部により選択されていない被割当対象に対して、前記設定条件にしたがい前記割当対象を割り当てる、前記第１アルゴリズムと異なる第２アルゴリズムを第２演算部に実行させる第３ステップと、
を備えることを特徴とする割当方法。
【請求項１２】
前記第２ステップは、前記同一の割当対象の割り当てが制限される被割当対象の数が、被割当対象に割当可能な前記複数の割当対象の数より少ない被割当対象を選択していき、各選択時点において、選択した被割当対象を次の選択時点における選択対象から除去し、かつその選択した被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その選択した被割当対象との関係における制限を解除し、
第４ステップとして、選択した順番と逆の順番で前記割当対象を割り当てていき、各割り当て時点において、割り当てた被割当対象と同一の割当対象の割り当てが制限される被割当対象について、その割り当てた被割当対象との関係における制限を復活させることを特徴とする請求項１１に記載の割当方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００９−１８１２７９（Ｐ２００９−１８１２７９Ａ）
【公開日】平成２１年８月１３日（２００９．８．１３）
【国際特許分類】
【出願番号】特願２００８−１８９２３（Ｐ２００８−１８９２３）
【出願日】平成２０年１月３０日（２００８．１．３０）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
【公開日】平成２１年８月１３日（２００９．８．１３）
【国際特許分類】
【出願日】平成２０年１月３０日（２００８．１．３０）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
[ Back to top ]