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 ===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, 5, 7 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. <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 if((check % 2 ==0 && check !=[[User:Gtsmyth 2) || Graeme Smyth]] (check % 3 ==0 && check !=3) || (check % 5 == 0 && check != 5) || (check % 7 ==0 && check !=7) || (check % 11 ==Topic0 && 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 xMaking parallel an application which calculates the first n primes. flag = false; //Found to not be prime
if(flag) //If prime
blockSum[i] = 1; //Add one to our numbers
}
__syncthreads(); //Ensure all threads are caught up
for (int stride =blockDim.x >> 1; stride > 0; stride >>=1) { if (i < stride) blockSum[i] +==[blockSum[User:Rhotin | Roman Hotin]i + stride]; __syncthreads(); } if (i ====0) answer[blockIdx.x] =====Topic=====blockSum[0];encrypting text}---</pre>
150 / 150 = 1
This created a speedup of roughly 2x, as compared to A2.
Compared to A1, the results were more than 125,000x for n=1000.
This means that the simple algorithm improvements made appear to be the only optimizations possible.
[[Image:Gtsmyth a3.png|widthpx| ]]
[[Image:Gtsmyth a3 2.png|widthpx| ]]
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)).
<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
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.
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
//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;
}
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(string 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>--- === Assignment 2 ====== Assignment 3 ===-