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

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

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

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

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

· матрица вероятностей следования друг за другом MDBjk (Mqj=||qjks||);

· матрица, элементами которой являются функции распределения объёмов информации при выполнении MDBjs при условии того, что перед этим использовался модуль MDBjk (МФj=||Fj(Vobjs)||);

· тип MDBjk, с которого начинается обращение к базе данных (kO), и количество MDBjk, реализуемое при данном обращении j-го программного модуля к базе данных (mOj).

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

Динамика выполнения задач пользователей на оборудовании узла вычислительной системы отражается последовательностью j-х программных модулей и имеет вероятностный характер. Каждый j-й программный модуль узла захватывает ресурс центрального процессора, часть ресурса оперативной памяти (Voni) и обращается к внешней памяти (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) по методу Монте-Карло будет сформировано три матрицы, компонентами которой будут пары значений:

M1ih=||(MTжih, DTжih)||; M2ih=||(M?CPUih, DCPUih)||; M3ih=||(M?HDDih, D?HDDih)||.

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

MYПАКh=, DYПАКh=,

где 0?i1 - весовой коэффициент задач i-го типа в пакете;

m0 - общее число задач в пакете;

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

YПАКh - отклик, содержание которого соответствует одной из характеристик вычислительного процесса в вычислительной системе (Тж, ?CPU, ?HDD).

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

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

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

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

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

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

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

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

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

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

Шаг n. Размерность множества STR равна 1 (|STR| = 1). На этом шаге осталось только одно задание, не вставленное в расписание. Оно вставляется в расписание последним, и вычисляется оценка T?(STRin), 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.

Страницы: 1, 2, 3, 4