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

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

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

M_1ih=||(MT_жih, DT_жih)||; M_2ih=||(Mη_CPUih, D_CPUih)||; M_3ih=||(Mη_HDDih, Dη_HDDih)||.

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

MY_ПАКh= , DY_ПАКh= ,

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

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

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

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

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

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

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

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

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, которая и будет итоговой оценкой (временем) обработки заданий пакета рабочей нагрузки при соответствующем ей расписании.

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

Заключение

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

Изучив и проанализировав ряд научных статей, посвящённых данной проблеме, следует отметить, что наиболее простым и распространённым способом её решения является метод ветвей и границ. Было установлено, что большинство существующих оригинальных алгоритмов являются модификациями данного метода. Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.

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

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

Список источников

1. Галиев Р.С. Экспериментальные методы исследования вычислительного процесса ЕС ЭВМ. – Дис., Гомель, 1987.

2. Демиденко О.М., Максимей И.В., Имитационное моделирование взаимодействия процессов в вычислительных системах. – Мн.: Белорусская наука, 2000.

3. Корбут А.А., Финкельштейн Ю.Ю., Дискретное программирование. – М.: Наука, 1969.

4. Максимей И.В., Серегина В.С. Задачи и модели исследования операций. Часть 2. – Гомель, 1999.

5. Максимей И.В. Имитационное моделирование на ЭВМ. – М.: Радио и связь, 1988.

6. Грек В.В., Максимей И.В. Стандартизация и метрология систем обработки данных. – Мн.: Высшая школа, 1994.

7. Бышик Т.П., Маслович С.Ф., Мережа В.Л. О построении оптимальной последовательности заданий на обработку в узле ЛВС // Известия Гомельского государственного университета имени Ф. Скорины. – 2002. – №6 (15) – С. 7–9.

8. Кузин Л.Т. Основы кибернетики. Том 1. – М.: Энергия, 1973.

9. Land A.H., and Doig A.G. An automatic method of solving discrete programming problems. Econometrica. v28 (1960), pp.497–520.

10. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research. v11 (1963), pp. 972–989.