現代のマルチコアチップでは、各コア(プロセッサー)が独自の小さなメモリキャッシュを持ち、頻繁に使用されるデータを保存しています。しかし、チップにはより大きな共有キャッシュもあり、すべてのコアがこれにアクセスできます。
あるコアが共有キャッシュ内のデータを更新しようとすると、同じデータを扱っている他のコアがそれを把握する必要があります。そのため、共有キャッシュは、どのコアがどのデータのコピーを持っているかを示すディレクトリを保持しています。
このディレクトリは、メモリの大きな部分を占めます。64コアのチップでは、共有キャッシュの12%に達することもあります。そして、この割合はコア数とともに増加する一方です。128、256、さらには1,000コアを想定したチップでは、キャッシュコヒーレンスを維持するより効率的な方法が必要になります。
10月に開催された国際並列アーキテクチャ・コンパイル技術会議(International Conference on Parallel Architectures and Compilation Techniques)で、MITの研究者らは、30年以上ぶりとなるキャッシュコヒーレンスの根本的に新しいアプローチを発表します。既存の手法ではディレクトリのメモリ割り当てがコア数に正比例して増加するのに対し、新しい手法ではコア数の対数に比例して増加します。
128コアのチップでは、新しい手法は前身の手法の3分の1のメモリしか必要としないことを意味します。インテルが近日中に72コアの高性能チップを発売する予定であることを考えると、これは単なる仮定上の利点にとどまりません。しかし、256コアのチップでは省スペース率は80%に上昇し、1,000コアのチップでは96%になります。
複数のコアが同じ場所に保存されたデータを単に読み取るだけであれば、問題はありません。競合が生じるのは、いずれかのコアが共有データを更新する必要がある場合のみです。ディレクトリ方式では、チップがそのデータを扱っているコアを検索し、それらのコアにローカルに保存されたコピーを無効化するメッセージを送信します。
「ディレクトリは、書き込みが発生した時点で古いデータのコピーが存在しないことを保証します」と、MITの電気工学・コンピュータ科学専攻の大学院生で、新論文の筆頭著者であるXiangyao Yu氏は述べています。「この書き込みが行われた後は、以前のバージョンに対する読み取りは行われるべきではありません。したがって、この書き込みは、物理時間の順序において、それ以前のすべての読み取りの後に順序付けられます。」
タイムトラベル
Yu氏と博士論文の指導教員であるSrini Devadas氏(MIT電気工学・コンピュータ科学学科、Edwin Sibley Webster教授)が気づいたのは、分散計算の物理時間の順序は、論理時間の順序が維持される限り、実際には重要ではないということでした。つまり、コアAは、コアBがその後上書きしたデータに対して作業を続けることができます。ただし、システムの残りの部分がコアAの作業をコアBの作業より前に行われたものとして扱うことが条件です。
Yu氏とDevadas氏のアプローチの独創性は、グローバルな論理時間の順序を強制する、単純で効率的な手段を見つけた点にあります。「私たちがしていることは、各操作にタイムスタンプを割り当て、すべての操作がそのタイムスタンプの順序に従うようにすることです」とYu氏は述べています。
Yu氏とDevadas氏のシステムでは、各コアが独自のカウンターを持ち、メモリ内の各データ項目にも関連付けられたカウンターがあります。プログラムが起動すると、すべてのカウンターはゼロに設定されます。コアがデータを読み取るとき、そのデータに対して「リース」を取得します。これは、データ項目のカウンターを、例えば10に増加させることを意味します。コアの内部カウンターが10を超えない限り、そのコピーのデータは有効です。(具体的な数値はそれほど重要ではありません。重要なのは相対的な値です。)
一方、コアがデータを上書きする必要がある場合、そのデータの「所有権」を取得します。他のコアは、ローカルに保存されたデータのコピーで作業を続けることができますが、リースを延長したい場合は、データ項目の所有者と調整しなければなりません。書き込みを行っているコアは、データ項目のカウンターの最後の値よりも大きい値に、自身の内部カウンターを増加させます。
例えば、コアAからDまでがすべて同じデータを読み取り、内部カウンターを1に設定し、データのカウンターを10に増加させたとします。コアEがそのデータを上書きする必要があるため、所有権を取得し、内部カウンターを11に設定します。この内部カウンターにより、コアEは他のコアよりも後の論理時間で動作していることになります。他のコアは1の位置にとどまっていますが、コアEは11で先行しています。時間を先へ飛躍させるこの考え方が、システムの名前の由来となっています。名称のTardisは、英国のSF界のヒーローであるDr. Whoに登場する時間旅行する宇宙船にちなんでいます。
ここで、コアAが新たなリースを取得しようとすると、データがコアEによって所有されていることがわかり、コアEにメッセージを送信します。コアEはデータを共有キャッシュに書き戻し、コアAはそれを読み取り、内部カウンターを11以上に増加させます。
未開拓の可能性
メモリの節約に加え、Tardisは、データ項目を共有しているすべてのコアに無効化メッセージを一斉送信する必要もなくします。超多コアチップでは、これによって性能向上につながる可能性もあるとYu氏は述べています。「これらの実験では、その点による性能向上は見られませんでした」とYu氏は述べています。「しかし、それはベンチマークによるのかもしれません」――Yu氏とDevadas氏がTardisのテストに使用した業界標準のプログラムのことです。「非常に最適化されているため、すでにこのボトルネックを取り除いているのかもしれません」とYu氏は述べています。
「このようなリースの考え方を検討した人は他にもいます」と、インテル・ラボのプリンシパル・エンジニアであるChristopher Hughes氏は述べています。「しかし、私の知る限り、それらは物理時間を使用する傾向があります。誰かにリースを与え、『はい、このデータを例えば100サイクルの間使用して構いません。その間は他の誰もこのデータに触れないことを保証します』と言うわけです。しかし、その場合、性能に上限を設けてしまうことになります。なぜなら、直後に別の誰かがデータを変更したくなった場合、その人は100サイクル待たなければならないからです。一方、ここでは問題ありません。単にクロックを進めればよいのです。これは、私の知る限りこれまで行われたことのないことで、本当に素晴らしい鍵となるアイデアです。」
しかし、Hughes氏は、チップ設計者は本質的に保守的であると述べています。「量産される商用システムのほぼすべては、ディレクトリベースのプロトコルに基づいています」と彼は述べています。「実装を変更する際には間違いを起こしやすいため、それらには手を加えません。」
しかし、「彼らの方式の利点の一部は、現在の[ディレクトリベースの]方式よりも概念的にやや単純であることです」と彼は付け加えています。「また、これらの研究者が行ったもう一つのことは、アイデアを提案しただけでなく、その正しさを証明する別の論文も発表していることです。これはこの分野の人々にとって非常に重要です。」
本記事は MIT Newsとの協力により公開されています。掲載は世界経済フォーラムによる見解の支持を意味するものではありません。
Agendaの最新情報を追うには、 週刊ニュースレターにご登録ください。
著者:Larry Hardesty氏は、MIT Newsの客員寄稿者です。
画像:台湾のXinchuにあるTaiwan Semiconductor Manufacturing Company(TSMC)で、2007年1月9日に展示された12インチウェハー。REUTERS/Richard Chung



