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

仮想環境を考慮した要求駆動型負荷分散
良本 海

八杉 昌宏

平石 拓

馬谷 誠二

並列言語 Tascell の要求駆動型負荷分散では，各ワーカは論理スレッド等を生成せずに逐次的に計算を行い，他のワーカから要求が来たときにのみ，一時的バックトラックにより最古のタスク生成可能状態を復元してタスクを生成することで，効率の良い並列処理を実現している．この方式では，ワークスティール処理の完了のために，タスクを要求するワーカだけでなく要求されるワーカも CPU 資源の利用をともなう処理を行う必要がある．そのため，仮想環境では，仮想マシンの CPU 利用率を制限すると，制限分以上に性能が低下する恐れがある．本研究では，要求されるワーカが関与せず盗めるタスクを一定数以内で準備しておくようにすることで，仮想環境での並列性能の改善を図る．

を実現している．一方，並列言語 Tascell の実装 [2]1 はじめにで用いられている要求駆動型負荷分散では，通常時，マルチコアプロセッサを搭載したコンピュータが広各ワーカは論理スレッドを生成せず逐次的に計算をく普及し，それらを用いた並列計算が一般化してい行う．他のワーカから要求がくると，一時的なバックる．それに伴い，効率と拡張性に優れた並列計算の需トラックにより最古のタスク生成可能状態を復元し，要が高まっている．また，計算資源の効率的利用のたタスクを生成し，送信する．これにより，効率の良いめに，仮想化といった技術も普及しており，仮想環境並列処理を実現している．

上での並列処理が行われるようになっている．しかし仮想環境上の並列処理では，CPU の物理コア（仮ながら，仮想環境上での並列処理では，物理コア数以想環境では単に物理 CPU と呼ばれる）数を超えて仮上の仮想 CPU が時分割多重で実現されると，並列処

想 CPU を運用する場合がある．そのような場合，物理の性能が低下する恐れがある．

理 CPU を仮想 CPU に対して時分割で割り当てるこ

並列言語 Cilk とその実装 [1] では，ワーカはそれとによって，見かけ上は仮想 CPU の数で動作する．

ぞれ多数の論理スレッドを生成し，最古優先のワー

しかし，実際には時分割で割り当てているので，いずクスティールにより良好な負荷分散を伴う並列処理

れかの仮想 CPU が休止状態となっている時間が存在∗ This is an unrefereed paper.

Copyrights belong tothe Authors.
Kai Yoshimoto, 九州工業大学大学院情報工学府, Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology.
Masahiro Yasugi, 九州工業大学大学院情報工学研究院,
Department of Artificial Intelligence, Kyushu Institute of Technology.
Tasuku Hiraishi, 京都大学学術情報メディアセンター,
Academic Center for Computing and Media Studies, Kyoto University.
Seiji Umatani, 京都大学大学院情報学研究科, Graduate
School of Informatics, Kyoto University.

する．そのような状況における Tascell を用いた並列計算では，休止中の CPU に割り当てられたワーカがタスク要求にすぐに反応できないことにより並列処理の性能が低下する恐れがある．
この問題に対処するため，本研究では Tascell 処理系の改良を行った．具体的には，各ワーカはすぐにスティールできるタスクを一定数用意しておくようにし，スティールされる側の関与なしでスティールできる機会を増やした．また，スティールされる側は，タスクが一定数用意されているかを定期的に確認し，

1int fib ( int n ) {fib(40)2if ( n <= 2) return 1;

3else {

4int s1 ;5int s2 ;6

do_two {fib(39)a task request

fib(38)fib(38)s1 = fib ( n - 1);7

s2 = fib ( n - 2);

8fib(37)} handles fib {9fib(36)

this . n = n - 2; // タスクの入力を渡す

10

s2 = this . r ;11after spawning// タスクの結果を受け取る}

12

return s1 + s2 ;1314

2. spawn a task

1. backtrack}

図1

fib(40)3. return frombacktracking

fib(39)

フィボナッチ数を求める Tascell プログラム

fib(38)fib(38)満たない場合は補給するようにした．
以下，本論文は，第 2 節で，並列言語 Tascell とそfib(37)の従来実装について述べ，第 3 節で，仮想環境上での従来実装の問題点について述べる．第 4 節で，本研究

fib(36)

intratask
intertask

4. resumeの参考となる既存実装として並列言語 Cilk の実装 [1]とその改良版である Indolent Closure Creation [3]について述べる．第 5 節で，仮想環境を考慮した提案手法を述べ，第 6 節で提案手法に基づく Tascell の

図2

Tascell における一時的バックトラックおよびタスク生成新しい実装の詳細を述べる．第 7 節で今後，評価を進めるにあたっての予定について述べる．第 8 節で変換器として実装されている．この際バックトラック関連研究について述べ，第 9 節でまとめと今後の課を最小限のオーバーヘッドで実現するため，文献 [5] [6]

題を述べる．

で提案されている L-closure や Closure に基づく低コストの入れ子関数を利用している [2]．

2 並列言語 Tascell
2. 1 概要

2. 2 Tascell におけるワークスティール

Tascell 言語 [2] は，Cilk 言語 [1] のように，ワー

Tascell のワーカは Cilk [1]（4. 1 節参照）と異なクスティールによる並列計算を実現する拡張 C 言語

り，他のワーカからワークスティールの要求（タスクである．図 1 に例として，フィボナッチ数を doubly-要求）を受け取るまでは，自身に割り当てられたタスrecursive アルゴリズムにより並列に計算する Tascell

クを逐次実行し，タスクの生成は行わない．すなわ

プログラムを示す．プログラム中にタスクを生成可能

ち，タスク生成が可能な箇所（do_two など）に到達な箇所（たとえば図 1 の do_two）や，タスク（およしてもその場ではタスク生成を行わず，完全な逐次実びその結果）を他ワーカに与える（から受け取る）た行を選択したかのように計算を続ける．

めの処理（図 1 の handles fib ブロック）を記述しワーカ（victim）が計算中に他ワーカ（thief）からておくと，必要なタスク生成やそのワーカへの割り当

タスク要求を受け取ると，タスク生成が可能であったてが実行時に行われる．

箇所のうち最古のもの，すなわち最大のタスクが生成

Tascell コンパイラは，Tascell 言語から C 言語へのできると期待できる箇所の実行状態を一時的バックトラックにより復元し，過去の選択を変更したかのよに），treq を再送信する．

うにタスクを生成する．victim ワーカはタスクの生タスクの実行を完了したワーカは，そのタスクの成後，一時的バックトラック前の実行状態を再度復元

結果を rslt メッセージとして victim ワーカに返信し，自身の計算を再開する．このタスク生成の一連のする．rslt を受け取ったワーカはサブタスクスタッ

流れを図 2 に示す．

クの対応するアイテムに結果を書き込んでおく．書き込まれた結果の取り込み（図 1 の s2=this.r の処理

2. 3 ワークスティールの従来実装等）やサブタスクスタックの pop は，victim の計算

本節では従来の Tascell のワークスティールの実装

実行がそのタスクを生成した位置（do_two など）まについて説明する．

で戻ってきたときに処理される．

各ワーカは，自身が実行すべきタスクの情報を格

なお，実装上は，各メッセージの送受信が共有メモ納するタスクスタックと，他ワーカから受け取ったタリ環境内で行われる場合には，直接的なメッセージスク要求情報を格納するリクエストキュー，および他のやりとりがワーカ間で行われているわけではなく，ワーカに送信したタスクを管理するサブタスクスタッ

送信元ワーカ用スレッドが，受信先ワーカの代理とクを持つ．

なり，受信先ワーカのデータを直接書き換えることでワーカは，自身のタスクスタックが空ではなく，かメッセージ送信処理を（受信先ワーカ用スレッドとつその top にあるタスクが実行可能であればそのタ相互排他しつつ）実現している．たとえば，treq のスクを実行する．一方，スタックが空になるか，top送信処理では，受信先（victim）ワーカのリクエストにあるタスクが他のタスクの結果の待ち合わせなどにキューへのアイテムの追加を，rslt の送信処理ではより実行できなくなると，そのワーカは thief として受信先（victim）ワーカのサブタスクキューのアイテ（適切な戦略により）他のワーカから 1 つを victim として選択し †1 ，タスク要求メッセージ（treq）を出ムへのタスクの結果の書き込みを送信元スレッドが直す．treq を受け取ったワーカは，その情報をリクエで，これらのメッセージを受けてのタスク生成・送信ストキューに追加する．

処理あるいはタスクの結果の取り込み処理について各ワーカはタスクの実行中，ポーリングによりリク接行うことで，メッセージ処理を実現している．一方は，受信先ワーカ用スレッドが実行する．

エストキューにタスク要求が届いていないかを確認す

上記のように，送信元ワーカ用スレッドが受信先る．要求が届いていれば，その各アイテムに対して以ワーカの代理となって振る舞うときは，送信元ワー下の処理を行った後，キューから取り除く．

カがそのまま動作しているとみなすことも可能であ• 自身がタスク送信可能であるかを確認し，もしり，受信先ワーカの（相互排他以外の）関与なしに，可能であれば前述の一時的バックトラック処理

キューへの追加や結果の書き込みを行っているとみなによりタスクを生成し，task メッセージとしてすこともできる．以後，受信先ワーカの関与という点

thief に返信する．また，そのタスクに対応するについて考える場合は，送信元ワーカがそのまま動作アイテムをサブタスクスタックに push する．

しているとみなすこととする．

• タスク送信が不可能であれば，その旨を伝えるメッセージ（none）を thief に返信する．

3 仮想環境上での並列処理

none を受け取った thief ワーカは，別のワーカを選

第 1 節で述べたように，仮想環境上の並列処理で択し（場合によってはしばらく待機して同じワーカは，物理 CPU 数を超えて仮想 CPU を運用する場合がある．例えば，別のホストにマイグレーションする†1 結果の待ち合わせの際には，その結果を計算するタス
クをスティールしたワーカを victim として選択する
ことでスタックサイズを逐次計算の定数倍以下とすることが可能である [4]．

場合や，1 つのホストで複数の仮想マシンを運用するために物理 CPU 数以上の仮想 CPU が必要となる場合などが考えられる．

物理 CPU を仮想 CPU に対して時分割で割り当てることによって，見かけ上は仮想 CPU の数で動作するが，いずれかの仮想 CPU が休止状態となっている

1

cilk int fib ( int n ) {2if ( n <= 2) return 1;

3else {

時間が存在する．そのような状況における Tascell を4用いた並列計算では，休止中の CPU に割り当てられ5int s2 ;6s1 = spawn fib ( n - 1);

7s2 = spawn fib ( n - 2);

8sync ;たワーカがタスク要求にすぐに反応できないことにより並列処理の性能が低下する恐れがある．
第 2 節で述べた Tascell の実装では，treq の送信元ワーカがリクエストキューへのアイテムの追加まで

int s1 ;return s1 + s2 ;

9}

1011}

は，受信先ワーカの関与なしで行うことができるが，タスク生成・送信処理は受信先ワーカが行う必要があ

図3

フィボナッチ数を求める Cilk プログラム

る．受信先ワーカは仕事をしながら定期的にリスクエストを確認しているが，休止中はリクエストの確認もログラムの簡単な例として，フィボナッチ数を求めるできない．

プログラムを並列化したものを図 3 に示す．

これにより並列処理性能がどの程度低下するかはCilk の標準的な実装 [1] では，各ワーカは，固有の仮想環境に依存する．特に，送信元となる仮想 CPUランタイムスタック，および，実行可能な手続き（論で OS レベルのスリープが行われたときに，仮想マシ理スレッド）の両端キュー（ready deque）を持つ．各ンモニタレベルでも受信先となる仮想 CPU へと物理

ワーカは，両端キューの末尾側で要素を push またはCPU が割り当て直されるような仮想環境であれば性pop することができ，他のワーカも先頭側（末尾の反能低下は少なくて済む可能性がある．また，その切り対側のもう片方の端）から要素を取り出すことができ替えコストも性能に影響すると考えられる．

る．ワークスティールは，アイドル状態となったワー

また，実際に行われるスティール試行の回数も，どカが thief (盗む側) となり，ランダムに victim (盗まの程度の並列性能低下となるかに関係すると考えられる側) として選ばれたワーカ（の ready deque の先れる．ワークスティールは特に並列計算全体の終盤で頭側）から，論理スレッドを盗んで実行する形で行わ多く行われるが，この期間の負荷分散がうまくいかなれる．

いことで全体が終了するまでの時間が延びることも，各 cilk 手続きは，fast clone と slow clone の 2

逆に，仕事をもつワーカがワークスティールされずにバージョンのコード（手続き）へとコンパイルされ終了できることで全体が終了するまでの時間が短縮

る．各ワーカは spawn キーワードのついた手続き呼されることも考えられる．

び出しを実行すると，新しい論理スレッドでその手続きを実行する．

4 既存手法新しい論理スレッドで手続きを実行するには，単

本節では，本研究の提案手法の参考となる既存実装に fast clone を通常の手続きと同様に呼び出す．fastとして並列言語 Cilk の実装 [1] とその改良版である

clone 開始時には，ワークスティールが可能なように，Indolent Closure Creation [3] について述べる．

論理スレッドの局所変数の値などを保存するフレームをヒープ割り当てし，意味的には slow clone のコー

4. 1 マルチスレッド言語 Cilk の実装

ドと合わせてクロージャとして生成する．このクロー

Cilk 言語 [1] は，C 言語を拡張して作られた並列言ジャが論理スレッド（の継続）に相当する．

語である．Cilk の特徴は，spawn と sync キーワード

論理スレッド tp（parent）が，新しい論理スレッドを使用して並列化可能な箇所を指定し，実際の並列化tc （child）を spawn するときには，（tc ではなく）tpは処理系が自動で行う点にある．Cilk による並列プの継続（クロージャ）が，両端キュー（ready deque）の末尾に push される．これは，ワーカとしては新しイする．

い論理スレッド tc の実行を開始するため，1 つ古いTHE プロトコルは一見すると，単に変数を読み書

論理スレッド tp は新たにスティール対象となったときしているだけだが，読み出しアクセス，書き込みア考えればよい．

クセスはそれぞれ不可分である必要がある．加えて，末尾に push された論理スレッド tp は，他のワー書き込みアクセス後に，H > T でないことの確認のたカから盗まれる対象となる．論理スレッド tc を実行

めの読み出しアクセスを行うが，現代的な計算機ではしている間に，tp が他のワーカによって盗まれるこ

その間に（プログラム通りに書き込み後に読み出しととがなかった場合には，tc のための呼び出しの完了いう順序となるように）メモリバリア命令を必要とす

後，tp の継続を push したワーカによって両端キューる．現代的な計算機では，メモリバリア命令は比較的（ready deque）の末尾から tp の継続は pop される．

重いため，ある程度のオーバヘッドとなる．Tascell

その後，tp の実行再開（継続の実行）は pop されたが Cilk よりも高い性能を示すのは，スティールが起クロージャではなく，fast clone の実行として行う．

きない限り，このオーバヘッドを不要としている点が子の論理スレッド tc が終了するまでの間に，親で大きい [2]．

ある tp（の継続）が他のワーカによって盗まれていた
場合は，tc のための呼び出しの完了後に，tp は fast

4. 2 Indolent Closure Creation

clone として実行は本格的に再開せず，直ぐに中止

Indolent Closure Creation [3] は，Cilk 言語の別する．の実装として位置付けられる．その名の通り，そのアイドル状態となったワーカが thief (盗む側) とな

基本的なアイディアは 4. 1 節で述べた Cilk 言語の標り，ランダムに victim (盗まれる側) として選ばれた

準的な実装におけるクロージャ（論理的スレッドの継ワーカ（の ready deque の先頭側）から，論理スレッ続）の生成（と両端キューへの push）を本当に必要ド（の継続）をクロージャとして盗んだ場合，その再になるまで遅延させるというものである．

開はクロージャに含まれる show clone を実行することで行われる．

Indolent Closure Creation では，Tascell と同様にvictim 側でポーリングを用いる．スティール試行が両端キュー（ready deque）の末尾側からの victim

空の両端キュー（ready deque）に対して発生してスによる pop と，両端キュー（ready deque）の先頭側ティールに成功しなかったということをポーリングからの thief によるスティールでは，要素を重複してで調べる．成功しなかったスティール試行を検出する取り出さないようする必要がある．この実現のためと，ランタイムスタックを用いて手続き呼出しとしてに，Cilk の標準的な実装 [1] において THE プロトコ

実行中のすべての論理スレッド（のうちクロージャ未ルが提案されている．ここでは，各ワーカの持つ変数生成のもの）に関してクロージャ生成（と両端キューT，H がそれぞれ deque の末尾（tail）と先頭（head）への push）を行う．

を表すようにして用いる．また，E は例外のために用いるがここでは説明を省略する．victim は T を変化

5 提案手法させて push や pop を行い，thief は H を変化させて前述（第 3 節）の問題を回避するため，Tascell にスティールを行う．push は T を 1 増やして次の場所おけるワークスティールの新たな手法を提案する．従を使い，pop は T を 1 減らす．スティールは H を 1

来の Tascell ではタスクの受渡しの際に，要求元ワー増やし，反対側から要素を取り出す．THE プロトコ

カと要求先ワーカの双方の CPU 資源の利用が必要に

ルでは，この際，取り出した直後に互いの H と T をなる．よって，要求先ワーカが仮想環境の CPU スケ

読み，H > T でなければ，取り出しが成功したことがジューリングにより停止している場合には，要求元わかるというものである．最初の取り出しの試行が成ワーカも動作がストップしてしまうという問題があっ功しなかったときには，ロックを獲得してからリトラた．これに対し本研究では，一方の CPU 資源の利用

だけで受渡しのできるタスクを用意することで対処の詳細を述べる．

する．具体的には，4. 1 節で述べた Cilk 言語の標準的な実装と同様に，各ワーカが両端キューを持ち，そ6. 1 データ構造

こに要求元ワーカの動作のみで獲得できるタスクを各ワーカに対して，サブタスクを要素する両端蓄えられるようにする．要求元ワーカが treq を代理キューを配列として追加した．従来実装のサブタスク処理するという見方をすると，両端キューからサブタスタックも残しており，各サブタスクは配列またはサスクを取り出して自身に task メッセージとしてタスブタスクスタックからアクセスできる．

ク送信するところまで（あるいは none メッセージ送信まで）代理で行ってしまうともいえる．

両端キューの末尾 (tail) と先頭 (head) を表す 0 以
上の整数はそれぞれ 16 ビット幅とし，32 ビット符

もちろん，タスクを常に生成したのでは，タスク生号なし整数の上位 16 ビット（tail），下位 16 ビット

成にかかるオーバーヘッドを含め，従来の，必要に応（head）として，これを保持するワーカ毎の 32 ビッ

じてタスクを生成することによる効率の良さが損な

トの変数 ltq_th（初期値 0）を用いることとした．こわれてしまう．そこで，各ワーカはすぐにスティールうすることで，compare and swap (CAS) を利用しできるタスクを一定数（例えば 3 個）用意しておくよて，両者を一度に，また両者が特定の値のときのみ不うにし，スティールされる側の関与なしでスティール可分に更新することができ，両端キューの実装をシンできる機会を増やす．また，スティールされる側は，プルにすることができる．Cilk の実装のように，各タスクが一定数用意されているかを定期的に確認し，ワーカに変数 T と変数 H を持たせて，読み書きとメ満たない場合はその分のタスクを生成して補給する

モリバリアを用いることも考えられるが，仮想環境こととする．

を考慮した Tascell の実装でも，victim ワーカは変数あるワーカが生成済みのタスクの結果の待ち合わせ

ltq_th を定期的に読んでタスク補給の判断をする際を行う際，従来の Tascell であれば，結果が有れば受には CAS は不要であり，また，現代的な計算機ではけ取り，無ければそのワーカは thief となって victim

メモリバリアも CAS とどちらも重いという点で大差からタスクをスティールして実行しようとする．一はない．

方，提案手法では，あるタスクの結果を待ち合わせた

push は head が変わらないまま tail をインクリメい場合，そのタスクが両端キューに残ったまま盗まれント，pop は head が変わらないまま tail をデクリメていないことがあるので，その場合はそのワーカが自ント，head からのサブタスクのスティールも tail が分で pop してこれを実行する．

変わらないまま head のインクリメント，によりで実提案方式は，タスクの生成を必要最小限にしようという考えに近いという点で，4. 2 節の Indolent Clo-現できる．pop の際にはサブタスクをフリーリストに返却するようにする．

sure Creation と似ている点もあるが，生成可能なタ両端キューを実現するための配列は，同時にスティースクすべてではなく，一定数を目標にタスクを生成しルされたサブタスクも保持することとした．これはて補給する点，空の両端キューとなる前から補給する

head の値をそのまま用いて，0 以上 head 未満のサブ点（スティール試行の時点で補給が完了していて，スタスクが該当する．この部分は結果待ちに使うことティールが victim ワーカの関与なしに成功すると期になる．なお，両端キューとしては head 以上 tail 未待できる点），などが Indolent Closure Creation と満である．サブタスクスタックには「両端キューに含異なる．

まれるスティールされていないサブタスク列」と「スティールされたサブタスク列」が隣接して積まれた形

6 仮想環境を考慮した Tascell の実装となる．

本節では，第 5 節で述べた提案手法に基づき，第 2

各サブタスクには，従来のステータスに加えて，拡節で述べた Tascell の従来実装を改良した新しい実装張ステータスを持たせることにした．ここには，(1)結果が存在するか，(2) 相互排他を本格的に行うべき処理されているようであるが結果がない．の 3 通り

か，(3) 結果待ちの間にタスクをスティールしてきての場合がある．仮想環境向け実装では，(1) が新たに実行しようとしているか，(4) スティールされたのち加わっている．(1) の場合は，両端キューからサブタ初期化済みか（タスク返答先など），を表す各 1 ビッスクを自身で pop し，自身で実行する．一方，(2) かトのフラグを設けた．特に (1) と (3) を不可分に確(3) かの場合，その判断の前にそのサブタスクが初期認・更新するため，ここでも CAS を用いる．

化されるまで待つ．これは，thief はスティールに成功してからタスク返答先などを書き込んでいるため

6. 2 thief ワーカの動作である．仮想環境向けの実装でありながら，この部分タスクの要求元は treq メッセージを代理処理するはビジーループで「スティールされたのち初期化済みこととして，リクエストキューは使わず，victim の両（タスク返答先など）」フラグが立つのを待っているた

端キューの先頭 (head) を，末尾 (tail) を変えずに 1

め，簡単ではないが，今後，ビジーループを使わない増やせるかを CAS により試みる．成功した場合，そ形に修正することが望ましい．(2) の場合は，結果をの位置のサブタスクを初期化し，その後自身に task取り出すとともに，スティールされたサブタスクをサメッセージを返す．タスク本体を管理するタスクをブタスクスタックから pop する．また，head と tail

生成してタスクスタックに push して，タスク本体を共に 1 減らし，両端キューは空のまま，配列の 0の処理を開始する．
（タスク本体の処理中は相対的に以上 head 未満のサブタスクを一つ減らす．(3) の場

victim となることがある．
）タスク本体の処理を完了

合は，victim ワーカが，結果を待つ間は相対的にはしたら，そのタスクの結果を rslt メッセージとしてthief となり，そのサブタスクをスティールしたワー

victim ワーカに返信する．victim の代理として，該カが victim となるようなスティールを行って，その当するサブタスクの拡張ステータスを「結果が存在すスティールしたタスクを実行する．スティール試行る」に変更する．結果待ちの間にタスクをスティール

中に，結果（rslt メッセージ）を受け取った場合は，してきて実行しようとしていなかった場合は，rsltスティール失敗後に rslt メッセージに対する ACKメッセージに対する ACK メッセージを自身に返す．

メッセージを自身に返す．

6. 3 victim ワーカの動作

7 性能評価に向けて

victim ワーカは，自身の両端キューに一定数のタ

仮想環境における並列処理の性能評価については高スクがない場合は，従来の実装でリクエストキューの山，光来らの研究 [8] がある．仮想環境の設定として，treq を検知するときと同じように，これをポーリン(1)VM 間での物理 CPU の共有，(2)VM が利用できグで検知し，一時的バックトラックを行ってサブタスる CPU 使用率を制限，(3)VM への物理 CPU 割りクを生成し，両端キューに補給（push）する．また，当てを削減，を試し，特に (2) で Tascell でも並列性サブタスクスタックにも push する．

能の顕著な低下が報告されている．仮に，本研究で課

victim ワーカは，thief ワーカのスティールに協力題とした，時分割により休止状態の仮想 CPU がある（関与）する必要はない．ただし，上記の補給（push）

ことにその原因があれば，提案実装の効果が現れる可時には CAS を用いて不可分に head を変えずに tail能性があると期待される．

を増やすようにする．

victim ワーカが過去に生成したサブタスクの結果

また，両端キューを最初から用いている Cilk との性能比較も進めるのが望ましい．

が必要になるとき，(1) そのサブタスクはスティールされていない．
（両端キューからわかる）(2) そのサブ

8 関連研究タスクはスティールされていて処理されていて結果マルチスレッド言語 OPA とその実装 [7] も，In-もある．(3) そのサブタスクはスティールされていてdolent Closure Creation と同様にポーリングを用いている．OPA の実装では，victim がスティールの要求をポーリングで検出して，両端キューにスレッドがあれば，thief へ送り出す．また，両端キューにスいきたい．
謝辞 本研究の一部は，JSPS 科研費 JP17K00099，

JP26280023 の助成を受けて行ったものです．

レッドなければ，高速に動作するためにランタイムスタックに確保していたフレームを，ヒープに確保しな

参 考 文 献おしたフレームに変換し，スティール可能とする．ま[1] 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.
[2] Hiraishi, T., Yasugi, M., Umatani, S., and Yuasa,
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.
[3] Strumpen, V.: Indolent Closure Creation, Technical Report MIT-LCS-TM-580, MIT, June 1998.
[4] Wagner, D. B. and Calder, B. G.: Leapfrogging:
A Portable Technique for Implementing Eﬃcient
Futures, Proceedings of Principles and Practice ofParallel Programming (PPoPP’93), 1993, pp. 208–217.
[5] 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, March 2006, pp. 170–184.
[6] 八杉昌宏, 平石拓, 篠原丈成, 湯淺太一: L-Closure：高性能・高信頼プログラミング言語の実装向け言語機構, 情報処理学会論文誌：プログラミング, Vol. 49, No. SIG 1(PRO 35)(2008), pp. 63–83.
[7] 馬谷誠二, 八杉昌宏, 小宮常康, 湯淺太一: オブジェ
クト指向並列言語 OPA のための遅延正規化手法, 情報処理学会論文誌：プログラミング, Vol. 45, No. SIG 5(PRO 21)(2004), pp. 12–25.
[8] 高山都旬子, 光来健一: VM が利用可能な CPU 数の変化に対応した並列アプリケーション実行の最適化, 日本
ソフトウェア科学会第 33 回大会講演論文集, September
2016.

た，ヒープに確保したフレームにを用いて実行を再開するときは 1 フレームずつ行うため，スタック全体を再構築する Indolent Closure Creation よりも素早く再開できる．OPA の実装では，全体的にポーリングを用いているため，Tascell と同様に要求元ワーカが，要求先ワーカに待たされる恐れがある．この問題に対処するには，thief が直接，victim のスレッドをスティールできればよく，これは既存の両端キューを用いて比較的容易に対応可能と考えられる．

9 まとめ
本研究では，並列言語 Tascell の要求駆動型負荷分
散では，ワークスティール処理の完了のために，タスクを要求するワーカだけでなく要求されるワーカもCPU 資源の利用をともなう処理を行う必要がある点に着目した．仮想環境では，仮想マシンの CPU 利用率を制限すると，制限分以上に性能が低下する恐れがある．
本研究では，仮想環境向けの Tascell の実装として，要求されるワーカが関与せず盗めるタスクを一定数以内で準備しておくようにする方法を提案した．
今後は，評価を行い，提案手法の有効性を確かめて