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

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

· матрица вероятностей следования друг за другом 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). Методика расчёта компонент этого вектора реализуется следующей последовательностью шагов.

Шаг 1. Нахождение времени решения задач (Т_ж_i) и определение коэффициентов загрузки (η_CPU_,η_HDDi) для различных уровней мультипрограммирования. Заметим, что обычно число уровней мультипрограммирования редко превышает величину 5, поэтому в нашем исследовании будем ориентироваться на максимальный уровень мультипрограммирования равный 5. Алгоритм реализации шага 1 основан на методе Монте-Карло для каждого уровня мультипрограммирования.

После N реализаций имитационного эксперимента с моделью вычислительного процесса для h-го уровня мультипрограммирования (h-й вариант вычислительного процесса, h=0,…, 5) по методу Монте-Карло будет сформировано три матрицы, компонентами которой будут пары значений:

M₁_ih=||(MT_ж_ih, DT_ж_ih)||; M₂_ih=||(Mη_CPUih, D_CPUih)||; M₃_ih=||(Mη_HDDih, Dη_HDDih)||.

Шаг 2. По матрицам M₁_ih, M₂_ih, M₃_ih для h-го уровня мультипрограммирования определяют математические ожидания и дисперсии вычислений каждого из откликов: времени решения всего пакета (МТ_ПАК_h, МТ_ПАК_h); общей загрузки центрального процессора (Mη_HDDh, Dη_HDDh); общей загрузки внешней памяти (Mη_HDDh, Dη_HDDh) по формулам:

MY_ПАК_h=

, DY_ПАК_h=

где 0

δ_i1 – весовой коэффициент задач i-го типа в пакете;

m₀ – общее число задач в пакете;

m_i – количество задач i-го типа в пакете;

Y_ПАК_h – отклик, содержание которого соответствует одной из характеристик вычислительного процесса в вычислительной системе (Т_ж, η_CPU_,η_HDD).

4.3 Модификация последовательности решения задач в пакете по методу ветвей и границ

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

1. Все задания пакета рабочей нагрузки имеют один и тот же тип (i=1).

2. В пакете имеются различные типы заданий и количество типов (1<i<m₀).

3. Все задания пакета имеют различные типы (i=m₀).

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

Шаг 0. Вычисляется общее время обработки всего ещё не упорядоченного пакета Tξ(STR).

Шаг 1. Размерность множества STR равна n (|STR| = n). На первом уровне ветвления вычисляются оценки Tξ(STR_i¹), i=1,…, n. Они вычисляются при условии, что i-е задание начинает обрабатываться первым, а оставшиеся n-1 заданий входят в расписание по мере возрастания Т_ж_i. Среди этих оценок выбирается оценка с наименьшим Tξ(STR_i¹) и соответствующее i-е задание (i₁) вставляется в расписание первым. При этом остальные оценки отбрасываются и соответствующие им порядки следования задач заданий считаются заведомо неоптимальными.

Шаг 2. Размерность массива STR равна n-1 (|STR| = n-1). Этот уровень ветвления осуществляется при условии, что одно из заданий i (i₁) уже вставлено в расписание для обработки первым. Для остальных n-1 заданий, ещё не вставленных в расписание, вычисляются оценки Tξ(STR_i²), i=1,…, n-1, при условии, что задание i загружается для обработки вторым, а оставшиеся n-2 заданий входят в расписание по мере возрастания Т_ж_i. Среди этих оценок выбирается оценка с наименьшим Tξ(STR_i²) и соответствующее i-е задание (i₂) вставляется в расписание вторым. При этом остальные оценки отбрасываются и соответствующие им порядки следования задач заданий считаются заведомо неоптимальными. В результате второго шага в оптимальное расписание будут вставлены уже два задания.

Шаг k (k>2). Размерность массива STR равна n-k+1 (|STR| = n-k+1). Этот уровень ветвления осуществляется при условии, что k-1 задание уже вставлено в расписание. Для остальных n-k+1 заданий, ещё не вставленных в расписание, вычисляются оценки Tξ(STR_i^k), i=1,…, n-k+1. Среди этих оценок выбирается оценка с наименьшим Tξ(STR_i^k) и соответствующее i-е задание (i_k) вставляется в расписание k-ым. При этом остальные оценки отбрасываются и соответствующие им порядки следования задач заданий считаются заведомо неоптимальными. В результате k-го шага в оптимальное расписание будут вставлены уже k заданий.

Шаг n. Размерность множества STR равна 1 (|STR| = 1). На этом шаге осталось только одно задание, не вставленное в расписание. Оно вставляется в расписание последним, и вычисляется оценка Tξ(STR_iⁿ), i=1, которая и будет итоговой оценкой (временем) обработки заданий пакета рабочей нагрузки при соответствующем ей расписании.

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

Заключение

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