MEMORY ACCESS BUFFERING IN MULTIPROCESSORS

MEMORY ACCESS BUFFERING
IN MULTIPROCESSORS
米澤研究室M1 増山隆
概要



バッファリングとSequencial consistencyの
相性の悪さ(問題提起)
Weak Consistencyの提唱
単純なモデルで性能評価

ここではSystem with shared global
mempory (System1のみ)
メモリアクセスのバッファリング

Prosessor環境内

Prefetch buffer




命令、オペランド
Store buffer
Memory buffer
interconnection内のbuffer
Sequential consistency
それぞれのプロセッサ内ではプログラム順
 すべてのプロセッサの操作がある逐次実
行と同じ結果を常に与える
by Lamport

共有データをprefetchできない
processor1
processor2
A:=0
…
A:=1 //event
B:=0
…
B:=1 //event S2(B)
LAB2: if(A=1)GOTO LAB2
//event L2(B)
<Critical Section>
B:=0
S1(A)
LAB1: if(B=1)GOTO LAB1
//event L1(B)
<Critical Section>
A:=0
Sequential → 排他制御かdeadlock
データのprefetchを行うとSCを満たさない
L1(B)→L2(A) →S1(A) →S2(B) 同時にCSへ
Memory system coherence

「最新のSTORE」の結果をLOADが返す
by Censier and Feautrier
いくつかのBUFFERにSTORE要求があるので、
「最新」の意味があいまい
メモリアクセスの段階の分類
initiating→issuing→performing
initiating→issuing
メモリ要求を出した時点。書き込み読み込みはま
だ行われていない。
 performing

Load
他のプロセッサのどのSTOREにも影響されない時点
 Store
他のプロセッサのどのLOADにも影響する時点

「最新」は「最後にperformされた」ということ
Strong ordering of storage
access
1.
2.
個々のプロセッサ内でメモリ要求はプログラム
順
Iの共有データへのSTOREがKから観察されて
いるとき、そのSTOREの前にIに関して
performedな共有データへのすべてのアクセス
はKに関してもperformedでなければならない
at the time when a STORE on global data by
processor I is observed by processor K,all
access to global data performed with respect
to I before the issuing of the STORE must
be performed with respect to K
(2)の必要性
S1(A)→L1(A)
S2(A)→L3(A)
⇒
S1(A) →L3(A)
もし、S1(A)がP3に対して
performedになるのが遅
かったら….
L3(A)は古いAを読みうる
⇒S1(A)がP3に関して
performedになるのを
待たなければならない
P1
S1(A)
L1(A)
P2
S2(B)
B
L3(B)
P3
A
L3(A)
問題点


同期に使われない変数に対しても依存性
をチェックするのは無駄
LOADが異なるアドレスにたいするSTORE
を追い越せない
Weak ordering





共有データを同期に使われるか否かで分類
同期プリミティブを用意(TEST_AND_SET …)
同期変数はstrongly ordered
同期変数がissueされる時点で他のアクセスは
performed。
同期変数がperformされるまで後のアクセスは
issueされない
Weak ordering
: 同期に使わない
: 同期に使う
System with shared global
memory
System with shared global
memory
tinref 一つのプロセッサ内の共有データアクセス間にかかる平
均時間
tp 共有データに触る間に行われる計算にかかる平均時間
tperform, tissue メモリ要求がperform,issueする最小の時間
Tm メモリバンクへのアクセス時間(メモリにバッファがあれば0)
tinref ≧ tp + tperform + Tm(no buffering)
tinref ≧ MAX[tp,tperform] (strong)
tinref ≧ MAX[tp,tissue] (weak)
性能
効率比較(MIPS比)
1.2
1
E
0.8
no buffering
strong ordering
weak ordering
0.6
0.4
0.2
0
0
1
2
3
tperform/tp
E = (It.c./Is.p.)=(tp/tinref)
4
5
It.c.:マルチプロセッサでのMIPS
Is.p.:シングルプロセッサでのMIPS
結論


パイプライン化され、メモリアクセスがバッファリ
ングされるとStrong orderingは効率が悪い
Weak Orderingを提唱、効率を上げる


メモリアクセスがバッファリングされる
プログラマ(コンパイラ)が同期に使用する変数を指定
する
参考文献

MEMORY ACCESS BUFFERING IN
MULTIPROCESSORS
Michel Dubois et al
1998,SIGARCH,ACM Press

Download Report