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

分散メモリ環境における階層性と仕事量を考慮したワークスティール戦略
中嶋 隆介

八杉 昌宏

平石 拓

馬谷 誠二

我々はワークスティールに基づく動的負荷分散を提供する並列言語 Tascell を提案している．Tascell では小さいタ
スクの分割を防ぐために，ワーカが持つ仕事の大きさを実数値で見積もり，その値を優先度あるいは重みとして用いるスティール戦略が採用されている．本研究では分散メモリ環境における既知の問題点と既存の対応を踏まえて，ノード内に分割可能なタスクが残っている場合にも定期的にノード外へタスク要求を行う方式を Tascell に実装した．また，ワーカがサブタスクの結果待ち状態になった際のタスクの取り返しによる小さいタスクの授受を抑制するために，一定回数までは取り返しではないタスク要求を許す方式も実装した．

計算を行う．アイドル状態のワーカからの要求時にの1 はじめにみ，一時的なバックトラックにより最古のタスク生成

ワークスティールは並列化に用いる手法の 1 つで，可能状態を復元し，タスクを生成する．この手法は論

theif ワーカが victim ワーカの仕事を盗むことで効率

理スレッドの生成や管理に伴うコストの削減，作業空的な動的負荷分散を提供する．ワークスティールに間の再利用の促進，参照局所性の改善といった利点に基づく動的負荷分散を実現している並列言語として，

加え，作業空間の複製を必要になるまで遅延可能といCilk [4]，Tascell [5, 9] などがある．Cilk では，多数う特徴を持つ．

の論理スレッドを生成して最古優先のワークスティー

Tascell プログラムは起動時に接続先の Tascell サー

ルを採用することで全てのワーカを有効に活用する．

バを指定することで，サーバに接続した複数の計算

一方，論理スレッドフリーな並列言語 Tascell では，ノードを用いた分散メモリ環境での並列計算を行う

ワーカはタスク要求を受け取るまで基本的には逐次∗Work-Stealing Strategies for Distributed Memory
Environments That Consider Hierarchy and Work
Amount.
This is an unrefereed paper. Copyrights belong to
the Author(s).
Ryusuke Nakashima, 九州工業大学大学院情報工学府,
Graduate School of Computer Science and Systems
Engineering, Kyushu Institute of Technology.
Masahiro Yasugi, 九州工業大学大学院情報工学研究院,
Dept. of Computer Science and Networks, Kyushu
Institute of Technology.
Tasuku Hiraishi, 京都大学学術情報メディアセンター,
Academic Center for Computing and Media Studies, Kyoto University.
Seiji Umatani, 神奈川大学理学部情報科学科, Dept. ofInformation Sciences, Faculty of Science, Kanagawa
University.

こともできる．

Tascell では小さいタスクの分割を防ぐために，優先度選択ならびに重み付選択 [16] というスティール
戦略が提案されている．これらの戦略ではワーカが持
つ仕事の大きさを実数値で見積もり，その値を優先度
あるいは重みとして用いることで，より大きな仕事を持つワーカがタスク要求先として選択されることが期待できる．本研究では，Tascell のワークスティー
ル戦略の改善を行った．
従来の Tascell では，分散メモリ環境上でタスク要求を行う際に，まず最初に同一計算ノード内の他ワーカに対してタスクを要求し，ノード内のどのワーカもタスク要求を受け付けないときのみノード内の代表
ワーカから外部ノードへタスク要求するスティール

戦略を採用している．このスティール戦略ではノード間のタスク授受の回数を減らすことができる一方で，外部ノードに大きいタスクがある場合でもノード内のワーカへタスク要求を行うため，ノード内でタスクが細断される恐れがあるという問題があった．
また，Tascell では，ワーカがタスクの結果待ち状態になった際のタスク要求先を，結果待ちの原因となっているタスクを実行しているワーカに限定する（タスクの取り返し）という戦略も採用している．このスティール戦略にはワーカの実行スタックの肥大を抑える効果がある反面，当該ワーカ間で取り返し合いが発生し，複数のワーカ間で小さいタスクが授受されるという問題が生じる可能性がある．
これらの問題に対する解決策として，ノード内にint a [12];// manage unused pieces
int b [70];// the board, with (6+sentinel) × 10 cells// Try from the j0-th piece to the 12th piece in a[].
// The i-th piece for i<j0 is already used.
// b[k] is the first empty cell in the board.
int search ( int k , int j0 ){int s =0; // the number of solutions// iterate through unused pieces
for ( int p = j0 ; p <12; p ++) {int ap = a [ p ];for (each possible direction d of the piece) {. . . local variable definitions here . . .
if (Can the ap-th piece in the d-th direction be placed on
the board b?) ;else continue ;Set the ap-th piece onto the board b and update a.
kk = the next empty cell;if (no empty cell?) s ++;// a solution foundelse s += search ( kk , j0 +1) ; // try the next piece
Backtrack, i.e., remove the ap-th piece from b and restore a.
}}
return s ;}分割可能なタスクが存在する場合にも定期的に外部ノードへタスク要求させるスティール戦略を Tascellに実装した．さらに，取り返しにより生じる問題を緩

図1

バックトラック探索により Pentomino パズルの全解探索をするプログラム (C 言語による疑似コード)和するために，結果待ち状態の場合に一定回数までは取り返しではないタスク要求を許すという取り返し
制約緩和を適用したスティール戦略も実装した．
本論文の構成は以下の通りである． 2 章では並列言語 Tascell の概要を述べる． 3 章では従来の Tascell(1) 一時的なバックトラックを行って過去の計算状
態を復元し，(2) その時点でタスク要求があったかのようにタスクを生成し，で採用しているワークスティール戦略について説明す(3) バックトラックからもとの計算状態に戻り，る． 4 章では従来の問題点と提案するスティール戦(4) 自身が行っていた計算を再開する．

略について説明する． 5 章では性能評価の結果を示

このように最古のタスク生成可能状態までバックト

す． 6 章で関連研究を紹介し，最後に 7 章で本論文ラックすることでより大きなタスクを生成しやすくなのまとめと今後の課題を述べる．

る．また，各論理スレッドが固有の作業空間を必要とする Cilk とは異なり，Tascell では逐次計算を行って2 並列言語 Tascell

いる間は 1 つの作業空間を再利用できる．Tascell は

本 章 で は 並 列 言 語 Tasacell と そ の 実 装 に 関 しタスク要求されたときのみにタスクを生成するので，て [5, 18] に基づき説明する．

作業空間のコピーも実際に必要になったときだけ行わ
れる．

2. 1 概要
並列言語 Tascell はワークスティールに基づく動的負荷分散のための拡張 C 言語である．

Tascell では一時的なバックトラックに基づくタスクの遅延分割を行う．計算中の Tascell ワーカはタス

2. 2 Tascell 言語
図 1 は Pentomino パズルの全ての解を見つける
バックトラック探索を行う C プログラムであり，図 2
はそれを並列化した Tascell プログラムである．

クの分割が可能な点に到達しても，最初は「タスクをこの Tascell プログラムでは，pentomino というタ

生成しないこと」を選択し逐次的に計算を行う．他のスクオブジェクトの構造を定義している．フィールドワーカからタスク要求を受信すると，

k，i0，i1，i2，a，b はタスクの入力を，フィールド stask pentomino {out : int s ;// output
in : int k , i0 , i1 , i2 ;in : int a [12]; // manage unused pieces
in : int b [70]; // the board, with (6+sentinel) × 10 cells};
task_exec pentomino {this . s = search ( this .k , this . i0 , this . i1 , this . i2 , & this ) ;}worker int search ( int k , int j0 , int j1 , int j2 , task pentomino * tsk ){int s =0; // the number of solutions// parallel for construct in Tascellfor ( int p : j1 , j2 ){int ap = tsk - > a [ p ];for (each possible direction d of the piece) {. . . local variable definitions here . . .
if (Can the ap-th piece in the d-th direction be placed on the board tsk->b?) ;else continue ;dynamic_wind // construct for specifying undo/redo operations{ // do/redo operation for dynamic_wind
Set the ap-th piece onto the board tsk->b and update tsk->a.
}{ // body for dynamic_windkk = the next empty cell;if (no empty cell?) s ++; // a solution foundelse// try the next pieces += search ( kk , j0 +1 , j0 +1 , 12 , tsk ) ;}{ // undo operation for dynamic_wind
Backtrack, i.e., remove the ap-th piece from tsk->b and restore tsk->a.
} // end of dynamic_wind}}
handles pentomino ( int i1 , int i2 )// Declaration of this and setting a range (i1-i2) is done implicitly{// put part (performed before sending a task){ // put task inputs for upper half iterations
copy_piec e_in fo ( this .a , tsk - > a ) ;copy_board ( this .b , tsk - > b ) ;this . k = k ; this . i0 = j0 ; this . i1 = i1 ; this . i2 = i2 ;}// get part (performed after receiving the result){ s += this . s ; }} // end of parallel for
return s ;}図2Pentomino パズルのバックトラック探索を行う Tascell プログラム

は結果を格納するために用意されている．pentomino

る．search 関数では Tascell の並列 for 構文を用いタスクを受け取った Tascell ワーカは pentomino のて反復計算を分割する．その構文は次の通りである．

task_exec 部を実行する．
task_exec を実行中のワーカは，this キーワードfor (int identifier : exprfrom , exprto ) statbody
handles task-name (int identifier from ,によって受け取ったタスクオブジェクトを参照するこ

int identifier to )とができる．例えば，図 2 の task_exec 内ではタス{ statput statget }クオブジェクトの入力フィールドの値を引数としてタスク要求ハンドラ（statbody の実行中に有効）がワーカ関数 search を呼び出している．

呼び出されると，未処理の反復の半分にあたる計算

Tascell の並列構文を利用できるのは，キーワーが新たな task-name タスクとして生成され，そのタ

ド worker によって属性付けられた関数内に限られスクオブジェクトは statput で初期化される．statput

ク生成可能状態の復元と，その状態からの復帰を意味(2) make a copy of the board
and spawn a task

(1) backtrack(removing pieces)a task request

るピースの除去/設置のような，アプリケーション依.. ..

存の undo/redo 操作は，dynamic_wind 構文によっ
after spawning(3) return frombacktracking(setting theremoved pieces)

するということに注意されたい．Pentomino におけa board copyて指定する．

2. 3 Tascell フレームワーク
Tascell フレームワークは Tascell サーバおよび..

Tascell 言語のコンパイラにより構成されるフレーム..

ワークである．Tascell コンパイラは Tascell 言語か(4) resume

intratask
intertask

ら C 言語，あるいは拡張 C 言語である XC-cube 言
語 [12, 17] への変換器として実装されている．

図3

一時的バックトラックによるタスク生成の流れ．

コンパイルされた Tascell プログラムは 1 台以上の(1) undo しつつバックトラック (すなわち，ピース除

計算ノードで実行される．各計算ノードでは 1 つ以去)．(2) 反復の半分をタスクとして生成 (一時的に過去の上のワーカによる共有メモリ環境での並列計算が行状態に戻った盤面をコピー)．(3) redo しつつバックト

われる．

ラックから復帰 (すなわち，ピース再設置)．

Tascell サーバは計算ノード間のメッセージの中継，
ユーザインターフェースとの入出力処理，各計算ノーでは，実際に割り当てられた範囲を identifier from とドの負荷情報の管理等を行う．Tascell サーバに複数

identifier to によって参照することができる．ワーカの計算ノードを接続することにより，分散メモリ環境

は statget の実行によって生成されたタスクの結果をでの並列計算も実行できる．また，Tascell サーバに統合（マージ）する．ワーカは，タスク要求されないは計算ノードだけでなく別の Tascell サーバも接続す限り並列 for 文を逐次的に実行するため，ローカル

ることができる．

配列などの 1 つの作業空間を再利用し続けることができる．
並列 for 文はそれぞれの statbody で動的に入れ子にすることもできる．これにより，複数のタスク要求

2. 4 ワーカが保持する内部データ
Tascell ワーカは以下のスタックおよびキューを保持する．

ハンドラを同時に有効にすることができる．ワーカはtask スタック そのワーカ自身が保持するタスク

各並列 for 文のエントリポイントでポーリングによのリスト．各エントリは allocated（タスクオブるタスク要求の検出を試みる．タスク要求を検出する

ジェクト受信待ち），initialized（タスクオブジェと，一時的なバックトラックを行い，できる限り古い

クト受信済み），running（実行中），suspended

ハンドラを呼び出すことでより大きなタスクを生成（サブタスクの結果待ち），done（計算終了）なする．

どの状態をとる．

図 2 の Tascell プログラムにおいて，ワーカがタス

reqest キュー 他のワーカからのタスク要求を受

ク要求を受理したときの一時的バックトラック，タス

理し，タスク生成待ちになっているエントリのク生成，および一時的バックトラックからの復帰の流

キュー．タスクが生成されると，対応するエント

れを図 3 に示す．ここで，“バックトラック” と，リが次に述べる subtask スタックに移動する．

“バックトラックからの復帰” が，ワーカが終えた計

subtask スタック 他のワーカに送信したサブタ

算全体を undo/redo 操作することを意味するのではスクのリスト．各エントリは allocated（request

なく，最小限の undo/redo 操作によって最古のタス

キューでタスク生成待ち），initialized（タスク生成・送信済み），done（タスクの結果を受信済

ワーカがタスクを生成できる状態にない場合，そみ）の状態をとる．

のタスク要求を拒否するために送信するメッセー

task スタック，subtask スタックの各エントリに対しジである．メッセージの書式は以下の通りであて，1 つのタスクオブジェクトへの参照が対応付けさる．

れている．サブタスクに関しては，生成側の subtask

none ⟨送信先アドレス⟩

スタックと計算側の task スタック内のエントリが同

rslt メッセージ (result) タスクの計算結果を分一のタスクオブジェクトを参照する必要があり，分散

割元のワーカへ送信するためのメッセージであメモリ環境ではそれぞれのノードで別の実体とする

る．メッセージの書式は以下の通りである．

が，必要なデータはノード間通信で一致させる．

rslt ⟨送信先アドレス⟩:⟨タスク ID⟩ ⟨データ⟩⟨タスク ID⟩ には task メッセージを受け取った

2. 5 ワーカ間のメッセージ

時の整数をそのまま指定する．⟨データ⟩ はそのワーカ間でのタスク要求やタスク送信などはメッ

タスクの出力（結果）である．

セージを用いて行われる．Tascell ではノード間・ノーrack メッセージ (result ack) rslt メッセージ

ド内に関わらず共通のメッセージが用いられる．以下を受け取ったワーカがその送信元に送り返す確認に主なメッセージを示す．

メッセージである．メッセージの書式は以下の通

treq メッセージ (task request) 送信先のワー
カにタスクを要求するメッセージ．メッセージの書式は以下の通りである．

りである．

rack ⟨送信先アドレス⟩
ワーカは，送信した rslt メッセージのうち，対treq ⟨送信元アドレス⟩ ⟨送信先アドレス⟩

応する rack メッセージを受け取っていないもの

タスクの要求先がどのワーカでもよい場合，送信が 1 つでもある場合，タスクの分割を行わない

先アドレスを明示的に指定するかわりに any と（全ての treq メッセージに対して none メッセー

することもできる（any 要求）．

ジを返す）．この仕組みは取り返しの対象でない

task メッセージ 他のワーカにタスクを送信する
メッセージ．メッセージの書式は以下の通りであ仕事に由来するタスクの生成を防ぐためのもの
である．

る．

task ⟨分割回数⟩ ⟨送信元アドレス⟩:⟨タスク ID⟩⟨送信先アドレス⟩ ⟨タスク種別⟩ ⟨データ⟩⟨分割回数⟩ は，そのタスクが最初のタスクから

3 従来のワークスティール戦略
本章では従来の Tasacell で採用されているワーク
スティール戦略に関して [9, 16] に基づき説明する．

何回分割されたサブタスクであるかを示す自然数で，タスクの大きさの目安になる．この数は

3. 1 タスク要求の処理

メッセージを中継する Tascell サーバがどの計算

従来の Tascell では，タスクスタックが空になったノードに大きなタスクがあるかを見積もるため

ワーカ（thief）は以下の戦略でタスク要求先（victim）に利用することを目的としており，必ずしも必要を決定する．

なものではない．

(1) 同一計算ノード内の別のワーカを victim とし⟨タスク ID⟩ は，ワーカが生成したサブタスクて選択し，タスク要求メッセージを送信する．

に対して割り当てるユニークな整数である．

(2) ノード内にタスク生成が可能なワーカがいな⟨タスク種別⟩ は ど の タ ス ク 型 に 対 応 す る タ ス

い場合，ノード内の代表ワーカが，接続している

クかを示す番号である．⟨データ⟩ はそのタスク

Tascell サーバにタスク要求（treq）メッセージの入力である．

none メッセージ treq メッセージを受け取ったを送信する．

(3) Tascell サーバは接続されているノードの中から 1 つのノードをランダムに選択し，treq メッティールしてしまう恐れがある．

セージを転送する．このとき，– treq メッセージの送信元のノード

3. 3 優先度選択– task メッセージを送った回数と rslt メッ大きなタスクを持つワーカを要求先として選択する

セージを受け取った回数が同数のノード（タ戦略として優先度選択 [9,16] が提案されている．優先

スクが存在しないノード）

度選択はタスクの大きさを実数値で見積もり，その実は転送先ノードとして選択しない．

数値をワーカ固有の変数に設定して，ワークスティー(4) 転送された treq メッセージを受け取った計算ノードでは適当なワーカ 1 つを victim として選択し，そのメッセージを送信する．タスク生成可能なワーカがいない場合は，none メッセージがTascell サーバを再び介して thief ワーカに返される．

ル時に優先度として利用する戦略である．優先度選択
によるワークスティールは次のように動作する．

(1) thief はノード内の全 victim 候補の中から κ
ワーカをランダムに選択する．

(2) その κ ワーカの各々に設定された優先度を読み取り，最も高い優先度を持つワーカに対して
ワークスティールを行う．このとき victim がタ

3. 2 一様ランダム選択

スク生成が可能であればスティールは成功する．

初期の Tascell [5] では，3.1 節の手順 (1) および(3) thief は none メッセージを受け取った場合に(4) においてノード内で victim を選択する際ワーカ

は，ノード内の別のワーカらを一周 victim としの持つタスクの大きさなどの情報によらず無作為にて選んでいく形でタスク要求の転送を試みる．

victim を選択する「一様ランダム選択」方式を採用

優先度を参照する victim 候補の数は 1 ≤ κ ≤ n（nしていた．一様ランダム選択方式では，thief は以下

は victim 候補の数）の範囲の中から選択する．κ = nの手順でノード内から victim を決定する．

とすると，常に最高の優先度を持つワーカが victim(1) thief はランダムに選んだ victim に対して treq
メッセージを送信する．

(2) タスク要求を受け取った victim は，タスク生として選択されるようになり，κ を小さくすると，優先度を考慮しつつランダム性も持った victim の選択を行うようになる．

成が可能な場合，タスクを生成し thief へ送信する．タスクを持っていないなどの理由によりタス

3. 4 タスクの取り返し

ク生成ができない場合は拒否（none）メッセー

Tascell ワーカは，別のワーカに送信したタスクのジを thief へ送信する．

結果を受け取らないと，実行中のタスクを進められな(3) thief は none メッセージを受け取った場合にくなった場合（結果待ち状態）にも，タスク要求を行

は，手順 (1) に戻り残りのワーカへのタスク要求

う．結果待ち状態でのタスク要求では，その結果待ちを試みる．
（本研究で実際に用いている実装では，の原因となっているタスクを送信したワーカをタスク

タスク要求が victim の request キューに受理さ要求先に指定し treq メッセージを送信する．これをれない場合，thief は，ノード内の別のワーカら

タスクの取り返しという．

を一周 victim として選んでいく形でタスク要求

結果待ちの際のタスク要求を取り返しに限定するの転送を試みる．結局受理されない場合に none

ことで，タスクスタックの最大サイズ，実行スタック

メッセージを生成する．ノード外から treq メッの最大サイズそれぞれについて，「単一ワーカタスク

セージを受け取った場合もメッセージ処理スレッ

生成型実行」の場合の定数倍以下と保証できる．ここドが thief の代理として同様に処理する．
）

でいう単一ワーカタスク生成型実行では，1 ワーカの一様ランダム選択では無作為に victim ワーカを選択

みで，スティール可能なサブタスクを（Cilk などとするため，小さいタスクを持つワーカから頻繁にス同様に，両端キューに）spawn しておく（そのため，

並列 for 構文の反復を分割統治で実行する）ことに加

表1

えて，自ら実行する場合にもタスクスタック上で実行

Xeon PhiIntel Xeon E5-2697 v2 12-core × 2
64GB (shared)
Intel Xeon Phi 3120P 57-core × 4(four hardware threads per core)
6GB (for each co-processor)
Each co-processor is connected to the hostvia PCIe 3.0×16 (Bandwidth = 15.6 GB/s)
CentOS 6.5 (64bit)
Intel Compiler 13.1.3 with -O3 optimizers
Trampoline-based implementation(compatible with the GCC extension [1])Steel Bank Common Lisp 1.2.7(runs on the host processors)

するものとする．

4 ワークスティール戦略の改善

Host processor(s)Host memory
Co-processor(s)Co-processor Memory
Network

4. 1 外部ノードへのタスク要求
3. 1 節で述べた通り，従来の Tascell では同一ノード内に分割可能なタスクがない場合にのみ，ノード
内代表ワーカから外部ノードへのタスク要求を行う

OS
Compiler
ClosureTascell server

評価環境という戦略を採用している．この戦略は，ノード間のタスク授受の回数を減らすために有効であると考えが τ 未満であれば取り返しの代わりに any 要求によられる．しかし一方で，ノード内に小さなタスクしかるスティールを開始する方式を実装した．より具体的存在せず，外部ノードに大きなタスクが存在する場合には，ワーカは以下のように動作する．

に，ノード内でタスクが細断され小さなタスクが授受される恐れがあるという問題がある．

(1) ワーカは結果待ち状態になった際，カウンタの値 ct が τ 未満であれば，カウンタをインクリ

本研究では，この問題の解決策として，ノード内へメントし，取り返しの代わりに any 要求を送信の any 要求の代わりに外部ノードへ any 要求をどのする．τ であれば，従来実装における挙動と同様

ワーカも定期的に行う戦略を実装した．具体的には，に，取り返しによるタスク要求を行う．結果待ち

ワーカ固有のカウンタで any 要求を開始した回数をが解消されたときには，カウンタの値を結果待ちカウントして，カウンタの値が E に達したら，内部状態になったときの値に戻す．

ノードへの any 要求の代わりに Tascell サーバを介し(2) 取り返しの代わりの any 要求を受け取ったワーて外部ノードに any 要求を行い，カウンタの値を 0

カは，タスク生成可能であればタスクを生成し，に戻すという方式を実装した．E = 0 とすると従来自身のカウンタの値 cv と共に要求元へ送信する．

実装と同じ戦略になる．

カウンタ値は task メッセージの ⟨分割回数⟩ 部分に付加するようにした．

4. 2 取り返し制約の緩和(3) 取り返しの代わりの any 要求によりタスクを

3. 4 節で説明した結果待ち状態での取り返し制約獲得したワーカは，自身のカウンタ値 ct とタスにより，Tascell ワーカのタスクスタックのサイズのクとともに受け取ったカウンタ値 cv を比較し，上限は保証されている．しかし一方で，取り返し先の

ct < cv であれば，カウンタを cv に更新する．

ワーカが小さなタスクしか生成できなくても，別のワーカにタスク要求を出すことができないという問

5 性能評価題がある．また，取り返し先のワーカが別のワーカへ

本章では提案手法の分散メモリ環境における性能の取り返しを行うことで複数のワーカの間で小さな評価について述べる．評価環境は表 1 の通りである．

タスクが授受されるという問題も生じうる．

性能評価では，優先度選択と 4 章で説明したス

本研究では，ワーカが取り返し要求を行うべき状況

ティール戦略を組み合わせて測定を行った．また比較においても一定回数までは any 要求によるスティーのために，一様ランダム選択，優先度選択に関してもルを許容することにより，この問題の解決を試みた．

測定を行った．

具体的には，各ワーカが取り返しの代わりに any 要

評価には次のベンチマークプログラムを用いた．

求を開始した回数をカウントするためのカウンタを• Fib(n) n 番目のフィボナッチ数を再帰的に求め用意し，結果待ち状態になった際にそのカウンタの値るプログラム．優先度 w は w = n で与えられる．

• Nq(n) n 女 王 問 題 の 全 解 探 索 を バック ト ラ
w = n − (j + 1) で与えられる．ここで j は設置済みの女王駒の数である．

• Pen(n) n ピースを用いたペントミノパズル（n > 12 は追加のピースと拡張ボードを使用する）の全解探索をバックトラックを用いて行うプ
ログラム．優先度 w は w = n − j で与えられる．

140
speedup relative to serial C

ック を 用 い て 行 う プ ロ グ ラ ム ．優 先 度 w は

120
100
80
60
40
20
0

ここで j は設置済みのピースの数である．

1×114
2×114
3×114
4×114
(# of nodes) × (# of workers per node)• Cmp(n) 2 つの n 要素の配列間の全要素のペア（0 ≤ i, j < n として，(ai ,bj )）について比較演算を行うプログラム．優先度 w は w = n で与え

図4

Fib(50) の分散メモリ環境における速度向上 (逐次C プログラムに対する性能比)

られる．

• Histogram(n, NR , d) 2 以上 2 + n 未満の dセット{gcd(i1 , i2 , . . . , id ) | 2 ≤ i1 , i2 , . . . , id < 2 + n}をヒストグラムとして集計するプログラム．優先度 w は w = nd で与えられる．
プ ロ グ ラ ム の 入 力 に つ い て は ，Fib(50)，Nq(17)，Pen(15)，Cmp(150000)，Histogram(50,50,7) と し

250
speedup relative to serial C

個の自然数からなる nd 組の最大公約数のマルチ

200
150
100
50

randompriority-all
remote-10
remote-20
remote-40
relaxed-3

0

た．

1×114
2×114
3×114
4×114
(# of nodes) × (# of workers per node)

評価結果を図 4 から図 8 に示す．グラフには 22 回測定したときの第一四分位数と第三四分位数をエラー

randompriority-all
remote-10
remote-20
remote-40
relaxed-3

図5

Nq(17) の分散メモリ環境における速度向上 (逐次バーとして表示している．グラフの縦軸は逐次 C プ

C プログラムに対する性能比)

ログラムに対する性能比であり，tS /tP で計算される．
（tS は逐次 C プログラムの実行時間，tP は P ワーカ
グラフ中の凡例の詳細については以下の通り．

• random は一様ランダム選択を用いたときの速度向上を示す．

• priority-all は優先度選択（κ = P ）を用いた
ときの速度向上を示す．全 victim の中から最大の優先度を持つワーカへスティールを行う方式でspeedup relative to serial C

使用したときの Tascell プログラムの実行時間．
）

160• remote-20 は優先度選択（κ = P ）で E = 20としたときの速度向上を示す．ただし，ノード数

100
80
60
40
20

randompriority-all
remote-10
remote-20
remote-40
relaxed-3

1×114
2×114
3×114
4×114
(# of nodes) × (# of workers per node)• remote-10 は優先度選択（κ = P ）で E = 10
1 のときは E = 0 とした．

120

0

ある．

としたときの速度向上を示す．ただし，ノード数

140

図6

Pen(15) の分散メモリ環境における速度向上 (逐次C プログラムに対する性能比)

relaxed-3 については remote-20 と比較すると，

250
speedup relative to serial C

Fib(50)，Nq(17)，Cmp(15000)，Histogram(50,50,7)200では性能比に大きな変化は見られず，Pen(15) では-

150

22.5%悪化している．この評価では，remote-20 によりすでに十分な性能改善がなされていたことが原100

randompriority-all
remote-10
remote-20
remote-40
relaxed-3

50
0

1×114
2×114
3×114
4×114
(# of nodes) × (# of workers per node)
図7

Cmp(150000) の分散メモリ環境における速度向上 (逐次 C プログラムに対する性能比)

speedup relative to serial C

6 関連研究ワークスティーリングフレームワークは一般的に，
マルチスレッド言語 [3, 4, 6, 8, 10] やライブラリ [7] として実装されている．マルチスレッド言語とは異なり，Tascell [5] は論理スレッドフリーかつオンデマン
ドな並列実行を提供する．

Duran らはタスク並列向けに adaptive cut-oﬀ を250

提案している [2]．この手法では実行時にアプリケー
200

ションから収集された情報を用いてどのタスクを枝切りするか決定する [2]．Wang らは，タスクを実行中

150のワーカがアイドルな他ワーカを検出した時点から
100

randompriority-all
remote-10
remote-20
remote-40
relaxed-3

50
0

1×114
2×114
3×114
4×114
(# of nodes) × (# of workers per node)
図8

因として考えられる．

Histogram(50,50,7) の分散メモリ環境における速度向上 (逐次 C プログラムに対する性能比)

も，指定されたカットオフに応じた数の分割可能なタ
スクを生成するという手法により動的なタスク粒度調整を実現している [11]．Tascell はあらかじめ論理ス
レッド (あるいは OpenMP 用語におけるタスク) を生成しない．また，Tascell では粒度制御はスティール時に適用することができ，生成時のカットオフとは異なり，常にスティールする機会があり，仮想確率的
ガード [14, 15] や優先度および重み付選択 [9, 16] を

1 のときは E = 0 とした．
• remote-40 は優先度選択（κ = P ）で E = 40としたときの速度向上を示す．ただし，ノード数1 のときは E = 0 とした．
• relaxed-3 は優先度選択（κ = P ）で E = 20，

用いたときには，thief は victim 上の大域的な情報を利用することができる．
八杉らは、階層的計算省略に基づく並列実行モデル

HOPE [13] を提案しており、これは主に耐障害性を実現している．

τ = 3 としたときの速度向上を示す．ただし，ノード数 1 のときは E = 0 とした．

7 まとめと今後の課題

図 4 から図 8 より，remote-20 で顕著な性能向本研究では，Tascell に定期的に外部ノードへのタ上が得られていることが分かる．4 ノード × 114

スク要求を行うスティール戦略と取り返しでないタス

ワーカを用いた場合では，priority-all と比較すると

ク要求を許容するという取り返し制約を緩和したス

remote-20 は Fib(50) において 44.7%，Nq(17) におティール戦略を実装した．性能評価では，定期的に外いて 62.5%，Pen(15) において 16.5%，Cmp(150000)

部ノードへのタスク要求を行うことで性能向上が得において 73.8%，Histogram(50,50,7) において 62.4%

られることを確認した．また，取り返し制約の緩和にの性能改善が得られた．

よる性能改善は得られていないため，より多くの場合

の評価も行っていきたい．

参 考 文 献[ 1 ] Breuel, T. M.: Lexical Closures for C++, Usenix
Proceedings, C++ Conference, 1988.
[ 2 ] Duran, A., Corbalán, J., and Ayguadé, E.: An
Adaptive Cut-oﬀ for Task Parallelism, Proceedingsof the 2008 ACM/IEEE Conference on Supercomputing, SC ’08, 2008, pp. 36:1–36:11.
[ 3 ] Feeley, M.: A Message Passing Implementationof Lazy Task Creation, Proceedings of the International Workshop on Parallel Symbolic Computing: Languages, Systems, and Applications, Lecture Notes in Computer Science, No. 748, SpringerVerlag, 1993, pp. 94–107.
[ 4 ] Frigo, M., Leiserson, C. E., and Randall, K. H.:
The Implementation of the Cilk-5 Multithreaded
Language, ACM SIGPLAN Notices (PLDI ’98),
Vol. 33, No. 5(1998), pp. 212–223.
[ 5 ] Hiraishi, T., Yasugi, M., Umatani, S., andYuasa, T.: Backtracking-based Load Balancing,
Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2009), February 2009, pp. 55–
64.
[ 6 ] IBM Research: X10: Performance and Productivity at Scale. http://x10-lang.org/.
[ 7 ] Intel Corporation:
Intel Threading Building Block Reference Manual, 2007.
http://
threadingbuildingblocks.org/.
[ 8 ] Mohr, E., Kranz, D. A., and Halstead, Jr., R. H.:
Lazy Task Creation: A Technique for Increasing the
Granularity of Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, Vol. 2,
No. 3(1991), pp. 264–280.
[ 9 ] Nakashima, R., Yoritaka, H., Yasugi, M., Hiraishi, T., and Umatani, S.: Extending a WorkStealing Framework with Priorities and Weights,
Proceedings of the 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3 2019)(held in conjunction with SC 2019), November
2019, pp. 9–16.
[10] Taura, K., Tabata, K., and Yonezawa, A.:
StackThreads/MP: Integrating Futures into CallingStandards, Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Program-ming (PPoPP’99), May 1999, pp. 60–71.
[11] Wang, L., Cui, H., Duan, Y., Lu, F., Feng, X.,
and Yew, P.-C.: An Adaptive Task Creation Strategy for Work-stealing Scheduling, Proceedings of the
8th Annual IEEE/ACM International Symposiumon Code Generation and Optimization, CGO ’10,
2010, pp. 266–277.
[12] Yasugi, M., Hiraishi, T., and Yuasa, T.:
Lightweight Lexical Closures for Legitimate Execution Stack Access, Proceedings of the 15th International Conference on Compiler Construction(CC2006), Lecture Notes in Computer Science,
No. 3923, Springer-Verlag, Mar 2006, pp. 170–184.
[13] Yasugi, M., Muraoka, D., Hiraishi, T., Umatani,S., and Emoto, K.: HOPE: A Parallel Execution
Model Based on Hierarchical Omission, Proceedingsof the 48th International Conference on Parallel
Processing (ICPP 2019), August 2019, pp. 77:1–
77:11.
[14] Yoritaka, H., Matsui, K., Yasugi, M., Hiraishi,T., and Umatani, S.: Extending a Work-Stealing
Framework with Probabilistic Guards, Proceedingsof the 45th International Conference on Parallel Processing Workshops (ICPPW 2016) (Ninth
International Workshop on Parallel Programming
Models and Systems Software for High-End Computing P2S2 2016, held in conjunction with ICPP
2016), August 2016, pp. 171–180.
[15] Yoritaka, H., Matsui, K., Yasugi, M., Hiraishi,T., and Umatani, S.: Probabilistic guards: A mechanism for increasing the granularity of work-stealing
programs, Parallel Computing, Vol. 82(2019),
pp. 19–36. (Available online 22 June 2018).
[16] 寄高啓司, 八杉昌宏, 平石拓, 馬谷誠二: 優先度な
らびに重みを用いたワークスティールフレームワークの性能改善, The 1st. cross-disciplinary Workshop on
Computing Systems, Infrastructures, and Programming (xSIG 2017), April 2017. (口頭発表，ヤング・リサーチャー枠).
[17] 八杉昌宏, 平石拓, 篠原丈成, 湯淺太一: L-Closure：
高性能・高信頼プログラミング言語の実装向け言語
機構, 情報処理学会論文誌：プログラミング, Vol. 49,
No. SIG 1 (PRO 35)(2008), pp. 63–83.
[18] 平 石 拓, 河 野 卓 矢, 八 杉 昌 宏, 馬 谷 誠 二, 湯 淺 太
一: バックトラックに基づく負荷分散の高並列環境における評価, 情報処理学会研究報告 (SWoPP 2010),
Vol. 2010-HPC-126, No. 25(2010), pp. 1–11.