* Parallel Sieve Of Eratosthenes
@ 2024-06-30 8:06 Lawrence D'Oliveiro
2024-06-30 8:10 ` Lawrence D'Oliveiro
0 siblings, 1 reply; 6+ messages in thread
From: Lawrence D'Oliveiro @ 2024-06-30 8:06 UTC (permalink / raw)
with Ada.Text_IO;
use Ada;
procedure parasieve1 is
task type child is
entry next_int(i : integer);
end child;
subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type
task body child is
my_prime : integer;
subchild : access offspring;
begin
accept next_int(i : integer) do
my_prime := i;
Text_IO.Put_line(integer'image(my_prime));
end next_int;
subchild := new offspring;
loop
accept next_int(i : integer) do
if i mod my_prime /= 0 then
subchild.next_int(i);
end if;
end next_int;
end loop;
end child;
first_child : child;
i : integer;
begin -- parasieve1
i := 1;
loop
i := i + 1;
first_child.next_int(i);
end loop;
end parasieve1;
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Parallel Sieve Of Eratosthenes
2024-06-30 8:06 Parallel Sieve Of Eratosthenes Lawrence D'Oliveiro
@ 2024-06-30 8:10 ` Lawrence D'Oliveiro
2024-06-30 16:36 ` J-P. Rosen
0 siblings, 1 reply; 6+ messages in thread
From: Lawrence D'Oliveiro @ 2024-06-30 8:10 UTC (permalink / raw)
This version uses a protected type to pass the stream of integers from
one task to the next. It seems to be much faster.
----
with Ada.Text_IO;
use Ada;
procedure parasieve2 is
protected type int_buffer is
entry put(i : in integer);
entry get(i : out integer);
private
last_i : integer;
got_i : boolean := false;
end int_buffer;
protected body int_buffer is
entry put(i : in integer) when not got_i is
begin
last_i := i;
got_i := true;
end put;
entry get(i : out integer) when got_i is
begin
i := last_i;
got_i := false;
end get;
end int_buffer;
type int_buffer_ptr is access int_buffer;
task type child(from_parent : int_buffer_ptr) is
end child;
subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type
task body child is
my_prime, i : integer;
subchild : access offspring;
to_child : int_buffer_ptr;
begin
from_parent.get(my_prime);
Text_IO.Put_line(integer'image(my_prime));
to_child := new int_buffer;
subchild := new offspring(to_child);
loop
from_parent.get(i);
if i mod my_prime /= 0 then
to_child.put(i);
end if;
end loop;
end child;
to_first_child : int_buffer_ptr;
first_child : access child;
i : integer;
begin -- parasieve2
i := 1;
to_first_child := new int_buffer;
first_child := new child(to_first_child);
loop
i := i + 1;
to_first_child.put(i);
end loop;
end parasieve2;
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Parallel Sieve Of Eratosthenes
2024-06-30 8:10 ` Lawrence D'Oliveiro
@ 2024-06-30 16:36 ` J-P. Rosen
2024-07-01 0:02 ` Lawrence D'Oliveiro
0 siblings, 1 reply; 6+ messages in thread
From: J-P. Rosen @ 2024-06-30 16:36 UTC (permalink / raw)
Le 30/06/2024 à 10:10, Lawrence D'Oliveiro a écrit :
> This version uses a protected type to pass the stream of integers from
> one task to the next. It seems to be much faster.
That's because in your first version, you call the child within the
accept statement. Therefore you wait for the value to go to the end of
the pipeline before processing the next value.
Try to copy the number to a variable, and call the child after the end
of the accept. This will give you 100% CPU time usage.
BTW, you don't need an access type. Just use a declare block to create
the child after the first accept.
--
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
https://www.adalog.fr https://www.adacontrol.fr
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Parallel Sieve Of Eratosthenes
2024-06-30 16:36 ` J-P. Rosen
@ 2024-07-01 0:02 ` Lawrence D'Oliveiro
2024-07-01 9:17 ` J-P. Rosen
0 siblings, 1 reply; 6+ messages in thread
From: Lawrence D'Oliveiro @ 2024-07-01 0:02 UTC (permalink / raw)
On Sun, 30 Jun 2024 18:36:45 +0200, J-P. Rosen wrote:
> That's because in your first version, you call the child within the
> accept statement. Therefore you wait for the value to go to the end of
> the pipeline before processing the next value.
> Try to copy the number to a variable, and call the child after the end
> of the accept. This will give you 100% CPU time usage.
>
> BTW, you don't need an access type. Just use a declare block to create
> the child after the first accept.
Thanks for the comments, how about this slight rework of the first
version. It does seem faster, but I’m not sure it’s as fast as the second
version.
----
with Ada.Text_IO;
use Ada;
procedure parasieve1b is
task type child is
entry next_int(i : integer);
end child;
subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type
task body child is
my_prime : integer;
begin
accept next_int(i : integer) do
my_prime := i;
Text_IO.Put_line(integer'image(my_prime));
end next_int;
declare
subchild : offspring;
ii : integer;
begin
loop
accept next_int(i : integer) do
if i mod my_prime /= 0 then
ii := i;
else
ii := 0;
end if;
end next_int;
if ii /= 0 then
subchild.next_int(ii);
end if;
end loop;
end;
end child;
first_child : child;
i : integer;
begin -- parasieve1b
i := 1;
loop
i := i + 1;
first_child.next_int(i);
end loop;
end parasieve1b;
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Parallel Sieve Of Eratosthenes
2024-07-01 0:02 ` Lawrence D'Oliveiro
@ 2024-07-01 9:17 ` J-P. Rosen
2024-07-01 21:48 ` Lawrence D'Oliveiro
0 siblings, 1 reply; 6+ messages in thread
From: J-P. Rosen @ 2024-07-01 9:17 UTC (permalink / raw)
Le 01/07/2024 à 02:02, Lawrence D'Oliveiro a écrit :
> On Sun, 30 Jun 2024 18:36:45 +0200, J-P. Rosen wrote:
>
>> That's because in your first version, you call the child within the
>> accept statement. Therefore you wait for the value to go to the end of
>> the pipeline before processing the next value.
>> Try to copy the number to a variable, and call the child after the end
>> of the accept. This will give you 100% CPU time usage.
>>
>> BTW, you don't need an access type. Just use a declare block to create
>> the child after the first accept.
>
> Thanks for the comments, how about this slight rework of the first
> version. It does seem faster, but I’m not sure it’s as fast as the second
> version.
That's better, but as a general principle, you should move as much as
you can out of the rendezvous (minimize critical sequences). For example:
accept next_int(i : integer) do
my_prime := i;
end next_int;
Text_IO.Put_line(integer'image(my_prime)); -- moved
declare
subchild : offspring;
ii : integer;
begin
loop
accept next_int(i : integer) do
ii := i;
end next_int;
if ii mod my_prime /= 0 then --moved
subchild.next_int(ii);
end if;
end loop;
--
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
https://www.adalog.fr https://www.adacontrol.fr
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Parallel Sieve Of Eratosthenes
2024-07-01 9:17 ` J-P. Rosen
@ 2024-07-01 21:48 ` Lawrence D'Oliveiro
0 siblings, 0 replies; 6+ messages in thread
From: Lawrence D'Oliveiro @ 2024-07-01 21:48 UTC (permalink / raw)
On Mon, 1 Jul 2024 11:17:09 +0200, J-P. Rosen wrote:
> That's better, but as a general principle, you should move as much as
> you can out of the rendezvous (minimize critical sequences).
Still, it looks like protected types are the way to go.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2024-07-01 21:48 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-06-30 8:06 Parallel Sieve Of Eratosthenes Lawrence D'Oliveiro
2024-06-30 8:10 ` Lawrence D'Oliveiro
2024-06-30 16:36 ` J-P. Rosen
2024-07-01 0:02 ` Lawrence D'Oliveiro
2024-07-01 9:17 ` J-P. Rosen
2024-07-01 21:48 ` Lawrence D'Oliveiro
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox