Erlang Programming/Parallel Programming

Prime Sieve (parallel with linda type coordination)

Linda is a way to coordinate the actions of multiple processors. A tuplespace is created for the candidate primes to live. The sieve processes are created and send messages to the tuplespace to remove non-primes. The sieve processes also send messages to each others to remove the non-prime sieves.

How many processors can this program use? This program creates as many sieves as the square root of the numbers in the matrix (tuplespace). If we are looking for the primes below 100 then there are about 10 parallel sieve processes. Actually, most of the sieve processes are halted and only (the number of prime numbers under the square root of Max) processes are left at the end. This allows an easy parallelism of 10 for 100 and 100 for 10000 with little modification.

In Erlang, it is not recommended that one use a huge number of atoms, so N should not get too large. We also might run out of processes or memory.

This program breaks one of the general rules of Erlang process management: do not use peer managers. Each of the sieve processes is a peer manager because each sieve may halt any other sieve. Rather, processes should be managed in a top-down tree structure. The peer management of the sieves causes some nasty timing issues. Timing is one reason why peers are usually a bad idea.

When the sieve for 2 ends, the list of primes is dumped. Erlang should give each process equal CPU time. When the slices are even, the sieve for 2 starts first and ends last. When some other sieve is starved for time, it may end after sieve 2 and the prime number dump will be too early, leaving some numbers divisible by 2 in the list of putative primes. Relative starvation of some process happens about 1 out of 10 times. Clearly the critical word should be: "tries". "Erlang TRIES to give each process equal time slices."

Does it hurt to have non-prime sieves running? We can use a 6-sieve. A 6-sieve is redundant because the 2-sieve and the 3-sieve remove all numbers that the 6-sieve would remove. By removing the 6-sieve and its non-prime sieve brothers we reduce the number of messages that the matrix must handle thereby speeding the final result.

Prime Sieve Program (parallel)

   -module(primes).

   % This is a simple linda tuplespace. Here we use it to find primes numbers.
   % This tuplespace cannot have duplicate tuples, but with a prime sieve it does
   % not matter.

   -compile(export_all).

   start() -> start(100).  % default value for max is 100
   start(Max) -> 
       io:format("  Loading ~w numbers into matrix (+N) \n ", [ Max ] ),
       Lid = spawn_link( primes, linda, [Max, [], [] ]),
       Sqrt = round(math:sqrt(Max)+0.5),  
       io:format(" Sqrt(~w) + 1 = ~w \n " , [Max,Sqrt] ),  
       io:format(" Tuple space is started ~n ",[]),  
       io:format(" ~w sieves are spawning (+PN) ~n ", [Sqrt] ),
       io:format(" Non prime sieves are being halted (-PN) ~n ", [] ),
       % load numbers into tuplespace 
       % and spawn sieve process
       spawn( primes, put_it, [Max, Max, Lid] ).

   start_sieves(Lid) ->
       Lid ! {self(), get, all, pids},  
       receive 
           {lindagram, pids, Pids} -> done
       end,
       start_sieve_loop(Pids).

   start_sieve_loop([]) -> done;
   start_sieve_loop([Pid|Pids]) ->
       receive
       after 100 -> done
       end,
       Pid ! {start},
       start_sieve_loop(Pids).

   spawn_sieves( _Max, Sqrt, _Lid, Sqrt ) -> done;  
   spawn_sieves( Max, Inc, Lid, Sqrt ) ->
       T = 1000,
       Pid = spawn( primes, sieve, [ Max, Inc+Inc, Inc, Lid, T ]),
       Name = list_to_atom("P" ++ integer_to_list(Inc)),
       Lid ! {put, pid, Name},
       register( Name, Pid),
       io:format(" +~s ", [atom_to_list(Name)]),
       spawn_sieves( Max, Inc+1, Lid, Sqrt ).

   put_it(Max, N, Lid) when N =< 1 ->
       Sqrt = round(math:sqrt(Max)+0.5),
       spawn_sieves( Max, 2, Lid, Sqrt );  

   put_it(Max, N,Lid) when N > 1 ->
       receive
       after 0 ->
           Lid ! {put, N, N},
           if 
               N rem 1000 == 0 ->
                   io:format(" +~w ", [N]);
               true -> done
           end,
           put_it(Max, N-1,Lid)
       end.

   % the 2 sieve starts last and has the most to do so it finishes last
   sieve(Max, N, 2, Lid, _T) when N > Max -> 
       io:format("final sieve ~w done, ~n", [2] ),
       Lid ! {dump,output};

   sieve(Max, N, Inc, _Lid, _T) when N > Max ->    
       io:format("sieve ~w done ", [Inc] );

   sieve(Max, N, Inc, Lid, T) when N =< Max ->   
       receive 
       after 
           T -> NT = 0   
       end,
       receive 
           {lindagram,Number} when Number =/= undefined -> 
               clearing_the_queue;
           {exit} -> exit(normal)
       after
           1 -> done 
       end,

       % remove multiple of number from tuple-space
       Lid ! {self(), get, N},
       Some_time = (N rem 1000)==0,
       if Some_time -> io:format("."); true -> done end,

       % remove (multiple of Inc) from sieve-process space
       Name = list_to_atom("P" ++ integer_to_list(N)),
       Exists = lists:member( Name, registered()),
       if 
           Exists ->
               Name ! {exit},
               io:format(" -~s ", [atom_to_list(Name)] );
           true -> done
       end,
       sieve(Max, N+Inc, Inc, Lid, NT).        % next multiple
        
   %% linda is a simple tutple space 
   %%    if it receives no messages for 2 whole seconds it dumps its contents 
   %%    as output and halts

   linda(Max, Keys, Pids) ->
       receive
       {put, pid, Pid} ->
           linda(Max, Keys, Pids++[Pid]);
       {put, Name, Value} ->
           put( Name, Value),
           linda(Max, Keys++[Name], Pids);
       {From, get, Name} ->
           From ! {lindagram, get( Name)},
           erase( Name ),                          % get is a destructive read  
           linda(Max, Keys--[Name],Pids);
       {From, get, all, pids} ->
           From ! {lindagram, pids, Pids},
           linda(Max, Keys, Pids );
       {From, get, pid, Pid} ->
           L1 = length( Pids ),
           L2 = length( Pids -- [Pid]),
           if 
               L1 > L2 ->  % if it exists
                   From ! {lindagram, pid, Pid};
               true -> 
                   From ! {lindagram, pid, undefined}
           end,
           linda(Max, Keys, Pids );
       {dump,output} ->
           io:format(" ~w final primes remain: ~w ~n ", [length(Keys),  lists:sort(Keys) ])
       after (100*Max) -> % if there is not tuple action after some time then print the results
           io:format(" ~w primes remain: ~w ~n ", [length(Keys),  lists:sort(Keys) ])
       end.

Sample Output for Prime Sieve

c(primes).
primes:start(1000).
 Loading 1000 numbers into matrix (+N)
 Sqrt(1000) + 1 = 32
 Tuple space is started
 32 sieves are spawning (+PN)
 Non prime sieves are being halted (-PN)
 +1000 <0.46.0>
+P2  +P3  +P4  +P5  +P6  +P7  +P8  +P9  +P10  
+P11  +P12  +P13  +P14  +P15  +P16   
+P17  +P18  +P19  +P20  +P21  +P22  +P23  +P24  
+P25  +P26  +P27  +P28  +P29  +P30  
+P31  -P8  -P6  -P4  -P9  -P12  -P10  -P15  
-P15  -P18  -P14  -P21  -P21  -P22  
-P26  -P20  -P24  -P25  -P27  -P28  -P30  -P30  -P16 
sieve 31 done sieve 29 done 
sieve 19 done sieve 23 done sieve 11 done 
sieve 13 done sieve 17 done sieve 7 done 
.sieve 5 done sieve 3 done .final sieve 2 done,
168 final primes remain: 
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,
101,103,107,109,113,127,131,137,139,149,151,157,163,
167,173,179,181,191,193,197,199,
211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,
307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,
401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,
499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,
601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,
701,709,719,727,733,739,743,751,757,761,769,773,787,797, 
809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,
907,911,919,929,937,941,947,953,967,971,977,983,991,997]