Comment by duped

Comment by duped 2 days ago

> 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?

ww520 2 days ago

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.

Reply View 4 replies

duped 2 days ago

How are the subsets defined?

Reply View | 3 replies
- ww520 2 days ago
  
  At every round of the algorithm, all nodes with 0 in-degree (i.e. they are not depending on anyone) are collected as a dependence-free subset.
  They serve as the root set to the rest of the graph for the current round. The depending nodes reached from root set have their in-degree decremented. When their in-degrees reach 0, they are added to the next root set.
  I'm using double-buffering to maintain the current root set for processing and to collect the next root set for the next round, instead of using a queue as in Kahn's algorithm. At the end of the round, I simply swap the double-buffers. It's very efficient. When the next root set is empty, all nodes have been processed.
  
  Reply View | 2 replies
  
  duped 2 days ago
  
  Do you define "in degree" as the number of incoming edges from nodes that have not been visited/sorted yet?
  I believe what you've implemented is equivalent to Kahn's algorithm. Your double buffer is the queue.
  
  Reply View | 1 reply
  
  ww520 a day ago
  
  It's a variant to the Kahn's algorithm. Here's the description in the comment on the function.
  // This is a variant to the Kahn's algorithm, with additions on // finding dependence-free subsets and finding the cyclic nodes. // // This algorithm iteratively finds out the root sets of the graph. // 1. Find the first root set of the graph. // 2. Remove the nodes of the root set from the graph. // 3. Find the next root set. Go to 2 until the graph is empty. // A root set consists of nodes depending on no other nodes, i.e. // nodes whose incoming link count is 0.
  The successive root sets form a topological order.
  The in-degree of a node is the count of the incoming links of the leading nodes that the node is depending on. The in-degree can change as other nodes are removed from the graph.
  Kahn's algorithm uses a queue to hold the pending nodes and works on one node at a time. My insight is that it's simpler to treat the root nodes as sets, and to partition the root nodes into the current root set and the next root set, which work nicely with the double-buffer mechanism. As a benefit, the nodes in a root set are dependence-free with regard to the current round and can be used for parallel processing.
  
  Reply View | 0 replies