C++

Prime Finding

You should start off by coding a single threaded C++ program that finds all the primes in a given range. Basically this is the same starting code you used for the previous lab.

To test your results, the number of primes in the range [10..100] is 21 and for [1,000...1,000,000] it is 78,330.

You should take in the min and max ends of the range via the command line parameters: a.out 10 100

Parallel Partitioning

Next you are to run your program in parallel by adding openMP directives to the code. One of the first major choices one makes in creating parallel code is how to partition the data over the threads/nodes. For this lab we will be doing that partitioning in 2 ways. Each of these techniques should be coded as a separate function.

• Blocking: You are to break up the entire range of numbers to check into N even chunks where N is the number of threads you have running. You can find how many thread you have running by using the omp_get_num_threads() method. You can also get your thread number with omp_get_thread_num(). I understand that for certain implementations of openMP the default may be to break things up in this manner, however I want you to be explicit about it. That is, fully specify how you want it broken up and by exactly what size.
• Striping: You are to break up the entire range in round-robin fashion, giving the 1 to the first thread, 1 to the next thread, etc. Again you should be explicit about specifying things in your code.

Note that you can change the number of threads available to openMP by use of the function omp_set_num_threads(x). Remember that you have to include omp.h as well as compile with the -fopenmp flag (for linux). If you are using a mac you need to install openMP and use the flags:

-Xpreprocessor -fopenmp -lomp

Run Times

Lastly, you are to compare the running times of the 2 partitioning techniques. To do this, first up the range to something like [1,0001,000,000] that will take a bit of time to run. Next you need to know how to get the current time. There are several ways of doing so, but the best for openMP programs is to use omp_get_wtime() which returns a double representing the current time in seconds. I want the output to look like the following. Specifically, you should display the runtime for each thread as well as how many primes each thread found. You should also display the total runtime and total number of primes found. Run both methods sequentially from the main so all their results show up one after the next on the console.

Blocking time for 0: 0.668064 with 4199 found time for 1: 5.599338 with 3634 found time for 2: 10.659718 with 3464 found time for 3: 13.539341 with 3383 found time for 4: 14.312197 with 3300 found overall time: 14.348329 with 17980 found

Striping

......