マルチスレッド(2)

並列分散ソフトウェア

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/2001-01-25
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/
http://www.is.tsukuba.ac.jp/~yas/index-j.html
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■訂正

SunOS 5.6 (sakura) でセマフォを使う時には、-lrt ではなくて、 -lposix4 をつける。

SunOS 5.6 (sakura) には、pthread_setconcurrency()、 pthread_getconcurrency() は使えない。 代りに thr_setconcurrency()、 thr_getconcurrency()を使う。使い方は、まったく同じである。 もともと Sun 独自の機能であったものが、標準に採り入れられた。SunOS 5.6 でpthread_setconcurrency()、 pthread_getconcurrency()を含むソースをコンパイルする時には、 Ｃコンパイラのコマンドラインで次のようなマクロを定義するとよい。

	-Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency

#define	pthread_setconcurrency	thr_setconcurrency
#define	pthread_getconcurrency	thr_getconcurrency

■マスタ・スレーブ

◆基本

master()
{
	初期化;
	for( i=0 ; i<nthreads; i++ )
	{
	    pthread_create(,,slave,);
	}
	マスターの処理;/*必要なら*/
	for( i=0 ; i<nthreads; i++ )
	{
	    pthread_join(,,slave,);
	}
	終了処理;/*必要なら*/
}

slave(void *params)
{
	paramsからiを取り出す;
	仕事をする;
	結果を大域変数かparamsに返す;
	return; /* pthread_exit() */
}

◆マスタ・スレーブの例:行列の掛け算

wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/ms_matrix-main.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/ms_matrix.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/Makefile
make ms_matrix-main
./ms_matrix-main 1 1
./ms_matrix-main 2 1
./ms_matrix-main 3 1
./ms_matrix-main 4 1
./ms_matrix-main 5 1
./ms_matrix-main 6 1

サンプルがWWWページにある。 http://www.sun.com/books/catalog/kleiman/

邦訳: Steve Kleiman, Devang Shah,Bart Smaalders著、岩本伸一訳: "実践マルチス レッドプログラミング",アスキー出版局, 1998年. ISBN 4-7561-1784-8

◆マスタ・スレーブ(バリア付き)

master()
{
	初期化;
	for( i=0 ; i<nthreads; i++ )
	{
	    pthread_create(,,slave,);
	}
	while( !termcond )
	{
	    マスターの処理Ａ;/*必要なら*/
	    barrier_wait();
	    マスターの処理Ｂ;/*必要なら*/
	    barrier_wait();
	}
	for( i=0 ; i<nthreads; i++ )
	{
	    pthread_join(,,slave,);
	}
	終了処理;/*必要なら*/
}

slave(void *params)
{
	paramsからiを取り出す;
	while( !termcond )
	{
	    /* マスターの処理Ａの完了を待つ */
	    barrier_wait();
	    スレーブ処理Ｂ;
	    結果を大域変数かparamsに返す;
	    barrier_wait();
	}
	return; /* pthread_exit() */
}

◆バリア同期の例:弛緩法(relax.c)

http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/ms_relax.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/ms_relax-main.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/barrier.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/Makefile

■ワークパイル

◆基本

worker_thraed()
{
	while( (ptr=work_get(workpile))!=NULL )
	{
	    ptrが示す仕事をする;
	    if( 新しい仕事ができた )
	    {
		work_put(workpile,新しい仕事);
	    }
	}
}

◆応用

• 並列化ループ。繰り返しごとに計算量が変化する時にマスタスレーブより有利。
• レイトレーシング
• イメージのレンダリング
• 最短経路探索
• ゲーム
• 分割統治

◆ワークパイルコントローラ

workpile_t work_init(int max_pile, work_proc_t worker_proc, int n_threads)

初期化する。max_pile は、蓄える仕事の数の最大。worker_proc は、１回の仕事をするスレッド。n_threads は、スレッドの数。

void work_put(workpile_t wp, void *ptr)

仕事をワークパイルに加える。

void work_wait(workpile_t wp)

仕事がなくなるのを待つ。

◆並列クイックソート

http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/quicksort-main.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/quicksort.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/workpile.c
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/Makefile

■パイプライン

■性能

◆よい性能をえるために重要なこと

• 粒度
  • CPUの数より仕事は多くする。
  • スレッドを作りすぎない。
  • １つの仕事のばらつきに適応する。
  • 同期オーバヘッドを考慮する。
• ロック競合。場合によってはスピンする。
• データ共有、キャッシュを意識したメモリの利用。
• 計算の複雑さ

◆並列プログラムを書くためのガイドライン

• コンパイラが使えるならつかう。Pthread を使うコードを出すコンパイラが利用可能な場合もある。
• 正しいプログラムを作成する。特に同期。スレッドを小さなモジュールに押し込める。
• 最適化を後にする。
• アルゴリズムが時間を消費している所を知る
• デバッグを考える。１スレッドでも動くプログラムを書く。なるべく非決定性を避ける。

◆gprofコマンド

コンパイル時: -pg オプションを付ける。

実行すると gmon.out というファイルが作られる。 これを、実行形式ファイルと共に gprof コマンドに渡す。

◆spinロック

sleeping (標準)

ロックが確保できない時、そのスレッドをキューに入れ、ブロック状態 にする。ロックを保持しているスレッドが、ロックを解放する時に起してもら う。

spin

ロックが確保できるまで、同期変数を繰り返し調べる。

ロックを確保したスレッドが、CPU を横取りされていたなら待っているのは無 駄になる。

無限のスピンは避けたい。 コンテキスト切り替えに要する時間の 50%-100% だけスピンするのがよい。 [Anderson 90]

■課題

レポートは、次のような形式の電子メールで送ること。

----------------------------------------------------------------------
To: yas@is.tsukuba.ac.jp
Subject: [pdsoft/report-thread-2] ＜内容に関したサブジェクト＞

学籍番号 000000 (各自の学籍番号で置き換える)
名前 漢字の名前

＜本文＞
----------------------------------------------------------------------

＜内容＞

★配列の総和

• 総和、平均値、分散、標準偏差
• 最大値、最小値
• 中央値
• 最頻値

★行列の掛け算を分割統治で

★その他