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
.

Relevant Pages

  • Re: Next Generation of Language
    ... |>> algorithms are graph based and have to search a tree. ... |>> graph algorithms are inherently unparallelizable. ... | over any number of cores (supposing one doesn't care about exact DFS ... enqueue a node, ...
    (comp.lang.lisp)
  • Re: help: a O(n) algorithm to find the longest path in a tree
    ... Yes, you're right, this is a mistake (it is only case I. of the ... frequently as an exercise in basic courses concerning algorithms). ... It should be contained in any standard textbook dealing with graph ... of a tree. ...
    (comp.theory)
  • Re: Depth First Search in Binary Search Tree?
    ... called "dfs" is beyond me. ... That's not the meaning of a depth-first search. ... This method means that you'll get all the way to the bottom of the tree down ... While a tree is a graph, and therefore can have DFS applied to it, it ...
    (comp.programming)
  • Re: [OT] Graph programming problem.
    ... I believe the original poster needed to test if a graph were connected ... or not, so DFS or BFS would not solve this problem, an algorithm such ... > Finding all nodes in a connected component is trivial: you would use DFS ... > if you need more graph algorithms. ...
    (comp.lang.cpp)
  • Re: Basic graph theory questions
    ... I have a couple questions concerning graph theory. ... The simplest is, of course, to check for connectedness in the ... in the tree. ... Experimental Algorithms, ...
    (sci.math)