Next Generation of Language
in [Lisp]
|
Prev: a potential lisp convert, and interpreting the shootout
Next: ANN: ABLE 0.1, A Basic Lisp Editor
From: Maciek Pasternacki on 11 Jan 2007 11:35 On Sweetmorn, Chaos 11, 3173 YOLD, Juan R. wrote: >> | If you want to analyse chess positions you can never >> | have too much speed and it has nothing to do with >> | rendering. I'm sure it's the same situation with go and >> | many other games. >> >> But having more than one core will not be a benefit if your algorithms >> are graph based and have to search a tree. IIRC most graph algorithms >> (dfs bfs) are inherently unparallelizable. > > And did not a parallel search tree could distribute subtree search > between cores at each branching point? I thought about parallelizing DFS with queues: single thread would work like: (loop (if *node-queue* (let ((node (dequeue *node-queue*))) (do-something-with node) (dolist (subnode (children node)) (enqueue subnode *node-queue*))) (return)) Search would start with enqueuing root node, and would end by any thread setting *node-queue* to NIL. This would be parallelizable over any number of cores (supposing one doesn't care about exact DFS search order -- but if one cared about order, one wouldn't have considered parallelizing). -- __ Maciek Pasternacki <maciekp(a)japhy.fnord.org> [ http://japhy.fnord.org/ ] `| _ |_\ /{Podobnie my�la�em kiedy� pod �ukiem sklepienia w ko�ciele.Czemu� ,|{-}|}| }\/to,pomy�la�em,sklepienie si� nie zapada,skoro go nic nie podpiera? \/ |____/Bo wszystkie,odpowiedzia�em,kamienie chc� ruszy� naraz.}(J.P.) -><-
From: Paul Wallich on 11 Jan 2007 13:53 Barry Margolin wrote: > In article <1168489207.874750.19330(a)77g2000hsv.googlegroups.com>, > wv9557(a)yahoo.com wrote: > >> I don't think there is anything more anti parallelism like Lisp. Lisp >> is recursive, a function has to basically wait for another instance of >> itself to finish before continuing. Where is the parallelism? > > Functions like MAPCAR easily lend themselves to parallel variants that > operate on many elements concurrently. *Lisp, the Lisp dialect for the > massively-parallel Connection Machine, was built around operations like > this. > > For coarse-grained parallelism, you can easily make use of the > multi-threading features of most modern Lisps. And even if you (unnecessarily) stick to recursive expressions of your algorith, you can do a fair amount of work in parallel by using futures (q.v.) or techniques analagous to loop-unrolling. paul
From: Thomas A. Russ on 11 Jan 2007 13:54 wv9557(a)yahoo.com writes: > I don't think there is anything more anti parallelism like Lisp. Lisp > is recursive, a function has to basically wait for another instance of > itself to finish before continuing. Where is the parallelism? MAPCAR. -- Thomas A. Russ, USC/Information Sciences Institute
From: mark.hoemmen on 11 Jan 2007 15:40 Alex Mizrahi wrote: > nobody needs just 64 cores. they need that many cores FOR A SPECIFIC TASK. > if it's web-server, it can be easily paralelizable -- you can handle each > request in a separate thread. > there are well-known paralellization techinques for scientific tasks that > involve large matrices, etc. > > so, actually there's no much need for automatic parallel programming. tasks > requiring high-performance ALREADY are running in parallel. Um, yes and no; the big problem is not the huge-scale HPC applications (for which NSF, DARPA, etc. fund the research necessary to parallelize them effectively) but the smaller stuff, e.g. Matlab written by engineers for ad-hoc problem solving. Individual cores aren't getting much faster so in order to get performance gains from multiple cores, parallelism needs to be automatically extracted (because we can't expect Joe / Jane Civil Engineer to know how to extract it manually) or at least made easy to extract (in the style of Matlab*p or the new parallel Matlab that Cleve Moler is pushing). > i bet if you run some usual single-core task with some magic auto-parallel language, you > won't make significant benefits. Well, extracting parallelism effectively on future machines is going to require a lot of tuning, much of which may be done automatically (like ATLAS or FFTW do for single-processor codes). It's quite probable that people who code parallel libraries (e.g. for sorting or linear algebra) will in the future write very little explicitly parallel code -- instead they will supply annotations to an auto-tuner. See e.g. the PLAPACK project. > btw, you don't have to wait 10 years. you can buy GeForce 8800 for 500$, it > has hundreds of computing cores. Heh, wait until they at least document their floating-point semantics first ;P mfh
From: mark.hoemmen on 11 Jan 2007 15:47
Tim Bradshaw wrote: > Of course, all this is predicated on there being enough memory > bandwidth that everything doesn't just starve. I dunno how good > current seriously-multicore systems are in this respect. Intel's proposed 80-core architecture will have DRAM attached to each core -- sort of how Cell has "local stores" attached to each SPE. That's how they plan to solve the BW problem -- amortize it over all the cores. Basically it means that scicomp people like me get a huge job advantage 'cause we know how to deal with these issues (that's what i'm hoping anyway ;P ). mfh |