Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #22372
| From | mhx@iae.nl (Marcel Hendrix) |
|---|---|
| Subject | Re: Parallel FIB |
| Newsgroups | comp.lang.forth |
| Message-ID | <00941497988434@frunobulax.edu> (permalink) |
| Date | 2013-05-06 21:09 +0200 |
| References | <90969699988434@frunobulax.edu> |
| Organization | Wanadoo |
mhx@iae.nl (Marcel Hendrix) writes Re: Parallel FIB
> Paul Rubin <no.email@nospam.invalid> writes Re: Parallel FIB
[..]
>> I have access to a big machine (16 cores, 32 threads) and would be
>> interested in giving the Erlang version (and maybe the Forth version) a
>> try.
[..]
> With 16 cores the tree can be unfolded to at least 3 PAR levels.
>Then fib(47) will not be enough work to time accurately.
> BTW, here's the current source. I have gone from 350 ms
> to 57 ms.
I unfolded it one more level for my 4 core i7 920 CPU and
finally observe 100% CPU with a further 8 times speedup (pfib_abcd).
FORTH> TIMER-RESET #64 pfib_abcd U. .ELAPSED 17167680177565 20.621 seconds elapsed. ok
(don't try this for the serial fib :-)
-marcel
-- pfib.frt ---------------
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
CREATE table 1 , 1 , 2 , 3 , 5 , 8 ,
: fib6 ( u -- u2 ) table []CELL @ ;
: sfib ( n1 -- n2 )
DUP 6 < IF ( n) fib6 EXIT ENDIF
DUP 5 - fib 8 *
SWAP 6 - fib 5 * + ;
: pfib0 ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n fibs OFF
PAR
STARTP n 4 - sfib 3 * fibs LOCKED+! DROP ENDP
STARTP n 5 - sfib 5 * fibs LOCKED+! DROP ENDP
STARTP n 6 - sfib 2* fibs LOCKED+! DROP ENDP
ENDPAR
fibs @ ;
: pfib1 ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n fibs OFF
PAR
STARTP n 5 - sfib 8 * fibs LOCKED+! DROP ENDP
STARTP n 6 - sfib 5 * fibs LOCKED+! DROP ENDP
ENDPAR
fibs @ ;
VARIABLE fibs_ab 0 VALUE n_ab
VARIABLE fibs_cd 0 VALUE n_cd
VARIABLE fibsa 0 VALUE na
VARIABLE fibsb 0 VALUE nb
VARIABLE fibsc 0 VALUE nc
VARIABLE fibsd 0 VALUE nd
: pfib_a ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO na fibsa OFF
PAR
STARTP na 5 - sfib 8 * fibsa LOCKED+! DROP ENDP
STARTP na 6 - sfib 5 * fibsa LOCKED+! DROP ENDP
ENDPAR
fibsa @ ;
: pfib_b ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO nb fibsb OFF
PAR
STARTP nb 5 - sfib 8 * fibsb LOCKED+! DROP ENDP
STARTP nb 6 - sfib 5 * fibsb LOCKED+! DROP ENDP
ENDPAR
fibsb @ ;
: pfib_c ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO nc fibsc OFF
PAR
STARTP nc 5 - sfib 8 * fibsc LOCKED+! DROP ENDP
STARTP nc 6 - sfib 5 * fibsc LOCKED+! DROP ENDP
ENDPAR
fibsc @ ;
: pfib_d ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO nd fibsd OFF
PAR
STARTP nd 5 - sfib 8 * fibsd LOCKED+! DROP ENDP
STARTP nd 6 - sfib 5 * fibsd LOCKED+! DROP ENDP
ENDPAR
fibsd @ ;
: pfib_ab ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n_ab fibs_ab OFF
PAR
STARTP n_ab 5 - pfib_a 8 * fibs_ab LOCKED+! DROP ENDP
STARTP n_ab 6 - pfib_b 5 * fibs_ab LOCKED+! DROP ENDP
ENDPAR
fibs_ab @ ;
: pfib_cd ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n_cd fibs_cd OFF
PAR
STARTP n_cd 5 - pfib_c 8 * fibs_cd LOCKED+! DROP ENDP
STARTP n_cd 6 - pfib_d 5 * fibs_cd LOCKED+! DROP ENDP
ENDPAR
fibs_cd @ ;
: pfib_abcd ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n fibs OFF
PAR
STARTP n 5 - pfib_ab 8 * fibs LOCKED+! DROP ENDP
STARTP n 6 - pfib_cd 5 * fibs LOCKED+! DROP ENDP
ENDPAR
fibs @ ;
-- Anton Ertl
: pfib2 ( n1 -- n2 )
DUP 6 < IF fib6 EXIT ENDIF
TO n fibs OFF
PAR
STARTP n 5 - sfib 5 *
n 6 - sfib 2* + fibs LOCKED+! DROP ENDP
STARTP n 4 - sfib 3 * fibs LOCKED+! DROP ENDP
ENDPAR
fibs @ ;
-- Bernd Paysan, various bugs.
5e FSQRT FDUP 1/F FCONSTANT /sqrt5
1e F+ F2/ FLN FCONSTANT gbase
: fibL ( n -- ) ( F: -- f )
DUP S>F gbase F* FDUP FEXP FSWAP FNEGATE FEXP
1 AND IF F+ ELSE F- THEN /sqrt5 F* ;
: 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) (1ab) : " TIMER-RESET #47 pfib_ab U. .ELAPSED
CR ." \ parallel FIB(47) (abcd) : " TIMER-RESET #47 pfib_abcd U. .ELAPSED
CR ." \ parallel FIB(47) (2) : " TIMER-RESET #47 pfib2 U. .ELAPSED
CR ." \ linear FIB(47) : " TIMER-RESET #48 fibL F>S U. .ELAPSED ;
\ FORTH> bench
\ serial FIB(47) : 4807526976 45.876 seconds elapsed.
\ new FIB(47) : 4807526976 6.707 seconds elapsed.
\ parallel FIB(47) (0) : 4807526976 1.012 seconds elapsed.
\ parallel FIB(47) (1) : 4807526976 0.620 seconds elapsed.
\ parallel FIB(47) (ab) : 4807526976 0.057 seconds elapsed.
\ parallel FIB(47) (abcd) : 4807526976 0.007 seconds elapsed.
\ parallel FIB(47) (2) : 4807526976 1.021 seconds elapsed.
\ linear FIB(47) : 4807526975 0.000 seconds elapsed. ok
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar
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