Существует ли имя для алгоритма, который находит минимальный набор ресурсов, который не допускает конкуренции за ресурсы в графе потока данных / взвешенной группе доступности базы данных? - PullRequest
0 голосов
/ 26 мая 2011

Я не уверен, что у этого есть простое решение или это «именованный» алгоритм, поэтому я подумал, что я должен спросить здесь.

У меня есть граф потока данных (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++;  

Тогда массив ресурсов будет иметь минимальное количество ресурсов, необходимых для обеспечения отсутствия конкуренции, и окончательное значение тактового сигнала будет критическим путем (это просто для того, чтобы доказать, что это не домашняя задача =])

Мне просто интересно, есть ли у этого "имя" или есть какой-то другой милый способ сделать это. Спасибо!

...