Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #21965

Parallel bubble-sort

Show all headers | View raw

Here is a parallel bubblesort, derived from the Pascal prototype. 

The paper claims linear complexity for infinitely many cores. 
They may have neglected to do a little testing.

With four cores I get a speedup of slightly more than two times
(from 9.5 to 4.4 seconds on an i7 920 @2.67 GHz).

Of course Quicksort will beat this, unless run on a very good 
Transputer box (The GA144 may do if there's sufficient memory).

-marcel

-- ------------------------------
ANEW -psorts

DOC
(*
  Parallel Bubble Sort
  Felician ALECU
  Economic Informatics Department, A.S.E. Bucharest
  alecu.ase.ro/conferences/nat_conf_2005_ro_am.pdf
*)
ENDDOC

VARIABLE unsorted?
$10000 CONSTANT n
CREATE array  n CELLS ALLOT

: INIT-ARRAY  ( -- )  n    0 ?DO  RANDOM array I CELLS + !  LOOP ;
: ?SORTED     ( -- )  n 1- 0 ?DO  array I CELLS + 2@ < ABORT" unsorted"  LOOP ;

: exchange ( addr -- ) DUP 2@ SWAP ROT 2! ;

: exchange? ( bool1 ix -- bool2 ) 
	array SWAP CELLS + ( -- addr )
	DUP 2@ < IF  exchange DROP 1  ELSE  DROP  ENDIF ;

: signal ( u -- ) unsorted? LOCKED+! DROP ;
: job1 ( bool up down -- ) DO  I 2*     exchange?  LOOP signal ;
: job2 ( bool up down -- ) DO  I 2* 1+  exchange?  LOOP signal ;

: Serial_BubbleSort ( -- )
	INIT-ARRAY
	BEGIN
	   unsorted? OFF 
		0  n 2/                0 job1
		0  n 2/  n 1 AND + 1-  0 job2
	   unsorted? @ FALSE =
	UNTIL ?SORTED ;

: Parallel_BubbleSort ( -- )
	INIT-ARRAY
	BEGIN
	   unsorted? OFF 
		PAR
		  STARTP  0  n 8 /               	    0 job1  ENDP
		  STARTP  0  n 4 /          		n 8 / job1  ENDP
		  STARTP  0  n 3 8 */     		n 4 / job1  ENDP
		  STARTP  0  n 2/         	     n 3 8 */ job1  ENDP
		ENDPAR
		PAR
		  STARTP  0  n 8 /		    	    0 job2  ENDP
		  STARTP  0  n 4 /			n 8 / job2  ENDP
		  STARTP  0  n 3 8 */              	n 4 / job2  ENDP
		  STARTP  0  n 2/  n 1 AND + 1-      n 3 8 */ job2  ENDP
		ENDPAR	
	   unsorted? @ FALSE =
	UNTIL ?SORTED ;

: BENCH ( -- )
	CR ." \ Sorting " n U. ." numbers." 
	CR ." \ serial   : " TIMER-RESET   Serial_BubbleSort .ELAPSED
	CR ." \ parallel : " TIMER-RESET Parallel_BubbleSort .ELAPSED ;

\ FORTH> bench
\ Sorting 65536 numbers.
\ serial   : 9.513 seconds elapsed.
\ parallel : 4.362 seconds elapsed.

\ EOF

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar

Thread

Parallel bubble-sort mhx@iae.nl (Marcel Hendrix) - 2013-04-28 01:29 +0200
  Re: Parallel bubble-sort mhx@iae.nl (Marcel Hendrix) - 2013-04-28 22:56 +0200
  Re: Parallel bubble-sort fred <email@address.com> - 2013-04-29 13:08 +0100
    Re: Parallel bubble-sort m.a.m.hendrix@tue.nl - 2013-04-29 06:44 -0700

csiph-web