baycedar commented 1 year ago

ちょっと気になるものを見つけたので共有（後でちゃんとしたPDFも共有します）．この論文の2.3節によると，同じキャッシュラインに連続で書き込む際にflushを使うと劇的に遅くなるとあります．今の提案手法では記述子を各スレッドで専有するので，記述子の準備中にこれと同じパターンが発生します．一方で，microsoft/pmwcasは1回毎に別の記述子を使うのでランダムアクセスの方のパターンになり，このおかげで性能の劣化を免れているんじゃないかと疑っています．

まず，今まで読んできてもらったPMEM系のサーベイ論文に，これと類似した記述はありましたっけ？もし再現性のある結果なら，これの解消を頑張るのは価値がありそうです．

Streaming（non-temporal）storeは，実装的にはpmem_memcpyで実現できるはずです．CASによる同時実行制御が必要な部分では使えないので，AddPMwCASTarget，status_，target_count_あたりが使いどころかと思います．例えばAddPMwCASTargetなら以下のような感じじゃないかと思います．

  template <class T>
  constexpr void
  AddPMwCASTarget(  //
      void *addr,
      const T old_val,
      const T new_val,
      const std::memory_order fence = std::memory_order_seq_cst)
  {
    constexpr auto kNTStore = PMEM_F_MEM_NONTEMPORAL | PMEM_F_MEM_NODRAIN;

    assert(target_count_ < kPMwCASCapacity);

    PMwCASTarget target{addr, old_val, new_val, fence};
    pmem_memcpy(&targets_[target_count_++], &target, sizeof(PMwCASTarget), kNTStore);
  }

ちょっと後ででいいのでこの件を調査および試してみてもらえますか？

baycedar commented 1 year ago

ただ，これをやるとキャッシュに乗らないのでそれはそれでどうなんだろうとは思っています．論文中の実験はwrite onlyで読んでなさそうなので，実用的なワークロードで考えるとちょっと？な感じはあります．

manabinohibi commented 1 year ago

ありがとうございます．似たような話だと，前に紹介した論文にDouble Flush Latencyについての記述がありました（4.3.2）．ただこの結果はnon-temporal storeでも比較的高いレイテンシが出てますね．

manabinohibi commented 1 year ago

ただ，これをやるとキャッシュに乗らないのでそれはそれでどうなんだろうとは思っています．論文中の実験はwrite onlyで読んでなさそうなので，実用的なワークロードで考えるとちょっと？な感じはあります．

低コンテンション環境ならnon-temporalが生きるかなとなんとなく思ってましたが… （ベンチマークの構造やマルチスレッドでのキャッシュの利用を把握しきれていないので何とも言えませんが）

baycedar commented 1 year ago

ちょっと試しにいくつかpmem_memcpyで置き換えれそうなところを置き換えてみたんですが，全く変わらず（ないしちょっと遅くなって）ダメですね．CPU命令の問題ではない気がします．実装的にはこの辺が落とし所っぽいですが，論文が一通りかけたら色々調査してみてください．

あとは，1点大事なこととして，interleaved構成での実験はしておいた方がよいですね．今はPMEM1枚しか使っていない（non-interleaved）ので，namespaceの設定から変更して，1ソケット最大4枚まで使って実験したほうがよいです．可能ならCPUソケットを跨いで8枚全部使えたらベストですね．

baycedar commented 1 year ago

あと，実験結果でもう出てるかもしれませんが，single CASなら自前とmicorsoftとで同じくらいの性能なんですよね．原因を推察するためのヒントになりそうですが，いまいち謎です．

baycedar commented 1 year ago

また気になったんでちょっとperfでボトルネック検証をしてみました．1スレッドと28スレッドでは使っている時間の割合がそこまで変わらないのに対し，28から56ではstoreにかかっている割合が大きく増えてPMwCAS関数内の処理の割合も微増という感じでした．どう解釈するかは難しいとことですが，PMEMアクセスの部分で詰まってそうな感じはあるので，interleavedな構成にして複数枚に並列で書けるようになったら解消しないかなぁという期待はあります．

1スレッド

-   51.46%     0.22%  pmwcas_bench  pmwcas_bench         [.] PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                       ▒
   - 51.24% PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                                                                        ▒
      - 35.27% dbgroup::atomic::pmwcas::PMwCASDescriptor::PMwCAS                                                                                                                                                                                                                                  ▒
         - 17.89% dbgroup::atomic::pmwcas::component::PMwCASTarget::RedoPMwCAS                                                                                                                                                                                                                    ▒
              8.69% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::store                                                                                                                                                                                                           ▒
         - 4.71% dbgroup::atomic::pmwcas::component::PMwCASTarget::EmbedDescriptor                                                                                                                                                                                                                ▒
              0.86% 0x7f5261643e92                                                                                                                                                                                                                                                                ▒
              0.56% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::compare_exchange_strong                                                                                                                                                                                         ▒
           0.51% dbgroup::atomic::pmwcas::component::PMwCASTarget::Flush                                                                                                                                                                                                                          ▒
      - 12.61% dbgroup::atomic::pmwcas::PMwCASDescriptor::Read<unsigned long>                                                                                                                                                                                                                     ▒
           12.41% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::load                                                                                                                                                                                                              ▒
      + 1.23% std::unique_ptr<dbgroup::atomic::pmwcas::DescriptorPool, std::default_delete<dbgroup::atomic::pmwcas::DescriptorPool> >::operator->                                                                                                                                                 ▒
      + 1.16% dbgroup::atomic::pmwcas::PMwCASDescriptor::AddPMwCASTarget<unsigned long>

28スレッド（1socket physical cores）

-   58.26%     0.22%  pmwcas_bench  pmwcas_bench         [.] PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                       ▒
   - 58.05% PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                                                                        ▒
      - 37.14% dbgroup::atomic::pmwcas::PMwCASDescriptor::PMwCAS                                                                                                                                                                                                                                  ▒
         - 18.90% dbgroup::atomic::pmwcas::component::PMwCASTarget::RedoPMwCAS                                                                                                                                                                                                                    ▒
              11.47% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::store                                                                                                                                                                                                          ▒
         - 6.94% dbgroup::atomic::pmwcas::component::PMwCASTarget::EmbedDescriptor                                                                                                                                                                                                                ▒
              3.21% 0x7fb0b0e0be92                                                                                                                                                                                                                                                                ▒
              0.59% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::compare_exchange_strong                                                                                                                                                                                         ▒
      - 18.00% dbgroup::atomic::pmwcas::PMwCASDescriptor::Read<unsigned long>                                                                                                                                                                                                                     ▒
           17.81% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::load                                                                                                                                                                                                              ▒
      - 1.12% dbgroup::atomic::pmwcas::PMwCASDescriptor::AddPMwCASTarget<unsigned long>                                                                                                                                                                                                           ▒
           0.53% dbgroup::atomic::pmwcas::component::PMwCASTarget::PMwCASTarget<unsigned long>                                                                                                                                                                                                    ▒
      + 0.93% std::unique_ptr<dbgroup::atomic::pmwcas::DescriptorPool, std::default_delete<dbgroup::atomic::pmwcas::DescriptorPool> >::operator->

56スレッド（1socket physical/logical cores）

-   61.71%     0.26%  pmwcas_bench  pmwcas_bench         [.] PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                       ▒
   - 61.44% PMwCASTarget<dbgroup::atomic::pmwcas::DescriptorPool>::Execute                                                                                                                                                                                                                        ▒
      - 47.14% dbgroup::atomic::pmwcas::PMwCASDescriptor::PMwCAS                                                                                                                                                                                                                                  ▒
         - 26.16% dbgroup::atomic::pmwcas::component::PMwCASTarget::RedoPMwCAS                                                                                                                                                                                                                    ▒
              19.58% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::store                                                                                                                                                                                                          ▒
         - 3.59% dbgroup::atomic::pmwcas::component::PMwCASTarget::EmbedDescriptor                                                                                                                                                                                                                ▒
              0.88% 0x7f1b83d5de92                                                                                                                                                                                                                                                                ▒
      - 12.79% dbgroup::atomic::pmwcas::PMwCASDescriptor::Read<unsigned long>                                                                                                                                                                                                                     ▒
           12.60% std::atomic<dbgroup::atomic::pmwcas::component::PMwCASField>::load                                                                                                                                                                                                              ▒
        0.78% dbgroup::atomic::pmwcas::PMwCASDescriptor::AddPMwCASTarget<unsigned long>

manabinohibi commented 1 year ago

いろいろとありがとうございます．取り急ぎinterleaved構成での実験をすべきですね．ちょっとやってみます．（うまく設定できるかわからないのですが．三輪さんにお願いしたほうが早いかも）

manabinohibi commented 1 year ago

あと気になったのですが，僕が測定するとスループットが56スレッドで4.0Mくらいなんですが，https://github.com/dbgroup-nagoya-u/pmwcas/pull/23#issue-1551749043 ではもっと出てるのでなんか測定方法が不適当ですかね？

num_execは1000000で，ノード０固定です．

baycedar commented 1 year ago

@manabinohibi すみません，ボケてました．Interleavedについてはregion構成時（サーバ起動前）にやってある話で，すでに4枚でのinterleaved構成です．

あと気になったのですが，僕が測定するとスループットが56スレッドで4.0Mくらい

すみません，これは言葉足らずでした．自分は2wCASでやってるので，3wCASならそのくらいだと思います．

manabinohibi commented 1 year ago

Interleavedについてはregion構成時（サーバ起動前）にやってある話で，すでに4枚でのinterleaved構成です．

なるほど，そうなんですね．となると8枚での構成が測定すべき項目ですかね？

自分は2wCASでやってるので，3wCASならそのくらいだと思います．

了解しました．自分の方でも1とか2とかで計測してみます．

baycedar commented 1 year ago

実験についてですが，あとやれるのはqueueを実装して測るのと，poolsetを用意して複数ソケットで走らせる（ソケット0のPMEM/pmem0と1のPMEM/pmem1を作ったので，これらの下にバラしてpoolsetを用意したらたぶん8枚使える？）のとくらいですね．（poolsetはトラブルがなければすぐ動きそうですが）ひとまず修論を一旦完成させるの優先で，終わったら試してみてください．

あと，まだ原稿を送っていなければ石川先生にも現状を共有しておいてください．

manabinohibi commented 1 year ago

ありがとうございます．了解しました．測定結果はまとめ次第，一度共有します．

石川先生にも現時点での原稿を送っておきます．

manabinohibi commented 1 year ago

スループットの測定結果を共有しておきます！

3ワードPMwCAS
- skew=0：throughput-3words-low.pdf
- skew=1：throughput-3words-high.pdf
1ワードPMwCAS
- skew=0：throughput-1word-low.pdf
- skew=1：throughput-1word-high.pdf

baycedar commented 1 year ago

ありがとうございます．時間があったら16以降は8刻み（および物理コア数の28）で測っておいてもらえますか？

それはそれとして，スレッド数が少ないうちは自前の方が速いので，基本的な手続きの効率性では当然ながら良くなっているはずです．となるとスレッド数が増えたことによる何かしらの競合が性能低下の原因のはずですが，謎です．交換ワード数を増やすことでだんだん遅くなってるので，やはり普通に交換先である配列上で発生しているなにかしらの競合な気はしますが，それだとmicrosoft/pmwcasで性能が低下しないのがよくわかりません．（この点をはっきりさせるために，交換ワード数（1, 2, 3, 4, 6, 8くらい？）を横軸に取った実験を追加したほうがよい気はします．）

ただ1点だけ，以前PMwCAS同士の競合がほぼ発生していない（1%未満くらい）なのは確認したんですが，microsoft/pmwcas側のread時の補助については確認してないことを思い出しました．ひょっとすると，競合が少なければread時に別の記述子を見つけて上手いこと補助できているのかもしれません．一応，PMEM上ではflushのための待ち時間がかなり大きいので，後追いで処理しても追い越せる（CASに失敗したらflushなしで次のワードのCASに移れる）可能性がDRAM上よりも高いという理由付けもできはしますし．

manabinohibi commented 1 year ago

時間があったら16以降は8刻み（および物理コア数の28）で測っておいてもらえますか？

了解です．不足分を追加で測定します．あと，スループットと同じ条件でレイテンシも測定はしてあります．

ひょっとすると，競合が少なければread時に別の記述子を見つけて上手いこと補助できているのかもしれません．

なるほど．それはあるかもしれないですね…

manabinohibi commented 1 year ago

@baycedar 対象ワードを変えながらスループット測定したので，共有しておきます．（取り急ぎ数値データです，すみません）

PMwCAS（ダーティフラグなし）

1word
pmwcas,0.0,56,1.28184e+07
pmwcas,0.0,56,1.28085e+07
pmwcas,0.0,56,1.28335e+07
pmwcas,1.0,56,5.28686e+06
pmwcas,1.0,56,5.32057e+06
pmwcas,1.0,56,5.264e+06
2words
pmwcas,0.0,56,6.50267e+06
pmwcas,0.0,56,6.50369e+06
pmwcas,0.0,56,6.50458e+06
pmwcas,1.0,56,2.60346e+06
pmwcas,1.0,56,2.67478e+06
pmwcas,1.0,56,2.59256e+06
3words
pmwcas,0.0,56,4.08158e+06
pmwcas,0.0,56,4.07816e+06
pmwcas,0.0,56,4.07723e+06
pmwcas,1.0,56,1.67928e+06
pmwcas,1.0,56,1.62907e+06
pmwcas,1.0,56,1.6516e+06
4words
pmwcas,0.0,56,3.04753e+06
pmwcas,0.0,56,3.04671e+06
pmwcas,0.0,56,3.04692e+06
pmwcas,1.0,56,1.14599e+06
pmwcas,1.0,56,1.1738e+06
pmwcas,1.0,56,1.19443e+06
6words
pmwcas,0.0,56,1.9561e+06
pmwcas,0.0,56,1.95711e+06
pmwcas,0.0,56,1.95459e+06
pmwcas,1.0,56,596414
pmwcas,1.0,56,622473
pmwcas,1.0,56,651233
8words
pmwcas,0.0,56,1.38459e+06
pmwcas,0.0,56,1.37759e+06
pmwcas,0.0,56,1.37628e+06
pmwcas,1.0,56,364168
pmwcas,1.0,56,486571
pmwcas,1.0,56,491279

microsoft/pmwcas

1word
microsoft-pmwcas,0.0,56,1.29672e+07
microsoft-pmwcas,0.0,56,1.30716e+07
microsoft-pmwcas,0.0,56,1.30601e+07
microsoft-pmwcas,1.0,56,815100
microsoft-pmwcas,1.0,56,828219
microsoft-pmwcas,1.0,56,834551
2words
microsoft-pmwcas,0.0,56,9.88217e+06
microsoft-pmwcas,0.0,56,9.86836e+06
microsoft-pmwcas,0.0,56,9.88735e+06
microsoft-pmwcas,1.0,56,429515
microsoft-pmwcas,1.0,56,367124
microsoft-pmwcas,1.0,56,458402
3words
microsoft-pmwcas,0.0,56,7.58631e+06
microsoft-pmwcas,0.0,56,7.58955e+06
microsoft-pmwcas,0.0,56,7.57088e+06
microsoft-pmwcas,1.0,56,277553
microsoft-pmwcas,1.0,56,227700
microsoft-pmwcas,1.0,56,234792
4words
microsoft-pmwcas,0.0,56,6.22489e+06
microsoft-pmwcas,0.0,56,6.22388e+06
microsoft-pmwcas,0.0,56,6.2612e+06
microsoft-pmwcas,1.0,56,186186
microsoft-pmwcas,1.0,56,179051
microsoft-pmwcas,1.0,56,180746
6words
microsoft-pmwcas,0.0,56,4.96452e+06
microsoft-pmwcas,0.0,56,5.0258e+06
microsoft-pmwcas,0.0,56,4.98644e+06
microsoft-pmwcas,1.0,56,112981
microsoft-pmwcas,1.0,56,112839
microsoft-pmwcas,1.0,56,104905
8words
microsoft-pmwcas,0.0,56,4.06086e+06
microsoft-pmwcas,0.0,56,3.97339e+06
microsoft-pmwcas,0.0,56,3.96417e+06
microsoft-pmwcas,1.0,56,67649.9
microsoft-pmwcas,1.0,56,

microsoft/pmwcasの方は低コンテンション環境ならそこまでスループットが落ちない気がします．あと，これは体感なんですがmicrosoft/pmwcasは競合が多いと終了しないことがしばしばあります．実際に8wordsの測定を3回試したのですがどれも完了しないままでした（出力結果はその名残です）．実装の問題な気もしますが…

manabinohibi commented 1 year ago

@baycedar

スループットを測定しなおしたので，グラフを共有しておきます！

3word PMwACS

skew=0
skew=1

1word PMwCAS

skew=0
skew=1

今気づいたんですが，1wordの低コンテンションだと16スレッドまでダーティフラグあった方がちょっと高いですね．

また，https://github.com/dbgroup-nagoya-u/pmwcas/issues/24#issuecomment-1403261171 のグラフも貼っておきます．

skew=0
skew=1

baycedar commented 1 year ago

競合が少ないと安定して2倍くらい遅いんですね．修論のほうに実験結果を追加してもらったらまた細かく確認します．

baycedar commented 1 year ago

改めてソースコードを眺めてたらやっと原因がわかりました．microsoft/pmwcasのバグです．交換後にflushする対象が実際に交換しているワードのアドレスじゃなくて記述子上のワードアドレスを保持しているメンバ変数のアドレスを指定していて，配列上のものを一切永続化せずひたすら記述子だけ永続化しているからです．ここの &address_ を address_ に変えてあげれば予想通りの結果が出ます．

baycedar commented 1 year ago

こんな感じです．

sugiura@giants:~/workspace/cpp/pmwcas-benchmark
: (add-our-pmwcas *%) 09:12:11 [EXIT=0]
$ numactl -N 0 -m 0 ./build/Release/pmwcas_bench --pmwcas --microsoft-pmwcas --num-thread 1 /pmem_tmp/sugiura/
*** START PMwCAS ***
...Prepare workers for benchmarking.
...Run workers.
...Finish running.
Throughput [Ops/s]: 332915
*** FINISH ***

*** START microsoft/pmwcas ***
...Prepare workers for benchmarking.
...Run workers.
...Finish running.
Throughput [Ops/s]: 130719
*** FINISH ***

sugiura@giants:~/workspace/cpp/pmwcas-benchmark
: (add-our-pmwcas *%) 09:13:31 [EXIT=0]
$ numactl -N 0 -m 0 ./build/Release/pmwcas_bench --pmwcas --microsoft-pmwcas --num-thread 28 /pmem_tmp/sugiura/
*** START PMwCAS ***
...Prepare workers for benchmarking.
...Run workers.
...Finish running.
Throughput [Ops/s]: 4.48425e+06
*** FINISH ***

*** START microsoft/pmwcas ***
...Prepare workers for benchmarking.
...Run workers.
...Finish running.
Throughput [Ops/s]: 3.38566e+06
*** FINISH ***

sugiura@giants:~/workspace/cpp/pmwcas-benchmark
: (add-our-pmwcas *%) 09:13:59 [EXIT=0]
$ numactl -N 0 -m 0 ./build/Release/pmwcas_bench --pmwcas --microsoft-pmwcas --num-thread 56 /pmem_tmp/sugiura/
*** START PMwCAS ***
...Prepare workers for benchmarking.
...Run workers.
...Interrupting workers.
...Finish running.
Throughput [Ops/s]: 4.07302e+06
*** FINISH ***

*** START microsoft/pmwcas ***
...Prepare workers for benchmarking.
...Run workers.
...Interrupting workers.
...Finish running.
Throughput [Ops/s]: 3.58195e+06
*** FINISH ***

manabinohibi commented 1 year ago

ありがとうございます！急いでmicrosoftの結果だけ急いで測定し直します．ちょっと安心しました．

manabinohibi commented 1 year ago

@baycedar

すみません．そこだけいじったらセグフォが発生してしまいました．そのあと元に戻してもクローンしなおしてもセグフォになっちゃうのですが，なにか考えられる原因ってありそうですかね… これだけ報告してもよくわからないかもしれませんが，めっちゃ焦ってるので思いつくこととかあれば教えてほしいです．

baycedar commented 1 year ago

@manabinohibi 一旦対象のPMEM上のディレクトリを削除してもダメですか？また，セグフォはほぼ確定で発生するか数回に1回かも教えて下さい．

baycedar commented 1 year ago

あと，今動かしてないならgiantsにログインしてこちらでも確認するのでいってください．

dbgroup-nagoya-u / pmem-atomic

Non-temporal storeによるスケーラビリティの改善 #24

1スレッド

28スレッド（1socket physical cores）

56スレッド（1socket physical/logical cores）