0

我不确定这是否有一个简单的解决方案或者是一个“命名”算法，所以我想我会在这里问。

我有一个来自编译器的数据流图（DFG）。这是一个弧加权 DAG。弧权重表示各种操作的延迟，节点表示操作本身（加法、减法、加载等）。我试图找到允许计算在其关键路径上运行的最小资源集。

我已经通过以下方式做到了这一点： 

// Initialize   
ready_list <- 0   
clock = 0   
resource[resource_types] <- 0   
resource_max[resource_types] <- -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 <- n    

// "schedule" instruction   
n = pop(ready_list)   
n = SCHEDULED   
resource[resource_type(n)]++

// Update maximum resource required   
if resource[resource_type(n)] > resource_max[resource_type(n)]      
    resource_max[resource_type(n)] = resource[resource_type(n)]   

if ready_list = empty   
    clock++;

然后资源数组将具有确保没有争用所需的最少资源，最终时钟值将是关键路径（这只是为了证明这不是作业问题=]）

我只是想知道这是否有一个“名称”，或者是否有其他一些可爱的方式来做到这一点。谢谢！

4

0 回答 0