Re: Next Generation of Language



* Maciek Pasternacki <87r6u1plm6.fsf@xxxxxxxxxxx> :
| 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?
[...]
| 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).

Your stopping criterion will have to be different. Also, if your
input is not a tree, this algorithm will expand the same node multiple
times. This [inefficiency] can be done in parallel, of course :)

Which is why order tends to be important in DFS, and why it is
unsuitable for decomposition. Of course, as others have noted, once
the leaves are reached there are usually gains to be made. The point
I wanted to make was akin to that in chemistry, where the overall rate
of a reaction is limited by the rate of the slowest step. (The slowest
step here being walking the graph)

--
Madhu
.