Erlangを使った並列処理プログラムの作成

マルチコアCPUを最大限活用する方法

　Erlangは並列処理向けの言語であり、現在そして将来のマルチコアCPUの能力を最大限に活用する並列処理プログラムの作成に適しています。この記事では、Erlangを使って現在そして将来のマルチコアCPUを最大限活用する方法について説明します。

はじめに

　CPUメーカーは、発熱の問題上、クロックレートが4.0GHzを超えるCPUを何年も実質的に製造できずにいます。シングルコアプロセッサの速度にこうした限界がある以上、プログラムの実行速度を上げるには、プログラムを複数のプロセッサで実行するしかありません。そこで、CPUメーカー各社は複数のコアを持つプロセッサ（マルチプロセッサCPU）を製造し始めました。近い将来には、100基以上のコアを持つプロセッサも登場することでしょう。このような新しいプロセッサの性能を最大限に活用するために、ソフトウェア開発者は並列処理プログラムを作成することが求められます。ハーブ・サッター氏がムーアの法則について述べたとおり、「The Free Lunch Is Over（タダ飯は終わった）」のです。とはいえ、並列処理プログラムの作成は厄介で、移行は容易ではありません。

　過去30年、並列処理の主要フレームワークは、シングルプロセス、シングルスレッド、またはシングルプログラムが、共有メモリ領域の読み書きおよびロックとセマフォによって互いに通信するものでした。マルチプロセッサCPUでは、個々のコアが主に非同期メッセージを送信することによって相互に通信します。このフレームワークでは、共通リソースが同時に使用されたり、セマフォによってデッドロックなどの副作用が生じたりしないよう、相互排他的なアルゴリズムに十分に注意する必要があります。

　この記事では、並列処理プログラムの作成に適した関数型言語Erlangを紹介し、Erlangを使って現在そして将来のマルチコアCPUを最大限活用する方法について説明します。

Erlangとは

　1986年にEricsson研究所で開発されて以来、Erlang（デンマークの数学者Agner Krarup Erlangの名前から命名）は電気通信業界で多く使われています。しかしながら、Erlangは汎用的な関数型プログラミング言語であり、宣言型言語のなかでも制約的ではない広範な分類に属しています。Erlangの重要な特徴の1つは、アクターモデルに基づいて並列処理を実装していることです。アクターモデルとは、「すべてのものはアクターである」とする数学的スキーマです（オブジェクト指向が「すべてのものはオブジェクトである」とするのと似ています）。アクターはメッセージの送受信を行い、それに応じて他のアクターとして動作したり他のアクターを作成したりするので、アクターモデルは本質的に並列的です。これに対し、オブジェクト指向パラダイムは実質的にシーケンシャルです。

　Erlangソフトウェアの並列処理パラダイムにはステート（状態）がありません。変数には1回しか値を代入できず、再帰によって反復処理を実行する必要があります。ステートがないのでメモリの保護が不要になり、副作用もプロセス間で共有するデータの量も抑えられます。

　Erlangの関数は数学の関数と似ています。呼び出しのコンテキストに関係なく、入力が同じなら結果も同じになります。Erlangの関数では各パラメータを値で渡すので、参照できるのはすべて値です。このような特徴を参照透過性と呼びます。

　変数の代入は厳密に制限されますが、Erlangでこの制約を部分的に補っているのが、パターンマッチングという強力なメカニズムです。この機能は、人間が現実を解釈するときに、現実の対象と概念的スキーマの類似点を頭の中で結び付ける行為と似ています。

Erlangを使った算術演算分割

　整数論の基礎計算には、並列処理を使うと効果的なものが多数あります。例えば、ある数の階乗の計算と乗法の結合法則について考えてみましょう。nの階乗を以下の[1]のように表すとき、

[1]    n! = 1 * 2 * 3 *...* n

　qを以下の整数とすると、

q < n
t = n/q

　[1]は次のように記述できます。

n! = a * b * c * ...* j

　ここで、a、b、c、jはそれぞれ次のように記述できます。

a = 1 * 2 * 3 *...* q
b = [(q+1) * (q+2) * ... * 2q]
c = [(2q+1) * (2q+2) * ... * 3q]
...
j = [((t-1)q+1) * ((t-1)q+2) * ... * tq]

　n/qに剰余がある場合は、次のように記述できます。

n! = a * b * c * ...* j * k

　このとき、kは次のようになります。

k = [(tq + 1) * (tq + 2) * ... * n]

　つまり、数の区間全体をt+1個の小さい区間に分割して部分積を計算し、それらを再び乗算すると、最終的な結果を得られます。

　a、b、...、kをマルチプロセッサマシンで同時に計算し、それらの結果を乗算すれば、総所要時間を短縮できるのでは、と筆者は考えました。この問題を解決しようと、小さなErlangコードを書いてみました。このコードは、階乗の関数として実用に耐えるものではないものの、Erlangの構文とErlangの並列処理能力を知る手がかりにはなります（図1を参照）。

図1　この記事のコードの簡単なフローチャート：コード内の主な関数間の通信

　この記事では以降、Erlangのメッセージ受け渡しを使って並列プロセスを同時に処理する方法を解説します。筆者のコードを分析しながらErlangの構文について説明し、再帰処理、パターンマッチング、並列処理がどのように動作するか見ていきます。Erlangの構文と機能をここですべて紹介することはできませんが、インターネット上に資料が多数あるので参考にしてください。