Cilk multiprocessing API for newLISP

[Lutz]

Cilk is a simple API to launch forked child processes and collect the results. Well suited for newLISP because of newLISP's small overhead when starting forks. On multi core architectures multiple spawned processes will be distributed onto different cores.



The small API has only 3 functions: spawn, sync and abort. The API can be used recursively, i.e. childs spawning childs.



This is a preview, no compiled binaries, Mac OS X/UNIX only, only tested on Mac OS X.



File: http://newlisp.org/download/development/newlisp-9.3.7.tgz">http://newlisp.org/download/development ... -9.3.7.tgz">http://newlisp.org/download/development/newlisp-9.3.7.tgz



Changes notes: http://newlisp.org/downloads/development/CHANGES-9.3.7.txt">http://newlisp.org/downloads/developmen ... -9.3.7.txt">http://newlisp.org/downloads/development/CHANGES-9.3.7.txt



Ps: I am traveling and not available on this board until Saturday.

[Jeff]

It would be inappropriate to express my feelings on this forum.  Thanks, Lutz.  I can't wait to start writing truly concurrent software with this!

[Lutz]

Thanks to you for pointing us to Cilk in the first place ;-)



'fork' has been in newLISP for a long time, but the inconvenience to program with shared memory and semaphores has not made it accessible to many. The Cilk interface is easy enough to understand and program, that more people will use it.

[Jeff]

A couple of suggestions.  (sync -1) should indefinitely block until all children have joined.  On Windows and non-pthread systems, these functions should still work, but not spawn any threads.



Since cilk's premise is to have a scheduler decide if a spawned block should even be launched as a separate thread, it should present no logic problem to have all spawned blocks launch in the current process for non-posix systems.  That would allow code using spawn/sync to be portable.

[Lutz]

Yes, we can make 'spawn' just work like  a 'set' on Win32 for portability and 'sync' and 'abort' will just do nothing. This way code is portable to Win32, albeit running slower. newLISP does not do threads, always forks instead. But we could have a scheduler in the future, to decide to fork functions or queue them it if a maximum number of processes is reached. For most tasks the number of processes it takes is probably known, so having that functionality is nor urgent.

[Jeff]

Browsing the code, I see that you are implementing it yourself (not using the actual cilk library).



Would it be possible to implement a scheduler that would decide to run a block inside a thread or not depending on the number of processes currently spawned and the number of cpus?  Perhaps eventually with some sort of primitive load balancing?

[Jeff]

Yes, we can make 'spawn' just work like  a 'set' on Win32 for portability and 'sync' and 'abort' will just do nothing. This way code is portable to Win32, albeit running slower. newLISP does not do threads, always forks instead. But we could have a scheduler in the future, to decide to fork functions or queue them it if a maximum number of processes is reached. For most tasks the number of processes it takes is probably known, so having that functionality is nor urgent.

Not all recursive functions are trivial.  Say I were doing a puzzle solver, like for sudokus (always a fun exercise).  That is a naturally recursive problem and one that would likely benefit from concurrency.  Something like that where the starting point has no idea how deeply it will recurse would benefit from a scheduler.



I am thinking that, at least initially, it could be done cheaply- if the number of child processes/number of cpus reaches some set point, then spawn doesn't launch a new process.

[newdep]

interesting ;-) lets have a look..



back in 2005 i suggested this: http://www.sics.se/~adam/pt/">//http://www.sics.se/~adam/pt/



but when Chess is involved ..Im inn ;-)

[newdep]

make linux_readline (32 bits slackware)





make[1]: Entering directory `/home/'

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX newlisp.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-symbol.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-math.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-list.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-liststr.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-string.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-filesys.c

nl-filesys.c: In function `processSpawnList':

nl-filesys.c:1326: warning: pointer of type `void *' used in arithmetic

nl-filesys.c:1331: warning: pointer of type `void *' used in arithmetic

nl-filesys.c:1335: warning: pointer of type `void *' used in arithmetic

nl-filesys.c: In function `p_spawn':

nl-filesys.c:1401: warning: pointer of type `void *' used in arithmetic

nl-filesys.c:1406: warning: pointer of type `void *' used in arithmetic

nl-filesys.c:1407: warning: pointer of type `void *' used in arithmetic

nl-filesys.c:1408: warning: pointer of type `void *' used in arithmetic

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-sock.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-import.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-xml.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-web.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-matrix.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX nl-debug.c

gcc -Wall -pedantic -Wno-uninitialized -Wno-strict-aliasing -Wno-long-long -c -O2 -g -DREADLINE -DLINUX pcre.c

gcc newlisp.o nl-symbol.o nl-math.o nl-list.o nl-liststr.o nl-string.o nl-filesys.o nl-sock.o nl-import.o nl-xml.o nl-web.o nl-matrix.o nl-debug.o pcre.o -g -

lm -ldl -lreadline -lncurses -o newlisp

strip newlisp

make[1]: Leaving directory `/home'

[newdep]

Wow... Slick !! only 4Kb bigger binary.. Looks like this fits

right into newlisp ..nice smooth code ;-)