Top > Search of Japanese Patents > INFORMATION PROCESSOR AND METHOD, LAYOUT DEVICE AND METHOD USING THE SAME, AND PROGRAM

INFORMATION PROCESSOR AND METHOD, LAYOUT DEVICE AND METHOD USING THE SAME, AND PROGRAM

Patent code P09A014802
Posted date Nov 13, 2009
Application number P2007-061826
Publication number P2008-225750A
Patent number P4882073
Date of filing Mar 12, 2007
Date of publication of application Sep 25, 2008
Date of registration Dec 16, 2011
Inventor
  • (In Japanese)山川 烈
  • (In Japanese)堀尾 恵一
  • (In Japanese)星野 雅治
Applicant
  • (In Japanese)国立大学法人九州工業大学
Title INFORMATION PROCESSOR AND METHOD, LAYOUT DEVICE AND METHOD USING THE SAME, AND PROGRAM
Abstract PROBLEM TO BE SOLVED: To materialize topological mapping between graphs.
SOLUTION: A competitive layer and an input layer of a self-organizing map are expressed by graphs, a winner unit Uc is selected according to a distance on the input layer graph between an input position x, a unit position wj related to each unit of the competitive layer, and each the unit position wj is changed into other position on the input layer graph according to the input position x and a distance on the competitive layer graph with the winner unit Uc.
Outline of related art and contending technology (In Japanese)


グラフは、幾つかの要素とそれらの結びつきを数学的に表現する手法であり、電子回路やWWW(World Wide Web)等の接続状態を表現することのできる重要な数学的概念である。グラフの応用では、グラフをその位相を保持しながら平面に写像することがしばしば必要となる。例えば、電子回路のレイアウト設計を行う際には、電子回路の接続状態を示すグラフを、基板を示す平面に写像しなければならない。さらに実用上は、位相を保持しながらグラフからグラフへ写像する手法も重要である。すなわち、電子部品を配置できない場所がある基板をグラフにより近似的に表現して、電子回路の接続状態を示すグラフを、そのような基板を示すグラフに写像することにより、レイアウトに制約のある基板への電子部品の適切な配置を得ることができる。



従来、位相を保持した写像関係を獲得するアルゴリズムとしては、自己組織化マップが知られている。自己組織化マップは、外界からの刺激に対して自らを変化させ、適応させていく、脳の学習機構の数理モデルであって、外界から信号が与えられると、互いに類似している信号はマップ上の近い位置に写像される一方、類似していない信号はマップ上の離れた位置に写像され、これにより位相保持写像が実現される。

Field of industrial application (In Japanese)


本発明は情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラムに関し、特にグラフからグラフへの位相保持写像の実装に関する。

Scope of claims (In Japanese)
【請求項1】
 
入力層及び競合層がそれぞれグラフで表現された自己組織化マップに関する情報処理を行う情報処理装置であって、
前記入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、
前記競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段と、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、
を含むことを特徴とする情報処理装置。

【請求項2】
 
請求項1に記載の情報処理装置において、
前記移動手段は、前記各ノードに関する位置を、該位置から前記入力手段により入力される位置に至る前記入力層に係るグラフ上の最短経路に沿ってそれぞれ移動させる、
ことを特徴とする情報処理装置。

【請求項3】
 
入力層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、
競合層に係るグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段、
前記入力層に係るグラフ上の位置を入力する入力手段、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段
としてコンピュータを機能させるためのプログラム。

【請求項4】
 
入力層及び競合層がそれぞれグラフで表現された自己組織化マップを用いて回路のレイアウト設計を行うレイアウト装置であって、
前記入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段と、
前記競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段と、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段と、
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段と、
を含むことを特徴とするレイアウト装置。

【請求項5】
 
請求項4に記載のレイアウト装置において、
前記移動手段は、前記各ノードに関する位置を、該位置から前記入力手段により入力される位置に至る前記入力層に係るグラフ上の最短経路に沿ってそれぞれ移動させる、
ことを特徴とするレイアウト装置。

【請求項6】
 
入力層に係るグラフであって、レイアウト可能な領域にノード及びエッジが配置されたグラフの構造及び該グラフの各ノードに関する位置を記憶する入力層グラフ記憶手段、
競合層に係るグラフであって、前記回路の要素を示すノード及び配線を示すエッジを含むグラフの構造及び該グラフの各ノードに関する位置を記憶する競合層グラフ記憶手段と、
前記入力層に係るグラフ上の位置を入力する入力手段、
前記入力手段により入力される位置と、前記競合層グラフ記憶手段に記憶される各ノードに関する位置と、の前記入力層に係るグラフ上の最短経路の距離に従って、前記競合層に係るグラフのノードを少なくとも1つ選択するノード選択手段、及び
前記競合層に係るグラフの各ノードに関する位置を、前記ノード選択手段により選択されるノードとの前記競合層に係るグラフ上の最短経路の距離、及び前記入力手段により入力される位置に従って、前記入力層に係るグラフ上の他の位置にそれぞれ変更する移動手段
としてコンピュータを機能させるためのプログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007061826thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close