アモルファス・コンピューティング
From Wikipedia, the free encyclopedia
アモルファスコンピューティングとは、計算能力とメモリが限られた多数の同一の並列プロセッサが局所的に相互作用する系でモデル化されるような計算、およびそのようなシステムを研究する学術分野である。アモルファスコンピューティングという用語は、1996年にMITでHal Abelson, Thomas F. Knight, Gerald Jay Sussmanらによって発表された論文"Amorphous Computing Manifesto"の中で初めて用いられた。
自然科学におけるアモルファスコンピューティングの例は、発生生物学（単一細胞からの多細胞生物の発生）、分子生物学（細胞内コンパートメントの組織化と細胞内シグナル伝達）、ニューラルネットワーク、化学工学（非平衡系）など、多くの分野で見られる。アモルファスコンピューティングについての研究は、ハードウェア的な実装（生物学、電子工学、ナノテクノロジーなど）に依存せず、既存の天然システムの理解や新しいシステムのエンジニアリングを目標としてアルゴリズムの特性評価に重点が置かれる。アモルファスコンピューティングにおける各プロセッサは、自身のメモリと隣接する他のプロセッサの情報は参照できるが、系のグローバル状態について知る術を持たない。この分野の主要な課題は、メモリ・計算能力・知覚可能な範囲が限られた多数のプロセッサの自己組織化を制御して、系全体の状態をプログラム可能にするアルゴリズムを探索することにある。将来的に、アモルファスなコンピュータはエンジニアリングされた細胞を用いて合成生物学的に実装されうる。
アモルファスコンピュータは、次のような特性を持つ傾向にある。
- 冗長化された、潜在的に故障する可能性のある、大規模に並列化されたデバイス群で実装される
- デバイスは、制限されたメモリと計算能力を持つ
- 非同期のデバイス
- 初期状態においてデバイスは自身の位置についての情報を持たない
- デバイス同士の通信はローカルに限定される
- 創発的または自己組織化の動作（個々のデバイスよりも大きなパターンまたは状態）を示す
- 偶発的に発生する不正なデバイス動作や状態の変動に対して耐性を持つ
(これらのアルゴリズムの中には、名前が知られていないものもある。名前が知られていない場合は、説明的な名前を記している。)
- 「フィック型通信」 デバイスは、デバイスが存在する媒体を介して拡散するメッセージを生成することで通信する。メッセージの強度は、フィックの拡散の法則で説明される逆二乗則に従う。このような通信の例は、生物系や化学系でよく見られる。
- 「リンク拡散型通信」 デバイスは、デバイスからデバイスへと有線接続されたリンクを介してメッセージを伝播させることで通信。「フィック型通信」とは異なり、デバイスが存在する拡散媒体は必ずしも存在しないため、空間次元は無関係であり、フィックの法則は適用されない。例としては、拡散更新アルゴリズムなどのインターネットルーティングアルゴリズムが挙げられる。アモルファスコンピューティングに関する文献で説明されているアルゴリズムのほとんどは、この種の通信を前提としている。
- 「波動伝搬」 (Ref 1) デバイスは、ホップカウントが符号化されたメッセージを送信する。以前にメッセージを受信していないデバイスは、ホップカウントをインクリメントして再送信する。波動は媒体を介して伝播し、媒体を介したホップカウントは、送信元からの距離勾配を効果的に符号化する。
- 「ランダムID」 重複を排除するのに十分な大きさのID空間から各デバイスが自身にランダムなIDを付与する。
- 「成長点(Growing-point)プログラム」 （Coore）。「屈性」（外部刺激による生物の動き）に従ってデバイス間を移動するプロセス。
- 「波動座標」 DARPA PPT slides参照
- 「近傍クエリ」 (Nagpal）。デバイスは、プッシュまたはプルメカニズムのいずれかによって、近傍の状態をサンプリングする。
- 「ピアプレッシャー」 各デバイスは状態を維持し、その状態を近傍デバイスに伝達する。各デバイスは、何らかの投票スキームを使用して、近傍の状態に変更するかどうかを決定する。このアルゴリズムは、初期分布に従って空間を分割するものであり、クラスタリングアルゴリズムの一例である。
- 「自己維持ライン」 (Lauren Lauren, Clement). リンク拡散通信を介して、デバイスで覆われた平面上の1つの端点から勾配が作成される。各デバイスは、勾配における自身の値と、勾配の原点に近い隣接デバイスのIDを認識する。反対側の端点は勾配を検出し、より近い隣接デバイスにそれが直線の一部であることを通知する。これは勾配を伝播し、磁場の乱れに対して堅牢な直線を形成する。
- 「クラブ形成」 (Coore, Coore, Nagpal, Weiss). プロセッサのローカルクラスターがローカル通信ハブとして機能するリーダーを選出する。
- 「座標形成」 (Nagpal) 複数のシグナル勾配を形成し、それらを用いた三角測量によってグローバル座標を各デバイスにマッピングする。