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

SML# の並列処理機能とその性能
上野 雄大

大堀 淳

マルチコア CPU がコモディティとして広く普及している一方で，宣言的で高水準な記述が可能な関数型言語におけるマルチコア CPU のサポートは十分とは言えない．この状況を打開する戦略のひとつは，関数型言語の言語処理系と並列計算を実現する軽量スレッド技術とをそれぞれ独立したモジュールとして直接連携させることである．この洞察に基づき，我々はシステムが提供する並列スレッド機能と直接連携する関数型言語処理系を実現する基盤技術を確立し，対話環境や自動的メモリ管理などの ML 系関数型言語の特徴を失うことなく高い並列計算性能を発揮する関数型言語 SML# の開発を推進してきた．最新の SML# コンパイラは，軽量スレッドの並列動作を止めない並行並列GC を搭載し，いくつかのベンチマークプログラムにおいて C 言語に匹敵するスケーラビリティを示している．本
発表では，SML# コンパイラの並列計算機能および並列処理性能の概要を報告する．

自動並列化の研究は古くから綿々と続けられている．

1 はじめに

しかしながら，関数型言語におけるマルチコア CPU

マルチコア CPU はコモディティとして広く普及し対応の並列処理のサポートは，C 言語に代表されるており，大型計算機から組み込み機器に至るまで，計手続型言語におけるそれと比較して，いまだ十分と算能力を有するあらゆるデバイスに搭載されている．

は言えない．その原因のひとつは，関数型言語の実行

科学技術計算，人工知能，ビッグデータ解析などの高モデルが要求する自動的なメモリ管理，およびそのい計算効率が求められる分野では，これら多数のコア実装技術であるガベージコレクション（GC）にある．

を持つプロセッサを最大効率で駆動するための並列

GC はプログラムが使用するメモリ全体を管理するたプログラミング技術は必須である．メニーコア化とめ，大域的な同期を本質的に含む逐次的な処理であ

並列プログラミングへの流れは今後ますます加速し，り，従ってプログラム全体の並列性能を落とす主要な近い将来には，複数のコアを高効率で駆動することが要因となり得る．また，GC の実行にはスレッドスケあらゆるドメインにおいて要求されるであろうこと

ジューラと GC の連携が必要不可欠であり，その連は想像に難くない．ソフトウェア開発の広い範囲にお携のために，GC とマルチスレッドの両方を装備する

いて，複数のコアをひとつの目的のためにフル活用す言語の多くは独自のスレッドスケジューラを言語処理る高水準並列プログラミング技術の確立は，幅広いア系に組み込んでいる．結果として，システムライブラプリケーション開発において枢要な課題と言える．

リとの互換性は低くなり，最新のシステムプログラミ

宣言的で高水準な記述が可能な関数型言語によるング研究の成果を含む軽量スレッドライブラリなどの並列計算は，並列プログラミングの難しさを大きく改活用が難しい．

善する可能性がある技術のひとつである．関数型言

この状況を打開するひとつの戦略は，大域的な同語と並列計算の相性が良いことは古くから主張され期を含まず，かつシステムが提供するスレッドスケており，関数型言語をベースとした並列計算モデルやジューラと互いの独立性を保ったまま直接連携する

Katsuhiro Ueno, Ohori Atsushi, 東 北 大 学, Tohoku
University.

ムを核として関数型言語処理系の実装技術を再構築

GC 方式を確立することである．この GC アルゴリズ

することで，マルチコア CPU 上の並列処理を実現す: (’a -> unit ptr, ’a) -> myth_thread_t

る最新のシステムプログラミング技術を，将来に渡っ

ここで#boxed は，型変数がヒープにアロケートされて，そのまま関数型言語から利用することが可能とた値のみ動く（従って C の void*と互換な表現を持なると期待される．この洞察の下，著者らは GC アつ）ことを表す型カインドである．myth_create 関数

ルゴリズムおよび関数型言語処理系の研究開発を行の第 1 引数はコールバック関数へのポインタである．

い，関数型言語 SML# [3] から軽量スレッドライブラ

SML# の FFI により，第 1 引数として任意の SML#

リ MassiveThreads [1] を直接利用する並列プログラ関数を myth_create 関数に渡すことができる．

ミングを可能にした．2020 年 5 月にリリースされた便宜のため，Pthreads API および MassiveThreads

SML# 3.6.0 版（以下，最新の SML# と呼ぶ）は，世API をほぼそのままインポートしたバインディング界を止めない並行並列 GC を装備し，いくつかのベライブラリが SML# コンパイラに付属している．こンチマークプログラムにおいて C 言語に匹敵する並れらのライブラリは，並列性を阻害しないように注

列処理性能を発揮する．本発表では，SML# が提供す意深く書かれている以外は，前述した FFI を用いたる並列処理機能およびそれを実現する GC 技術を概ユーザープログラムとして構築されている．これらの観すると共に，最新の SML# が示す並列処理性能のライブラリが提供する Pthread および Myth ストラ

概要を報告する．これらの技術的詳細は他の機会にクチャのシグネチャの一部を図 1 に示す．

発表する予定である．なお，本研究のこれまでの結果

SML# のスレッドはシステムライブラリが提供すは， [2] や [5] で口頭発表されている．本発表ではそのるスレッドそのものであるから，GC の対象ではな後の進展も踏まえた現状を報告する．

い．従って，create で作成したスレッドの資源は，スレッド API を C 言語から利用する場合と同様に，2 SML# の並列処理機能ユーザープログラムから detach または join を呼ぶ

前述の通り，高い並列性能を有する関数型言語を実ことで解放されなければならないことに注意が必要

現するための我々の戦略は，関数型言語とは独立に研である．

究されているシステムプログラミング技術を，そのSML# の並列処理性能を試す最も簡便な方法は，独立性を保ったまま，関数型言語から利用可能にす

MassiveThreads API の create および join を用いることである．従って，SML# は言語独自のスレッドてタスク並列プログラムを書き，それを SML# コンパモデルや並列計算機能をユーザーに提供しない．代イラの対話モードから実行することである．関数型言

わりに，SML# は POSIX スレッド（Pthreads）API語の一般的な書き方で再帰関数を書き，再帰呼び出しおよび軽量スレッドライブラリ MassiveThreads をを行う箇所を create と join で囲めばよい．ただし，直接サポートする．ユーザーは，C 言語との FFI を計算にかかる時間が軽量スレッドの管理にかかるオー通じて，これらの API そのものや，これらの API をバーヘッドを上回るように，計算の規模がごく小さい利用して書かれたライブラリを SML# にインポート

場合は create を呼ばないようにする（カットオフをすることができる．例えば，新たなユーザースレッド設定する）．Myth ストラクチャを用いて書いた fibを作成する MassiveThreads の API である関数の例を図 2 に示す．このプログラムは fib 40

myth_thread_t myth_createを計算するために 3,524,577 個の軽量スレッドを生(void *(*)(void *), void *);成する．MassiveThreads の軽量スレッドは，実際のは，以下のようにして SML# にインポートすること

CPU コア数や OS の制限を受けることなく，低コスができる．

トで大量に作成することができる．MassiveThreads

type myth_thread_t = unit ptr

は大量に作成された軽量スレッドを各 CPU コアに最val ’a#boxed myth_create =適にスケジューリングする．2 つ以上の CPU コアを_import "myth_create"

使用するには，SML# の対話モードを起動する際にstructure Pthread : sig

fun fib 0 = 0

structure Thread : sig| fib 1 = 1

type thread| fib n =val create : (unit -> int) -> thread

if n < 10

val detach : thread -> unit

then fib (n - 1) + fib (n - 2)

val join : thread -> intelse

val exit : int -> unit
val self : unit -> threadletval t = Myth.Thread.create

val equal : thread * thread -> boolend(fn _ => fib (n - 2))
instructure Mutex =structtype mutex

fib (n - 1) + Myth.Thread.join tend
図2

SML# による並列 fib 関数

val create : unit -> mutex
val lock : mutex -> unit

MYTH_NUM_WORKERS 環境変数にコア数をセットする．

val unlock : mutex -> unit

例えば，4 コアマシンで

val trylock : mutex -> bool
val destroy : mutex -> unit

MYTH_NUM_WORKERS=4 smlsharp
として起動した対話モードで fib 40 を実行したときendにかかる実時間は，環境変数をセットせずに起動した...

対話モードで実行したときに比べて約 1/4 になるはずである．

structure Myth : sig
structure Thread : sig
type thread

3 SML# の並行並列 GC
前述の通り，システムが提供するスレッドライブラ

val create : (unit -> int) -> thread

リを直接利用可能な関数型言語を実現するにあたり

val detach : thread -> unit

中核となる技術は，スレッドスケジューラと独立性を

val join : thread -> int

保ったまま連携するガベージコレクタである．この性

val exit : int -> unit

質を満たすために GC アルゴリズムに求められる要

val yield : unit -> unit

件は以下の通りである．

val self : unit -> threadval equal : thread * thread -> bool

• ミューテータスレッドの実行を止めないこと．最大の並列性能を得るためには逐次性を徹底的にend除去しなければならない．関数型言語処理系が導structure Mutex : sig

入する逐次性のひとつは，本質的にグローバルな

type mutex

GC 処理である．マルチコア CPU を駆動するス

val create : unit -> mutex

レッドスケジューラの性能を最大限に発揮させる

val lock : mutex -> unit

ためには，複数のコアで同時に実行されるミュー

val unlock : mutex -> unit

テータスレッドの動作を GC の実行が妨げては

val trylock : mutex -> boolならない．この性質を満たすためには，GC は世

val destroy : mutex -> unit...
図1

界を止めない並行 GC である必要がある．

• ミューテータが複数のコアにスケールするのにend

Pthread および Myth ライブラリのシグネチャ

合わせて GC も複数のコアにスケールすること．

ション領域を持つ．各ワーカースレッドは，自身関数型言語のスレッドの実行には，CPU タイムに割り当てられたユーザースレッドのルートセッスライスの他に，ヒープ（メモリ）の連続的なトを列挙し，生きているオブジェクトをトレース割り当てが必要である．このメモリの割り当てし，自分のアロケーション領域内の未使用領域をは GC によって実現される．同時に実行される回収する．ワーカースレッドとユーザースレッドミューテータが増えると，それらが要求するメモとの関連付けは，スレッドスケジューラとは独立リ量も必然的に増える．複数のミューテータによに行う．ガベージコレクタはスレッドローカルスるメモリ要求に応え続けるためには，メモリ要求トレージのみを用いてスレッドの生成やスレッドの増加に合わせて GC の効率も高めなければなの移動を認識する．

らない．この性質を満たすためには，GC は並列GC である必要がある．
• スレッドスケジューラによる自由なスケジュー• 3.5.0 版以前の SML# に実装されていた並行 GC
方式 [4] とは異なり，コレクタ専用のスレッドを用意しない．代わりに，各ワーカースレッドはリングを妨げないこと．マルチコア CPU の性能時折コレクタとして振る舞う．グローバルな GCを最大限に引き出す軽量スレッドスケジューラの進行はコレクタの集合によって管理される．コは，可能な限り多くのコアに均等に軽量スレッドレクタとしての仕事は他のワーカースレッドとはを割り当てようとする．そのため，軽量スレッド並行並列に行われる．この構成により，GC の並はその実行中にあるコアから別のコアに移動す

列度はワーカースレッドが増えるに従って自動的る可能性がある．一方，メモリの割り当てには，に増加する．シングルスレッドで動作していると

CPU タイムスライスの分配と同様，コンテキスきは自然に逐次 GC となる．

トの管理が必要である．このコンテキストには，GC を制御するためのグローバルな情報を含む．

4 SML# の並列処理性能

これらコンテキストを，スレッドスケジューラの最新の SML# には以下のタスク並列ベンチマーク

動作とは独立に，スレッドが移動する可能性も考慮して管理する方式の確立が必要である．
我々は，軽量スレッドスケジューラの下でのスケーラブルなメモリ管理を実現するため，マルチコア対応の並行 GC [4] を見直し，これらの要件を満たす並行プログラムが付属する．

• ﬁb．図 2 に示された fib 関数を用いて fib 40を計算する．

• mandelbrot．2048 × 2048 ピクセルのマンデルブロ集合を描画する．

並列 GC 方式を新たに構築し，SML# コンパイラに• nqueens．14-クイーン問題を解く．

実装した．その概要は以下の通りである．

• cilksort．4,194,304 個の浮動小数点数を並列マー• SML# の並行並列 GC は，ワーカー–ユーザーモジソートする．

デルに基づくノンプリエンプティブな軽量スレッ

これらのベンチマークプログラムを SML# 3.5.0 版

ドに対応する．ワーカースレッドが CPU タイム（SML#-3.5），および最新の SML# に対してバグフィッ

スライスをユーザースレッドに供給するのと同様クスとチューニングを行ったバージョン（SML#）でに，ワーカースレッドがユーザースレッドに連続実行したときの平均実行時間（average task time）お的なメモリ割り当て機能を提供する．ワーカース

よび最大 resident set size(MaxRSS) を図 3 に示す．

レッドはそのために必要なコンテキストを持つ．

図では，参考のため，同等のプログラムを c 言語で実なお，GC の正しさを保証するため，SML# コー行した結果（C）も示している．この結果から分かるドを実行している間は，ユーザースレッドのコン通り，最新の SML# は従来の SML# に比べて，ほぼテキストスイッチは起こらないものとする．

同等のメモリ消費量で大幅な並列性能の向上を達成• 各ワーカースレッドはそれぞれ独立したアロケーしている．

ﬁbmandelbrot

Speed-up

40

1.5

480.5
400seq32

124816the number of workers

0.624

MaxRSS (GB)

83264

C
SML#-3.5
SML#

0.5

1656

18C
SML#-3.5
SML#average task time (sec.)

48CSML#-3.5
SML#

seq

168816243240
the number of workers

48

56

seq

124816the number of workers

32640nqueens

4840
Speed-up

816243240
the number of workers

4856

C
SML#-3.5
SML#

248

140

seq

124816the number of workers

0.6
24

MaxRSS (GB)

832

64

C
SML#-3.5
SML#

0.5

1656

0.5
08162432
40
the number of workers

0.3
0.2

seq

124816the number of workers

3264

0.4

seq

48

56

64

124816the number of workers

0.6241683264

C
SML#-3.5SML#

0.5

0.3
0.2

C
SML#-3.5
SML#

3.5
32.5
2
1.5
10.5
032

0.1064

0.4

4C
SML#-3.5
SML#

1.532032

C
SML#-3.5
SML#

064

MaxRSS (GB)average task time (sec.)

56

4816
the number of workers

cilksort
64

2.5

C
SML#-3.5
SML#

Speed-up

64

20.1
0064

average task time (sec.)

01

0.5

0.1
03
2
100.3
0.2

54

0.6
24

0.4

C
SML#-3.5
SML#

7632

MaxRSS (GB)average task time (sec.)

5664

2C
SML#-3.5SML#Speed-up

64

0.4
0.3
0.2
0.100seq124816the number of workers

図332640816243240
the number of workers

4856640seq

124816the number of workers

3264

並列ベンチマーク結果

参 考 文 献5 まとめ
大域的な同期を含まず，かつ POSIX スレッドライブ
ラリおよび軽量スレッドライブラリ MassiveThreadsと互いの独立性を保ったまま直接連携する並行並列GC の開発に成功し，SML# に実装した．本発表では，SML# が提供する並列処理機能とその基盤となる GC 方式の概要，および最新の SML# の並列処理性能の評価結果の概略を報告した．達成された枠組みと技術の詳細は，他の機会に発表する予定である．
謝辞 本研究の一部は JSPS 科研費 19K11893 および 18K11233 の助成を受けたものです．

[1] Nakashima, J. and Taura, K.: MassiveThreads:
A Thread Library for High Productivity Languages,Concurrent Objects and Beyond, Lecture Notes in
Computer Science, Vol. 8665, 2014, pp. 222–238.
[2] Ohori, A., Taura, K., and Ueno, K.: Making SML# a general-purpose high-performance language, Unpublished manuscript, 2017.
[3] SML#, http://www.riec.tohoku.ac.jp/smlsharp/,2006–2020.
[4] Ueno, K. and Ohori, A.: A Fully Concurrent
Garbage Collector for Functional Programs on Multicore Processors, Proceedings of the 21st ACM
SIGPLAN International Conference on Functional
Programming, ICFP 2016, New York, NY, USA,ACM, 2016, pp. 421–433.
[5] 上 野 雄 大, 大 堀 淳, 田 浦 健 次 朗: SML#と MassiveThreads の 統 合 に よ る 超 並 列 言 語 の 実 現, 日 本
ソフトウェア科学会第 36 回大会論文集, 2019.