TOP > 国内特許検索 > 情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラム > 明細書

明細書 :情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4882073号 (P4882073)
公開番号 特開2008-225750 (P2008-225750A)
登録日 平成23年12月16日(2011.12.16)
発行日 平成24年2月22日(2012.2.22)
公開日 平成20年9月25日(2008.9.25)
発明の名称または考案の名称 情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラム
国際特許分類 G06F  17/50        (2006.01)
G06F  19/24        (2011.01)
FI G06F 17/50 658A
G06F 17/50 658E
G06F 19/00 624
請求項の数または発明の数 6
全頁数 10
出願番号 特願2007-061826 (P2007-061826)
出願日 平成19年3月12日(2007.3.12)
審査請求日 平成22年1月27日(2010.1.27)
特許権者または実用新案権者 【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】山川 烈
【氏名】堀尾 恵一
【氏名】星野 雅治
個別代理人の代理人 【識別番号】110000154、【氏名又は名称】特許業務法人はるか国際特許事務所
審査官 【審査官】田中 幸雄
参考文献・文献 山川烈ほか,入力データ集合がグラフで表現された自己組織化マップ,第22回ファジィシステムシンポジウム講演論文集,日本,日本知能情報ファジィ学会,2006年 9月 6日,77-80頁,6B2-1
調査した分野 G06F 17/50
G06F 19/24
特許請求の範囲 【請求項1】
入力層及び競合層がそれぞれグラフで表現された自己組織化マップに関する情報処理を行う情報処理装置であって、
前記入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、
前記競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段と、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、
を含むことを特徴とする情報処理装置。
【請求項2】
請求項1に記載の情報処理装置において、
前記移動手段は、前記各ノードに関する位置を、該位置から前記入力手段により入力される位置に至る前記入力層に係るグラフ上の最短経路に沿ってそれぞれ移動させる、
ことを特徴とする情報処理装置。
【請求項3】
入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、
競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段、
前記入力層に係るグラフ上の位置を入力する入力手段、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段
としてコンピュータを機能させるためのプログラム。
【請求項4】
入力層及び競合層がそれぞれグラフで表現された自己組織化マップを用いて回路のレイアウト設計を行うレイアウト装置であって、
前記入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、
前記競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段と、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、
を含むことを特徴とするレイアウト装置。
【請求項5】
請求項4に記載のレイアウト装置において、
前記移動手段は、前記各ノードに関する位置を、該位置から前記入力手段により入力される位置に至る前記入力層に係るグラフ上の最短経路に沿ってそれぞれ移動させる、
ことを特徴とするレイアウト装置。
【請求項6】
入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、
競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段
としてコンピュータを機能させるためのプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラムに関し、特にグラフからグラフへの位相保持写像の実装に関する。
【背景技術】
【0002】
グラフは、幾つかの要素とそれらの結びつきを数学的に表現する手法であり、電子回路やWWW(World Wide Web)等の接続状態を表現することのできる重要な数学的概念である。グラフの応用では、グラフをその位相を保持しながら平面に写像することがしばしば必要となる。例えば、電子回路のレイアウト設計を行う際には、電子回路の接続状態を示すグラフを、基板を示す平面に写像しなければならない。さらに実用上は、位相を保持しながらグラフからグラフへ写像する手法も重要である。すなわち、電子部品を配置できない場所がある基板をグラフにより近似的に表現して、電子回路の接続状態を示すグラフを、そのような基板を示すグラフに写像することにより、レイアウトに制約のある基板への電子部品の適切な配置を得ることができる。
【0003】
従来、位相を保持した写像関係を獲得するアルゴリズムとしては、自己組織化マップが知られている。自己組織化マップは、外界からの刺激に対して自らを変化させ、適応させていく、脳の学習機構の数理モデルであって、外界から信号が与えられると、互いに類似している信号はマップ上の近い位置に写像される一方、類似していない信号はマップ上の離れた位置に写像され、これにより位相保持写像が実現される。
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、従来の自己組織化マップはグラフを扱うことができず、従って回路レイアウト設計等への応用に限界があった。
【0005】
本発明は上記課題に鑑みてなされたものであって、その目的は、グラフからグラフへの位相保持写像を実現できる情報処理装置、方法並びにプログラム、及びそれを用いたレイアウト装置、方法並びにプログラムを提供することにある。
【課題を解決するための手段】
【0006】
上記課題を解決するために、本発明に係る情報処理装置は、入力層及び競合層がそれぞれグラフで表現された自己組織化マップに関する情報処理を行う情報処理装置であって、前記入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、前記競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、前記入力層に係るグラフ上の位置を入力する入力手段と、前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、を含むことを特徴とする。
【0007】
また、本発明に係る情報処理方法は、入力層及び競合層がそれぞれグラフで表現された自己組織化マップに関する情報処理を行う情報処理方法であって、前記入力層に係るグラフ上の位置を入力する入力ステップと、前記入力ステップで入力される位置と、前記競合層に係るグラフの各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択ステップと、前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択ステップで選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力ステップで入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動ステップと、を含むことを特徴とする。
【0008】
また、本発明に係るプログラムは、入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段、前記入力層に係るグラフ上の位置を入力する入力手段、前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段としてコンピュータを機能させるためのプログラムである。プログラムは、CD-ROMやDVD-ROM等のコンピュータ読取可能な情報記憶媒体に格納されてもよい。
【0009】
本発明では、位置を入力すると、入力層に係るグラフにおいてその位置と近傍に位置するノードが、競合層に係るグラフのノードから選択される。さらに、競合層に係るグラフの各ノードに関する位置と選択されたノードの位置との距離、及び入力される位置に従って、競合層に係るグラフの各ノードに関する位置が更新される。このとき、更新後の位置は、入力層に係るグラフ上の位置に拘束されるようになっている。本発明によれば、グラフからグラフへの位相保持写像を実現でき、回路レイアウトの設計等への応用が可能となる。
【0010】
また、本発明に係るレイアウト装置は、入力層及び競合層がそれぞれグラフで表現された自己組織化マップを用いて回路のレイアウト設計を行うレイアウト装置であって、前記入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、前記競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、前記入力層に係るグラフ上の位置を入力する入力手段と、前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、を含むことを特徴とする。
【0011】
また、本発明に係るレイアウト方法は、入力層及び競合層がそれぞれグラフで表現された自己組織化マップを用いて回路のレイアウト設計を行うレイアウト方法であって、前記入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフ上の位置を入力する入力ステップと、前記入力ステップで入力される位置と、前記競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択ステップと、前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択ステップで選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力ステップで入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動ステップと、を含むことを特徴とする。
【0012】
また、本発明に係るプログラムは、入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、前記入力層に係るグラフ上の位置を入力する入力手段、前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフの構造に応じて算出される距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフの構造に応じた距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段としてコンピュータを機能させるためのプログラムである。
【0013】
本発明によると、入力層に係るグラフにより基板におけるレイアウト可能な領域が表現され、競合層に係るグラフにより回路構造が表現される。そして、競合層に係るグラフの各ノードに関する位置として、回路要素の位置が算出される。本発明によると、レイアウト上の制約がある基板に対して、総配線長を短くしつつ回路要素を配置することができるようになる。
【0014】
なお、前記移動手段は、前記各ノードに関する位置を、該位置から前記入力手段により入力される位置に至る前記入力層に係るグラフ上の最短経路に沿ってそれぞれ移動させてよい。
【発明を実施するための最良の形態】
【0015】
以下、本発明の一実施形態について図面に基づき詳細に説明する。
【0016】
図1は、本発明の一実施形態に係る情報処理装置により処理される自己組織化マップの概念図である。同図に示すように、この自己組織化マップは、入力層と競合層とから構成されており、いずれの層もグラフ構造を有している。
【0017】
すなわち、入力層では、図中白丸又は黒丸で示されるノードが、図中実線で示されるエッジにより接続されている。この入力層のグラフ構造を記述するため、本情報処理装置では、各ノードの識別情報に関連づけて、その平面位置座標、各ノードがどのノードと接続されているかを示す接続情報を記憶している。
【0018】
また、競合層では、図中白丸又は黒丸で示されるユニットが、図中実線で示されるエッジにより接続されている。この競合層のグラフ構造を記述するため、本情報処理装置では、各ユニットの識別情報に関連づけて、各ユニットがどのユニットと接続されているかを示す接続情報を記憶している。さらに、競合層の各ユニットUには、同図中、破線で示されるように入力層グラフのいずれかのノードの位置がユニット位置wとして関連づけられている。このユニット位置wは、従来一般の自己組織化マップにおける結合重みベクトルに相当するものである。そして、本情報処理装置では、競合層の各ユニットの識別情報に関連づけて、ユニット位置w(入力層グラフにおけるノード位置(ノードの識別情報))が記憶されている。
【0019】
この自己組織化マップでは、入力層グラフのいずれかのノードの位置が入力位置x(図中×印で示される)として指定される。すると、ユニット位置wのうち、入力位置xとの、入力層グラフ上の距離が最も近いものが判定され、そのユニット位置wに関連づけられた競合層のユニットが勝者ユニットUとして選択される。すなわち、勝者ユニットの序数cは、次式(1)により表される。ここで、arg minは、引数を最小化する序数を返す関数である。また、d(x,w)は、入力位置xとユニット位置wとの入力層グラフ上の距離である。グラフ上の距離は、グラフ上の最短経路の意味であり、例えばダイクストラ法などにより求められる。
【0020】
【数1】
JP0004882073B2_000002t.gif

【0021】
その後、競合層の各ユニットUについて、近傍係数hが次式(2)に従って算出される。
【0022】
【数2】
JP0004882073B2_000003t.gif

【0023】
ここで、rはユニットUの識別情報であり、rは勝者ユニットUの識別情報であり、d(r,r)はユニットUと勝者ユニットUとの競合層グラフ上の距離である。グラフ上の距離は、グラフ上の最短経路の意味であり、例えばダイクストラ法などにより求められる。また、σ(t)は学習係数であり、学習ステップtに従って減少する関数である。これにより、学習ステップtに従って勝者ユニットUの近傍範囲が狭まるようになっている。
【0024】
次に、競合層の各ユニットUのユニット位置wが次式(3)に従って更新される。
【0025】
【数3】
JP0004882073B2_000004t.gif

【0026】
ここで、wnewは、更新後のユニット位置wであり、関数moveは、更新前のユニット位置woldを、入力位置xの方向に、入力層グラフ上の最短経路に沿って、距離α(t)h(x,wold)だけ移動したノードを返す関数である。moveは、次式(4)により定義できる。
【0027】
【数4】
JP0004882073B2_000005t.gif

【0028】
ここで、vは、更新前のユニット位置woldから入力位置xの方向にグラフ上の最短経路に沿って距離の近い順に順序付けされたノードの識別情報である。この最短経路に含まれるノード数をNとすると、v=woldとなり、v=xとなる。また、α(t)は学習係数であり、学習ステップtに従って減少する。
【0029】
こうして、勝者ユニットUとの競合層グラフ上の距離(近傍係数h)、及び入力位置xに従って、入力層グラフ上の他の位置にそれぞれ変更される。特に、本更新式によると、図2に示すように、各ユニット位置wは、該位置から入力位置xに至る入力層の最短経路に沿ってそれぞれ移動する。以上の処理を様々な入力位置xについて繰り返すことにより、学習後のユニット位置wを得ることができる。
【0030】
すなわち、図3(a)に示すように、基板における回路要素を配置可能な領域にノード及びエッジを配置し、配置不能な領域にはそれらが配置されないように、入力層グラフを構成する。同図では、実線がエッジを示し、その交点がノードを示している。また、同図(b)に示すように、回路要素を競合層のユニット(ノード)とし、それらの間の配線をユニット間のリンク(エッジ)とするよう、競合層グラフを構成する。同図では、白丸が回路要素を示し、実線が配線を示している。そして、入力層グラフのノードの位置を入力位置xとして図1に示す自己組織化マップに入力し、それに応じて競合層のユニットのユニット位置wを更新することにより、同図(c)に示すように、ユニット位置wが基板における望ましい配置位置を示すものとなる。
【0031】
図4は、本実施形態に係る情報処理装置の機能ブロック図である。本情報処理装置は、パーソナルコンピュータなどの公知のコンピュータシステムに本発明を適用したプログラムを実行させることにより実現されるものであり、機能的には、入力層グラフ記憶部10、競合層グラフ記憶部12、入力部14、勝者ユニット決定部16、近傍係数算出部18、ユニット位置更新部20を含んでいる。なお、プログラムはCD-ROMなどのコンピュータ読取可能な情報記憶媒体からコンピュータにインストールされてもよいし、インターネットなどのデータ通信ネットワークからダウンロードされてもよい。
【0032】
入力層グラフ記憶部10は、入力層グラフの構造、及び該グラフの各ノードの位置座標を記憶するものである。競合層グラフ記憶部12は、競合層グラフの構造、及び競合層の各ユニットUのユニット位置wを記憶するものである。
【0033】
入力部14は、入力層グラフ上の位置、すなわち入力位置xを入力するものである。ここでは、入力層グラフのいずれかのノードの識別情報を入力するようにしている。勝者ユニット決定部16は、入力位置xと、各ユニット位置wと、の入力層グラフ上の距離dに従って、競合層のユニットUの中から1つを勝者ユニットUとして選択するものである。
【0034】
近傍係数算出部18は、各ユニットUについて、勝者ユニットUとの競合層グラフ上の距離d(r,r)を算出するとともに、該距離に基づいて式(2)に示される近傍係数hを算出するものである。
【0035】
ユニット位置更新部20は、こうして算出される近傍係数h、及び入力位置xに従って、各ユニット位置wを更新するものである。ここでは、更新前のユニット位置woldから入力位置xに至る入力層グラフ上の最短経路に従って移動させて、更新後のユニット位置wnewを得るようにしている。
【0036】
本実施形態によると、グラフからグラフへの位相保持写像を実現できる。また、これにより回路レイアウトの設計等への応用が可能となる。特に、図2に示すように入力層グラフにより配置に制約のある基板を示すようにして、競合層グラフにより回路を示すようにすれば、容易に制約のある基盤への回路レイアウトができるようになる。
【0037】
なお、本発明は種々の変形実施が可能である。例えば、以上の説明ではユニット位置wを入力層グラフのノード位置に対応づけたが、エッジの位置に対応づけてもよい。この場合も、入力層グラフの構造に従って入力位置xに対する各ユニット位置wの距離を算出し、これにより勝者ユニットUを選出すればよい。また、近傍係数も、競合層グラフ上の距離に従って算出すればよい。また、この変形例では、入力位置xとして、入力層グラフのエッジの位置を示す情報を入力してもよい。
【0038】
さらに、入力位置xを自己組織化マップに入力する毎にユニット位置wを更新する代わりに、多数の入力位置xを入力し終えてから、ユニット位置wを更新するようにしてもよい。この場合も、入力位置x及びその入力位置xに対応する近傍係数hに従って、入力層グラフ上の位置をユニット位置wとして決定すればよい。例えば、全ての入力位置xについて、それに対する勝者ユニットUciを上記式(1)と同様にして算出するとともに、その勝者ユニットUciに関する近傍係数hijを上記式(2)と同様にして算出した後に、次式(5)に従って、ユニット位置wを更新すればよい。
【0039】
【数5】
JP0004882073B2_000006t.gif

【0040】
これは、自己組織化マップのエネルギー関数を最小化するユニット位置wを求めることに相当する。このようにすれば、入力位置xの入力順に依存しない学習結果を得ることができる。この場合も、入力位置xやユニット位置wを入力層グラフのエッジに位置させてよいのはもちろんである。
【図面の簡単な説明】
【0041】
【図1】本発明の実施形態に係る情報処理装置で実装される自己組織化マップの概念図である。
【図2】ユニット位置の更新方法を説明する図である。
【図3】入力層グラフ及び競合層グラフを示す図である。
【図4】本発明の実施形態に係る情報処理装置の機能ブロック図である。
【符号の説明】
【0042】
10 入力層グラフ記憶部、12 競合層グラフ記憶部、14 入力部、16 勝者ユニット決定部、18 近傍係数算出部、20 ユニット位置更新部。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3