parallel computing of prime numbers

parallel computing of prime numbers

[meh]

I'd like to compute parallely primes with variable amount of tasks. I 
made a task with an entry to compute a single number's primeness and 
then looped through all tasks and assigned each task a new number to 
work on.
My problem is that the assigning command waits until the prime 
calculation ends, I want it to assign the task a number to work on and 
then CONTINUE IMMEDIATELY assigning other numbers to other tasks.
I thought of making an array of semaphore and input variables, and then 
to use them to assign numbers to tasks (I'll intialize each task with 
the relevant semaphore), but it seems very clumsy way to do things.
Pray, how can I do that in a more elegant way?

Re: parallel computing of prime numbers

[Robert I. Eachus]

meh wrote:

> I'd like to compute parallely primes with variable amount of tasks. I 
> made a task with an entry to compute a single number's primeness and 
> then looped through all tasks and assigned each task a new number to 
> work on.
> My problem is that the assigning command waits until the prime 
> calculation ends, I want it to assign the task a number to work on and 
> then CONTINUE IMMEDIATELY assigning other numbers to other tasks.
> I thought of making an array of semaphore and input variables, and then 
> to use them to assign numbers to tasks (I'll intialize each task with 
> the relevant semaphore), but it seems very clumsy way to do things.
> Pray, how can I do that in a more elegant way?


The elegant solution uses a protected object (or if you prefer a task) 
to allocate numbers to test and collect results:

protected Dispatcher is
   entry Get_Candidate(Candidate: out Number);
   procedure Success(Prime: in Number);
   procedure Shut_Down;
end Dispatcher;

Now your tasks can call Get_Candidate to get a candidate, and Success 
then Get_Candidate if successful. Something like:

task type Grinder is end Grinder; -- no entries needed.

task body Grinder is
   Candidate: Number;
begin
   loop
     Dispatcher.Get_Candidate(Candidate);
     if Prime_Test(Candidate) then Dispatcher.Success(Candidate); end if;
   end loop;
end Grinder;

Now for the magic part.  How do you shut down the tasks?  You can abort 
them if you want to stop them in mid-calculation.  Or if you have a list 
of numbers you want to test, Get_Candidate can raise an exception in its 
body that will be propagated to the task, but handled inside 
Get_Candidate.  When no tasks remain active the scope in which the tasks 
were declared may be left.  So your main program looks like:

procedure Main is
    type Number is ...; --I assume some arbitrary precision type;
    Candidate_List: array ... of Number;
    Result_List: array ... of Number; -- or you can use a boolean array
                            -- dimensioned to match the Candidate_List;
begin
    declare
      -- task type goes here.
    begin
      null; -- or maybe print number of primes found or something;
    end;
    -- Print results here.
end Main;

When the last task becomes completed, the declare block will be left, 
and you can output the results from a single thread.

If you have a lot of processors, you may want to distribute the list of 
numbers to be tested to several tasks (instead of one protected object) 
so that multiple task can recieve candidates at the same time.  But I 
expect that for interesting prime candidates, the ratio of parameter 
passing time to testing time will be small.

For example, if you wanted to test a range of integers, you might have 
eight dispatching tasks, one each for numbers of the form 30*k + 1, 30*k 
+ 3, etc.  If you do this of course, you want to associate Grinder tasks 
with particular dispatchers, and possibly have them check other 
dispatchers if their current dispatcher is exhausted.

Of course, the techniques for managing task dispatching to several 
thousand processors (and collecting results) can get complex.  But if 
that is your eventual goal, do the single dispatcher case first, then 
modify it to handle multiple dispatchers (put the main program above 
inside a task), and finally deal with the logrithmic time setup case.

-- 
                                           Robert I. Eachus

"The war on terror is a different kind of war, waged capture by capture, 
cell by cell, and victory by victory. Our security is assured by our 
perseverance and by our sure belief in the success of liberty." -- 
George W. Bush