ZEAM開発ログ2018年総集編その1: Elixir 研究構想についてふりかえる(前編)

(この記事は[「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/fukuokaex)の1日目です)

ZACKY こと山崎進です。

2018年ももう12月です。ついにアドベントカレンダーの季節がやってまいりました。[「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/fukuokaex)のトップバッターということで，**Elixir研究構想**について，ふりかえりたいと思います。

なお，[「技術的ポエム Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/poem)にて[「ZEAM開発ログ2018ふりかえり第1巻(黎明編): 2017年秋の出会いから2018年2月にElixirを始めるに至った経緯について」](https://qiita.com/zacky1972/items/236dea1013252b648eeb)というタイトルで，fukuoka.ex 代表の @piacere_ex さんとの出会いからElixir研究に突入するまでの経緯について詳細に解説しています。もしよろしければ合わせてご覧になっていただければ幸いです。

# Elixir 研究構想全体像

私が2018年4月の時点で思い描いた Elixir 研究構想の全体像を下図に示します。

![Elixir-proposal-2018.png](https://qiita-image-store.s3.amazonaws.com/0/55223/83a8e3e6-5145-9765-c6b8-5d25466b13e1.png)

この研究構想の中で，2018年中に着手した研究テーマは次の通りです。

* **Hastega**(ヘイスガ): 並列コンピューティングドライバのうち，マルチコアCPUとGPUに該当
* **micro Elixir / ZEAM**: コード生成/実行基盤に該当
* データ分析基盤のAI/ML/各種数学については，Hastegaと統合してFAISにて研究申請し採択。目下，研究開発中。
* **Sabotendar**(サボテンダー): 並行プログラミング機構に該当

以下，2018年中に得られた各プロジェクトの成果をふりかえります。前編の今回は，Hastega と micro Elixir / ZEAM についてふりかえります。

# Hastega: SIMD マルチコアCPU / GPU 駆動処理系

**Hastega**(ヘイスガ)は当初 Elixir から GPU を駆動して超並列処理をするライブラリ/処理系として研究がスタートしました。Hastega の名称はファイナルファンタジーに登場する最強のスピードアップ呪文に由来します。ちなみに Elixir や Phoenix もファイナルファンタジー由来の名称です。この研究プロジェクトが目標とするマルチコア CPU / GPU をフル活用して高速化する技術として Hastega は最もふさわしい名称ではないでしょうか。

Hastega は，次のような Elixir の MapReduce スタイルのコード

```elixir
1..1_000_000
|> Enum.map(foo)
|> Enum.map(bar)
```

は，次のような関数 `f` 

```elixir
def f(a) do
  a |> foo |> bar
end
```

を処理するコードを 1,000,000 並列に実行するのと等価であることから着想しています。

整数演算ベンチマークについて，Elixir から，SIMD 命令を用いたマルチコアCPU駆動のネイティブコードおよび OpenCL による GPU 駆動のネイティブコードを呼び出す Hastega プロトタイプを開発しました。8月にプログラミング研究会とSWESTにて発表しました。当時得られた結果では Elixir からの速度向上は約4〜8倍，Pythonからの速度向上は3倍以上となりました。発表資料(論文，プレゼンテーション，ポスター)を下記に示します。

[![Hastega: Elixirプログラミングにおける超並列化を実現するためのGPGPU活用手法](https://qiita-image-store.s3.amazonaws.com/0/55223/b81d5c4c-f8d5-387f-571d-e8251ce4509e.png)](https://zeam-vm.github.io/papers/GPU-SWoPP-2018.pdf)

[![Hastega: Elixirプログラミングにおける超並列化を実現するためのGPGPU活用手法](https://qiita-image-store.s3.amazonaws.com/0/55223/2fb20104-f286-53ae-456f-58abbe7f3fc7.png)](https://zeam-vm.github.io/GPU-SWoPP-2018-pr/#/)

[![Hastega: Elixirプログラミングにおける超並列化を実現するためのGPGPU活用手法](https://qiita-image-store.s3.amazonaws.com/0/55223/95ec444a-889c-e0d2-9e1d-8b24d84cb485.png)](https://zeam-vm.github.io/papers/SWEST_Hastega.pdf)

その後，複数の研究助成を受けて数々のマシンでテストする機会が得られたり，研究室学生が研究に合流してくれたりして，研究が進みました。

GPUでの並列処理そのものは非常に高速であるものの，CPUとGPUの間のプログラムコードやデータの転送がボトルネックになることが明らかになりました。したがって，GPUの高速性を生かすには，少ないデータ転送で計算負荷の高い処理を選ぶことと，転送のスケジューリングを最適化することが求められます。

マルチコアCPUによる並列処理も，並列化するまでのデータを分配する部分や，並列処理した後の結果を集計する部分に同期処理が必要で，これらの部分にかかる時間を短縮しないと並列化の効果が出ません。このことはアムダール(Amdahl)の法則として知られています。数々の実験をしたことで，CPUバウンドな処理の場合，処理するデータ量が相当多くないとマルチコアCPUで並列化するのがペイしないことが明らかになりました。一方，SIMD命令を用いた並列処理については，このようなペナルティが少なくなる見込みであることも明らかになりました。I/Oバウンドな処理の場合については，おそらくマルチコアCPUによる並列化の前に，並行プログラミング機構と非同期I/Oの整備に取り組んだ方が効果が高いと考えられます。

以上の知見から，現在研究開発を進めている Elixir コードから並列処理するネイティブコードを生成する Hastega / micro Elixir / ZEAM 処理系では，SIMD命令による並列化に優先して取り組むのが最善だろうと考えています。

# micro Elixir / ZEAM: 

**ZEAM**(ジーム) は ZACKY's Elixir Abstract Machine の略です。Erlang VM の BEAM (Bogdan/Björn's Erlang Abstract Machine)に対応するような形で命名しました。ZEAM という名称の初出は[2018年2月の「fukuoka.ex #5」](https://techjin.connpass.com/event/79311/)です。

[![fukuoka.ex ZEAM開発ログ 第1回: BEAMバイトコード・インサイド〜30年の歴史を誇るBEAMを超えるには](https://qiita-image-store.s3.amazonaws.com/0/55223/318b55bb-4b36-45ee-c9b9-b1ae7b80e55e.png)](https://zeam-vm.github.io/zeam-fukuoka.ex-20170223/#/)

ZEAM はその名の通り，Erlang VM に代わる Elixir ネイティブな処理系として構想されました。当初構想では BEAM バイトコードと互換性を持たせるつもりでいたのですが，BEAMバイトコードの解析に難儀したことと，その後の議論で，バイトコードレベルの互換性は不要で，Elixir のソースコードレベルの互換性があれば良いという結論に至り，当初構想から大きく方向転換することとなりました。

現在の構想では，Elixir のサブセットとなるプログラミング言語を策定し，その言語をコンパイル・実行する処理系として研究開発を始動しています。このサブセット言語を **micro Elixir** と呼んでいます。

micro Elixir / ZEAM 構想の初出は[fukuoka.ex#13：夏のfukuoka.ex祭＝技術のパラダイムシフト](https://fukuokaex.connpass.com/event/89472/)および[SWEST20](https://swest.toppers.jp/SWEST20/program/)です。下記のプレゼンテーションの後半で示されるように，かなり野心的な構想になっています。

[![耐障害性が高くマルチコア性能を最大限発揮できるElixir(エリクサー)を学んでみよう](https://qiita-image-store.s3.amazonaws.com/0/55223/75f39ef5-0517-509a-180e-095165054f4e.png)](https://swest.toppers.jp/SWEST20/program/pdfs/s2c_public.pdf)

micro Elixir の全ての仕様はまだ確定していませんが，まずは Elixir の**データ処理**の部分を抜き出して Hastega のコードを生成するという部分に集中することにしました。また，当面は NIFコードを生成することとし，Elixir / Erlang VM から呼び出すようにすることにしました。これを **Hastega / micro Elixir / ZEAM** と呼んでいます。このようにデザインすることで，すぐに既存のElixirのコードに組込むことが可能になります。

実装には Elixir マクロと LLVM を用いました。この辺りについては，明日2018年12月2日に公開予定の[「言語実装 Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/lang_dev)2日目の記事[「ZEAM開発ログ: Elixir マクロ + LLVM で超並列プログラミング処理系を研究開発中」](https://qiita.com/zacky1972/items/cc88260a3c93c9f71317)に詳しく書きますので，お楽しみに。

前述の通り，Hastegaの研究によって得られた知見をもとに，基本的な算術演算をコンパイルできるようにした後は，リストと `Enum.map` による次のような計算を SIMD 命令による並列化をしたループとしてコード生成することに集中する方針を立てました。

```elixir
1..1_000_000
|> Enum.map(foo)
|> Enum.map(bar)
```


# おわりに

当初別個に始まった Hastega と micro Elixir / ZEAM ですが，現在は合流して Hastega / micro Elixir / ZEAM として リストと Enum.map を用いた Elixir コードから SIMD 命令による並列化をしたループのネイティブコードを生成する処理系を研究開発しています。この詳細については，明日2018年12月2日に公開予定の[「言語実装 Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/lang_dev)2日目の記事[「ZEAM開発ログ: Elixir マクロ + LLVM で超並列プログラミング処理系を研究開発中」](https://qiita.com/zacky1972/items/cc88260a3c93c9f71317)に書きます。お楽しみに！

2018年中に着手した残りの研究構想は次のように紹介する予定です。お楽しみに！

* AI/ML/各種数学ライブラリ:
  * 2018年12月9日に公開予定: [「機械学習工学 / MLSE Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/mlse)9日目[「並列プログラミング言語 Elixir (エリクサー)を用いた機械学習ツールチェーン」](https://qiita.com/zacky1972/items/c8eae19ea8c047dfc6f9)
* 並行プログラミング機構 Sabotendar:
  * 2018年12月15日に公開予定: [「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/fukuokaex)15日目[「ZEAM開発ログ2018年総集編その2: Elixir 研究構想についてふりかえる(後編)」](https://qiita.com/zacky1972/items/a754a769ac7923edb79c)

もしよかったら他の[「ZEAM開発ログ」](https://qiita.com/zacky1972/items/70593ab2b70d192813df)もお読みください。

明日の[「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」](https://qiita.com/advent-calendar/2018/fukuokaex)2日目の記事は，  @koyo-miyamura さんの「【Phoenix】パスワード認証＆リレーションあり「ブログチュートリアル」」です。こちらもお楽しみに！