CS245
Homework 6
Overview
In this assignment you will work with a partner. The task is to produce two programs that do exactly the same thing (in slightly different ways.)
One version in Go and the other using Rust. Then, based on your experience with the
programs answer the questions posed at the end of the assignment. I imagine that you will do the following:
- Find a partner
- With your partner, sketch out program flow for the Go and Rust programs.
- Split work, one person do the program in Go, the other in Rust (Alternately you could use
paired programming. If you do this, I highly encourage you to switch off the person who is typing and the
person who is thinking / researching.)
- Answer the summary questions.
You are not required to work with a partner. If you do not, then you must write the program in Rust. There is a special set of summary questions a for people working solo. You should answer only those questions.
S Perfect numbers
According to Wikipedia "in number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number." All of that you know from an assignment earlier in the semester. In this assignment you will actually write a program to find "S Perfect" numbers (and numbers very close to "S Perfect").
The set "S" consists of all integers such that the sum their factors that are in the S set -- call these S-factors -- is less than or equal to the number. (Exclude the number itself when considering factors.) For example, the smallest number NOT is S is 12, because its S-factors are {1,2,3,4,6} which sum to 16 which is greater than 12.
An "S-Perfect number" is a number whose S-factors sum to itself. S-Perfect numbers are more common than Perfect numbers, but they are still rare (Perfect numbers are a subset of S-Perfect numbers). Here are all S-perfect numbers less than 1,000,000,000
[6, 24, 28, 96, 126, 224, 384, 496, 1536, 1792, 6144, 8128, 14336, 15872, 24576, 98304, 114688, 393216, 507904, 917504, 1040384, 1572864, 5540590, 6291456, 7340032, 9078520, 16252928, 22528935, 25165824, 33550336, 56918394, 58720256, 100663296, 133169152, 246650552, 402653184, 469762048, 520093696]
Here is a C program to find S-Perfect numbers.
#include
#include
#define MAX_SIZE_SSET 1000000
int main(int argc, char* argv[]) {
int Sset[MAX_SIZE_SSET] ;
int Ssetsize = 1;
Sset[0] = 1 ;
for(int n = 2; n < MAX_SIZE_SSET; n++) {
int dsum = 0 ;
for(int i = 0; i < Ssetsize; i++) {
if( n % Sset[i] == 0 && Sset[i] < n) dsum += Sset[i] ;
if (dsum > n || Sset[i] >= n) break ;
}
if(dsum <= n) {
if(dsum == n) printf("%d %d\n", n, Ssetsize) ;
Sset[Ssetsize++ ] = n ;
}
}
}
Note that in order to find S-Perfect numbers you must build up the S set along the way. This C program is limited by the size of stack memory; your program should not be so limited. (As an aside, there are far more integers in S than not in S.)
If you are interested, an executable for this is available at
/home/gtowell/bin/sperfect
This C program is correct; it works; but it is slow. It runs in O(n2) time.
Task 0
Find a partner.
Send the names of the two people in your group to gtowell@brynmawr.edu.
Actual Task
Write programs in Rust and Go that run with multiple threads to find S-Perfect, and close to S-Perfect, numbers. Your program need not be super efficient -- a brute force approach as exemplified by the C program above that runs in O(n2) time is OK. Even better (and worth extra credit), would be code that runs in O(n * n0.5) time; still brute force but a lot faster.
Parallelization Suggestion
Two properties of this problem render it tractable for parallelization. First, to compute whether a number N is in S (or is S-Perfect) it seems like you need to know all of the elements of S that are less than N. This is not true. You only need to know all of the elements of S that are less than (N+1)/2. Second, let H(N) be the difficulty of computing whether a number N is in S (or is S-Perfect). Then for any number M>N, H(M)>=H(N). As a result, it takes less time to compute all the members of S in the range 10,000-20,000 than it does to compute all of the members of S in the range 20,000-30,000. (and so forth)
Program Requirements
- Your programs should take one argument from the command line, namely the maximum number to consider in your search for perfect numbers
- You programs should, in addition to finding S-Perfect numbers, find all numbers that are within 7 of being S-Perfect. (That is, the absolute value of sum of the S-factors of a number minus the number itself should be less than or equal to 7).
- Your programs must be multi-threaded. The machines in the labs all have 8 processors. Use all 8.
- Your Go program should use shared memory for communication between the threads.
- Your Rust program should use message passing for thread communications
- Both versions of the program should use at least 8 threads.
- No more than 9 threads (including the main thread) should be active at any time.
- The work should be parcelled into small chunks. For instance, if you were only doing to 1000, then the chunk size might be 20. Hence, there would be 50 parcels of work. Whether you use one thread per parcel or 8 threads each of which can do more than one parcel is up to you.
- If it is convenient, you can start the program single threaded to compute the first part of the problem. Because of the way the difficulty grows, the first 1% of the numbers may take less than 0.01% of the CPU time.
- After finishing searching all numbers for S perfection (up to the given max) you program should print a table similar to the following:
Deficient (in S)
-7 --> [50]
-6 --> [7 15 52 54 132 315 592 1155]
-5 --> [9]
-4 --> [5 14 44 110 152 884 2144 6700 8384]
-3 --> [100 4624 7560]
-2 --> [3 10 136 5796]
-1 --> [2 4 8 16 32 64 128 256 512 1024 2048 4096 8192]
Perfect (in S)
0 --> [6 24 28 96 126 224 384 496 1536 1792 6144 8128]
Abundant (Not in S)
1 --> []
2 --> [20 84 104 464 650 780 1488 1952]
3 --> [18]
4 --> [12 70 88 1888 4030 5264 5830]
5 --> []
6 --> [80 90 8925]
7 --> [196]
- Use the UNIX time function to determine the speedup from parallelization for both your Go and Rust programs. This is very easy to use, just stick the word "time" in front of your program. For instance:
time go run perfect.go > p.out
real 8m55.397s
user 71m1.982s
sys 0m1.907s
This shows that my program used about 71 CPU minutes in about 9 clock minutes. That is a speedup of about 7.9 times (on an 8 core machine in the lab).
Before starting any run, make sure than no one else is using the lab machine for their run. To do this log into the a lab machine and execute the Unix "uptime" command. The numbers after "load average" should all be near zero.
- Report your speedup(s) in your readme file for a run (of both your Go program and Rust program) that takes somewhere between 5 minutes and 60 minutes. How many S-Perfect numbers you find is not important, your speedup is. You should certainly exceed 7, and preferably get close to 8.
Show the output of this "short" runs (both Go and Rust) of your program for finding S-Perfect numbers in the Readme file.
- Do a multi-hour (at least 8 hours) test of you perfect number finder on a lab machine: preferably do it overnight. (Penalties may be assessed for being a bad sharer; for instance using all 8 cores on a machine during a scheduled lab time.) Show the output of your programs from multi-hour run along with the time stats from the Unix "time" function. Put these results in your readme also. You only need to do one overnight run.
The Unix nohup command (short for "no hangup") will help you a lot in this effort; its use means that your program will not stop running when the terminal closes. For instance, the following might start a long run of my go program
nohup go run sperfect.go 1000000000 &
(The '&' at the end is intentional and important.)
The number that you program can achieve may be much smaller.
My recent experience is that you should not combine nohup with time. At least when running my rust executable, that combination causes the process to be killed after about 45 minutes of run time. So do not do the following:
nohup time rustExecutable 1000000000 &
Using nohup also requires some responsibility on your part as you could accidentally leave a program running on every CPU of a machine for several days. Find me if you run into this problem lest I assess penalties for being a bad sharer.
To determine if you program is being a "bad sharer", you might start by looking at my page showing machine availability. If you see the machine you are running your program on has an 8 in one of the usage columns and it is the middle of the day, then you might have a problem. To fix this problem (ie kill the running program)
- Log into the machine
- execute the Unix command "top". In the resulting listing, find the line with your id and a process that is about 800 in the %CPU column. (It is usually the topmost entry.)
- Note down the number in the PID column.
- Quit top by hitting 'q'.
- Enter the Unix command "kill -9 PID" where you replace PID with the number you noted in step 3
Questions
Once you complete your programs, write answers to the following questions. Please note that I am often
asking you for opinions; so correctness is not an issue. Rather I am looking for well-thought statements based
on you experience with writing these programs. Also, in all cases the portion of the response that address why is far
more important than the part that address what. (For instance, suppose each response is worth 10 points, then what
is worth no more than 1 or 2 points, why no less than 8 or 9.)
Questions for people who worked in pairs
- Overall, which version of the was easier / harder to write? why? (Try to correct for exogenous factors like
"We wrote the Go version first".)
- Which program ran faster (assuming you compiled the rsut program fro release)? Can you account for the speed difference? How?
- What about each language helped / hindered with task? This is about
features of the language itself. Explain.
- I assert that message passing is slightly more difficult to implement, but much more flexible than shared memory". Do you agree? Explain.
- Code readability / modifiability. Suppose in the next assignment you needed to adapt the program you wrote
here. Which version would you think would be easier to adapt? Why?
- Did you prefer message passing or shared memory for communications. Why?
Questions for people who worked Individually
- What features of the language made it particularly easy or hard to write this program. Explain
- I assert that message passing is slightly more difficult to implement, but much more flexible than shared memory". Do you agree? Explain.
- What features of the problem made it particularly well suited (or ill suited) to multi-threading? An in particular, for message passing?
- Code readability / modifiability. Suppose in the next assignment you needed to adapt the program you wrote
here. What features of message passing would make this adaptation easy ... or hard?
Electronic Submissions
Your submission will be handed in using the submit script.
If you write your program on computers other than those in the lab, be aware that your program will be
graded based on how it runs on the
department’s Linux server, not how it runs on your computer. The most likely problem is not
submitting everything or hard coding file locations that are not correct on the Linux servers.
The submission should include the following items:
- README:
- This file should follow the format of this sample README
-
- Names of both people in a group. You need only submit once.
- Source files
- All of them (you might have only one)
- Data files used:
- Be sure to include any non-standard data files uses. (Rare)
-
DO NOT INCLUDE:
- Data files that are read from the class site. Do include any of your own data files.
Again: Once you have everything you want to submit in the a6 directory within /home/YOU/cs245/
- Go to the directory /home/YOU/cs245
- Enter /home/gtowell/bin/submit -c 245 -p 6 -d a6
If this worked you will get a message with the word "success". If you cannot achieve success and the deadline is
approaching, send me email. We can set up a meeting to work out your problems. The email will establish that you
intended to submit. Once you send the email, do not change the files that you were trying to submit.