粗粒度のロックとトランザクション同期

同カテゴリーの次の記事

Haswell のトランザクション同期

この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Coarse-grained locks and Transactional Synchronization explained」の日本語参考訳です。

粗粒度のロックとトランザクションの重要性は、インテル® Transactional Synchronization Extensions (インテル® TSX) のメリットを理解するための鍵となる概念です。ここでは、これらの概念について説明します。

Haswell のトランザクション同期」では、粗粒度のロックのパフォーマンスを向上させる新しい命令 (インテル® TSX) について説明しています。粗粒度のロックとトランザクションの概念を理解することはどちらも、インテル® TSX について理解するために重要です。

インテル® TSX は粗粒度のロック以外に排他制御のパフォーマンスも向上させますが、ここでは一般的な粗粒度のロックに注目します。インテル® TSX は、単純なロックメカニズムのみを使用して高度な同時アクセスを可能にします。


単純なハッシュテーブルを考えてみましょう。ハッシュテーブルは、キー (key) と値 (value) のペアをリニアにキー (key) にマップするのに使用されます。2 つの鍵となる処理は、追加 (挿入) と照合 (検索) です。サイズ変更と削除も一般的な処理ですが、ここでは説明しません。

高度な同時ハッシュテーブルの設計は容易ではなく、高レベルの同時性を達成するためにさまざまなアプローチが用いられています。これらのアプローチではプログラムが複雑になります。データ構造が複雑になることもあります。

最も単純なアプローチは、シングルロック です。このアプローチでは、ハッシュテーブルのすべての処理はテーブルのロックを取得することで開始し、ロックを解放することで終了します。ある処理のためにロックが取得されている間、システムのほかのタスクはロックを取得できないため、ハッシュテーブルを処理することはできません。

図 1 では、同時処理は許可されていないため、図で示されている 5 つの処理は一度に 1 つのみ行われます。

図 1: 5 つのハッシュテーブルの処理
ソリューション

一般的なソリューションは、ハッシュテーブルを小さな領域に分割して、領域ごとにロックを行うアプローチです。このアプローチでは競合は減りますが、これまでと同じように不要な遅延が発生します。また、コーディングとデータ構造が複雑になります。

このアプローチは、粗粒度のロック (ハッシュテーブル全体で単一のロックを使用) と呼ばれ、より細粒度のロック (テーブルの複数のセクションで複数のロックを使用) を行う典型的な例です。粗粒度のロックは、より簡単に使用し、理解し、デバッグできます。唯一の短所は、マルチスレッド環境でパフォーマンスを制限する傾向があることです。マルチコアプロセッサーではパフォーマンスが制限される可能性が高くなりますが、新しいハードウェアの機能を活用することで、プログラミングを複雑にすることなく、この問題に対処できます。

インテル® TSX を利用したソリューション

理想は、容易に使用できエラーが発生しにくい単一のロック (粗粒度のロック) を使用して、細粒度のロックを使用した場合に得られるパフォーマンスを達成することです。図 1 の例では、1 つの処理がほかの処理と競合しているだけで、通常の想定よりも競合は少なくなっています。

この例では、3 つの処理はほかの処理と競合しないため、単一のロックで HLE (インテル® TSX の一部) を使用することで完全にロックが無視されます。つまり、コードのロックまたはアンロックが行われない場合、コードのパフォーマンスがそのまま反映されます。しかし、重要なのは、これらの処理がインテル® TSX によって保護され、ロックで意図した保護が保証される点です。

同じハッシュテーブルのエントリーにマップする 2 つの処理は交互に配置する必要があります。2 つの処理が同時に行われると、インテル® TSX はロックが必要であると判断して、ロックによるオーバーヘッドが発生します。この場合、プロセッサーが競合を検出するまで競合するタスクは保護されたコードに進み、両方の更新により保護されたコード (トランザクション) は中止されます。最も一般的なソリューションは、各タスクを進めて、その後でロックする方法です。1 つのタスクの処理が完了するまで、ほかのタスクは待たされることになります。競合の制御方法は、プロセッサー (HLE) または開発者 (RTM) が決定します。オリジナルのロックのセマンティクスとインテル® TSX 未対応プロセッサーとの互換性を保持するため、HLE のプロセッサーの実装はかなり単純で保守的なものになるでしょう。

まとめ

ハッシュマップにインテル® TSX を利用すると、必要なロックの保護を失うことなく、正しい処理を行えます。粗粒度のロックと同様の結果が得られることを保証しつつ、粗粒度のロックによる遅延を発生させることなく無関係な処理を進められます。トランザクション同期についての詳細は、「Haswell のトランザクション同期」を参照してください。

この仕様をぜひ一読してください。そして、今後インテルや他社から提供されるツールに関する情報を見逃さないようにしてください。

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。

関連記事