くそみそスーパースケール

ところでこいつを見てくれ。どう思う?

• • 1スレッド実行：計測時間4.807秒
  • 2スレッド実行：計測時間1.718秒 ( ×並列度=3.436 )

すごく…スーパースケールです…
※id:ange1:20100514の続きです。
とまあ。
いや、何が言いたいかというと、ちゃんとスーパースケールするんだなあと。
今回も、ですが、実用性は皆無です。単なる大道芸です。なお、環境も同じHarpertownです。

前回は、頻繁にアクセスする領域をコアで分割して上手くキャッシュに乗せるような筋書きでサンプルを作っていましたが、今回は次のようなシナリオを考えました。

• • 共有L2のアーキテクチャで、スレッド間で読み込み専用データを共有するというお題※affinityを指定して、L2を共有するコアのペアを固定で割り当てます
  • 共有データは巨大な配列で、それを毎回なめるような処理がメイン
  • シングルスレッドでやると、毎回キャッシュから捨てられるためキャッシュミスだらけ
  • しかし、マルチスレッドでタイミングをかみ合わせると、お互いがアクセスした領域がキャッシュに残っていて、ある程度キャッシュヒットする

では、実際のサンプルの概要に移ります。

用意した共有配列のサイズは64MB。配列をなめる処理を4000回やって約4.8秒。
ちなみに、4KBおきに8バイトだけアクセスという、キャッシュ的に凄くもったいないことをしています。L1もこの配列アクセスでは全く役に立ってません。
そうは言っても、これを配列サイズ1/16にしてL2に全て乗るようにすると0.06秒、実質5倍の速度になります。L2とメインメモリでも大きな性能差があるわけです。

で、肝心な処理ですが、配列のアクセスパターンを次のようにします。A1やB1というのは、それぞれメモリの領域だと思ってください。

• • A1,B1,A2,B2,A3,B3,…,An,Bn ( 奇数回目のループ )
  • B1,A1,B2,A2,B3,A3,…,Bn,An ( 偶数回目のループ )

シングルスレッドの場合、配列の後ろの方をアクセスする頃には、先頭の方は既にキャッシュから捨てられています。なので次のループでのアクセスもキャッシュミスだらけです。
しかし、2スレッドで上手くタイミングをかみ合わせると、相手がキャッシュフィルさせた分を再利用することで、キャッシュミスを減らせることが期待できます。
そこで出た結果が、冒頭に挙げた計測時間なわけです。

…しかしながら、これ、処理が全然かみ合わないと、キャッシュが全然再利用できず、メモリ読み込みがより辛くなるだけで散々な結果になります。
実際、2スレッド版を計測したとき、2.789秒 ( ×並列度=5.578 ) という結果も出ました。1スレッドだとブレは殆どないのですが、2スレッドだと計測時間の変動が結構あります。
処理を上手くかみ合わせるため、ループの開始をバリア同期で合わせているんですけどね。

ちなみに、バリア同期といっても、pthread_spin_lockによるちょっとしたビジーループです。pthread_barrier_waitではありません。
なぜかというと、ちょっと考えてみれば、GB/sオーダーの速度でキャッシュが入れ替わるでしょうから、6MBのL2が完全に入れ替えるのにmsオーダー。
一方、OSのタイマー制御でも精度はmsオーダー。なので、OSに頼っていたら、多分上手くかみ合わせるのは無理、ということで敢えてビジーループにするのが良いかなあ、と。

と、いう訳で、一応スーパースケールしましたよ、と。うん。色々実用性は無いと思いますが。
最後に、今回のサンプル一式のtar+bz2アーカイブを、BASE64エンコードしたものを貼っておきます。
展開の方法が分からなければ、id:ange1:20100515を参考に。

QlpoOTFBWSZTWZT9sdMABwl/x+x0AIB/f///f+/f////3/oABACBAQAAAIAIYAi+
+fIaAFAGihQAKApQHDQAA0Gg0BggBoaaZANDRpkAMQNABw0AANBoNAYIAaGmmQDQ
0aZADEDQAcNAADQaDQGCAGhppkA0NGmQAxA0ACU9SJFHqbKP1TEAeo9QyPUBmofq
ho0NNAAA0AAANqRSeKPU0NGmjRpoDQADIA0GQAANNAAAJEiAIyNExNTE00DRlNPS
TJ6nhNRp6m00j1MIZtUPUZqaHaH908qXj0Wc8GUIQjkwJJlECBK/wYKGEmcGGJSS
1giJ9w7lIBZSmkmCFcwCEgTESAaBFwYvr/NR4PcPom14l3Px93aobP8CLg3MHM9G
a8GJ/KsIrhtZCqRVpJJuayVUbGNviIqUhZlL4pRFrSK1XAWFFanPQsCgSdjf43K5
fVqWiXLfFLuk27BDJJCZLYZTh1iKxF8CLEqwNAbkmkIR/lJgCVbBICbDaiYDG05g
AVCGhI/Dr6tgXdjdhBV+ya3B7vldjzoD0rzU9qo+1odBskL246y7kxLcug7gM9HR
bPXBLW7PC5cxm8bpqXO70myAJjApgKNFopUv3+HPc0FeG7pg9Tzg2Pa12eQNTlVT
CuRU/o7wT5qea4naWWUkz9pOwQqEi+2aSmTGNMGEqSqlQVyCIpn4ZxrC477gc67a
xxJuIy5p3tYl3OeAIXmkh+EX6MYxsbG/QpoNjWtA01fAI3/7Fo+7CZQZ6LOo5aXS
bwbNwXtmYc3308tXTnlmM7ss7rSDlukULm5YPrqogzFpmN8eJ5vj3H2j6pwbfHEo
ihkHKaTRMyLlpXDQRPz55N8WhIip6UKTMyNowJ+GoRADIKPJo1cOff0Blbltr0hM
g6VgvkQNg2jzsIGiOfWTLKgD6agqGTDF+kJDAlKEm3MRs5tnb55oMeLJ9PvsO3Zb
YZREqNoWtGrhq0fWV6aUv3bAO0xJPgoF4pUiNCe5mhCOJIFqoLFgfGD+7arMq1eI
OS12WB6WLs+OlJomMWajBp4iOtWesReCKrrG4ihld32dHpmuAbbzUpbMNlvdS04p
VBnZiQle5Vwl7KI3lEKJFBhk6zTGpRmr1WwldXX39PYnrxxCu1uVMCLrTPjsoow8
nxJCz5xtjvqLPrs0iMFGNKXCIkIqzJiWe8LxgxMZtrljddbfTuLhFlSVCW6+dVFf
OWFUhUZ3bpMMEilLPndilm0TLqbyTPqMM9lRJJ41KyxJSEU0p4EF8wornKiUxxTK
8vqhKQiVSVxG8SssJ2iLZ0q+LKi20RURUWJilVBUwmMJtEidyzXCIToLimIU4EWi
PZZ4efxc5l0kIKqqpJBYGjysuFOhPM0ampdJebr99ozJjo8tk8XnYqt8FDE/JE6M
0YSL+zFNDVFd7e6/yYU6x8ZmAg1GasPUUE+A5fP5QJm8hG9LxNL2w4XfG0dLj0Vm
BWBYbKSoMjSejXaWIu47/OLQfPs4y5H3G9dbWj5mhvdqeATdJImAKhqWR3Lp2JLA
sunwlCnGjSAWSKaFQTMCZ/T+6NTFQNGSFJRj2D8FIiRQrKyzRkW50NdaKMCy4QXF
QdSEn+JejMj1I3my/3I/juSXGCsIOClGP73nLFiC+w34lc1K9cdgLMvXN6QXXubx
HeTYgp2YEDW813SV0KhcWCaMQVt6K39CbAigBYn4iNbm5fGSMEn38uxq9Lq5hlZg
z58cpeb6fkOY7ZRrRxT4zvTaBsYbZdzg8mwca0oXyrhNhQIpP1np3zlHSokrFWcg
E/MDQmoS60q+NH5njqEVlCQ0Ype+eY9QlSlp+09oSL0VQGWk5dHBwCD2BjYI56gh
JTeCVQff8/v8F/0FZvAOriEWnjP5sxQSL20i2fayrAu/LIiTiyYQQ0SlMm9lCmUN
C2FQiWf/SC2tVCVoUK9jCG2F8GvMaTaEtxApTQTTaE2Wy9gjQQyqEiAYcYCpcCFY
QuM4qLjal24QVL+2gRo4bg1FJ9XwNBt0CMUJalCGZJYXISmuIgVeBSuK2zLODmHY
SKJDSYcMCJZZMOQIUFZ/U+X1THRzIMyYmu2udkCVnKe0gQoGkesDs0BpENdZeesg
3JYGGXNQUlRBWLhErdiOMDuiLUGc7UcRQzTkxKUtihxc+YnTtLxE4RyGdviJGFBV
K4kIjGJNLsngEFFN1hTYBDGeAC6O1cc4krREoDFrMSUcokohyFFcgsCJivEtiCna
g3JOgStAo/JSKxyQNYyCBBIM6JjgkkWMGmCUkw7locyzkZiQUNHIcCSNKVgZuR7e
kR8KUFupBAXnIgM6RjIQa81SXCHo1IShBx7BLLLv9ugG29b+LvaFkhWpYCN6AiZJ
CTWnPuEuYRXStQYGBgR8OmsRNLmWkVZYju+/YSab0MNIE0NrS1yRYc1JmVl93vn4
bNa7N4yEHL3EDEumLF2tXMahLWFn4O95tMtGOvRJ0OqqVVHe2lcMRuRJP79yI3vq
dCDKpKCgODWttLQl8ArP0YcgfpBY/+sn+knVwUoWiQZ31xwcNtLiAVQcs5IaCxWG
JQ1QxZLpSOhAbqlaOtZzDmEqQlw/NBp75GoZ0NU/H5cd+0Ris6NJkBhxjvvfzI22
2CLWrxBt2iMwGtoFS2N9V21TQlwC4QkXiPElNIwWTKzQ2lnOGQcNVRcaMScj5IwS
NRgFrVyXCHUEgkKQSCJA0gX/xdyRThQkJT9sdMA=