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

実環境向け並列言語実装技法の仮想環境における有効性の調査
與田 拓磨

八杉 昌宏

平石 拓

光来 健一

並列言語ならびにその処理系は，並列環境において効率良い並列計算を実現するために重要な役割を果たす．並列言語には，Cilk 言語，Tascell 言語，HOPE 言語などがあり，その処理系では，ワークスティールによる実行時負荷分散（Cilk，Tascell）や，階層的計算省略による耐障害性（HOPE）が実現されている．様々な並列言語実装技法があり，1 つの選択肢としてビジーウェイトがある．これは，Tascell のワークスティールの仕事待ちに用いた場合の有効性が実環境において確認されている．近年は仮想環境における効率良い並列計算も必要であり，本研究では上記のような実環境向けの高速化手法が仮想環境ではどのような効果を持つかについて調査を行う．仮想環境における実験では，仮想化ソフトウェアとして Xen を用いる．

ク返信待ちに用いた．結果として実環境でのビジー

1 はじめにウェイトの有効性が確認されている．

並列言語には Cilk 言語 [3]，Tascell 言語 [4]，HOPE

近年は仮想環境における効率の良い並列計算も重言語 [6] などがあり，その処理系では，ワークスティー

要であるが，仮想環境上では実環境向け高速化手法がルによる実行時負荷分散（Cilk，Tascell）や，階層

実環境とは異なる効果をもたらす可能性がある．

的計算省略による耐障害性（HOPE）が実現されている．
従来の Tascell では，ワークスティール時のタスク

本研究では実環境向け高速化手法の 1 つであるビ
ジーウェイトが仮想環境ではどのような効果を持つかについて調査を行う．

要求後のタスク返信待ちにおいて一時的にブロック状

本論文の構成は以下の通りである．第 2 章では本態としている．そのためタスクの返信が来た場合すぐ研究で対象とする並列言語である Tascell の概要を説に処理へと移行できない場合があり，並列計算の性能明する．第 3 章では Tascell におけるワークスティーが低下する場合がある．そこで，並列言語実装技法のルの概要を説明した後，タスク返信待ちの，条件変1 つであるビジーウェイトをワークスティールのタス数を用いる既存の実装手法とビジーウェイトを用い∗ Investigating How Virtual Environments Aﬀect theEﬀectiveness of Pallarel Language Implementation
Techniques for Real Environments.
This is an unrefereed paper. Copyrights belong to
the Author(s).
Takuma Yoda, 九州工業大学大学院情報工学府, Graduate
School of Computer Science and Systems Engineering, Kyushu Institute of Technology.
Masahiro Yasugi, Kenichi Kourai, 九州工業大学大学
院情報工学研究院, Dept. of Computer Science andNetworks, Kyushu Institute of Technology..
Tasuku Hiraishi, 京都大学学術情報メディアセンター,
Academic Center for Computing and Media Studies, Kyoto University.

る手法の違いを述べる．第 4 章では実環境での評価を行う．第 5 章では仮想環境の概要と本研究の仮想環境の構築方法について述べる．第 6 章では仮想環
境での評価を行う．第 7 章では PAUSE 命令を利用した場合について，仮想環境上で効果が期待できる

PAUSE-Loop Exiting を考慮した評価を行う．第 8
章では関連研究の紹介を行う．第 9 章では今後の課題について述べる．

3. 2 条件変数による返信待ちの実装

2 並列言語 Tascell

タスク要求を送信した thief ワーカは，その返信

Tascell の概要について，文献 [4] [7] に基づいて述が返ってくるまで待機する必要があるが，従来の実べる．Tascell はワークスティールにより並列計算を

装ではこの待機を条件変数を用いて実現していた．

実現している拡張 C 言語である．素朴な並列化の方

すなわち，ワーカに対応する OS スレッドはタスク

法としては，各ワーカがその時々の状態に基づいてタ

要求メッセージを送信した後，pthread_cond_wait

スク生成するかどうかを判断することが考えられる．

に よ り ブ ロック 状 態 と な る ．タ ス ク 要 求 に 対 すすなわち，各ワーカが最外ループのすべての反復をる返信が届くと，pthread_cond_signal あるいは自分で計算するか反復の一部をタスクとして生成す

pthread_cond_broadcast によりこのワーカスレッ

るかを，何らかの基準（タスクワーカが存在するときドを再開させる．

のみタスクを生成する，など）で判断する．効率の良

この方式では，返信待ちのワーカにより計算資源がい負荷分散のためには，各ワーカは計算の初期段階

浪費されることがない一方，ブロック状態への移行やで適切な数のタスクを生成しておき，その後はずっとブロックの解除に時間を要してしまうという問題点が（計算終盤の微調整を除き）生成を行わないような判ある．

断基準が最善である．

Tascell では一時的バックトラックを行うことで，タ3. 3 ビジーウェイトによる返信待ちの実装

スクの遅延分割を行なっている．すなわち，ワーカは，

ビジーウェイトとは共有メモリに同期用の変数を設

常に最初は「タスクを生成しない」ことを選択する

けて，そのフラグの状態を繰り返し確認することにが，他のワーカからタスク要求を受けると，過去の選より同期待ちを実現するという並列処理における実択を変更したかのようにタスクを生成する．Cilk [3]装技法の 1 つである．条件変数を用いる代わりにビにおける LTC と呼ばれる手法に対して，論理スレッ

ジーウェイトでタスク要求に対する返信待ちを行うよ

ドを一切生成しないので，タスクキュー管理コストがうにすることで，ワーカスレッドは返信待ちの際に計発生しないなどの優位点を持つ．

算資源を消費するようになる一方，タスク要求に対する返信を受け取った後に処理を再開するまでの時間を

3 Tascell の実環境向け高速化手法
3. 1 Tascell のワークスティール

短縮できることが期待できる．
実装には図 1 に示す pthread_cond_busywait マ

Tascell のワークスティールについて [4] をもとに説クロを使用した．このマクロはロック PMUT を解放し明する．Tascell ワーカは自身のタスクスタックが空た状態で式 EXP が偽になるまで繰り返し評価し，偽になると，thief ワーカとしてタスクを実行中のワーになれば PMUT を再び獲得するという処理を行うもの

カ（victim）にタスク要求メッセージを送信する．要である．

求を受けたワーカは一時的バックトラックにより最古

このマクロを用いたビジーウェイトによるタスのタスク生成可能状態を復元した後，タスクを生成

ク 返 信 待 ち の 処 理 の コ ー ド を 図 2 に 示 す．な お ，して thief ワーカに送信する．Tascell では一時的バッ

こ の コ ー ド は 説 明 の た め に 一 部 簡 略 化 し て あ り，

クトラックによって，より仕事量の多いタスクを生

また，比較のために条件変数を用いた処理コード

成して渡すことができる．タスクを受け取った thiefも図に示している（#ifdef ディレクティブの#else

ワーカはそのタスクを実行し，結果を victim ワーカ

節 ）．ビ ジ ー ウェイ ト を 用 い た 実 装 で は ，ワ ー カに返信する．

ス レッド は pthread_cond_wait を 呼 ぶ 代 わ り に ，pthread_cond_busywait を用いてビジーウェイトを継続するための条件式の値を繰り返し評価する．ここで，volatile 型修飾子を持つ型への型キャストを

表1# define p t h r e a d _ c o n d _ b u s y w a i t ( EXP , PMUT ) \do {並列実行環境（実環境）Linux PC Server\

p t h r e a d _ m u t e x _ u n l o c k (( PMUT ));\OS

Ubuntu 16.04.3 LTS 64bit

while (( EXP ));\CPUIntel Xeon E5-2630 v3 2.40GHz 8 コア × 2

pt h re a d_ m ut e x_ l oc k (( PMUT ));

\

メモリ

64GB

コンパイラ

Tascell コンパイラ，GCC 5.4.0

ハイパースレッディング

無効} while (0)図1pthread-cond-busywait マクロn × n の行列の LU 分解を cache-oblivious な再帰ア
用いることで，コンパイラの最適化による条件式の繰ルゴリズムで計算する（lu(n)），n ピースのペントミ

り返し評価の省略や実行順序の入れ替えを防いでいノパズル（n > 12 は追加のピースと拡張ボードを使ることに注意する．

用する）の全解探索を行う（pen(n)），2 つの n 要素

pthread_cond_busywait 内での条件式の評価はの配列間の全要素ペア（(ai , bj ) for all 0 ≤ i, j < n）

ロック thr->mut を解放した状態で行っているため，について比較演算を実行するプログラム（cmp(n)），

pthread_cond_busywait を抜けたとしても，最後(2n + 1)3 個の同一質量の質点からある点にかかる総の評価の後に条件式の真偽が変化している可能性を排除できない †1 ．そのため，ワーカスレッドは引力を計算するプログラム（grav(n)）を用い，上記

pthread_cond_busywait を抜けた後 while ループ

時間を調べることにより評価を行った．

プログラムを実環境上 16 ワーカで実行し，その実行の先頭に戻り，thr->mut を再獲得した状態で条件式の値を再確認するようにしている．

4. 2 評価結果

なお，図 2 中の thr->sub は，ワーカが他のワーカ

実環境上での評価結果を図 3 に示す．アプリケーに送信して結果待ち状態になっているタスクの存在のションを 22 回実行し，その中央値で評価を行った．

有無を示している．そのようなタスクが存在する場合，それぞれのアプリケーションで pthread_cond_wait

タスク要求を送信したワーカは，その要求に対する返信（ビジーウェイト無し）の結果を 1 として busywaitがあったとき（tx->stat が TASK_ALLOCATED 以外に（ビジーウェイト有り）の比率を求め，棒グラフとしなったとき）だけでなく，結果待ちのタスクの結果を受て表している．各棒グラフの上部に実際の実行時間け取ったとき（thr->sub->stat が TASK_HOME_DONE[秒] を表記している． 全てのアプリケーションでビになったとき）にも返信待ちを抜けることになってジーウェイトを適用した方が実行時間が短くなり，特いる．

に fib(44) にて 1.9%程度，lu(4000) にて 4.2%程度実
行時間が短縮された．

4 実環境での効果

ここまで並列言語実装技法のひとつであるビジー

4. 1 評価方法

ウェイトの実環境上での Tascell ワークスティールに

並列言語実装技法の 1 つであるビジーウェイトをおける有効性を示した．

Tascell のワークスティールのタスク返信待ちに適用した場合の実環境上での効果を評価する．実環境とし5 仮想環境て用いた並列実行環境を表 1 に示す．

5. 1 概要

ベンチマークプログラムには文献 [8] と同様の，n仮想環境における仮想マシン（VM）では，CPU番目のフィボナッチ数を再帰的に計算する（fib(n)） ，は物理的な CPU コア（物理 CPU）を仮想化した仮想的な CPU（仮想 CPU）として提供されている．1†1 条件式の評価による確認がデータレースとなっているのも意図的である．ここで，データレースの影響は条件式の真偽値にのみ現れると仮定している．

台の実環境マシンに対して 1 台の仮想マシンであれ
ば，仮想 CPU 1 つにつき 1 つの物理 CPU が割り当

while (1) {if ( thr - > sub ) {if (!( tx - > stat == TA SK_ALLOCATED && thr - > sub - > stat != TASK_ HOME_DONE ))break ; // 返信到着確認（または到着待ちの必要がなくなった）} else {if (!( tx - > stat == TA SK_ALLOCATED )) {break ; // 返信到着確認}}# ifdef BUSYWAIT/* ビジーウェイトを用いる実装 */if ( thr - > sub ) {p t h r e a d _ c o n d _ b u s y w a i t (*( volatile enum task_stat *) (& tx - > stat ) == TASK_ALLOCATED&& *( volatile enum task_home_stat *) (& thr - > sub - > stat ) != TASK_HOME_DONE ,& thr - > mut );} else {p t h r e a d _ c o n d _ b u s y w a i t (*( volatile enum task_stat *) (& tx - > stat ) == TASK_ALLOCATED ,& thr - > mut );# else/* 条件変数を用いる実装 */pth rea d_c ond _ wa it (& thr - > cond , & thr - > mut );# endif}} // while の先頭に戻り，thr->mut のロック獲得した状態で再確認

図2□: pthread_cond_wait

1.2
1

タスク要求に対する返信待ちの実装■: busywait
0.498

0.488

1.509

1.449

4.680

4.607

1.580

1.563

5. 2 構築方法
主な仮想環境の構築方法にはホスト型とハイパーバ

4.218 4.210

イザ型がある．ホスト型は OS 上で仮想化ソフトウェ

0.8

アを利用して VM を動かすもので VMware Player や
0.6

Oracle VirtualBox などがある．ハイパーバイザー型

0.4

では直接サーバに VM を立ち上げるもので Xen [1]0.2などがある．ホスト型の構築では簡単に VM を構築

0

fib(44)lu(4000)

図3

pen(14)

cmp(80000)

grav(800)

実環境上での相対実行時間

することができるなどの利点があり，ハイパーバイ
ザー型の構築では OS を介さずに VM を構築するためハードウェアのリソースを直接管理できるなどの利てられる．しかし仮想マシンを利用する場合，運用上点がある．

の理由で 1 台の実環境マシンに複数台の仮想マシン

本研究では仮想化ソフトウェアとして，ハイパーバを配置することがある．そういった場合，仮想 CPU

イザ型の構築方法を持つ Xen 4.6 を用い（表 2），ハに対し物理 CPU が不足することがある．

イパーバイザをハードウェア上で直接実行した．その本研究では様々な場合を想定し，16 コアの（表 1

上でドメイン 0 と呼ばれる制御用仮想マシンを実行の CPU とメモリを持ち，ハイパースレッディングはし，ドメイン U と呼ばれる仮想マシンを用いて実験無効化している）実環境マシン上に仮想 CPU 数 16を行った．構築したドメイン U の設定を表 3 に示す．

の VM を複数台構築して評価を行う．

表2

使用したハイパーバイザ

バージョン

0.7

ハイパーバイザ0.6

Xen 4.6

0.5

0.622
0.498

0.573
0.488

0.4
0.3

表3

ドメイン U（仮想環境 1 台分）の設定
仮想環境

仮想マシン上の OS

Ubuntu 16.04.5 LTS 64bit

仮想化方式

HVM

仮想 CPU

16

メモリ

1.6GB

0.2
0.1
0

図4

pthread_cond_wait
実環境

busywait
仮想環境1VM

実環境と仮想環境 1VM での fib(44) の実行時間

ワーカは通知が来るまでブロックするが，仮想環境の

6 仮想環境での効果方が実環境に比べて通知によってワーカ起こされるま

6. 1 評価方法

でに余計に時間がかかる．そのため仮想環境の方がビ

Tascell アプリケーションの 1 つで，フィボナッチ

ジーウェイトを適用することによる実行時間の短縮が数を求める fib を利用し，実行時間を計測することに大きくなったのではないかと考えられる．

より評価を行う．仮想マシン（表 3）を複数台同時にbusywait の場合も，仮想環境では実環境より実行

起動し，parallel ssh を利用してそれらに同時にアプ

時間が長くなっているが，これは，ビジーウェイト

リケーションを実行させてその実行時間を計測する．

を，すべてのウェイトに対しては適用していないた

ビジーウェイト適用前後の fib(44) による性能比較のめ，つまり，条件変数でウェイトする場合が残ってため，はじめに実環境と VM 数が 1 台の場合を比較いることもその要因として考えられる．具体的にはして評価を行い，その後 VM 数（「16 仮想 CPU でタスク要求の返信待ちでビジーウェイトを適用して

16 ワーカ実行する VM」の数）を 1, 2, 4, 8, 16 台といるものの，同時に結果待ちとしていたたサブタス

変化させ，それぞれの場合について，平均実行時間

クの結果が先に受け取れた場合は，タスク要求につ（全 VM 実行時間合計/VM 数）からの換算実行時間

いては後で必ず none が返信されることが確定してい（平均実行時間/VM 数）を求めて評価を行った．

るため，none が返信されることのウェイトをすぐには行わず，返信待ち数の記録のみで，次のタスク要

6. 2 評価結果

求直前まで遅延しており，遅延後のウェイトは条件

実環境と仮想環境 VM1 台で fib(44) を 22 回実行

変数でのウェイトのままになっている．残っている

して，実行時間の中央値を図 4 に示す．実環境上に比条件変数でのウェイトにもビジーウェイトを適用し，べて仮想環境 1VM の方が実行時間が長くなるが，こpthread_cond_broadcast も削除する場合の調査はれは仮想環境での実行時はドメイン U が 1 台であっ今後の課題である．

てもドメイン U だけでなくドメイン 0 を並行実行しVM 数を 1, 2, 4, 8, 16 台と変化させた場合の評価ていることや，それを含めた仮想化全般のオーバー結果を図 5 に示す．fib(44) を 22 回実行して換算実行

ヘッドが原因ではないかと考えられる．

時間を求め，その中央値を棒グラフで示し，四分位数

pthread cond wait（ビジーウェイト無し）の場合をプロットしている．VM 数が 1 の場合には，上のと busywait（ビジーウェイト有り）の実行時間の短評価結果にもあるようにビジーウェイトの適用によ

縮割合を比較した場合，実環境では 1.9%程度，仮想り実行時間が 7.9%程度短縮された．それに対し VM

環境 1VM では 7.9%程度短縮されている．

数が 2, 4, 8, 16 の場合にはビジーウェイトの適用にpthread cond wait の場合タスク要求の返信を待つ

より実行時間が増加する結果となった．また VM 数

# define p t h r e a d _ c o n d _ b u s y w a i t ( EXP , PMUT ) \do {\p t h r e a d _ m u t e x _ u n l o c k (( PMUT ));\while (( EXP )) xcc_pause ();\p t h r e a d_ m ut e x_ l oc k (( PMUT ));\} while (0)図6PAUSE 命令を追加した pthread-cond-busywait
マクロ

仮想環境上でタスクを要求した後の返信をビジー
図5

VM 数を変えたときの換算実行時間

ウェイトして待つ場合，実行時間がビジーウェイトしない場合に比べ長くなっているが，ビジーウェイトのが増えるほど実行時間が増加する．

繰り返しに PAUSE 命令を用いることで上記と同様の

これは返信が得られるまでの確認の繰り返しによ効果が得られる可能性がある．PAUSE 命令を仮想環

り，有限の計算資源が消費されてしまうためであり，境で利用するにあたって，Intel の仮想化対応プロセッ

VM 数が増えるほど消費される割合が増えていくた

サには Pause Loop Exiting（PLE） [5] という機能がめだと推測される．

ある．PLE を利用することにより PAUSE 命令が連

pthread cond wait の場合，VM 数が増えるほど実続的に使用された場合，ハイパーバイザに制御を戻す

行時間が短縮されるが，これは仮想 CPU をオーバーことができる．PLE には PLE Gap と PLE Window

コミットしたことにより効率的に物理 CPU が利用さという 2 つの設定値がある．

れたり，特に終盤でのワークスティールの増加が他のVM の処理があったために抑制されたりしたのではないかと考えられる．

• PLE Gap：PAUSE 命令が連続していると認識するまでの最大時間• PLE Window：PAUSE 命令が連続して実行される最大時間7 PAUSE 命令の効果

PLE Gap の設定値以下の間隔で連続して PAUSE

7. 1 概要

命令が実行され，その実行が PLE Window の設定値

マルチスレッドを使用する並列プログラムを正し以上の時間連続すると，PLE によるハイパーバイザ

く機能させるには，何らかの同期操作が必要であり．

への exit が発生する．

通常の同期操作は，共用の同期変数と，それをチェックする「スピン・ウェイト」ループで行う．現在，大7. 2 評価方法

部分の Intel プロセッサ [2] ではスピン・ループに関ビジーウェイトマクロのループ部分に PAUSE 命するパフォーマンス問題に対処するための命令として令を追加した図 6 として，先ほどの評価と同様に，ア

PAUSE 命令を提供している．同期変数をあまりに頻

プリケーション fib を利用して評価を行う．

繁にチェックすると，不必要にシステム・リソースを消費し，プロセッサがループを抜けるまでにかなり大きなペナルティを受けることとなる．PAUSE 命令をループに入れることによって，ループにわずかな遅延が入り，システム・リソースの使用量が少なくなり，
スピン・ウェイト中の電力消費量が大きく減少する効
果が得られる．

• pthread_cond_wait+ PLE（gap = 128, window = 4096）• ビジーウェイト PAUSE 命令無+ PLE（gap =128, window = 4096）• ビジーウェイト PAUSE 命令有+ PLE（gap =128, window = 4096）• ビジーウェイト PAUSE 命令有+ PLE（gap =512, window = 1024）の 4 つ場合で実行する．上 3 つの PLE の値はデフォルトの値であり，PAUSE 命令有りの場合には PLE
が確実に動くような PLE の値も設定している．VM
数（「16 仮想 CPU で 16 ワーカ実行する VM」の数）
を 1, 2, 4, 8, 16 台と変化させて，平均実行時間（全

VM 実行時間合計/VM 数）からの換算実行時間（平均実行時間/VM 数）を求めて評価を行った．

第 1 四分位数，第 3 四分位数）を求めた：• pthred cond wait+デフォルト PLE：0.479（0.466，
0.494）• PAUSE 無+デ フォル ト PLE：0.784（0.753，
0.839）• PAUSE 有+デ フォル ト PLE：0.780（0.737，
0.829）• pthread cond wait+確実な PLE：0.488（0.481，
0.495）

7. 3 評価結果• PAUSE 無+確実な PLE：0.734（0.688，0.764）

評価結果を図 7 に示す．fib(44) を 22 回実行し，換• PAUSE 有+確実な PLE：0.709（0.655，0.760）

算実行時間を求めて中央値を棒グラフで示している．

同じ結果を図 8 にも示す．

デ フォル ト PLE+PAUSE 無 の 場 合 と ，確 実 なタスク要求の返信待ちのビジーウェイトで PAUSE

PLE+PAUSE 有の場合の実行時間を比較すると，命令を用いない場合であっても，デフォルト PLE か

VM が 1 台 の 場 合 は 実 行 時 間 に ほ ぼ 差 が 無 い 結ら確実な PLE に設定変更することで，換算実行時間

果（ デ フォル ト PLE+PAUSE 無 で 0.573[s]，確 実の中央値が 0.050 秒程度も短縮されている．この理由

な PLE+PAUSE 有で 0.570[s]）となり，VM が 2 台としては，タスク要求の返信待ちのビジーウェイト以以上の場合は確実な PLE+PAUSE 有の場合の方が外でも例えば pthread_mutex_lock やゲスト OS 内

実行時間が短くなり，VM が 2 台の場合には 8.0%程部で PAUSE 命令が用いられていること，その部分に度実行時間が短縮されている．pthread cond wait の対して確実な PLE の効果があったこと，が考えられ場合と確実な PLE+PAUSE 有の場合を比較すると，る．また，タスク要求の返信待ちのビジーウェイトでVM が 1 台のときののみ確実な PLE+PAUSE 有の

PAUSE 命令を用いていた場合は，デフォルト PLE方が実行時間が短く，それ以外は pthread cond wait

から確実な PLE に設定変更することで，0.071 秒程の場合の方が実行時間が短くなる結果となった．

度とさらに大きく中央値が短縮されている．

PAUSE 命令と確実な PLE 設定を組み合わせるこ

確実な PLE では，PLE Gap を 128 から 512 にとによって，VM が複数台のときのビジーウェイト

増やすことでキャッシュミスなどで数百サイクル程によるリソースの余計な消費を多少抑えられたが，度のペナルティがあっても対象から外れにくくなり，pthread cond wait と比較すると，実行時間が長く

PLE Window を 4096 から 1024 に減らすことで exit

なっている．その理由としては，exit して他の仮想するまでの資源消費が低減されている．

CPU に切り替えたとしても，切り替え先の仮想 CPU

また，PAUSE 命令無から有にプログラムを変更すも結局ビジーウェイトしている場合がある，といっることの単独の効果は，デフォルト PLE では換算実た点や，exit によって最も切り替えたい先は thief と

行時間の中央値で 0.004 秒程度の短縮と小さい．確実

同じ VM にいる victim ワーカであるが，VM 数が増

な PLE の場合は，0.025 秒程度の短縮と，PLE の設えることで順番が回って来にくい点，などが考えら

定変更ほどではないが，一定の短縮効果が見られる．

れる．

ただ，確実な PLE の場合に，換算実行時間の第 3 四

図 7 の評価では，図 6 による PAUSE 命令と確実な PLE 設定（デフォルトとは異なる設定）の両方を用いていたため，それぞれ単独の効果を，図 7 で性能比が最も大きい VM 数 2 の場合について調査した．

55 回の実行に関して換算実行時間の中央値（並びに分位数では PAUSE 命令無と有の差はほとんどなく，

55 回の実行間の「ばらつき」が大きいといえる．

第1四分位数

1.2

第3四分位数

デフォルトPLE■：pthread_cond_wait

確実なPLE■：PAUSE有1

2■：PAUSE無■：PAUSE有換算実⾏時間[s]

1
0.8
0.6
0.4
0.2
0
4

8

16

VM数
図7

換算実行時間おいて並列処理の性能が低下する恐れがある．この問第⼀四分位数

第三四分位数■：pthread_cond_wait ■：PAUSE無 ■：PAUSE有研究 [9] では，本研究で「pthread cond wait によ

0.9
0.8

るタスク要求待ち」とした実装（本研究での調査では

0.7

換算実⾏時間[s]題への対応を試みる研究 [9] がある．

性能低下は見られず，むしろオーパコミットの場合に

0.6
0.5

はスループットが向上する）をベースとして，各ワー

0.4

カがすぐにスティールできるタスクを一定数用意して

0.3
0.2

おくことにより，スティールされる側の関与なし（一0.1

方の CPU 資源の利用）でスティールできる機会を増0

デフォルトPLE

図8

確実なPLE

やす手法が提案されている．

VM 数 2 の場合の比較

8. 2 VM が利用可能な CPU 数の変化に対応した並列アプリケーション実行の最適化

8 関連研究VM 内で並列アプリケーションを動かす時に生じ8. 1 仮想環境を考慮した要求駆動型負荷分散

る，物理 CPU の不足や並列アプリケーションの性能

CPU の物理コア数を超えて仮想 CPU を運用するが割り当てる CPU の減少以上に低下する問題の改場合，物理 CPU を時分割で割り当てるため，いずれ善を試みた研究として pCPU-Est [10] がある．物理かの仮想 CPU は休止状態となっている時間が存在す

CPU が不足する状況として，複数の VM 間での物理る．そのような状況では Tascell を用いた並列計算に

CPU の共有，VM が利用できる CPU 使用率の制限，

VM に割り当てる物理 CPU を減らす，が想定されてよび JP17K00099 の助成を受けたものである

いる．この研究では実行時情報に基づいて VM の仮
想 CPU 数を動的に最適化することで並列アプリケー

参 考 文 献

ションの性能を改善する手法が提案されている．

[ 1 ] : Xen Project Hypervisor, https://wiki.xenproject.org/
wiki/.
[ 2 ] : イ ン テ ル Pentium4 プ ロ セッサ お よ び イ ン
テ ル Xeon プ ロ セッサ に お け る ス ピ ン・ル ー プ の使 用, https://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/w spinlock j.pdf.
[ 3 ] Frigo, M., Leiserson, C. E., and Randall, K. H.:
The Implementation of the Cilk-5 Multithreaded
Language, Proc. of the ACM SIGPLAN Conf.
PLDI, 1998, pp. 212–223.
[ 4 ] Hiraishi, T., Yasugi, M., Umatani, S., andYuasa, T.: Backtracking-based Load Balancing,
New York, NY, USA, ACM, 2009, pp. 55–64.
[ 5 ] Intel Corporation: Intel 64 and IA-32 Architectures Software Developer’s Manual Volume 3 (3A,
3B, 3C & 3D): System Programming Guide, 2016.
[ 6 ] 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.
[ 7 ] 平石拓, 河野卓矢, 八杉昌宏, 馬谷誠二, 湯淺太一:
バックトラックに基づく負荷分散の高並列環境における評価, 情報処理学会研究報告. [ハイパフォーマンスコン
ピューティング], Vol. 2010, No. 25(2010), pp. 1–11.
[ 8 ] 平石拓, 八杉昌宏, 馬谷誠二: 動的負荷分散フレーム
ワーク Tascell の広域分散およびメニーコア環境における評価, 先進的計算基盤システムシンポジウム論文集,
Vol. 2011, May 2011, pp. 55–63.
[ 9 ] 良本海, 八杉昌宏, 平石拓, 馬谷誠二: 仮想環境を考慮した要求駆動型負荷分散, 日本ソフトウェア科学会第34 回大会講演論文集, September 2017.
[10] 高山都旬子, 光来健一: VM が利用可能な CPU 数の変化に対応した並列アプ リケーション実行の最適化, 日本ソフトウェア科学会第 33 回大会講演論文集,
September 2016.

9 まとめ
並列言語実装技法の 1 つであるビジーウェイトを並列言語とその処理系である Tascell におけるワーク
スティールの返信待ちに適用したところその有効性を確認した．同様に仮想環境上で VM 数を変動させながら評価を行ったところ，VM 数が 1 の場合を除いてビジーウェイトを適用した場合の方が既存の手法に比べて実行時間が長くなる結果となった．ビジー
ウェイトの適用によって仮想環境での実行時間が長くなることを少しでも回避するため，PAUSE 命令をビ
ジーウェイトの繰り返しに用いて，PLE によってハ
イパーバイザに exit させる場合の評価を行ってみた
ところ，単にビジーウェイトする場合に比べて実行時間が短縮されたが，既存の pthread cond wait する
場合に比べると実行時間は長くなった．
今後の課題として，PAUSE 命令に関する調査では共通の PLE の設定での評価をいくつか増やす必要がある．現在の PAUSE 命令により exit する仕様ではexit 先によって PAUSE 命令による恩恵が得られにくい場合がある．そのため，exit した仮想 CPU の優
先度をしばらく下げて exit 先として選ばれにくくす
るような設定項目があれば，より PAUSE 命令を有効に使えるのではないかと考える．
謝辞 本研究の一部は JSPS 科研費 JP19H04087 お