Parallel Sieve of Eratosthenes

Discussion in 'NZ Computing' started by Lawrence D'Oliveiro, Nov 14, 2009.

  1. In Algol 68. The parent thread spits out a sequence of integers. Each child
    thread takes the first integer it’s given as a prime, outputs it as such,
    spawns its own child, and passes it all subsequent integers that are not
    multiples of that first one.

    Note the PAR clauses for parallel execution of the constituent statements.
    Also note the use of semaphores (nowadays considered too low-level and
    error-prone) for synchronizing access to the buffers.

    ----
    MODE BUFFER = STRUCT
    (
    SEMA full,
    SEMA empty,
    REF INT n
    );

    PROC produce = (BUFFER b, INT n) VOID :
    BEGIN
    DOWN empty OF b;
    n OF b := n;
    UP full OF b
    END;

    PROC consume = (BUFFER b) INT :
    BEGIN
    DOWN full OF b;
    INT n = n OF b;
    UP empty OF b;
    n
    END;

    PROC sieve = (BUFFER b1) VOID :
    BEGIN
    INT n = consume(b1);
    print((" => ", n, new line));
    BUFFER b2 = (LEVEL 0, LEVEL 1, HEAP INT);
    PAR BEGIN
    DO
    INT i = consume(b1);
    IF i MOD n /= 0 THEN
    produce(b2, i)
    FI
    OD,
    sieve(b2)
    END
    END;


    BEGIN
    BUFFER b = (LEVEL 0, LEVEL 1, HEAP INT);
    INT n := 1;
    PAR BEGIN
    DO
    n := n + 1;
    produce(b, n)
    OD,
    sieve(b)
    END
    END
     
    Lawrence D'Oliveiro, Nov 14, 2009
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Silverstrand

    How To Build Parallel Port Prototypes

    Silverstrand, Oct 14, 2005, in forum: Front Page News
    Replies:
    1
    Views:
    877
    unholy
    Oct 14, 2005
  2. Ex Ronny
    Replies:
    1
    Views:
    537
    Robert B. Phillips II
    Nov 5, 2004
  3. Lawrence D¹Oliveiro

    Parallel Sieve of Eratosthenes in Bash

    Lawrence D¹Oliveiro, Oct 2, 2004, in forum: NZ Computing
    Replies:
    1
    Views:
    423
    Harry
    Oct 2, 2004
  4. Lawrence D'Oliveiro

    sieve.py

    Lawrence D'Oliveiro, Sep 30, 2005, in forum: NZ Computing
    Replies:
    0
    Views:
    510
    Lawrence D'Oliveiro
    Sep 30, 2005
  5. Lawrence D'Oliveiro

    Adobe Reader Leaks Like A Sieve

    Lawrence D'Oliveiro, Aug 7, 2009, in forum: NZ Computing
    Replies:
    2
    Views:
    339
    Lawrence D'Oliveiro
    Aug 8, 2009
Loading...

Share This Page