47250 (Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса), страница 3

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

В целом эти методы легче справляются с проблемой округлений, чем методы отсечения, как правило, не используют симплекс-процедуру линейного программирования и имеют более «простую арифметику» и более «сложную логику».

Основное содержание этих методов составляют динамическое программирование и совокупность способов решения, объединённых общим термином – метод «ветвей и границ».

Комплексный подход по схеме ветвлений объединяет целый ряд близких комбинаторных методов, как-то: метод ветвей и границ, метод последовательного конструирования, анализа и отсева вариантов и др. Общая идея метода крайне проста. Множество допустимых планов некоторым способом разбивается на подмножество. В свою очередь каждое из подмножеств по этому же или другому способу снова разбиваются на подмножества до тех пор, пока каждое подмножество не будет представлять собой точку в многомерном пространстве. В силу конечности наборов значений переменных дерево подмножеств (схема ветвления) конечно.

Построение схемы ветвления есть ни что иное, как формирование процедуры перебора. Перебор может осуществляться различными способами. Сечение исходной допустимой области G₀ гиперплоскостью на части G₁₁ и G₁₂ с последующим разделением G₁₁ на G₂₁ и G₂₂ представляет собой построение дерева ветвлений с соответствующими подмно-жествами, как это показано на рис. 4.

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

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

Схема ветвления иллюстрируется решением обобщённой задачи одномерного раскроя (пример 3) с конкретными числовыми данными.

Пример 3.

Имеются заготовки длиной a₁=18, a₂=16, a₃=13. Разрезая их на части, но не склеивая, можно получать детали длинной b₁=12, b₂=10, b₃=8, b₄=6, b₅=5, b₆=4. Стоимость каждой детали известна и в условных единицах численно равна их длине. Перечисленные детали представляют собой «портфель заказов», который желательно обеспечить в первую очередь. В том случае, если это невозможно, максимизируется стоимость получаемых деталей из заданной номенклатуры. Если же портфель заказов обеспечивается, необходимо максимизировать стоимость дополнительной продукции.

Величину будем называть дефицитом. Отрицательность дефицита ещё не означает существование варианта раскроя, при положительном дефиците раскрой невозможен. Это свойство может быть использовано для указания перспективности варианта. Так, если заготовка a₂ раскраивается на b₂ и b_5, то независимо от комбинаций остальных отрезков раскрой невыполним, поскольку для оставшихся отрезков дефицит положителен.

Первые этапы приводимой ниже схемы ветвления, использующей комбинаторные отношения подмножеств вариантов, показаны на рис. 5. На первом этапе формируются разбиения первой группы отрезков (заготовок) на вторую группу (деталей) независимо от того, какой именно отрезок первой группы разрезается. Количество ветвей первого этапа можно вычислить лишь по рекуррентным соотношениям. Смысл подмножества {1, 2, 3} заключается в том, что один из отрезков первой группы в результате раскроя даёт один отрезок второй группы, один из оставшихся отрезков первой группы раскраивается на два отрезка второй группы из числа оставшихся и, наконец, последний отрезок первой группы делится на три части, образуя три отрезка второй группы. На втором этапе формируются все перестановки (с учётом порядка) элементов первого этапа. Скажем, вариант {2, 1, 3} означает, что именно первый элемент первой группы a₁ разрезается на две части и т.д.

Очередной этап ветвления образуется фиксацией отрезков второй группы при указанном на предыдущем этапе числе частей, на которое разрезается первый элемент. Другими словами, формируем сочетания по числу разделений первого элемента первого множества на число элементов второго множества. В дальнейшем фиксируем отрезки второй группы при втором элементе первой группы и, наконец, при оставшемся элементе первой группы получаем варианты раскроя, всего 447 вариантов. В подробно описанной схеме ветвления в отличие от часто применяемых ни на одном этапе не используется конкретный числовой материал. Рекомендуется построить для этого же примера иную схему ветвления, начиная с третьего этапа, по следующему признаку: отрезки второй группы фиксируются при элементе первой группы, разрезаемом на меньшее число частей. Затем надо сравнить схемы. Нетрудно убедиться, что на каждом этапе ветвления осуществляется по регулярной процедуре, что позволяет запоминать лишь один вариант. Сравнение дефицитов предыдущего и последующего вариантов позволяет выделить перспективную ветвь. Окончательный результат имеет вид:

{(b₂, b₃), (b₄, b₅, b₆), (b₁)};

{(b₁, b₄), (b₂, b₅), (b₃, b₆)};

{(b₁, b₄), (b₂, b₆), (b₃, b₅)};

{(b₁, b₅), (b₂, b₄), (b₃, b₆)};

{(b₂, b₃), (b₁, b₆), (b₄, b₅)};

{(b₁, b₆), (b₂, b₄), (b₃, b₅)};

{(b₂, b₄), (b₁, b₆), (b₃, b₅)}.

Формально задачу можно было бы свести к общему виду линейной задачи целочисленного программирования, но такое сведение приведёт к значительному увеличению количества переменных и другим трудностям. Матрица коэффициентов при этом приобретает квазиблочный вид с неплотным заполнением её отличными от нуля элементами. Как правило, задачи многоиндексные с большим числом условий и сложной упорядоченностью рекомендуется решать по схеме ветвлений, используя специфику условий и ограничений.

Для задач дискретного типа этот метод получил наибольшее распространение в силу простоты и доступности самого метода и, кроме того, наиболее естественной формы описания систем условий и ограничений, являющихся, как правило, отправным пунктом построения дерева ветвления. По существу большинство оригинальных алгоритмов (Балаша-Фора-Мальгранжа, Черенина, Джефферсона, Хиллиера и др.) являются модификациями метода ветвей и границ с учётом специфики условий задачи.

4. Построение оптимальной последовательности заданий на обработку в узле вычислительной системы

4.1 Формализация вычислительного процесса и рабочей нагрузки

Узел вычислительной системы представляется в виде совокупности оборудования и программных компонент. Оборудование включает в себя: центральный процессор (CPU), внешнюю память (HDD), устройства ввода-вывода информации (IOI). Программными компонентами в вычислительной системе являются операционная система (OS) и множество задач, реализуемых по запросам рабочей нагрузки. Для моделирования рабочей нагрузки на узлах вычислительной системы необходимо провести декомпозицию каждого задания пакета рабочей нагрузки на отдельные программные модули (ПМ_j). Количество и типы программных модулей зависят от имеющегося состава оборудования и программных средств узла вычислительной системы. При этом можно выделить следующие типы программных модулей: ввода информации; обработки информации; реализация вычислений на центральном процессоре; вывода информации. Модуль обработки информации обращается к базе данных вычислительной системы.

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

Поскольку реализация задания i из рабочей нагрузки характеризуется полумарковским процессом, то для определения характера этого процесса необходимо задать следующие характеристики:

• матрицу вероятности переходов i-го задания от одного (j-го) программного модуля к другому (l-му) программному модулю МР_i=||Р_ijl||;

• матрицу, элементами которой являются функции распределения времени обработки задачи i в i-ом программном модуле при условии получения им управления от j-го программного модуля (MF_i=||F_i(t_jl)||);

• тип j-го программного модуля, с которого начинается полумарковский процесс задания i (j_Oi) и количество j-х программных модулей, реализуемых цепочкой j-х программных модулей (n_Oi).

Аналогичным способом определяются характеристики полумарковского процесса реализации обмена. В качестве исходной информации задаются:

• матрица вероятностей следования друг за другом MDB_jk (Mq_j=||q_jks||);

• матрица, элементами которой являются функции распределения объёмов информации при выполнении MDB_js при условии того, что перед этим использовался модуль MDB_jk (МФ_j=||F_j(V_objs)||);

• тип MDB_jk, с которого начинается обращение к базе данных (k_O), и количество MDB_jk, реализуемое при данном обращении j-го программного модуля к базе данных (m_Oj).

4.2 Особенности организации имитационного эксперимента

Динамика выполнения задач пользователей на оборудовании узла вычислительной системы отражается последовательностью j-х программных модулей и имеет вероятностный характер. Каждый j-й программный модуль узла захватывает ресурс центрального процессора, часть ресурса оперативной памяти (V_oni) и обращается к внешней памяти (HDD). Ресурс центрального процессора всегда выделяется j-м программным модулем полностью. Распределение ресурса центрального процессора организует операционная система. Ресурс центрального процессора распределяется по всем j-м программным модулям и для его выделения на определённый квант времени (Δt) используется система управляющих сигналов, формируемых по заявкам, поступающим от j-х программных модулей. Внешняя память моделируется как место размещения базы данных, и поэтому выделение ресурса внешней памяти для j-х программных модулей осуществляется до завершения выполнения задания. Функционирование устройств информации ввода вывода и модуля вывода информации моделируются как обычные устройства массового обслуживания с дисциплиной FIFO.

Время, затраченное на выполнение задания i, обозначим через Т_жi. Причём, в Т_жi включается сумма времени обслуживания задачи i на всех устройствах вычислительной системы, а также сумма времён издержек выполнения запросов заданий из-за занятости требуемых ресурсов другими задачами.

Целью моделирования вычислительного процесса в вычислительных системах является минимизация за счёт оптимизации порядка входа заданий рабочей нагрузки в вычислительной системе при неизменном составе ресурсов системы. Для получения оптимальной последовательности задач рабочей нагрузки необходимо знать: перечисленные ранее характеристики полумарковского представления процесса решения задач; ресурсные характеристики вычислительной системы; возможные реакции вычислительной системы на задания рабочей нагрузки с целью подсчёта времени обработки i-го задания в вычислительной системе.

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

Поскольку каждое задание использует ресурс вычислительной системы вероятностным образом, то для расчёта наиболее вероятного времени обработки узлом вычислительной системы i-го задания T_жi, а также коэффициентов загрузки центрального процессора (η_CPU) и внешней памяти (η_HDD) используется метод Монте-Карло. Количество реализаций (N) i-го задания i=1,…, n в вычислительной системе определяется из точности моделирования ( ) для получения оценок вектора (Т_жi, η_CPUi, η_HDDi). По окончании N реализаций имитационного эксперимента всех n заданий рабочей нагрузки получается матрица для каждого отклика (Т_жi, η_CPUi, η_HDDi). Методика расчёта компонент этого вектора реализуется следующей последовательностью шагов.