3 ms·

Depth First Search is not parallelizable at all? Provably so? Just divvy up subtrees.

nothrabannosir 8y ago
I'm assuming they mean actually Depth First, where splitting up a tree and traversing branches in parallel violates the "First" part. It's a bit contrived, because obviously the name implies that it's sequential. But yeah, sometimes that's precisely what you need.
- waynecochran 8y ago
  Yes. I guess the divvying up is more like breadth first. Most cases where I would use DFS this would work.
  - wtracy 8y ago
    Nothing that processes nodes in parallel can guarantee either correct depth first or breadth first ordering. That said, it's easy enough to get effectively correct ordering by reassembling the results in the correct order as the workers finish.
rbehrends 8y ago
What he is presumably talking about here is lexicographic DFS (as opposed to an unordered DFS), i.e. a DFS where the traversal order matters. To be precise: given a rooted digraph G with a set of vertices, an ordered adjacency list for each vertex, and two vertices a and b in G, does a DFS traversal of the graph that follows each adjacency list in order, visit a before b or b before a? In practice, what we are interested in in particular is both a reproducible preorder and postorder ordering based on the DFS traversal, which is of use in other algorithms (such as Tarjan's algorithm for strongly connected components [1]). This problem is P-complete and under the assumption that P != NC and under the parallelization assumptions underlying NC [3], is difficult to parallelize. So far, this is not very controversial, but in practice, NC does not properly reflect what we think of as "inherently sequential"; especially the assumption of a polynomial number of processors is a bit odd when you're not dealing with hardware circuits. On top of that, we often aren't interested in all possible graphs, but only specific types of graphs. As a consequence, yes, lexicographic DFS can be parallelized for many use cases or in a fashion that we care about. As a simple example, lexicographic DFS for trees can be parallelized efficiently. More generally, lexicographic DFS is already extremely fast if we have an existing in-memory representation of the graph (linear in the size of the representation with a small constant factor). It may take longer to construct the graph than to calculate a depth-first ordering of the vertices. In this case, we may not want to parallelize the DFS algorithm as such, but organize the construction of the graph so that we can run DFS in parallel with the construction. This is of particular interest if we can't fit the graph in memory or if computing the edges of the graph is expensive. For example, we may not be able to parallelize the search as such, but we can instead parallelize the neighbor expansion. The biggest issue here is that lexicographic DFS is a rather specialized problem in the family of graph search problems and many, many interesting types of graph searches can be parallelized just fine. For example, we can easily construct a parallel version of the A* algorithm; it will not explore the graph in the precisely same order, but as we are dealing with an algorithm guided by a heuristic, this is rarely a problem in practice. [1] Though we have, contra ESR, parallel algorithms for strongly connected components in directed graphs that do not require a DFS ordering for the entire graph [2]. [2] See the previous work section of this thesis, for example: https://www.cs.vu.nl/~wanf/theses/matei.pdf https://www.cs.vu.nl/~wanf/theses/matei.pdf [3] https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarc...
nickpsecurity 8y ago
First thing I do when someone says something is impossible is DuckDuckGo it to see if it's been done. Second I read those claims, I DDG'd each one with "parallel" in quotes to narrow it down. Already submitted one to Lobsters. The DFS paper I havent read yet. There's definitely opportunities in prior work in some of them, though. Yall try it to see what you find. http://iss.ices.utexas.edu/Publications/Papers/ICS2016.pdf http://iss.ices.utexas.edu/Publications/Papers/ICS2016.pdf https://repository.upenn.edu/cgi/viewcontent.cgi?article=1444&context=cis_reports https://repository.upenn.edu/cgi/viewcontent.cgi?article=144...

I'm assuming they mean actually Depth First, where splitting up a tree and traversing branches in parallel violates the "First" part. It's a bit contrived, because obviously the name implies that it's sequential. But yeah, sometimes that's precisely what you need.

waynecochran 8y ago
Yes. I guess the divvying up is more like breadth first. Most cases where I would use DFS this would work.
- wtracy 8y ago
  Nothing that processes nodes in parallel can guarantee either correct depth first or breadth first ordering. That said, it's easy enough to get effectively correct ordering by reassembling the results in the correct order as the workers finish.

rbehrends 8y ago

What he is presumably talking about here is lexicographic DFS (as opposed to an unordered DFS), i.e. a DFS where the traversal order matters. To be precise: given a rooted digraph G with a set of vertices, an ordered adjacency list for each vertex, and two vertices a and b in G, does a DFS traversal of the graph that follows each adjacency list in order, visit a before b or b before a? In practice, what we are interested in in particular is both a reproducible preorder and postorder ordering based on the DFS traversal, which is of use in other algorithms (such as Tarjan's algorithm for strongly connected components [1]). This problem is P-complete and under the assumption that P != NC and under the parallelization assumptions underlying NC [3], is difficult to parallelize. So far, this is not very controversial, but in practice, NC does not properly reflect what we think of as "inherently sequential"; especially the assumption of a polynomial number of processors is a bit odd when you're not dealing with hardware circuits. On top of that, we often aren't interested in all possible graphs, but only specific types of graphs. As a consequence, yes, lexicographic DFS can be parallelized for many use cases or in a fashion that we care about. As a simple example, lexicographic DFS for trees can be parallelized efficiently. More generally, lexicographic DFS is already extremely fast if we have an existing in-memory representation of the graph (linear in the size of the representation with a small constant factor). It may take longer to construct the graph than to calculate a depth-first ordering of the vertices. In this case, we may not want to parallelize the DFS algorithm as such, but organize the construction of the graph so that we can run DFS in parallel with the construction. This is of particular interest if we can't fit the graph in memory or if computing the edges of the graph is expensive. For example, we may not be able to parallelize the search as such, but we can instead parallelize the neighbor expansion. The biggest issue here is that lexicographic DFS is a rather specialized problem in the family of graph search problems and many, many interesting types of graph searches can be parallelized just fine. For example, we can easily construct a parallel version of the A* algorithm; it will not explore the graph in the precisely same order, but as we are dealing with an algorithm guided by a heuristic, this is rarely a problem in practice. [1] Though we have, contra ESR, parallel algorithms for strongly connected components in directed graphs that do not require a DFS ordering for the entire graph [2]. [2] See the previous work section of this thesis, for example: https://www.cs.vu.nl/~wanf/theses/matei.pdf https://www.cs.vu.nl/~wanf/theses/matei.pdf [3] https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarc...

nickpsecurity 8y ago

First thing I do when someone says something is impossible is DuckDuckGo it to see if it's been done. Second I read those claims, I DDG'd each one with "parallel" in quotes to narrow it down. Already submitted one to Lobsters. The DFS paper I havent read yet. There's definitely opportunities in prior work in some of them, though. Yall try it to see what you find. http://iss.ices.utexas.edu/Publications/Papers/ICS2016.pdf http://iss.ices.utexas.edu/Publications/Papers/ICS2016.pdf https://repository.upenn.edu/cgi/viewcontent.cgi?article=1444&context=cis_reports https://repository.upenn.edu/cgi/viewcontent.cgi?article=144...