1
edit
Changes
→Assignment 2
RAM: 1GB DDR2
GPU: nVIDIA GEFORCE GT 620
== Closet Pair ==
'''Unfortunately we had to abandon the project since it was not really compatible with CUDA(there is no time to look more into it as the semester is almost over...). Team TudyBert, who are also working on the same project, have found that CUDA uses dynamic libraries where Dirve_God_Lin uses static libraries and there isn’t much to be done about that. As a result, we will be using Stephanie’s closet pair program.'''
The closet pair problem can be explained simply by imagining a random set of points spread in a metric space. Now the process of finding two points with the smallest distance between them is called the closet pair problem.
One of the more common algorithm used to find the closet pair is the Brute-force algorithm; which is calculating the distances of all the point ( O(n^2) notation):
n=total number of pints
n(n-1)/2
then simply look for the pair of points that has the smallest distance between each other. However, this algorithm was evident to be slow.
This is the function used in the closestPair.c program that Stephanie used for here assignment 1:
double brute_force(point* pts, int max_n, point *a, point *b)
{
int i, j;
double d, min_d = MAXDOUBLE;
for (i = 0; i < max_n; i++) {
for (j = i + 1; j < max_n; j++) {
d = dist(pts[i], pts[j]);
if (d >= min_d ) continue;
*a = pts[i];
*b = pts[j];
min_d = d;
}
}
return min_d;
}
This the profile:
As a consequence, we presume “parallellazing” this algorithm using CUDA technology will speed up the process significantly.
=== Assignment 3 ===
