MIT、大規模マルチコアCPUの効率を向上させるデータ構造を開発

taraiok 曰く、　マサチューセッツ工科大学の研究者が、大規模マルチコアプロセッサの効率を向上させるというデータ構造を開発したそうだ。現在のプライオリティキューを使用するアルゴリズムでは、8コアを超えるコアを追加するとパフォーマンスが急落する。複数のコアが同時に優先キューの先頭にアクセスしようとすると競合が生じためだ。新たに開発された「SprayListアルゴリズム」では、各コアがキューに最初の項目にアクセスする必要要件を緩和し、ランダムにタスクを割り当てることにしたという（ITWORLD、MITNews、Slashdot）。

　こうしたランダムにタスクを割り当てる方式は過去にも考えられたことがあるが、キャッシュの効率が落ちると批判され使われてこなかった。しかし、コア数が増加した場合はメリットがデメリットを上回る状態になるようだ。80コアプロセッサをシミュレートした環境で実験したところ、コア数が増えるごとに直線的な性能向上が見られたとしている。

　スラッシュドットのコメントを読む | ITセクション | ソフトウェア

　関連ストーリー：
新たなデータ圧縮アルゴリズム「LZHAM」 2015年01月27日
汎用プロセッサなど存在しない 2014年11月11日
マイクロプロセッサの未来、将来のコンピュータスタイルは ? 2011年06月06日
今後のCPUのコア数増加とLinux 2010年10月02日