Databases
StackOverflow2013
Postsdbo
POIs there a name for the algorithm that finds a minimal set of resources that will allow for no resource contention on a dataflow graph/weighted DAG?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs there a name for the algorithm that finds a minimal set of resources that will allow for no resource contention on a dataflow graph/weighted DAG?
    primarykey
    data
    text
    <p>I'm not sure if this has a simple solution or is a "named" algorithm, so I thought I'd ask here.</p> <p>I have a dataflow graph (DFG) from a compiler. It's an arc-weighted DAG. The arc weights denote the latency of various operations, with the nodes representing the operations themselves (addition, subtraction, loads, etc). I'm trying to find the minimal set of resources that allow the computation to be run at it's critical path. </p> <p>I've already done this in the following way: </p> <pre><code>// Initialize ready_list &lt;- 0 clock = 0 resource[resource_types] &lt;- 0 resource_max[resource_types] &lt;- -1 source = SCHEDULED // Get ready instructions for each node n in V // The following means the predecessors of n have finished running based on their // latecies/arc weights, not just been labeled "scheduled". My apologies for the poor //pseudo-code if predessesors of n are scheduled ready_list &lt;- n // "schedule" instruction n = pop(ready_list) n = SCHEDULED resource[resource_type(n)]++ // Update maximum resource required if resource[resource_type(n)] &gt; resource_max[resource_type(n)] resource_max[resource_type(n)] = resource[resource_type(n)] if ready_list = empty clock++; </code></pre> <p>Then the resources array will have the minimal number of resources required to ensure no contention, and the final clock value will be the critical path (this is just to prove this isn't a homework problem =] )</p> <p>I'm just wondering if this has a "name" or if there's some other cute way of doing this. Thanks!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USp4553d
    1. USuser770901
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. POIs there a name for the algorithm that finds a minimal set of resources that will allow for no resource contention on a dataflow graph/weighted DAG?
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    1. COlet me make sure I understood you correctly, you are looking for an algorithm that finishes the compilation within the minimum possible time, with the minimal resources difference between every two tasks?
      singulars
      1. POIs there a name for the algorithm that finds a minimal set of resources that will allow for no resource contention on a dataflow graph/weighted DAG?
      1. USamit
    2. COI'm not sure what you mean by "with the minimal resources difference between every two tasks?". What the algorithm generates is the minimal number of resources needed to ensure no contention. Which is to say that every instruction can execute immediately when it is ready (when all it's predecessors have been executed). If the graph were visualized in "stages" corresponding to clock cycles, and there were only one resource type, this would correspond to the maximal width of the graph at a given stage. I'm doing it for multiple resource types.
      singulars
      1. POIs there a name for the algorithm that finds a minimal set of resources that will allow for no resource contention on a dataflow graph/weighted DAG?
      1. USuser770901
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload