1
edit
Changes
→Assignment 3
{{GPU610/DPS915 Index | 20131}}
[[Image:teamname.png|right|frameless|widthpx| ]]
= Project Name TBA Optimus Prime = The following page outlines the three-step progression through a program that counts the number of primes between 1 and N.
== Team Members ==
# [mailto:gtsmyth@learn.senecac.on.ca?subject=gpu610 Graeme Smyth], Some responsibility primary coder# [mailto:rhotin@learn.senecac.on.ca?subject=gpu610 Roman Hotin], Some other responsibility primary coder
[mailto:gtsmyth@learn.senecac.on.ca,rhotin@learn.senecac.on.ca?subject=dps901-gpu610 Email All]
== Progress ==
=== Assignment 3 ===
The lowest integer a division can produce that results in a prime is 2. In other words, the highest number we need check 150 for is 75, as all numbers between 1 and 2 aren't integers, and being 1 (150/150) doesn't make it prime. Hence, for checking if X is prime, we need only check from 1 to X/2, not to X. This Wiki page will created a speedup of roughly 2x, as compared to A2. Compared to A1, the results were more than 125,000x for n=1000. Higher values of n were not checked, due to the ridiculously long time A1 would take. For comparison's sake, A2 and A3 were compared using the max value they could compute (maxThreads * maxBlocks, 512 * 512 = 262,144). Even at such high numbers, A3 is still 2x more efficient than A2. Other forms of optimization were not possible.Memory coalescence couldn't be updated with details before done, as we aren't accessing values within an array (like a vector or matrix). When checking if a number is divisible by something, you need only check primes (Is it divisible by 2? 3? 5? 7? etc).You don't need to check non-primes. We thought we could store all primes found. That way, threads could merely check the previously found primes, instead of all numbers 1 to x/2. However, the logic structure of parallelization doesn't permit this, due date (11to threads running simultaneously. This means that a list of primes wouldn't exist prior to running any of the threads. This means that the simple algorithm improvements made appear to be the only optimizations possible. Data for all assignments, with available graphs, is shown below. [[Image:Gtsmyth a3.png|widthpx| ]][[Image:55pm April 12th)Gtsmyth a3 2.png|widthpx| ]]
=== Assignment 2 ===
Demonstration of how efficient A2 runs for n = 1,000 (for comparison, A1 took 20.78 seconds).
[[Image:A2_2.png|widthpx| ]]
=== Assignment 1 ===
Making parallel an application which calculates the first n primes.
<pre>
//DPS915 Assignment 1
//
//Graeme Smyth
//Code written by Graeme Smyth, with inspiration from course Workshop 1
//February 7th, 2013
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;
bool isPrime(int x)
{
for(int a = 0; a < x; a++) //a is any integer [0,x)
for(int b = 0; b < x; b++) //b is any integer [0,x)
if(a * b == x) //If a * b = x, then x has two integers that multiply to form it,
return false; //hence x is not prime
return true; //If we haven't returned by this point, x must be prime.
}
void findPrimes(int* answers, int n)
{
for(int i = 1, primesFound = 0; primesFound < n; i++) //Keep going until we have found n primes
if(isPrime(i)) //Test if "i" is prime
answers[primesFound++] = i; //If it is, record it
}
//Main takes one argument, integer n, and calculates the first n primes.
int main(int argc, char* argv[])
{
time_t timeStart, timeEnd;
//Check argument count
if (argc != 2)
{
cerr << "**invalid number of arguments**" << endl;
return 1;
}
int n = atoi(argv[1]);
int* answers = new int[n];
timeStart = time(nullptr); //Start timing
findPrimes(answers, n);
timeEnd = time(nullptr); //Finish timing
delete answers;
cout << setprecision(3);
cout << "Elapsed time : " << difftime(timeEnd, timeStart) << endl;
}
</pre>
====[[User:Rhotin | Roman Hotin]]====
