c++ - boost :: detail :: spinlock_poolでの偽共有？

Question

私はこのSOの質問に出くわし、それを読んで最終的に私はを見るようになりましたboost::detail::spinlock_pool。

の目的は、のアドレスをハッシュしてsのboost::detail::spinlock_pool配列から選択することにより、グローバルスピンロックの潜在的な競合を減らすことです。これは妥当な解決策のようですが、現在の（Boost v1.49）バージョンの実装に問題があるようです。spinlockshared_ptr

spinlock_poolspinlock41個のインスタンスの静的に割り当てられた配列を管理します。私がsizeof(spinlock)==4調べたプラットフォームの場合、つまり、64バイトのキャッシュラインを備えたx64では、spinlockキャッシュラインごとに16秒になるようです。

つまり、アレイ全体が21/2キャッシュラインすべてにまたがっています。

つまり、あるランダムなスピンロックが別のスピンロックと誤って共有される可能性が40％あります。

...そもそもプールの目的をほぼ完全に無効にします。

私の分析は正しいですか、それとも重要な何かが欠けていますか？

更新： 私はついに小さなベンチマークプログラムを書きました：

#include <boost/shared_ptr.hpp>
#include <boost/thread.hpp>
#include <boost/timer.hpp>
#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

enum { BufferSize = 1<<24,  SLsPerCacheLine = 1 };

int          ibuffer[BufferSize];

using boost::detail::spinlock;
size_t nslp = 41;
spinlock* pslp = 0;

spinlock& getSpinlock(size_t h)
{
  return pslp[ (h%nslp) * SLsPerCacheLine ];
}


void threadFunc(int offset)
{
  const size_t mask = BufferSize-1;
  for (size_t ii=0, index=(offset&mask); ii<BufferSize; ++ii, index=((index+1)&mask))
  {
    spinlock& sl = getSpinlock(index);
    sl.lock();
    ibuffer[index] += 1;
    sl.unlock();
  }
};


int _tmain(int argc, _TCHAR* argv[])
{
  if ( argc>1 )
  {
    size_t n = wcstoul(argv[1], NULL, 10);
    if ( n>0 )
    {
      nslp = n;
    }
  }

  cout << "Using pool size: "<< nslp << endl;
  cout << "sizeof(spinlock): "<< sizeof(spinlock) << endl;
  cout << "SLsPerCacheLine: "<< int(SLsPerCacheLine) << endl;
  const size_t num = nslp * SLsPerCacheLine;
  pslp = new spinlock[num ];
  for (size_t ii=0; ii<num ; ii++)
  { memset(pslp+ii,0,sizeof(*pslp)); }

  const size_t nThreads = 4;
  boost::thread* ppThreads[nThreads];
  const int offset[nThreads] = { 17, 101, 229, 1023 };

  boost::timer timer;

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii] = new boost::thread(threadFunc, offset[ii]); }

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii]->join(); }

  cout << "Elapsed time: " << timer.elapsed() << endl;

  for (size_t ii=0; ii<nThreads; ii++)
  { delete ppThreads[ii]; }

  delete[] pslp;

  return 0;
}

2つのバージョンのコードをコンパイルしました。1つは。 SLsPerCacheLine==1、もう1つはSLsPerCacheLine==8。です。MSVS 2010を使用して最適化された32ビット、4コアXeon W3520 @ 2.67Ghz（ハイパースレッディング無効）で実行。

これらのテストから一貫した結果を得るのに苦労しました。50％までの誤ったタイミング変動が時折観察されました。ただし、平均して、バージョンはサイズ41のスピンロックテーブルを備えたバージョンSLsPerCacheLine==8よりも約25〜30％高速であるように見えます。SLsPerCacheLine==1

これがコア数、NUMA、ハイパースレッディングなどでどのように拡張されるかを確認するのは興味深いことです。現在、この種のハードウェアにはアクセスできません。

score 14 · Accepted Answer

簡単に

スピンロックが異なるキャッシュラインにある可能性があるときに、スピンロックが同じキャッシュラインを共有しているという点で、あなたは正しいです。別名偽共有。また、異なるキャッシュラインにロックを割り当てることで、パフォーマンスがいくらか向上する可能性があります（ただし、以下を参照）。

ただし、これはロックの競合と同じではありません。ロックの競合は、1人の男がロックを保持していて、他の1人以上の男がそれにアクセスしたい場合に発生します。

つまり、spinlock_poolには、同じキャッシュラインに共存するロックが原因でキャッシュラインの競合が発生します。しかし、それは（減少した）ソフトウェアロックの競合を持っています。

ソフトウェアロックの競合の減少は、ほぼ間違いなく良いことです。

ベンチマークがある程度示しているように、キャッシュラインの競合はおそらく少し痛いですが、ソフトウェアロックの競合と比較すると2次的な影響です。

詳細

バックグラウンド

まず、いくつかの背景：

従来のスピンループは、テストアンドテストアンドセットです。

    loop: 
         tmp := load( memory_location_of_sw_lock )
         if( is_locked(tmp) ) goto loop
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop
     got_the_sw_lock:
          ...
          ... critical section
          ...
          // release the lock, e.g.
          memory_location_of_sw_lock := 0

テストアンドセットのスピンロックもあります。

    loop: 
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop

これらは、キャッシュ、ライトスルー、またはライトバックを備えたほとんどの最新のメモリシステムで非常に悪いパフォーマンスを示す可能性があります。（私が提案したハードウェア最適化のいくつかは、テストアンドセットスピンループをテストアンドテストアンドセットスピンループと同じくらい速くしますが、それらは小さいのでわずかに速くなります。）

ここでのロックには2つの異なる概念があることに注意してください。スピンロックが取得する「ソフトウェア」ロックと、Intel LOCKINCmemやCMPXCHGなどのatomic_hw_locked_rmw命令によって使用されるハードウェアロックです。後者についてはあまり気にしませんが、通常はソフトウェアロックを保持しているキャッシュラインに無条件に書き込み、キャッシュラインの他のコピーを無効にすることを知っています。（書き込みを条件付きにすることは、別の可能なハードウェア最適化です。）

O（N ^ 2）バーストのキャッシュミス（ソフトウェア）ロック競合

テストアンドテストアンドセットスピンループとのロック競合は特に悪いです。ウェイターは全員ロックを回し、ロックが解除されるとバスアクセスが急増します。1人の男が勝ち、他の男は負けたことに気づき、最終的には落ち着いて再びスピンします。このアクティビティのバーストは特に悪いです。なぜなら、N人の待機中の人（スレッド/プロセス/プロセッサ）の場合、バスアクティビティのバーストのサイズはO（N ^ 2）になる可能性があるためです。最悪の場合、全員がテストの一部を終了するからです。および-テストアンドセットスピンループ、およびx86 LOCK INC memやCMPXCHGなどのアトミックロックされたRMW（読み取り-変更-書き込み）命令を同時に実行しようとします。これは、最初の人を除いて全員がロックを取得しないためにロックを書き込む必要がない場合でも、最終的には全員が行を書き込むことを意味します。

例えば

Lock is held by P0
P1-PN are spinning in test-and-test-and-set spinloops waiting for it.

P0 releases the lock, e.g. by writing it to 0

P1's "test-" instruction reads the lock
...
PN's "test-" instruction reads the lock

All of P1-PN see the lock as released, 
   so they fall out of the "test-" part of the spinloop which uses ordinary instructions
   to the test-and-set part of the spinloop, which uses a hardware atomic RMW like LOCK INC mem

P1's locked RMW happens, and acquires the spinlock for P1
   It invalidates all other cache lines
   P1 goes away and does something with the data protected by the lock

P2's locked RMW fails to acquire the spinlock
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

P3's locked RMW fails
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

...

PN's locked RMW fails

そして今、少なくとも、残りのすべてのP2..PNプロセッサは、テストスピンループに対して通常のロック解除されたキャッシュミスを実行する必要があります。これは、少なくともN +（N-1）個のキャッシュミスを意味します。ロックの取得に失敗するウェイターによる書き込みごとに、他のすべてのウェイターがロック解除された読み取りを実行するようにトリガーする可能性があるため、かなり悪化する可能性があります。つまり、タイミングによっては、

   1 release the lock
   N reads to test- the lock
   1 locked atomic RMW to acquire the lock
   N reads...
   for each of the remaining N-1 processors
      1 locked RMW that fails to acquire the lock
      N reads

これはO（N ^ 2）です。または、プロセッサMの場合、1つのロックされたRMWに続いて、2..Mの読み取りが行われます。これはまだO（N ^ 2）です。

これはこの質問にとってどういう意味ですか？

OK、真のロック競合があった場合、競合するロックが解放されると、このO（N ^ 2）バーストのキャッシュミスが発生します。

ただし、spinlock_poolは、ウェイターを複数のロックに分散させます。スピンロックプールにSロックがある場合、ウェイターははるかに少なくなります。おそらくN / Sよりも少なくなります（同じロックを共有する人の数で競合が超線形になる傾向があるため）。

つまり、Boostのspinlock_poolを使用すると、競合の量が1/41になり、おそらくそれより少なくなると単純に予想できます。

spinlock_poolは、shared_pointerごとにロックを設定すること、共有ポインターのサイズを増やすこと、およびすべてのshared_pointersが同じロックを共有することの間の妥協点であることを忘れないでください。したがって、shared_pointerのスピンロックでの競合は、（a）真の競合、または（b）spinlock_pool内の同じエントリへの独立したハッシュであるshared_pointersによって引き起こされる誤った競合である可能性があります。

さて、はい、N人のウェイターがいる代わりにN / 41人のウェイターしかいない場合でも、バーストはO（（N / 41）^ 2）またはO（N ^ 2）です。しかし、Nが通常41未満の場合、あなたはその考えを理解します。

基本的に、shared_Pointersを複数のspinlock_poolエントリに分散させるためのハッシュは、競合の量をすばやく減らします。

しかし...スピンロックは同じキャッシュラインに住んでいますか？そうです...しかし、他のキャッシュラインのウェイターは、スピンループのテストアンドセット部分に進みません。

つまり、M人のウェイターと競合するロックがM人の他のプロセスとキャッシュラインを共有している場合、M*Nトラフィックを取得します。ただし、ハッシュによってMがO（1）に減少した場合、トラフィックはN個しか得られません。

そして、ほとんどの場合、他のウェイターがまったくいない場合は、ロック解除時にO（1）ラフィックのみを取得します。

ボトムライン：

ソフトウェアロックの競合を減らすことは、ハードウェアキャッシュラインの競合を引き起こすキャッシュの偽共有を減らすよりも、パフォーマンス面ではるかに高いメリットがあります。

さて、同じキャッシュラインにそれほど多くのspinlock_poolエントリをパックしないのは難しいという利点がまだあるかもしれません。しかし、これは決して明白ではありません。これは経験的な質問です。つまり、実験を実行する必要があり、ワークロードによって異なります。

同じキャッシュラインでこれらのロックを誤って共有すると、問題が発生する場合があります。典型的な例は、プロセッサの実行キューを保護するロックです。

同じキャッシュラインでこれらのロックを誤って共有するとよい場合があります。これにより、プリフェッチがキャッシュで行うのと同じ利点が得られます。たとえば、shared_pointersの配列を割り当て、人々が通常aosptr [i]にアクセスしてから、aosptr [i+1]などにアクセスするとします。

それはすべてあなたのワークロードに依存します。私はそれが両方の方向に落ちるのを見ました。通常、私の経験では、キャッシュラインごとに1つのロックの方が優れていますが、それほど多くはありません。

もっと楽しく

ご参考までに、テストアンドテストアンドセットスピンループのハードウェア最適化は、私のMS論文「バス放棄ロックを含む同期プリミティブの機能分類法」の主題でした。これは、バーストを排除したハードウェア更新キャッシュプロトコルです。バスアクセスの。University Microficheを除いて、正式な出版物には掲載されていません。

私の仕事は、Tアンダーソンによる「共有メモリマルチプロセッサのスピンロック代替のパフォーマンス」という論文に触発されました-並列および分散システムでのIEEEトランザクション、1990年。

有名なMCSロックを含め、ほとんどの出版物はソフトウェア、アルゴリズムに関するものであると言っても過言ではありません。このような手法は、理論的には一般的ですが、ジャーニーマンのプログラマーにはほとんど使用されていないと言っても過言ではありません。

ちなみに、ここではさらにいくつかのハードウェアの最適化が可能です。たとえば、CMPXCHGはロックをまったく書き込む必要はありません。残念ながら、現在のIntelハードウェア、または少なくとも1991年に設計したIntelハードウェアでは、まだ使用されていると思いますが、ハードウェアロック（アトミックロックされたRMWの実装に使用される）を解放する唯一の方法は、特別なものを使用することです。マイクロコードは「store-unlock」と書き込みます。ちなみに、マイクロコードはLoadLinked / StoreConditional（LL / SC）を使用することもでき、ナイーブなLL/SCが一部のスレッドで前進しない状況ではロックにフォールバックします。

Intelが最近これを修正した可能性があります。私は2009年にIntelを去りました。1991年以来、Intelを修正、改善、最適化しようとしていました。そして、Intelは最近ロックのパフォーマンスを大幅に改善しています。しかし、彼らは主に非競合ロックのパフォーマンスに取り組んでおり、競合ロックのパフォーマンスを最適化していないと思います。

同様に、Alain Kagiは、彼の論文といくつかの出版物、および特許http://www.google.com/patents/US6460124で、賢明な遅延を追加することにより、キャッシュハードウェアがスピンロックをキューロックと同じくらい効率的にできることを示しています。

これらのハードウェア最適化のいくつかは、テストアンドセットスピンループをテストアンドテストアンドセットスピンループよりも優れたものにします。

最新の開発は、HLE（Hardware Lock Elision（Ravi RajwarはUWiscでこれに取り組み、私とAlain Kagiはそこにいましたが、同期の作業はUIUCで以前に行われました））とRTMで構成されるIntel TSX（Transactional Synchronization Extensions）です。（制限付きトランザクションメモリ）。これらは両方とも、競合しないものを支援します..うーん、誤って競合している競合するロックを支援します。たとえば、独立したものを保護する粗いグレインロックなどです。つまり、誤ったロックの競合です。いくつかの点で、HLEはspinlock_poolを不要にする場合があります。

謝罪

申し訳ありませんが、「ソフトウェアロックの競合を減らすことは、スピンループのハードウェアキャッシュラインの競合よりもはるかに重要である可能性があります」という長い答えを提供しました。

キャッシュラインごとに1つのスピンループを割り当てることである程度のパフォーマンスが得られると思いますが、それは小さい場合があり、一部の非常に珍しいワークロードでは損失が発生する場合もあります。

そして確かに、あなたはそれを測定しなければならないでしょう。

ただし、いずれの場合も、ソフトウェアロックの競合を減らすことで大きなメリットが得られます。

c++ - boost :: detail :: spinlock_poolでの偽共有？

1 に答える 1

Related

Reference