スケーラブルな優先度キューが競合を最小化

Tiffany Trader

マルチコアは今の時代では完全に普及したが、それでもすべての並列の長所を利用することは大きな課題だ。理想的にはコアが増えれば計算効率がリニアにスケールするのだが、常にそうなるとは限らない。
演算のスペクトルに渡ってコア数が増えるようにセットされているだけであって、それは重大で注意すべき問題なのだ。

MITの計算科学と人口知能研究室の研究者達が、タスクスケジュールや離散イベントシミュレーション等のアプリケーションにとって不可欠な優先度キューのスケーラビリティを改善する方法を探求している。並列優先度キューは8コアまでスケールするが、１桁を超えると、キューの先頭で要素にアクセスしようとする複数のスレッドのために効率が低下する。優先度キューを変更して先頭までの距離をある程度取るようにすることで、このMITチームは80コアまでの効率を改善することに成功した。

優先度キューの従来のバージョンでは、複数のスレッドが同時に優先度キューの先頭にアクセスしようとすることでボトルネックが発生する。MITチームが作成したSprayListアルゴリズムはタスクをランダムにアサインすることで問題の解決を行っている。スキップリストをベースにしたこのアルゴリズムは、多くのコアが一斉に動作するようなプロセッサを可能にする。

「大雑把に言って各SkipListレベルにおいては、スレッドがそのレベルで何ノードスキップして先に進むかランダムコインを投げているようなものです。」と論文に彼らは書いている。「本質的には、ローカルな偶然性と、リストの先頭へのアクセスを均衡化するためのSkipListのランダム構造を利用しています。各レベルでのジャンプの距離は、最初のO(p log3 p)の中でノードを打つ確率が一様に近くなるように選択されます。」

図1はsprayの背後にある直観を示している。

MITの電気工学と計算機科学の大学院生とこの論文の共著者の一人でもあるJustin Kopinskyはこのアプローチが、桁違いの減速もしくは標準優先度キューに関連する衝突と停滞がさらに増えることに対処できると説明している。

研究者達はSprayListアルゴリズムを、4個の10コアIntel Xeon E7-4870 (Westmere EX)プロセッサを搭載して合計80個のハードウェアスレッド(約80コアセットアップ)をサポートしている富士通のRX600 S6サーバを使って行った。論文中に詳述されている複数のベンチマークを実行して、このアルゴリズムは競合の大幅な削減を実現したと言われている。研究者等は、ランダムなアプローチが通常の優先度キューと比較して遠回りで時間が掛かる一方で、スケーラビリティにおけるメリットが合理的に並列なワークロードに対する余計な仕事を凌ぐと説明している、さらに、彼らのアルゴリズムの緩和パラメータが、ワークロードと特定のコア数に依存して性能を向上するように調整することができると述べている。

研究達は2月に開催されたACM Symposium on Principles and Practice of Parallel Programmingにおいて成果を発表している。