1. Forum
  2. Usenet
  3. COMP.LANG.ADA

  • Parallel Sieve Of Eratosthenes

    From Lawrence D'Oliveiro@21:1/5 to All on Sun Jun 30 08:06:35 2024
    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;

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Lawrence D'Oliveiro@21:1/5 to All on Sun Jun 30 08:10:06 2024
    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;

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From J-P. Rosen@21:1/5 to All on Sun Jun 30 18:36:45 2024
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Lawrence D'Oliveiro@21:1/5 to J-P. Rosen on Mon Jul 1 00:02:59 2024
    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;

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From J-P. Rosen@21:1/5 to All on Mon Jul 1 11:17:09 2024
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Lawrence D'Oliveiro@21:1/5 to J-P. Rosen on Mon Jul 1 21:48:06 2024
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)