この記事は、インテル® デベロッパー・ゾーンに掲載されている「Exploring Intel® Transactional Synchronization Extensions with Intel® Software Development Emulator」(http://software.intel.com/en-us/blogs/2012/11/06/exploring-intel-transactional-synchronization-extensions-with-intel-software) の日本語参考訳です。
インテル® Transactional Synchronization Extensions (インテル® TSX) は、第 4 世代インテル® Core™ マイクロアーキテクチャー (開発コード名 Haswell) に追加された最も重要な命令セット・アーキテクチャーの拡張の 1 つと言えます。インテル® TSX は、ベストエフォート型の「トランザクショナル・メモリー」 (複雑な細粒度のロック・アルゴリズムやロックフリー・アルゴリズムとは対照的にスケーラブルなスレッドの同期を行う単純なメカニズム) に対するハードウェア・サポートを実装します。この拡張には 2 つのインターフェイス、Hardware Lock Elision (HLE) と Restricted Transactional Memory (RTM) があります。
ここでは、第 4 世代インテル® Core™ プロセッサーの出荷を待たずに、初めて RTM コードを記述し、エミュレート環境で実行する方法を紹介します。
この記事は新しい RTM 命令の基礎知識があることを前提にしています。基礎知識については、こちらの記事をご覧ください。また、Haswell ハードウェアのインテル® TSX 実装について述べた Ravi Rajwar と Martin Dixon によるインテル・デベロッパー・フォーラム 2012 のプレゼンテーション (英語) と Linux* への HLE の追加 (および RTM の使用) について述べた Andi Kleen によるプレゼンテーション (http://www.halobates.de/adding-lock-elision-to-linux.pdf) も参考になります。
ここでは、STL の (スレッドを意識しない) C++ データ構造を利用して、インテル® TSX で管理される取引履歴への同時アクセスを含む、架空の銀行口座処理アプリケーションを記述します。このようなアプリケーションであれば、単純かつスレッドセーフで、スケーラブルな実装が可能でしょう。
開発環境
インテル® Software Development Emulator (インテル® SDE) の最新バージョン (5.31) と (組込み関数またはマシンコードによる) RTM 命令を生成可能なコンパイラーが必要です。RTM を実行するインテル® SDE におけるパフォーマンス測定は、実際のハードウェアの代わりにソフトウェアでトランザクショナル・メモリー (TM) をエミュレートするためオーバーヘッドが非常に大きく、測定結果が制限されます。しかし、後述のように、インテル® SDE は、並列ライブラリーおよび並列アプリケーションの開発者に RTM の利用に関して重要なポイントを示します。
私のラップトップが Windows* なので、ここでは Windows* 上でインテル® SDE/RTM を使用します。コンパイラーは、Microsoft* Visual Studio* 2012 の C++ コンパイラーを使います (無料の Visual Studio* Express 2012 for Windows Desktop も使用可)。Visual Studio* でコンソール・アプリケーション・プロジェクトを作成し、RTM 組込み関数を使うためメインの .cpp ファイルで immintrin.h ヘッダーをインクルードします。
検証
銀行口座の構造として、C++ 標準テンプレート・ライブラリーの単純な std::vector<int> を使用します。「Accounts[i]」は、口座番号 i の現在の残高を保持します。これは単純で一般的なデータ構造ですが、スレッドセーフではないため、並行処理制御メカニズムにより並列アクセスを保護する必要があります。通常、データ構造に同時アクセスするスレッド数の制限にはロック/mutex が用いられます。しかし、多くの場合、並列書き込みアクセスでは、データ構造の特定の場所だけを更新する場合であっても、データ構造全体が排他的にロックされます。このような場合、インテル® TSX が役立ちます。インテル® TSX は、書き込みが安全だと推定して実行するため、実際にデータ競合が発生しない場合、シリアル化せずに書き込みをコミットできます。
口座処理を単純にするため、安全でないデータへの同時アクセスから現在の C++ スコープを保護する便利な C++ ラッパーを実装します。
{
std::cout << "open new account" << std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
Accounts.push_back(0);
}
{
std::cout << "open new account" << std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
Accounts.push_back(0);
}
{
std::cout << "put 100 units into account 0" <<std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
Accounts[0] += 100; // RTM によるアトミックな更新
}
{
std::cout << "transfer 10 units from account 0 to account 1 atomically!" << std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
Accounts[0] -= 10;
Accounts[1] += 10;
}
{
std::cout << "atomically draw 10 units from account 0 if there is enough money"<< std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
if(Accounts[0] >= 10) Accounts[0] -= 10;
}
{
std::cout << "add 1000 empty accounts atomically"<< std::endl;
TransactionScope guard; // このスコープ内のすべてを保護する
Accounts.resize(Accounts.size() + 1000, 0);
}
レガシー・アプリケーションは、1 つの書き込みだけにクリティカル・セクションの実行を許可するロックによりガードを実装します (読み取り/書き込みロックは扱いがより複雑なだけでなく、ここではすべてのアクセスが書き込み/更新なのであまり意味がありません)。
class TransactionScope
{
SimpleSpinLock & lock;
TransactionScope(); // forbidden
public:
TransactionScope(SimpleSpinLock & lock_): lock(lock_) { lock.lock(); }
~TransactionScope() { lock.unlock(); }
};
RTM の実装と検証
TransactionScope の簡単な RTM 実装を以下に示します (読み取り/検索アクセスと書き込み/更新アクセスが透過的に行われます)。変更された行は、 マークで示されます。
class TransactionScope
{
public:
TransactionScope()
{
int nretries = 0;
while(1)
{
++nretries;
unsigned status = _xbegin();
if(status == _XBEGIN_STARTED) return; // 開始成功
// アボートハンドラー
std::cout << "DEBUG: Transaction aborted "<< nretries <<
" time(s) with the status "<< status << std::endl;
}
}
~TransactionScope() { _xend(); }
};
このコードは問題なくコンパイルされ、インテル® SDE で実行したところ、以下のような出力が得られました。
./sde-bdw-external-5.31.0-2012-11-01-win/sde.exe -hsw -rtm-mode full -- ./ConsoleApplication1.exe open new account DEBUG: Transaction aborted 1 time(s) with the status 0 DEBUG: Transaction aborted 2 time(s) with the status 0 DEBUG: Transaction aborted 3 time(s) with the status 0 DEBUG: Transaction aborted 4 time(s) with the status 0 DEBUG: Transaction aborted 5 time(s) with the status 0 DEBUG: Transaction aborted 6 time(s) with the status 0 DEBUG: Transaction aborted 7 time(s) with the status 0 DEBUG: Transaction aborted 8 time(s) with the status 0 DEBUG: Transaction aborted 9 time(s) with the status 0 DEBUG: Transaction aborted 10 time(s) with the status 0 DEBUG: Transaction aborted 11 time(s) with the status 0 DEBUG: Transaction aborted 12 time(s) with the status 0 DEBUG: Transaction aborted 13 time(s) with the status 0 DEBUG: Transaction aborted 14 time(s) with the status 0 DEBUG: Transaction aborted 15 time(s) with the status 0
無限ループが発生すると、プログラムは常に最初のトランザクションでアボートします。これは、インテル® SDE により出力された RTM のデバッグログ (emx-rtm.txt) でも確認できます (-rtm_debug_log 2 オプションを指定します)。一般に、仕様を無視した実装では多かれ少なかれ問題が発生するものです… 『Intel® Architecture Instruction Set Extensions Programming Reference (インテル® アーキテクチャー命令セット拡張プログラミング・リファレンス)』では、「ハードウェアは RTM 領域がトランザクションのコミットに成功するかどうかを保証しません」と明示しています。そのため、RTM を利用するソフトウェアは、アボートが (多数) 発生した場合に実行される (非トランザクションの) フォールバック・パスを提供する必要があります (HLE は、最初のアボートで同じクリティカル・セクションを非トランザクション実行するため、自動でフォールバックを提供します)。
フォールバックの実装
以下の実装は、指定したリトライ回数の上限に達するとフォールバック・スピン・ロックを非トランザクションに取得します。
LONGLONG naborted = 0; // グローバルなアボート統計。代わりに、インテル® SDE オプションの –rtm_debug_log 2 を使用可
class TransactionScope
{
SimpleSpinLock & fallBackLock;
TransactionScope(); // 禁止
public:
TransactionScope(SimpleSpinLock & fallBackLock_, int max_retries = 3) :
fallBackLock(fallBackLock_)
{
int nretries = 0;
while(1)
{
++nretries;
unsigned status = _xbegin();
if(status == _XBEGIN_STARTED)
{
if(!fallBackLock.isLocked())
return; // トランザクションの開始成功
/* トランザクションを開始したが、 誰かが
トランザクション・セクションを非投機的に実行中
(フォールバック・ロックを取得) -> アボート */
_xabort(0xff); // コード 0xff でアボート
}
// アボートハンドラー
InterlockedIncrement64(&naborted); // アボート統計の出力
std::cout << "DEBUG: Transaction aborted "<< nretries <<
" time(s) with the status "<< status << std::endl;
// xabort(0xff) の処理
if((status & _XABORT_EXPLICIT) &&
_XABORT_CODE(status)==0xff &&
!(status & _XABORT_NESTED))
{ // ロックが解放されるまで待機
while(fallBackLock.isLocked()) _mm_pause();
}
// リトライの上限に達したらフォールバック・ロックを取得
if(nretries >= max_retries) break;
}
fallBackLock.lock();
}
~TransactionScope()
{
if(fallBackLock.isLocked())
fallBackLock.unlock();
else
_xend();
}
};
次のように、出力結果が改善されました。
open new account DEBUG: Transaction aborted 1 time(s) with the status 0 DEBUG: Transaction aborted 2 time(s) with the status 0 DEBUG: Transaction aborted 3 time(s) with the status 0 open new account put 100 units into account 0 transfer 10 units from account 0 to account 1 atomically! atomically draw 10 units from account 0 if there is enough money add 1000 empty accounts atomically
最初に処理されたトランザクションを除き、すべてのトランザクションが出力されます。最初のトランザクションは 3 回リトライした後にフォールバック・ロックを取得しています。これは、オペレーティング・システムのベクトル用に新しいメモリーの確保とアクセスを行わなければならないため、特別なケースです。システムコール、特権リングの移行 (ring 3 [application]->ring 0 [OS])、ページフォルト、トランザクション・バッファーに収まらない可能性がある大きなメモリーチャンクの初期化/0 への設定などの複雑な処理です。『Intel® Architecture Instruction Set Extensions Programming Reference (インテル® アーキテクチャー命令セット拡張プログラミング・リファレンス)』によると、これはすべてアボートにつながります。
RTM アボート・ステータス・ビットの活用
アボートステータス情報を活用してさらに最適化することができます。「ハード」アボートの場合、アボートステータスの「リトライ」ビット (位置 1) はセットされません。このビットは、トランザクションがリトライで成功するとハードウェアが見なした場合にセットされます。アボートハンドラーに、以下のマークした行を追加します。
// _xabort(0xff) の処理
if((status & _XABORT_EXPLICIT) &&
_XABORT_CODE(status)==0xff &&
!(status & _XABORT_NESTED))
{
while(fallBackLock.isLocked()) _mm_pause(); // ロックの解放を待機
} else if(!(status & _XABORT_RETRY)) break; /* リトライ・アボート・フラグが
セットされていない場合はフォールバック・ロックを取得 */
次のような出力結果が得られます。
open new account DEBUG: Transaction aborted 1 time(s) with the status 0 open new account put 100 units into account 0 transfer 10 units from account 0 to account 1 atomically! atomically draw 10 units from account 0 if there is enough money add 1000 empty accounts atomically
これにより、「ハード」アボートが発生した場合、フォールバック・ロックを素早く取得できるようになり、プログラムの処理速度が向上します。
すでにお気付きかもしれませんが、これまでの変更は TransactionScope 同期インターフェイス内のものだけでした。アプリケーション・コードは全く変更していません。今後、一般に利用可能なインテル® TSX のソフトウェア基盤が進化するとともに、同期プリミティブの落とし穴を回避するため、RTM 対応の (スコープ) ロックを持つ既存のライブラリーの利用を考慮すべきでしょう (アプリケーション・コードの落とし穴については将来の記事で取り上げる予定です)。例えば、すでに Linux* 向けのインテル® TSX 対応の pthread* ライブラリー (http://www.halobates.de/adding-lock-elision-to-linux.pdf) があります。その一方で、既存のアプリケーションで拡張またはカスタム同期インターフェイスを利用するのは珍しいことではなく、これらをインテル® TSX に対応させることも慎重に行えば難しくありません。
インテル® TSX による複数スレッドからの同時アクセスの管理
基本的なデバッグが終わったら、本題であるインテル® TSX の真価について見てみましょう。中央の口座データ構造をランダムに同時更新する 2 つのワーカースレッドを実行します。
unsigned __stdcall thread_worker(void * arg)
{
int thread_nr = (int) arg;
std::cout << "Thread "<< thread_nr<< " started." << std::endl;
// <random> からスレッドローカルな TR1 C++ 乱数ジェネレーターを作成
std::tr1::minstd_rand myRand(thread_nr);
long int loops = 10000;
while(--loops)
{
{
TransactionScope guard(globalFallBackLock);
// ランダムなアカウントに 100 単位をアトミックに代入
Accounts[myRand() % Accounts.size()] += 100;
}
{
TransactionScope guard(globalFallBackLock);
/* ランダムなアカウント間で 100 単位をアトミックに転送
(十分な残高がある場合) */
int a = myRand() % Accounts.size()
int b = myRand() % Accounts.size();
if(Accounts[a] >= 100)
{
Accounts[a] -= 100;
Accounts[b] += 100;
}
}
}
std::cout << "Thread "<< thread_nr<< " finished." << std::endl;
return 0;
}
DEBUG と記されたメッセージを出力しない Release 構成でビルドしたところ、アボート件数は 20,000 トランザクション中 100 ～ 300 件だけでした。アボート・フラグ・ステータスは 6 リトライで、「メモリーアクセス競合」ビットがセットされたことが出力から分かりました。これは期待どおりの結果と言えます。ほとんどの更新が並列に実行され、競合によりロールバックされたのはほんのわずかでした。
この結果を裏付け、エミュレーターが期待どおりに動作することを再確認するため、トランザクションにグローバルカウンターのインクリメント/更新を追加し、大量のアクセス競合が発生するようにしてみました。その結果、この変更によりアボート件数が 5,000 ～15,000 件に増えました。RTM エミュレーターで取得した絶対数から将来のハードウェアの実行メトリクスを正確に予測することはできませんが、桁違いな結果から RTM 利用の潜在的な問題が分かります。
最後に
ここでは、RTM と新しいインテル® Software Development Emulator について、筆者の検証結果を紹介しました。Haswell に備え、インテル® SDE を利用してソフトウェアで Restricted Transactional Memory を使用する方法の調査に今すぐ取りかかりましょう!
—
Roman
(以下のファイルに完全なソースコードがあります。)
| 添付ファイル | サイズ |
|---|---|
| ダウンロード exploringinteltsx.cpp (http://software.intel.com/sites/default/files/blog/335035/exploringinteltsx.cpp) | 11.22KB |
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。
