Вычислительных систем
 Скачать 0.78 Mb.
|
28 Глава 3. Организация функционирования ВС Обозначим через Ω множество допустимых расписаний. В качестве по- казателя оптимальности расписаний будем использовать время ?????? (??????) окон- чания решения последней задачи ?????? (??????) = max ??????∈?????? {?????? ?????? + ?????? ?????? }. Итак, требуется найти допустимое расписание ??????, доставляющее мини- мум целевой функции ?????? (??????). Формально ?????? (??????) = max ??????∈?????? {?????? ?????? + ?????? ?????? } → min ??????∈Ω , (3.1) при ограничениях: ∑︁ ??????∈?????? (??????) ?????? ?????? ≤ ??????, ∀?????? ∈ R, (3.2) ∏︁ ??????∈?????? (??????) ∏︁ ?????? ′ ∈?????? (??????)∖{??????} (?????? ???????????? − ?????? ?????? ′ ?????? ′ ) ̸= 0, ?????? = 1, 2, . . . , ?????? ?????? , ?????? ′ = 1, 2, . . . , ?????? ′ ?????? , (3.3) ?????? ???????????? ∈ ??????, ?????? ?????? ∈ R. (3.4) Задача (3.1)–(3.4) относится к дискретной оптимизации и является трудноразрешимой. Один из подходов к приближенному решению задачи основан на ее сведении к задаче двумерной упаковки прямоугольников в полуограничен- ную полосу (2D strip packing, 2DSP). Каждая параллельная программа ?????? ∈ ?????? представляется в виде прямоугольника шириной ?????? ?????? и высотой ?????? ?????? условных единиц. Ширина полосы составляет ?????? условных единиц, высо- та – не ограничена. Требуется упаковать прямоугольники в полосу без их вращений и пересечений так, чтобы высота упаковки была минимальной. 4 5 1 2 1 2 3 4 5 … 3 Элементарные машины Вр ем я 10 T(S) Рис. 3.1. Пример упаковки прямоугольников в полуограниченную полосу: ?????? = 5, ?????? = 10, ?????? (??????) = 8 3.1. Планирование решения задач на ВС 29 На рис. 3.1 приведен пример упаковки 5 прямоугольников (задач) в полосу шириной 10 условных единиц (элементарных машин). Задача с но- мером 1 запускается на решение в нулевой момент времени (?????? 1 = 0 ) и использует элементарные машины 1–5 (?????? 11 = 1 , ?????? 12 = 2 , . . ., ?????? 15 = 5 ), за- дача 4 начинает решаться в момент времени 2 и использует ЭМ 8, 9 и 10. Значение целевой функции ?????? (??????) = 8. 3.1.2. Задание 1. Написать программу, реализующую алгоритмы NFDH – Next-Fit Decreasing Height и FFDH – First-Fit Decreasing Height для приближен- ного решения задачи (3.1)–(3.4). В качестве входных параметров программа получает имя файла с на- бором задач, количество ?????? ЭМ в системе и название алгоритма (NFDH или FFDH). Результат работы программы: – расписание ?????? решения задач; – значение ?????? (??????) целевой функции; – отклонение ?????? значения целевой функции от ее нижней границы ?????? ′ ; – время ?????? выполнения программы в секундах. ?????? = ?????? (??????) − ?????? ′ ?????? ′ , ?????? ′ = 1 ?????? ∑︁ ??????∈?????? ?????? ?????? ?????? ?????? Упорядочивание задач в алгоритмах NFDH и FFDH выполнять сорти- ровкой подсчетом (counting cort) [2, С. 223]. При реализации алгоритма FFDH рекомендуется использовать дерево турнира (tournament tree, max winner tree). Каждый лист такого дерева – уровень упаковки, а значение листа — количества свободных ЭМ на уровне. Каждый внутренний узел дерева содержит максимальное из зна- чений левого и правого дочерних узлов. В таком дереве поиск первого подходящего уровня (first fit, FF) выполняется за время ??????(log ??????). Послед- нее обеспечивает выполнение алгоритма FFDH за время ??????(?????? log ??????). Источники информации об алгоритмах FF, NFDH и FFDH: – David S. Johnson. Case Studies: Bin Packing & The Traveling Salesman Problem http://logic.pdmi.ras.ru/midas/sites/default/files/Johnson-Tuesday.pdf – Heidi Smith. Level Algorithms and Shelf Algorithms for // http://users.cs.cf.ac.uk/C.L.Mumford/heidi/Approaches.html – Jan H van Vuuren. 2D Strip Packing Problem // http://dip.sun.ac.za/vuuren/repositories/levelpaper/spp[1].htm 2. Исследовать время выполнения алгоритмов в зависимости от коли- чества ?????? задач в наборе. |