Parallel Sieve Of Eratosthenes

Parallel Sieve Of Eratosthenes

[Lawrence D'Oliveiro]

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;

Re: Parallel Sieve Of Eratosthenes

[Lawrence D'Oliveiro]

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;

Re: Parallel Sieve Of Eratosthenes

[J-P. Rosen]

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

Re: Parallel Sieve Of Eratosthenes

[Lawrence D'Oliveiro]

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;

Re: Parallel Sieve Of Eratosthenes

[J-P. Rosen]

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

Re: Parallel Sieve Of Eratosthenes

[Lawrence D'Oliveiro]

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.