直列と並列について考えてみた

概念


仕事の仕方には直列と並列があります。人間で例えると、一人で仕事をするのが直列処理、複数人で分担して仕事をするのが並列処理です。一人で仕事をするのは単純ですが、複数人で仕事をするには分担を決めて、各々が担当分の仕事をして、その結果をまとめるといったように直列に比べて複雑になります。

仕事をするスピードには個人差がありますが、いくら仕事が速い人でも一人でできる仕事量には限界があります。また、仕事には分担が簡単なものと難しいものがあり、複数人で分担しやすいポイントを見つけて分担します。例えば、スーパーのレジは複数台あることが多いと思います。レジは多ければそれだけ速く清算できます。一方、同じ商品の仕入れ担当が複数人いるということは少ないのではないかと思います。同じ商品の仕入れ担当が3人いたとすると、2重仕入れしないように声をかけあう必要があるなど、分担が難しいです。人を増やすのであれば、レジ担当のほうが簡単で、増やせばそれだけ清算が速くなります。

このようなことを考えてみなさん仕事をされていると思いますが、コンピュータの世界でも同じことが言えます。ソフトウェアはハードウェアで実行され、最終的には電気的、機械的な物理現象になります。CPU のクロック周波数やストレージのI/O性能には製品によって差がありますが、いくら性能が良いCPUやストレージでも単体で可能な処理スピードには限界があります。いくら技術が進歩しても物理法則に逆らうことはできません。

例えば、はてなダイアリーのようなブログのシステムであれば、ユーザIDの範囲で分割して複数のサーバで処理することができます。ユーザIDがa〜dはサーバ1で、e〜hはサーバ2でという具合に分担することができます。一方、同じデータの更新を並列化するのは難しく、無理に並列化すると、直列処理より遅くなったりします。そのような場合は、直列処理のスピードをあげる方法を考えるほうが有効です。シングルスレッドの処理の性能向上にCPUのクロック周波数を上げるのは有効ですが、コア数が増えても速くなりません。1970年代にIBMで System/360 の設計に関わっていたジーン・アムダールが考えた「アムダールの法則」というのがあります。

IBM360システムの設計者のひとりであるGene Amdahl氏(アムダール)によって1967年に提唱された、並列化によるコンピュータの性能効果について示した法則。
並列化によるコンピュータの処理性能の向上は、並列化できず逐次実行するしかないタスクに制約を受ける。したがって高い並列化率の望める場合は、使用するプロセッサ数を増やし並列処理を行うことで大きな性能効果を得ることができるが、並列化できない部分が大きい場合は、使用するプロセッサ数を増やしても大きな性能の向上は望めないというもの。

404エラー アクセスしようとしたページが見つかりません - WISDOM

というものです。性能向上において、並列化は有効な手段ですが、このアムダールの法則を考えて並列化を行わないと効率的に性能を向上させることはできません。「法則」などと名前がつくと難しそうに思いますが、普段、複数人で何かをするときは誰でも考えていることだと思います。

「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。

Fran Allen氏は、コンパイラプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。

講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。

...

もちろん、これまでも性能向上のために並列化は取り入れられてきました。パイプライン、ブランチ予測といった技術をハードウェアレベルで用いてきました。並列化をチップの内部で行ってきました。しかしそれではもう不十分です。ソフトウェア自身が並列化されなければなりません。

しかし現在のソフトウェアは、ここで必要とされるような並列化を提供していません。性能を向上するにはソフトウェアの並列化に向かわなければなりませんが、それは提供できていない。これが現在のジレンマです。

コンピュータサイエンス史上最大の課題「並列処理による性能向上」~情報処理学会創立50周年記念全国大会の招待講演 - Publickey

この記事を読んでも、現時点ではハードウェアレベルなど低レイヤーでの自動並列化には限界があり、もっと上のレイヤー(インフラやアプリケーションの設計)で並列化を考慮する必要があると思います。

メリット/デメリット

直列処理
  • メリット
    • 仕組みがシンプルなため、作りやすく運用も簡単。
  • デメリット
    • 並列化による性能向上や冗長化のメリットを享受できない。
並列処理
  • メリット
    • 性能向上: 同じ時間で処理できる仕事量が増え性能が向上する
    • 冗長化: 一部が故障しても処理を継続することができる
  • デメリット
    • 分岐点や合流点があるため排他制御などを考慮する必要があり、仕組みが複雑になるため、作るのも運用するのも直列処理に比べると難しい。アーキテクチャをよく考えて作ったり運用したりしないと、トラブルやボトルネックが発生しやすい。

思ったことを徒然と

memcached や Cassandra、Redis などの KVS(Key-Value Store)、HaskellErlangScala などの関数型言語、node.js などの技術が流行している背景には、GooglefacebooktwitterDeNAGREEdwangomixi など大規模Webサービスを提供する企業が増え、膨大なトラフィックやデータを処理する必要性が高まっていたり、CPU のクロック周波数が頭打ちになりメニーコア化にシフトしているなどにより、並列処理への需要が高っているからではないかと思います。

大規模Webサービスを提供するような企業で働くエンジニアには、ハードウェア、ネットワーク、OSとシステムの全体最適化など幅広い分野について深い知識が求められると思います。このようなスキルを持ったエンジニアは Google などの企業が台頭する前から、大規模なインフラを扱うエンタープライズな企業(IBMAT&Tとか?)の中に存在していたと思いますが、そのノウハウが一般に公開されることはなく、また多くのエンジニアにとってそのようなノウハウに対する需要も低かったのではないかと思います。今の時代はこれまで以上にこのような知識に興味を持つエンジニアの数が増え、大規模なシステムのインフラ設計や運用のノウハウがインターネットや勉強会などで共有されるようになっていることは素晴らしいことだと思います。

何も考えずに Exadata のような高性能なインフラに頼るだけで良いこともあると思いますが、そのような場合でもトラブルシューティングやパフォーマンスチューニングにおいてはアーキテクチャの理解が役に立ちます。日々、新しい技術が生まれていますが、全く新しい概念というのは少なく、アーキテクチャや本質を理解していると、新しい技術の本質を見抜いて表面的な宣伝文句に踊らされることなく適切に使うことができると思います。

例えば、KVS と RDBMS は違うものですが、その中で使われているアルゴリズムや OS のシステムコール、ハードウェアは同じだったりします。ハードディスクであればディスクが回転してシークして、セクタ単位でデータを読み書きしていると言う点では同じで、KVS でも RDBMS でもハードディスクを効率的に使うためにランダムアクセスよりシーケンシャルアクセスになるようにアクセスしたり、B-Tree アルゴリズムを使ってアクセスするデータ量を少なくしたり、そもそもメモリ上にキャッシュしてディスクアへのクセスを減らすといったアプローチは同じだと思います。

私がすごいなと思うプログラマコンサルタント、インフラアーキテクト、サポートエンジニア、元々メインフレームアセンブラを書かれていたDB使いの方などの共通点はアーキテクチャを理解されている、もっと抽象的に言うと本質を理解されている点ではないかと思います。

並列処理の具体例

  • 肺や腎臓
  • 複数車線の道路
  • 高速道路の料金所
  • スーパーやコンビニなどのレジ
  • 対称型マルチプロセッシング(SMP)
  • RAID
  • NIC の bonding
  • FCストレージのマルチパス構成
  • Oracle Real Application Clusters
  • Oracle Coherence
  • SQL のパラレル実行
  • MapReduce
  • Hadoop