投機的マルチスレッド実行とトランザクショナルメモリを用いた新しい実行方式

投機的マルチスレッド実行とは

当研究室ではトランザクショナルメモリを利用した投機的なマルチスレッド実行の研究を行っています。投機的とは今後プログラムがどう実行されるかを予測し、その予測を信じて待機することなく実行を始めることです。その予測が的中すれば待機しなかっただけ実行が高速化され、もし予測が外れた 場合は最初からやり直すことでカバーします。身近な例に例えると、授業で先生に解けと指名されそうな問題を事前に解いておく、といったところでしょうか。ヤマが当たれば授業ではすぐ答えられますし、ヤマが外れたらその場で問題を解くことになるでしょう。

この投機的なシステムを組み込んでマルチスレッド実行をすることで、単純に並列に実行する以上の高速実行を実現することができます。では、なぜ投機的実行によって高速化するのか、つまりただのマルチスレッド実行では対応しきれない問題についてこれから説明していきます。

マルチスレッド実行の悩み

シングルスレッド実行で限界が見えていた性能は、そのプログラムをマルチスレッド化することで更なる高速化を果たすことが可能となりました。ですが、このマルチスレッド化にはプログラマを悩ませる要因があります。それは各スレッドが共有して扱うデータの存在です。他のスレッドと共有しているデータは自分のスレッド以外の処理によって値が変化します。それが原因で、複数のスレッドが共有関係にあるデータに対して同時にアクセスした際に結果が正しくならない場合があります。

これを競合と呼びます。プログラマはマルチスレッド実行を正しく行うために何らかの工夫を凝らす必要があります。たとえばセマフォやロックなどの排他制御を用いると、複数のスレッドが同一のデータへ同時にアクセスできないようにすることで、競合を防止します。しかしこれは各スレッドに自分の番が来るまでの待機時間を生み、マルチスレッド実行の性能を低下させる原因となります。

トランザクショナルメモリを使って解決

そこで、この性能低下の要因に対して、当研究室ではトランザクショナルメモリを使って解決します。トランザクショナルメモリとは、マルチスレッド実行において各スレッドにそれぞれが共有するデータへ同時にアクセスすることを許可しつつ、プログラムの正しい実行結果を保証する仕組みです。各スレッドは自分以外のスレッドの処理が自分の処理に影響を与えないだろうと楽観的に考えてプログラムの実行を進めます。そして後で本当に影響が無かったかどうかを調べ、無ければそのまま実行を続けることで高速化、影響があればそのスレッドはもう一度実行をやり直すことで正しい実行結果を保証します。共有データへのアクセスが競合しないことが多いプログラムでは、実行やり直しが起こりにくいので大幅に高速化されます。

トランザクショナルメモリのメリット

トランザクショナルメモリを使うメリットの一つは、発生するかどうかわからない競合のためにロックを使うより、プログラム実行の遅延を抑えられることです。プログラムにはほとんど発生しないものの稀に起こり得る競合が存在する場合があります。プログラムの正しい動作を保証するためには非常に稀な場合であってもロックで保護することが要求され、結果として大きな遅延を生んでしまいます。そんな場合に対して、このトランザクショナルメモリを使うことで遅延は最小限に抑えられ、プログラムを高速化することができます。

また、プログラマはどこで競合を起こす可能性があるか、どこにロックが必要かを探し求めることに大変苦労しています。一つ間違えばプログラムは不正な実行をしたり終わらなくなってしまうので蔑ろにするわけにもいきません。そんな作り手側の問題もトランザクショナルメモリを使えば解決が可能なのです。トランザクショナルメモリの場合は競合が発生しうる範囲を指定する、ただそれだけで良いのです。

これからはトランザクショナルメモリの時代

トランザクショナルメモリは大きく分けて、ソフトウェア的に実現したものとハードウェア的に実現したものがあります。両者の性能は全く異なり、ハードウェアサポートで実現されるものの方が圧倒的に高速です。しかし、今までトランザクショナルメモリをサポートしてくれるハードウェア、プロセッサはほとんどありませんでした。

ですが、2013年夏到来のインテル製プロセッサ“Haswell”にはこのトランザクショナルメモリをハードウェア的にサポートする機能が搭載されています。さらに2014年に販売が予定されているインテル製プロセッサ“Broadwell”はそのHaswellをベースにしてより高性能化したプロセッサです。これから世界に普及していくパソコンの多くが、トランザクショナルメモリをサポートしているのです。

これらのハードウェアパワーを利用することでトランザクショナルメモリによる更に高速な投機的マルチスレッド実行ができるはずです。そしてその高速化の恩恵は研究者などの一部の人だけでなく、皆さんを含めた多くの人々が受けられることでしょう。