该算法是否有名称,可以找到最少的资源集,从而不会在数据流图/加权DAG上争用资源?
|
我不确定这是一个简单的解决方案还是“命名”算法,所以我想在这里问。
我有一个来自编译器的数据流图(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++;
然后,资源数组将具有确保无争用所需的最少资源,并且最终时钟值将是关键路径(这只是证明这不是家庭作业问题=])
我只是想知道它是否有一个“名称”,或者是否有其他可爱的方法可以做到这一点。谢谢!
没有找到相关结果
已邀请:
0 个回复