CS245

Homework 6

Overview

1. Find a partner
2. With your partner, sketch out program flow for the Go and Rust programs.
3. 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.)
4. Answer the summary questions.

S Perfect numbers

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 ;
                }
              }
        }
    

        /home/gtowell/bin/sperfect
    

Task 0

Send the names of the two people in your group to gtowell@brynmawr.edu.

Actual Task

Parallelization Suggestion

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)
  1. Log into the machine
  2. 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.)
  3. Note down the number in the PID column.
  4. Quit top by hitting 'q'.
  5. Enter the Unix command "kill -9 PID" where you replace PID with the number you noted in step 3

Questions

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/

1. Go to the directory /home/YOU/cs245
2. Enter /home/gtowell/bin/submit -c 245 -p 6 -d a6