C言語のpthreadについて

Question

C言語においてpthreadを用いてクイックソートの高速化を勉強中なのですが、疑問点があるのでどうかご教授お願いします。

高速化するためにいろいろとスレッドを作る場所や、*func_thread()で行う処理などを考えました。初めは再帰関数が呼び出されているところでスレッドを作れば高速化できると考えていました。しかし、結局以下のように最初のquick_sort_pthread()の呼び出しのところでスレッドを作ったら高速化できました。どうして下のようなコードで逐次処理に比べ高速化したのかがわかりません。別のスレッドでただquick_sort_pthread()を動かしているだけに見えます。なぜ高速化したのか、これが最善の高速化なのかが分からなくてもやもやしてます。絶対にこれより良いpthreadを用いた高速化ができると思うのですが。

どうかご教授お願いします。

#include <stdio.h>
#include<stdlib.h>
#include <unistd.h>
#include <omp.h>
#include<time.h>
#include<sys/time.h>
#include<pthread.h>
int partition(int[],int,int);
void *func_thread(void *p);
void quick_sort_pthread(int[],int,int);

int *array = NULL;
const int data_num = 100000;
int left;
int right;
int pivot;

void *func_thread(void *p){
    if (left < right) {
    pivot = partition(array, left, right);
    quick_sort_pthread(array, left, pivot-1);
    quick_sort_pthread(array, pivot+1, right);
  }
}


void quick_sort_pthread(int array[], int left, int right) {
  int pivot;
  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort_pthread(array, left, pivot-1);
    quick_sort_pthread(array, pivot+1, right);
  }
}


int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;
  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);  

  return j;
}


void Shuffle(int *array, int n)
{
	int i,j,t;
	
	srand(1);
	for (i = 0; i < n; i++) {
		j = rand() % n;
		t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
}


int main (void) {
	int i;
	struct timeval time_start, time_end,start,end;
    pthread_t pthread1;
    pthread_t pthread2;
    int thread_id1=1;
    int thread_id2=2;
	
	array= (int *)malloc(sizeof(int)*data_num);
	for(i=0; i<data_num; i++){
		array[i]=i;
	}
	Shuffle(array, data_num);//配列をシャッフル

	gettimeofday(&time_start, NULL);
  
	
    pthread_create( &pthread1, NULL, &func_thread, &thread_id1);
	pthread_create( &pthread2, NULL, &func_thread, &thread_id2);
    quick_sort_pthread(array,0,data_num);
    pthread_join(pthread1, NULL);
	pthread_join(pthread2, NULL);
	gettimeofday(&time_end, NULL);


	printf("Serialtime = %.3lf ms\n", ((time_end.tv_sec - time_start.tv_sec) + (time_end.tv_usec - time_start.tv_usec)*1.0E-6)*1000);
	
	return 0;
}

Comments

[y_waiwai]

なにがどういうふうに高速化したという話でしょうか。
具体的なデータが提示されないでは答えようもありません

[angel_p_57]

指摘にある、pthread_create で作り出したスレッドが実質何もしない、というのもありますが、そもそも partition() がバグってるので正しく動く保証がないです。( i++ や j-- にストッパーがないので配列外まで行く可能性がある )
まずは正しく動くコードかどうかを確かめてからです。

[Tinasp]

10万個のランダムな値が入っている配列をソートするプログラムなのですが、逐次処理の場合は平均17.144ms、上のコードの場合は12.965msという結果になりました。

Answer 1

quick_sort_pthread()の呼び出しのところでスレッドを作ったら高速化できました。

高速化できた、というのは何かの間違いではないでしょうか。
main()で作っている2つのスレッドは、何もしないで一瞬で終了しているはずです。(グローバルのleftとrightが0のまま変更されないため)

Answer 2

マルチコア

現代のコンピュータは演算コアを複数持っている場合がそれなりにあります。 これを効果的に活用するには演算を分割して各コアで実行させる必要があり、それがマルチスレッドで性能が上がる理由です。

ハイパースレッディング

一部の製品はハイパースレッディングというひとつのコアを疑似的に二つに見せかける技術を使っています。 無いよりは有ったほうがマルチスレッドの性能はかなり高くなりますが、そうは言っても疑似的なものなので二つのコアよりは低い性能です。

時分割マルチスレッド

スレッドの割り当ては OS が管理しており、ごく短い時間で複数のスレッドを切り替えながら実行することでたくさんのスレッドをひとつのコアで実行できるようになっています。

OS を起動しただけでも数千単位のスレッドが走っている状態になるのが普通ですが、実際には何かのイベントが起きるまで待機状態にあるだけなので演算性能を (それほど) 圧迫することはありません。

スレッドとコアの割り当て

上述の理由により、スレッドをたくさん作ることは出来ますが、あまりたくさん作ってもひとつのコア上で複数のスレッドが走っている状況では全体の演算性能は上がりません。 コアの数よりたくさんスレッドを作る意味はあまりないどころかスレッド切り替えのコストのために性能が下がる可能性が高いです。

スレッド生成コスト

プログラムを書くときに気を付けなければならないのは、スレッドの生成・解体のコストがかなり大きいということです。 頻繁にスレッドを作ったり解体するのは性能の足を引っ張ることになります。

スレッドプール

よく使われる一般的なテクニックが「スレッドプール」です。 事前に一定数のスレッドを生成して、そこに処理すべきデータを「割り当て (アタッチ)」することでスレッドの数を効果的な一定数に保ちながら、スレッドの生成・解体コストも抑えることができます。

ただし、処理の割り当てを管理するのが煩雑になりますし、割り当て管理の演算で演算コストが増えるようでもそれはそれで全体の演算性能の足を引っ張るわけです。

質問者のコード

質問者の提示しているコードでは、もし再帰のたびにスレッドを生成するのだとスレッドの数が爆発的に増えます。 先述のように、コアの数を超えるスレッドは高速化に寄与しません。 スレッド生成のコストが並列演算の恩恵を大幅に超えてしまいます。

スレッドを二個に限るという割り切りで (シングルスレッドよりは) 性能を出しつつ、マルチスレッドの問題を踏まないような構成に結果的になっているのでそれなりに良い性能が出たのでしょう。

Comments

[Tinasp]

回答ありがとうございます。回答者様のヒントを元に調べたところ、スレッドを用いた高速化の具体的な方法が見えてきました。