Assignment #2: Prime Factor Search

Description:

This assignment deals primarily with one of the most challenging mathematical challenges, that is to find prime factors in huge numbers. This is the basis of modern cryptography. One interesting set of numbers is the Fermat numbers for which the factors are difficult to find for. The RSA challenge numbers pose an interesting set of numbers for application of parallelism: http://www.rsasecurity.com/rsalabs/node.asp?id=2093

The algorithm used here is taken from Wikipedia, http://en.wikipedia.org/wiki/Prime_factorization. The algorithm is simple. It iteratively finds all the prime numbers between 2 and N (considering N as our large input number) and then checks whether it is prime or not. This program again does static work assignment as was in Assignment 1. When the workers find a prime number, it just prints the result on the standard output & proceeds with its computation. We also visualize the program execution & send/receive calls using MPE library. This program uses bignum package to generate large numbers as strings.

Main areas & issues explored in this assignment:

1. This is one of the uses of parallelism in solving a practical complex problem in mathematics. The question of whether more parallelism results in more work than its corresponding sequential version is an experimental question. The main issue here is not to let workers search for a possible factor in an area which is known not to have any factors from the analysis done by some other worker. How would the workers cooperate to share this knowledge will be an interesting question. Without this, increasing the number of workers could result in linear increase in more work. There is an optimum of course which can be arrived at my varying the number of workers. This program of course does not go into such detail of analysis but the assignment does give us an insight into these issues.
   Another issue here is the fact that 88% of the prime factors for any number are less than 100 and so it is necessary to split this search space (2 to 100) into more number of workers so that they may quickly search this space in parallel and the probability of finding  factor increases. It was seen after running the program that some workers unnecessarily keep searching for factors at a higher search region where the probability of finding a factor is very less. I will look into this issue if time permits at a later assignment or as an extension wok for this assignment.
2. Use of bignum to generate large numbers & send/receive them as strings.

Assignment Resources:

1. Linear program using Bignum.

2. Program that generates the input file for parallel program.

3. The generated input file

4. Parallel LAM program using big num.

5. Sample Output from the program.
   Description of the output:
   Each worker process prints its search space. UL signifies the upper limit of the search space & LL signifies the lower limit. So, every worker searches the region UL-LL. If a factor is found, the worker prints "Factor found" & then the factor.

6. MPE slog2 File

7. MPE Makefile
   Note: If you want to compile my programs using the above Makefile in UBC CS Deptt machines, replace this block in my Makefile
   ##### User configurable options #####
   bla bla bla ...
   ### End User configurable options ###
   with this block (simply copy & paste it over my original makefile, erasing the previous block).

8. MPE Visualization using Jumpshot (the number of nodes is different from sample run)
   
   Description & Observations of the visualization:
   
   The output shows the processes receiving their limits of their search space from the manager & performing computation. There are 4 worker processes (1-4) and one manager process (marked 0). Since there is no processor reuse, once each of the workers complete their computation, they again keep waiting to receive more messages from the manager. This is a big draw back of the program. Somehow, dynamic load balancing & processor reuse has to be implemented within the algorithm for a better performance. The processing times should overlap between the worker processes. in the visualization, somehow this has not been shown to be occurring. There is no limitation on the algorithm side though that would prevent this from happening.

First posted: Jan 23rd 2006. Last updated: Feb 7th 2006 Credits: 10

Page Last Revised:Monday March 31, 2008