Computation of prime numbers on Master/Slaves architecture
One method to determine prime numbers in a given interval is to divide the search space into several subintervals and to assign the search task in each subinterval to a process created by the father process. Thus, if we divide the interval [1, N] into p subintervals, the father process creates p children and each child k searches in the interval [k*N/p + 1, (k+1) N/p], k = 0,…, p – 1. This technique can be used on parallel machines composed of p processers where each subinterval is assigned to one of the p processors. Parallel computation allows us to reduce the execution time. However, this technique has the drawback of assigning unbalanced computation load to the different processes. Thus, process 0 finishes the search on its assigned [1, N/p] interval, earlier than the process p-1. Therefore, this technique does not allow us to benefit from the parallelism in an optimal way.
One solution (that you should implement) to balance the load of different processes is to create a pool of p processes and to assign successively small intervals of size T <<N/p to the processes. When a child process finishes it assigned task, the father assign to it a new interval not yet explored.
Solution hints
· The master is the father process and the p slaves are the children processes.
· The father process uses p pipes to communicate with its children. However, all the children processes use the same tube to communicate with the father process.
· The communication protocol is the following:
o Father -> child: two integers representing the interval
o Child -> father: each found prime number in its assigned interval (0 is sent to inform the father that the child has finished). The child precedes each sent prime number by its identifier.
· When the whole interval is checked, the father kills all slaves using signals.
· The interval and the number of slaves are passed to the father process as command-line arguments.