1

私は今、同時実行のクラスを受講していて、最初の (ばかばかしいほど単純な) プロジェクトを完成させました。

私のコードでは、2 番目の配列の値ごとに、配列を介してバイナリ検索を行っています。2 番目の配列の値ごとに、スレッドを生成しています。これはシーケンシャル ソリューションよりも遅いことが判明したため、少数のスレッドを生成し、実行が完了するたびに新しいキーを渡すことを考えました。

いくつか問題があります。1 つ目は、キーがなくなったときにスレッドを終了させるにはどうすればよいかということです。

新しいキーを渡すにはどうすればよいですか?

新しいキーを待っている間、スレッドが古いキーで実行されないようにするにはどうすればよいですか (条件付き待機について読んでいて、それが必要だと思います)。

これが私の現在の(効果のない)解決策です。

#define ARRAYSIZE 50000
#define KEY_NOT_FOUND -1
#define KEY_FOUND 0

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h> 

int binary_search(int *array, int key, int min, int max); 
void *worker(void *arg);

int count = 0;
pthread_mutex_t L;
int l_array[ARRAYSIZE * 2];

int main(void)
{
    int r_array[ARRAYSIZE]; 
    int *p;
    pthread_t *threads;
    int ix = 0;
    int jx = 0;

    struct timeval start, stop;
    double elapsed;

    for(ix = 0; ix < ARRAYSIZE; ix++)
    {
        r_array[ix] = ix;
    }
    for(ix = 0; ix < ARRAYSIZE * 2; ix++)
    {
        l_array[ix] = ix + 2;
    }

    gettimeofday(&start, NULL);

    threads = (pthread_t *) malloc(ARRAYSIZE * sizeof(pthread_t));

    for (jx = 0; jx < ARRAYSIZE; jx++) {
         p = (int *) malloc(sizeof(int));  
        *p = r_array[jx];
        pthread_create(&threads[jx], NULL, worker, (void *)(p));
    }

    for (jx = 0; jx < ARRAYSIZE; jx++) {
        pthread_join(threads[jx], NULL);
    }

    fprintf(stderr, "%d\n", count);

    gettimeofday(&stop, NULL);
    elapsed = ((stop.tv_sec - start.tv_sec) * 1000000+(stop.tv_usec-start.tv_usec))/1000000.0;
    printf("time taken is %f seconds\n", elapsed);
    return 0;
}

void* worker(void *arg)
{
    int boolean = 0;
    int key = *((int *) arg);
    boolean = binary_search(l_array, key, 0, ARRAYSIZE * 2);
    if(boolean == 1)
    {
        pthread_mutex_lock(&L);
        count++;
        pthread_mutex_unlock(&L);
    } 
}

int binary_search(int *array, int key, int min, int max)
{
   int mid = 0;
    if (max < min) return 0;
    else
    {
      mid = (min + max) / 2;
      if (array[mid] > key) return binary_search(array, key, min, mid - 1);
      else if (array[mid] < key) return binary_search(array, key, mid + 1, max);
      else 
        {
        return 1;
        }
    }
}
4

2 に答える 2

2

注:以下のコードはテストされていませんが、簡単です...

  • のベースアドレスr_array[]をワーカーに渡します
  • グローバルを維持するnext_index
  • 別の定義pthread_mutex

PS:スレッド数と同様に、2から始めて、スループットに違いがなくなるまで進めます。すべてのオーバーヘッドも考慮する必要があります。

void worker(void *arg)
{
    int* r_arrPtr = (int*) arg;
    int boolean = 0;
    int key =0;[

    while (1) {
        pthread_mutex_lock(&pNextIndex_MutEx);
        if (next_index < ARRAYSIZE) {
            key = r_arrPtr[next_index];
            next_index ++;
        } else {
            pthread_mutex_unlock(&pNextIndex_MutEx);
            return;
        }
        pthread_mutex_unlock(&pNextIndex_MutEx);

        boolean = binary_search(l_array, key, 0, ARRAYSIZE * 2);
        if (boolean == 1) {
            // ....
        }
    }
}
于 2012-10-30T19:57:55.370 に答える
1

コアごとに 1 つのスレッドのスレッド プールを構築することをお勧めします。現在、基本的なデスクトップでは 4 つまたは 8 つです。

「分割統治」戦略のアプリケーションでは、スレッドごとに、検索の一部を含むジョブを与えます。コントローラーとワーカーの間には「プロデューサー/コンシューマー」の関係が存在します。ブロッキング キューを使用できます。ワーカーはジョブを待機し、コントローラーはそのジョブをキューに入れます。

「ジョブ」は、機能するすべての情報を含む構造体である場合があります。

于 2012-10-30T19:35:28.457 に答える