前回 Part.1 では、Transactional Language Constructs for C++ (以下 TM 提案)について Atomic transaction の記述「他のスレッドが transaction の中間結果を観測しない」が、どのようなからくりになっているかを説明しました。Part.2 では、TM 提案と対とも言える文書、Intel TM ABI specification を元にコンパイラがどのように C++ TM を実現しようとするかについて覗いてみたいと思います。
TM 提案を実装しているコンパイラはいくつかありますが Intel によるプロトタイプ実装 Intel C++ STM Compiler, Prototype Edition というものがあります。Intel TM ABI とはこの実装で使用されている ABI です。元々 TM 提案は何が実現されるか(what)についてだけ規定しておりどのように実装するか(how)については規定していません。これはソフトウェア、ハードウェア、ハイブリッドといった区分を含め様々な TM 実装を利用できるようにするためです。コンパイラの実装としてもこの方針に則っており、Tntel TM ABI に則ったライブラリ(libitm)を差し替えることで実装を切り替えられるようになっています。GCC 4.7 以降も TM 提案を試験的に実装していますが、同様に Intel TM ABI に則ったライブラリ(正確には特に例外周りで変更があるみたいですが)への呼び出しに変換されて実現されます。
さて、では TM 提案 に則ったコードをコンパイラがどのように libitm への呼び出しに変換するのかを見てみましょう。以下は TM ABI の例を一部改変しています。
int s;
[[transaction_safe]] int f(int);
void foo(void)
{
int i;
for (i=0;i<10;i++)
{
__transaction_atomic {
s += f(i);
if (s > 1000) __transaction_cancel;
}
}
}
このコードは(例外関係を無視し効率を考えないとして)例えば次のようなコードに変換されます。
int s;
int f(int);
static _ITM_srcLocation start_outer_loc = {…};
static _ITM_srcLocation commit_outer_loc = {…};
static _ITM_srcLocation abort_loc = {…};
void foo(void)
{
_ITM_transaction * td = _ITM_getTransaction();
for (i=0;i<10;i++) {
int doWhat = _ITM_beginTransaction (td,pr_instrumentedCode | &start_outer_loc);
if (doWhat & a_restoreLiveVariables) {
/* TM 化していない有効なローカル変数を復元する */
}
if (doWhat & a_abortTransaction) goto txn1_abort_label;
if ((doWhat & a_saveLiveVariables)) {
/* TM 化しない有効なローカル変数を保存する */
}
int sval = (int)_ITM_RU4 (td, (uint32 *)&s);
sval += f_@TXN(i); // TM 化された関数 f の呼び出し
_ITM_WaRU4 (td, (uint32 *)&s, (unit32_t)sval);
if (sval > 1000)
_ITM_abortTransaction(td,userAbort,&abort_loc);
_ITM_commitTransaction(td,commit_outer_loc);
txn1_abort_label:
}
return;
}
以下では _ITM_ を省略して記述します。srcLocation 関連はデバッグ情報みたいなもので無視して構いません。"instrumented" という表現は TM 対応化された、くらいの意味に取ればいいと思われます。では、簡単に流れに沿って説明してみましょう。
- まず最初に getTransaction() で transaction descriptor を取得しています。以下の libitm 関数呼び出しで共通して渡されている情報です。内部に libitm で必要な情報が格納されているわけですが、結局は実質スレッドに紐付け可能なわけで libitm 側で管理すればいいんじゃね？という話はあります。この辺りも簡単に ABI spec 3.8 節に触れられており、また、実際 GCC の場合は td が存在しないコードになります。特に本筋に大きな影響はないので spec の記載通りで書いています。
- beginTransaction() によって transaction を開始します。これは内部的に setjmp() と同じような処理を含んでおり、commit に失敗した場合や abort された場合に(longjmpと同様の処理が行われ)再びこの関数から戻ってきます。戻り値は次にどのような処理を行うべきか、です。前述の通り abort した場合などもこの関数から戻ってくるためどのような処理をするか戻り値から判別しなければなりません。下表で再実行となっているのは commit に失敗した場合の transaction 再実行です。取り消し不可能云々は本稿では説明しません。さしあたって無視してもらっても大筋は成立します。
transaction 開始時 状況 戻り値 直列で取り消し不可能な transaction (serial irrevocable transaction)を開始 a_runUninstrumentedCode transaction 開始 a_saveLiveVariables | a_runInstrumentedCode transaction 再実行 a_restoreLiveVariables | a_runInstrumentedCode 直列で取り消し不可能な transaction として transaction 再実行(モード変更) a_restoreLiveVariables | a_runUninstrumentedCode 取り消し不可能な transaction として transaction を開始 a_runInstrumentedCode transaction 終了時 状況 戻り値 transaction が abort a_restoreLiveVariables | a_abortTransaction - a_restoreLiveVariables と a_saveLiveVariables はローカル変数に対するものです。libitm に渡して TM 化する場合オーバーヘッドがかかるため TM 化する変数アクセスは当然出来るだけ絞りたいわけです。transaction 中であればローカル変数は自分のスレッドからしか有効にアクセスできません。ということでローカル変数について保存・復帰によって対処しようというものがこれらのフラグとそれに対応する処理となります。
- abort された場合は、a_abortTransaction が返ってくるので(a_restoreLiveVariables によってローカル変数の復帰済み)、以降の transaction 関連コードをスキップします。
- RU4() だとか WaRU4() が実際に TM 化するためのメモリアクセスの置き換えです。最初の R or W が読み書きの区別、最後が型です(この場合は U4)。途中の aR 等は読み込みの後(after Read)等の意味を持ち、状況に応じて不要な処理を省くといったことを実現するために分けられています。
- f_@TXN は関数 f() の TM 化バージョンという表記です。実際にはコンパイラによって変わってくるでしょう。transaction 中であるかを判別する inTransaction() という関数もあるのでそれを使って関数内で切り替えることも可能だと思いますが、恐らくはゼロオーバーヘッドを考慮して 2 バージョン用意する形を想定して書かれているのだと思います。
- abortTransaction() はそのまま transaction の abort で前述のように beginTransaction() の場所に戻ります。
- commitTransaction() もそのまま transaction の commit です。commit に失敗した場合、前述のように beginTransaction() に戻って transaction が再実行されます。
さて、どうでしょうか？ まだ libitm の中まで見ていませんが、begin, abort, commit があって変数アクセスが置き換えられているということから(単一グローバルロックでなくとも)、Transactional Memory が実現できそうかなという感じがするんじゃないでしょうか？ part.3 では libitm 実装の一つである RSTM を参考にして TM がどのように実現されているかを簡単に見てみたいと思います。
0 件のコメント:
コメントを投稿