ZEAM開発ログv0.1.1 AI/MLを爆速にしたい！ Flow / GenStage でGPUを駆動できないの？

（この記事は、「Elixir or Phoenix Advent Calendar 2017」の11日目です）

昨日は @twinbee さんの「ElixirのGenStageに入門する#2 バックプレッシャーを理解する」でしたね。

「ZEAM開発ログ 目次」はこちら

はじめに

ZACKYです。

先日の fukuoka.ex に関するインタビューが記事になりました！ 私がElixirの研究に励むようになった経緯や，ZEAM構想について，すんげー長く，熱く語ったのですが，勢いはそのままに，当社比4分の1(笑)に圧縮してお送りしています。

【part.3】福岡のElixirコミュニティ fukuoka.exをどんな人がやってるか聞いてきた

さて，前回は「ZEAM開発ログv0.1.0 Flow / GenStage による並列プログラミング入門」で，Flowを使って並列プログラミングする時のコツについてご紹介し，次のようにまとめましたね。

1. Elixir では Flow / GenStage を用いて並列プログラミングをすることが容易にできます。
2. 思ったように並列性を稼げていないようならば，Flow.from_enumerable の max_demand を調整しましょう。
3. Flow.map をパイプラインで数珠繋ぎにしたい時には，Flow.map を1回に集約させて，Flow.map の中にパイプラインを作って数珠繋ぎにした方が高速です。
4. Flowでは stages のデフォルト値はHT込みのコア数となっているので，stages は多くの場合最適に設定されています。

ロジスティック写像のベンチマークを GitHubとHexで公開しました。

最後に次のように書きました。

• 上記の2,3についていちいち意識するのは面倒ですね。そこで私たちが開発しているZEAM(ZACKY's Elixir Abstract Machine)という処理系では，この辺りを最適化する仕組みを導入したいなと思っています。
• 次回は Elixir の可能性をもっと高められないか，ZEAMでどのような最適化を取り入れると効果的か，考察してみましょう。お楽しみに！

最近，並列プログラミングで実用的に熱いのが，GPUの利用，すなわちGPGPU(General Purpose computing on Graphics Processing Units)です。GPUを利用すると高速で計算できることから，人工知能AIや機械学習MLではGPUの利用が不可欠になってきています。

そこで今回は，「ZEAM開発ログv0.1.1 Flow / GenStage でGPUを駆動できないの？」というタイトルで考察してみたいと思います。先日の fukuoka.ex #8 でも講演した内容を踏まえています。

GPUの動作原理

最近のCG，3Dグラフィックというのは数学的な演算を非常に多く行うものなので，CPUにも勝る計算能力を備えたGPUが一般的に出回るようになってきました。3Dグラフィックでは，整数や浮動小数点の演算を非常に数多く並行して行う必要があることから，最近のGPUにはCPU以上の並列処理機能が備わっています。

一般的なGPUの並列プログラミングのモデルは，SIMD (シムディー)と呼ばれるものです。SIMD は Single Instruction, Multiple Data の略で，直訳すると，単一の命令列で複数のデータを処理するということになります。GPUは同じような計算を異なるオブジェクトに対して行うことが多いので，SIMDが適合します。

ちなみにSIMDを「シムディー」と読むのは米国流だそうです。日本の多くの方は「シムド」と読むことがあるそうです。「シムド」だと外国に行くと通じないので，注意してくださいね。(私はもともと「シムディー」と呼んでいて「シムド」と読むことを知りませんでした)

これに対し一般的なCPUの並列プログラミングのモデルは，MIMD(ミムディー)と呼ばれるものです。MIMD は Multiple Instruction, Multiple Data の略で，直訳すると複数の命令列で複数のデータを処理するということになります。CPUは異なるタスクを並行動作させて雑多な処理をすることが多いことから，SIMDは適合せずにMIMDで処理する必要があります。

SIMDとMIMDでは異なる進化を遂げてきました。SIMDは単純な処理ができるプロセッサを100以上とか1000以上といった超並列で動作させるという方向で進化してきています。最新のGPU，たとえばNVIDIAのGeForce GTX 1080 Tiでは3000を超えるコア数からなる並列度を備えています。CPUのコア数がせいぜい数10くらいのレベルに留まっていることを考えるとすさまじいです。

そのかわり，MIMDであるCPUでは1つのコアでの高度な処理能力を発展させてきました。特に違いが顕著なのは，CPUでは高度な分岐予測と投機的実行の機能を備えることにより，複雑な条件分岐と複雑なデータ構造からなるプログラムを高速に実行できるように進化してきました。このようなプログラムをGPUに与えても性能を発揮しません。

GPUが向いているのは，単純な構造で均質で大量にあるデータを，ほぼ同じような命令列で処理する場合です。多くの画像処理があてはまります。また最近の流行りですとディープラーニングやビットコインのマイニングもあてはまります。このようにグラフィック処理だけでなく一般的な目的でGPUを活用することをGPGPU (General Purpose computing on Graphics Processing Units)と呼びます。

まったくの余談ですが，中古のグラフィックボードの価格は，仮想通貨の価格に連動することが知られていますが，それはGPUでマイニングするのが一般的だからですね。なので，ゲーム用途やVR/AR用途，画像処理用途，人工知能用途などでGPUを利用する人は，仮想通貨の価格が下がったら，中古で良質のグラフィックボードが市場に出回っていないか，チェックするといいですよ。

ElixirとGPU〜FlowからのGPU利用の検討

現行のElixirでは，CPUマルチコア対応はしているものの，GPUをまるで活用していません。前回の実験でも検証したように，Elixirは並列プログラミングにとても向いた特性を持っていますから，GPGPUにも向いているんじゃないかと期待が持てます。

私のアイデアはこうです: たとえば下記のようなプログラムを考えます。

list
|> Flow.from_enumerable
|> Flow.map(foo)
|> Flow.map(bar)
|> Flow.map(hoge)
|> Enum.to_list

前回も説明したように上記↑のプログラムは下記↓のプログラムと等価，すなわち同じ結果になり，かつ下記↓の方が実行速度が速いです。そこで，まず上記↑のようなプログラムを等価な下記↓のプログラムに内部変換します。このような処理をコード最適化あるいは単純に最適化と言います。

list
|> Flow.from_enumerable
|> Flow.map(& (&1
  |> foo
  |> bar
  |> hoge
  ))
|> Enum.to_list

ここで前述のGPUの特性を考えてみましょう。GPUの並列プログラミングのモデルであるSIMDでは，単純な構造で均質で大量にあるデータを，同じような命令列で処理する場合に効果を発揮します。 このプログラムだと，単純な構造で均質で大量にあるデータである list というリスト構造について，同じような命令列である &1 |> foo |> bar |> hoge という一連のパイプライン処理を実行しています。

ということは，GPUに listで示されるリストを一気に転送した上で，各SIMDのコアに &1 |> foo |> bar |> hoge という命令列を実行させることで，一気に計算できるんじゃないか？ というわけです。

一般に，Flow を使ったプログラムは，このような単純変換の考え方でGPU駆動できると考えられます。これが私のアイデアです！

さっそくやってみよう〜でもその前に

GPU駆動でどのくらいスピードが向上するのか，とても期待が持てますね！

でもその前に，公正な評価をするためには，条件を揃えておく必要があります。GPGPUで書くプログラムは，Elixirではない別の言語，たとえばC言語で書く必要があるので，もしCPU単体で動作するプログラムをElixirで記述して，GPUを駆動するプログラムをC言語で記述したりすると，条件が異なりますよね。それだと，CPUとGPUの違いを測定しているのか，ElixirとC言語の違いを測定しているのか，わけがわからなくなります。

というわけで，まずは前回のElixirで書かれたロジスティック写像のベンチマークプログラムをC言語に移植して，速度を比較してみましょう。

おさらいとして，Elixir のベンチマークプログラムです。ソースコード全体はこちら

defmodule LogisticMap do
  def calc(x, p, mu) do
    rem(mu * x * (x + 1), p) 
  end

  def loopCalc(num, x, p, mu) do
    if num <= 0 do
      x
    else
      loopCalc(num - 1, calc(x, p, mu), p, mu)
    end
  end

  def mapCalc(list, num, p, mu, stages) do
    list
    |> Flow.from_enumerable(stages: stages)
    |> Flow.map(& loopCalc(num, &1, p, mu))
    |> Enum.to_list
  end

  def benchmark(stages) do
    IO.puts "stages: #{stages}"
    IO.puts (
      :timer.tc(fn -> mapCalc(1..0x2000000, 10, 6_700_417, 22, stages) end)
      |> elem(0)
      |> Kernel./(1000000)
    )
  end

  def benchmarks() do
    [1, 2, 4, 8, 16, 32, 64, 128]
    |> Enum.map(& benchmark(&1))
    |> Enum.to_list
  end
end

C言語で書くとこうなります。ソースコード全体はこちら

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

#define LOOP 10
#define P 6700417
#define MU 22
#define NUM_VALUES 0x2000000

static int logisticsmap_calc(int x, int p, int mu) {
    return mu * x * (x + 1) % p;
}

static int logisticsmap_loopCalc(int num, int x, int p, int mu) {
    for(int i = 0; i < num; i++) {
        x = logisticsmap_calc(x, p, mu);
    }
    return x;
}

void benchmark() {
    const int mu = MU;
    const int p = P;
    int *x;
    x = (int *)malloc(sizeof(int) * NUM_VALUES);

    for(int i = 1; i < NUM_VALUES; i++) {
        x[i] = i;
    }
    for(int i = 1; i < NUM_VALUES; i++) {
        x[i] = logisticsmap_loopCalc(LOOP, x[i], p, mu);
    }
    free(x);    
}

int main() {
    struct timeval start_time;
    gettimeofday(&start_time, NULL);

    benchmark();

    struct timeval end_time;
    gettimeofday(&end_time, NULL);

    time_t diffsec = difftime(end_time.tv_sec, start_time.tv_sec);
    suseconds_t diffsub = end_time.tv_usec - start_time.tv_usec;
    double realsec = diffsec + diffsub * 1e-6;
    printf("%f sec\n", realsec);

    return EXIT_SUCCESS;    
}

このC言語のプログラムは並列プログラミングではないので，コアを1つしか使いません。なので，公正な比較のためには，stagesが1の場合と比較する必要がありますね。また，今回はループを伴うのでbenchmarkと比較してみましょう。

実行結果

検証環境は次の通りです。

Mac Pro (Mid 2010)
Processor 2.8GHz Quad-Core Intel Xeon
Memory 16GB
ATI Radeon HD 5770 1024MB

実行結果を表にまとめると，次のようになりました。

Elixir(秒)	C言語(秒)
52.795620	4.232451

おお，さすがC言語は速いですね！ ざっと12倍は速いです。

前向きに捉えれば，Elixirという言語にはまだまだ高速化の余地があるということですね！ ZEAMのロードマップとしては，Elixirのコードの実行効率をC言語並みに高めたいです。そのために日夜研究に励んでいます。

ちなみに並列数を増やしたElixirの実行結果，さらにインライン展開したElixirの実行結果と比較するとこんな感じです。

Elixir(秒)	Elixir(秒)	Elixir(秒)	C言語(秒)
1並列ループ	8並列ループ	8並列インライン展開	1並列ループ
52.795620	12.664873	11.308742	4.232451

最速のものと比べても並列化されていないC言語はElixirより2.7〜3倍は速いですね。C言語を並列化した結果が楽しみです！

おわりに

1. GPUはSIMD(シムディー)というモデルで動作します。これに対し，CPUはMIMD(ミムディー)というモデルで動作します。
2. GPUはSIMDなので，単純な構造で均質で大量にあるデータを，同じような命令列で処理する場合に効果を発揮します。
3. ElixirのFlowを手がかりに最適化すると，GPUに向いたプログラムに変換することができます。
4. C言語はElixirよりざっと12倍は速い。Elixirにはまだまだ高速化の余地があります。

次回は「ZEAM開発ログv0.1.2 AI/MLを爆速にしたい！ Flow のコードを OpenCL で書いてみる〜CPU編」です！ お楽しみに！

明日は， @takasehideki さんの「ElixirでIoT#2：いろいろ分かるベンチマークを整備してみる」です。こちらもお楽しみに！