K.Sasada's Home Page

こめんとのついか

こめんとこめんと!

message

please add long comment :).

_23(Sat)

IPAX の大量の招待券が来た。これをどうしろというんだ。

誰か、要る? タイムインターメディアにどかっと持っていくかなあ。


学校の机の上が大変なことになっている。なんとか資料を整理しようと思ってるんだが・・・。

ちなみに、家の机の上はもっと大変なことになっているんだが、見ないふり。


そういえば、先日森さん(LSI-C 作った人)としゃべってたんだけど「高橋メソッドって(略)」と言われた。


花見で使ったシートを干していたのを忘れていて夜回収。


しまった。コーヒー切れてたんだ。


proc1(int self){
  int start = MAX/PC_NUM * self;
  int end   = MAX/PC_NUM * (self+1);
  TYPE result = 0;
  int i;
  
  for(i=start; i<end; i++){
    result += A[i] * B[i];
  }
}

と、

proc2(int self){
  TYPE result = 0;
  int i;
  
  for(i=self; i<MAX; i+=PC_NUM){
    result += A[i] * B[i];
  }
}

ベクトルの内積を求めるプログラムを並列化する proc1 と proc2(これらの関数が PC_NUM分並列に走る)ですが、どっちが速いでしょう。キャッシュのヒット率に気をつけて答えてください。

ちなみに、キャッシュは 2way set associative。

TYPE はとりあえず double。


いや、proc2 のほうが速いと思ったんだよー。なんで proc1 のほうが速いのー。何を間違えてるんだろう。俺。

proc1 よりも proc2 のほうが、キャッシュのミス回数が多い。なんで?


なんとなく、仮説はたったんだが、うーん。本当かなあ。


そういえば、「故郷から10000光年」やっと読み終わった。すげー読みづらかった。何個か飛ばしちゃったし。


すみません,大事なことを書き忘れていました.並列単位はそれぞれキャッシュを共有します.この条件がないと,全然違う話になっちゃいますね.


proc3(int self){
  TYPE result = 0;
  int i, t;
  
  for(i=ITER*self; i<MAX; i+=ITER*PC_NUM){
    for(t=0; t<ITER, i<MAX; t++, i++){
      result += A[i] * B[i];
    }
  }
}

でxx(論文ネタ)すると速いことが発覚.

まぁ,世の中そんなもんだよな.

あれ,おかしいな.こういうことを紹介する論文じゃなかったはずなんだけど・・・(というかか,こんなんじゃ駄目だろぅ).

というか,xxなんて,もう既にきっと発表されてるんだろうなぁ・・・.でも,探したところ,見つからなかったし.うーむ.


要するに,並列単位あわせてのワーキングセットを狭くしたいんですよ.キャッシュを共有するから.

で,ブロック分割型の並列化は,ワーキングセット広くなっちゃうよね,だから狭くしたほうがいいんだよ,というのが1997年の論文に出ているのです.

そんなこと気にしたくネーヨ,という人は,キャッシュなんか共有しちゃいけないのです.で,そうやってる Intel HyperThreading なプロセッサはダメダメなのです.いや,使う側が,って意味だけど.icc は随分この辺を頑張ってる(はず)なんだけどね.


で,proc1 よりも proc2 のほうが遅くなったのは,proc2 だと各並列単位で変なところを指しやすくなる(不確定)ので,ワーキングセットが大きくなるからだと思う.

では,なんで proc3 だと速くなるのか?


答え.各イテレーションが ITER だけ短くなるから.ウワーン.

正しくはこちら.

proc3modified(int self){
  TYPE result = 0;
  int i, t;
  
  for(i=ITER*self; i<MAX; i+=ITER*(PC_NUM-1)){
    for(t=0; t<ITER, i<MAX; t++, i++){ // ここで i+=ITER していた
      result += A[i] * B[i];
    }
  }
}
_mput(Sat Apr 23 23:13:55 JST 2005)

 そんなことより関数の型をちゃんと書いてください

_maeda(Sun Apr 24 01:12:03 JST 2005)

 ちゃんと考えてないけどproc1のほうがふつーに速いんじゃないのか、という気がするが。空間的局所性とか。false sharingとか。

_通りすがり☆(Sun Apr 24 01:17:58 JST 2005)

キャッシュラインサイズ(特に 2 次キャッシュの方)が分かりませんが、配列A[i], B[i] を read したときに配列の後続のデータもキャッシュ(prefetch)されますが、proc2 のように cyclic にアクセスすると、キャッシュ(prefetch)した効果がなくキャッシュミスが proc1 より多くなるかと。


好きなだけ長いコメントをどうぞ。

お名前


back

tton 記述が使えます。YukiWikiな記述してりゃ問題ありません。

「行頭に#code」 と、「行頭に#end」 で挟むと、その間の行は pre で囲まれます。プログラムのソースを書くときに使ってください。

例:

#code

(なんかプログラム書く)

#end

リンクは

[[なまえ|http://www.example.org]]

とか

[[http://www.example.org]]

で貼れます。

$Date: 2003/04/28 10:27:51 $