From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=ham autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,70248dce89939ca0
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2003-12-28 09:52:34 PST
Path: 
 archiver1.google.com!news2.google.com!newsfeed2.dallas1.level3.net!news.level3.com!crtntx1-snh1.gtei.net!news.gtei.net!newsfeed1.easynews.com!easynews.com!easynews!small1.nntp.aus1.giganews.com!border3.nntp.aus1.giganews.com!intern1.nntp.aus1.giganews.com!nntp.giganews.com!nntp.comcast.com!news.comcast.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 28 Dec 2003 11:52:33 -0600
Date: Sun, 28 Dec 2003 12:52:32 -0500
From: "Robert I. Eachus" <rieachus@comcast.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:1.4) Gecko/20030624 Netscape/7.1 (ax)
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: parallel computing of prime numbers
References: <bsmiuj$5k7$1@news2.netvision.net.il>
In-Reply-To: <bsmiuj$5k7$1@news2.netvision.net.il>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ReOdnWlGvpL8hXKiRVn-jg@comcast.com>
NNTP-Posting-Host: 24.34.214.193
X-Trace: 
 sv3-THlYm8oshxpoPAy4UDSKoqS9O9h0bxPgXAPvWXafnbv9ecREEroAc2UXjRTUyEoe3KFDKCtKLCGttfI!LQYzD33JB9acsVQAqEbiQGKZD1lQpuV7PjJblWGJRMJl2xjwK4Ll7BdbLGf/AQ==
X-Complaints-To: abuse@comcast.net
X-DMCA-Complaints-To: dmca@comcast.net
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint
 properly
X-Postfilter: 1.1
Xref: archiver1.google.com comp.lang.ada:3892
Date: 2003-12-28T12:52:32-05:00
List-Id: <comp.lang.ada>

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