Multithreaded Perfect Numbers Project

For this project you will write a C program which figures out whether or not a positive integer is a perfect number. Your program will support using multiple threads to speed up computation.

There are multiple ways you could approach this problem. For full credit you must follow the approach laid out here. Please read these instructions carefully in their entirety before you begin.

Perfect Numbers

A positive integer \(n\) is a perfect number if the sum of all its factors, excluding itself, is \(n\).

For example, the factors of \(6\) are \(1\), \(2\), \(3\), and \(6\), and \(1 + 2 + 3 = 6\), so \(6\) is a perfect number.

Finding Factors

The most straightforward algorithm for finding the factors of a postive integer \(n\) is as follows:

for each integer x from 1 to n / 2:
    if n % x is 0:
        add x to the list of factors

One optimization we can make is to take advantage of the fact that if \(x\) is a factor of \(n\) and \(x \lt \sqrt{n}\), then \(\frac{n}{x}\) is also a factor of \(n\). Whether or not you take advantage of this fact is up to you. I recommend implementing the simpler version first and then applying the optimization later if you have time. The rest of these instructions assume you are using the more straightforward algorithm that searches from \(1\) to \(\frac{n}{2}\).

Partitioning the Search Space

Rather than having a single thread test each number from \(1\) to \(\frac{n}{2}\), we can divide the search space into partitions and have a different thread search each partition.

For example, if we are checking whether or not \(120\) is a perfect number, then we need to check each number from \(1\) to \(60\). If we use 4 threads, each thread can check a portion of the range. The first thread can check \(1\) through \(12\), the second can check \(13\) through \(24\), etc.

Keep in mind that if the size of the search space is not divisible by the number of threads, then each thread will not be able to check the same number of potential factors. In this case you will need to spread the remainder over some of the threads, so some threads will have one more number to operate on than the others.

For example, if you are checking the number 28 with 4 threads, then there are 14 numbers to be checked, which is not divisible by 4. Using integer division, 14 / 4 is 3 with a remainder of 2. A naive way to divide the range up would be to give every thread 3 numbers, and then give the last one 2 extra. However, this strategy will result in one thread having a significantly larger range than the rest in situations where there is a large remainder, and you will not take full advanage of the efficiency gain of using threads. So in this case you want 2 threads that will operate on 4 numbers and one thread that will operate on 3.

Another case that can occur is if the number of threads is larger than the size of the search space. In this case, reduce the number of threads to be the same size as the search space.

Storing the factors

Each time a thread finds a new factor, it must place it into an array of factors that is shared by all threads.

It is possible that this array will need to be as large as \(\frac{n}{2}\) (in the case of \(n = 6\)), but normally it will not need to be nearly that large. As to not waste memory, begin by creating a modestly sized array using malloc(), and then exponentially increase the size of the array using realloc() by doubling the size of the array each time it fills up. This is the strategy that is used behind the scenes for dynamic arrays in most language, such as C++’s vector class.

To accomplish this in a thread-safe fashion, all the threads will need to be able to read and write 4 shared items: a pointer to the array, the current number of items in the array, the current capacity of the array, and a pointer to a mutex. If a thread finds a factor and the current number of items in the array is smaller than the current capacity of the array, then the thread may simply write the next factor into the array and increment the current number of items in the array. If the current number of items in the array is equal to the current capacity of the array, then the thread will need to call realloc() to increase the size (the capacity) of the array. Both of these scenarios should fall in the same critical section, and the shared mutex must be used appropriate to achieve mutual exclusion.

Passing Data to Threads

In the counter example we passed information to a thread in a single structure. For this one I recommend two separate structures. One will get passed to the thread function, and that structure will have a pointer to an instance of another structure type which stores the shared information.

So the structures could look like this:

struct shared_data {
    // capacity, number of items, array pointer, and lock pointer go here
};
    
struct thread_data {
    // n and the beginning and end of the range to operate on goes here

    // pointer to an instance of the shared data struct
    struct shared_data *shared_data;
};

You will need an array of instances of struct thread_data, but only a single instance of struct shared_data.

Output

Your program must print all of the number’s factors (excluding itself) and then print whether or not the number is perfect. All of the printing must happen in main() after joining the threads. Below is some example output. Note that the factors will not necessarily be in the array in ascending order, since the scheduling of the threads is not deterministic.

$ ./perfect 28 4
Factors of 28:
7
1
2
4
14
28 is a perfect number

$ ./perfect 17153557 4
Factors of 17153557:
1
2957
5801
17153557 is not a perfect number

Testing

Make sure you test your program with a number of different cases. Here are some:

• The number of threads is greater than \(\frac{n}{2}\) (or \(\sqrt{n}\) if you go that route)
• Prime numbers (you should not find any factors besides 1)
• The largest perfect number that can be factored in a reasonable amount of time (I have found that 12 digits can be done in minutes, going up to 13 digits means you will have to wait a while). You can find lists of perfect numbers online.
• Numbers with many factors so that your code is forced to grow the array many times, and to a size larger than a page (factorials are great for this)
• Scenarios that would be likely to cause a race condition if you did not handle the critical section appropriately. This was easy to demonstrate with the counter example, but more difficult here since the critical section will be executed less frequently (only when a factor is found). I was able to force a race condition on code that did not have proper locks by using a sufficiently large factorial with 128 threads.

Analyzing the Speedup

In the file timing.md, report the results of some timing analysis. The extension .md indicates that this is a Markdown file. You can edit this file in any text editor. Feel free to use Markdown features if you wish, but it is not required. There is a Markdown guide under the “Guides” section of this site.

The point of using multiple threads in this program is to speed up the computation. In order to see a speedup with multiple threads in your VM, you will need to make sure your VM has access to multiple CPU cores. To do this, right click on the VM in the VirtualBox Manager, then go to Settings, click the System section on the left, then go to the Processor tab. Move the Processor(s) slider so that you give the VM the maximum possible number of CPUs. You may need to shutdown the VM and start it again if you change this.

You can verify that your VM has access to multiple CPUs by running the nproc command, which will print the number of processors.

Time the execution of your program with different numbers of threads using the time command. Use a fixed \(n\) and record results for 1, 2, 4, 8, and 16 threads. Make \(n\) large enough that your fastest time is significant (at least a few seconds). Here is some example output using time for an \(n\) that is too small:

$ time ./perfect 122 4
Factors of 122:
61
1
2
122 is not a perfect number
./perfect 122 4  0.00s user 0.00s system 86% cpu 0.002 total

Depending on your system and your shell, you may see different output that looks like this:

$ time ./perfect 122 4
Factors of 122:
1
2
61
122 is not a perfect number

real    0m0.002s
user    0m0.000s
sys     0m0.000s

If your output looks like the first case, you want to record the total time (0.002 seconds here, this \(n\) was too small!). If your output looks like the second case, you want to record the real time. In either case, this refers to the actual amount of time between when the process was started and the process exited. The other two times refer to the amount of time spent executing in user mode, and the amount of time spent executing in kernel mode. If your threads are properly running concurrently, the user value will be greater than the total or real value because the user value is the sum of all of the time that all of the threads spent actively using the CPU in user mode.

In timing.md place your results as well as a paragraph discussing the results. Make sure you include the number of processors your VM is using in your discussion.

Requirements

For full credit you must follow the specifications laid out above, as well as the following:

• Use the pthread library for your threads and mutexes.
• Use unsigned long long to store \(n\) and the factors so that your program will work with larger numbers. There is a function strtoull() which can convert a string to an unsigned long long. It works differently than atoi() so you will need to look up the documentation. %llu is the printf() format specifier for unsigned long long.

Submission

The main motivation for this assignment is that you properly implement this with multiple threads. Since there is not a good way for me to check that automatically with git-keeper, this project will be collected through git-keeper but graded manually.