Re: Parallel FIB

From	mhx@iae.nl (Marcel Hendrix)
Subject	Re: Parallel FIB
Newsgroups	comp.lang.forth
Message-ID	<17061400988434@frunobulax.edu> (permalink)
Date	2013-05-03 21:29 +0200
References	<2013May3.142604@mips.complang.tuwien.ac.at>
Organization	Wanadoo

Show all headers | View raw

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Parallel FIB

> mhx@iae.nl (Marcel Hendrix) writes:
>>In the context of a benchmark the actual speed of solving the problem 
>>doesn't matter.

> That's debatable.

Please debate, then :-)

I assume that we use the benchmark only to compare Forth systems for 
particular features. For the fib benchmark, the aim is to test recursion 
efficiency. As fib's argument can't be larger than say 100, the fastest 
implementation is obviously a table lookup or a simple loop, but I am not 
interested in that.

>> What I am looking for is a way to put to work 
>>all 4 (n) cores to work so that they deliver a significant contribution 
>>to the final result.

[..]

> Actually my suggestion (based on your earlier version) is:

> : pfib ( n1 -- n2 )
>	TO n  n 6 < IF  n fib EXIT  ENDIF
>	fibs OFF
>	PAR
>	  STARTP  n 4 - fib 3 * 
>	          n 5 - fib 5 * + fibs LOCKED+! DROP  ENDP
>	  STARTP  n 6 - fib 2*    fibs LOCKED+! DROP  ENDP
>	ENDPAR
>	fibs @ ;

You want to swap n 4- with n 6 - , but I see what you mean. Sorry
for misunderstanding your original suggestion. 

> Should have the same CPU time, and on 1 or 3+ cores similar wallclock
> time as your old version; and have lower wallclock time on 2 cores.

Yes (not tested for 2 cores).

> For getting more cores to work, let's just start with the unoptimized
> fib and parallelize the recursions:

> : pfib1 ( n1 -- )
>    dup 2 < if
>	drop 1 fibs locked+! drop
>    else {: n :}
>	PAR
>         STARTP n 1- recurse ENDP
>	  STARTP n 2- recurse ENDP
>        ENDPAR
>    endif ;

> : pfib ( n1 -- n2 )
>  0 fibs ! pfib1 fibs @ ;

I am not sure I understand this. We have only 4 (or 6) 
cores, so this is just a test of how long it takes to queue 
and dequeue tasks. As every recursive call needs a thread,
this will be horrendously slow. That's not what I want
to test.

I think the problem of efficiently using more than 2 cores 
for a recursive fib is still open.

-marcel

-- ----------------------
ANEW -pfibs

NEEDS -tps

: fib ( n1 -- n2 )
    DUP 2 < IF
	DROP 1
    ELSE
	DUP  1- RECURSE
	SWAP 2- RECURSE
	+
    ENDIF ;

0 VALUE n
VARIABLE fibs

\ ... f5          f4       f3       f2        f1             F0
\ ... (f6+f7)  (f5+f6)  (f5+f4)  (f4+f3)   (f3+f2)       f2+2f3+f4
\ ...                            (2f4+f5)  (f3+2f4+f5)   f3+4f4+2f5
\ ...                            (3f5+2f6) (3f4+2f5)     8f5+5f6
: pfib0 ( n1 -- n2 )
	TO n  n 6 < IF  n fib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 4 - fib 3 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 5 - fib 5 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 6 - fib 2*  fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;

: pfib1 ( n1 -- n2 )
	TO n  n 6 < IF  n fib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 5 - fib 8 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 6 - fib 5 * fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;

: pfib2 ( n1 -- n2 )
	TO n  n 6 < IF  n fib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 5 - fib 5 * 
	          n 6 - fib 2* + fibs LOCKED+! DROP  ENDP
	  STARTP  n 4 - fib 3 *  fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;

: sfib ( n1 -- n2 )
	TO n  n 6 < IF  n fib EXIT  ENDIF
	n 5 - fib 8 * 
	n 6 - fib 5 * + ;

: bench	CR ." \ serial FIB(47)       : " TIMER-RESET #47  fib  U. .ELAPSED 
	CR ." \ new FIB(47)          : " TIMER-RESET #47 sfib  U. .ELAPSED 
	CR ." \ parallel FIB(47) (0) : " TIMER-RESET #47 pfib0 U. .ELAPSED  
	CR ." \ parallel FIB(47) (1) : " TIMER-RESET #47 pfib1 U. .ELAPSED  
	CR ." \ parallel FIB(47) (2) : " TIMER-RESET #47 pfib2 U. .ELAPSED ; 

\ FORTH> bench ( 4, 5, 6 )
\ serial FIB(47)   : 4807526976 46.130 seconds elapsed.
\ new FIB(47)      : 4807526976 13.344 seconds elapsed. 
\ parallel FIB(47) : 4807526976 7.018 seconds elapsed. ok

\ FORTH> bench ( 5, 6 )
\ serial FIB(47)   : 4807526976 44.669 seconds elapsed.
\ new FIB(47)      : 4807526976 6.502 seconds elapsed.
\ parallel FIB(47) : 4807526976 4.160 seconds elapsed. ok

\ FORTH> bench
\ serial FIB(47)       : 4807526976 45.180 seconds elapsed.
\ new FIB(47)          : 4807526976 6.533 seconds elapsed.
\ parallel FIB(47) (0) : 4807526976 6.836 seconds elapsed.
\ parallel FIB(47) (1) : 4807526976 4.104 seconds elapsed.
\ parallel FIB(47) (2) : 4807526976 6.759 seconds elapsed. ok

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

Thread

Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-02 01:20 +0200
  Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-02 14:13 +0000
    Re: Parallel FIB Paul Rubin <no.email@nospam.invalid> - 2013-05-02 08:25 -0700
    Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 07:04 +0200
      Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-03 12:26 +0000
        Re: Parallel FIB Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-03 15:23 +0200
          Re: Parallel FIB fred <email@address.com> - 2013-05-03 16:56 +0100
          Re: Parallel FIB Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-03 18:13 +0200
        Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 21:14 +0200
          Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-04 13:45 +0000
        Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 21:29 +0200
          Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 23:53 +0200
            Re: Parallel FIB Paul Rubin <no.email@nospam.invalid> - 2013-05-03 18:10 -0700
              Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-04 07:07 +0200
                Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-06 21:09 +0200
        Re: Parallel FIB albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-05-04 00:26 +0000

csiph-web