マルチスレッド(2)

並列分散ソフトウェア

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

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

■捕捉

2004/01/20 19:40:05

Java から pthread_setconcurrency() を呼ぶためのクラスが次の場所にある。

~yshinjo/java/jni/NativeConcurrency/v9/

% cd ~yshinjo/java/jni/NativeConcurrency/v9 
% make run 
env LD_LIBRARY_PATH=. java NativeConcurrencyTest
NativeConcurrency.set( 3 ) returned 0
NativeConcurrency.get() returned 3
% cat NativeConcurrencyTest.java  
//
// NativeConcurrencyTest
// 2004/01/07 20:20:28

class NativeConcurrencyTest
{
    public static void main( String argv[] )
    {
        int res ;
        res = NativeConcurrency.set( 3 );
        System.out.println("NativeConcurrency.set( 3 ) returned "+res );
        res = NativeConcurrency.get();
        System.out.println("NativeConcurrency.get() returned "+res );
    }
}
% 

Java VM の JIT を止める(-Xint)と、うまく台数効果が測定できるかもしれない。

% java -Xint Filename 

Java レベルのスレッドと OS レベルのスレッドの対応関係を変更することも できる。Solaris 7 (sakura) で Java 1.4 を動かした場合、標準では、 Many-to-Many lwp based。次のように変更できる。Java 1.4 では、 他に次のものがつかえる。

-XX:-UseLWPSynchronization

Many-to-Many thread based

default

Many-to-Many lwp based

-XX:+UseBoundThreads

One-to-One via bound threads

(sakura/Solaris7では使用不可) export LD_LIBRARY_PATH=/usr/lib/lwp

One-to-One via Alternate Libthread*

sakura:~yshinjo/java/thread/SpinThreads/RunSpinThreads.java

■今日の重要な話

• マスタ・スレーブ
  • 単純なfork-joinよる実現
  • バリア同期
• 分割統治
• タスクバッグ(ワークパイル)

[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

[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

ＷＷＷ上に追補がある。

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

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

• Sync
  • Mutex
  • ReentrantLock (Recursive Lock)
  • ReadWriteLock
  • Semaphore
  • Barrier
• Channel (BoundedBuffer (循環バッファ))
• Executor (タスクバッグ(ワークパイル))
• Futures

■マスタ・スレーブ

◆基本

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-2003/2004-01-15/ex/ms_matrix-main.c
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/ms_matrix.c
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/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 )
	{
	    マスターの処理Ａ;/*必要なら*/
	    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)

wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/ms_relax.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/ms_relax-main.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/barrier.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/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 は、１回の仕事をするスレッド。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-2003/2004-01-15/ex/quicksort-main.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/quicksort.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/workpile.c
wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-15/ex/Makefile
make quicksort-main
./quicksort-main

■パイプライン

■性能

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

• 粒度
  • 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] ＜内容に関したサブジェクト＞

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

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

電子メールの本文の先頭に学籍番号と名前（漢字の名前がある人は、漢字で） を書きなさい。

内容は、文法的に正しい、日本語、または英語で書くこと。文章には、述語を 付ける。体言止めは、使ってはいけない。単にプログラムを含めるのではなく、 「以下に○○のプログラムを示す」と書く。実行結果を必ず付ける。

送られたレポートには、最初の締切り以降にまとめて確認応答(acknowledge) を返す。メッセージの紛失、クラッシュ等に対応するために、時間切れによる 再送などのリカバリは適宜やること。

送ったレポートは、講義が終るまで保存しなさい。

★全体に関する注意事項

マスタ・スレーブや タスクバッグ(ワークパイル) でプログラムを書くこと。 その場合、pthread_mutex_lock() も pthread_cond_wait() も出てこない。バ リア同期を使ってもよいが今日の課題では使わなくても可能である。

Java を使ってもよいが、台数効果はうまく図れないかもしれない。 捕捉 を試して欲しい。

★配列の総和

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

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

★行列の掛け算をタスクバッグで

★その他