Embarrassingly Parallel なプログラムを pthread で並列化してみた

やったこと

後輩の授業で Embarrassingly Parallel なプログラムを並列化するという課題が出ていたので、ちょっとやってみました。

実際に使ったコードはgithubで公開中です。公開は課題の締切後に行いました。

課題1 1次元関数の数値積分の区間分割による並列化

実関数 $f(x)=sin(x)$ が与えられ、 $\int_0^{\pi/2} f(x) dx$ を区分求積法で求めるプログラムがあったとき、区間 $(0, \frac{\pi}{2})$ を N 分割し、 N 個の POSIX thread に割り当てて並列化するという問題です。

この課題は練習用で、プログラムは公開されていました。単に走らせて性能を測ればよいものでした。

課題2.1 素数探索プログラムの区間分割による並列化

2から10000000までの整数のうち、素数がいくつあるかを数えるプログラムが与えられたとき、区間を N 個に分割し、 N 個の POSIX thread で並列化する問題です。課題1のコードを利用すればできる比較的簡単な課題です。

課題2.2 素数探索プログラムの負荷分散を考慮した並列化

素数の分布は一様ではないため、課題2.1のコードでは負荷が偏ってしまいます。そこで区間を M 分割し、 N 個の POSIX thread を利用することで並列化するのが本課題です。

やりかたは単純で、

区間を M 個に分割し、それぞれをタスクとして作る。
N 個の POSIX thread を作る。

というものです。各 thread は

for j in range(0 .. M-1) :
  if (j 番目のタスクは終わっていない) :
    j 番目のタスクをやる

とふるまいます。これに排他制御を行います。タスクを表す構造体に「手を付けた」というフラグを追加します。

for j in range(0 .. M-1) :
  lock(mutex)
  if (j 番目のタスクは誰も手を付けていない) :
    j 番目のタスクに手を付ける
    unlock(mutex)
    j 番目のタスクをやる
  else :
    unlock(mutex)

このようにすれば OK です。

性能評価

性能評価は8コア(AMD64 2GHz)のマシン上で行いました.

実行時に gcc の最適化オプションを付け忘れたのでそのままです。。。

課題2.1

実行時間とスケーラビリティを示します.

課題2.2

この評価は「いくつ thread があったか」と「いくつのタスクに分割したか」という2点の切り口からグラフを作ってみました。

タスクを分割しないときは thread がいくつあっても意味がないので性能が出ず、分割されると性能が向上しています。1000-10000くらいに分割するとほぼ8倍の性能が出ていますが、100000分割したときには性能が劣化しています。キャッシュには乗ってるはずなので溢れることはないと思うのですが…謎です。