以下の結果を見て、コードをさらに最適化して高速化できる場所を教えてください。
Result
使用マシン: Mac Book Pro プロセッサ: 2.5 GHz Intel Core i5 (論理コアが 4 つ以上)
メモリ: 4GB 1600 MHz コンパイラ: Mac OSX コンパイラ
Sequential Time:0.016466
Using two threads:0.0120111
Using four threads:0.0109911(Speed Up ~ 1.5)
Using 8 threads: 0.0111289
II マシン: OS: Linux ハードウェア: Intel(R) Core™ i5-3550 CPU @ 3.30GHz × 4 メモリ: 7.7 GiB コンパイラ: G++ バージョン 4.6
Sequential Time:0.0128901
Using two threads:0.00838804
Using four threads:0.00612688(Speed up = 2)
Using 8 threads: 0.0101049
直線的なスピードアップが得られないコードのオーバーヘッドを教えてください。コードには大したことはありません。次のように、メイン関数で関数「findParallelUCHWOUP」を呼び出しています。
#pragma omp parallel for private(th_id)
for (th_id = 0; th_id < nthreads; th_id++)
findParallelUCHWOUP(points, th_id + 1, nthreads, inp_size, first[th_id], last[th_id]);
コード：
class Point {
double i, j;
public:
Point() {
i = 0;
j = 0;
}
Point(double x, double y) {
i = x;
j = y;
}
double x() const {
return i;
}
double y() const {
return j;
}
void setValue(double x, double y) {
i = x;
j = y;
}
};
typedef std::vector<Point> Vector;
int second(std::stack<int> &s);
double crossProduct(Point v[], int a, int b, int c);
bool myfunction(Point a, Point b) {
return ((a.x() < b.x()) || (a.x() == b.x() && a.y() < b.y()));
}
class CTPoint {
int i, j;
public:
CTPoint() {
i = 0;
j = 0;
}
CTPoint(int x, int y) {
i = x;
j = y;
}
double getI() const {
return i;
}
double getJ() const {
return j;
}
};
const int nthreads = 4;
const int inp_size = 1000000;
Point output[inp_size];
int numElems = inp_size / nthreads;
int sizes[nthreads];
CTPoint ct[nthreads][nthreads];
//function that is called from different threads
int findParallelUCHWOUP(Point* iv, int id, int thread_num, int inp_size, int first, int last) {
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;
}
double crossProduct(Point* v, int a, int b, int c) {
return (v[c].x() - v[b].x()) * (v[a].y() - v[b].y())
- (v[a].x() - v[b].x()) * (v[c].y() - v[b].y());
}
int second(std::stack<int> &s) {
int temp = s.top();
s.pop();
int sec = s.top();
s.push(temp);
return sec;
}
//reads points from a file and divides the array of points to different threads
int main(int argc, char *argv[]) {
// read points from a file and assign them to the input array.
Point *points = new Point[inp_size];
unsigned i = 0;
while (i < Points.size()) {
points[i] = Points[i];
i++;
}
numElems = inp_size / nthreads;
int first[nthreads];
int last[nthreads];
for(int i=1;i<=nthreads;i++){
first[i-1] = (i - 1) * numElems;
if (i == nthreads) {
last[i-1] = inp_size - 1;
} else {
last[i-1] = i * numElems - 1;
}
}
/* Parallel Code starts here*/
int th_id;
omp_set_num_threads(nthreads);
double start = omp_get_wtime();
#pragma omp parallel for private(th_id)
for (th_id = 0; th_id < nthreads; th_id++)
findParallelUCHWOUP(points, th_id + 1, nthreads, inp_size, first[th_id], last[th_id]);
/* Parallel Code ends here*/
double end = omp_get_wtime();
double diff = end - start;
std::cout << "Time Elapsed in seconds:" << diff << '\n';
return 0;
}