アルゴリズムレベルの並列分散処理の設計

はじめに

私は約3年間並列分散処理を専攻してきました。データマイニング系の研究室であったため、周囲に同様の分野を専攻する人がおらず、基礎を確立させるには辛いものがありました。並列分散処理に対する自分の知見を周りと共有したことがあまりないので、本当に自分の持つ知識は正しいのか不安です。ここで、3年間の知識を簡単に整理することにしますが、話の内容は多岐にわたっているので文章にあまりまとまりがないかもしれません。主にアルゴリズムの並列化・並列分散化についてまとめました。なお、私は並列分散処理基盤に関して Hadoop と Spark しか触れておらず、主に OpenMP のような低層の話はよく理解していません。

並列処理と並列分散処理の基礎

言葉の定義

まず並列処理とは、1台の計算機が持つ複数のコアを用いて処理を並列に実行すること。分散処理とは、複数台のサーバーを用いて処理を実行すること。並列分散処理はその両方を兼ね備えた処理のことを指すとする。Intelなどのハイパースレッディング・テクノロジーを搭載している場合は、一つのコアを複数のコアと認識できるため、並列に処理できる数を増やせる。ただし、その性能は複数コア分にはならないようなので、厳密な扱いには注意が必要。

並列化と分散化

並列化と分散化は似たようなところはあるかもしれません。直列処理から並列処理への移行は、一つのコアで処理させていたものを複数のコアで処理させる、といったように概念の変化があります。一方で、直列処理もしくは並列処理を分散化させるには、一つの計算機で処理したものを複数の計算機で処理する、といったように概念の変化があります。まず分散処理は一つのタスクを複数のタスクに分割して問題を解くため、分散処理を取り組む前に並列処理を取り組む必要があるでしょう。ただ、並列処理はコア単位、分散処理は計算機単位の話になるため、二つの特性は大きく異なります。

並列処理の背景

並列処理は複数のコアがあって、初めて効率化ができます。現在は、一般のユーザーが8コアのノートPCを使用する時代ですが、このようなマルチコアはどういうときに有効に働くのだろう。例えば、二つのアプリケーションを起動していたならば、コア1でアプリケーション X を実行し、コア2でアプリケーション Y を実行できます。このとき、並列の粒度はアプリケーション単位と言えるでしょう。ソフトウェアエンジニアは並列化という概念を全く知らずにプログラムを実装したとしても、ユーザーはアプリケーションを複数立ち上げることはしばしばあるので、その恩恵を大いに受けるでしょう。

直列実装の効率性の低さ

初学者が初めて作成するようなライブラリを使わないC言語やJavaのプログラムは、シングルスレッドで動作するプログラムです。例えば、8コア搭載のPCでシングルスレッドのプログラムを動作させる場合には、最大12.5%の性能しか得られないでしょう。まだプログラムの計算量が少ないから気にすることはありません。ただし、問題はとんでもなく重い処理を一つのプログラムかつシングルスレッドで実行している場合です。プログラムの実行から出力を得られるまで数分から数時間かかるようなプログラムをただ待つのは疲れるでしょう。何のライブラリも使用せずに、並列化を考慮しない純粋な実装をしたときには、間違いなくシングルスレッドで動作するプログラムのはずです。並列化を検討しないと、手元にある高い性能を持ったマシンが、マルチコアの恩恵を一切受けることなくのんびりと処理をし続ける羽目になります。現代のコンピュータアーキテクチャーに対して、直列実装は適さないでしょう。

並列に詳しくないとマルチコアの恩恵を受けられないのか

実はそんなこともないようです。プログラムの実装に使用するライブラリが並列処理をサポートしているかもしれません。もしパフォーマンスを改善したいならば、どんなライブラリが並列処理をしているのかは調べるとよいでしょう。使用するライブラリによっては極端な実行時間の差が出るかもしれない。特に低いレイヤーで実装をする人は気をつけたほうがよいのかもしれない。

並列分散化の実行容易性

現在、並列分散処理はライブラリを用いれば簡単に実行できます。これは、Apache Spark のGithubの例に掲載されているPythonのコードを少しだけ変化させたものです。

sc.parallelize(range(1000),5).count()

このコードの意味は、1から1000までの離散値集合を5つのデータに分割し、個々のプロセッサでそのデータを数え上げた後に集約をします。並列分散処理を実行するための基盤があれば、細かい並列分散処理はバックエンドで実行してくれるので、ユーザー側の実装は非常に簡単になります。

じゃあ並列アルゴリズムで問題を解こう

全てのアルゴリズムが並列化できるわけではありません。並列化するにはまず問題を解く計算をどのように分割するのかを考えなければいけません。

並列化可能な問題とは

並列計算の粒度を決めるということです。並列処理の入門がワードカウントです。並列分散処理のフレームワークであるMapReduceなどでも問題の解き方としてよく挙げられる例です。並列計算の粒度を単語とし、それを幾つかのプロセッサーに振り分ける。単語の頻度テーブルを各プロセッサーで作成し、最後にそのテーブルを合成する。このワードカウントの問題を一般化すると、「データをいくつかのチャンクに分割し、そのチャンクごとに問題を解く順番が関係性がないという条件のもとで、非同期的に各プロセッサで処理実行し、その計算結果を集約できる」ということになります。このように問題を定式化できないときに、並列化はできません。

並列化不可能な問題とは

前の計算結果を利用して次の計算をしなければならないような、順次的に結果を更新しなければいけないタイプの問題は並列化不可能です。この場合、f(t)を計算するためにtを必要とし、それが繰り返しで表現されています。

int t = 0;
for(i = 0; i < 10000; i++){
 t += f(t);
}

この例はこれ以上考えようがないように思います。ただし、問題を並列化で解く時に考えるのは、どの部分を並列処理の単位とするかです。異なる部分を対象とすることで並列化できるかもしれません。なので、アルゴリズムの根本を考え直すと、並列化へ持ち込むことも可能な場合があります。

並列分散化を考える前に

素直に問題を解いて処理が重たすぎると感じた場合、計算量が中程度でありその計算を用いて大量のデータを処理しなくてはならない場合、もしくは計算量が多いが有限時間内に計算を解くことができると理解している場合に、初めて並列分散化を検討するべきでしょう。特に問題となっていないのに、むやみに並列分散化から検討するのはよくないと感じます。もしかしたら、純粋に並列化をするだけで問題を解ける可能性があるからです。並列分散化すると早くなるというモチベーションで挑むと厄介なことになります。

並列分散処理で考えるべきこと

アルゴリズムが正しい設計なのかをまず確認するべきです。設計が正しくないのならば、複数の計算機を用いて並列分散処理を実行させることは資源の無駄遣いとなってしまいます。

並列化と分散化の困難性

並列化の問題に限定して考えると、時間計算量や空間計算量などを事前に見積もり、どこがボトルネックになりそうかを判断する知識、直列アルゴリズムを並列アルゴリズムに落とし込むための手法の考案、それを解くためにどういった性能を持つハードウェアを用意するべきなのか、対費用効果で良い結果を得ることができるのか。分散化の観点ではもっと難しくなります。ネットワーク周辺やセキュリティの問題、複数の計算機での効率の良いデータの持ち方、デバッグの考え方といったように、単体の計算機での処理が複数台になるときに非常に大きなパラダイムの変化があります。

考えることが多すぎるが...

CやC++などの低層レベルでプログラムを実装しようとなると、それ以上の困難性が付きまといます。ただ、ここまで検討するのが予測できなくても、ビッグデータというバズワードで流行した並列分散処理の分野では、おおよその知見と事例が積み重ねられてきました。どういう場合に並列分散化を検討するべきなのかは、実例をみることがよいでしょう。技術的な観点からはSpark、AWS Elastic MapReduceやCloudera Manegerといった並列分散処理機構を駆使し、効率よく問題を解くことで、そのユーザーが向き合うべき問題の本質により時間をかけることが可能になってきています。

並列分散化だけがパフォーマンスを改善するわけではない

並列分散化だけがパフォーマンスを改善させるわけではありません。

設計を考える順番

直列化、並列化、並列分散化の順番で設計を考えるべきだと思っています。この順番で規模が大きくなり、それが大きくなるほど、あらゆる側面を考慮して設計をしなければならないからです。

  1. 直列実装：並列化困難（並列処理の粒度が細かすぎる）もしくは、小規模の時間計算量と空間計算量を要する場合
  2. 並列実装：並列化が可能（並列処理の粒度を大きくできる）かつ、直列実装で処理困難である場合
  3. 並列分散実装：並列実装でも処理しきれないレベルの時間計算量と空間計算量を要する場合

ちなみに時間計算量が指数的に増加する場合、並列分散では線形にしか対応できないので、データ量が十分に大きい場合対応不可能です。なので、計算量が指数的に増加する場合、データ量が小さいという条件が必要になるでしょう。

直列化だけで改善することを試みる

実行速度を改善したいならば、より高速に動作するCやC++といったプログラミング言語の選択を検討するのもよいでしょう。実装言語によっても実行時間に100倍スケールの差が出ることもあるからです。感覚的に低層のプログラミング言語は並列化の実装が困難になります。開発効率という観点を評価しなければならず、実装言語を変更できないのであれば、並列化を検討してみましょう。

並列化しても高速化されるとは限らない

アルゴリズムを並列化すると、処理時間がコア数に反比例するというわけではない。アムダールの法則というものがある。99%の並列化であっても、プロセッサ数が99の場合、残りの 50%の性能向上を無駄にします。多くのプロセッサを使用する場合は、基本的には全てのアルゴリズムの並列化を問われます。並列化しても使用したプロセッサ数だけの高速化は見込めないことはまず当然の話になってきます。

まとめ

アルゴリズムの並列分散処理をする場合には、山ほど考えるべきことがあります。並列化を検討してもなお処理が終わらないといった問題に直面した時に、はじめて並列分散処理で実装することを考えるべきでしょう。まだ語りきれない部分も多くありますが、一旦締めとします。