Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Computing > NZ Computing > Parallel Sieve of Eratosthenes

Reply
Thread Tools

Parallel Sieve of Eratosthenes

 
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      11-14-2009
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parallel Sieve Of Eratosthenes Lawrence D'Oliveiro NZ Computing 2 12-18-2009 10:11 PM
Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ) jzakiya Python 3 07-19-2008 07:39 PM
Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ) jzakiya C Programming 4 06-13-2008 10:56 PM
Remarkable results with psyco and sieve of Eratosthenes Steve Bergman Python 15 11-30-2006 09:14 PM
Parallel Sieve of Eratosthenes in Bash Lawrence DOliveiro NZ Computing 1 10-02-2004 09:51 AM



Advertisments