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

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

国内特許コード P09A014802
掲載日 2009年11月13日
出願番号 特願2007-061826
公開番号 特開2008-225750
登録番号 特許第4882073号
出願日 平成19年3月12日(2007.3.12)
公開日 平成20年9月25日(2008.9.25)
登録日 平成23年12月16日(2011.12.16)
発明者
  • 山川 烈
  • 堀尾 恵一
  • 星野 雅治
出願人
  • 国立大学法人九州工業大学
発明の名称 情報処理装置並びに方法、それを用いたレイアウト装置並びに方法、及びプログラム
発明の概要

【課題】グラフからグラフへの位相保持写像を実現する。
【解決手段】自己組織化マップの入力層及び競合層をそれぞれグラフで表現しておき、入力位置xと、競合層の各ユニットに関するユニット位置wと、の入力層グラフ上の距離に従って、勝者ユニットUを選択するとともに、各ユニット位置wを、勝者ユニットUとの競合層グラフ上の距離、及び入力位置xに従って、入力層グラフ上の他の位置にそれぞれ変更する。
【選択図】図1

従来技術、競合技術の概要


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



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

産業上の利用分野


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

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

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

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

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

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

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

※ 画像をクリックすると拡大します。

JP2007061826thum.jpg
出願権利状態 権利存続中
詳細は、下記「問合せ先」まで直接お問い合わせください。


PAGE TOP

close
close
close
close
close
close
close