高速通信機構を用いたソフトウェア DSM のパフォーマンス解析
バルリ ニコ デムス

渡辺 正泰
坂井 修一
東京大学 工学系研究科

田中 英彦

概要
近年、高速ネットワークの研究が進んでおり、低オーバヘッド 高バンド 幅のネット
ワークが開発されている。このようなネットワークを用いると、ノード 間の通信がボト
ルネックとなるソフトウェア DSM の性能を大きく向上できる可能性がある。
本稿では低オーバヘッド 通信機構とメモリマップ通信機構に着目して、このような通信機構をページベースソフトウェア DSM に用いるときにどれぐ らい性能向上が得られるかを定量的に解析した。解析した結果、100 Mbps イーサネットに比べると共有メ
モリオーバヘッド が 10 % 〜 49 % 削減されたが FFT や Ocean のような、メモリアクセスパターンによってページフォルトが頻繁に起こるようなアプ リケーションでは充分な高速化は得られなかった。

Performance Analysis on
Software DSM System Connected with High Speed Network
Niko Demus Barli

Masahiro Watanabe

Shuichi Sakai

Hidehiko Tanaka

Graduate School of Engineering, University of Tokyo

Abstract

Recent researches on High Speed Network have resulted in signi cant improvementon the performance of network. There are now many low overhead, high bandwith
networks available. By using these high speed networks, there is possibility that we
can greatly improve performance of software DSM system, whose bottleneck is incommunication overhead between nodes.
In this paper, we put our attention on low overhead communication mechanismand memory mapped communication mechanism, and quantitatively analyzed how
much performance improvement we can get from using these mechanisms in pagebased software DSM system. We found that compared to 100 MBps Ethernet, theoverhead of software DSM system is reduced by 10 % 〜49 %. But for applications
whose memory access pattern causes frequent pagefaults, like FFT and Ocean, we stillcannot get enough speed up.

1 はじめにソフトウエア DSM は非常に小さいコストで共有メモリを実現した。しかし、このようなソフトウェアベース
システムは専用ハード ウェアを用いた分散共有メモリシ
ステムに比べれば処理性能が低い。その原因はメモリコ
ンシステンシを保持するためにノード 間の通信が頻繁に起こり、ソフトウェア処理時間と通信時間が増大してしまうからである。
この問題を解決するために様々な研究が行なわれてきた。その成果の一つは共有メモリオーバヘッドを軽減する
Release Consistency プロトコルがソフトウェア仮想分散
共有メモリシステムのプロトコルとして確立してきた。
このような研究が進んでいる中で、近年、Myrinet[2],DEC Memory Channel[3], Gigabit Ethernet, ATM Network, といった高速ネットワークが商用化されてきた。ソフトウェア DSM はこのようなネットワークを用いることによって性能が大きく向上できることが期待されている。
本研究は高速ネットワークの技術の中の、(1) 低オーバ
ヘッド 通信機構及び (2) メモリマップ通信機構に着目する。まずページベースソフトウェア DSM を実装し、このシステムを用いて、通信コストの解析を行ない、上述の通信機構を用いたときのソフトウェア DSM のパフォー
マンスを定量的に解析する。解析結果から、どれぐ らいの速度向上が期待できるか、またソフトウェア DSM の
ボトルネックが解消されるかどうかを明確になる。
本稿では、2 章で低オーバヘッド 通信機構及びメモリ
マップ通信機構について述べ、ソフトウェア DSM でどのように使われるかを述べる。3 章でシステムの実装とそのシステムを用いた解析手法を述べる。4 章で解析結果をまとめ議論を行なう。最後に 5 章でまとめをする。

2 高速通信機構
2.1

低オーバヘッド 通信機構

低オーバヘッド 通信機構はネットワークインタフェー
スに専用プロセッサやメモリを搭載し、従来ホストプロ
セッサが処理するプロトコル処理の一部をネットワーク
インタフェースに任せることで通信のソフトウェアオー
バヘッド を軽減する。またユーザメモリに直接読み書きできるような 0-copy 通信 や、 DMA を活用することでさらにオーバヘッド の少ない通信を可能にする。
低オーバヘッド 通信機構を代表する Myrinet のネット
ワークインタフェースの概略図は図 1に示す。このような通信機構を用いると高速な通信が可能になり、例えば、
従来 100 MBps のイーサネットで小パケットを送受信す
るのに 100[s] 以上かかったものは 10[s] 程度にすることができた。
To I/O Bus
Host DMA

MemoryProcessor

2.3

高速通信機構とメモリコンシステンシプ
ロト コル

低オーバヘッド 通信機構とメモリマップ通信機構は抽象レベルの異なる通信機構と考えることができる。図 3に示すようにメモリマップ通信機構は通信レイヤにおいてより上位にあることがわかる。
ソフトウェア DSM のコンシステンシプロトコルにはメッセージパッシング通信機構で実装される Sequential
Consistency (SC) 、Lazy Release Consistency (LRC)[6],Home-based Lazy Release Consistency (HLRC)[9] プロ
トコルがある。またメモリマップ通信機構を生かしコン
システンシを保持する Automatic Update Release Consistency (AURC)[4] プロトコルがある。

Packet Interface

Consistency
ProtocolLayer

To Network Link

図 1: Myrinet NIC の構成
2.2

Communication
Layer

メモリマップ通信機構

SC,
LRC,
HLRC

AURC

Message Passing
Memory Mapped
Comm. Mechanism Comm. Mechanism

Low Ovh. Comm. Mechanism

メモリマップ通信機構は各ノード でグローバルメモリ
空間を送信バッファ(outgoing bu er) あるいは受信バッ
ファ(incoming bu er) としてマップし、送信バッファに書き込まれたデータはリモート メモリライト機構を用いて自動的に受信バッファにコピーされる (図 2)。
メモリマップ通信機構は次のような特徴をもつ。

これらのコンシステンシプロトコルの性質を簡単にまとめると次のようになる。

1. 受信バッファはローカルメモリ領域として存在す
るが送信バッファはネットワーク I/O アド レスに

 LRC、 共有メモリへの更新は Acquire 同期の時にマップされる。
2. 書き込み・読みだしのオーバヘッド は通常のロー
カルメモリアクセスと同じである。また、受信バッ
ファへの書き込みは DMA を用いるのでホストプロ
セッサを割り込むことなく書き込むことができる。
3. あるグローバルメモリ空間を送受信バッファにマップしたいときは図 2のノード 1 のように送信バッ
ファと受信バッファ、２つのアド レス空間にマップしなければならない。



図 3: 高速通信機構とコンシステンシプロトコル SC、 共有メモリへの更新は更新した直後に他のノード に反映される。

GlobalAddress Space
Node 1

3 パフォーマンス解析とその手法

Node 3

out

in

in

Node 2

Node 4ininout

図 2: メモリマップ通信機構反映される。
HLRC 、 LRC と同様に共有メモリへの更新は Acquire 同期の時に反映される。但し、各ページにホームノード を割り当て、共有メモリへの更新はRelease 同期の時にホームノード に送られる。ホームノード にあるページのコピーは常に有効なコピーである。
AURC 、 LRC と同様に共有メモリへの更新は Acquire 同期の時に反映される。但し、各ページにホームノード を割り当て、共有メモリへの更新はメモリ
マップ通信機構を用いて更新する都度にホームノード に送られる。ホームノード にあるページのコピーは常に有効なコピーである。

3.1

解析概要

解析を行なうにはまずページベースソフトウェア DSM
システムを実装する。このシステムに SPLASH-2 のベン
チマーク郡からいくつかのプログラムを移植し実験を行
ない、実行時間、共有メモリオーバヘッド、通信トレー
スなどのデータを収集する。通信トレースから実験に用いた 100 Base-TX ネットワークにおける通信コストを解析する。さらに Myrinet のような低オーバヘッド ネッ
トワークを想定し、その通信コストを推定する。最後に、
低オーバヘッド 通信機構の効果及びメモリマップ通信機
構効果を求めるために 低オーバヘッドネットワークを用いたとき (Myrinet)と用いないとき (100Base-TX)
メモリマップ通信機構を用いたとき (AURC) と用いないとき (SC, LRC, HLRC)の性能を比較する。



システムの実装

システムはライブラリとして実装した。メモリコンシ
ステンシ管理は 8[kB ] のページ単位で行ない、ノード 間通信には UDP/IP プロトコルを用いている。このシス
テムは SC 、LRC 、及び HLRC プロトコルをサポートする。実行形態は１ノード 当たり１スレッド のみである。
このシステムの API は表 1にまとめる。
AURC の解析に関しては HLRC を用いて AURC の動作をシミュレーションする。AURC のページの更新はコストが生じないと仮定し HLRC の実行時間から twinの作成、di の作成、di の送信・適用コストを削除し求める。
表 1: システムのインタフェース

tsm startup()
システムの初期化
tsm alloc()
共有領域の確保tsm create procs() リモートプロセスの起動
tsm nish()
システムの終了
tsm barrier()barrier 同期
tsm lock()lock 同期
tsm unlock()unlock 同期
TSM PID
プロセスの識別子
TSM NUMNODES システムのノード 数
3.3(a) 1 Datagram Packet -> 1 Ethernet Packet

イーサネット 上の UDP/IP の通信コスト の解析

イーサネット上の UDP/IP 通信過程は図 4に示している。図 4(a) は 1 つのイーサネットパケットに収まるよ

Symbols:
S : Socket Level
Processing
P : UDP/IP Level
Processing
D : Device Driver
Processing
I : Network Interface
Processing
T : Transfer TimeHI

Host Processor 1 S
Network IF 1
Network
Network IF 2
Host Processor 2

P D

D
I

SI

SI

T
I
D

P

S

HI

sendmsg
overhead

Observed
Network Latency

recvmsg
overhead

HI : Hardware Interrupt
SI : Software Interrupt(b) 1 Datagram Packet -> 2 Ethernet Packet
HI

Host Processor 1
Network IF 1
Network
Network IF 2
Host Processor 2

S

P

D D

HI
D

I

D
I

T
I

SI

D

P

SI

I
D

sendmsg
overhead

HI
T

HI

P

S

SI

Observed
Network Latency

recvmsg
overhead

図 4: イーサネット上の UDP/IP の通信過程

通信コスト の解析

通信コストの解析はプログラム実行時間からどれぐ らい通信コストが占めているかを求めるためである。まず、
イーサネット上の UDP/IP の通信コストを抽出し、その他の計算時間・共有メモリオーバヘッド 時間から分離する。次に低オーバヘッド 通信機構を想定した場合の通信コストを推定し、それをもともとの通信コストのところに入れ換えることで低オーバヘッド 通信機構のを用いたときの実行時間・共有メモリオーバヘッド を求めることができる。
通信コストは通信レイテンシと通信オーバヘッド と２つの場合に分けて解析する。通信コストが通信レイテン
シであるのは「要求を出してその応答を待つ」の場合である。このとき要求を出す側からみると通信コストは要
求メッセージの通信レイテンシと応答メッセージの通信
レイテンシの和である。一方、通信コストが通信オーバ
ヘッド であるのは「要求をもらってそれに応答する」という場合である。つまり応答する側からみると通信コス
トは要求メッセージを受信するときの受信オーバヘッドと応答メッセージを送信するときの送信オーバヘッド の
和である。
3.3.1

された場合を示す。
図 4の sendmsg overhead 、observed network latency 、
recvmsg overhead は通信レイテンシの測定可能な量である。図 5は Sun SparcStation 20 (SuperSPARC-II 75
MHz Processor 、100Base-TX NIC) 上で測定した通信
レイテンシを表している。通信コストが通信レイテンシである場合、single trip latency の測定結果を用いて通信コストを直接計算することができる。一方、sendmsg
overhead と recvmsg overhead は図 4からわかるようにそれぞれ真の送信オーバヘッド と受信オーバヘッド の一部にしかすぎないので、通信コストが通信オーバヘッド
である場合これらの値を直接用いることができない。

UDP Communication Latency
3000
Time [us]3.2

うな、小さいパケットを転送する場合を示す。また、図4(b) はパケットがが 2 つのイーサネットパケットに分割

2000
1000
0
0

5
10
15
Message Size [kBytes]
send overhead
receive overhead

20

observed network latency
single trip latency

図 5: UDP 通信レイテンシ、測定結果
真のオーバヘッド は一般に ソケットレベルの処理 (S) 、
UDP/IP レベルの処理 (P) 、デバイスドライバの処理 (D) 、と割り込みコスト (HI/SI) からなる。通信オーバヘッドの解析は次のように行なう。ソケットレベルの処理 (S) はrecvmsg overhead で近似する。また、UDP/IP レベルの処理 (P) 、デバイスド ライバの処理 (D) は 1 イーサネッ
トパケット当たりに固定であると仮定する。これを測定結果に適用し近似を求めた結果、 イーサネットパケット
当たりの P + D は 4000 cycle 、また割り込みコストは
1 回当たり 3000 cycle と求まった。通信オーバヘッド は

4 実験とパフォーマンス解析の結果

これらの値を用いて計算する。
3.3.2

低オーバヘッド 通信機構の通信コスト の推定

低オーバヘッド 通信機構は Myrinet のようなネット
ワークを想定する。データを送受信するときの様子は図6に示している。ユーザプロセスに呼び出された通信ライ
ブラリはデータの送信を準備し、デバイスド ライバを呼び出す。ド ライバはデータのアド レスをネットワークイ
ンタフェースに通知し、DMA 転送を開始させる。デー
タはネットワークインタフェースのメモリにコピーされ、専用プロセッサがそれを処理してパケット インタフェー
スを通して相手に送信する。このとき DMA コントロー
ラ、専用プロセッサ、パケットインタフェースはオーバーラップして処理を行なう。DMA 転送が終ったらネット
ワークインタフェースは割り込みを起こしド ライバに通知する。受信側では届いたパケットが専用プロセッサに渡され、パケットから取り出したデータを DMA 転送でユーザプロセスの受信バッファにコピーする。
HI
Host Processor 1
Network IF 1

U

D

実験環境及びベンチマークパラメタ

4.1

実験に用いられるワークステーションクラスタは 100
Base-TX で接続されている 4 つのノード から構成されている (表 3)。また、測定対象となるプログラムは SPLASH2[8] ベンチマーク群から FFT, LU, Ocean 及び WaterNsquared を使用した。プログラムのパラメタ及び必要な共有メモリ領域は表 4に示している。
測定に用いた４つのプログラムはレギュラーなプログ
ラムである。つまり、各ノード の計算量が動的に変化す
ることはない。これはクラスタが同性能のノード から構成されていないことによる負荷アンバランスの影響を小さくするためである。以下は測定結果・解析結果を説明するが、全ての測定結果は性能の一番低いノード (1) における測定結果である。
表 3: クラスタの構成
NodeMachineProcessor

Mem

OS

1

SparcStation 20

SuperSparc-II

128

Solaris75 MHz

[MB]

2.5

2

Ultra 1

UltraSPARC

96

Solaris167 MHz[MB]

2.5
SolarisD
O

I

Network

SI

T

Network IF 2

I

Host Processor 2

O

D

HI

3

D

U

HI

Symbols:
U : User’s Communication Library Call
D : Device Driver Processing
O : NIC Overhead (DMA Transfer + Packeting Ovh)
I : Network Interface Processing
T : Transfer TimeHI : Hardware Interrupt
SI : Software Interrupt

図 6: 低オーバヘッド 通信機構の通信過程
通信コストを求めるには通信レイテンシ・送信オーバ
ヘッド・受信オーバヘッド を推定しなければならない。これらの値を推定するには各通信パラメタを仮定し図 6の通信過程に適用する。用いられた通信パラメタは表 2にまとめた。
表 2: 低オーバヘッド 通信機構のパラメータ

Software Overhead
I/O Bus Bandwith
Network Bandwith
Interrupt Cost

400 [cycle]
132 [MBps]
100 [Mbps]
1 [Gbps]
3000 [cycle]

Software Overhead は データを準備する時間であり、データのサイズによらず 400 cycle 固定と仮定する。I/OBus Bandwith はネットワークインタフェースとメモリとの間のデータ転送のバンド 幅を表し、32 bit - 33 MHz
PCI バスの理想的な場合を仮定する。Network Bandwith
はネットワークバンド 幅を表し、100 Mbps と 1 Gbps 、２つの場合に分けて解析する。これは同じバンド幅で 100
Mbps イーサネットに比べて低オーバヘッド 化の効果とさらにバンド 幅をあげたときの効果をみるためである。
最後に Interrupt Cost は UDP/IP の場合と同様に 3000
cycle とする。

4

Ultra Enterprise

UltraSPARC-II

504

3000

248 MHz

[MB]

2.5.1

Ultra 10UltraSPARC-IIi

128

Solaris300 MHz[MB]

2.6

表 4: ベンチマークのパラメタ

BenchmarkFFT
LU (Contig.)
Ocean (Contig.)
Water-Nsquared
4.2

Problem Size
262144 points
1024 2 1024 matrix
258 2 258 ocean
1331 molecules

Memory
12 MB
8 MB
11 MB
1 MB

並列実行による高速化

各ベンチマークの実行時間は図 7-図 10に表す。実行時
間は上からの順番で次のように分割して表示する。

 barrier, barrier 同期に消費された時間。
 readsegv, リード ページフォルトの処理時間。
 writesegv, ライトページフォルトの処理時間。
 sigio, アプリケーションコード を実行する最中に起

こった SIGIO のハンド ラの処理時間。
(un)lock/sigalrm, lock 同期の時間, unlock 同期の時間, 及び アプ リケーションコード を実行する
最中に起こった SIGALRM のハンド ラ処理時間を合わせたもの。
computing, アプ リケーションコード を実行する
時間。

また、各ベンチマークの高速化は表 5に示している。
この結果から、LU と Water-Nsquared は複数ノードで並列実行されることによって高速化が見られるが、FFTと Ocean では高速化が得られず、逆に遅くなったことがわかる。FFT と Ocean では共有メモリコンシステンシ

FFT − 262144 pts

LU − 1024 x 1024 matrix

computingwritesegv

computingwritesegv(un)lock/sigalrm
sigio

readsegv
barrier(un)lock/sigalrm
sigio

readsegv
barrier

60
Time [s]Time [s]

15
10
5
0

40
20
0

1

2 4
SC

1

2 4
LRC

1 2 4
HLRC

1 2 4
AURC

1

2 4
SC

Protocol − Number of Nodes

図 8: LU 1024

1 2 4
HLRC

1 2 4
AURC

2 1024 matrix - 実行時間分割

Water−Nsquared − 1331 molecules

computing(un)lock/sigalrm

writesegv
readsegv

computing(un)lock/sigalrm

writesegv
readsegv

sigio

barriersigio

barrier

150

Time [s]Time [s]Ocean − 258 x 258 ocean

100
50
0

40
20
0

1 2 4
SC

1 2 4
LRC

1 2 4
HLRC

1 2 4
AURC

1

2 4
SC

Protocol − Number of Nodes

図 9: Ocean 258

2 258 ocean - 実行時間分割

管理の時間及び同期時間が大きくなり並列実行によるメリットを打ち消してしまうからである。
このようにソフトウェア DSM の性能はアプリケーションの特徴によって大きく左右される。一般に高速化を得るためには高い computation to communication ratio が必要になる。
FFT の場合を考えてみると、 FFT は N 個のデータ
p
N の 行列として表現する。各ノード に PN
点を N
行 (P はノード の数) をブロックとして割り当てる。FFTの計算は radix- N six-step FFT アルゴリズムを用いるが、このアルゴリズムの６つのステップの中の 3 ステップは行列の転置 (transpose) である。図 11は 262144 points
FFT の転置を示している。各ノード は自分のブロックに書き込むための必要な要素を要求し転置行列を作る。このとき他のノード のブロックは読み込み不可になっているためリード ページフォルトが起こる。一回の転置において 2 ノード 構成では 128 回、4 ノード 構成では 192 回のリード ページフォルトが起こる。リード ページフォル
トが起こるとリモート ノード から有効なページあるいはdi を持って来なければならない。一回の転送で数 ms から数十 ms がかかり、全体的には一回の転置では数秒の時間がかかってしまう。一方、行列転置の計算内容は主にメモリコピーだけであり、メモリコピーにかかる時間
は数十 [ms] である。このように FFT の転置は非常に小さい computation to communication ratio をもち並列実行による高速化を得るのは困難である。

2

2 4
LRC

Protocol − Number of Nodes

図 7: FFT 262144 points - 実行時間分割

p

1

1

2 4
LRC

1 2 4
HLRC

1 2 4
AURC

Protocol − Number of Nodes

図 10: Water 1331 molecules - 実行時間分割

2 Processors

P0

512 rows=
256 pages

P1

pcauses128 page read faults

512 x 8 = 4096 bytes(2 rows -> 1 page)p

4 Processors
P0
512 rows=
256 pages

P1
P2
P3
512 x 8 = 4096 bytes(2 rows -> 1 page)causes128+64 page read faults

FFT Transpose Phase (262144 points)

図 11: FFT のデータ行列の転置

Ocean についても同じように解析することができ、隣合うノード のブロックをアクセスすいるとき、FFT と同じようにページフォルトが頻繁に起こり遅くなってしま
うことがわかる。

表 5: スピード アップ (100Base-TX)

2 Nodes

Benchmark
FFT
LU
Ocean
Water-Nsquared

4 Nodes

SC

LRC

HLRC

AURC

0.21
1.3
0.39
1.4

0.14
1.2
0.40
1.4

0.25
0.86
0.23
1.5

0.35
1.2
0.40
1.7

SC

LRC

HLRC

AURC

0.14
2.0
0.07
1.9

0.13
2.0
0.11
2.3

0.19
1.5
0.15
2.5

0.21
2.2
0.20
3.1

表 6: スピード アップ (Low Overhead - High Bandwith (1 GBps) Network)

2 Nodes

Benchmark
FFT
LU
Ocean
Water-Nsquared

4 Nodes

SC

LRC

HLRC

AURC

0.29
1.4
0.49
1.5

0.19
1.3
0.49
1.5

0.38
1.1
0.34
1.6

0.47
1.4
0.49
1.8

SC

LRC

HLRC

AURC

0.18
2.2
0.09
2.1

0.19
2.2
0.15
2.4

0.30
2.1
0.22
2.8

0.32
2.3
0.28
3.2

表 7: 低オーバヘッド 通信機構による共有メモリオーバヘッド の削減率

Benchmark
FFT
LU
Ocean
Water-Nsquared

2 Nodes

4 Nodes

SC

LRC

HLRC

AURC

SC

LRC

HLRC

AURC

33 %
27 %
22 %
20 %

26 %
24 %
19 %
18 %

42 %
45 %
39 %
32 %

36 %
30 %
30 %
37 %

23 %
22 %
19 %
17 %

32 %
27 %
25 %
17 %

40 %
49 %
35 %
32 %

32 %
23 %
34 %
35 %

表 8: メモリマップ通信機構による共有メモリオーバヘッド の削減率

Benchmark
FFT
LU
Ocean
Water-Nsquared
4.3

to HLRC
2 Nodes 4 Nodes
26 %
11 %
42 %
25 %
41 %
23 %
47 %
43 %

高速ネットワークを用いたときのパフォー
マンス

4.3.1

低オーバヘッド 化・バンド 幅の拡大による通信コ
スト の削減図 12-図 15は通信コストを解析した結果を表している。
「 LOH 」
「 LOH-HB 」の記号は想定したネッ
図の「 Eth 」
トワークを表し、それぞれ次のようである。

Eth

:

LOH

:

LOH-HB:

Ethernet 100Base-TX 、UDP/IP
プロトコル、バンド 幅 100 [Mbps]
低オーバヘッド通信機構、0-copy 通
信プロトコル、バンド幅 100 [Mbps]
低オーバヘッド通信機構、0-copy 通
信プロトコル、バンド 幅 1 [Gbps]

図 12-図 15の「 Eth 」と「 LOH 」を比べると「 Eth 」と「 LOH 」が同じバンド であっても「 LOH 」の通信コスト(割り込みコストも含む) は 「 Eth 」より 40 % - 63 %も少ない。また、バンド 幅を 100 [Mbps] から 1 [Gbps]に拡大するとさらに通信コストが減少する。
「 LOH 」と

to Best Protocol
2 Nodes
4 Nodes(HLRC) 26 % (HLRC) 11 %(SC) 10 %(LRC) 11 %(LRC) 19 % (HLRC) 23 %(HLRC) 47 % (HLRC) 43 %「 LOH-HB 」の場合を比べると 5 % - 38 % 通信コストが削減されることがわかる。このように低オーバヘッド 化の効果とバンド 幅の拡大の効果を合わせるとイーサネッ
ト 100Base-TX の場合に比べると通信コストが 43 % 72 % 削減されることがわかる。
4.3.2

低オーバヘッド 通信機構の効果・メモリマップ通信機構の効果低オーバヘッド 通信機構による、共有メモリオーバヘッ
ド ( メモリコンシステンシ管理のオーバヘッド と同期のオーバヘッド ) の、削減率を表 7に示す。全体的には 17% - 49 % の削減率が見られるが、特に HLRC プロトコルにおける削減率が 32 % - 49 % 一番大きいことがわかる。その次は AURC で 20 % - 37 % の削減率がみられる。HLRC と AURC は、通信量が多く、またソフト
ウェア処理が軽いため、通信コストの割合が大きい。従って低オーバヘッド ネットワークの効果が一番大きくみられる。

FFT − 262144 pts

Time [s]computingconsistency protocolcomm.cost (excl. interrupt cost)interrupt cost

15
10
5

[Eth]−4[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−4[LOH−HB]−2[LOH−HB]−2[LOH]−4[Eth]−2[LOH]−2[Eth]−2[LOH]−2

1[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[Eth]−4[LOH]−4[LOH]−2[LOH−HB]−21[Eth]−2[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−20[Network Type] − Number of Nodes
4 Groups of Results (from left SC − LRC − HLRC − AURC)

図 12: FFT 262144 points - 実行時間と通信コスト
LU − 1024 x 1024 matrix
computingconsistency protocolcomm.cost (excl. interrupt cost)interrupt cost

Time [s]

60
40
20

1

[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[Eth]−4[LOH]−4[LOH]−2[LOH−HB]−21[Eth]−2[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−20[Network Type] − Number of Nodes
4 Groups of Results (from left SC − LRC − HLRC − AURC)

図 13: LU 1024

2 1024 matrix - 実行時間と通信コスト

表 8はメモリマップ通信機構によってどれぐらい共有メ
モリオーバヘッドが削減されるかを表している。この表に示した値は AURC の共有メモリオーバヘッド を、 HLRCの共有メモリオーバヘッド 及び (SC・LRC・HLRC) の中で一番性能のよいプロトコルの共有メモリオーバヘッドと比較した場合を表している。この表からメモリマップ
通信機構を利用することによって他のプロトコルに比べて 10 % - 47 % の共有メモリオーバヘッド の削減が得られることがわかる。
バンド 幅 1 [Gbps] の低オーバヘッド ネットワークを用いたときのスピード アップは表 6に示す。アプ リケー
ション別にみてみると FFT 及び Ocean は通信コストが大きく削減されたものの並列実行による高速化がえられなかった。これは図 12及び図 14をみればわかるように
FFT と Ocean の場合、通信コスト以外の、主にページ
フォルトによるコンシステンシ管理のオーバヘッド が大きいからである。通信コストが大きく削減されてもコン
システンシ管理のソフトウェア処理コストが解消されな
いためボトルネックになってしまう。
このように低オーバヘッド 通信機構及びメモリマップ
通信機構によって共有メモリオーバヘッド が大きく短縮されたが、既存のコンシステンシプロトコルではシステ
ムのボトルネックが解消されず充分な高速化が得られない場合もある。

5 まとめ
本研究は低オーバヘッド 通信機構及びメモリマップ通信機構に着目して、このような通信機構を用いたページ
ベースソフトウェア DSM の性能はどれぐ らい向上できるかを定量的に解析した。
ページベースソフトウェア DSM は共有メモリ領域をページ単位で管理するが、細粒度のシステムに比べると性能
がアプリケーションの特徴によってより大きく左右される。
並列実行による高速化を得るには充分高い computation
to communication ratio が必要になる。測定を行なった
結果、LU 及び Water-Nsquared では並列実行による高速化が得られるが FFT 及び Ocean では得られなかった。
解析結果から低オーバヘッド 通信機構及びメモリマッ
プ通信機構によって共有メモリオーバヘッド が大きく削減されたことがわかる。しかし、FFT や Ocean のような、メモリアクセスパターンによってページフォルトが頻繁に起こるような場合は性能が向上されたものの、システムのボトルネックが解消されず充分な高速化が得られなかった。この場合は通信コストが小さくなるがメモリコンシステンシ管理のソフトウェア処理コストがボト
ルネックになってしまう。

Ocean − 258 x 258 oceanTime [s]computingconsistency protocolcomm.cost (excl. interrupt cost)interrupt cost

150
100
50

[LOH−HB]−4[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH−HB]−2[LOH]−4[LOH]−2[Eth]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[Eth]−4[LOH]−4[LOH−HB]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[Eth]−4[LOH]−4[LOH−HB]−2[Eth]−2[LOH]−2

1[LOH−HB]−4[Eth]−4[LOH]−4[LOH−HB]−2[Eth]−2[LOH]−2

10[Network Type] − Number of Nodes
4 Groups of Results (from left SC − LRC − HLRC − AURC)

図 14: Ocean 258

2 258 ocean - 実行時間と通信コスト

Water−Nsquared − 1331 molecules

Time [s]computingconsistency protocolcomm.cost (excl. interrupt cost)interrupt cost40
20[Eth]−4

1[LOH]−4[LOH−HB]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[LOH]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−2[LOH−HB]−4[LOH]−4[Eth]−4[LOH−HB]−2[LOH]−2

1[Eth]−20[Network Type] − Number of Nodes
4 Groups of Results (from left SC − LRC − HLRC − AURC)

図 15: Water-Nsquared 1331 molecules - 実行時間通信コスト

今後の課題
ページベースソフトウェア DSM の性能を向上させるには通信ネットワークの部分の高速化だけでなく、メモ
リコンシステンシ管理のソフトウェア処理の部分も充分小さく抑える必要がある。このため今後の課題として以下のような点があげられる。

 アーキテクチャ的なサポートを利用し、その特徴を


最大に利用できるコンシステンシプロトコルを開発する。
アプリケーションの特徴を理解し、ページベースのソフトウェア DSM に適用すると 充分高い、 computation to communication ratio が得られるかど
うかを調べる。得られない場合は アルゴリズムを考え直すか、computation to communication ratioが低いところだけを逐次実行させる、などの対策が考えられる。

「 Myrinet { A Gigabit-per-Second Local-Area
Network」. IEEE Micro, 15(1):29-36, February 1995
[3] Marco Fillo and Richard B. Gillett. 「 Architecture and
Implementation of MEMORY CHANNEL 2」. Digital
Su.

Technical Journal, Volume 9, Number 1, 1997.

[4]

Liviu Iftode, Cezary Dubnicki, Edward W. Felten and Kai「 Improving Release-Consistent Shared Virtual
Memory using Automatic Update」. 2nd IEEE Sympo-

Li.

sium on High-Performance Computer Architecture, February 1996

「 Understanding
Application Performance on Shared Virtual Memory」. Proceedings of 23rd Annual Symposium on Computer[5]

Liviu Iftode, Jaswinder Pal Singh, Kai Li.

[6]

Pete

[7]

Leonidas Kontothanassis, Galen Hunt, Robert Stets, Niko-

Architecture, May 1996

Keleher. 「 Distributed Shared Memory Using
Lazy Release Consistency」. PhD Thesis, Rice Univer-sity, December 1994.

laos Hardavellas, Michal Cierniak, Srinivasan Parthasarathy,
WagnerMeira,「 VM-Based

Sandhya

Dwarkadas,

andStevenCameronWoo,

Moriyoshi

Ohara,

Jaswinder Pal Singh, and Anoop Gupta.

Nanette J. Boden, Danny Cohen, Robert E. Felderman, Alan
E. Kulawik, Charles L.Seitz, Jakov N. Seizovic, Wen King

Torrue,national Symposium on Computer Architecture, June 1995

Angelos Bilas and Jaswinder Pal Singh.

percomputing 97, San Jose, CA, November 1997.
[2]

Evan

「 The SPLASH-

2 Programs: Characterization and Methodological
Considerations」. Proceedings of the 22nd Annual Inter-

参考文献「 The E ects ofCommunication Parameters on End Performance ofShared Virtual Memory Clusters」. Proceedings of Su-

Scott.

the Twenty-Fourth International Symposium on Computer
Architecture, pages 157-169, Denver, CO, June 1997.

[8]

[1]

MichaelShared Memory on Low-Latency,
Remote-Memory-Access Networks」. Proceedings of[9]「 Performance
Evaluation of Two Home-Based Lazy Release Consistency Protocols for Shared Virtual Memory Systems」. Proceedings of the Operating Systems Design and

Yuanyuan Zhou, Liviu Iftode and Kai Li.

Implementation Sysmposium, October 1996