Теорема. При любом назначении задания с длиной максимального пути в графе предшествования, равной , на процессоры из множества всегда существует корректный план продолжительностью, не превышающей , если .
Доказательство. Разобьем множество задач рассматриваемого задания по ярусам в направлении от входа к выходу. Построим план выполнения задания по следующему правилу: задачи i-го яруса выполняются на i-м периоде. Этот план корректен, так как все задачи первого яруса будут решены на первом периоде, все задачи второго яруса - на втором периоде, причем все исходные данные для них будут подготовлены на предыдущем периоде, и т.д.
Автоматическая генерация примеров для исследования эффективности алгоритма
Для исследования эффективности предложенного алгоритма назначения была поставлена цель сбора статистики с использованием программы случайной генерации примеров. Получаемая статистика может в существенной степени зависеть от применяемого набора тестовых примеров, поэтому желательно, чтобы генерируемые наборы назначаемых заданий обладали бы свойствами, характерными для практических приложений. Однако достижение этой цели является сложной проблемой, поэтому был использован следующий подход. Предварительно формируется библиотека конкретных структур заданий, а затем при генерации примеров из этой библиотеки случайным образом выбирается некоторая структура, а уже потом для ее задач случайным образом выбираются длительности. Этот путь имеет недостатки, и, прежде всего, непонятно какие структуры должны быть включены в библиотеку. Успешность решения того или иного примера определялась путем соотнесения получаемого решения с оптимальным результатом, который формировался методом полного перебора с применением заданного критерия оптимальности. В данном случае критерий оптимальности имел следующий аддитивный вид:
,
где P - число использованных процессоров;
C - число использованных каналов обмена;
a, b - весовые коэффициенты.
При этом в библиотеку структур включались все возможные иерархические структуры с числом задач не более шести. Кроме того, в библиотеку добавлялось ограниченное число характерных структур с большим числом задач. В итоге общее число структур равнялось 30. Поскольку выбор правильного соотношения между коэффициентами a и b зависит от практических ограничений, моделирование производилось при разных значениях этого соотношения. В процессе исследования формировались статистики примеров, отличающихся от оптимального результата не более чем на 10, 20 и 30 %. Длительности задач моделировались в условных единицах как равномерно распределенные в интервале [0,1, 10], длительности обменов - в интервале [0,1, 5] при допустимой загрузке процессора и канала обмена, равных 10. Для каждого значения отношения b/a моделировалось по 300 примеров. Кроме того, для предлагаемого алгоритма формировалась величина так называемого интегрального проигрыша (ИП), определяемого как отношение разности сумм значений критерия по всем примерам для предлагаемого и оптимального алгоритмов к сумме значений критерия для оптимального алгоритма. Результаты исследования приведены в табл. 2. Столбцы таблицы соотнесены с разными значениями отношения b/a, а в строках приведены полученные статистики (в долях от количества использованных примеров).
2. Результаты исследования предложенного алгоритма назначения
|
b/a, % |
1 |
5 |
10 |
15 |
|
|
10 |
0,58 |
0,65 |
0,76 |
0,8 |
|
|
20 |
0,69 |
0,77 |
0,76 |
0,8 |
|
|
30 |
0,85 |
0,78 |
0,76 |
0,8 |
|
|
ИП |
0,12 |
0,15 |
0,17 |
0,15 |
Заключение
В настоящей работе предложен алгоритм назначения на процессоры системы реального времени заданий с иерархическим отношением предшествования. Причем производительности используемых процессоров не хватает для решения любого из заданий за период входного потока данных. В результате оказывается неизбежной распределенная обработка информации. Проведенное сопоставление предложенного алгоритма с оптимальным показало, что интегрально предложенный алгоритм проигрывает не более 17 %.
Библиографический список
Теория расписаний и вычислительные машины / Под ред. Э. Г. Коффмана. М.: Наука, 1984. 334 с.
Топорков В.В. Модели распределенных вычислений. М.: Физматлит, 2004. 316 с.
Каляев И.А., Мельник Э.В. Децентрализованные системы компьютерного управления. Ростов н/Д: Изд-во ЮНЦ РАН, 2011. 196 с.
Liu J.W.S. Real-Time Systems // Prentice Hall, Englewood Cliffs. NJ, 2000. 600 p.
Гергель В.П. Теория и практика параллельных вычислений. М.: Изд-во Интернет-университет информационных технологий - ИНТУИТ.ру; БИНОМ. Лаборатория знаний, 2007. 424 с.