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.

<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 != 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 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  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[i + stride]; __syncthreads(); }  if (i == 0) answer[blockIdx.x] = blockSum[0];}</pre>  The biggest significance was in the numbers we checked. Note the "checked/2" in our for loop, which wasn't divided by 2 in A2. Consider if 150 is prime: 150 / 75 = 2 150 / 76 = 1.9... ... 150 / 150 = 1  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| ]]