マルチスレッド(2)

 並行分散ソフトウェア/並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/pdsoft-2005/2005-12-16
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/

■捕捉

J2SE 5.0 で、java.util.concurrent.locks パッケージにPthread mutex/条件 変数相当の機能が追加された。 http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/Condition.html (English)http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/concurrent/locks/Condition.html (日本語)
 class BoundedBuffer {
   final Lock lock = new ReentrantLock();
   final Condition notFull  = lock.newCondition(); 
   final Condition notEmpty = lock.newCondition(); 

   final Object[] items = new Object[100];
   int putptr, takeptr, count;

   public void put(Object x) throws InterruptedException {
     lock.lock();
     try {
       while (count == items.length) 
         notFull.await();
       items[putptr] = x; 
       if (++putptr == items.length) putptr = 0;
       ++count;
       notEmpty.signal();
     } finally {
       lock.unlock();
     }
   }

   public Object take() throws InterruptedException {
     lock.lock();
     try {
       while (count == 0) 
         notEmpty.await();
       Object x = items[takeptr]; 
       if (++takeptr == items.length) takeptr = 0;
       --count;
       notFull.signal();
       return x;
     } finally {
       lock.unlock();
     }
   } 
 }
類似の機能は、ArrayBlockingQueue 等のクラスで提供されているので、自分 で作る必要はない。

■今日の重要な話

教科書

[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

WWW上に追補がある。

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

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

J2SE 5.0 の java.util.concurrent では、さまざまな並行プログラミングの クラスが標準化された。

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html (English) http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/concurrent/package-summary.html (日本語)

■マスタ・スレーブ

◆基本

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() */
}

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

SMP (4 CPU, SPARC, Solaris) での実行例。
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_matrix-main.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_matrix.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile [←]
% emacs Makefile (CFLAGSの調整) [←]
% make ms_matrix-main [←]
gcc -D_REENTRANT ms_matrix-main.o -lpthread -lposix4 -o ms_matrix-main
% ./ms_matrix-main 400 1 1 [←]
matrix_size==400, nthreads==1, niters==1, concurrency==1
 1.846 [sec] / 1 [iteration] ==  1.846 [sec/iteration]
1 [iteration] /  1.846 [sec] ==  0.542 [iteration/sec]
% ./ms_matrix-main 400 1 1 [←]
matrix_size==400, nthreads==1, niters==1, concurrency==1
 1.842 [sec] / 1 [iteration] ==  1.842 [sec/iteration]
1 [iteration] /  1.842 [sec] ==  0.543 [iteration/sec]
% ./ms_matrix-main 400 2 1 [←]
matrix_size==400, nthreads==2, niters==1, concurrency==2
 0.924 [sec] / 1 [iteration] ==  0.924 [sec/iteration]
1 [iteration] /  0.924 [sec] ==  1.082 [iteration/sec]
% ./ms_matrix-main 400 3 1 [←]
matrix_size==400, nthreads==3, niters==1, concurrency==3
 0.657 [sec] / 1 [iteration] ==  0.657 [sec/iteration]
1 [iteration] /  0.657 [sec] ==  1.523 [iteration/sec]
% ./ms_matrix-main 400 4 1 [←]
matrix_size==400, nthreads==4, niters==1, concurrency==4
 0.467 [sec] / 1 [iteration] ==  0.467 [sec/iteration]
1 [iteration] /  0.467 [sec] ==  2.144 [iteration/sec]
% ./ms_matrix-main 400 5 1 [←]
matrix_size==400, nthreads==5, niters==1, concurrency==5
 0.728 [sec] / 1 [iteration] ==  0.728 [sec/iteration]
1 [iteration] /  0.728 [sec] ==  1.374 [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.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_relax.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_relax-main.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/barrier.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile [←]
% emacs Makefile (CFLAGSの調整) [←]
% make ms_relax-main.c [←]
% ./ms_relax-main 50 1 1 [←]
matrix_size==50, nthreads==1, niters==1, concurrency==1
 1.575 [sec] / 1 [iteration] ==  1.575 [sec/iteration]
1 [iteration] /  1.575 [sec] ==  0.635 [iteration/sec]
% ./ms_relax-main 50 1 1 [←]
matrix_size==50, nthreads==1, niters==1, concurrency==1
 1.572 [sec] / 1 [iteration] ==  1.572 [sec/iteration]
1 [iteration] /  1.572 [sec] ==  0.636 [iteration/sec]
% ./ms_relax-main 50 2 1 [←]
matrix_size==50, nthreads==2, niters==1, concurrency==2
 0.857 [sec] / 1 [iteration] ==  0.857 [sec/iteration]
1 [iteration] /  0.857 [sec] ==  1.167 [iteration/sec]
% ./ms_relax-main 50 3 1 [←]
matrix_size==50, nthreads==3, niters==1, concurrency==3
 0.646 [sec] / 1 [iteration] ==  0.646 [sec/iteration]
1 [iteration] /  0.646 [sec] ==  1.547 [iteration/sec]
% ./ms_relax-main 50 4 1 [←]
matrix_size==50, nthreads==4, niters==1, concurrency==4
 0.938 [sec] / 1 [iteration] ==  0.938 [sec/iteration]
1 [iteration] /  0.938 [sec] ==  1.066 [iteration/sec]
% uptime [←]
  1:06am  up 116 day(s), 14:35,  7 users,  load average: 1.33, 1.14, 1.10
% []

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

◆基本

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.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/quicksort-main.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/quicksort.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/workpile.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile [←]
% emacs Makefile (CFLAGSの調整) [←]
% make quicksort-main [←]
% ./quicksort-main 1000000 1 [←]
size==1000000, nthreads==1, concurrency==1
execution time:  0.766 [sec]
    throughput:  1.305 [/sec]
% ./quicksort-main 1000000 1 [←]
size==1000000, nthreads==1, concurrency==1
execution time:  0.761 [sec]
    throughput:  1.315 [/sec]
% ./quicksort-main 1000000 2 [←]
size==1000000, nthreads==2, concurrency==2
execution time:  0.439 [sec]
    throughput:  2.280 [/sec]
% ./quicksort-main 1000000 3 [←]
size==1000000, nthreads==3, concurrency==3
execution time:  0.334 [sec]
    throughput:  2.993 [/sec]
% ./quicksort-main 1000000 4 [←]
size==1000000, nthreads==4, concurrency==4
execution time:  0.318 [sec]
    throughput:  3.145 [/sec]
% ./quicksort-main 1000000 5 [←]
size==1000000, nthreads==5, concurrency==5
execution time:  0.276 [sec]
    throughput:  3.621 [/sec]
% []

■性能

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

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

◆gprofコマンド

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

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

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

◆spinロック

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

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

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

■練習問題

★練習問題(11) 配列の総和

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

プログラミング言語としては、C言語、または、Java を用いなさい。

★練習問題(12) 行列の掛け算を分割統治で

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

プログラミング言語としては、C言語、または、Java を用いなさい。

★練習問題(13) 行列の掛け算をタスクバッグで

行列の掛け算をするプログラムを、タスクバッグ(ワークパイル)を使った手 法で書き直しなさい。ワーカは、CPU の数だけ作る。タスクは、CPU の数より も多くてもよい。

プログラミング言語としては、C言語、または、Java を用いなさい。

★練習問題(14) 逐次プロラムの並列化

自分が持っている逐次プログラムを、Pthreads、または、Java を使って並列 処理をするプログラムに書き換えなさい。

プログラミング言語としては、C言語、または、Java を用いなさい。

★練習問題(15) J2SE 5.0 の Lock と Condition の利用

Pthread の mutex と条件変数、または、 Java の synchronized と wait() を使って記述されたプログラムを、 J2SE 5.0 の java.util.concurrent.locks.ReentrantLock と java.util.concurrent.locks.Condition を使って書き直しなさい。 または、 EDU.oswego.cs.dl.util.concurrent パッケージのクラスの ReentrantLock や CondVar を使って書き直しなさい。
↑[もどる] ←[12月9日] ・[12月16日] →[12月22日]
Last updated: 2005/12/16 03:07:36
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>