Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2730 Systems Programming</fs></WRAP>
</WRAP>

~~TOC~~

======Project: ALGORITHMS - PRIME NUMBER CALCULATION (pnc1)======

=====Objective=====
To apply your skills in the implementation of prime number calculating algorithms, this time in a concurrent setting.

=====Prerequisites/Corequisites=====
In addition to the new skills required on previous projects, to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * **fork**(**2**)
  * algorithms to appropriately split up the work among a group

=====Algorithmic Complexity=====
A concept in Computer Science curriculum is the notion of computational/algorithmic complexity.

Basically, a solution to a problem exists on a spectrum of efficiency (typically constrained by time vs. space): if optimizing for time, the code size tends to grow.

Additionally, if optimizing for time (specifically to reduce the amount of time taken), strategic approaches are taken to reduce unnecessary or redundant operations (yet still achieving the desired end results).

Through the concurrent implementations in this project, we should start to see some of the impacts those approaches can have on runtime. It may not offer exact 50% cuts in runtime, but more fully utilizing available computing resources should have a notable and appreciable impact on overall runtime.

=====Background=====
We explored the basic essence of prime numbers in the last project. This time around, we will be modifying the brute force and square root variants to utilize **fork()**, so the work can be split up and performed by child processes (the parent will merely be coordinating the effort, and not performing any prime computational work).

=====Calculating the primality of a number=====
As of yet, there is no quick and direct way of determining the primality of a given number. Instead, we must perform a series of tests to determine if it fails primality (typically by proving it is composite).

This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take increasing amounts of time. Often, approaches to prime number calculation involve various algorithms, which offer various benefits (less time) and drawback (more complex code).

Your task for this project is to implement 2 prime number programs:

  - forked brute force prime calculation
  - forked square root-optimized brute force calculation

====brute force====
The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to  have something to compare against).

To perform it, we simply attempt to evenly divide all the values between 1 and the number in question. If any one of them divides evenly, the number is **NOT** prime, but instead a composite value.

Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state).

For example, the number 11:

<code>
11 % 2 = 1 (2 is not a factor of 11)
11 % 3 = 2 (3 is not a factor of 11)
11 % 4 = 3 (4 is not a factor of 11)
11 % 5 = 1 (5 is not a factor of 11)
11 % 6 = 5 (6 is not a factor of 11)
11 % 7 = 4 (7 is not a factor of 11)
11 % 8 = 3 (8 is not a factor of 11)
11 % 9 = 2 (9 is not a factor of 11)
11 % 10 = 1 (10 is not a factor of 11)
</code>

Because none of the values 2-10 evenly divided into 11, we can say it passed the test: **11 is a prime number**

On the other hand, take 119:

<code>
119 % 2 = 1 (2 is not a factor of 119)
119 % 3 = 2 (3 is not a factor of 119)
119 % 4 = 3 (4 is not a factor of 119)
119 % 5 = 4 (5 is not a factor of 119)
119 % 6 = 5 (6 is not a factor of 119)
119 % 7 = 0 (7 is a factor of 119)
</code>

Because 7 evenly divided into 119, it failed the test: 119 is **not** a prime, but instead a composite number.

There is no further need to check the remaining values, as once we have proven the non-primality of a number, the state is set: it is composite. So be sure to use a **break** statement to terminate the computation loop (will also be a nice boost to runtime).

So when contemplating a concurrent solution, imagine we were computing the primes between 2-4096, and we were splitting up the work among 4 child processes:
  * 4096 / 4 is 1024
    * one child would do 2-1024
    * another would do 1025-2048
    * a third would do 2049-3072
    * and the last would do 3073-4096 (4095, technically)

This way the same amount of work is being performed, only instead of in one batch run, as 4 concurrent fractions of the work. Theoretically, this should result in a near 4X performance improvement, but as we will see, it won't be that direct, due to hardware and software details (I/O, memory access, OS mechanisms, etc.); there should be notable improvements, however.

====square root====
An optimization to the computation of prime numbers is the square root trick. Basically, if we've processed numbers up to the square root of the number we're testing, and none have proven to be evenly divisible, we can also assume primality and bail out.

The C library has a **sqrt()** function available through including the **math.h** header file, and linking against the math library at compile time (add **-lm** to your gcc line).

To use **sqrt()**, we pass in the value we wish to obtain the square root of, and assign the result to an **int**:

<code c>
int x = 25;
int y = 0;

y = sqrt(x);

// y should be 5 as a result
</code>

For instance, the number 37 (using the square root optimization), we find the square root (whole number) of 37 is 6, so we only need to check 2-6:

<code>
37 % 2 = 1 (2 is not a factor of 37)
37 % 3 = 1 (3 is not a factor of 37)
37 % 4 = 1 (4 is not a factor of 37)
37 % 5 = 2 (5 is not a factor of 37)
37 % 6 = 1 (6 is not a factor of 37)
</code>

Because none of these values evenly divides, we can give 37 a pass: **it is a prime**

This will dramatically improve the runtime, and offers a nice comparison against our brute force baseline.

Similar to the forked brute force, we will look to split up the work among a group of child processes, with the parent being the coordinator.

=====Program=====
It is your task to write 2 separate prime number calculating programs:

  - **primebrutefork.c**: for your forked brute force implementation
  - **primesqrtfork.c**: for your forked square root-optimization of the brute force

Your program should:
  * obtain 3 parameters from the command-line (see **command-line arguments** section below):
    * argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number)
    * argv[2]: visibility. If a **1** is provided, print out the prime numbers in a space separated list; if a **0** is provided, run silent: only display the runtime information.
    * argv[3]: number of child processes to fork (we'll be testing with 2 and 4 child processes).
    * these values should be positive integer values; you can make the assumption that the user will always do the right thing.
  * start your stopwatch (see **timing** section below):
  * determine how to split up the work load, and fork() the requested number of child processes
  * have each child perform its share of the work utilizing the given algorithm 
    * if enabled, display the prime numbers found in the range
    * in a concurrent implementation, you'll likely want to have each child open up a unique file and output all its values there. When the children are finished, the parent can then reassemble and display the primes in sequential order.
  * output the processing run-time to STDERR (do this always).
  * your output **MUST** be conformant to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically:
    * if primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued.
    * the timing information will be displayed in accordance to code I will provide (in the **timing** section).

====Other considerations====
All your programs MUST perform the calculations to determine primality- you may not always be printing it out (depending on argv[2]), but work must be done to ensure the value is identified as a prime/composite value.

For example:

<code>
if (show == 1)
{
	work to determine if it is prime
	if prime
		print number
}
</code>

will actually skip the core processing, and you’ll see some amazing runtimes as a result. They may be amazing, but they’re not real, because you’re not actually doing anything.

What you want instead:

<code>
work to determine if it is prime
if (show == 1)
{
	if prime
		print number
}
</code>

there are many ways to express the above, through compound if statements and other arrangements, but notice how nothing is holding back “work to determine if it is prime”.

That also isn’t to say you can’t avoid doing a work run if you’re able to determine its non-primality with a simple pretest (even value, factor of 3, etc.), but that’s actually considered more of the core “work”, so it is more than okay (and encouraged in the optimized prime variants).

=====Command-Line Arguments=====
To automate our comparisons, we will be making use of command-line arguments in our programs. As we have yet to really get into arrays, I will provide you same code that you can use that will allow you to utilize them for the purposes of this project.

====header files====
We don't need any extra header files to use command-line arguments, but we will need an additional header file to use the **atoi(3)** function, which we'll use to quickly turn the command-line parameter into an integer, and that header file is **stdlib.h**, so be sure to include it with the others:

<code c>
#include <stdio.h>
#include <stdlib.h>
</code>

====setting up main()====
To accept (or rather, to gain access) to arguments given to your program at runtime, we need to specify two parameters to the main() function. While the names don't matter, the types do.. I like the traditional **argc** and **argv** names, although it is also common to see them abbreviated as **ac** and **av**.

Please declare your main() function as follows:

<code c>
int main(int argc, char **argv)
</code>

The arguments are accessible via the argv array, in the order they were specified:

  * argv[0]: program invocation (path + program name)
  * argv[1]: our maximum / upper bound
  * argv[2]: visibility (1 to show primes, 0 to be silent)
  * argv[3]: processes (number of child processes to fork; 2,4)

There are ways to do flexible argument parsing, and even to have dashed options as we have on various commands. But such things are beyond the scope of our current endeavors, so we will stick to this basic functionality for now.

====Simple argument checks====
Although I'm not going to require extensive argument checking for this project, here's how we would check to see if the minimal number of arguments has been provided:

<code c>
    if (argc < 4)  // if less than 4 arguments have been provided
    {
        fprintf(stderr, "Not enough arguments!\n");
        exit(1);
    }
</code>

If you're wondering, "why 4? I thought we only had 3.", C includes the program's name as the first argument, so we want program + max + visibility + processes, or 4.

====Grab and convert max and visibility====
Finally, we need to put the arguments representing the maximum value, visibility settings, and number of processes into variables.

I'd recommend declaring two variables of type **int**.

We will use the **atoi(3)** function to quickly convert the command-line arguments into **int** values:

<code c>
    max  = atoi(argv[1]);
    show = atoi(argv[2]);
    np   = atoi(argv[3]);
</code>

And now we can proceed with the rest of our prime implementation.

=====Timing=====
Often times, when checking the efficiency of a solution, a good measurement (especially for comparison), is to time how long the processing takes.

In order to do that in our prime number programs, we are going to use C library functions that obtain the current time, and use it as a stopwatch: we'll grab the time just before starting processing, and then once more when done. The total time will then be the difference between the two (end_time - start_time).

We are going to use the **gettimeofday(2)** function to aid us in this, and to use it, we'll need to do the following:

====header file====
In order to use the **gettimeofday(2)** function in our program, we'll need to include the **sys/time.h** header file, so be sure to add it in with the existing ones:

<code c>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
</code>

====timeval variables====
**gettimeofday(2)** uses a **struct timeval** data type, of which we'll need to declare two variables in our programs (one for storing the starting time, and the other for the ending time).

Please declare these with your other variables, up at the top of main() (but still WITHIN main()-- you do not need to declare global variables).

<code c>
    struct timeval time_start; // starting time
    struct timeval time_end;   // ending time
</code>

====Obtaining the time====
To use **gettimeofday(2)**, we merely place it at the point in our code we wish to take the time.

For our prime number programs, you'll want to grab the start time **AFTER** you've declared variables and processed arguments, but **JUST BEFORE** starting the driving loop doing the processing.

That call will look something like this:

<code c>
    gettimeofday(&time_start, 0);
</code>

The ending time should be taken immediately after all processing (and prime number output) is completed, and right before we display the timing information to STDERR:

<code c>
    gettimeofday(&time_end, 0);
</code>

====Displaying the runtime====
Once we having the starting and ending times, we can display this to STDERR. You'll want this line:

<code c>
    fprintf(stderr, "%10.6lf\n", time_end.tv_sec - time_start.tv_sec + ((time_end.tv_usec - time_start.tv_usec) / 1000000.0));
</code>

For clarity sake, that format specifier is "%10.6lf", where the "lf" is "long float", that is **NOT** a number one but a lowercase letter 'ell'.

And with that, we can compute an approximate run-time of our programs. The timing won't necessarily be accurate down to that level of precision, but it will be informative enough for our purposes.

=====Execution=====
Several operating behaviors are shown as examples.

Brute force showing primes, 2 child processes:

<cli>
lab46:~/src/sysprog/pnc1$ ./primebrutefork 90 1 2
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 
  0.000088
lab46:~/src/sysprog/pnc1$ 
</cli>

Brute force not showing primes, 2 child processes:

<cli>
lab46:~/src/sysprog/pnc1$ ./primebrutefork 90 0 2
  0.000008
lab46:~/src/sysprog/pnc1$ 
</cli>

Similarly, for the square root version (showing primes, 4 child processes):

<cli>
lab46:~/src/sysprog/pnc1$ ./primesqrtfork 90 1 4
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 
  0.000089
lab46:~/src/sysprog/pnc1$ 
</cli>

And, without showing primes (4 child processes):

<cli>
lab46:~/src/sysprog/pnc1$ ./primesqrtfork 90 0 4
  0.000006
lab46:~/src/sysprog/pnc1$ 
</cli>

Don't be alarmed by the visible square root actually seeming to take MORE time; we have to consider the range as well: 90 is barely anything, and there is overhead incurred from the **sqrt()** function call. The real savings will start to be seen once we get into the thousands (and beyond).

And that's another neat thing with algorithm comparison: a "better" algorithm may have a sweet spot or power band: they may actually perform worse until (especially at the beginning).

The same goes for your optimized solution (same parameters).

The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.

=====Check Results=====
If you'd like to compare your implementations, I rigged up a script called **primerun** which you can run.

In order to work, you **MUST** be in the directory where your **primebrutefork** and **primesqrtfork**.

It is recommended to have your single process versions of **primebrute**, **primesqrt**, and **primeopt** available in the same directory for comparisons against these new variants.

For instance (running on my implementations):

<cli>
lab46:~/src/sysprog/pnc1$ primerun
============================================
   range       brute        sqrt         opt 
============================================
       8    0.000002    0.000002    0.000002  
      16    0.000002    0.000002    0.000002  
      32    0.000003    0.000004    0.000002  
      64    0.000005    0.000020    0.000003  
     128    0.000012    0.000023    0.000003  
     256    0.000037    0.000029    0.000006  
     512    0.000165    0.000036    0.000014  
    1024    0.000540    0.000080    0.000033  
    2048    0.001761    0.000187    0.000078  
    4096    0.006115    0.000438    0.000189  
    8192    0.021259    0.001036    0.000458  
   16384    0.077184    0.002520    0.001153  
   32768    0.281958    0.006156    0.002826  
   65536    1.046501    0.015234    0.007135  
  131072    5.160141    0.045482    0.021810  
  262144    --------    0.119042    0.057520  
  524288    --------    0.301531    0.146561  
 1048576    --------    0.758027    0.370700  
 2097152    --------    1.921014    0.943986  
 4194304    --------    4.914725    2.423202  
 8388608    --------    --------    --------  
============================================
 verify:       OK          OK          OK     
============================================
lab46:~/src/sysprog/pnc1$ 
</cli>

For evaluation, each test is run 4 times, and the resulting time is averaged. During development, I have it set to only run each test once.

If the runtime of a particular prime variant exceeds an upper threshold (likely to be set at 2 seconds), it will be omitted from further tests, and a series of dashes will instead appear in the output.

If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate.

In the example output above, my **primeopt** is playing with an implementation of the **6a+/-1** algorithm.

I also include a validation check- to ensure your prime programs are actually producing the correct list of prime numbers. If the check is successful, you will see "OK" displayed beneath in the appropriate column; if unsuccessful, you will be "MISMATCH".

If you'd like to experiment with other variations, the script also recognizes prime variants of the following names:
  * primeoptfork (for an additional optimization)
  * primemapfork
  * primesievefork

=====Submission=====
To successfully complete this project, the following criteria must be met:

  * Code must compile cleanly (no warnings or errors)
  * Output must be correct, and match the form given in the sample output above.
  * Code must be nicely and consistently indented (you may use the **indent** tool)
  * Code must utilize the algorithm(s) presented above:
    * **primebrutefork.c** must do the forked unoptimized brute force method
    * **primesqrtfork.c** must utilize the forked brute force method along with the square root trick (no other tricks)
  * Code must be commented
    * have a properly filled-out comment banner at the top
      * be sure to include any compiling instructions
    * have at least 20% of your program consist of **<nowiki>//</nowiki>**-style descriptive comments
  * Output Formatting (including spacing) of program must conform to the provided output (see above).
  * Track/version the source code in a repository
  * Submit a copy of your source code to me using the **submit** tool.

To submit this program to me using the **submit** tool, run the following command at your lab46 prompt:

<cli>
$ submit sysprog pnc1 primebrutefork.c primesqrtfork.c
Submitting sysprog project "pnc1":
    -> primebrutefork.c(OK)
    -> primesqrtfork.c(OK)

SUCCESSFULLY SUBMITTED
</cli>

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.
Lab46 Wiki

User Tools

Site Tools

Page Tools
