マルチスレッド(2)

並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/2002-01-24
あるいは、次のページから手繰っていくこともできます。
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

■今日の重要な話

教科書

[1] Steve Kleiman, Devang Shah and Bart Smaalders: "Programming with Threads", Sun Microsystems Press, 1996. ISBN 0-13-172389-8
[2] Steve Kleiman, Devang Shah,Bart Smaalders著、岩本伸一訳: "実践マルチス レッドプログラミング",アスキー出版局, 1998年. ISBN 4-7561-1784-8

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

[3] Doug Lea: "Concurrent Programming in Java: Design Principles and Patterns, Second edition", Addison-Wesley, November 1999. (ISBN 0-201-31009-0).
[4] ダグ リー (著), Doug Lea (原著), 松野良蔵 (翻訳): " "Javaスレッド プログラミング―並列オブジェクト指向プログラミングの設計原理",翔泳社 (2000). ISBN: 4881359185

WWW上に追補がある。

http://gee.cs.oswego.edu/dl/cpj/

util.concurrent パッケージには、実用になるクラスが多数含まれている。

■Quizに関する追加レポート

10点満点の5点以下(5点を含む)の人は、間違えた部分についてレポートを提出 しなさい。

■フィードバック

前回の課題[pdsoft/report-thread-1] に対するコメント。

◆化学反応

H や O をスレッドとして実現していれば、合格とする。次のようなものは、 再提出すること。
H_func()
{
    int i ;
    for( i=0 ; i<10; i++ )
    {
       H_Ready();
    }
}
H が 2 個固定、O が 1 個固定のものは、合格とする。複数個扱えるように修 正して再提出してもよい。新たな課題に挑戦してもよい。

スピンしているものは、一応、合格とする。相手が揃うまで wait() するよう に書き換えて再提出してもよい。 スピンとは、wait() しないで、ひたすら条件が整うのを待つものである。 sleep() を入れても、だめである。

単に H と O のスレッドを作っていて、中で wait していなものは不可とする。 再提出すること。

◆狭い端

スピンしているものは、一応、合格とする。条件が揃うまで wait() するよう に書き換えて再提出してもよい。

◆セマフォ

sem_getvalue() して goto loop は、再提出とする。

複数スレッドによる put/get に対応していないものは、合格とする。 再提出しなくてもよい。

■マスタ・スレーブ

◆基本


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-2001/examples/ms_matrix-main.c
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/ms_matrix.c
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/Makefile
% make ms_matrix-main
gcc -D_REENTRANT ms_matrix-main.o -lpthread -lposix4 -o ms_matrix-main
% ./ms_matrix-main 200 1 1
matrix_size==200, nthreads==1, niters==1, concurrenc==1
 1.381 [sec] / 1 [iteration] ==  1.381 [sec/iteration]
1 [iteration] /  1.381 [sec] ==  0.724 [iteration/sec]
% ./ms_matrix-main 200 1 1
matrix_size==200, nthreads==1, niters==1, concurrenc==1
 1.391 [sec] / 1 [iteration] ==  1.391 [sec/iteration]
1 [iteration] /  1.391 [sec] ==  0.719 [iteration/sec]
% ./ms_matrix-main 200 2 1
matrix_size==200, nthreads==2, niters==1, concurrenc==2
 0.694 [sec] / 1 [iteration] ==  0.694 [sec/iteration]
1 [iteration] /  0.694 [sec] ==  1.441 [iteration/sec]
% ./ms_matrix-main 200 3 1
matrix_size==200, nthreads==3, niters==1, concurrenc==3
 0.494 [sec] / 1 [iteration] ==  0.494 [sec/iteration]
1 [iteration] /  0.494 [sec] ==  2.025 [iteration/sec]
% ./ms_matrix-main 200 4 1
matrix_size==200, nthreads==4, niters==1, concurrenc==6
 0.382 [sec] / 1 [iteration] ==  0.382 [sec/iteration]
1 [iteration] /  0.382 [sec] ==  2.621 [iteration/sec]
% ./ms_matrix-main 200 5 1
matrix_size==200, nthreads==5, niters==1, concurrenc==6
 0.333 [sec] / 1 [iteration] ==  0.333 [sec/iteration]
1 [iteration] /  0.333 [sec] ==  3.005 [iteration/sec]
% ./ms_matrix-main 200 6 1
matrix_size==200, nthreads==6, niters==1, concurrenc==6
 0.279 [sec] / 1 [iteration] ==  0.279 [sec/iteration]
1 [iteration] /  0.279 [sec] ==  3.587 [iteration/sec]
% 
台数効果をうまく図る方法

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


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

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

ループの間、マスタの仕事がないこともある。その場合は、マスタはバリアに は参加しない(relax.c参照)。

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

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

■タスクバッグ(ワークパイル)

◆基本


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 は、1回の仕事をするスレッド。n_threads は、スレッドの数。
void work_put(workpile_t wp, void *ptr)
仕事をワークパイルに加える。
void work_wait(workpile_t wp)
仕事がなくなるのを待つ。

◆並列クイックソート

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

■パイプライン

もともとのプログラムが専門家並列ならよい。 スレッドにはあまり適していない。

■性能

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

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

◆gprofコマンド

アルゴリズムが時間を消費している所を知るための道具。

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

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

◆spinロック

ロックの種類
sleeping (標準)
ロックが確保できない時、そのスレッドをキューに入れ、ブロック状態 にする。ロックを保持しているスレッドが、ロックを解放する時に起してもら う。
spin
ロックが確保できるまで、同期変数を繰り返し調べる。
スレッドをブロックさせたり起したりする操作は、重たい。 際どい領域が小さいなら、スピンした方が得。

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

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

■課題

次の課題から1つを選んで提出しなさい。問題を難しい方に変えてもよい。締 め切りは、2002/01/31 (水曜日) 18:00 とする。(23:59:59 ではない)。

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

----------------------------------------------------------------------
To: yas@is.tsukuba.ac.jp
Subject: [pdsoft/report-thread-2] phrase in English

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

<本文>
----------------------------------------------------------------------
可能ならば、Subject: は、英語で、かつ、MIME エンコードしないで欲しい。 前回の注意事項も参照のこと。

★再提出

前回の課題で、問題の解釈が間違っていた人は、もう一度前回の課題をやり直 す。問題の解釈は合っていたが、未完成だった場合(スピンしてるもの、スレッ ドと原子が対応していない、等)も、もう一度前回の課題をやってもよい。

★配列の総和

配列が与えられた時に、次のような値を計算する並列プログラムを記述しなさ い。 注意:並列化しにくいものも混じっている。全部はやらなくてもよい。

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

行列の掛け算をするプログラムを、分割統治法で書き直しなさい。部分行列に 分割して、掛け算して足す。配列の要素の並びに注意する。

★その他

自分が持っている逐次プログラム、または、クラスタ計算用の並列プログラム を、Pthreads を使って並列処理をするプログラムに書き換えなさい。そして、 プロセッサ数を変えながら実行して、台数効果を調べなさい。
↑[もどる] ←[1月17日] ・[1月24日] →[1月31日]
Last updated: 2002/01/31 03:15:48
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>