（この記事は、「fukuoka.ex(その2) Elixir Advent Calendar 2017」の6日目，「機械学習と数学 Advent Calendar 2017の5日目です)
昨日は @twinbee さんの「Elixirから簡単にRustを呼び出せるRustler#3 いろいろな型を呼び出す」でしたね。
おしらせ
満員御礼！Elixir MeetUpを6月末に開催します
※応募多数により、増枠しました
「fukuoka.ex#11：DB／データサイエンスにコネクトするElixir」を6/22（金）19時に開催します
私も現在連載中のElixirのGPU駆動について発表します！
さて本題〜はじめに
こんにちは， @zacky1972 こと山崎進です。ElixirでAI/MLを高速化する研究に取り組んでいます。現状としては，ElixirからGPUを駆動しようとしていて，今までにOpenCLでGPUを駆動するサンプルプログラムを公開しました。
本連載の前回記事はこちら
|> ZEAM開発ログv0.1.0 Flow / GenStage による並列プログラミング入門
|> ZEAM開発ログv0.1.1 AI/MLを爆速にしたい！ Flow / GenStage でGPUを駆動できないの？
|> ZEAM開発ログv0.1.2 AI/MLを爆速にしたい！ Flow のコードを OpenCL で書いてみる〜CPU編
|> ZEAM開発ログv0.1.3 AI/MLを爆速にしたい！ Flow のコードを OpenCL で書いてみる〜GPU編
|> ZEAM開発ログv0.1.4 Python/NumPyとElixir/Flow一本勝負！ElixirはAI/ML業界に革命をもたらすか!?
今までのまとめとしては次の通りです。
- OpenCLでGPUを利用した時にはC言語の1並列と比べて3.95倍の速度向上，Elixirの同等プログラムと比べて10.8〜11.9倍の速度向上になりました。
- OpenCLを使わずにマルチコアかつSIMD命令やAVX命令を使った場合は，GPUの場合より高速になる可能性があります。見積もりではElixirの同等プログラムと比べて13倍前後の速度向上を期待できそうです。
- GPUの場合は，データの転送に時間がかかっているので，データの転送量に比べて演算負荷が大きくなればなるほど，CPUよりGPUの方が有利になると思われます。
- CPUとGPUで適性を見極めて適切に負荷分散をすること，さらにCPUとGPUを並列実行することで，さらなるパフォーマンスを引き出せる可能性があります。
- Elixir / Flow は Python / NumPy より1.5倍前後速いです。
- OpenCL(GPU) は Python / NumPy より17倍前後速いです。
- 今後，研究・開発が進んだ暁には，PythonからElixirに移行することで，AI/ML処理の実行速度が大幅に向上する可能性があります。
今回はElixirからネイティブコードで書かれたロジスティック写像のベンチマークを呼び出してみます。これは，ElixirからGPUを駆動するにあたってネイティブコードを実行する必要があるので，その準備にあたります。 @twinbee さんが Rustler を使って下記のような連載をしていますので，参考にしながら進めていきましょう。
@twinbee さんのRustler連載はこちら
|> Elixirから簡単にRustを呼び出せるRustler #1 準備編
|> Elixirから簡単にRustを呼び出せるRustler #2 クレートを使ってみる
Rustler による1回のロジスティック写像のコード
Elixir のロジスティック回帰のプログラムを Rustler で実行できるように改造しました。Elixir に加えて，Rust のインストールが済んでいる前提です。
lib/logistic_map_Nif.ex の一部
defmodule LogisticMapNif do
use Rustler, otp_app: :logistic_map, crate: :logistic_map
# When your NIF is loaded, it will override this function.
def calc(_x, _p, _mu), do: :erlang.nif_error(:nif_not_loaded)
end
native/logistic_map/src/lib.rs の一部
#[macro_use] extern crate rustler;
#[macro_use] extern crate lazy_static;
use rustler::{NifEnv, NifTerm, NifResult, NifEncoder, NifError};
mod atoms {
rustler_atoms! {
atom ok;
//atom error;
//atom __true__ = "true";
//atom __false__ = "false";
}
}
rustler_export_nifs! {
"Elixir.LogisticMapNif",
[("calc", 3, calc)],
None
}
fn calc<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>> {
let x: i64 = try!(args[0].decode());
let p: i64 = try!(args[1].decode());
let mu: i64 = try!(args[2].decode());
Ok((atoms::ok(), mu * x * (x + 1) % p).encode(env))
}
以上で，Elixirの LogisticMapNif.calc を呼び出すと，Rustの calcを呼び出すことができます。順にコードを見ていきます。
defmodule LogisticMapNif do
use Rustler, otp_app: :logistic_map, crate: :logistic_map
# When your NIF is loaded, it will override this function.
def calc(_x, _p, _mu), do: :erlang.nif_error(:nif_not_loaded)
end
do以下で NIF(Native Implemented Functions)を呼び出すという宣言をしています。引数に_をつけることで，変数を使用していないという警告を抑制しています。
rustler_export_nifs! {
"Elixir.LogisticMapNif",
[("calc", 3, calc)],
None
}
この記述は Rustler の設定です。Elixir の "LogisticMapNif"モジュールの"calc"関数を呼び出した時に Rust の calc 関数を呼び出します。この例では関数が同じ名称になっているのでわかりにくいですが，二重引用符 "" がついている方が Elixir の関数名，ついていないほうが Rust の関数名です。数字の3は引数の数を表します。
fn calc<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>> {
let x: i64 = try!(args[0].decode());
let p: i64 = try!(args[1].decode());
let mu: i64 = try!(args[2].decode());
Ok((atoms::ok(), mu * x * (x + 1) % p).encode(env))
}
Rust の calc 関数の本体です。最初のfn calc<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>>は，Rustlerを使った場合，どんな関数であってもまったく同じ型をしています。実行時環境 NifEnv と項 NifTerm を受け取って項を要素に持つ結果 NifResult<NifTerm>を返します。
let x: i64 = try!(args[0].decode()); let p: i64 = try!(args[1].decode()); let mu: i64 = try!(args[2].decode()); では項から引数を読み取っています。i64は64ビットの整数型で，Elixirの整数型に対応します。ここで型が合わないとエラーになります。
Ok((atoms::ok(), mu * x * (x + 1) % p).encode(env)) では計算して結果を返しています。atoms:ok() はElixirで書くと:okというアトムに対応します。mu * x * (x + 1) % p はロジスティック写像の計算部分です。整数演算はC言語とほぼ同じです。(atoms::ok(), mu * x * (x + 1) % p)と括ることで Elixir のタプルに相当する構造体を構成し，encode(env)でElixirの表現形式に変換します。OK(...)によって正常終了であることを示します。 @twinbee さんの「Elixirから簡単にRustを呼び出せるRustler #3 いろいろな型を呼び出す」も参照するといいですよ。
以上の実行結果は次のような感じです。
iex(1)> LogisticMapNif.calc(1,61,22)
{:ok, 44}
Rustler によるロジスティック写像ベンチマーク
ロジスティック写像の1回の呼び出しだけをネイティブコードで呼び出しても速度向上は少ないと思われますので，まとまった演算をネイティブコード化してみます。
lib/logistic_map_Nif.ex の一部
defmodule LogisticMapNif do
use Rustler, otp_app: :logistic_map, crate: :logistic_map
def map_calc_list(_list, _num, _p, _mu), do: :erlang.nif_error(:nif_not_loaded)
end
インタフェースとしては，第1引数としてリストを受け取り，1つ1つの要素を x として num回のロジスティック写像の計算を行います。
Elixirのコードで書くと次のような計算をRustで書いてみましょう。
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
|> Enum.map(& loopCalc(num, &1, p, mu))
|> Enum.to_list
end
#[macro_use] extern crate rustler;
#[macro_use] extern crate lazy_static;
use rustler::{NifEnv, NifTerm, NifResult, NifEncoder, NifError};
use rustler::types::list::NifListIterator;
rustler_export_nifs! {
"Elixir.LogisticMapNif",
[("map_calc_list", 4, map_calc_list)],
None
}
fn loop_calc(num: i64, init: i64, p: i64, mu: i64) -> i64 {
let mut x: i64 = init;
for _i in 0..num {
x = mu * x * (x + 1) % p;
}
x
}
fn map_calc_list<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>> {
let iter: NifListIterator = try!(args[0].decode());
let num: i64 = try!(args[1].decode());
let p: i64 = try!(args[2].decode());
let mu: i64 = try!(args[3].decode());
let res: Result<Vec<i64>, NifError> = iter
.map(|x| x.decode::<i64>())
.collect();
match res {
Ok(result) => Ok(result.iter().map(|&x| loop_calc(num, x, p, mu)).collect::<Vec<i64>>().encode(env)),
Err(err) => Err(err),
}
}
まず
rustler_export_nifs! {
"Elixir.LogisticMapNif",
[("map_calc_list", 4, map_calc_list)],
None
}
ここでRustlerの設定を記述して Elixir のコードと Rust のコードの対応関係を記述しています。何が書いてあるかは大体もうわかりますね？ 数字の4は引数の数ですよ。
fn loop_calc(num: i64, init: i64, p: i64, mu: i64) -> i64 {
let mut x: i64 = init;
for _i in 0..num {
x = mu * x * (x + 1) % p;
}
x
}
これはElixirから直接呼ばれないRustの関数loop_calcを定義しています。
-
fn loop_calc(num: i64, init: i64, p: i64, mu: i64) -> i64は，64ビット整数型のnum, init, p, muを引数にして64ビットの整数型を返す関数loop_calcの宣言です。 -
let mut x: i64 = init;ですが，変数宣言にmutと書くことで，ミュータブル，つまり再代入可能だと宣言しています。Rustの変数はデフォルトでイミュータブル，つまり1回値が決まると変更できないという設定になっています。 -
for _i in 0..numはC言語で書くとfor(int i = 0; i < num; i++)です。iの値を後で使わないので，_iとして警告を抑制しています。 -
x = mu * x * (x + 1) % p;はロジスティック写像の漸化式にあたります。xに再代入していますね。 - 最後の
xは，xの値を返すという意味になります。Rustでは，Rubyのように，最後に評価された式が関数全体の戻り値になります。
fn map_calc_list<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>> {
let iter: NifListIterator = try!(args[0].decode());
let num: i64 = try!(args[1].decode());
let p: i64 = try!(args[2].decode());
let mu: i64 = try!(args[3].decode());
let res: Result<Vec<i64>, NifError> = iter
.map(|x| x.decode::<i64>())
.collect();
match res {
Ok(result) => Ok(result.iter().map(|&x| loop_calc(num, x, p, mu)).collect::<Vec<i64>>().encode(env)),
Err(err) => Err(err),
}
}
- Elixirから呼ばれるRust関数は
fn map_calc_list<'a>(env: NifEnv<'a>, args: &[NifTerm<'a>]) -> NifResult<NifTerm<'a>>という型をしています。 -
let iter: NifListIterator = try!(args[0].decode());では第1引数のリストを読み込んでいます。Elixirのリストに対応する構造体はNifListIteratorです。この時点ではまだ先頭要素だけを読み込んでいます。 -
let res: Result<Vec<i64>, NifError> = iter.map(|x| x.decode::<i64>()).collect();では，リストの各要素を読み込んで整数型のベクターVec<i64>化しています。型が合わないとエラーになることがあるので，直接Vec<i64>の型になるのではなく，Result<Vec<i64>, NifError>型で受けます。 - リストの読み込み方については @twinbee さんの「Elixirから簡単にRustを呼び出せるRustler #3 いろいろな型を呼び出す」も参照するといいですよ。
-
iter.map(...).collect()という形式は，MapReduce的な計算，Elixirでいうと，list |> Enum.map(...) |> Enum.to_listに相当します。 -
iter.map(|x| x.decode::<i64>())で，Elixir形式の各要素を整数型として読み込みます。これによりリストをまず1回走査することになります。 -
match res以下で，リストの各要素が全て整数型だった時にはOk(result) =>以下を実行し，どれか整数型ではなかった場合にはErr(err) =>以下を実行します。ちょうどtry ... catch ...構文に相当しますね。 -
result.iter().map(|&x| loop_calc(num, x, p, mu)).collect::<Vec<i64>>().encode(env)はおなじみ MapReduce 的な構文でloop_calc関数を呼び出しています。collect::<Vec<i64>>()をもし単にcollect()とすると，型推論に失敗してエラーになります。ここではcollectで集めた結果をVec<i64>型であると注釈をつけています。これは慣れないと難しいですね。この辺りが Rust プログラミングの難しさの一端になっています。ここでも1回走査します。 - 全体として2回走査します。これをうまく1回の走査で実現できれば高速化の余地がありますが，型エラーに阻まれてうまくプログラミングできませんでした。
ここまでで実行してみると，ちゃんと動作します。
iex(1)> [1,2,3] |> LogisticMapNif.map_calc_list(10, 61, 22)
[28, 25, 37]
ではベンチマークプログラムに組み込んでみましょう。次のように実行してみたとします。
lib/logistic_map.ex
defmodule LogisticMap do
@logistic_map_size 0x2000000
@default_prime 6_700_417
@default_mu 22
@default_loop 10
def mapCalc5(list, num, p, mu, stages) do
list
|> Enum.to_list
|> LogisticMapNif.map_calc_list(num, p, mu)
end
@doc """
Benchmark
"""
def benchmark5(stages) do
IO.puts "stages: #{stages}"
IO.puts (
:timer.tc(fn -> mapCalc5(1..@logistic_map_size, @default_loop, @default_prime, @default_mu, stages) end)
|> elem(0)
|> Kernel./(1000000)
)
end
@doc """
Benchmarks
"""
def benchmarks5() do
[1, 2, 4, 8, 16, 32, 64, 128]
|> Enum.map(& benchmark5(&1))
|> Enum.reduce(0, fn _lst, acc -> acc end)
end
end
mapCalc5 で Enum.to_list を挟んでいるのは，Rustler のコードが範囲オブジェクトに対応していないためです。
では，実行してみます。
iex(1)> LogisticMap.benchmark5(1)
stages: 1
16.628159
現時点では並列実行していませんから，なかなかの速さではないでしょうか。
では気を良くして Flow を使って並列実行してみましょう。
mapCalc5 のみ変更
def mapCalc5(list, num, p, mu, stages) do
list
|> Stream.chunk_every(stages + 1)
|> Flow.from_enumerable(stages: stages)
|> Flow.map(fn(i) ->
i
|> LogisticMapNif.map_calc_list(num, p, mu)
end)
|> Enum.to_list
|> List.flatten
end
やりたいことは，Flow の並列実行機能は使いつつ，リストの要素自体はひとまとめにして渡したいということです。そこで，Stream.chunk_everyを使って並列実行したい数にリストを分割してから Flow に渡してあげます。最後に List.flatten で平滑化します。
実行してみましょう。
あれ？ かえって遅くなったような。。。
実は，Stream.chunk_every を使って Flowを起動するのにオーバーヘッドがかかるのと，NIFを呼び出して完了するまでの時間を1ms以内に抑えないとVMが停止してしまいパフォーマンスが落ちてしまっているという2つの原因で実行速度が落ちているのです。
後者の対策としては，一度に渡すリストの長さを短くすることが有効です。そこで，次のようにしてみました。
@logistic_map_chunk_num 0x400
def mapCalc5(list, num, p, mu, stages) when stages <= 1 do
list
|> Enum.to_list
|> LogisticMapNif.map_calc_list(num, p, mu)
end
def mapCalc5(list, num, p, mu, stages) when stages > 1 do
chunk_size = div(Enum.count(list) - 1, stages) + 1
list
|> Stream.chunk_every(chunk_size)
|> Flow.from_enumerable(stages: stages)
|> Flow.map(fn(i) ->
i
|> Stream.chunk_every(@logistic_map_chunk_num)
|> Enum.map(fn(j) ->
j
|> LogisticMapNif.map_calc_list(num, p, mu)
end)
end)
|> Enum.to_list
|> List.flatten
end
高速化のため，stages = 1 のときには Flow を使わずに直接駆動しています。1より大きい時には，リスト長を取得して chunk_size を計算し， Flow.mapの中で，Stream.chunk_everyとEnum.mapをつなげてリストを分割しています。1回のNIF呼び出しで渡すリストのチャンクサイズは @logistic_map_chunk_num で与えます。
ほかにRustでつくった NIF 関数は次のものがあります。興味があったら，ソースコードを読んでみてください。相当苦労しましたが，速度面でそれほど報われませんでしたw
-
to_binary: リストからバイナリに変換する NIF 関数。とっても苦労しました！ そのうち解説を書きます。 -
map_calc_binary: バイナリ版のmap_calc
Flow.Window による Rustler 並列処理の高速化
mapCalc5もなかなか高速なのですが，並列化した時にもっと高速化できるのではないかと期待してしまいます。
@twinbee さんに相談したところ， Flow.Window という便利な機能があると教わったので， @twinbee さんと一緒に探求してみました！
Flow.Window は並列処理するにあたって処理を分配した後，一定の長さや時間の処理をするところで区切りを設けて，次の処理の分配を行うという機能です。
Flow.Window を使ったコードはこちらです。なお stage = 1 のときは mapCalc5 と同じ動作です。
@logistic_map_chunk_num 0x400
def mapCalc8(list, num, p, mu, stages) when stages <= 1 do
list
|> Enum.to_list
|> LogisticMapNif.map_calc_list(num, p, mu)
end
def mapCalc8(list, num, p, mu, stages) when stages > 1 do
window = Flow.Window.global
|> Flow.Window.trigger_every(@logistic_map_chunk_num, :reset)
list
|> Flow.from_enumerable
|> Flow.partition(window: window, stages: stages)
|> Flow.reduce(fn -> [] end, fn e, acc -> [e | acc] end)
|> Flow.map_state(& &1 |> LogisticMapNif.map_calc_list(num, p, mu))
|> Flow.emit(:state)
|> Enum.to_list
end
1ms問題を解決するためのキャリブレーション機能
NIFの呼び出しは実行時間が1ms以内でないとVMが停止してパフォーマンスが極端に落ちるという問題があるので，1ms以内に収まるようにリスト長を調整するキャリブレーション機能を実装してみました。
lib/logistic_map_Nif.ex
defmodule LogisticMapNif do
use Rustler, otp_app: :logistic_map, crate: :logistic_map
# When your NIF is loaded, it will override this function.
def calc(_x, _p, _mu), do: :erlang.nif_error(:nif_not_loaded)
def map_calc_list(_list, _num, _p, _mu), do: :erlang.nif_error(:nif_not_loaded)
def to_binary(_list), do:
:erlang.nif_error(:nif_not_loaded)
def map_calc_binary(_binary, _num, _p, _mu), do:
:erlang.nif_error(:nif_not_loaded)
def floor(value, precision \\ 1) do
Float.floor(value / precision) * precision |> Kernel.trunc
end
def get_env(key) do
System.get_env(key) |> String.to_integer
end
def put_env(key, value) do
System.put_env(key, "#{value}")
"#{key}: #{value}\n"
end
def env_floor(key) do
System.put_env(key, "#{Kernel.max(1, floor(get_env(key), 100))}")
end
def calibration(key, function, is_map_calc, length \\ 10) do
input = 1..length |> Enum.to_list
{micro, _} = :timer.tc(fn -> function.(input) end)
ms = micro |> Kernel./(1000)
if ms >= 1 do
env_floor key
get_env key
else
put_env(key, length)
calibration(key, function, is_map_calc, length + 10)
end
end
def min_calibration(keywords, number \\ 10) do
key = keywords[:key]
function = keywords[:function]
is_map_calc = keywords[:is_map_calc]
value = 1..number
|> Enum.map(fn _ -> calibration(key, function, is_map_calc) end)
|> Enum.min
put_env(key, value)
end
def init do
[[key: "LogisticMapNif_map_calc_list", function: fn x -> map_calc_list(x, 10, 61, 22) end, is_map_calc: true],
[key: "LogisticMapNif_map_calc_binary", function: fn x -> x |> Enum.reduce("", fn (x, acc) -> acc<><<x>> end) |> map_calc_binary(10, 61, 22) end, is_map_calc: true],
[key: "LogisticMapNif_map_calc_binary_to_binary", function: fn x -> x |> to_binary |> map_calc_binary(10, 61, 22) end, is_map_calc: true]]
|> Enum.map(& min_calibration(&1))
|> IO.puts
end
end
実行結果
下記の環境での実行結果です。
Mac Pro (Mid 2010)
Processor 2.8GHz Quad-Core Intel Xeon
Memory 16GB
実行結果を表にまとめてみました。またC言語やOpenCLでの実行結果を付記しています。
| stages | benchmark1 | benchmarks3 | benchmarks5 | benchmarks8 | C | OpenCL1 | OpenCL2 |
|---|---|---|---|---|---|---|---|
| pure Elixir | pure Elixir | Rustler | Rustler | C | OpenCL | OpenCL | |
| loop | inlining inside of Flow.map | loop, passing by list | passing by list, with Window | loop | CPU, loop | CPU, inlining | |
| 1 | 54.162408 | 42.181708 | 12.165364 | 10.138827 | 4.232451 | - | - |
| 2 | 27.194265 | 24.057105 | 35.714096 | 17.302215 | - | - | - |
| 4 | 17.949165 | 15.936957 | 35.665139 | 16.241035 | - | - | - |
| 8 | 14.621331 | 13.465502 | 36.476310 | 16.663471 | - | 1.496656 | 1.483530 |
| 16 | 14.823739 | 13.914704 | 38.289668 | 18.059605 | - | - | - |
| 32 | 15.294675 | 13.257334 | 41.796529 | 21.647251 | - | - | - |
| 64 | 15.303911 | 13.338678 | 40.862091 | 28.272938 | - | - | - |
| 128 | 15.729719 | 13.180197 | 42.129716 | 40.542968 | - | - | - |
- pure Elixir では論理コア数と等しい
stages=8のときが最速ですが，Rustlerではstages=1の時が最速です。並列プログラミングがうまく機能していませんね。おそらくFlowのオーバーヘッドが原因と思われます。 -
benchmarks8ではだいぶ並列処理性能が改善されています。Flow.Windowは比較的うまく機能するようです。 - 最速同士で比べると，pure Elixir → Rustlerで速度差はほとんどありませんでした。残念。
-
stages=1のときの Rustler とC言語を比べるとまだまだ速度差は歴然としています。これはElixirの表現形式と相互変換する部分，とくにリストとベクターの相互変換に時間がかかっているものと思われます。C言語並みに高速化するには，リストをベクター化(配列化)する部分に工夫が要りそうです。LLVMで直にアセンブリコードを出力したらどうなるか興味があります！
おわりに
- Rustler を使っても pure Elixir から高速化できませんでした。
- Flow は便利ですが，オーバーヘッドがかなりあります。
- Rustler とC言語やOpenCLと比べるとまだまだ速度差は歴然としています。さらなる高速化に向けてはデータ表現の相互変換をどのように工夫するかが鍵になりそうです。LLVMで直にアセンブリコードを出力したらどうなるか興味があります！
そういうわけで今回は失意の結果ではあるのですが，次回は気を取り直してRustlerからGPUを駆動してみたいと思います。お楽しみに！
明日は @koga1020 さんの「Elixirのパーサーコンビネータライブラリ Combine入門」です。こちらもお楽しみに！
p.s.「いいね」よろしくお願いします
よろしければ，ページ左上の 
や 
のクリックをお願いしますー
ここの数字が増えると，書き手としては「ウケている」という感覚が得られ，連載を更に進化させていくモチベーションになりますので，もっとElixirネタを見たいというあなた，私たちと一緒に盛り上げてください！