アモルファス・コンピューティングとは？わかりやすく解説

アモルファスコンピューティングとは、計算能力とメモリが限られた多数の同一の並列プロセッサが局所的に相互作用する系でモデル化されるような計算、およびそのようなシステムを研究する学術分野である。アモルファスコンピューティングという用語は、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) 複数のシグナル勾配を形成し、それらを用いた三角測量によってグローバル座標を各デバイスにマッピングする。

研究室および研究者

Hal Abelson, MIT
Jacob Beal, レイセオンBBNテクノロジーズ (アモルファスコンピューティングのための高等言語)
Daniel Coore, 西インド諸島大学
Nikolaus Correll, コロラド大学 (robotic materials)
Tom Knight, MIT (合成生物学による計算)
Radhika Nagpal, ハーバード大学 (自己組織化システム、座標形成)
Zack Booth Simpson, テキサス大学オースティン校、エリントン研究室 (細菌を用いたエッジ検出)
Gerry Sussman, MIT AI Lab
Ron Weiss, MIT (ルールトリガー、微生物コロニー言語、大腸菌パターン形成)

参考文献

The Amorphous Computing Home Page

MIT AIラボの論文とリンク集
Amorphous Computing (Communications of the ACM, May 2000)

Coore の成長点言語の例と、Weiss のルールトリガー言語から作成されたパターンを示すレビュー記事
"Amorphous computing in the presence of stochastic disturbances"

故障したコンポーネントに対処するアモルファスコンピュータの能力を調査した論文
Amorphous Computing Slides from DARPA talk in 1998

実装のためのアイデアと提案の概要
Amorphous and Cellular Computing PPT from 2002 NASA Lecture

上記とほぼ同じ内容、ppt形式
Infrastructure for Engineered Emergence on Sensor/Actuator Networks, Beal and Bachrach, 2006.

「Proto」と呼ばれるアモルファスコンピューティング用の言語
Self-repairing Topological Patterns Clement, Nagpal.

自己修復・自己維持ラインのアルゴリズム
Robust Methods of Amorphous Synchronization, Joshua Grochow

グローバルな時間同期を誘導する方法
Programmable Self-Assembly: Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics and Associated Slides Nagpal PhD Thesis

折り紙のような折り畳まれた構造の高レベルの記述からローカル相互作用命令をコンパイルする言語
Towards a Programmable Material, Nagpal Associated Slides

上記の論文と同様の概要
Self-Healing Structures in Amorphous Computing Zucker

生物の再生に着想を得たトポロジーの検出と維持の方法
Resilient serial execution on amorphous machines^{[リンク切れ]}, Sutherland Master's Thesis

アモルファスコンピュータ上でシリアルプロセスを実行するための言語
Paradigms for Structure in an Amorphous Computer, 1997 Coore, Nagpal, Weiss

アモルファスコンピュータに階層的秩序を作り出す技術
Organizing a Global Coordinate System from Local Information on an Amorphous Computer, 1999 Nagpal.

勾配形成による座標系の作成技術と精度限界の分析
Amorphous Computing: examples, mathematics and theory, 2013 W Richard Stark.

この論文では、単純なものから複雑なものまで約 20 の例を示し、標準的な数学ツールを使用して定理を証明し、予想される動作を計算し、4 つのプログラミングスタイルを特定して調査し、3 つの計算不可能性の結果を証明し、複雑で動的なインテリジェンスシステムの計算の基礎を概説する。

アモルファス・コンピューティングとは？わかりやすく解説