ネットワーク仮想化機構とその評価
佐藤充, 田中英彦
東京大学 工学系研究科
東京都文京区本郷 7{3{1概要
並列計算機上で複数のユーザをサポートするための機構として, ハード ウェアを用いたネットワークノード番号変換を用いることを提案する. ハード ウェアによる変換を行なう
ことによって, 頻繁に生じるであろう相互結合網経由の通信を高速に行なうことができ,分散共有メモリシステムにも対応できる. このようなノード番号変換を行なうと, 複数のノード を単一ノード として扱うことによって, 等価的に相互結合網とノード とのスループットをあげることができる. 本稿ではネットワーク仮想化機構の概念について述べた
後, 簡単な評価結果についても報告する.

Virtual Network System and its Preliminary Evaluation
Mitsuru SATO, Hidehiko TANAKA
School of Engineering, the University of Tokyo
7{3{1 Hongo, Bunkyo-Ku, Tokyo

Abstract
We propose the hardware system which supports multi-user system on parallel computers. Translation of network node ID with hardware makes communications throughinterconnection network fast and supports distributed shared memory.

By using thismechanism, we can tolerate multiple node as a single node, and this makes throughput
between interconnection network and node fast.

In this paper, we describe concept of

Virtual Network System and report result of preliminary evaluation of Virtual NetworkSystem.

11 はじめにア, および相互結合網ハード ウェアに大きく依存するものである.

数値演算を主な目的とした並列計算機は, 高速なネット汎用の並列計算機を考えた場合, ハード ウェアの汎用性,ワーク, 高速な要素プロセッサなどによって徐々に実用的なレベルに達しようとしている. しかしその一方で, 汎用ソフトウェアの移植性, 既存の技術を容易に利用できるな的な並列計算機はまだまだ一般に浸透しているとはいい

どの点から, 要素プロセッサとして一般に用いられている難い.

高性能 RISC プロセッサを用いるのが適切であると思われ

近年のワークステーション・クラスタなどの流行は, ポーる. この高性能 RISC プロセッサは, 基本的に逐次的な流タビリティーを保ちつつ高速性や経済性を重視した並列シれの計算を前提としており, プログラムの持つ時間的・空ステムに対する要求を示していると言えるであろう. にも間的局所性を利用して, レジスタやキャッシュなどによりかかわらず, 並列計算機がその役割を果たしていないのは,性能を向上させている. したがって, これらのプロセッサ

現在の並列計算機システムにいくつか欠けているものがあでのタスクスイッチのオーバーヘッドはかなり大きく, 計るためであると考えられる. それらは, たとえば算を効率良く行なうための処理の粒度はある程度以上大きくなければならない.

 複数ユーザが利用できる環境
 ユーザが扱いやすい並列プログラミング環境

2.3

マルチユーザ環境

並列計算機の資源を複数のユーザが同時に利用する方法などである.

としては, 時間的分割と空間的分割の 2 つの方法が考えら

これらの問題を解決するためのハード ウェアサポートれる. 時間的分割は, 単一プロセッサでマルチユーザを実として, 本稿では「ネットワーク仮想化機構」を提案する.

現する場合と同様に, タイムスライスによって複数ユーザ

このネットワーク仮想化機構は簡単なハード ウェアを用いを切替える方法である. 一方, 空間的分割は, PE 空間を各て, これまでの並列計算機では実現できなかった上記の問ユーザに分け与え, それぞれの領域を単一のユーザが利用題を解消するための仕組みである.

するものである.

以下では, まず研究の背景およびネットワーク仮想化機

時間的分割では, スイッチのためのオーバーヘッドが単構について述べ その後にシミュレーションによる簡単な一プロセッサの場合に比べて大きくなる. システムの規模予備評価とその結果について述べる.

が大きくなるほど, このスイッチのためのオーバーヘッド

2 背景は大きくなる.

,

2.1

また, 汎用のシステムにはさまざまな規模の処理が実行

汎用並列計算機される. 処理の中には規模の大きなものから小さなもの,数値演算が主な目的である計算機は, その規則性を利用またそれらのもつ並列度もさまざまに分布しているであろしてできる限りの高速化を行なう. しかし汎用計算機では,うことが予想される. 前節で述べた最適な計算粒度を考慮

定型的な問題から非定型的な問題まで扱わなくてはならな

すると, 小さな規模の計算では, たとえ並列度が大きくてい. また問題の規模についても, 小さな問題から大きな問も小数の PE で計算を実行した方が全体の利用効率が高く題まで効率良く扱えなくてはならない. したがって, 汎用なることが予想される. つまり, それぞれの処理に応じてのシステムでは, 単純にシステム全体を使ってひとつのア空間的分割を行なうことが, 全体の効率を向上させること

プ リケーションを最適に実行するというわけにはいかず,につながる.

全体的な効率を考えて実行しなくてはならない.
2.2

以上のことから, 本研究で対象とするシステムは, 基本

並列計算機における粒度コント ロール的に各ユーザに適当な PE を割り当てる空間的分割による一般に, 並列計算機上でプログラムを効率良く実行する複数ユーザのサポートを行なうことを考える. 当然のことためには 計算の粒度を適切に設定することが必要である

ながら, レイテンシ隠蔽などのためにさらに時間的分割も粒度が小さ過ぎると, 実際の計算よりもタスク (スレッ併用することも考えられるが [2], 空間的分割が基本にある,[1].

ド ) の切替のオーバーヘッドが大きく, 効率がよくない. 逆ということを前提とする.に大き過ぎると, 充分に並列度を利用することができず, 並列計算機としての利点を活かせない. 適切な粒度は計算機
アーキテクチャ, 特に要素プロセッサと通信用ハード ウェ

2

3 ネット ワーク仮想化機構

タベースシステムのように本質的に通信を頻繁に行な

ネット ワーク番号変換

うアプリケーションでは, 通信のレイテンシが全体の3.1計算時間を左右する場合がある. そこでハード ウェア

ひとつの並列計算機上に複数のユーザを空間的に共存さインプ リメントによる高速な処理が有効となる.
 分散共有メモリを利用した場合にも機能する

せるには, これまでは相互結合網にパーティショニング機能を設け, そのハード ウェアに頼って分割する方法がとら

分散共有メモリは, 細かな通信を行なうのに適したシれてきた.

ステムである. しかし, 通信というインタフェースがしかしこの方法では,メモリアクセスに一元化されるために, OS やライブ

 静的な分割しかできない 相互結合網のトポロジに依存した分割しかできないラリなどが途中で介在する余地がなくなってしまう.
したがってハード ウェアでの実現が必須となる.などの問題点があり, 実際に利用しても, 台数の少ない, 独などが挙げられる. 逆に, 複雑なハード ウェアを用意しな立した並列計算機が複数あるようなイメージを提供するにければならないという欠点も生じる. この欠点に対してとどまっていた.

は, 実用上少量の簡単なハード ウェアで実現できることをそこで 空間分割をソフトウェア的に行なう方法が考え,第 3.5 節で説明する.

られる. すなわち, 相互結合網へのアクセスがある度にテー

このネットワーク仮想化機構を用いて, ユーザが他のノーブル引きを行ない, 物理的空間ではなく論理的な空間を提ド に対するアクセスを行なった時の様子を図 1 に示す.

供するというものである. したがって, このテーブルを更新するだけで, 動的にマッピングを変更することができ, 柔軟性が向上するという利点が生じる. また, ハード ウェア

012345789が提供する物理トポロジを直接見せるのではなく, 論理的なトポロジ空間をユーザに提供することができる.
このようなテーブル引きの機構は, たとえばメッセージ

6

パッシングライブラリのようなライブラリレベルで提供し10たり, オペレーティングシステムで提供したり, ハード ウェ
アで提供したりと, さまざまなレベルのものが考えられる.
本稿では, この中でハード ウェアを用いた手法を提案す

図 1: Accessing to Another Nodeる. すなわち, MMU(Memory Management Unit) のよう
3.2に, ハードウェアによりテーブル引きを行ない, ネットワー
ク上でのアド レス ノード 番号 変換を行なう方法である().

アド レス変換

前節で説明したように, ハード ウェアによるネットワー

以下では, 各ノードに物理的に割り振られている番号をクノード番号変換は, ネットワーク空間上におけるアド レ「物理ノード番号」, 各ユーザから見たノードの番号を「論ス変換と位置付けることができる. システムがグローバル理ノード 番号」と呼ぶ. この用語を用いると, このテーブなメモリ空間を提供している場合, このネットワーク空間ル引きは論理ノード番号から物理ノード番号への変換と言上におけるアドレスはメモリアド レスそのものになる. こい直すことができる. これを「ネットワークノード番号変の場合, ネットワークノード 番号変換とは, アド レス変換換」と呼ぶ.の一部となる [3].

このネットワークノード番号変換をハード ウェアで実現

ネットワークノード番号変換は, ネットワークノード 番することのメリットは,号+ メモリアドレスをアドレスとした一括型のアドレス変換と比較すると, ネットワーク空間上におけるアド レスと 頻繁に生じるであろうノード間通信を高速に実現することができるメモリアド レスとを区別しているという点が違っている.
これは,大きなブロック転送を主とする通信では, メッセージ想化するのにライブラリまたは OS レベルで変換する ローカル/ リモートというのは物理的に大きな違いであるだけでも充分実用的であろう. しかし, たとえばデー ネットワーク空間とメモリ空間は違う資源である

パッシングをベースにし, ネットワークイメージを仮3といった観点によるものである. すなわち, すべてをアド3.4

ト ポロジ変換レスという形で一元化してしまうより, ネットワーク空間仮想ネットワーク機構は, あるユーザの利用する範囲内とメモリ空間を別に分けて管理した方が管理しやすく, パで自由に論理ノード番号をつけることができる仕組みであフォーマンス・チューニングもやりやすいであろうというると言い替えることもできる. すなわち, 物理的な接続を考えに基づいている.

気にしなければ1 ユーザに対して自由なネットワーク空間3.3

ノード 番号エイリアスを提供できるということである.

このようなネットワーク仮想化を行なうと, 任意の物理

たとえば, 図 3 のように相互結合網の一部を User1 とノード番号に適当な論理ノード番号を割り振ることができUser2 が分割して利用している場合を考える. User1 のもる. ひとつの例として, 複数の物理ノード 番号に同一の論

つ空間は物理的には不規則な形をしているが, これに論理理ノード 番号を割り当てた場合を考える. この場合, シス

ノード 番号としてテムの物理構成は図 2 のようになる.

(0, 0), (0, 1), (0, 2),(1, 0), (1, 1), (1, 2),(2, 0), (2, 1), (2, 2)という (0, 0) から始まる規則的なものを与えることによって, User1 は自分のもつ空間があたかも, 閉じたトー
Local
MemoryNetwork
RouterNetwork
RouterNINIラスのように扱うことができる.

Network
Router
Local
MemoryUser2 も同様に, あたかも自分の持つ空間が木構造をしているかのようにアクセスすることができる.

NIPEPEUser2

図 2: Node Number Alias
論理ノード 番号!物理ノード 番号の変換に適当なキー(メモリアドレスの一部のビットなど) を付け加えると, そのノード に到達するための経路を複数作ることができる.
その結果としてネットワークとノード間のスループットをUser1向上させることができる.
この方式は, 相互結合網のスループットを物理的に向上させる方法とは違い, ソフトウェア的にテーブルの書き換えのみで行なわれるので, 高い柔軟性を持つ. たとえば,相互結合網自体には変更を加えず, 各ノード に 2 つずつのネットワーク・インタフェースを持たせることによって,容易にネットワーク・ノード間のスループットを等価的に

図 3: Topology Translation倍にすることができる また ネットワークトラフックの.

,高い特定のノード のみ, ネットワーク・ノード間のスルー

このようなトポロジ変換は, OS または言語において, 記プットを向上させ, 全体の効率をよくするということも,述しやすい形でネットワーク空間を扱うことができるといテーブルの書き換えのみで行なうことができる.

う点で有用である. しかし一方で, MIMD 的に fork を繰また逆に, ひとつの物理ノード 番号に対して複数の論理り返して並列実行するようなモデルでは意味がない. この

ノード 番号を与えることもできる. この場合, いわゆる仮仕組みが有効であるかどうかは, どのような実行モデルを想プロセッサを実現していることになる. ただし, この場採用するか, またどのようなプログラミングスタイルで並合はすべてハード ウェアに任せるというわけにはいかず,列プログラムを記述するかによって大きく違ってくる.
1 たとえば, パケット型の相互結合網において, Virtual Cut Throughなどのルーティング技術を用いれば, 相互結合網でのホップ数が増えてもレイテンシは高々数クロックしか増えない

メッセージを受信したノード が, そのメッセージはどの論
理ノード番号宛かを調べる必要がある.
4

3.5

実現のためのハード ウェア構成

4.2

評価項目

これまで述べてきた, ハード ウェアによるネットワーク評価は, ネットワーク番号エイリアスによる性能向上にノード番号変換を実現するための仕組みは 他のノード へついて行なった. ここでは, ノードと相互結合網とのスルーのアクセスを検出してテーブル引きを行なうという単純なプットのみを向上させて, どのくらい全体の性能向上に寄動作だけで実現できる.

与するかについての確認を行なった.

,

5 評価結果大規模な並列計算機になると, ノードの数が大きくなり,必要なテーブルも大きくなる. しかし, 本研究では前提とアプリケーションとして行列演算 (行列とベクトルの積)して空間分割による複数ユーザのサポートを考えているのを実行した. NR と NIU の間のスループットを向上させて,で, ハード ウェアの内部に持たせなくてはならないテーブ

アプ リケーションの実行時間 (計算時間のみ), および NR

ルは, 現在 active なユーザの空間 (それほど頻繁に変化はと NIU の稼働率を測定した. 横軸は NR{NIU のスルーしない), および OS の空間のみである. それ以外はメモリプットで, 1 が相互結合網の NR 間のスループットと同じ,に追い出し, メモリのアド レス変換と同様に TLB という2形で保持すればよい. したがって, ハード ウェアで持たなはその 2 倍, 以下 8 倍まで増加させている. また, NR の稼働率は, NR が自ノード に対して送らなくてはならない

くてはならないテーブルのサイズはかなり削減することがパケットを持っている時にだけカウントしている (つまり,できる.

通過するだけのパケットが NR 内部に存在していても稼働

このユニットはグローバルな共有メモリを実現する際にしているとは見なさない).

も役立てることができる. ネットワークノード番号変換とともにメモリアド レス変換機能を持たせることによって,グローバルメモリアド レスを扱うことが可能になる.

34 予備評価
Speedup

仮想ネットワーク機構の実現性を示すために, 予備評価を行なった. 本章では, その結果を示し, 仮想ネットワー
ク機構の有用性について確認する.
4.1

2

1

評価環境

評価はシミュレーションによって行なった. 図 4 に示す構

01

造のソフトウェアシミュレータを作成し アプリケーション
,

2

4

5

6

7

8line throughputを実行してその実行時間によって評価した. シミュレータは,
Processor Emulator(PE), Network Interface Unit(NIU),
Network Router(NR), Local Memory(LM)3

図 5: Execution Timeから構成される. 他のノードへのアクセスのためのインタフェースは, メ
モリアクセスをベースに実現されている (分散共有メモリシ0.7ステム). 相互結合網としては, RDT(Recursive Diagonal0.6を用いた.
NODE

rate of workTorus)[4]PROGRAMPELOCALMEMORY

NIU0.50.4
0.30.2

NIU0.1

NR0NR

Interconnection
Network1234567line throughput

図 6: rate of NR and NIU's work time

図 4: Structure of Simlulator58

図 5 から, 相互結合網とノード の間のスループットを向この手法はハード ウェアでネットワークノード番号変換上させると, あるレベルまでは良く性能が向上しているこを行ない, それぞれのユーザごとに別々の空間を提供するとがわかる. この原因は, このアプ リケーションが相互結ものである. この手法では,合網に多大な負荷をかけており, ノードと相互結合網のや

 ソフトウェアで変換を行なうのに比べて高速に変換でりとりが計算時間を決定しているからである. それは図 6きるからわかる. スループット 1 のところでは, NIU の稼働率

 他のユーザ空間との間でプロテクションを実現できるに比べて NR の稼働率がかなり高くなっていることがわか ネットワークエイリアスを利用することによってノードと相互結合網との間のスループットをソフトウェアる. これはノード に送らなくてはならないパケットを持っているのに, ノード とのスループットが低くてパケットが的に向上することができる詰まっている状態を表している. NR{NIU 間スループット

 ユーザに対して論理的なトポロジを提供できるを向上させると差は縮まり, 実行時間は短くなる. スルーという特徴がある.

プット 5 を越えると, もはやパケットが詰まるということはなくなり, NIU の稼働率は一定値に達し, 性能向上は止また, シミュレータを用いた予備評価を行なった. その結果, ネットワークエイリアスによるノード ・相互結合網まる.
このように, 相互結合網とのやりとりが頻繁なアプ リ間のスループット向上によって相互結合網およびノードのケーションでは ノードと相互結合網のスループットを向負荷が均等化され, 性能向上に寄与できることがわかった.

上させることによってあるところまでは性能向上が図れる

謝辞,ことが確認された.

本研究を行なうにあたって, シミュレータ製作および性6 問題点と今後の課題
本手法では解決できていないいくつかの事項がある

能測定に協力していただいた富士通の三吉貴史氏および日立製作所の吉平健治氏に感謝します.

.

参考文献

 物理的な相互結合網の分割
本手法では, ノード番号変換を行なうことによってプ[1]

日高康雄, 小池汎平, 田中英彦. PIE64 における複合粒ロテクションを実現するが, パケットがルーティング

度並列処理を用いた最適粒度制御 {細粒度並列と粗粒の都合で他のユーザの領域に侵入することまでは防ぐ

度並列; 二つの異質な世界の分離と融合{. 並列処理シことはできない. ネットワークトラフィックが小さい

ンポジウム JSPP'95 論文集, pp. 115{122, 1995.

場合は問題ないが, あるユーザが相互結合網に多大な[2] Anoop

負荷をかけている場合は, そのパケットの侵入が問題chorloo,になる可能性もある.

Gupta,Todd

Comparative トポロジ変換の有効性
論理トポロジを元にプログラムを最適化してしまう

JohnHennessy,Mowry,andevaluation

tolerating techniques.

Inof

KouroshGhara-

Wolf-DietrichWeber.

latency

reducingand

The 18th Annual Inter-national Symposium on COMPUTER ARCHITEC-と, ネットワークトラフィックや通信のタイミングなTURE CONFERENCE PROCEEDINGS,どによって, 逆に性能が低下してしまう可能性もある.

Vol.

19,

pp. 254{263, May 1991.

またトポロジを意識したプログラミングが果たして有効なのかという疑問もある.

[3]

松岡浩司, 岡本一晃, 廣野英雄, 横田隆史, 堀敦司, 児玉祐悦, 佐藤三久, 坂井修一. 超並列計算機 RWC-1 にまた今回の測定も, 特定の場合のみについて測定したもおける. 情報処理学会研究報告 93-ARC-101, Vol. 93,のであり, 決して一般的な結果であるとは言えない. そのNo. 71, pp. 17{24, 1993.

ため, さらに一般的なアプ リケーション, ネットワークで測定する必要がある.

[4]

7 まとめ

楊愚魯, 天野英晴. 超並列向きのプロセッサ結合網の提案. 情報処理学会計算機アーキテクチャ研究会報告,
No. 96-20, October 1992.

本稿では, マルチユーザ環境の元で, ネットワーク空間を仮想化する手法について提案し, その予備評価を行なった.

6