For a simple try at parallelization on my own outside of school, I've created a number factors calculator. I hope to eventually come up with something more creative.
Since I don't have access to parallel computers at this time, I'm using OpenMP provided by my compiler (gcc 4.8.1) and running it on my laptop (Intel Core i3-2330M). I'm using a maximum of four threads, which was determined from a call to omp_get_max_threads()
.
I've conducted four runs, each with four billion values and from one to four threads:
#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <omp.h>
void displayCompTime(std::clock_t start, std::clock_t end, std::int64_t integer, int threads)
{
double elapsed = static_cast<double>(end - start) / CLOCKS_PER_SEC;
std::cout << integer << " values and " << threads << " thread(s): "
<< std::setprecision(4) << std::fixed << elapsed << "s\n";
}
void calcFactors(std::int64_t integer, int threads)
{
std::map<std::int64_t, std::int64_t> factors;
std::int64_t i;
#pragma omp parallel for num_threads(threads) default(none) \
shared(factors, integer), private(i)
for (i = 2; i <= integer; i++)
{
if (integer % i == 0)
{
factors[i] = integer / i;
}
}
}
int main()
{
const std::int64_t integer = 4000000000;
const int runs = 4;
for (int i = 0; i < runs; i++)
{
std::clock_t start = std::clock();
int threads = i + 1;
calcFactors(integer, threads);
std::clock_t end = std::clock();
displayCompTime(start, end, integer, threads);
}
}
Output:
4000000000 values and 1 thread(s): 67.7330s 4000000000 values and 2 thread(s): 40.7640s 4000000000 values and 3 thread(s): 32.5630s 4000000000 values and 4 thread(s): 29.7640s
Based on these results, this code doesn't appear to scale very well. I don't know if using a non-default static schedule would give faster times, and anything else would just incur additional overhead. Fortunately, I didn't need to include atomic or critical.
Would avoiding a lot of division help? I didn't try for anything else yet as this is only a start. I also wanted to see how well my laptop could handle parallelization.
Other than performance, I'm okay with any general OpenMP advice. I was sure to use some good practices for that, such as default(none)
for explicitly listing the variables.