1

C++ と OpenMP を使用してアルゴリズムを並列化し、凸包を見つけています。しかし、私は期待されるスピードアップを得ることができません。実際、順次アルゴリズムの方が高速です。ポイントの入力および出力セットは配列に格納されます。

コードを調べて、修正点を教えてください。

Point *points = new Point[inp_size]; // contains the input
  int th_id;

  omp_set_num_threads(nthreads);
  clock_t t1,t2;
      t1=clock();
  #pragma omp parallel private(th_id)
  {
    th_id = omp_get_thread_num();
///////////// …. Only Function called ….///////////////////////////////////
    findParallelUCHWOUP(points,th_id+1, nthreads, inp_size);

  }
  t2=clock();
  float diff ((float)t2-(float)t1);
  float seconds = diff / CLOCKS_PER_SEC;
  std::cout << "Time Elapsed in seconds:" << seconds << '\n';

/////////////////////////////////////////////// /////////////

int findParallelUCHWOUP(Point iv[],int id, int thread_num, int inp_size){

    int numElems = inp_size/thread_num;
        int first = (id-1) * numElems;;
        int last;
        if(id == thread_num){
            last = inp_size-1;
        }
        else{
            last = id*numElems-1;
        }

        output[first]=iv[first];
          std::stack<int> s;
          s.push(first);
          int i=first+1;
        while(i<last){
            if ( crossProduct(iv, i, first, last) > 0){
                s.push(i);
                i++;
                break;
            }else{
                i++;
            }
        }

        if(i==last){
            s.push(last);
            return 0;
        }

        for(;i<=last;i++){
            if ( crossProduct(iv, i, first, last) >= 0){
                  while ( s.size()>1 && crossProduct(iv, s.top(), second(s), i) <= 0){
                      s.pop();
                  }
                  s.push(i);
            }

        }
          int count=s.size();
          sizes[id-1] = count;
          while(!s.empty()){
              output[first+count-1]=iv[s.top()];
              s.pop();
              count--;
          }

    return 0;
}

///////////これらのマシンでテスト済み/////

連続時間:0.016466 2 つのスレッドを使用:0.022979 4 つのスレッドを使用:0.035213 8 つのスレッドを使用:0.03315

使用マシン: Mac Book Pro プロセッサ: 2.5 GHz Intel Core i5 (論理コアが 4 つ以上) メモリ: 4GB 1600 MHz コンパイラ: Mac OSX コンパイラ

4

1 に答える 1

1

問題は時間の数え方です。実際には、次のように書くことができます。

diff / (float) (CLOCKS_PER_SEC * nthreads)

これは概算にすぎません (常に正しいとは限りません)。
CLOCKS_PER_SEC は、すべてのコアのクロックの合計を表します
... OpenMP の特殊関数を使用した方がよいでしょう...

于 2013-06-16T21:27:03.537 に答える