Open main menu

CDOT Wiki β

Changes

Team Name (Official)

5,587 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 A3 was difficult to produce, due to the shear success of A2. Still, some optimizations were found. See below. Please note the preliminary check for division by 2, 3 was , 5, 7 and 11. By checking these common primes first, we could eliminate most possibilities without even entering a loop. It is very successfulinsignificant, but helps in most cases. <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 check = j+1;
We are submitting the files now blockSum[i] = 0; __syncthreads(7:00pm April 11th).;
This Wiki page will be updated with details before the due date if(11:55pm April 12thcheck >= 2 && check <= n). { bool flag = true; //Assume prime
if((check % 2 == 0 && check != 2) || (check % 3 == 0 && check != 3) || (check % 5 == 0 && check !=5) || (check % 7 == Assignment 0 && check != 7) || (check % 11 == 0 && check != 11)) //If divisible by x flag = false; //Found to not be prime for(int 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
we have chosen to work on the program that finds out how many primes are between 1 and N=== 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 check = j+1;
blockSum[i] = 0; __syncthreads();  if(check >= 2 && check <= n) { bool flag = true; //Assume prime for(int len x = strTarget.length2; 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) a answer[blockIdx.x] = strTargetblockSum[0];}</pre>  Sample output from A2, for demonstration: [[Image:gtsmyth A2.atpng|widthpx| ]]    Demonstration of how efficient A2 runs for n = 1,000 (ifor comparison, A1 took 20.78 seconds); .  [[Image:A2_2.png|widthpx| ]] === Assignment 1 =======[[User:Gtsmyth | Graeme Smyth]]=========Topic=====Making parallel an application which calculates the first n primes.
int b = (int)a; <pre>//get the ASCII value of 'a'DPS915 Assignment 1////Graeme Smyth//Code written by Graeme Smyth, with inspiration from course Workshop 1//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);
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;
 
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/95143...95160"