メモリ階層を考慮したチップマルチプロセッサでのOS とプロセスのスケジューリング

2N - 2

滝田 裕 † , 坂井 修一 † , 田中 英彦 ††東京大学大学院工学系研究科{takita,sakai,tanaka}@mtl.t.u-tokyo.ac.jp

1

はじめに
本稿では、マルチプロセッサシステムのメモリアク3

評価モデル

3.1

プロセス移動のコストセスに関するモデルを元に簡単なシミュレーションを行い、一般的な SMP や CMP, 複数の CMP を用いたマルチプロセッサシステムにおけるプロセス移動がおこ

CPU 間のプロセス移動の処理手順は図 2 のように行われる。

る場合の OS とプロセスのスケジューリングについて述べる。

2

CPU 1

CPU 2
割込

割込処理
(カーネル処理)

プロセス実行(ユーザーモード)

背景

プロセス転送要求

モード切替
待機

近年の CPU の高速化により、チップ外からのデータプロセス停止処理(特権モード)転送のコストは大幅に上がったが、今後もチップ外かタスク切替(カーネル処理)らのデータ供給能力と CPU 内の処理速度の差は広がるモード切替

一方である [1]。
一般的なシングルプロセッサシステムでも、トランプロセス停止通知

プロセス実行(ユーザーモード)

プロセスイメージ転送(カーネル処理)

タスク切替(カーネル処理)
モード切替

ザクション処理のような I/O 処理が多いアプリケーショ

プロセス実行(ユーザーモード)

ンでは性能に影響が出てきている [2] が、マルチプロ

図 2: プロセス移動処理の例

セッサシステムの場合は割込処理等によるプロセスの移動に伴い、キャッシュ上のデータを一旦メモリ書き戻

プロセス移動にかかる時間は、モード切り替え、プす必要がでるため、性能への影響がより大きい (図 1)。

ロセス停止にかかる時間と、プロセスイメージ転送にかかる時間がわかれば概算できる。

1) I/Oからの割り込み(ネットワーク, UI)

Unix では、ユーザープロセスによりシステムコールが呼ばれた時に、プロセス情報の保存のためにプロセCPU 1

CPU 2

キャッシュ

キャッシュ

ス停止処理と同様の処理を行っている。
そこで、実機 (OS: Linux-2.2.16, CPU: Celeron 533MHz)
上でシステムコールを 100 万回実行してシステムタイ

I/O 待ちプロセス

ムを計測し、一回のシステムコールの実行にかかる時間を算出した。表 1 は 10 回試行した結果の平均をとっ

2) プロセスのコピー(キャッシュからメモリ)
バススヌープできる
場合はキャッシュ間転送(点線)システムバス3) プロセスのコピー(メモリからキャッシュ)メインメモリ

図 1: 割込によるプロセスの移動
しかし、1 つのチップの上に複数の CPU を搭載した

CMP では、チップ間データ転送の頻度を下げることが可能である。
Processes and OS Scheduling Giving Consideration to Memory Hierarchy of Chip Multi Processor
Hiroshi TAKITA† , Shuichi SAKAI† , Hidehiko TANAKA†† Graduate School of Engineering, University of Tokyoたものである。
表 1: システムコールの実行時間 (単位: µs)
system callcache on cache oﬀ

getpid0.244

23.332

write(socket, 1KByte)

2.922

1122.68

システムコール getpid は特権モードにおいて変数の読み出しを行うだけなので、カーネルモード ↔ ユー
ザーモードの移行にかかる時間は一回のシステムコー
ルにかかる時間の半分、約 0.122 µs、クロックに直すと約 65 クロックと考えられる。

• 一定間隔でプロセス移動を伴う割込処理が、同一プロセスイメージ転送のコストは、L1, L2 キャッシュ

CPU またはランダムな CPU に与えらるを切り、強制的にメモリ上のデータを読み書きした場合と同じであると考えると、23.332 − 0.244 × 2 = 約

22.844 µs, 約 12000 クロックになる。
また、I/O からの割込処理を同じ I/O 処理ということで、UDP socket への書き込みで代用すると、約 1400 クロックとなる。

• プロセス移動では、プロセスの交換が行われる(プロセスの移動と同一クロックで処理)
結果は表 3 の通り。
表 3: 結果
転送要求 CPU

3.2 評価モデル

プロセッサの構成

fixedrandomプロセッサの構成として、一般的な SMP と CMP, 複

1CPU × 4

134624880.2

112393121.9

数の CMP を SMP 構成にしたものの 3 種類について考2CPU × 2102564280.0

100749722.0

える (図 3)。

4CPU × 1102564280.0 100749722.0(プロセス実行時間: 1 億 clocks, 割込間隔:100000clocks)

CPU

Cache

割込処理を行うプロセッサを固定にした場合、どの構成でも割込処理が増える分だけ遅くなる。CMP を用いた場合、1 つのチップに全ての CPU を載せたものと、メモリ2 つのチップに分かれているものとの間に全く差が見られなかった。

a) 1CPU x 4

CPU5

CPU

Cache

Cache

まとめ
本稿では、マルチプロセッサシステムのメモリアクセスに関するモデルを元に簡単なシミュレーションを行い、一般的な SMP や CMP, 複数の CMP を用いたマメモリメモリb) 2CPU x 2c) 4CPU x 1

図 3: CPU の構成

ルチプロセッサシステムにおけるプロセス移動がおこる場合の OS とプロセスのスケジューリングについて述
べた。今後、シミュレーションのパラメータを調整し、簡略化するため、評価モデルのパラメータは表 2 の値を利用し、転送要求を受けるプロセスや OS は全て実際の挙動に近いモデルを構築し、新たなスケジューリング手法についての検討を行う予定である。

チップ内のキャッシュに載っているものとする。
表 2: 評価モデルの構成
チップ間転送メモリを経由モード切替 + プロセス停止

100 clock

プロセス再開 + モード切替

100 clock

同一チップ: CPU 間プロセス移動

0 clock

異なるチップ: CPU 間プロセス移動

20000 clock

割込処理2000 clock

4

評価と考察
以下のような条件でシミュレーションを行った。

• 全ての CPU に同一の実行時間の異なるプロセスが動いている

参考文献[1] ITRS:
InternationalTechnology
Roadmapfor
Semiconductors,
2000
Update(2000).
http://public.itrs.net/Files/2000UpdateFinal/2kUdFinal.cfm.
[2] Barroso, L. A., Gharachorloo, K. and Bugnion,
E.: Memory System Characterization of Commercial
Workloads, The 25th International Symposium on
Computer Architecture , ACM and IEEE, pp. 3 -- 14(1998).