Предыстория: у меня есть независимые задачи, показанные в виде графиков потоков данных (которые повторяются вечно). Предельно простой пример:
задача 1: b1 -> c
задача 2: e -> b2
Дано назначение процессора. На самом графике показаны доступные процессоры, на которых они будут выполняться. для приведенного выше примера b1 и b2 выполняются на процессоре b, c на c и e на e.
Время выполнения всех задач известно во время компиляции. Поскольку это циклическое моделирование, наихудший случай время выполнения каждой задачи изменяется, чтобы зафиксировать арбитраж ресурсов для циклического планирования >. Пример: предположим, что первоначально все задачи в приведенном выше примере имели время выполнения 1. Затем мы меняем тайминги на b1 и b2, занимающие 2 единицы времени, c и e, занимающие 1. Это потому, что процессор b выполняет следующий код: while(1) { run_task_b1 (); run_task_b2(); } Таким образом, если мы проанализируем задачу1 (по пропускной способности и т. д.), чтобы сказать, что задача b1 занимает 2 единицы времени, достаточно разделить b1 и b2 на процессоре b.
Моя проблема: каждая задача использует дополнительный ресурс (DMA). Допустим, у нас есть 2 DMA. Если мы наивно распределяем D1 и D2 следующим образом:
b1 получает D1
c получает D2
e получает D1
b2 получает D2
Тогда после циклического моделирования b1 и b2 получает время выполнения 3 (потому что b1 делит D1 с e и b1, b2 делит процессор b, 1+1+1 = 3), а c и e получают время 2 (потому что c делит D2 с b2, а e делит D1 с b1). Итак, время 3,2,2,3.
Но если мы зададим распределение следующим образом: b1 получает D1
c получает D2
e получает D2
b2 получает D1
Смоделированное время выполнения составляет 2,2,2,2.
Итак, как сделать алгоритм для поиска назначения ресурсов (DMA) во время компиляции (статическое назначение) для заданных графов задач, чтобы смоделированное время RR было минимальным? Планирование списка даст неэффективные результаты, как объяснено в приведенном выше примере.
