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

(この記事は「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」の15日目です)

ZACKY こと山崎進です。

「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」の14日目は， @kotar0 さんの「LiveViewというウェブアプリを作る第三の選択肢」でした。

さて，「ZEAM開発ログ2018年総集編その1: Elixir 研究構想についてふりかえる(前編)」では，下記の研究構想についてご紹介しました。

• Hastega(ヘイスガ): 超並列高速実行処理系
• micro Elixir / ZEAM: コード生成/実行基盤

今回の記事「ZEAM開発ログ2018年総集編その2: Elixir 研究構想についてふりかえる(後編) 」では，残りの下記の研究構想についてご紹介します。

• AI/ML/各種数学ライブラリ
• Sabotender(サボテンダー): 省メモリ並行プログラミング機構

AI/ML/各種数学ライブラリ

平成30年度 FAIS 新成長戦略推進研究開発事業 シーズ創出・実用性検証事業の研究助成金をいただいて「並列プログラミング言語 Elixir (エリクサー) における数学/AI/ML 基礎ライブラリの開発」を進めております。この研究では次のことを進めています。

1. 線形回帰とニューラルネットワークとそれらに必要な数学ライブラリの Elixir 実装の開発
2. 超並列高速実行処理系 Hastega の研究開発
3. 1 に 2 を適用した時の性能検証プロトタイプの実装と性能評価
4. 機械学習を用いた防災システム(光陽無線との共同研究開発)への 1,2 の適用の検討

現在表明できる研究開発内容については下記の記事にまとめています。

AI/ML/各種数学ライブラリ
|> 並列プログラミング言語 Elixir (エリクサー)を用いた機械学習ツールチェーン
|> Elixir(エリクサー)で数値計算すると幸せになれる

Sabotender (サボテンダー)

Sabotender は micro Elixir / ZEAM に搭載する予定の省メモリ並行プログラミング機構です。発祥としては，私たちが 2016年(Elixir研究を始めるより前)から進めていた Zackernel (ザッカーネル) の研究が原点です。

Zackernel の研究を始めてから Elixir の研究をスタートさせるまでの経緯と，Zackernel の原理については「ZEAM開発ログ2018ふりかえり第1巻(黎明編): 2017年秋の出会いから2018年2月にElixirを始めるに至った経緯について」に詳しく書きました。

また，2018年に Zackernel の省メモリ性能の評価と，Node.js・Zackernelと同じコールバック方式をネイティブコードを使わずに Elixir のみで実装した軽量コールバックスレッド(LCB)の実装と省メモリ性能の評価を行いました。その研究成果は次の通りです。

Zackernel は1スレッドあたり約200バイトという省メモリ性能を達成しました。これに対し LCB は1スレッドあたり約1.3KBでした。比較対象となる Elixir プロセスは1プロセスあたり約2.8KB，C++11 スレッドは1スレッドあたり約546KBでした。

さらに学生が取り組んだ研究では，Zackernel のアプローチでさらに省メモリ性を追求すると1スレッドあたり50バイト強の省メモリ性を達成できる可能性があることが示唆されました。

以上を踏まえた時に，Elixir における省メモリ並行プログラミング機構としては，LCB 方式，すなわち Erlang VM をそのまま用いた Elixir プログラミングによって実現するよりも，Zackernel 方式，すなわち並行プログラミング機構をネイティブコードで実装して Elixir から利用できるようにした方が，より省メモリ性能を追求できるということがわかりました。そこで，現在新規研究開発中の micro Elixir / ZEAM に Zackernel 方式の並行プログラミング機構を搭載する方向で研究開発を進めています。これが Sabotender (サボテンダー) です。

Sabotender も，Elixir や Phoenix，Esuna，Hastega などと同様，ファイナルファンタジー由来の名称です。ファイナルファンタジーのサボテンダーはモンスター・召喚獣の一種で，非常に素早く攻撃されてもなかなか当たらない，針を1,000本飛ばす攻撃技を持つ，といった特徴を備えています。このような特徴が省メモリ並行プログラミング機構のイメージに合致したので，Sabotender と命名しました。

Sabotender では，次のような研究開発目標を掲げています。

• 省メモリ: Zackernel 方式の採用により1タスクあたり200バイト程度もしくは200バイトを切る省メモリ性能を備える
• 同時セッション接続数: Phoenix に適用した時に従来の10倍程度以上の同時セッション接続数を達成する
• コンテキストスイッチの効率性: Zackernel 方式の追求により従来方式よりも高速にコンテキストスイッチをできるようにする
• マルチコアCPUの効率性: マルチコアCPUで効率よく実行できるような設計にする
• キャッシュメモリの効率性: キャッシュメモリの利用効率を向上させるスケジューリングとコンテキストスイッチ時のプリフェッチを実装する
• スケジューリングの効率性: Hastega と連携した 実行時間推定に基づくスケジューリング最適化機構を実装する
• 耐障害性: GC を含むメモリ管理機構との連携と GenServer 互換の API の提供により，従来の Erlang VM で達成していた高い耐障害性を維持する
• イベント処理能力: アクターモデルに基づく並行プログラミングスタイルを維持したまま，従来の Erlang VM で起こったイベントキューが「詰まる」問題を抜本的に改善する
• 安全性: モデル検査と型検査などを駆使して，処理系の不具合によるデッドロックや不公平性，型不一致を防止する

それぞれ説明します。

省メモリ

Nodeプログラミングモデルに基づくコールバック方式のマルチタスク機構をネイティブコードで一から実装することで，Zackernel で達成できた1スレッドあたり約200バイトの省メモリ性能と同等以上の省メモリ性能を追求します。これにより従来の10倍以上の省メモリが達成できると考えています。

同時セッション接続数

Sabotender で従来の10倍以上の省メモリが達成できることにより，Sabotender を Phoenix に適用した時に，従来の10倍程度以上の同時セッション接続数を達成することができると期待しています。

コンテキストスイッチの効率性

従来方式では，コンテキストスイッチをするときにレジスタの退避やメモリ空間の切り替えなどを行う必要があります。

これに対し Sabotender では，コンテキストが関数へのコールバックとして表現されること，プリエンプションが無くコールバック単位での擬似プリエンプションであることから，各コールバックでレジスタ生存期間が完結するのでコンテキストスイッチのためにレジスタを退避する必要がないと考えています。

また，Sabotender では，メモリ空間の切り替えは関数の実行に必要な実行時環境の切り替えとして表現されます。

マルチコアCPUの効率性

現状でも数コア〜数十コアのオーダーのマルチコアCPUが市販されており，将来的には数百コア〜数千コアのオーダーのマルチコアCPUが実現する可能性もあると考えています。

Sabotender は，このようなマルチコアCPUでの運用を前提とし，効率よくマルチコアCPUを活用できるような設計，すなわち，従来の Erlang VM の設計で追求されてきたように，コア間の同期・排他制御を極力しないで済むような設計を追求します。たとえば Erlang VM では，プロセスごとに独立したメモリ管理を行う分散メモリ方式や，コアごとに独立したスケジューラーを採用することで，コア間の同期・排他制御を行う状況を排除しています。Sabotender でも，このような設計思想を継承し，徹底的にコア間の同期・排他制御を削減します。

またコア数が数十以上になってくると，計算量も問題になってきます。O(n)以上の計算量のアルゴリズムではなく，たとえばO(log n)のアルゴリズムの採用も必要になってきます。どうしても必要なコア間の同期・排他制御については，計算量の少ないアルゴリズムの採用を進めます。

キャッシュメモリの効率性

CPUとメモリの速度差が大きく開いている現状では，キャッシュメモリの効率化が高速化のためにとても重要になっています。

そこで，micro Elixir / ZEAM では，超インライン展開を行い，ある関数の中で必要になるメモリのプリフェッチを，その関数を実行する以前にスケジューリングすることで，キャッシュメモリの効率化を図ろうとしています。

この考え方を Sabotender にも適用したいと考えています。すなわち，コンテキストスイッチを行う以前に，コンテキストスイッチ後に必要となるメモリのプリフェッチをスケジューリングすることができないかを検討します。

このような最適化は，従来のプリエンプティブかつ動的にスケジューリングするマルチタスクではほぼ実現不可能です。これに対し，Sabotender ではコールバック単位の粒度でコンテキストスイッチするため，本質的にはノンプリエンプティブであり，ある程度静的にスケジューリングできる余地があります。このことを利用し，コンテキストスイッチの前後でメモリのプリフェッチの最適スケジューリングを図りたいと考えています。

スケジューリングの効率性

停止性問題，すなわち「任意のプログラムが有限時間内で終了(停止)するかどうかを，アルゴリズムによって証明することはできない」という定理が存在することにより，任意のプログラムについて，そのプログラムを実行するのにどのくらいの時間がかかるのかを推定することは不可能だとされていました。

しかし，MapReduce プログラミングスタイルを徹底し再帰呼出しを禁止することで，有限の長さのデータを走査するプログラム片を帰納的に構成したプログラムに限定できます。そのようなプログラムは有限時間内で終了することを証明できると考えられるので，実用的な範囲で停止性問題の限界を超えることができます。

また，Stream を用いると MapReduce プログラミングスタイルでも無限長のデータを操作するプログラムを記述できますが，有限時間内で終了するのかどうかについて安全かつ近似的な判定をすることは比較的容易ではないかと考えられます。

これらの考え方を応用すると，機械語命令の実行時間の数理モデルとデータ長が与えられた時に，プログラムの実行時間をデータ長の関数として推定することが可能なのではないかと考えています。これらを取りまとめて実行時間推定を設計・実装したいと考えています。

実行時間推定により，コールバック関数で表される各タスクの所要時間を推定することができます。これをもとに静的スケジューリングを行うことで，スケジューリングを最適化できる可能性が拓けてきます。

また Hastega と連携することで，CPU コアだけでなく，GPU も統合してスケジューリングを最適化できると考えています。

実行時間推定に基づく静的スケジューリングにより，従来のマルチプロセス/マルチスレッド方式の動的スケジューリングでは実現が困難だった，ハードリアルタイム性の保証や高度な実行効率の最適化，コンテキストをまたぐプリフェッチによるキャッシュメモリの効率化などが可能になるのではないかと期待しています。

耐障害性

Erlang VM の耐障害性を支える設計方針の1つとして，プロセスごとに独立したメモリ管理機構と GenServer によるプロセス管理機構の採用があります。

プロセスごとに独立したメモリ管理により，プロセスを再起動することで，たとえメモリのリークや不整合が起きていたとしても，プロセス単位でメモリの状態をリセットすることができます。また，いわゆる Stop the world すなわち Full GC がかかることによる全プログラムの一斉停止を避けることが可能になります。

また，GenServer によるプロセス管理機構により，各プロセスが正常に機能しているのか異常状態なのかを監視し，プロセスに異常が起こった時にエラーログに記録してプロセスを再起動するなどの適切な例外処理を行うことができます。

これらの特徴により，Elixir / Phoenix は高い耐障害性を実現しています。

Sabotender / micro Elixir / ZEAM でも，このような設計の思想と方針を継承し，Sabotender の導入に合わせて改良を重ねることで，高い耐障害性を維持・向上したいと考えています。

イベント処理能力

Elixir はアクターモデルに基づく並行プログラミングモデルを採用しています。アクターモデルの採用により，各プロセスの中では単一スレッドによる実行に集約され，同期・排他制御を行う必要がありません。Elixir の設計思想として，1つの資源の管理を1つの資源管理プロセスに集約し，資源に対するアクセスを資源管理プロセスに対する通信で表現することで，資源ごとの同期・排他制御を不要にしています。これにより，Elixir は効率の良い並行・並列処理を可能にしています。

しかし，その代償として，通信が集中する資源管理プロセスには慢性的に処理待ちのイベントが蓄積されやすく，イベントキューが「詰まって」処理が滞る不具合がしばしば発生します。

Sabotender で実現しようとしているのは，イベントキューが「詰まる」前に，アクセスが集中する資源管理プロセスを Sabotender によって多重化することで，処理が滞ることを未然に防止することです。しかも，アクターモデルに基づくプログラミングスタイルを堅持したままで，処理の多重化を実現しようと考えています。

そのためには，Node のように，資源への同期アクセスを徹底的に廃し，すべて非同期アクセスで統一することが肝要だと考えています。非同期アクセスを徹底するために構文を用意し，非同期アクセスの構文を活用した静的解析と最適化を進める方針を採ります。

また，アクセスの集中をできるだけ早く，できれば事前に予測して，適切にコアを割り当てて負荷分散を図ることも有効だと考えています。アクセス集中の予測のため，キャッシュメモリ同様に，資源アクセスのプリフェッチに相当する擬似命令を用意して，超インライン展開でプリフェッチ命令をスケジューリングするアプローチを検討しています。資源プリフェッチ擬似命令の存在により，事前にコアをスケジューリングする計画を立てることができるようになり，コンテキストスイッチをまたぐ資源プリフェッチのスケジューリングも可能性が拓け，アクセスが集中する前にコアをあらかじめ配置して備えることができるようになるでしょう。

さらに，資源管理プロセスと，資源管理プロセスへの通信を対応づけて印づけをすることで，プロセスのスケジューリングを行う際にアクセスが集中することが予測されるプロセスを優先的に多めの実行時間が割り当てられるようにスケジューリングすることも考えられます。

資源アクセスプリフェッチ擬似命令の発行に際し，前述の非同期アクセスと巧みに連携する形で実装できれば良いのではないかと思います。

以上のようなアプローチでイベント処理能力の向上を図りたいと考えています。

安全性

このような高度な処理系を信頼できるものにするためには，処理系自体に不具合が織り込まれない仕組みに設計することが肝要です。

想定される不具合としては，データ型の不一致による問題のほかに，並列プログラミングに起因するデッドロックや不公平性といった不具合が考えられます。

データ型の不一致などの問題については，型理論によって型安全性を追求するアプローチや，Alloy のような反例を例示することによるアプローチが有効です。また，並列プログラミングに起因する問題については，SPIN などのモデル検査のようなアプローチが有効です。

Sabotender の研究開発にあたり，このような理論的アプローチを積極的に導入して進めたいと考えています。

おわりに

2回にわたって私たちfukuoka.ex の Elixir 研究構想について紹介してきましたがいかがだったでしょうか？ 近日中にfukuoka.exポータルサイトにて研究紹介のページを立ち上げますので，お楽しみに！

次に私がアドベントカレンダー記事を書くのは「FPGA Advent Calendar 2018」17日目の「RISC-V on FPGA と Elixir で究極のマルチコアシステムを構築しよう！」です。お楽しみに！

明日の「fukuoka.ex Elixir／Phoenix Advent Calendar 2018」16日目は， @callmekohei さんの「BashScript を Elixir で書き直してみたっ（２倍速〜）」です。こちらもお楽しみに！