分散コンピューティング




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


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


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


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




目次






  • 1 構成


  • 2 目標と利点


    • 2.1 オープン性




  • 3 欠点と問題


    • 3.1 技術的問題




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


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


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




  • 5 並行性


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


    • 5.2 マルチコアシステム


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


    • 5.4 分類


    • 5.5 コンピュータクラスター


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




  • 6 言語


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


    • 7.1 主なプロジェクト




  • 8 脚注


  • 9 参考文献


  • 10 関連項目


  • 11 外部リンク





構成


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


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



目標と利点


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


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



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


  • 安価

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




オープン性


分散システムのオープン性とは、各サブシステムが他のシステムとの相互作用について継続的にオープンであることをいう（参考文献参照）。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月終了）




脚注





  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




参考文献




  • 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. 



関連項目




  • Google（検索エンジンのシステムなどは分散コンピューティングを用いている）

  • 分散技法

  • スーパーコンピュータ

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

  • ユビキタスコンピューティング

  • Berkeley Open Infrastructure for Network Computing

  • 多層アーキテクチャ

  • 分散コンピューティングの落とし穴

  • Team2ch

  • プレイステーション3

  • 分散ネットワーク

  • センサネットワーク



外部リンク



  • 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での分散コンピューティング















































  • 表

  • 話

  • 編

  • 歴


並列計算
総論


  • クラウドコンピューティング

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

  • 高性能計算

  • コンピュータ・クラスター

  • 分散コンピューティング
並列レベル

  • タスク

  • データ

  • ビット

  • 命令

    		•
    スレッド

  • スーパースレッディング（英語版）

  • ハイパースレッディング

    		•
    理論

  • アムダールの法則

  • グスタフソンの法則

  • コスト効率性（英語版）

  • Karp-Flatt metric（英語版）

  • Parallel slowdown（英語版）

  • Speedup（英語版）

    		•
    要素

  • スレッド

  • ファイバー

  • プロセス

  • PRAM

  • Instruction window（英語版）

    		•
    調整

  • キャッシュコヒーレンシ

  • 同期

  • バリア

  • マルチスレッディング

  • マルチプロセッシング

  • メモリコヒーレンス

  • Cache invalidation（英語版）

  • Application checkpointing（英語版）

    		•
    プログラミング

  • スレッド (コンピュータ)


  • 並列プログラミングモデル

    • Implicit parallelism（英語版）

    • Explicit parallelism（英語版）

    • 並行性




  • フリンの分類

    • SISD

    • SIMD

    • MISD


    • MIMD
      • SPMD（英語版）




  • Lock-freeとWait-freeアルゴリズム

    		•
    ハードウェア

  • スーパーコンピュータ

  • スーパースカラー

  • ベクトル計算機

  • マルチプロセッシング

    • 対称型

    • 非対称型

    • マルチコア



  • メモリ

    • NUMA

    • en:COMA

    • en:分散型

    • 共有型

    • 分散共有型



  • SMT

  • MPP

  • Beowulf

    		•
    API

  • Ateji PX（英語版）

  • Boostスレッド

  • C++ AMP

  • Charm++（英語版）

  • Cilk（英語版）

  • Coarray Fortran（英語版）

  • CUDA

  • Dryad（英語版）

  • Global Arrays（英語版）

  • Intel Cilk Plus（英語版）

  • Intel Threading Building Blocks

  • MPI

  • OpenACC（英語版）

  • OpenCL

  • OpenHMPP（英語版）

  • OpenMP

  • PVM

  • POSIXスレッド

  • UPC

    		•
    問題

  • en:Embarrassingly parallel

  • en:Grand Challenge

  • en:Software lockout

    		•

  • 並行計算

  • カテゴリ:並行計算

  • カテゴリ:並列コンピューティング




    • -

    Popular posts from this blog

    CARDNET

    Image
    CARDNET は日本カードネットワークが運営するクレジット決済ネットワーク。日本カードネットワークの略称としてもCARDNETが使用されている。 事件・事故 2017年4月15日午前11時8分からクレジットカードの決済がしづらくなる障害が発生した。障害は同日午後5時18分に復旧した。原因は、複数あるCARDNETセンターの拠点のうち1つで、2重化してあるL3スイッチの片方が故障し、1系統にトラフィックが集中したことによる輻輳が発生したため。対処としては、故障したL3スイッチ交換とシステム再起動が行われた [1] 。 出典 ^ 金子寛人 ( 2017年4月17日 ). “CARDNETのクレジット決済に6時間強障害、原因はL3スイッチ故障”. 日経コンピュータ. 2018年10月18日 閲覧。 この項目は、コンピュータに関連した 書きかけの項目 です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 この項目は、経済に関連した 書きかけの項目 です。この項目を加筆・訂正などしてくださる協力者を求めています（ポータル 経済学、プロジェクト 経済）。 This page is only for reference, If you need detailed information, please check here
    Read more

    Boot-repair Failure: Unable to locate package grub-common:i386

    Image
    0 I am on a system dual-booting Windows and Debian (usually using the latter), and a recent Windows update appears to have wreaked havoc on the Debian boot system. I managed to boot Windows again, but not Linux. Following online suggestions, I created a Live USB of Ubuntu, and booted from that. Then I have installed and run the boot-repair utility. The utility instructs me to type several lines including sudo chroot "/mnt/boot-sav/sda6" apt-get purge -y grub*-common grub-common:i386 To which I receive the error E: Unable to locate package grub-common:i386 I am given to understand the issue may have to do with having UEFI vs BIOS (I believe I have UEFI), but do not understand this well. In any case I have subsequently run the boot-repair BootInfo Summary utility which created the following file h...
    Read more

    濃尾地震

    Image
    濃尾地震 『岐阜市街大地震之図』 歌川国利画 本震 発生日 1891年（明治24年）10月28日 発生時刻 6時38分50秒（JST） 震央 日本 岐阜県本巣郡西根尾村（現・本巣市） 北緯35度35分 東経136度20分（ 地図 ） 規模    マグニチュード（M）8.0 最大震度    震度7： 注1 福井県今立郡鯖江町、愛知県葉栗郡大田島村、東春日井郡勝川村 地震の種類 直下型地震 被害 死傷者数 死者7,273人、負傷者17,175人 注1：当時の震度階級では「激烈」 プロジェクト:地球科学 プロジェクト:災害 テンプレートを表示 濃尾地震 （のうびじしん）は、1891年（明治24年）10月28日に濃尾地方で発生した、日本史上最大の内陸地殻内地震。「 美濃・尾張地震 （みの・おわりじしん）」とも呼ばれている。辛卯の年に発生したことから 辛卯震災 と呼んでいる報告書もある。 目次 1 概要 1.1 震源断層 2 被害 3 各地の震度 4 前兆現象 5 報道 6 学術的な意義 7 地震防災 8 脚注 9 関連項目 10 外部リンク 概要 濃尾地震発生当時の根尾谷断層 濃尾地震を引き起こした根尾谷断層 写真中央を斜めに走る段差が根尾谷断層 濃尾地震は、1891年10月28日6時38分50秒に発生した。震源は、岐阜県本巣郡西根尾村（現・本巣市）、北緯35度35分、東経136度20分付近。河角廣 (1951) は岐阜市付近（北緯35.6度、東経136.6度）に震央を仮定し規模 M K = 7.0 を与え [1] 、マグニチュードは M = 8.4 に換算されているが、明治・大正期の地震については0.5程度大きく見積もられているとされる [2] 。また、震央距離と震度との関係など当時のデータから後にM8.0 [3] とも推定される。アメリカ地質調査所 (USGS) でも8.0としている [4] 。「根尾谷断層帯」が活動した典型的な内陸地殻内地震（いわゆる直下型地震）であり、これは記録が残っている日本の内陸...
    Read more