日本ソフトウェア科学会第 36 回大会 (2019 年度) 講演論文集

SML#と MassiveThreads の統合による超並列言語の実現
上野 雄大

大堀 淳

田浦 健次朗

マルチコア CPU のコモディティ化が進む中、プログラミング言語、特に宣言的で高水準な記述が可能な関数型言語におけるマルチコア対応の並列処理のサポートは十分とは言えない。この状況を打開する戦略のひとつは、マルチコア上の超並列計算を実現するシステム技術と関数型言語の言語処理系をそれぞれ独立したモジュールとして直接連携させることである。この連携の確立によって、種々のアーキテクチャ上で最適にスケジュールされる軽量スレッド技術の進歩が、将来に渡って、関数型言語で利用可能になると期待される。我々は、この課題の解決を目指し、システムプログラミング研究と言語コンパイラ研究を統合し、関数型言語 SML#と軽量スレッドライブラリ
MassiveThreads との直接連携に成功した。本発表では、この統合の概要および SML#の MassiveThreads 拡張の概要を報告する。

ウドなどに限らない、幅広いアプリケーション開発に1 はじめにとっての枢要な課題と言える。この課題に応える有種々の検証や学習など，高い計算能力を必要とする

望なアプローチのひとつは、並列処理単位を抽象し、アプリケーションの需要が高まるのに伴い、高性能アハードウェアを最大限に活用する、宣言的な超並列ププリケーション構築技術が求められつつある。現状でログラミング環境の構築と考える。各スレッドの実行は、これらアプリケーションのための計算資源はク単位である関数をデータとして抽象し、それら第一級ラウドコンピューティングやスーパーコンピュータにの関数を種々のデータ構造とともに宣言的にプログ

よって集中的に提供されているが、近い将来には、認ラムすることができる関数型プログラミング言語は、識や制御における柔軟でリアルタイムな処理の需要がこの超並列プログラミング技術の基盤になると期待拡大すると共に、個々の計算機器に高い計算能力が求される。

められると考えられる。このようなニーズに応え得る

しかしながら、現状では、宣言的で高水準な記述がアプローチのひとつは、マルチコア CPU を活用した可能な高階関数型言語におけるマルチコア対応の並超並列処理である。現在すでに、マルチコア CPU は列処理のサポートは十分とは言えない。その主な要因

PC から組込み機器に至る幅広いデバイスに採用されのひとつとして、関数型言語のスレッドや並列計算プており、また 32 コア以上を搭載するメニーコアプロリミティブのサポートが、急速なハードウェアの進歩セッサも急速に普及しつつある。これら大量のコアをと、ハードウェアを活用するシステムプログラミングひとつの目的のためにフル活用する超並列アプリケー技術の革新に十分に追いついていないことが挙げらションを構築する技術の確立が、大規模サーバやクラれる。多くの既存の関数型言語コンパイラは独自の並行並列実行モデルを持ち、実行時処理系の開発では、

Atsushi Ohori, 東北大学, Tohoku University.
Kenjiro Taura, 東京大学, The University of Tokyo.
Katsuhiro Ueno, 東北大学, Tohoku University.
(日本語表記は五十音順、英語表記は alphabetical orderである。)

それら並行並列実行モデルを直接実装するアプロー
チが取られてきた。このアプローチは、ガベージコレ
クション（GC）ベースのメモリ管理下で多相関数や第一級のスレッドなどを実現する上で数々の優位点を持つものの、その反面、システムライブラリとの互換量に低コストで作成可能なスレッドを指す。このアプ性が低く、結果として，異なるコアにスケジュールさローチでは、プログラマには軽量スレッドの生成と同れるマルチスレッドの実行さえ十分にサポートされ期機構を提供し、実行時処理系は軽量スレッドのハーていない（システムが提供するスレッドを利用できなドウェアコアへの最適なスケジューリングを行う。最い、あるいは利用できたとしても期待される並列性能小限のコンテキストを持つ軽量スレッドの実現と、タを発揮できない）のが現状である。

スクスティーリングを基本とする軽量スレッドスケ

この状況を抜本的に打開する戦略の一つは、マルジューリング技術は、システムプログラミング分野でチコア上の超並列計算を実現するシステムプログラ広く研究され、その成果として、メニーコアプロセッミング技術を、その独立性を保ったまま関数型言語にサ上でユーザプログラムから簡便に使用できる軽量統合し、GC を含む実行時処理系がスレッドライブラスレッドライブラリが開発されている。この軽量スリと直接連携する技術を確立することである。この

レッドアプローチは、第一級の関数と再帰的データ構連携によって、種々のアーキテクチャ上で最適にスケ造の柔軟かつ宣言的な定義を得意とする関数型言語ジュールされる超並列スレッド技術の進歩が、将来にとよく整合し、宣言的並列プログラミングの基盤とな渡って、そのまま関数型言語で利用可能になると期待り得るものである。

される。この洞察の下、著者らは、関数型言語コン

本研究における我々の戦略は、前述のとおり、このパイラ研究とシステムプログラミング研究を統合すシステムプログラミング技術を、その独立性を保っることによって、超並列処理を容易かつ効率よく使たまま、関数型言語コンパイラに直接取り入れるこ用できる関数型言語コンパイラの実現を目指し共同とである。これにより、関数型言語は、軽量スレッ研究を推進してきた。その結果、軽量スレッドライブドの実装技術の最新成果をそのまま享受することがラリ MassiveThreads を関数型言語 SML#に直接結でき、また、軽量スレッド技術は、それら技術を宣合することに成功した。その結果得られた言語処理言的プログラミングに展開できる。この洞察のもと、系は延べ 100 万を超える軽量スレッドをメニーコア

我々は、C 言語で書かれた軽量スレッドライブラリプロセッサの各コアに効率よくスケジュールできるこ

MassiveThreads [1] を、C 言語との直接連携機能を装と、またその上に宣言的な超並列処理が実現できる備している関数型言語 SML# [4] の実行時システムにことを確認した。本発表では、この統合の技術的課題結合することを具体的な課題とした。さらに、この結および SML#の MassiveThreads 拡張の概要を報告

合を基礎として、より高水準な並列言語機能の開発にする。なお、本研究の初期の結果は、 [3] で口頭発表取り組んだ。

されている。本発表では、その後の進展も踏まえた現状を報告する。SML#の MassiveThreads 拡張は、3 超並列関数型言語を実現する上での課題

並列スレッドスケジュール下のメモリ管理技術や超並MassiveThreads と SML#は、独立して開発され列言語機能の型理論的基礎づけを含む、数多くの技術たソフトウェアであり、また互いに、スレッドのスケ課題を克服した結果であり、それらの詳細は、他の機ジューリングやメモリ管理に係る低レベルの処理基会に発表する予定である。

盤でもある。それらの直接連携には数々の技術的課題がある。それら課題のうち主なものは以下の 2 点で2 超並列関数型言語を実現する戦略ある。

メニーコアを最大限に活用した並列プログラミン• スレッドスケジューリングとメモリ管理の統合

グを実現する上で、最も有望と思われるアプローチ

C 言語のスレッドとは異なり、関数型言語のスのひとつは、軽量スレッドによるタスク並列計算であレッドの実行には、CPU タイムスライス以外に、る。軽量スレッドとは、実際のハードウェアコア数や関数型言語処理系が管理するヒープ（メモリ）のオペレーティングシステムの制限を受けることなく大連続的な割当が必要である。このメモリ割当は、

本質的にグローバルな GC によって実現される。
この GC ベースのメモリ管理機構を GC とは独

open Myth.Thread

立に並行に動作する軽量スレッドスケジューラをfun fib 0 = 0統合することが、軽量スレッドと関数型言語との| fib 1 = 1統合の最大の課題である。CPU のタイムスライ| fib n =スの分配と同様、メモリの割当にはコンテキス

if n < 10トの管理が必要である。このメモリコンテキスthen fib (n - 1) + fib (n - 2)

トは、レジスタ集合やスタックといったスレッド

else
let val t =ローカルな情報からなるスレッドコンテキスト

create (fn () => fib (n - 2))とは異なり、GC を制御するためのグローバルな情報を含む。これは、共有メモリモデルにおけるin fib (n - 1) + join t

GC が本質的にグローバルな処理であることに由end

来する。これらコンテキストを、軽量スレッドス

図1

MassiveThreads–SML#プログラミングの例

ケジューラのスケジューリングオーバーヘッドを増加させずに管理する方式の確立が必要である。

• 超並列言語機能の設計

4 SML#の MassiveThreads 拡張の概要

MassiveThreads によって提供されるプログラミ

著者らは、これら課題を含む種々の課題を克服し、ングモデルは、タスク並列モデルである。このモ

MassiveThreads と SML#とを統合するための枠組

デルの下では、関数型プログラムにおける再帰みと技術を開発し、超並列機能を実現する SML#コ的な関数呼び出しを再帰的なスレッド生成に置ンパイラの開発に成功した。この開発成果の一部は、き換えるだけで、容易に並列処理を実現できる。

SML# 3.4.0 版としてすでにリリースされている。よ

その一方で、関数型言語においては、大規模集合り完全なサポートは今後のリリースで順次利用可能データ（bulk data）を処理の分配や結果の集約になる予定である。

を行うコンビネータで処理するプログラミング

本発表では、SML#の MassiveThreads 拡張の概パターン（例えば MapReduce モデルや並列ス要を報告する。達成された枠組みと技術の詳細についケルトンなど）も広く普及しており、大規模デーては、主な技術課題ごとに他の機会に発表する予定でタの宣言的な処理に貢献している。タスク並列ある。主要な開発項目は以下の通りである。に加え、これら集合データを並列処理する言語• MassiveThreads バインディングの作成

機能の設計と、その軽量スレッド基盤上での効率SML#では軽量スレッドを生成・同期する特別な的な実装技術の開発が、超並列関数型言語を実構文を用意せず、MassiveThreads の C 言語向け現する上でのさらなる課題のひとつであると考API を直接呼び出すバインディングライブラリえる。さらにそれら超並列言語機能を、関数型言のみをユーザーに提供することとした。このライ語が提供する高階の関数、多相型、ユーザ定義ブラリは、並列性を阻害しないように注意深く書の再帰的なデータ構造などの宣言的な機能と統かれている以外は、通常の SML#の C との直接合することで、単なる数値配列上の MapReduce連携機能のみを用いて構築されている。このライ計算を超える、幅広い並列アプリケーションの基ブラリを用いたプログラム例を図 1 に示す。

盤となると期待される。

• 並行 GC の拡張
軽量スレッドスケジューラの下での現実的でスケーラブルなメモリ管理を達成するため、マルチコア対応の並列 GC [5] のアーキテクチャを見直し、軽量スレッドにスケールする並行並列 GC

素について、predicateExp が満たされている間方式を新たに構築し、実装した。この GC は、スiteratorExp を繰り返し評価し、結果を大規模集レッドローカルストレージのみを用いて、スレッ合データとして返す式である。

ドの生成やタスクスティーリングの発生を認識実現された SML#は、実際に、100 万スレッドをし、GC とは独立に動く軽量スレッドライブラリ超えるスレッドを駆動することができ、さらに、36と連携する。

コアマシン上での初期的な実験により、コア数に対し• スケジューラの改良てスケールすることが確認されている。

我々の目標は、言語からの完全な独立を保ったま
ま、MassiveThreads ライブラリを SML#実行5 まとめ時処理系に統合することである。この制約の下、システムプログラミングと言語コンパイラ研究を軽量スレッドが言語処理系のメモリコンテキスト統合し、超並列スレッドライブラリ MassiveThreadsに効率よくアクセスできることを達成するため、と SML#の直接統合に成功した。本発表では、その効率よい軽量スレッドローカルメモリの実現と課題および拡張の概要を報告した。達成された枠組み

チューニングを行った。と技術の詳細は、他の機会に発表する予定である。
参 考 文 献• 大規模集合データに対する並列処理構文
リストや配列上の並列処理に加えて、近年注目されている vertex-centric 計算なども包摂する新たな宣言的並列構文と実装技術の確立を目指し、[2] によって提案された等式（方程式）の超並列処理を実現する言語構文

foreach id in dataExp[ where setupExp ] with pat
do iteratorExp while predicateExp
endとその軽量スレッドへのコンパイル技術を構築した。これは、大規模集合データ dataExp の各要[ 1 ] J. Nakashima, K. Taura. Massivethreads: A
thread library for high productivity languages. In
Concurrent Objects and Beyond, LNCS 8665, pages
222–238, 2014.
[ 2 ] S. Nishimura, A. Ohori. Parallel functional programming on recursively defined data via dataparallel recursion. J. Funct. Program., 9(4):427–462, 1999.
[ 3 ] A. Ohori, K. Taura, K. Ueno. Making SML#a general-purpose high-performance language. Unpublished manuscript.
[ 4 ] SML#. http://www.riec.tohoku.ac.jp/smlsharp/,2006–2019.
[ 5 ] K. Ueno, A. Ohori. A fully concurrent garbage
collector for functional programs on multicore processors. In Proc. ACM ICFP 2016, pages 421–433,2016.