集中共有メモリ型並列計算機　�

天野英晴

共有メモリ型計算機

• 共有するメモリに対する読み書きでデータ交換を行う
• 並列OSが動作する→従来のコンピュータと同じに見える
• プログラムを高速化するには並列化が必要
• プログラマによる明示的並列化（OpenMPなど）
• 並列化コンパイラ
• 理解のポイント
• メモリの構造をどうするか？
• 同期をどうするか？
• キャッシュの一貫性をどうするか？

​

１．メモリの構造をどうするか？�集中メモリ型と分散メモリ型

Node　１

Node　2

Node　３

Node　０

Ｉｎｔｅｒｃｏｎｎｅｃｔｏｎ

Ｎｅｔｗｏｒｋ

プロセッサ

メモリ

メモリが一か所に集中

UMA(Uniform memory access model)

いわゆるマルチコア

メモリが分散

NUMA(Non-Uniform memory access model)

​

CPU

L1キャッシュ

L2キャッシュ

L3キャッシュ

SRAM

主記憶

DRAM

～64KB　1-2clock

～256KB 3-10clock

2M～16MB 10-20clock

16～256GB 50-100clock

記憶の階層

​

高速小容量の

CPUの近くに置き

よく使うデータを入れておく

​

そこになければより遅い

大容量メモリに取りに行く

補助記憶　（2次記憶）

μ-msecオーダー

数TB

チップ内メモリ

ソフトウェアから

は透過

（トランスペアレント）

OSが管理

実際はどうなっているか？

CPU

North

Bridge

South

Bridge

Graphics

DRAM

USB

Ether

Legacy I/O

PCI/PCIexpress

Memory Controller HUB

I/O Controller HUB

L1

L2

L3

チップ

単純にCPUを増やして共有キャッシュ

CPU

North

Bridge

South

Bridge

Graphics

DRAM

USB

Ether

Legacy I/O

PCI/PCIexpress

Memory Controller HUB

I/O Controller HUB

L1

L2

L3

CPU

CPU

CPU

混雑がひどくて

やってられない

チップ

Consistency Problem ����������������������

CPU

North

Bridge

South

Bridge

Graphics

DRAM

USB

Ether

Legacy I/O

PCI/PCIexpress

Memory Controller HUB

I/O Controller HUB

L1

L2

L3

CPU

CPU

CPU

L1

L2

L1

L2

L1

L2

プライベートキャッシュを持つ方法

データの不一致問題

（Coherence Problemが起きる）

チップ

Snoop Cacheの装備 ����

CPU

North

Bridge

South

Bridge

Graphics

DRAM

USB

Ether

Legacy I/O

PCI/PCIexpress

Memory Controller HUB

I/O Controller HUB

L1

L3

CPU

CPU

CPU

L1

L2

L1

L1

Snoop Cacheで

一致問題を解決

Bus

Crossbar

チップ

集中共有メモリをどう繋ぐか？

• 集中メモリ型
• 共有バス：
• 一度に一つのプロセッサのみ転送可能
• ボトルネックになるので小規模なシステムに限られる
• スヌープキャッシュに利用できる→後程解説
• クロスバスイッチ
• バスの拡張として理解できる
• 大容量の転送バンド幅を確保できる
• ハードウェア量が大きい

​

共有バスの構造

Multiplexer

バスの基本は共通の

信号線、しかしこれは

もうあまり使われない。

バスの本質は、唯一のモジュールがデータを送信できること

色々な形の共有バスがあり得る

バス上のデータ転送

• アービトレーションを行ってバスマスタを選ぶ
• バストランザクション
• アドレス転送
• データ転送　(必要回反復)
• 終了操作
• バスマスタ権の解放

アービタ（調停装置）

．．

Priority Encoder

Arbiter

集中アービタ

H

Distributed bus

Daisy Chain

分散アービタ

オンチップでは集中アービタを主として使う

From

CMOS VLSI Design

by Weste and Harris

集中

アービタ

=

プライオリティ

エンコーダ

バス上のデータ転送とアービトレーション

アービトレーション

データ転送

n

n-1

bus master for

n-th transaction

n

n+1

n+1

bus master for

n+1-th transaction

n+2

n+1

bus master for

n+2-th transaction

n+3

アービトレーションはバス上のデータ転送とオーバーラップする

バス上のデータ転送

Strobe

Address/

Data

Acknowledge

Clock

最初と最後にハンドシェークを取る。その間はクロックに同期して連続転送

アドレストランザクション

データトランザクション

通常のデータ転送

メモリの読み出し

Module A

Module B

スプリットトランザクション

Module B

Module D

A→Bのトランザクションの間に

C→Dのトランザクションを実行→転送効率アップ

クロスバスイッチ

ｎ

ｍ

バスの交点に

スイッチを置く

クロスポイント数

ｎｘｍ

バスの拡張として考える

ことができる

​

同時に複数のプロセッサ

メモリ間が交信できる

ノンブロッキング

ｎ

ｍ

宛先が違えば

ぶつからない

宛先が同じだとぶつかる�Head Of Line (HOL) conflict

ｎ

ｍ

各バスにアービタが必要

バッファも必要

入力バッファ方式

Crossbar

Input buffer

アービタにより一つを選んで出力→最も一般的な方法

出力バッファ方式

Crossbar

動作速度をn倍にしなければならないため、実装は難しい

n倍の速度で動作する

出力バッファにデータを

格納

クロスポイントバッファ方式

ｎ

ｍ

バッファをクロスポイント

に置く方式。

性能は良いがハードウェア

量が大きい

キャッシュの一貫性問題

P

Main　Memory

Interconnection

キャッシュを分散すれば、当然それぞれのキャッシュで

データの不一致が生じる

A

A

A’

キャッシュ一貫性問題の解決

• キャッシュを分散する限り不一致は起きる
• いつでも一致させる
• コストは高いが共有メモリとして完全なモデルが実現できる→　Sequential Consistency
• 共有バスなどの「皆が見れる通信路」があればSnoop Cache
• 分散メモリ型ではDirectory方式が使われる
• 同期の時だけ一致を取る：緩いモデルも使われる。

​

復習：Write　Through　（Hit）

0011

…

…

0011010

Cache Directory

(Tag Memory)

8 entries X (4bit )

​

Cache

(64B=8bytes)

Main Memory

(1KB=128bytes)

​

Write Data

主記憶も同時に更新

From CPU

Write　Through　（Miss：Write Non-allocate）

0011

…

…

0011010

Cache Directory

(Tag Memory)

8 entries X (4bit )

​

Cache

(64B=8bytes)

Main Memory

(1KB=128bytes)

​

Write Data

主記憶のみ更新

From CPU

0000010

Write　Through　（Miss:Write Allocate）

0011

…

…

0011010

Cache Directory

(Tag Memory)

8 entries X (4bit )

​

Cache

(64B=8bytes)

Main Memory

(1KB=128bytes)

​

Write Data

From CPU

0000010

0000

復習：Write Back　（Hit）

0011

…

…

0011010

Cache Directory

(Tag Memory)

8 entries X (4bit+1bit )

​

Cache

(64B=8Lines)

Main Memory

(1KB=128Lines)

​

Write Data

From CPU

1

Dirty

復習：Write　Back　（Replace）

…

…

0011010

Cache Directory

(Tag Memory)

8 entries X (4bit+1bit )

​

Cache

(64B=8Lines)

Main Memory

(1KB=128Lines)

​

From CPU

0000010

0011

1

Dirty

0

0000

Write Throughのスヌープキャッシュ

P１

Main　Memory

A　large　bandwidth　shared　bus

Ｉ：Invalidated

Ｖ：Valid

Ｖ

Ｖ

ライトスルー時のスヌープによる無効化

P１

Main　Memory

A　large　bandwidth　shared　bus

Ｉ：Invalidate

Ｖ：Valid

Ｖ

Monitoring (Snooping)

Ｖ→

I

基本プロトコル

P1

Main　Memory

共有バス

キャッシュの各ブロックの状態

C：Clean (主記憶と一致)

D: Dirty

I：Invalidate：無効

C

C

バス上では、一度に

一つのデータ転送が

行われる

同じキャッシュブロックを読み出すと、両方共Cleanになる。

P3が書き込み無効化

P1

Main　Memory

共有バス

I

C

C

D

書き込みを行う

Clean→Dirtyに変化

共有バス上に書いたアドレスを送り

コピーを無効化

全てのキャッシュがバスを

見ており（スヌープ）、アドレスが

一致すると無効化

P1が読み出しをした場合

P1

Main　Memory

共有バス

C

C

I

D

共有バス上のアドレスを見て、アドレスが

一致してDのブロックへの読み出し要求を

検出→共有メモリに書き戻してからデータを

要求元に転送→Cleanになる

P1が読み出すとミスが起き、

主記憶に共有バスを通して取りに行く

Cleanになる

P1が書き込みをした場合

P1

Main　Memory

共有バス

I

D

I

D

P1が読み出すとミスが起き、

主記憶に共有バスを通して取りに行く

書き込みを行ってDirtyになる

共有バス上のアドレスを見て、アドレスが

一致してDのブロックへの書き込み要求を

検出→共有メモリに書き戻してからデータを

要求元に転送→I（無効）になる

I

C

D

​

read

Replace

​

write hit

Invalidate

​

write miss

Replace

​

read miss

Replace

​

read miss

Write back

& Replace

​

write miss

Write back

& Replace

​

write

Replace

CPUの要求

I

C

D

​

write miss for the block

​

Invalidate

​

read miss for the block

バススヌープによる遷移

基本プロトコルの状態遷移図

スヌープキャッシュの構造

Cache　Memory

実体

Directory

Directory

一致を取る

Dual　Port

CPU

共有バス

Directoryは、

両側からアクセス

可能

​

CPUとは関係なく

バスのTransaction

をチェックすること

ができる

Exclusive状態の導入�（MESIプロトコル）

P１

Main　Memory

A　large　bandwidth　shared　bus

各ブロックの状態

CE：Clean　Exclusive

CS：Clean　Sharable

DE：Dirty　Exclusive

I：Invalidate

最初のPUが読み出す

Exclusive:それが唯一のコピーである

CEになる

MESIプロトコル

P１

Main　Memory

A　large　bandwidth　shared　bus

CE：Clean　Exclusive

CS：Clean　Sharable

DE：Dirty　Exclusive

I：Invalidate

Snoop

Snoop

2つ目のPUが読み出し：CSになる

CEの効果

PU

Main　Memory

A　large　bandwidth　shared　bus

CE：Clean　Exclusive

CS：Clean　Sharable

DE：Dirty　Exclusive

I：Invalidate

→DE

CE→DEは、無効化信号を必要としない。

たったこれだけ？？？？

でも結構大きい

Ownershipの概念

Ownership→書き戻しに責任を持つ

OS:Owned　Sharable　OE:Owned　Exclusive

US:Unowned　Sharable　I：Invalidated

P１

Main　Memory

A　large　bandwidth　shared　bus

US

主記憶と一致

しているので

US

MOSIプロトコル

Ownership→responsibility of write back

OS:Owned　Sharable　OE:Owned　Exclusive

US:Unowned　Sharable　I：Invalidated

P１

Main　Memory

A　large　bandwidth　shared　bus

US

US

MOSIプロトコル（PUの書き込み）

PU

US

Main　Memory

A　large　bandwidth　shared　bus

→OE

→I

無効化信号がバスを流れる

コピーは無効（I)になる→基本プロトコルと同じ

snoop

しかし、ここで

Ownerになる

MOSIプロトコル

PU

OE

Main　Memory

A　large　bandwidth　shared　bus

PUがOwnerが居るブロックに読み出しを要求

snoop

MOSIプロトコル

P１

OE

Main　Memory

A　large　bandwidth　shared　bus

→OS

書き戻しは行わない

メモリでなく、Ownerがブロックを供給

キャッシュ間転送が起きる。US,OS共に主記憶と一致しない

書き戻しはOwnerがリプレイスされる時だけ！

→　US

MOESIプロトコルクラス

Owned

Exclusive

O：

Owned

M:

Modified

E：

Exclusive

Valid

S：Sharable

I：

Invalid

EもOも含めた5つの状態を持つことができる

O: OS　M:OE　E:UE　S:USのことなので注意！

まとめ

• スマフォ、ノートPCの全て、サーバー、スーパーコンピュータの多くが共有メモリ型計算機
• ポイント
• 高速化のためには並列化が必要
• プログラマによる並列化→来週OpenMPの演習を行う
• コンパイラによる自動並列化
• 共有メモリを使ったデータ交換には同期が必要
• 不可分命令
• バリア同期
• 分散したキャッシュの一貫性制御
• スヌープキャッシュ
• ディレクトリキャッシュ

演習2

• P1,P2,P3が同じキャッシュブロックについて以下の操作を行った際の各キャッシュの状態を求めよ。ただし、基本プロトコルを利用する。無効化信号がバス上に流れるのはどのタイミングか？初期状態は全てーとする。
• 　　　　　　　　　　　　P1　　　P2　　　P3
• 　　　　　　　　　　　　－　　　　ー　　　－
• P1が読み出し　　　
• P2が読み出し
• P1が書き込み
• P3が読み出し
• P2が書き込み
• P1が読み出し

​

​

次回の演習のために