Open main menu

CDOT Wiki β

Changes

Team Name (Official)

5,415 bytes added, 00:05, 12 April 2013
→‎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 ===
Assignment 3 A3 was very successfuldifficult to produce, due to the shear success of A2. Still, some optimizations were found. See below.
We are submitting Please note the files now (preliminary check for division by 2, 3, 5, 7:00pm April 11th)and 11. By checking these common primes first, we could eliminate most possibilities without even entering a loop. It is very insignificant, but helps in most cases.
This Wiki page will be updated with details before the due date <pre>__global__ void findPrimes(11:55pm April 12thint* answer, int n){ int i = threadIdx.x; int j = blockIdx.x * blockDim.x + threadIdx.x; __shared__ int blockSum[ntpb];
int check === Assignment 2 ===We chose to work on the program that finds out how many primes are between j+1 and N.;
Assignment 2 was very successful. blockSum[i] = 0; __syncthreads();
We are submitting the files now if(7:00pm April 11thcheck >= 2 && check <= n). { bool flag = true; //Assume prime
This Wiki page will if((check % 2 == 0 && check != 2) || (check % 3 == 0 && check != 3) || (check % 5 == 0 && check != 5) || (check % 7 == 0 && check != 7) || (check % 11 == 0 && check != 11)) //If divisible by x flag = false; //Found to not be updated with details before A3's due date prime for(11:55pm April 12thint x = 2; x < check/2 && flag; x++) //Check all numbers 2 to "check" if(check % x == 0). //If divisible by x flag = false; //Found to not be prime
=== Assignment 1 === if(flag) //If prime==== blockSum[[User:Gtsmyth | Graeme Smyth]i]=========Topic=====1; //Add one to our numbersMaking parallel an application which calculates the first n primes. }
__syncthreads(); //Ensure all threads are caught up
for (int stride = blockDim.x >> 1; stride > 0; stride >>= 1)
{
if (i < stride)
blockSum[i] += blockSum[i + stride];
__syncthreads();
}
 
if (i == 0)
answer[blockIdx.x] = blockSum[0];
}
</pre>
====[[User:Rhotin | Roman Hotin]]====
=====Topic=====
encrypting text
----
<pre>
#include <iostream>
#include <cstdlib>The biggest significance was in the numbers we checked. Note the "check/2" in our for loop, which wasn't divided by 2 in A2.
#include <ctime>Consider if 150 is prime:
#include <cstring>150 / 75 = 2
#include <string>150 / 76 = 1.9...
#include <cctype>...
150 / 150 = 1
using namespace std;The lowest integer a division can produce that results in a prime is 2.
void EncryptIn 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 (string&150/150);doesn't make it prime.
string Decrypt(string strTarget);Hence, for checking if X is prime, we need only check from 1 to X/2, not to X.
This created a speedup of roughly 2x, as compared to A2.
Compared to A1, the results were more than 125,000x for n=1000.
int main(int argcHigher values of n were not checked, char* argv[]) {due to the ridiculously long time A1 would take.
//initialize For comparison's sake, A2 and get A3 were compared using the string from the usermax value they could compute (maxThreads * maxBlocks, 512 * 512 = 262,144). Even at such high numbers, A3 is still 2x more efficient than A2.
string strTarget;
cout << "Enter a string to encrypt: ";
//getlineOther forms of optimization were not possible.Memory coalescence couldn't be done, as we aren't accessing values within an array (cin,strTargetlike a vector or matrix);.
strTarget = argv[1];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.
string temp(strTarget);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 to threads running simultaneously. This means that a list of primes wouldn't exist prior to running any of the threads.
Encrypt(strTarget);
This means that the simple algorithm improvements made appear to be the only optimizations possible.
cout << "Encrypted: " << strTarget << endl;Data for all assignments, with available graphs, is shown below.
cout << "Decrypted: " << Decrypt(strTarget) << endl;
[[Image:Gtsmyth a3.png|widthpx| ]]
[[Image:Gtsmyth a3 2.png|widthpx| ]]
return 0;=== Assignment 2 ===A2 featured a significantly improved prime-counting algorithm, coupled with GPU integration.
}
Going from A1 to A2, our code experienced a speed-up of 6,015,300% (or 60,154x faster (literally - A1 was <u>'''''that'''''</u> inefficient)).
void Encrypt(string &strTarget)Kernel code for A2:
<pre>__global__ void findPrimes(int* answer, int n)
{
int i = threadIdx.x;
int j = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int blockSum[ntpb];
int len check = strTarget.lengthj+1;  blockSum[i] = 0; __syncthreads();  if(check >= 2 && check <= n) { bool flag = true; //Assume prime for(int x = 2; x < check && flag; x++) //Check all numbers 2 to "check" if(check % x == 0) //If divisible by x flag = false; //Found to not be prime
char a;
string strFinal if(strTargetflag) //If prime blockSum[i] = 1;//Add one to our numbers }
for __syncthreads(int i = 0; i <= (len-1); i++)//Ensure all threads are caught up
for (int stride = blockDim.x >> 1; stride > 0; stride >>= 1)
{
if (i < stride)
blockSum[i] += blockSum[i + stride];
__syncthreads();
}
 
if (i == 0)
answer[blockIdx.x] = blockSum[0];
}</pre>
 
 
Sample output from A2, for demonstration:
 
[[Image:gtsmyth A2.png|widthpx| ]]
 
 
 
 
Demonstration of how efficient A2 runs for n = 1,000 (for comparison, A1 took 20.78 seconds).
a = strTarget.at(i);
int b [[Image:A2_2.png|widthpx| ]] = (int)a; == Assignment 1 =======[[User:Gtsmyth | Graeme Smyth]]=========Topic=====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//get the ASCII value of 'a'February 7th, 2013
b += 2#include <iostream>#include <iomanip>#include <cstdlib>#include <cmath>#include <ctime>using namespace std; //Mulitply the ASCII value by 2
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 > 254== x) { //If a * b = 254x, then x has two integers that multiply to form it, return false; } //hence x is not prime
a = (char)b return true; //Set the new ASCII value back into the charIf we haven't returned by this point, x must be prime.}
strFinal.insertvoid findPrimes(int* answers, int n){ for(int i , = 1, aprimesFound = 0; primesFound < n; i++)//Keep going until we have found n primes if(isPrime(i)) //Test if "i" is prime answers[primesFound++] = i; //Insert the new Character back into the stringIf 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;
}
string strEncryptedint n = atoi(strFinalargv[1]); int* answers = new int[n]; timeStart = time(nullptr); //Start timing  findPrimes(answers, 0, lenn);  timeEnd = time(nullptr);//Finish timing
strTarget = strEncrypteddelete answers;
cout << setprecision(3);
cout << "Elapsed time : " << difftime(timeEnd, timeStart) << endl;
}
</pre>
 
====[[User:Rhotin | Roman Hotin]]====
=====Topic=====
encrypting text
----
<pre>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <cctype>
using namespace std;
void Encrypt(string&);
string Decrypt(string strTarget);
 
 
int main(int argc, char* argv[]) {
//initialize and get the string from the user
string strTarget;
cout << "Enter a string to encrypt: ";
//getline(cin,strTarget);
strTarget = argv[1];
string temp(strTarget);
Encrypt(strTarget);
cout << "Encrypted: " << strTarget << endl;
cout << "Decrypted: " << Decrypt(strTarget) << endl;
string Decrypt(string strTarget) return 0;}
void Encrypt(string &strTarget)
{
int len = strTarget.length();
char a;
string strFinal(strTarget);
for (int i = 0; i <= (len-1); i++)
{
a = strTarget.at(i);
int b = (int)a; //get the ASCII value of 'a'
b += 2; //Mulitply the ASCII value by 2
if (b > 254) { b = 254; }
a = (char)b; //Set the new ASCII value back into the char
strFinal.insert(i , 1, a); //Insert the new Character back into the string
}
string strEncrypted(strFinal, 0, len);
strTarget = strEncrypted;
}
string Decrypt(string strTarget)
{
int len = strTarget.length();
 
char a;
 
string strFinal(strTarget);
 
for (int i = 0; i <= (len-1); i++)
 
{
 
a = strTarget.at(i);
 
int b = (int)a;
 
b -= 2;
 
 
a = (char)b;
 
strFinal.insert(i, 1, a);
 
}
 
string strDecrypted(strFinal, 0, len);
 
return strDecrypted;
 
}
</pre>
----
Gtsmyth
1
edit
Retrieved from "https://wiki.cdot.senecapolytechnic.ca/wiki/Special:MobileDiff/95145...95160"