Общая математическая модель распределения вычислительных ресурсов в многопроцессорных системах М.Х. Прилуцкий, С.Ю. Петри Нижегородский государственный. - презентация

1 Общая математическая модель распределения вычислительных ресурсов в многопроцессорных системах М.Х. Прилуцкий, С.Ю. Петри Нижегородский государственный университет им. Н.И. Лобачевского, Н.Новгород

2 Введение Процесс управления решением совокупности задач в многопроцессорных системах формально можно представить как проблему распределения ограниченных ресурсов в сетевых канонических структурах (см. [1-3]). Формальная постановка проблемы позволяет использовать хорошо разработанный аппарат решения задач распределения ресурсов к решению задач управления многопроцессорными системами.

3 Представление задачи Процесс решения задачи представляется в виде совокупности деятельностей. Последовательность выполнения деятельностей задается ориентированным графом без петель и контуров.

4 Ресурсы и деятельности Деятельность в процессе выполнения потребляет и производит ресурсы. Роль ресурсов играют вычислительные устройства и каналы связи, а роль деятельностей операции и подпрограммы. Взаимодействие ресурсов и деятельностей.

5 Содержательная постановка задачи Ресурсы, используемые в процессе выполнения деятельностей, будем подразделять на ресурсы общедоступного и ресурсы эксклюзивного типа. При моделировании вычислительного процесса эксклюзивным ресурсом является канал передачи данных, а общедоступными ресурсами являются отдельные процессоры.

6 Содержательная постановка задачи Процесс распределения ресурсов учитывает технологические, ресурсные, и организационные условия. К технологическим условиям относятся ограничения на интенсивности потребления ресурсов на последовательность и длительности выполнения деятельностей. К ресурсным условиям относятся ограничения на количества потребления деятельностями ресурсов. К организационным условиям относятся ограничения на возможные сроки начала и окончания выполнения деятельностей.

7 Математическая модель Исходные параметры модели T = {1,..,T 0 }- множество тактов планирования J – множество различных деятельностей, I - множество ресурсов, используемых в системе, Все ресурсы разбиваются на два подмножества: I Э – множество эксклюзивных ресурсов и I O – множество общедоступных ресурсов, I Э I О =I, I Э I О =. Vit – количество ресурса i, которое поступит в систему в такт t, i I, t T. K(j) – множество деятельностей, непосредственно предшествующих деятельности j, K(j) J, j J.

8 Математическая модель Исходные параметры модели R=(r ij ) матрица ресурсоемкостей, где r ij обозначает количество ресурса i, которое требуется для выполнения деятельности j, j J, i I.. и, соответственно, минимальная и максимальная длительности потребления деятельностью j ресурс i, i I, j J. h j – начальные сроки j J H. d j – директивные сроки j J D.

9 Математическая модель Варьируемые параметры математической модели X=( ) и Y=( ) матрицы времен начала и окончания потребления деятельностями ресурсов T, T; величины интенсивности потребления деятельностью j ресурса i в такт t, i I, j J, t T; величины, определяющие очередность расходования эксклюзивного ресурса i деятельностью j в такт t: i I Э, j,k J.

10 Математическая модель Ограничения математической модели Ограничения математической модели учитывают технологические, организационные и ресурсные условия. Технологические условия: i I, j J. (1) если и если i I, j J, t T. (2) i I, j J, (3), либо, i I Э, j,k J, (4)

11 Математическая модель Ограничения математической модели Организационные условия:, i I, j J Н. (5), i I, j J D. (6) Ресурсные условия: i I, j J. (7) i I, t T. (8) T, T,, i I, j J, t T. (9) Неформализованные условия (4) могут быть приведены к формальному виду: i I Э, j,k J, (10) i I Э, j,k J,

12 Постановка задачи В рамках построенной общей математической модели ставятся различные оптимизационные задачи такие, как задача равномерного расходования ресурсов, задача наилучшего выполнения организационных условий по начальным и (или) директивным срокам и др.

13 Алгоритмы решения задачи Алгоритмы эволюционно-генетического типа. Особь в популяции соответствует построенному расписанию, а функция приспособленности задается в соответствии с критериями задачи. Алгоритм Метрополиса. Основан на аналогии с процессом охлаждения термодинамической системы, с применением функции распределения вероятностей Больцмана. Детерминированные алгоритмы ограниченного перебора.

14 Литература 1. Прилуцкий М.Х., Батищев Д.И., Гудман Э.Д., Норенков И.П. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов// Информационные технологии. Москва, N1, 1997, с Прилуцкий М.Х., Батищев Д.И., Гудман Э.Д., Норенков И.П. Метод комбинирования эвристик для решения комбинаторных задач упорядочения и распределения ресурсов. //Информационные технологии. Москва, N2, 1997, с М.Х.Прилуцкий, Д.В.Попов. Распределение и упорядочение работ в многостадийных системах. «Моделирование и оптимизация сложных систем». Межвузовский тематический сборник научных трудов ВГАВТ, ННовгород, 1999, стр