ВУЗ:
Составители:
3
Лабораторная работа № 1
Разработка списочных расписаний для мультипроцессорных
детерминированных вычислительных систем жесткого
реального времени
Цель работы - приобретение практических навыков использования
эвристического метода составления списочных расписаний для мульти-
процессорных детерминированных вычислительных систем жесткого ре-
ального времени.
Методические указания.
1 Краткое теоретическое введение
Имеется однородная мультипроцессорная вычислительная система
(ВС), состоящая
из m идентичных процессоров (m
≥
2) и предназначенная
для функционирования в реальном времени.
Вычисления, проводимые в реальном времени, представляют собой
совокупность взаимосвязанных работ A
i
(i=1,...,n), которые должны быть
выполнены на процессорах ВС.
Отношения предшествования для совокупности работ задаются в
форме ациклического связного ориентированного графа, i-м (i=1,...,n) вер-
шинам которого соответствуют работы A
i
(i=1,...,n).
Для каждой i
-й работы известно целочисленное значение времени ее
выполнения t
i
(i=1,...,n). Вершины графа являются взвешенными, вес i-
ой вершины - это t
i
(i=1,...,n).
Требуется распределить работы из заданной совокупности с учетом
их отношений предшествования по процессорам ВС, т.е. составить для нее
расписание - план выполнения работ по каждому процессору ВС. Для ВС
реального времени минимизируемой величиной при составлении расписа-
ния является длина расписания
ω
, т.е. общее время выполнения ВС всей
совокупности работ.
В основе эвристического метода составления списочных расписаний
лежит список L=( A
i
1
, A
i
2
, ..., A
i
n
) , i
k
∈
{1,2,...,n}, k=1,...,n. Работы в спи-
ске упорядочены слева направо по убыванию (не возрастанию) некоторого
заданного приоритета.
Помимо списка L для указанного эвристического метода в качестве
исходной информации используются следующие данные:
Лабораторная работа № 1
Разработка списочных расписаний для мультипроцессорных
детерминированных вычислительных систем жесткого
реального времени
Цель работы - приобретение практических навыков использования
эвристического метода составления списочных расписаний для мульти-
процессорных детерминированных вычислительных систем жесткого ре-
ального времени.
Методические указания.
1 Краткое теоретическое введение
Имеется однородная мультипроцессорная вычислительная система
(ВС), состоящая из m идентичных процессоров (m ≥ 2) и предназначенная
для функционирования в реальном времени.
Вычисления, проводимые в реальном времени, представляют собой
совокупность взаимосвязанных работ Ai (i=1,...,n), которые должны быть
выполнены на процессорах ВС.
Отношения предшествования для совокупности работ задаются в
форме ациклического связного ориентированного графа, i-м (i=1,...,n) вер-
шинам которого соответствуют работы Ai (i=1,...,n).
Для каждой i-й работы известно целочисленное значение времени ее
выполнения ti (i=1,...,n). Вершины графа являются взвешенными, вес i-
ой вершины - это ti (i=1,...,n).
Требуется распределить работы из заданной совокупности с учетом
их отношений предшествования по процессорам ВС, т.е. составить для нее
расписание - план выполнения работ по каждому процессору ВС. Для ВС
реального времени минимизируемой величиной при составлении расписа-
ния является длина расписания ω, т.е. общее время выполнения ВС всей
совокупности работ.
В основе эвристического метода составления списочных расписаний
лежит список L=( Ai1, Ai2, ..., A in ) , ik ∈ {1,2,...,n}, k=1,...,n. Работы в спи-
ске упорядочены слева направо по убыванию (не возрастанию) некоторого
заданного приоритета.
Помимо списка L для указанного эвристического метода в качестве
исходной информации используются следующие данные:
3
