6. マルチスレッド

6.1 マルチスレッドとは

マルチスレッドとは、複数のコアを持ったCPUで、 同時に複数のスレッドを実行して処理を分割し計算時間を短縮するものです。
1台のコンピュータに複数のCPUが搭載されていればさらにその個数だけ速くなります。

6.2 マルチスレッドプログラミング

スレッド関係の関数はWindowsとLinuxで異なります。
Windows(VC++)ではWindows独自の関数を呼び出し、 Linux(gcc)ではPOSIX(Portable Operating System Interface for UNIX)準拠の関数を呼び出します。

スレッドの起動と終了
VC++ではCreateThread関数、gccではpthread_create関数でスレッドを起動し、 VC++ではWaitForMultipleObjects関数、gccではpthread_join関数でスレッドの終了を待ちます。

スレッド関数の引数
スレッド関数の引数は"void *"の一つだけですので、 複数の変数を渡すには構造体を作ってその中に格納します。
構造体のメンバーの数が多いときはグローバル変数にした方が便利なこともあります。

6.3 マルチスレッドプログラミング例

リスト6-1にベクトルの内積をマルチスレッドで計算するプログラムを示します。


リスト6-1 マルチスレッドプログラム(sdot_thread.c)
     1	/*
     2	dot product (multi-thread)
     3	
     4	VC++ : cl /Ox sdot_thread.c
     5	gcc  : gcc -O3 -std=c99 sdot_thread.c -o sdot_thread -lpthread
     6	
     7	Usage :
     8	> sdot_thread <num> <loop> <thread>
     9	*/
    10	
    11	#include <stdlib.h>
    12	#include <stdio.h>
    13	#include <time.h>
    14	
    15	#ifdef _WIN32
    16	#include <windows.h>
    17	HANDLE *hthread;
    18	#else
    19	#include <pthread.h>
    20	#include <sys/time.h>
    21	pthread_t *hthread;
    22	#endif
    23	
    24	typedef struct {
    25		int    nthread;
    26		int    tid;
    27		int    n;
    28		const float *a;
    29		const float *b;
    30		float  s;
    31	} thread_arg_t;
    32	
    33	// block
    34	static void sdot_thread(void *arg)
    35	{
    36		thread_arg_t *targ = (thread_arg_t *)arg;
    37		int    nthread = targ->nthread;
    38		int    tid     = targ->tid;
    39		int    n       = targ->n;
    40		const float *a = targ->a;
    41		const float *b = targ->b;
    42	
    43		int block = (n + nthread - 1) / nthread;
    44		int i0 =  tid      * block;
    45		int i1 = (tid + 1) * block;
    46		if (i1 > n) i1 = n;
    47		float sum = 0;
    48		for (int i = i0; i < i1; i++) {
    49			sum += a[i] * b[i];
    50		}
    51	
    52		targ->s = sum;
    53	}
    54	/*
    55	// cyclic
    56	static void sdot_thread(void *arg)
    57	{
    58		thread_arg_t *targ = (thread_arg_t *)arg;
    59		int    nthread = targ->nthread;
    60		int    tid     = targ->tid;
    61		int    n       = targ->n;
    62		const float *a = targ->a;
    63		const float *b = targ->b;
    64	
    65		float sum = 0;
    66		for (int i = tid; i < n; i += nthread) {
    67			sum += a[i] * b[i];
    68		}
    69	
    70		targ->s = sum;
    71	}
    72	*/
    73	static float sdot(int nthread, int n, const float *a, const float *b)
    74	{
    75		// thread arguments
    76		thread_arg_t *targ = (thread_arg_t *)malloc(nthread * sizeof(thread_arg_t));
    77		for (int tid = 0; tid < nthread; tid++) {
    78			targ[tid].nthread = nthread;
    79			targ[tid].tid     = tid;
    80			targ[tid].n       = n;
    81			targ[tid].a       = a;
    82			targ[tid].b       = b;
    83		}
    84	
    85		// multi thread
    86		if (nthread > 1) {
    87	#ifdef _WIN32
    88			for (int tid = 0; tid < nthread; tid++) {
    89				hthread[tid] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)sdot_thread, (void *)&targ[tid], 0, NULL);
    90			}
    91			WaitForMultipleObjects(nthread, hthread, TRUE, INFINITE);
    92			for (int tid = 0; tid < nthread; tid++) {
    93				CloseHandle(hthread[tid]);
    94			}
    95	#else
    96			for (int tid = 0; tid < nthread; tid++) {
    97				pthread_create(&hthread[tid], NULL, (void *)sdot_thread, (void *)&targ[tid]);
    98			}
    99			for (int tid = 0; tid < nthread; tid++) {
   100				pthread_join(hthread[tid], NULL);
   101			}
   102	#endif
   103		}
   104		// single thread
   105		else {
   106			sdot_thread((void *)targ);
   107		}
   108	
   109		// sum
   110		float sum = 0;
   111		for (int tid = 0; tid < nthread; tid++) {
   112			sum += targ[tid].s;
   113		}
   114	
   115		return sum;
   116	}
   117	
   118	int main(int argc, char **argv)
   119	{
   120		int    nthread = 1;
   121		int    n = 1000;
   122		int    nloop = 1000;
   123	#ifdef _WIN32
   124		clock_t t0, t1;
   125	#else
   126		struct timeval t0, t1;
   127	#endif
   128	
   129		// arguments
   130		if (argc >= 4) {
   131			n = atoi(argv[1]);
   132			nloop = atoi(argv[2]);
   133			nthread = atoi(argv[3]);
   134		}
   135	
   136		// thread
   137	#ifdef _WIN32
   138		hthread = (HANDLE *)malloc(nthread * sizeof(HANDLE));
   139	#else
   140		hthread = (pthread_t *)malloc(nthread * sizeof(pthread_t));
   141	#endif
   142	
   143		// alloc
   144		size_t size = n * sizeof(float);
   145		float *a = (float *)malloc(size);
   146		float *b = (float *)malloc(size);
   147	
   148		// setup problem
   149		for (int i = 0; i < n; i++) {
   150			a[i] = i + 1.0f;
   151			b[i] = i + 1.0f;
   152		}
   153	
   154		// timer
   155	#ifdef _WIN32
   156		t0 = clock();
   157	#else
   158		gettimeofday(&t0, NULL);
   159	#endif
   160	
   161		// calculation
   162		float sum = 0;
   163		for (int loop = 0; loop < nloop; loop++) {
   164			sum += sdot(nthread, n, a, b);
   165		}
   166	
   167		// timer
   168		double cpu = 0;
   169	#ifdef _WIN32
   170		t1 = clock();
   171		cpu = (double)(t1 - t0) / CLOCKS_PER_SEC;
   172	#else
   173		gettimeofday(&t1, NULL);
   174		cpu = (t1.tv_sec - t0.tv_sec) + 1e-6 * (t1.tv_usec - t0.tv_usec);
   175	#endif
   176	
   177		// output
   178		double exact = (double)nloop * n * (n + 1) * (2 * n + 1) / 6.0;
   179		printf("n=%d, nloop=%d, dot=%.6e(%.6e), cpu[sec]=%.3f\n",
   180			n, nloop, sum, exact, cpu);
   181	
   182		// free
   183		free(hthread);
   184		free(a);
   185		free(b);
   186	
   187		return 0;
   188	}

並列計算のアルゴリズム
ベクトルの内積を複数のスレッドで並列計算するには、 スレッド間で変数へのアクセスが重複することがありませんので、 単純にループを分割するだけで済みます。 最後に各スレッドの部分和を加えると全体の和になります。

ループ分割
ループ分割法には図6-1の二通りがあります。
リスト6-1には両方の方法が実装されています。


図6-1 ループ分割法(ループの長さ=10、スレッド数=3のとき)

下記がblock分割の定型文です。 ここで、第1行はブロックの大きさを計算するもので、 nがnthreadの倍数のときはn/nthreadになり、それ以外の時は1が加わります。 ここでnはループの長さ、nthreadはスレッド数、tidはスレッド番号(=0,1,...,nthread-1)です。

	int block = (n + nthread - 1) / nthread;
	int i0 =  tid      * block;
	int i1 = (tid + 1) * block;
	if (i1 > n) i1 = n;
	for (int i = i0; i < i1; i++) {
下記がcyclic分割の定型文です。
	for (int i = tid; i < n; i += nthread) {

OSによる違い
OSによる違いは以下のように記述します。

#ifdef _WIN32
	(Windows用コード)
#else
	(Linux用コード)
#endif

計算時間の計測
gccではclock関数は全スレッドの和になりますので、 リスト6-1では計算時間を計測するためにgettimeofday関数を使用しています。
なお、47,65行目では和をとる変数をfloatとしていますが精度上はdoubleが望ましいです。 計算時間もほとんど変わりません。

コンパイル・リンク方法
VC++ではコンパイル・リンクオプションは特に必要ありません。
> cl /Ox sdot_thread.c
gccではリンクオプション"-lpthread"が必要です。
> gcc -O3 -std=c99 sdot_thread.c -o sdot_thread -lpthread

プログラムの実行方法
プログラムの実行方法は以下の通りです。
> sdot_thread 配列の大きさ 繰り返し回数 スレッド数
例えば以下のようになります。
> sdot_thread 1000000 1000 4
繰り返し回数は計算時間の測定誤差を小さくするためです。

6.4 マルチスレッドの計算時間

表6-1に計算時間を示します。
配列の大きさ(=N)と繰り返し回数(=L)の積は一定(=10^10)です。従って全体の演算量は同じです。
表の下になるほど使用メモリーが小さくなりキャッシュに乗りやすくなります。
1スレッドではNo.1-4で計算時間はほぼ一定です。
4スレッドではNo.2ではある程度の高速化が得られていますが、 No.3-4ではスレッド起動回数(=L)が多いために逆に計算時間が増えています。 スレッド起動にかかるコストはOpenMPより大きく、 WindowsはLinuxより大きいことがわかります。
マルチスレッドプログラミングではスレッドの起動にコストがかかることに注意が必要です。
また、ループ分割については本ケースではblock型がcyclic型より速いですが、 どちらがよいかはアルゴリズムやデータの大きさによりますので、 両方実装して比較することが望ましいです。

表6-1 マルチスレッドの計算時間(()内は1スレッドとの速度比)
No.配列の大きさN繰り返し回数LWindowsLinux
1スレッド4スレッド
(block型)
4スレッド
(cyclic型)
1スレッド4スレッド
(block型)
4スレッド
(cyclic型)
110,000,0001,0008.62秒(1.0)5.94秒(1.45)6.53秒(1.32)10.49秒(1.0)7.25秒(1.45)7.32秒(1.43)
21,000,00010,0007.92秒(1.0)3.02秒(2.62)4.84秒(1.64)9.92秒(1.0)5.31秒(1.87)6.76秒(1.47)
3100,000100,0007.60秒(1.0)10.98秒(0.69)10.85秒(0.70)8.96秒(1.0)4.77秒(1.88)5.62秒(1.60)
410,0001,000,0007.78秒(1.0)178.16秒(0.04)147.90秒(0.05)8.94秒(1.0)21.06秒(0.42)21.38秒(0.42)