Yrurtj

分散コンピューティング（ぶんさんコンピューティング、英: Distributed computing）とは、プログラムの個々の部分が同時並行的に複数のコンピュータ上で実行され、各々がネットワークを介して互いに通信を行いながら全体として処理が進行する計算手法のことである。複雑な計算などをネットワークを介して複数のコンピュータを利用して行うことで、一台のコンピュータで計算するよりスループットを上げようとする取り組み、またはそれを実現する為の仕組みである。分散処理（ぶんさんしょり）ともいう。並列コンピューティングの一形態に分類されるが、一般に並列コンピューティングと言えば、同時並行に実行する主体は同じコンピュータシステム内のCPU群である。ただし、どちらもプログラムの分割（同時に実行できる部分にプログラムを分けること）が必須である。分散コンピューティングではさらに、それぞれの部分が異なる環境でも動作できるようにしなければならない^{[要検証 – ノート]}。例えば、2台の異なるハードウェアを使ったコンピュータで、それぞれ異なるファイルシステム構成であっても動作するよう配慮する必要がある。

問題を複数の部分問題に分けて各コンピュータに実行させるのが基本であり、素数探索や数多く試してみる以外に解決できない問題の対処として用いられているものが多い。分散コンピューティングの例としてBOINCがある。これは、大きな問題を多数の小さな問題に分割し、多数のコンピュータに分配するフレームワークである。その後、それぞれの結果を集めて大きな解を得る。一般的に処理を分散すると一台のコンピュータで計算する場合と比べ、問題データの分配、収集、集計するためのネットワークの負荷が増加し、問題解決の為のボトルネックとなるため、部分問題間の依存関係を減らすことが重要な課題となる。

分散コンピューティングは、コンピュータ同士をネットワーク接続し、効率的に通信できるよう努力した結果として自然に生まれた。しかし、分散コンピューティングはコンピュータネットワークと同義ではない。単にコンピュータネットワークと言った場合、複数のコンピュータが互いにやり取りするが、単一のプログラムの処理を共有することはない。World Wide Web はコンピュータネットワークの例であるが、分散コンピューティングの例ではない。

分散処理を構築するための様々な技術や標準が存在し、一部はその目的に特化して設計されている。例えば、遠隔手続き呼出し (RPC)、Java Remote Method Invocation (Java RMI)、.NET Remoting などがある。

構成

コンピュータ同士の相互のやり取りを組織して系統立てることが重要である。様々なコンピュータを利用可能とするには、通信プロトコルや通信経路に特定のマシンが認識できない情報が含まれていてはならない。メッセージが正しく配布されるよう特に注意を払う必要があり、不正なメッセージがあるとシステムやネットワークが動作不能となる危険性があるため、それを拒絶しなければならない。

もう1つの重要な要因は、ソフトウェアをコンピュータからコンピュータへ送信する機能であり、それによって送られたコンピュータが既存のネットワークとやり取りできるようになる。アーキテクチャが異なっているとこれができない場合があり、クロスコンパイラなどを使った移植が必要になる。

目標と利点

分散コンピューティング・システムには様々な形態がある。分散コンピューティングの主な目標は、透過的でオープンでスケーラブルな方法でユーザー群とリソース群を結びつけることである。理想的には、スタンドアローンシステム群の単なる組合せよりも、よりフォールトトレラントでより強力なシステムとなることが期待される。

次のような利点があるとされる。

高信頼
- 故障部分以外は稼動可能

安価
- グロッシュの法則（コンピュータの能力 ∝ コスト²）が破れ、ハードウェアとソフトウェアのコストが逆転。

オープン性

分散システムのオープン性とは、各サブシステムが他のシステムとの相互作用について継続的にオープンであることをいう（参考文献参照）。Webサービスプロトコルは、分散システムを拡張・拡大することを可能にする標準である。一般に、拡張性のあるオープンシステムは、自己完結型の完全にクローズなシステムよりも優れている。

オープンな分散システムは以下のような特性を持つ。

単調性: オープンシステム上で何かが公開されれば、それを取り消すことはできない。
複数性: オープンな分散システムの個々のサブシステムは、異質で重複し、場合によっては競合するような情報を含む。中心となる調停機能はオープンな分散システムには存在しない。
無制限の非決定性: オープンな分散システムでは、個々のサブシステムは非同期的に立ち上がったりダウンしたりし、サブシステム間の通信リンクも非同期に接続されたり切断されたりする。従って、ある処理が完了する時間を予測することはできない。

欠点と問題

「分散コンピューティングの落とし穴」も参照

不特定多数、または特定多数のコンピューターに処理させるためにセキュリティ面で脆弱になりやすい

上記されているように問題データの分配、収集、集計するためのネットワークの負荷が増加する

一般参加者を募る場合、志願者が少ないとその分処理も遅れる

技術的問題

計画に不備があると、分散システムは全体の計算の信頼性が低下し、ノードのダウンによって他のノードも動作不能に陥る可能性がある。レスリー・ランポートは、「分散システムは、そんな障害があるとは思ってもみなかった障害によって利用不能になるシステムである」と述べている^[1]。

分散システムにおけるトラブルシューティングや診断はますます困難になりつつある。問題の原因を突き止めようとすれば、遠隔ノードへの接続が必要であり、ノード間の通信内容を調べる必要がある。

分散環境に適さない計算の種類も多い。特に通信量が多くなるものや同期が必要なものは適さない。必要な帯域幅があまりに大きくレイテンシが少ないほどよいという場合は、分散コンピューティングは不適切であり、分散でない環境の方が性能がよいと予想される。

設計思想（アーキテクチャ）

分散コンピューティングでの設計思想（アーキテクチャ）

分散コンピューティングでは、様々なハードウェアおよびソフトウェアの設計思想（アーキテクチャ）が使われる。大きく分けると低レベルと高レベルに分けられる。

低レベルでの設計思想（アーキテクチャ）: 複数のCPUを何らかのネットワークで相互接続する必要がある（そのネットワークは、基板上にプリントされた回路かもしれないし、疎結合された機器とケーブルの集合体かもしれない）。
高レベルでの設計思想（アーキテクチャ）: 何らかの通信システムで個々のコンピュータ上で動作するプロセスを相互接続しなければならない。

分散プログラミングでの設計思想（アーキテクチャ）

分散プログラミングは、一般に以下の基本アーキテクチャのいずれかに分類される。

クライアントサーバ: クライアントがサーバに対してデータを要求し、それをフォーマットしてユーザー向けに表示する。クライアントへの入力がサーバのデータを変更するものである場合、サーバにそれが送られる。
3層アーキテクチャ: 3層システムは、クライアントとサーバの間に中間層を置く形態で、それによってクライアントの処理が軽減される。そのためアプリケーション配布が単純化される。多くのウェブアプリケーションは3層である。
N層アーキテクチャ: N層とは、ウェブアプリケーションが要求をさらにバックエンドにあるエンタープライズサービスに転送するものを指す。アプリケーションサーバを使ったアプリケーションはここに分類される。
密結合（クラスター）: 一般に、高度に集積されたマシン群で同じプロセスを並行して実行し、タスクを分割して個々のプロセッサに実行させる。計算結果は後に集約される。
Peer-to-peer: ネットワークにサービスを提供するマシンやリソースを管理する特別なマシンが存在しないアーキテクチャ。その代わりに全ての責任は参加している全マシンにある。各マシンはサーバとしてもクライアントとしても機能する。
タプルスペース・ベース: 単一のアドレス空間を共有しているかのように仮想化するアーキテクチャを指す。データは必要に応じて透過的にレプリケートされる。時間的/空間的結合度が弱められる。

分散コンピューティング・アーキテクチャの別の観点として、並行プロセス間の通信と作業配布の方法がある。プロセスは各種メッセージパッシングプロトコルを使って互いに直接通信でき、一般にマスタースレーブ型の関係にある。それとは別にデータベースを中心とするアーキテクチャもあり、直接のプロセス間通信をせず、データベースを共有することで分散処理を実現する^[2]。

並行性

分散コンピューティングには、ある種の並行性が実装される。並行コンピューティングとも密接な関係があり、しばしば同義に扱われる^[3]。

マルチプロセッサシステム

マルチプロセッサシステムは、複数のCPUを持つ単一のコンピュータである。オペレーティングシステムがその利点を生かすよう構築されていれば、異なるプロセス（あるいは同一プロセスの異なるスレッド）を異なるCPU上で同時に実行できる。

マルチコアシステム

インテルのCPUは、Pentium 4の世代の後期にハイパースレッディング・テクノロジーと呼ばれる技術を採用した。これは、複数のスレッドを同じCPU上で同時に実行できる技術である。その後、マルチコア技術で複数のCPUコアを1つのパッケージにするようになり、サン・マイクロシステムズは UltraSPARC T1 で、AMDは Athlon 64 X2/FX/Opteron で、インテルは Pentium D/Core/Core2/Xeonで実装している。これにより、複数のスレッドを同時実行できるようになり、同時実行可能スレッド数は増えていく傾向にある。

マルチコンピュータシステム

マルチコンピュータという用語は、疎結合型のNUMAマシンや密結合型のコンピュータ・クラスターを指す。マルチコンピュータは、電力消費を抑えつつ限られたスペースで強力な計算能力を持つシステムを構築する際に採用される。

分類

分散システムはフリンの分類によって次のように分類される。

SISD（Single Instruction, Single Data）

SIMD（Single Instruction, Multiple Data）

MISD（Multiple Instruction, Single Data）

MIMD（Multiple Instruction, Multiple Data）

コンピュータクラスター

詳細は「コンピュータ・クラスター」を参照

クラスターは複数の独立したマシンで構成され、高速なネットワークで相互接続されたマシンが並列に動作する。分散コンピューティングとコンピュータ・クラスターの違いは、分散コンピューティングで使われる個々のマシンが必ずしも同一グループのタスクを実行するためだけにあるわけではないのに対して、クラスターでは各マシンがより密に結合されている。分散コンピューティングは、クラスターよりも地理的に広範囲にあるマシンを含むことが多い。

グリッドコンピューティング

詳細は「グリッド・コンピューティング」を参照

グリッドも多数のコンピュータから構成され、ネットワーク（通常インターネット）で疎結合され、大きな計算問題を解くのに使われる。パブリック・グリッドでは、世界中の数千ものコンピュータの空き時間を利用する。グリッド・コンピューティングは、高価なスーパーコンピュータが必要になるような計算や、従来は不可能と思われていた計算を可能とした。

言語

システム内のあらゆるハードウェアにアクセスできるプログラミング言語は、時間さえあれば分散プログラミングに使える。遠隔手続き呼出し (RPC) は、オペレーティングシステムのコマンドをネットワーク経由で分散配布する。オブジェクト指向設計をネットワークにマッピングしようとする試みとして、CORBA、マイクロソフトのDCOM、Java RMI などがある。疎結合システムでは、一般に人間にも読める中間文書を使って通信を行う（例えば、XML、HTML、SGML、X.500、EDI）。

分散プログラミング向けに機能が強化されている言語としては、以下のものがある。

Ada ^[4]

Alef

E言語

Erlang

Limbo

KL1

Oz

Strand

ZPL

Orca

分散コンピューティングプロジェクト

一般に参加者を募っている分散コンピューティングプロジェクトが多くあり、既に目的とした問題解決などの成果を出したプロジェクトもある。多くのプロジェクトでは

計算する元データの分配、収集を行うサーバを用意

実際に計算を行う複数のコンピュータ用のクライアントソフトを配布

集計結果を Web などで公開

などの手法を用いて、分散コンピューティングを実現、参加者の募集等をおこなっている。これらのプロジェクトでは、一般ユーザの参加により、コストの削減も目指している。これらのプロジェクト特有の課題として、クライアントなどを改ざんして、意図的に誤った計算結果をサーバに送る危険性が挙げられるため、通信方式を非公開にする、同じ計算を複数のクライアントに行わせる、などの対策が行われている。

通常これらのプロジェクトでは個人の所有するPCによる計算結果を集計し、プロジェクトを進行している。その為、参加者数がプロジェクトの進行速度に大きく影響する。集計ではプロジェクトの進行状況とともに、参加者個人あるいは参加者がまとまったチームでの集計結果を表示するなどしているプロジェクトが多い。これが参加者同士の交流につながったり、参加者の競争意識を煽り、参加者の増加につながっているプロジェクトも存在する。

主なプロジェクト

稼働中（アルファベット順）
- BOINC - 分散コンピューティングの管理ソフト。さまざまなプロジェクトがこのソフトを利用して分散コンピューティングを行っている。
- distributed.net - 全探索による暗号解読によるプライバシー保護の訴え、全探索による数学的難問の証明など。
- Einstein@Home - 一般相対性理論から予言される重力波を、観測データから検出する事を目指す。
- Electric Sheep - フラクタルの動画を生成するフラクタルアート関連のプロジェクト。
- Folding@Home - 分子動力学法によるタンパク質の折り畳みの予測（タンパク質構造予測）。
- GIMPS - メルセンヌ素数の発見。
- M4 Project - 第二次世界大戦中に傍受されたナチス・ドイツの未解読暗号の解読を目指す。
- SETI@home - 宇宙生物学。地球外からくる信号から非自然信号を抽出し、地球外生命体を探索。
- World Community Grid - 主に医療系（エイズやがん、筋ジストロフィー）に関する新薬開発の為の分子解析、タンパク質解析に関するプロジェクト。上記BOINCを使って解析も出来る。
- グーグル八分発見システム「∞Eyes」 - 検索エンジンでの検索結果を解析し、グーグル八分を発見しようというプロジェクト。

稼動終了（アルファベット順）
- cell computing - 遺伝子の周期性の検索による遺伝病の検知を目指す。NTTデータが提供。（2008年3月終了）
- United Devices Cancer Research Project - 癌治療薬開発の為の分子解析。（2007年4月終了）

脚注

^ Leslie Lamport. “Subject: distribution (Email message sent to a DEC SRC bulletin board at 12:23:29 PDT on 28 May 87)”. 2007年4月28日閲覧。

^ A database-centric virtual chemistry system, J Chem Inf Model. 2006 May-Jun;46(3):1034-9

^ CS236370 Concurrent and Distributed Programming 2002

^ Ada Reference Manual, ISO/IEC 8652:2005(E) Ed. 3, Annex E Distributed Systems

参考文献

Attiya, Hagit and Welch, Jennifer (2004). Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley-Interscience. ISBN 0471453242.

Lynch, Nancy A (1997). Distributed Algorithms. Morgan Kaufmann. ISBN 1558603484.

Tel, Gerard (1994). Introduction to Distributed Algorithms. Cambridge University Press.

Davies, Antony (2004年6月). “Computational Intermediation and the Evolution of Computation as a Commodity”. Applied Economics. http://www.business.duq.edu/faculty/davies/research/EconomicsOfComputation.pdf.

Kornfeld, William; Hewitt, Carl (1981年1月). “The Scientific Community Metaphor”. MIT AI (Memo 641). https://dspace.mit.edu/handle/1721.1/5693.

Hewitt, Carl; de Jong, Peter (August 1983). “Analyzing the Roles of Descriptions and Actions in Open Systems”. Proceedings of the National Conference on Artificial Intelligence

Hewitt, Carl (1985年4月). “The Challenge of Open Systems”. Byte Magazine.

Hewitt, Carl (1999年10月23日–1999年10月27日). “Towards Open Information Systems Semantics”. Proceedings of 10th International Workshop on Distributed Artificial Intelligence. Bandera, Texas

Hewitt, Carl (1991年1月). “Open Information Systems Semantics”. Journal of Artificial Intelligence.

Nadiminti, Dias de Assunção, Buyya (2006年9月). “Distributed Systems and Recent Innovations: Challenges and Benefits”. InfoNet Magazine, Volume 16, Issue 3, Melbourne, Australia. http://www.gridbus.org/~raj/papers/InfoNet-Article06.pdf.

外部リンク

A primer on distributed computing

Distributed computing - DMOZ

Distributed computing journals - DMOZ

Distributed computing conferences - DMOZ

MIT's Open Course - Distributed Algorithms

Melbourne's Masters Course in Distributed Computing

各種分散コンピューティングプロジェクトの紹介

BOINCでの分散コンピューティング

[1] Leslie Lamport. “Subject: distribution (Email message sent to a DEC SRC bulletin board at 12:23:29 PDT on 28 May 87)”. 2007年4月28日閲覧。

[2] A database-centric virtual chemistry system, J Chem Inf Model. 2006 May-Jun;46(3):1034-9

[3] CS236370 Concurrent and Distributed Programming 2002

[4] Ada Reference Manual, ISO/IEC 8652:2005(E) Ed. 3, Annex E Distributed Systems

搜尋此網誌