logoalt Hacker News

duped • last Tuesday at 7:01 PM • 1 reply • view on HN

> Generating dependence-free subsets for parallel processing.

Unsure how this is defined (*) but graph cutting approaches to concurrent task scheduling is both pessimistic (poor utilization of available resources) and (iirc) NP-hard, so you pay an big cost upfront.

On the other hand, if you know the indegree/outdegree of each node at the time they are visited (meaning the graph is static) you can run Kahn's algorithm concurrently and put each node into a shared work queue. You can optimize that further by having per-thread work queues and stealing between them. Depending on what the nodes represent there are even more optimizations and heuristics, concurrent task scheduling is a hard problem.

* imagine the graph

(a, b) (a, c) (b, d) (c, d)

Is it possible to get nodes b and c in parallel "subsets" in your library?

Replies

ww520 • last Tuesday at 7:05 PM

Yes. It would produce dependence-free subsets. I just ran your sample (assuming a,b means a depends on b).

  Topologically sorted sets: [ { d }  { b c }  { a }  ]
  Topologically sorted list: [ d b c a ]
  Nodes: [ a b c d ]
  Dependency tree:
  [ d ]
    d -> [ b c ]
      b -> [ a ]
        a ->
      c -> [ a ]
        a ->
The dependence-free subset finding is probably not exhausting and optimal. I haven't gone through formal proofing. It's opportunistic and best effort at best currently.
➕ show 1 reply