すたっくすれっず（日本語化裏ぺーじ）
疲れたので途中で死亡。。。。
StackThreads/MP のほーむぺーじ
すたっくすれっず／MPってなに？
すたっくすれっず／MPは、gccで細粒度マルチスレッドを可能にするライブラリ。
共有メモリマルチプロセッサシステム上で実行時にスレッドが移動する。
pthreadsとの違いは、１万以上のスレッドを作ってもオーバーヘッドが非常に少ない。
オーバーヘッドとは、スレッドの生成と終了のこと。
プログラマがスレッドを好きなだけ作ることができて、プログラミングが楽になって嬉しい。
並列プログラムを作るコストが減ったという結果がある。
さぽーとされるプラットフォーム
ソラリス、リナックス、アイリックス、デジタルユニックス、エヌティ
必要なもの
GNU C 、GNU awk 、GNU make、あとgccにパッチもある（gccのバージョンによってはあてなくても良い。
たぶん、harpのgccにはあててない）。
警告： SPARC上のgcc 2.8は -mflatにバグあるので使わない方がベター（どうしてもというならパッチ）。
ダウンロード
すたっくすれっず（0.76と0.21)、ユーザーガイド、gccへのパッチ。
ヒストリ
1999 １がつ23にち 最初のリリース
2000 ２がつ25にち 次のリリース（アルファリナックスをサポート、gcc 2.95をサポート、バグフィックス）
めーりんぐりすと
sthreads@yl.is.s.u-tokyo.ac.jp
フィードバックくれー
すたっくすれっずは研究だけに終わらせるつもりはなーい。（おおー：）
リスト以外の環境（OS、CPU）で動作したらレポートして。
すたっくすれっずで並列化したアプリもレポートして。
バグもレポートして。
他のプラットフォームに移植してと言われても約束はしない。
gccへのぱっち
すたっくすれっずは修正なしのgccで動くんだけど、gccが生成したコードと相容れない場合がある。
詳細はマニュアルに記述してある。
安全性を保証したいならパッチをあてることをお勧めする。
明示的なオプションを付けなければ、パッチしたgccがはくコードはオリジナルと全く同じ。
オプションを付ければ、少し違うコードを生成する。
もちろん、オプションを付けて生成したコードは完璧にもとのコードとコンパチブル。
この明示的なオプションを付けてコンパイルした関数から、普通に、コンパイルされた関数を呼ぶことができる。逆も同様。
パッチはgcc 2.7.2.3へのパッチ。
パッチがgccに追加するオプションは：
-fcalls-clobber-sp これはgccに手続き呼び出しが、SPを予期されないやり方で変えることを教える。
gccは呼び出し後のスタックポインタを未知の値だとして扱う。
これは、i386でのある最適化を不可能にする。（？？？）
-mcallee-copies-struct-args (すぱーくだけ） このオプションはgccに、手続きがincoming structure argumentsをコピーしなければならないことを教えてやる。
出版物
"Stackthreads/MP : Integrating Futures into Calling Standards." かなり分かりのよい設計の記述。PPoPP99。
"Stackthreads/MP : Integrating Futures into Calling Standards." 短いバージョンのテクニカルレポート。こっちも分かり良い。
"Lazy task creation for C programs." 日本語。SWoPP97。プロトタイプの記述。
"Fine-grain multithreading with minimal compiler support---a cost effective approach to implementing efficient multithreading languages." PLDI97。単一プロセッササブセット上での記述。
"StackThreads : An abstract machine for scheduling fine-grain threads on stock CPUs." Theory and Practice of Parallel Programming。他のアプローチの仕方で同じ目的を達成した古いペーパー。
"An efficient implementation scheme of concurrent object-oriented languages on stock multicomputers." PPoPP93。我々がどこから来たかを記述。
関連研究プロジェクト
ConceConcert Project
Cilk Project
関連サイト
遠藤さんとかがやっている並列こんさーばちぶGC：速いメモリあろけーた
Threads FAQ
Sun's Threads Page
Thread Bibliography
このプロジェクトは"Advanced Software Enrichment Project"Information-technology Promotion Agency (IPA), Japanの一部として行われている。
マニュアル
インストール
１、 アーカイブを解凍する。
２、 次の環境変数をセットする。
ST_DIR unzipしたトップレベルディレクトリ
ST_OS_TYPE このソフトを使用するOS ex. solaris linux etc
ST_CPU_TYPE このソフトを使用するCPU ex. sparc i386 etc
ST_THREAD_PKG 下位レベルのスレッドパッケージ ex. st_solaris_thread st_pthread
pathに $(ST_DIR)/bin を追加する。
３、 コアライブラリをコンパイルする。
% cd src
% make
うまくいったら、$(ST_DIR)/lib/libst.a を作成する。
４、 いくつかのユーティリティをコンパイルする。
% cd ../ext_src
% make
うまくいったら、 $(ST_DIR)/lib/libstext.a を作成する。
５、 簡単なテストをする。
% cd ../ex/small
% make
うまくいったら、引数なしで実行してみる。
何も問題がなければ、最後のラインでOKと言われる。
i386上で nestcall プログラムはうまく実行されないが、これは未修整のgccを使った実装の限界。
See section Floating SP Problem for the description of the problem. gcc patchでfixできる。
See section Applying Safety Patches to GCC for how to apply patches.
SPARC上でstrpassはうまく実行されないが、これも未修整のgccを使った実装の限界。
See section Structure passing on SPARC for the description of the problem.
We have a patch to GCC that fixes this problem.
See section Applying Safety Patches to GCC for how to apply patches.
プログラム bin をさまざまな数のプロセッサで実行してみる。
-nw P で プロセッサ数を指定する。
たいてい、小さいシステム（~４プロセッサ）ではPをプロセッサの数にしたときにパフォーマンスが最大になる。
中規模、大規模システム（~１０プロセッサ以上）だと、若干小さい数にするときに最大になる。
プロセッサの数以上を与えることも許されているが、たいていよろしくない。
./bin -nw 1
./bin -nw 5
./bin -nw 10
./bin -nw 14
./bin -nw 15
./bin -nw 16
とやって、速度がどれくらい改善されているかを見よう。
６、 ドキュメントをコンパイルする。
% cd ../doc
% make
これは stman.dvi と stman.info を生成する。 stman.infoはコピーしよう。
７、 すたっくすれっずを２つ以上のプラットフォームにインストールして、ソースを共有したいときは。。。（略）のようにする。
８、ここでは、gccにパッチをあてよう。gcc 2.8.1をSPARCで使用しているとき以外は強制ではない。
SPARC上のgcc-2.8.1は すたっくすれっずがすんごく依存している -mflat オプションに簡単なバグがあるので、この場合にはパッチをあてよう。
このディストリビューションには gcc 2.7.2.3 と gcc 2.8.1用のパッチが gccpatch/gcc-2.7.2.3 と gccpatch/gcc-2.8.1 にある。
See section Applying Safety Patches to GCC for more detail.
基本
次のプログラムが基本的な使い方を示す。
1 #include <st.h>
2
3 int fib(int n)
4 {
5 if (n < 2) {
6
7 return 1;
8 } else {
9 int a, b;
10
11
12
13
14 a = fib(n - 1);
15 b = fib(n - 2);
16
17 return a + b;
18
19
20 }
21 }
22
23 void pfib(int n, int * r, st_join_counter_t *c)
24 {
25 if (n < 2) {
26 *r = 1; /* write the result */
27 st_join_counter_finish_1(c, 1);/* say I have done バージョンが違うと異なる */
28 } else {
29 int a, b;
30 st_join_counter_t cc[1];
31 ST_POLLING(); /* check if somebody is asking work
32 and free stack */
33 st_join_counter_init(cc, 2);/* initialize join counter */
34 ST_THREAD_CREATE(pfib(n - 1, &a, cc)); /* fork fib(n-1, ...) */
35 pfib(n - 2, &b, cc); /* fork fib(n-2, ...) */
36 st_join_counter_wait(cc); /* wait for child's completion */
37 *r = a + b; /* write the result */
38 st_join_counter_finish(c); /* say I have done */
39 ST_POLLING(); /* check if somebody is asking work
40 and free stack */
41 }
42 }
43
44 int st_main()
45 {
46
47 int n = 33;
48 long pfib_time, sfib_time;
49
50 {
51 long t0, t1, t2, t3;
52 int pr, sr;
53 st_join_counter_t c[1];
54
55 /* do parallel fib */
56 t0 = st_current_time_ms();
57 st_join_counter_init(c, 1);
58 pfib(n, &pr, c);
59 st_join_counter_wait(c);
60 t1 = st_current_time_ms();
61 pfib_time = t1 - t0;
62
63 /* do sequential fib */
64 t0 = st_current_time_ms();
65 sr = fib(n);
66 t1 = st_current_time_ms();
67 sfib_time = t1 - t0;
68
69 /* if (sr != pr) { */
70 /* fprintf(st_errout, "wrong\n"); */
71 /* st_stack_trace_and_die(); この関数がない */
72 /* } */
73 }
74
75 printf("pfib: %d ms on %d processors, sfib: %d ms\n",
76 pfib_time, st_n_toplevel_workers(), sfib_time);
77 return 0;
78 }
79
fib は逐次プログラム。pfibは並列プログラム。
３４行目で再帰呼び出しでスレッドを作る。
１、 どんなすたっくすれっずのファイルも<st.h>をインクルードすべき。
２、 mainのかわりにst_mainを定義する。main関数は(-nwのような）すたっくすれっずに共通ないくつかのコマンドライン引数を処理し、
セットアップを行ってからst_mainを呼び出す。
すたっくすれっずをmainから呼び出す方法もある。(see section Calling StackThreads/MP Procedure from Sequential Procedure).
３、 すたっくすれっず、とそうではないソースを維持したいなら、predefinedな STHREADS マクロを使おう。
それはすたっくすれっずでコンパイルされたときのみ定義される。(see section STGCC/STG++: A wrapper for GCC for more details).
コンパイル
前のセクションのさんぷるプログラムをコンパイルする。
% stgcc fib.c -o fib
gccに対するフロントエンドstgccを使っている。これはプリプロセッサではなく、gccを適切なオプションで呼び出す単純なスクリプト
（サーチパスやライブラリパスをインクルードしたりする）。
また、自動的にすたっくすれっずらいぶらりとゆーちりちぃをリンクする。
（すたっくすれっずのオプションと衝突しなければ）すべてのgccオプションを受け付け、gccでコンパイルできるCプログラムはstgccでもコンパイルできる。
すたっくすれっずは、簡単なMakefileを作成する小さなユーティリティを提供する。
stmkmf "app_name" > Makefile
とやる。
例えば、fibという名前のアプリケーションを作成したいなら、
stmkmf fib > Makefile
とやる。
（しかしながら、SGCを使っていないときは手動でmakefileの2箇所をコメントする必要があった）
これは、単一のソースファイルを想定している。
複数のソースに対しては 生成されたmakefileの BASES 変数を見よう。
例えば、もし実行ファイル fib が fib.o myutil.o main.o から生成されるとしたら、util main をBASES 変数に追加する。
BASES = $(APP) util main
実行
host% ./fib
とやる。
pfib: 10714 ms on 1 processors, sfib: 2114 ms
と結果がでる。
デフォルトは単一プロセッサで動作するので、１０プロセッサでやりたいなら-nw(number of workersか？：編者注）をつける。
harp:367% ./fib -nw 10
pfib: 1091 ms on 10 processors, sfib: 2062 ms
と結果がでる。
st_main は 引数-nw 10 を見ない。これらはst_mainに入る前に削除される。(see section Command Line Options Common for All StackThreads/MP Programs for more options).
並列版が逐次版よりも5倍ほど遅いことに気づくだろう。
実際にはスレッドの粒度はもっと大きい。
すたっくすれっずは２００命令くらいの粒度のスレッドに十分耐える。(see section A recommended programming style for performance for several advices to achieve good performance on StackThreads/MP ).
ノート：-nwで指定したプロセッサの数は、プログラムのなかで作成されるスレッドの数と関係がない。
-nw 10を与えると、プログラムは10個のOSレベルスレッドを産み出す。
そらりすだとLWPのように、OSレベルスレッドはOSによって直接サポートされるスレッド。
我々は、ここから後、OSレベルスレッドを”わーかー”と命名する。
すたっくすれっずランタイムしすてむは、実行時に作成されたスレッドをワーカーにあげる。
また、我々は-nwでプロセッサ数を指定すると言うが、実際にはワーカーの数を指定している。
特に、一つのワーカーは永久に特定のプロセッサにバウンドされることはない。
ワーカーをプロセッサと混同しても普通は全然問題ない。
基本的なプリミティブ
並列フィボナッチ関数に注目しよう。
1 void pfib(int n, int * r, st_join_counter_t *c)
2 {
3 if (n < 2) {
4 *r = 1; /* write the result */
5 st_join_counter_finish(c); /* say I have done */
6 } else {
7 int a, b;
8 st_join_counter_t cc[1];
9 ST_POLLING(); /* check if somebody is asking work
10 and free stack */
11 st_join_counter_init(cc, 2); /* initialize join counter */
12 ST_THREAD_CREATE(pfib(n - 1, &a, cc)); /* fork fib(n-1, ...) */
13 pfib(n - 2, &b, cc); /* fork fib(n-2, ...) */
14 st_join_counter_wait(cc); /* wait for child's completion */
15 *r = a + b; /* write the result */
16 st_join_counter_finish(c); /* say I have done */
17 ST_POLLING(); /* check if somebody is asking work
18 and free stack */
19 }
20 }
このアルゴリズムは簡単な並列再帰で、１２行目の
ST_THREAD_CREATE(fib(n - 1, &a, cc));
によってなされる。
逐次とは違って並列版は、２つパラメータが多い。２つめのパラーメータ r は帰り値が格納されるストレージへのポインタ。
３つめのパラメータは c は 計算の終了を知らせるストレージへのポインタ。
同期は、"同期カウンタ"がする。８行目で、
st_join_counter_t cc[1];
とカウンタを宣言する。
１１行目でカウンタを２に初期化する。
st_join_counter_init_(cc, 2); /* initialize join counter */
これは、２つの手続きがこのカウンタに関連づけられることを示す。２つの手続きは１２、１３行目にある。
ST_THREAD_CREATE(pfib(n - 1, &a, cc)); /* fork fib(n-1, ...) */
pfib(n - 2, &b, cc); /* fork fib(n-2, ...) */
カウンタ cc が両方の手続き呼び出しに与えられている。
pfib が終了したら、５、１６行目でカウンタを１減す。
st_join_counter_finish(c);
２つの手続きが終了したら、カウンタの値はゼロになる。
１４行目で親は、カウンタの値がゼロになるのを待つ。
st_join_counter_wait(cc);
手続きは最初に帰り値を格納してから、カウンタを1減す
逆に言えば、親はカウンタで待ってから帰り値を読み出す。
もしこの順番を守らなければ期待した値が渡されないことがあり得るので、この順番は重要。
このやり方が面倒だと思う人もいるだろう。でも、大丈夫。
同期カウンタとラッパー関数があるデータ構造を使えば、シンタクティクにより良い。例えば、int_box データ構造体
typedef struct int_box
{
int val;
st_join_counter_t c[1];
} * int_box_t;
と、２つのラッパー関数 void int_box_write(int_box_t b, int x) 、int int_box_read(int_box_t b) を定義してみる。
void int_box_write(int_box_t b, int x)
{
b->val = x;
st_join_counter_finish(b->c);
}
int int_box_read(int_box_t b, int x)
{
st_join_counter_wait(b->c);
return b->val;
}
他の制約のために、新しいプリミティブを追加するのもむずかしくない。
See section Implementing Synchronization Primitives for the bottom-level machinery for implementing new synchronization primitives.
ここまでに、 ST_THREAD_CREATE（スレッド生成） と 同期カウンタ（スレッド間同期）を説明した。残りは、９、１７行目の ST_POLLING だな。
えーとだね、 ST_POLLING は目に見える効果がないんだな。
ST_POLLING がしている１つのことは、そのプロセッサがアイドルプロセッサがスレッドを要求して来ていないかどうかをチェックし、もしあればスレッドを与える。
スレッドが移動する方法、スレッドがどのプロセッサに属しているか、について理解する必要なし。
でも、スレッドは ST_POLLING を時々呼ばなければスレッドが並列に実行されないことを理解する必要あり。
もしアイドルプロセッサが存在すれば、ST_POLLING は ワークを分散する。
See section Where should you insert ST_POLLING? for hints as to where to insert ST_POLLING.
要するに、逐次を並列に書き換えるには、次のステップを踏めばよい。
１、 並列性を抽出：ST_CREATE_THREADを挿入する。先祖代々受け継がれてきたスレッドライブラリとは異なり、すたっくすれっずではすんごく多いスレッド生成は全く問題ない。
２、同期を導入：安全性を保証するために適切な場所に挿入しなければならない。例えば、スレッドが値を書き込んだり資源を解放するのを待つ。
３、仕事を分散：プログラマが定期的にST_POLLING を挿入して、プロセッサ間に仕事を分散させてやらなければならない。(where shoud I best insert ST_POLLING or how oftern should I best insert it to maximize parallel performance?that's an awkward burden for the programmer.：編者注)
APIs
スレッド生成
しんたくす：
ST_THREAD_CREATE(e);
ここで、e は手続き呼び出し。
SPARC上で引数として構造体を渡すときは、特別の注意が払われなければならない。
(see section Structure passing on SPARC).
Pthreadsとの違いは、パラメータの数がいくらでもよい、コストが非常に小さいこと（~１０命令）。
よって、計算が手続き呼び出しのオーバーヘッドに耐えれば、スレッド生成のオーバーヘッドにもおそらく耐えるだろう。
引数の位置にたいする制約はもうちょっと緩和される；つまり、標準ライブラリのprintfとかatoiとか、すたっくすれっずのぷりみちぶを呼ばない手続きを許す。
しかし、上の規則は単純な安全ネット（？safety net）によって思い出される。例えば、
ST_THREAD_CREATE(f(1, 2, 3, 4, 5));
は妥当。
ST_THREAD_CREATE(f(atoi(argv[1])));
は妥当。なぜならatoiは絶対にすたっくすれっずのぷりみちぶを呼ばないから。最後に、
ST_THREAD_CREATE(f(g(x)));
は、もしgがすたっくすれっずのぷりみちぶを全然呼ばないのなら、妥当。
シンタクス：
ST_POLLING();
目に見える効果はないが、定期的にこのマクロをよばなければならない。
２つの仕事をする。
１つはスレッドマイグレーショウン要求がアイドルプロセッサから来ていないかをチェックして、あれば返事する。
もう１つは、スタックフレームのいくつかを解放する。
See section Where should you insert ST_POLLING? for where to insert this in your program.
ST_POLLING のオーバーヘッドをそんなに心配しすぎなくて良い。
もし、すべてのワーカーがビジーで、かつ全くスタックフレームを解放する必要がなければ、オーバーヘッドは１０から２０命令くらいですむ。
同期
mutex、セマフォ、条件変数などの同期ぷりみちぶを提供する。
mutex、条件変数は pthreadのそれと同じ振る舞いをする。pthreadでサポートされていないセマフォは、ソラリススレッドのそれと同じ振る舞いをする。
すたっくすれっずはまた、ジョインカウンタという生産者ー消費者の同期ぷりみちぶもサポートする。
これらのすべての待つためのプリミティブは、条件が満たされないと現在実行中のスレッドをブロックして他のスレッドをスケジュールする。
ノート： 次の記述の中で、"xxx signals an error, when ... "と言うが、この意味はライブラリのコンパイルされ方による。
これらの手続きは src/st_sync.cにあり、このファイルの先頭に #define ST_DIE_ON_ERROR 1 とうマクロを含む。
このフラグは、デファオルトでは１にセットされるが、その時は "signals an error" は、エラーが起こった時にアプリケーションが死ぬことを意味する（UNIXのシグナルとは全く関係ない）。
これはデバッグのときに役に立つ。
このフラグがゼロのときは、単に手続きがエラー値(ST_FAULT)を返すことを意味する。
ジョインカウンタ
シンタクス：
int st_join_counter_init(j, v);
int st_join_counter_wait(j);
int st_join_counter_finish_1(j, v);
int st_join_counter_finish(j)
int st_join_counter_spawn_1(j, v);
int st_join_counter_spawn(j)
int st_join_counter_destroy(j);
st_join_counter_t * j, unsigned long v;
st_join_counter_t x = ST_JOIN_COUNTER_INITIALIZER;
単純な生産者ー消費者スタイルの同期。内部では非負数を保持。
st_join_counter_init(j, v)はカウンタjをvに初期化。これは他のスレッドが並列にjにアクセスしていないときに呼ばなければならない。
st_join_counter_finish_1(j, v) and st_join_counter_spawn_1(j, v)はアトミックにカウンタjの値をvだけインクリメント、デクリメントする。
st_join_counter_finish(j) と st_join_counter_spawn(j) は st_join_counter_finish_1(j, 1) と st_join_counter_spawn_1(j, 1)の同義語。
st_join_counter_wait(j) はjがゼロになるのを待つ。
st_join_counter_destroy(j) はjを破壊する。これは他のスレッドが並列にjにアクセスしていないときに呼ばなければならない。
これはまた、カウンタがゼロかどうかをチェックし、そうでなければエラーシグナルを送る。
st_join_counter_t x = ST_JOIN_COUNTER_INITIALIZER(c) はcに初期化される大域的またはスタティックな変数を定義する。
カウンタが正しく初期化され各使用の後にdestroyされている限り、１つのカウンタを何度もリサイクルしてもよい。
典型的な同期カウンタの使用法は、子スレッドの完了を待つ。例えば、
{
st_join_counter_t j[1];
st_join_counter_init(j, n);
for (i = 0; i < n; i++) {
ST_THREAD_CREATE(f(..., j));
}
st_join_counter_wait(j);
}
ここで、f(..., j) は終わる前に st_join_counter_finish(j) を呼び、 st_join_counter_wait(j) はループで生成された全てのスレッドの完了を待つ。
st_join_counter_spawn と st_join_counter_spawn_1 はどれだけの数のスレッドがカウンタに関連づけられているかが分からないときのためにある。
１つのスレッドを生成するたびごとに st_join_counter_spawn によってカウンタをインクリメントし、それからスレッドを作成する。
これら全ての関数は成功時にゼロを返し、エラー時にエラーシグナルを送る。
セマフォ
シンタクス:
int st_sema_init_1(s, c, lim);
st_sema_init(s, c);
int st_sema_wait(s);
int st_sema_trywait(s);
int st_sema_post(s);
int st_sema_destroy(s);
st_sema_t * s; int c, int lim;
st_sema_t x = ST_SEMA_INITIALIZER_1(c, p);
セマフォはスレッドが共有する限られた資源を管理する。
セマフォは内部ではカウンタを持つ。
st_sema_init_1(s, c, lim) は カウンタ sをcに初期化する。
limが正数だと、カウンタの上限を支持する。
st_sema_init(s) は st_sema_init_1(s, 0) （上限なし）の同義語。
st_sema_wait(s) はカウンタsが正数になるのを待って、カウンタを1つデクリメントする。
st_sema_trywait(s) はカウンタが正数でない場合に、 すぐにST_BUSYを返すことを除けば、st_sema_wait(s)と同じように動作する。
t_sema_post(s) はカウンタsを１つインクリメントする。
もし、st_sema_init(s) が上限を課しておりインクリメントの後カウンタがが上限値を越えていれば、エラーをシグナルする。
st_sema_destroy(s) はsを破壊する。これはもしカウンタsが初期化時の値と同じでなければ（すなわち st_sema_post が st_sema_wait と同じ回数呼ばれなかったら）、エラーをシグナルする。
st_sema_t x = ST_SEMA_INITIALIZER_1(c, p) はカウンタの値がcで上限がpとなるとなる大域的あるいはスタティックな変数x を宣言する。
これら全ての関数は成功時にゼロを返し、エラーが起こればエラーを返す。
みゅーてっくす
シンタクス：
int st_mutex_init(m);
int st_mutex_trylock(m);
int st_mutex_lock(m);
int st_mutex_unlock(m);
int st_mutex_destroy(m);
st_mutex_t * m;
st_mutex_t x = ST_MUTEX_INITIALIZER;
みゅーてくすは本質的には上限が１となる2進セマフォのこと（セマフォは０か１の値だけを持つことができる）。
みゅーてくすはロックかアンロックの状態のどちらか。
st_mutex_init(m) はアンロック状態に初期化する。
st_mutex_lock(m) はmがアンロックになるのを待ってからそれをロックする。
st_mutex_trylock(m) は st_mutex_lock(m) のように動作するが、mがロックされていればすぐに ST_BUSY を返す。
st_mute_unlock(m) は m をアンロックする。It signals an error if m is not locked.
st_mutex_destroy(m) destroys m.
It signals an error if m is locked.
st_mutex_t x = ST_MUTEX_INITIALIZER defined a global or static mutex.
条件変数
シンタクス：
int st_cond_init(c);
int st_cond_wait(c, m);
int st_cond_signal(c);
int st_cond_broadcast(c);
int st_cond_destroy(c);
st_cond_t * c; st_mutex_t * m;
条件変数は、様々な同期が構築される一般的な機構。
スピンロック
簡単なスピンロックプリミティブのセットを提供する。
「read-and-lock」プリミティブによってアトミックに読みだししロックすることが可能。
ロケーションがアンロックになるのを待って、そのロケーションをアトミックにロックする。
帰り値は前にそのロケーションに書き込まれた値。
「write-and-unlock」プリミティブによってロックされたロケーションをアンロックすることができる。
値とロックされたロケーションを引数に取って、その値をそのロケーションに書き込み、そのロケーションをアンロックする。
そのロケーションはロックされていなければならない。そうでなければ動作は未定義。
これらのプリミティブは別個のlock単語を使わないで単一のロケーションにアトミックなread-modify-write を行うときに有用。
加えて、ロケーションが現在ロックされているときでさえ値を読むことができる。（？）
注意： 全てのロックぷりみちぶ(st_read_and_lock_xxx)はある回数のロックを試みたあとで失敗する。
失敗すると、プログラムはスタックトレース情報をプリントした後で終了する。
デバッグを簡単にするので、これは典型的にはよいこと。（ロケーションをアンロックするのを忘れたことが次にロックをしようとしたときに検知される）
一方、理論上さもなければ正しいプログラムをキルしてしまうこともあり得る。
しかしながら、大抵の場合、ロックを獲得するのに失敗したとき、ロックをとるのが長すぎがかとても競合しているロケーションにspin-lockを取っていること（両方とも謝り）を示す。
大抵の場合、ロック戦略を変えるべき。
See section Initialization, Lock, and Unlock for more about this.
初期化、ロック、アンロック
シンタクス：
typedef struct st_int_loc st_int_loc_t;
typedef struct st_long_loc st_long_loc_t;
typedef struct st_ptr_loc st_ptr_loc_t;
int st_read_and_lock_int(il);
long st_read_and_lock_long(ll);
void * st_read_and_lock_ptr(pl);
void st_write_and_unlock_int(il, i);
void st_write_and_unlock_long(ll, l);
void st_write_and_unlock_ptr(pl, p);
int ST_INT_LOC_INIT(il, i);
long ST_LONG_LOC_INIT(ll, l);
void * ST_PTR_LOC_INIT(pl, p);
st_int_loc_t * il; int i;
st_long_loc_t * ll; long l;
st_ptr_loc_t * pl; void * p;
st_int_loc_t v = ST_INT_LOC_INITIALIZER(x);
st_long_loc_t v = ST_LONG_LOC_INITIALIZER(x);
st_ptr_loc_t v = ST_PTR_LOC_INITIALIZER(x);
st_int_loc_t型はロックビットによってタグ付けされた整数型。同様に st_long_loc_t と st_ptr_loc_t はそれぞれ long と void *に対応する。
st_read_and_lock_int(il) はi1で指定されたロケーションがアンロックになるのを待つ。
アンロックされると、アトミックにロケーションをロックし、ilに以前に書き込まれた値を返す。
ロックビットは奪い取られる。
st_read_and_lock_long(ll) と st_read_and_lock_ptr(pl) は同じように動作するが、 st_loc_long_t と st_loc_ptr_t のそれぞれの型の値を持つ。
st_write_and_unlock_int(il, i) はilロケーションに値iを書き込み、そのロケーションをアンロックする。
そのロケーションは手続きを呼ぶときにロックされていなければならない。
st_write_and_unlock_long(ll, l) と st_write_and_unlock_ptr(pl, p) は st_long_loc_t * and st_ptr_loc_t *のそれぞれに対応する。
ST_INT_LOC_INT(il, i) はロケーションilをiで初期化する。アンロック状態に初期化される。
ST_LONG_LOC_INT(ll, l) と ST_PTR_LOC_INT(pl, p) は st_long_loc_t * と st_ptr_loc_t * のそれぞれに対応する。
st_int_loc_t v = ST_INT_LOC_INITIALIZER(x); はxに初期化される st_int_loc_t型の大域的あるいはスタティック変数を定義する。
ST_LONG_LOC_INITIALIZER(x) と ST_PTR_LOC_INITIALIZER(x) は st_long_loc_t and st_ptr_loc_t のそれぞれに対応する。
st_read_and_lock と st_write_and_unlock はアトミックな一連の read-modify-write を単一のロケーションで行う。例えば、
st_int_loc_t il = ST_INT_LOC_INITIALIZER(1);
void read_modify_write()
{
int x = st_read_and_lock_int(&il);
st_write_and_unlock_int(&il, 3 * x);
}
このコードはアトミックにロケーションilの値を3倍する。
所見１：st_read_and_lock_xxx というプリミティブは決して呼び出したスレッドをブロックしない；スピンによって、単にロケーションがアンロックになるのを待つ。
それゆえ、できるだけクリティカルセクションが小さくなるように努力をしよう。
どれくらい短ければ良いか？大雑把にいうと、２つの算術と２つのload、store以上は避けよう。
mallocのような動的なメモリアロケーションは避けよう。
ロックされているロケーションにロックを取ろうとしたら、デッドロックの原因になる。
もし、長いクリティカルセクションが避けられないのなら、最初にスピンロックを使うべきではない。ブロック同期プリミティブを使用すべき。
既に示されたように、すたっくすれっずは st_mutex_t を提供している。
それでも、スピンロックは短いクリティカルセクションでは役に立つ。
クリティカルセクションは大抵の場合短くすることが可能であり、その場合には時間と空間の効率が良いので、無条件にブロックプリミティブを採用できない。
間違ったスピンロックの使用による深刻なパフォーマンスの低下とデッドロックを避けるために、st_read_and_lock プリミティブはある回数の試みの後にタイムアウトする。
もっとはっきりと言うと、連続して１０００回ロックの獲得に失敗したら、１ミリセカンドスリープしてから再試行する。
この過程を10回繰り返す。
まだロックが認められないなら、エラーメッセージを出してdieする。
これは、そうでなければ正しかったかもしれないアプリケーションをキルする。
しかしながら、これは必要なアンロック操作を忘れたことによるプログラミングエラーを検知する。
たとえ、アプリケーションがうまく動作しているにせよ、ロックを１０ミリ秒も保持しているのは、典型的にはパフォーマンスを低下させるので、ロック戦略が間違っていることの示唆として、エラーメッセージを出すべき。
所見２： これらのプリミティブは２つのビットが単一のワード内部のタグに対して埋め込まれていることを想定する。
例えば、int が３２ビットとなるマシンでは、st_int_loc_t はleast significantな２ビットをタグに使用する。
この値は２びっと左シフトして、most significantな３０ビットを格納されている。
結果的に、most significantな２ビットは値がストアされると捨てられる。
逆に、値が読み込まれると、most significantな２ビットは符合拡張される。
だから、st_int_loc_t によって表現される値は -2^30 から 2^30 - 1 に制限される。
ポインタとして、ポインタの値が４バイトアライメントされていることを想定する。
つまり、ポインタのleast significantな２ビットがゼロで、それらの２ビットをタグに使用する。
適切にアラインされていない値が st_write_and_unlock_ptr に与えられると、least significantな２ビットは単に捨てられる。
ロケーションの読み込みとチェック
シンタクス：
int st_read_int(il);
long st_read_long(ll);
void * st_read_ptr(pl);
int ST_INT_LOC_CHECK(il, i);
int ST_LONG_LOC_CHECK(ll, l);
int ST_PTR_LOC_CHECK(pl, p);
int ST_INT_LOC_LOCKED(il);
int ST_LONG_LOC_LOCKED(ll);
int ST_PTR_LOC_LOCKED(pl);
st_read_int(il) はilロケーションの値を読むが、そのロケーションをロックしない。
それは、ロケーションがロックされていても値をすぐに読み出す。
st_read_long(ll) と st_read_ptr(pl) aは st_long_loc_t * と st_long_ptr_t * のそれぞれの型に対応する。
ST_INT_LOC_CHECK(il, i) は ilが現在アンロックで、iに等しいと1となる（を返す？）。
これは、意味的には (st_read_int(il) == i) と等しいが、あるCPUでは、こちらの方がかなり速い。
ST_LONG_LOC_CHECK(ll, l) と ST_PTR_LOC_CHECK(pl, p) は st_long_loc_t * と st_ptr_loc_t * のそれぞれに対応する。
ST_INT_LOC_LOCKED(il) は もしロケーションilが現在ロックされていれば、1となる。
ST_LONG_LOC_LOCKED(ll) と ST_PTR_LOC_LOCKED(pl) は st_long_loc_t * と st_ptr_loc_t * とにそれぞれ対応する。
トライロックとどれかをロック
シンタクス：
int st_read_and_lock_any_int(il, els, n, ires);
int st_read_and_lock_any_long(ll, els, n, lres);
int st_read_and_lock_any_ptr(pl, els, n, pres);
int st_try_read_and_lock_int(il, ires);
int st_try_read_and_lock_long(ll, lres);
int st_try_read_and_lock_ptr(pl, pres);
int els; int n;
st_int_loc_t * il; int * ires;
st_long_loc_t * ll; long * lres;
st_ptr_loc_t * pl; void ** pres;
ilがアドレスaを指しているとしよう。st_read_and_lock_any_int(il, els, n, ires) は { a, a + els, a + 2 els, ... , a + (n - 1) els }のどれかのロケーションをロックする。
ロックされたロケーションのインデクスを返す。すなわち、もしアドレスa + k els なら k を返す。
また、前に a + k els に書かれていた値を *ire に書き込む。
その後、ロックされたロケーションは、アドレス a + k els に st_write_and_unlock_int を適用させることによって解放される。
st_read_and_lock_any_long と st_read_and_lock_any_ptr は st_long_loc_t * と st_ptr_loc_t * にそれぞれ対応する。
これらのプリミティブは複数の資源が入手可能でそのうちどのリソースでも入手可能ならロックしたいときに役に立つ。
st_try_read_and_lock_int(il, ires) はロケーションをロックしようと試みる。
もしロックの獲得に成功すれば、以前にilに書き込まれていた値を*iresに書き出す。
さもなければ、-1を返す。
st_try_read_and_lock_long と st_try_read_and_lock_ptr は st_long_loc_t * と st_ptr_loc_t * のそれぞれに対応する。
フェッチあんどアッド
シンタクス：
int st_fetch_and_add_int(il, ix);
long st_fetch_and_add_long(ll, lx);
st_int_loc_t * il; int ix;
st_long_loc_t * ll; long lx;
st_fetch_and_add_int はアトミックにilに書き込まれた値をixだけインクリメントし、以前に書き込まれていた値をilに書き出す。
st_fetch_and_add_long は st_long_loc_t * に対応する。
いーるど
シンタクス：
void st_yield();
は一時的に現在のスレッドをデスケジュールする。そのスレッドはあとでスケジュールされる。
たいていの並列プログラムでは、実行中のスレッドをデスケジュールしなければならない理由はないはず。
われわれはこの手続きを特定のイベントが起こるのを待つのに使用しないように勧める。
そのような状況では、スレッドをサスペンドし、条件が満たされたときに他のスレッドにレジュームさせねばならない。
スタックとコンテキスト
実行中のワーカーのスタックの使用情報を得るいくつかの手続きがある。
これら全ての手続きは普通はプログラマに興味はない。
これらはスタックのデバッグと理解のため、スタックフレームが再利用されたときに正確にコントロールするため、に提供される。
現在のスタックサイズを調べる
シンタクス：
long st_stack_used_bytes()
は呼び出しワーカのスタックサイズをバイトで返す。現在のスタックトップとスタックボトムの距離を返す。
はっきりとスタックリミットを返すのではなく、現在占められているスタックのサイズを返す。
スタックサイズは手続きが呼ばれたときにインクリメントされ、手続きがリターンした時、あるいは ST_POLLING または ST_FREE_STACK が呼ばれた時に、 デクリメントされる。
スタックトレースを示す
シンタクス：
void st_stack_trace()
void st_show_context(c)
st_context_t c;
void st_show_exported_frames()
int st_n_live_exported_frames()
st_stack_trace() は呼び出しワーカのスタックトレースを現在のフレームから下方向にスタックボトムまでをプリントする。
呼び出しワーカのスタックボトムに達するか、５０フレームがプリントされるか、ポストプロセスされていない何らかの手続きに出会うとプリントをやめる。
占められているスタックを５０フレーム安全にプリントするとプリントをやめる。
もっとフレームをプリントしたいなら、 st.cの MAX_STACK_TRACE_DEPTH の定義を変えてコンパイルしなおそう。
cを st_suspend_thread で満たされるコンテキストだとして、st_show_context(c)はcで表現されるフレームを表示する。
st_show_exported_frames() は呼び出しワーカのスタックの中にアロケートされている、サスペンドしたコンテキストを表示する。
st_n_exported_frames() はそのようなコンテキストの数を返す。
スタック管理を呼び出す
シンタクス：
void ST_FREE_STACK()
はスタック管理を呼び出す。
これはもう使用されていないフレームを調べ、呼び出しワーカのスタックポインタを適切な場所（それより上にはフレームが使用されていないようなポイント）にリセットする。
これは ST_POLLING()を実行すると暗黙のうちに呼び出されるので、たいていは興味ないはず。
このAPIはすたっくすれっずの動作を理解し、スレッドマイグレーションをしないでスタックフレームを解放したいときに使おう。
スタックポインタとフレームポインタ
シンタクス：
void * asm_get_fp()
void * asm_get_sp()
void * asm_get_gp()
asm_get_fp() はフレームポインタを返す。
asm_get_sp() はスタックポインタを返す。
グローバルレジスタを持っているマシンでは、 asm_get_gp() はグローバルレジスタの値を返す。
グローバルレジスタを持っていないマシンでは、 asm_get_gp() は利用可能でない。
すべての手続きは呼び出し手続きから見える値を返す。
例えば、手続き f が asm_get_fp() を呼び出すと、f が実行中なら、フレームポインタレジスタの値を返す。
手続きが asm_get_fp() と asm_get_sp() を呼び出してみると、その値に驚くかもしれない；
すたっくすれっずでは、フレームポインタレジスタはいつも実行フレームを指す。一方、スタックポインタレジスタはいつもワーカのスタックトップを指す。
両方のポインタはスタックトップにアロケートされたフレームを指しているので、これらの２つの値は逐次の実行ではそんなに異ならない。
しかし、すたっくすれっずでは実行フレームはスタックトップにないかもしれないし、スタックトップからかなり離れているかもしれない。
他のワーカのスタックに存在さえしているかもしれない。
また、手続きが asm_get_sp() を何度も呼び出したとき、各時に異なる値を返すかもしれない。
これは実行フレームの上に他のフレームがある可能性があるから。
一方、asm_get_fp() の値は同じ手続きから呼び出されている限り、同じ値を返す。
帰り値は、手続き呼び出しの アイデンティファイア として役に立つ。
プロファイラ
シンタクス：
void st_config_profile_resolution(resolution);
int resolution;
void st_config_profile_max_intervals(buffer_size);
int buffer_size;
void st_config_profile_filename_prefix(filename);
char * filename;
void st_begin_profile();
void st_end_profile();
See section Performance Profiler for more information.
タイミング
シンタクス：
long st_current_time_ms()
long st_current_time_us()
それぞれ、現在の時間をミリ秒とマイクロ秒で返す。
呼び出し間の差異だけが意味をなす。
ワーカーずとワーカーグループず
ワーカは下位のsolalisスレッドライブラリやpthreadライブラリのようなOSスレッドのこと。
普通は、すたっくすれっずはプログラムの初期化時に個定数のワーカを作成し、st_main によって作成されるスレッドを直接／間接的に共有する。
単純なすたっくすれっずの使用では次の手続きを理解する必要はない。ワーカとかワーカグループの考えを知る必要もない。
すたっくすれっずはマルチスレッド機能へアクセスする他のやり方も許している。
はっきりいうと、動的にワーカの他のグループを作成し、ワーカーずを既存のグループへ追加することができる。
ワーカグループを実行時に作成することはいくつかの状況で役に立つ。
最初の状況は、ワーカのグループを複数持っていてそれらを隔離しておきたいとき；
スレッドは単一のグループ内部のワーカによってのみ共有され、スレッドはあるグループから他のグループへ移動しない。
第二の状況は、ワーカずのグループを実行時に作成することはOSレベルスレッドの数を増やしたり減したりする。
特に、アプリケーションは時間の大半を単一のスレッドで費やし、計算が集中した仕事を並列に行うワーカずのグループを作成すことがあり得る。
タスクが終了すると、全てのワーカずは死に、アプリケーションは単一スレッドの状態に戻る。
実際には、もし、アプリケーションが並列性を持っていおらず、アイドルスレッドがCPU時間を消費している事実に注意を払わなければ、このようなアプリケーションは動的にワーカーグループを作成することなしに構築することができる。
第三の状況は、他のすたっくすれっずの手続きと違って、ワーカグループを作成する手続き(stf_create_worker_group)がstgccでコンパイルされていないプログラムから呼び出されてもかまわない。
このようにして、ソースが手に入らないライ無頼からのコールバックとして使用できる。
グループを作る
シンタクス：
#include
void* stf_create_sync_worker_group(wgc, n, f, a0, a1, a2, a3)
void stf_create_async_worker_group(wg, wgc, n, f, a0, a1, a2, a3)
void* stf_wait_for_wg_to_exit(wg)
int stf_did_wg_exit(wg)
struct worker_group * wg;
struct worker_group_conf * wgc;
int n;
void * (*f)(void *, void *, void *, void*);
void * a0, * a1, * a2, * a3;
Both stf_create_sync_worker_group and stf_create_async_worker_group create a group of workers that initially consists of n workers.
f specifies the entry function and a0 ... a3 its arguments;
the group as a whole performs f(a0, a1, a2, a3), sharing threads created directly or indirectly from f.
wg is a pointer to an uninitialized storage of type struct worker_group.
Created workers exit when f returns, no matter whether there are running threads that belong to the group.
stf_create_sync_worker_group returns when workers exit.
The return value is the return value of f.
On the other hand, stf_create_async_worker_group returns immediately.
stf_wait_for_wg_to_exit(wg) waits for workers that belong to wg to exit (by blocking the underlying worker) and returns the return value of the entry function of wg. stf_did_wg_exit(wg) returns 1 if workers that belong to wg have already exited and 0 otherwise.
スレーブワーカを追加する
シンタクス：
void st_add_slave_worker()
adds a worker to the worker group that the current thread belongs to.
Currently there are no ways to remove a worker from a group.
ワーカ間でメッセージをチェックする
シンタクス：
void ST_STEAL_REQ_CHECK();
checks if an idle worker in the same group as the calling worker is requesting a thread migration from the calling worker.
If it is, it gives an appropriate thread to the requesting worker.
This is implicitly called by ST_POLLING(), so this should be usually of no interest for you.
Use this API only when you understand how StackThreads/MP works and when you want to migrate threads without freeing stack frames.
ワーカをデスケジュールする
シンタクス：
void st_yield_os_thread()
void st_sleep_os_thread_ms(ms)
int ms;
st_yield_os_thread() instructs the operating system to temporarily deschedule the calling worker (not thread).
Recall that in general many threads are running on top of a worker.
Descheduling a worker effectively deschedules all threads that are running on top of it.
The exact effect depends on the operating system and the underlying execution machinery of OS-level threads.
Specifically, it is likely to have no effects when the number of workers are less than the number of available CPUs.
st_sleep_os_thread_ms(ms) instructs the operating system to deschedule the calling worker (not thread) for ms microseconds.
Use these APIs only when you understand how StackThreads/MP works and you are sure they are really necessary.
Specifically, it is usually a bad idea to call these primitives to achieve a synchronization.
You should normally suspend the current thread (not the entire worker) and explicitly resume it when it can make a further progress.
コールバック
シンタクス：
ST_CALLBACK_BEGIN();
ST_CALLBACK_END();
これら２つの手続きは一緒に囲んでいる手続きが逐次プログラム（普通のgccでコンパイルされた手続き）から呼ばれることを宣言する。
手続き f が逐次プログラムから呼び出されると、ST_CALLBACK_BEGIN() は f の変数宣言の先頭に置かれていなければならない。
（ST_CALLBACK_BEGIN() は変数宣言に展開されるマクロ）
ST_CALLBACK_END() は f からリターンする直前に置かれていなければならない。
正確に言うと、 f は f の中のあらゆるサブ手続き呼び出しの前に ST_CALLBACK_BEGIN() を、 f の中のあらゆるサブ手続き呼び出しの後に ST_CALLBACK_END() を実行しれなければならない。
ST_CALLBACK_END() はシンタクティックに2度以上出現してもよい（もしそのうち１つだけが実行時に実行されるのでなければ（？））
See section Cooperating with Sequential Modules for more about this topic.
優雅なエグジット
シンタクス：
void st_wg_exit(wv);
void st_wg_die(wv);
void st_app_exit(av);
void st_app_die(av);
void * wv; int av;
st_wg_exit(wv) exits the worker group the calling thread belongs to and returns wv as the return status of the worker group. When the worker group is the toplevel group, the group that executes st_main, it exits the entire application. This is the preferred way of terminating an application.
st_wg_die(lv) behaves like st_wg_exit(av), except that it prints stack trace of the calling worker before exiting. It is advisable to call this procedure whenever a fatal error occurs, so that the application prints some useful pieces of information for debugging.
st_app_exit(av) simply kills the entire application by exit(av) on UNIX. st_app_die(av)) behaves like st_app_exit(av), except it prints the stack trace of the calling worker before dying.
すれっど移動
すれっどをサスペンドする
シンタクス：
void st_suspend_thread(st_context_t c);
where st_context_t is defined as follows:
typedef struct st_context * st_context_t;
この手続きと次の(resume_context)はボトムレベルプリミチブ。
プログラマがこのレベルでプログラムを書くとを期待していない。
既存のものからは簡単には作れない新しい同期を実装するのに役立つことがあるので記述した。
st_suspend_thread はスレッドをサスペンド（またはブロック）し、スレッドのコンテキストと呼ぶもので、Cが指す構造体をうめる。
それで他のスレッドが後でレジュームすることができる。
この手続きを呼び出すときには、validフィールドはクリア（ゼロに）されなければならない。
正しい使用を示す具体例は、
struct st_context c[1];
c->valid = 0;
st_suspend_thread(c);
... (xxx) ...
コントロールは即座に（xxx）に返らない。
それは、他の誰か明示的にそれをレジュームしたときにだけ実行される。
C->valid == 0 となるとき、構造体がスレッドのコンテキストによってうめられようとしているが、完了していないことを示す。
スケジュールする用意ができたときに、st_suspend_thread はvalid を１にセットする。
何よりも前に、st_suspend_thread は C->valid がクリアされているかをチェックし、クリアされていなければランタイムエラーをシグナルする。
大抵の場合、他のスレッドが見つけられるように、st_suspend_threadを呼ぶ前に他のどこかへのポインタをストアしたい。
スレッドをレジュームする
シンタクス：
void st_resume_context(st_context_t c);
st_resume_context はst_suspend_threadによってサスペンドされたスレッドを再開するボトムレベルライブラリ。
構造体st_context へのポインタを取り、st_suspend_threadしたスレッドの実行を再開する。
Procedure Information
Syntax:
st_proc_info_t st_get_proc_info(pc, zero_if_not_found, pi)
void * pc; int zero_if_not_found; st_proc_info_t pi;
int st_is_fork_point(pc)
void * pc;
void st_add_procedure_information_table(table)
st_proc_info_t * table;
Not documented yet.
Thread and Worker ID
Syntax:
extern long tls(worker_id);
long st_n_current_workers();
extern long tls(thread_id);
tls(worker_id) is an identifier of the calling worker within the worker group it belongs to. It holds a value from zero to n-1, where n is the number of workers withing the worker group the calling worker belongs to. When a worker group is created by stf_create_async_worker_group or stf_create_sync_worker_group, the entry function starts execution on the worker zero.
tls(thread_id) is a global identifier of the calling worker. It holds from zero to n-1, where n is the number of workers which have ever been created from the beginning of the program execution. The same identifier is (currently) not reused.
st_n_current_workers() returns the number of workers that currently belongs to the worker group that the calling worker belongs to. The worker group is initially created with the number of workers specified with the argument to stf_create_async_worker_group or stf_create_sync_worker_group (or the argument to -nw option in the case of the toplevel worker group) and may later be extended by st_add_worker(). The value returned by st_n_current_workers() at any moment may be smaller than the number of workers you have requested to create. For example, if you create a worker group that initially has 4 workers and performed st_add_worker() 3 times, st_n_current_workers() at a given moment may return any value from 1 to 7.
tls(worker_id) and tls(thread_id) can be used to guarantee that accesses to a single location do not occur concurrently. For example, the following code increments an element of a counter counters_array by one. The summation of all the elements in counters_array hold the total number of updates performed. Assuming counters_array is acceseed only from this worker group, there are no race conditions in counters_array because each access that may occur in parallel at runtime is given a unique value for tls(worker_id).
Syntax:
x = compute_increment();
counters_array[tls(worker_id)] += x;
Note that the value of tls(worker_id) or tls(thread_id) may change even within a single function, as a result of thread suspension or migration. Therefore, in practice, it is always dangerous to assume that they are persistent across a procedure call (including ST_POLLING() and ST_STEAL_REQ_CHECK()). For example, you cannot manually optimize away tls(worker_id) by caching it to a local variable; the following code is probably unsafe.
Syntax:
w = tls(worker_id);
x = compute_increment();
counters_array[w] += x;
Here, there are no guarantee that w at the two increments corresponds to the current worker id, because compute_increment may cause the rest of the computation to block or migrate.
The difference between tls(worker_id) and tls(thread_id) is important only when you create multiple worker groups within a program. However, it is recommended that you use tls(worker_id) where possible, because such programs are likely to be reusable.
Having said all, using tls(worker_id) or tls(thread_id) to gurantee freedom from races are not recommended at all. It is advisable to use a general synchronization method or a spin lock method, such as semaphore or st_read_and_lock_any. For example, the following code achieves the same effect without using tls(worker_id), given that counters_array is an array of st_int_loc_t.
Syntax:
int v;
int x = compute_increment();
int idx = st_read_and_lock_any_int(counters_array,
sizeof(st_int_loc_t), n, &v);
st_write_and_unlock_int(counters_array + idx, v + x);
It dynamically finds a location that is not locked. The size of counters_array is now arbitrary; it does not have to match the number of workers just to avoid out of range indices.
Memory Management
It may sound strange to talk about memory management in this manual. Yes, you can call any memory allocation function, including the standard malloc, from StackThreads/MP programs. However, once you start using StackThreads/MP in any serious parallel programs, you will soon notice that the system's default "malloc" function becomes a severe bottleneck. More specifically, typical malloc functions (including ones in Solaris libc) simply serialize all malloc calls using a mutex. If many threads contend, they cause many thread context switches of the underlying workers. In my experience, calling mallocs within a parallel section almost always makes a significant (negative) effect on performance. There are many xxx-malloc libraries, but most of them similarly serialize all malloc calls or are simply MT-unsafe (sure?).
We therefore provide some recommended alternatives to malloc. We also provide a mechanism with which you can easily replace the underlying memory allocator without changing application sources. With this mechanism, you can switch between several memory allocators (including the system's malloc). In this way, you will know how important are they for performance of parallel programs and what I am saying is not just a threat :-)
There are two (orthogonal) alternatives to the default malloc. One is to replace malloc with SGC library, and the other is a region-based allocator built on top of an underlying malloc. They are orthogonal. You can use either of them or combine both. We describe them in the following sections and then describe a mechanism with which you can easily switch between different memory-management alternatives.
並列保守的GC (SGC)
SGC は共有メモリでの保守的なゴミ集め（GC）ライブラリ。
インタフェースはmallocと同じだが、mallocの呼び出しは時々逐次化される。
並列なGCを行う。
いつGCを行うかを制御できる。
もしあなたが分別なくGCが遅いものと考える生物なら、GCを切って明示的にオブジェクトをfreeすることができる（この場合、SGCを効率的な並列malloc/freeライブラリとして使用する）
SGCは分離したライブラリとして提供される。
http://www.yl.is.s.u-tokyo.ac.jpから入手できる。
StackThreads/MP プログラムか使うためには、コンパイル時に WITH_STHREADS をconfig.mkの中で定義しなければならない。
これは現在 SPARC (Solaris), Pentium (Solaris), R10000 (IRIX)で使用可能。
SGC は Bohem's conservative GC library に由来する。
GC_MALLOC and GC_FREE
The basic API is almost identical to malloc/free:
Syntax:
#include
void * GC_MALLOC(sz);
unsigned int sz;
void GC_FREE(ptr)
void * ptr;
Header file sgc.h comes with SGC, so you have to give an appropriate include search path to stgcc/stg++ (with -I$SGC_DIR, where $SGC_DIR is the directory when SGC is in).
GC_MALLOC(sz) allocates sz bytes of memory. GC_FREE(ptr), where ptr is a value previously returned by a call to GC_MALLOC, returns the allocated memory to the allocator. Functions and variables control behavior of SGC:
Controlling GC behavior
Syntax:
void GC_gcollect(void);
int GC_dont_gc = 0;
int GC_free_space_divisor = 4;
GC_gcollect() explicitly triggers a GC at a point you desire. When GC_dont_gc is zero (this is the default), GC_MALLOC automatically triggers a GC when necessary. In this mode, you neither have to call GC_FREE nor GC_gcollect. When GC_dont_gc is non-zero, GC_MALLOC does not trigger GC (it always expands heap when heap overflows). You reclaim objects either by calling GC_gcollect at a point you desire or by calling GC_FREE on individual objects.
GC_free_space_divisor controls heap expansion policy. It only makes sense when GC_dont_gc is zero. The larger that value is, the more frequently GCs occur and the less aggressively the system expands heap. When heap overflows, SGC either triggers a GC or expands heap. Roughly, when this value is D, it tries to keep one Dth of heap available for allocation. More specifically, suppose a simple application that repeats allocating objects forever and keeps M bytes of them live all the time, the system tries to keep heap size (roughly) H to M + M/(D-1), so that H/D bytes are available for allocation. The long-term behavior in this case is that every H/D bytes of allocations trigger a GC, which reclaims H/D bytes from somewhere in heap. The default value is 4, meaning that it tries to keep 25% of the heap free for allocation. If you feel the system spends too much time on GC, set it to 3 or 2. Other values are hardly useful (note that D = 1 effectively prohibits GC).
There are other functions in SGC. See sgc.h and README.parallel in SGC.
Region-Based Memory Management
Memory management based on explicit regions is available on top of any malloc/free implementation. In this memory management model, an object is allocated on a specified region. You can dynamically create a region and then allocate an arbitrary number of objects in that region. Unlike malloc and free, you do not free individual objects; instead, you reset a region. Resetting a region reclaims all objects allocated in the region. The model is borrowed from Aiken and Gay, Memory-Management with Explicit Regions, PLDI 98, but is different from theirs in that (1) we do not provide any safety guarantee, (2) we do not require a dedicated compiler that understands region, and (3) we provide a reset operation, which make blocks associated with a region immediately reusable for subsequent allocations from the region.
Region Basics
Syntax:
#include
st_region_t st_make_region(void);
void * st_region_malloc(sz, rg);
void st_reset_region(rg);
void st_abandon_region(rg);
st_region_t rg;
unsigned sz;
ralloc.h is located at a place stgcc automatically searches. st_make_region() creates a new region. st_region_malloc(sz, rg) allocates sz bytes of memory from region rg. st_reset_region(rg) resets region rg. That is, it makes all blocks allocated in region rg reusable for subsequent requests with st_region_malloc(..., rg). st_abandon_region(rg) is similar to st_reset_region(rg), but it abandons all blocks associated with rg; it gives them back to the underlying memory allocator.
A region abstracts objects' death point. The basic observation is that objects allocated during a course of computation often die together. Such objects can be allocated from a single region and then freed all at once. This saves time for memory management and avoids fragmentation without a general and sophisticated mechanism.
A region internally keeps as many free lists as the number of workers. Each worker has its own private free list. Each free list is a list of fixed-sized chunks. A single chunk is, by default, 7KB. Associated with a free list are the current chunk pointer (C), which points to the chunk from which allocations are served, the current chunk limit pointer (L), which points to the end of the current chunk, and the allocation pointer (A), which points to a point in the current chunk from which the next allocation will be served. An allocation simply checks if A + the requested size exceeds L, and if it does not, it returns A and advances it by the requested size. Otherwise, the allocation goes on to the next chunk, changing C, L, and A appropriately. When a worker runs out of its private free list, it calls the underlying memory allocator to obtain a new chunk. No attempts are made to obtain one from another worker's free list.
st_reset_region(rg) simply resets its current chunk pointer to the first chunk of the free list and sets other pointers accordingly. It does not give chunks to the underlying allocator. It is st_abandon_region(rg) that does this.
Creating A Region
When a region is created by st_make_region(), free lists are empty. Therefore, allocations from a region gradually grow its free lists, occasionally calling the underlying allocator. As is mentioned in the beginning of this section, it may still suffer performance of parallel sections, if the underlying allocator serializes all allocation requests. One idea is to use SGC as the underlying allocator. If you want to (or must) deal with this problem with the default malloc, you may pre-allocate some chunks upon region creation. Here are the full APIs for creating regions. st_make_region() is repeated for completeness.
Syntax:
#include
st_region_t
st_make_region_aux(chunk_size, init_size,
pre_alloc_option, alloc, free);
st_region_t
st_make_region_highly_concurrent_1(init_size, alloc, free);
st_region_t
st_make_region_highly_concurrent(size);
st_region_t
st_make_region();
With st_make_region_aux, you can control all the parameters. chunk_size is the size of a single chunk. It is the unit of allocation via the underlying allocator. alloc and free specify the underlying allocator; alloc is a function that behaves similarly to the malloc in libc, whereas free is a function that behaves similarly to free in libc.
init_size specifies the initial size of the region in bytes. Each worker allocates init_size/N bytes from the underlying allocator when it makes the first allocation from the region, where N is the number of workers in the worker group the calling worker belongs to. The net effect is that, the region soon becomes approximately init_size bytes in total as long as all workers will soon attempt to allocate at least one byte from this region. If you can approximate the total size of allocations that are going to be made from the region, you can give this value to avoid occasionally calling underlying allocators in parallel sections.
pre_alloc_option specifies whether this first allocation is made at the region's creation time. When pre_alloc_option == st_region_pre_allocated_option_none, no pre-allocation is performed upon creation. Each worker allocates the specified bytes upon first allocation. When pre_alloc_option == st_region_pre_allocated_option_self, the calling worker allocates the specified bytes only for the calling worker. When pre_alloc_option == st_region_pre_allocated_option_all, the calling worker allocates the specified bytes for all the workers.
A commonly used combination is provided by st_make_region_highly_concurrent_1. It intends to be useful for regions from which many allocations are going to be made in a parallel section. It allocates init_size bytes upon creation and evenly distributes them to all the workers. st_make_region_highly_concurrent is a simple wrapper to st_make_region_highly_concurrent_1. It gives the value of a macro RG_ALLOC_FUNC and RG_FREE_FUNC to st_make_region_highly_concurrent_1 as the underlying alloc and free functions, respectively. Their default values are the system malloc and free, respectively, but you can override them before including ralloc.h. For example,
#define RG_ALLOC my_malloc
#define RG_FREE my_free
#include
replaces malloc/free with my_malloc/my_free.
How to Switch between Allocators
On top of two memory allocators described, StackThreads/MP provides a simple layer with which you can easily switch both the underlying allocator and whether the region-based allocator is used. The idea is that once you write a program in such a way that allocates and frees memory using the following primitives, you can experience several memory management mechanisms without changing your program.
Changing the Underlying Allocator
Syntax:
#include
void * MM_ALLOC(sz);
void MM_FREE(ptr);
void MM_ZERO_CLEAR(ptr, sz);
void MM_GC_POINT();
void MM_SETUP(fd);
They are macros whose behavior change according to the following parameter.
#define UNDERLYING_MM ...
It chooses the basic memory allocator and can be selected from the following values:
UNDERLYING_MM_SGC_AUTO_GC
UNDERLYING_MM_SGC_EXP_GC
UNDERLYING_MM_SGC_EXP_FREE
UNDERLYING_MM_MALLOC
UNDERLYING_MM_SGC_AUTO_GC uses SGC and relies on its automatic memory management. UNDERLYING_MM_SGC_EXP_GC uses SGC, but triggers GC only when explicitly requested by MM_GC_POINT(). UNDERLYING_MM_SGC_EXP_FREE uses SGC, but never frees objects by GC. Finally, UNDERLYING_MM_MALLOC uses the system's default malloc.
MM_ALLOC calls the appropriate allocator. MM_FREE(ptr) frees object pointed to by ptr when UNDERLYING_MM_SGC_EXP_FREE or UNDERLYING_MM_MALLOC is given, and otherwise has no effects. MM_ZERO_CLEAR(ptr, sz) clears a block of sz bytes from ptr, only when MM_ALLOC does not zero-fill allocated memory. Whenever you need to zero-clear allocated memory, use MM_ZERO_CLEAR instead of bzero, to avoid duplication of work in case MM_ALLOC already does it. MM_GC_POINT() invokes a GC when UNDERLYING_MM_SGC_EXP_GC is given, and has no effects otherwise. MM_SETUP(fd) sets GC_dont_gc parameter appropriately when a UNDERLYING_MM_SGC_xxx is given. It also sets GC_free_space_divisor to fd.
Changing Region-based Allocator
Interfaces to region-based memory manager is also wrapped.
Syntax:
#include
st_region_t MM_MAKE_REGION();
st_region_t MM_MAKE_REGION_AUX(chunk_size, init_size,
pre_alloc_option, alloc, free);
st_region_t MM_MAKE_REGION_HIGHLY_CONCURRENT_1(init_size,
alloc, free)
void * MM_REGION_MALLOC(sz, rg);
void MM_REGION_FREE(ptr);
void MM_RESET_REGION(rg);
void MM_ABANDON_REGION(rg);
They are macros whose behavior change according to the following parameter.
#define RALLOC ...
RALLOC is either 0 or 1. When RALLOC is 1, all MM_REGION_xxx, except for MM_REGION_FREE(ptr), are equivalent to st_region_xxx. For example, MM_MAKE_REGION() is equivalent to st_make_region(). MM_REGION_FREE(ptr) has no effects. When RALLOC is 0, all MM_REGION_xxx things are redirected to the underlying allocator. For example, MM_REGION_MALLOC(sz, rg) ignores the region parameter and is equivalent to MM_ALLOC(sz). MM_REGION_FREE(ptr) behaves like MM_FREE(ptr).
Alloca is not supported (yet)
alloca is sometimes used to optimize memory allocation. It behaves like malloc, but automatically frees the allocated storage when the procedure that called it returns. It is normally implemented by allocating a block of memory on top of the stack, effectively extending the currently running frame.
I have to tell you that alloca is currently not supported with StackThreads/MP, as the standard implementation of alloca fundamentally conflicts with the execution scheme of StackThreads/MP. Please use above alternatives (malloc, SGC, or region-based allocator). Region-based allocator will be particularly useful when a single procedure calls alloca many times, as blocks allocated in a single procedure die together.
stgcc currently redefines alloca as the name of an undefined function, so that programs that use alloca fail to link. If you want to optimize allocation on thin ice, you can call the builtin alloca function (__builtin_alloca), as long as you know it is safe. Calling __builtin_alloca from a procedure is safe, as long as the procedure does not call any procedure compiled by stgcc. In other words, if you place all calls to __builtin_alloca to the procedure entry, you are safe.
We are planning to support alloca in future, although it will not allocate memory from stack but from heap. Like standard alloca, it automatically frees memory allocated by a procedure after the procedure exits. However, it will not be as efficient as __builtin_alloca; its overhead is likely to be similar to that of the region-based allocator.
パフォーマンスプロファイラ
すたっくすれっずはプログラムの実行後に各プロセッサの状態を見ることができる単純なパフォーマンスプロファイラを持っている。
リアルタイムプロファイラではないし、インタフェースは洗練されていないが、パフォーマンスボトルネックを探すのに非常に役に立つ。
これを使うためにはプログラムを -tp オプションで実行させ、logをxgraphフォーマットに変換し、xgraphでそれを見る。
プログラムをプロファイルする
最も便利なやり方は -tp オプションでプログラムを実行すること。例えば、
harp:367% ./fib -nw 10 -tp
pfib: 1091 ms on 10 processors, sfib: 2062 ms
これは00stprof.xx.yyという名前のたくさんのファイルをカレントディレクトリに生成する。
１０プロセッサを使用すると１０ファイルになる。
プログラムの特定のセクションをプロファイルしたいと思うかもしれない。
この場合には、st_begin_profile() 呼び出しをプロファイルを開始したい場所に、st_end_profile()をプロファイルを終了したい場所に追加しよう。
現在は、それらを１プログラムの実行で1度だけ呼び出すことができる。
プロファイルの細かさはデフォルトで１００マイクロ秒。
各プロセッサはどれくらいの時間を（ビジー、アイドル、など）の状態で過ごしているかと１００マイクロ秒ごとにその期間の支配的な状態を計算する。
ログファイルは各期間の状態を記録する。
コマンドラインオプション--time_profile_resolution Sでプロファイルの間隔を変えることができる。Sは期間をマイクロ秒で指定する。
より小さい数を指定すると結果をより高信頼なものにするが、空間を犠牲にする。
書くプロセッサは固定サイズのバッファをプロファイルの貯蓄のために保持し、バッファがオーバフローすると（プロファイルが終了すると）ファイルにセーブする。
大きなHeisenberg効果をプロファイルにもたらすかもしれない。
--time_profile_buffer_size N を指定することによって、インメモリバッファのサイズを増やせる。Nはインメモリバッファのエントリの数を支持する。
デフォルトは８１００。
一つのエントリは単一の状態の連続した期間を記述するので、Nは必ずしも２次ストレージにインメモリプロファイルをセーブすることなしに耐えることが可能な期間の数を表さない。
例えば、プロセッサは時間の大半ビジーであるなら、必要なストレージはかなり小さい。
プロファイルされた結果を見る
生成されたログファイルをxgraphフォーマットに変換するにはmkxgrpを使用しよう。
それは２つのパラメータを取る。
１つはファイルネームのプレフィックス（もし明示的に与えなければ00stprof）、ともう一つはプロセッサの数。
例えば、
harp:367% mkxgrp 00stprof 10 > data.xg
はdata.xgというxgraph用のファイルを生成する。00stprof.xx.yy data.xgはうまく作成されると消される。
MTCAMP のほーむぺーじ
Last modified: Thu Apr 20 21:04:20 JST 2000