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

• Автор: Румянцев, Александр Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Петрозаводск
• Количество страниц: 109 с. : ил.

Содержание
Введение

Глава 1. Классические модели многопроцессорных вычислительных систем.

1.1. Система аОт .

1.2. Стационарность и возвратность по Харрису.

1.3. Конечность моментов вектора нагрузки.

1.4. Многопроцессорные системы и распределения с тяжелым хвостом

Глава 2. Распределения с тяжелым хвостом.

2.1. Определение классов

2.2. Замкнутость классов

2.3. Статистические аспекты моделирования распределений с тяжелым хвостом

Глава 3. Многопроцессорные системы, в которых заявке требуется случайное число процессоров.
3.1. Системы с независимым освобождением процессоров
3.2. Системы без ожидании.
3.3. Системы с бесконечным числом процессоров и групповым поступлением .
3.4. Модель вычислительного кластера
Глава 4. Численный эксперимент
4.1. Кластер ЦКП КарНЦ РАН.
4.2. Исследование маргинальных распределений
Заключение
Литература


Важным показателем качества обслуживания в МС является задержка задачи (время ожидания в очереди на обслуживание) и относительное замедление, рассчитываемое как отношение задержки ко времени вычисления задачи. В этой связи важной является задача прогнозирования развития системы и оценки влияния административного решения на показатели качества обслуживания, например, на среднее (или максимальное) время ожидания заявки в очереди. Наконец, отметим задачи, связанные с построением эффективных параллельных алгоритмов для вычисления на МС. Если степень параллелизма заявки может принимать несколько значений, то возникает задача аналитического описания ускорения, достигаемого на различном числе процессоров, для нахождения оптимального значения степени параллелизма []. Большой поток вычислительных задач и заранее неизвестное время выполнения задачи в МС приводят к необходимости использования вероятностных моделей для описания функционирования МС. Отметим, что параллельные вычисления в качестве основы для вероятностной модели впервые упомянуты в работе []. При этом, как правило, рассматривается следующая общая постановка задачи. В МС в случайные моменты времени ^ 1 поступает поток заявок. Заявке г требуется (случайное или детерминированное) число процессоров для выполнения заданий. В случае, когда задания внутри заявки независимы и могут начинать вычисления в разное время, говорят о приходе пачки заданий. Если Аг,- = 1, говорят о классической МС типа а/С/т. Если заявке с номером г одновременно требуется случайное число Д ^ 1 процессоров (т. МС с независимым освобооюдением процессоров [, | и МС с одновременным освобоэюдепием процессоров [, ]. В первом случае времена обслуживания на всех Д процессорах являются независимыми одинаково распределенными (н. Д процессорах используется одна и та же реализация времени обслуживания 5^ (т. Системы второго типа существенно более сложны для анализа []. Для таких систем известны лишь численные результаты [], а при отсутствии буфера — также некоторые аналитические результаты [, , 2]. Заметим, что модели с независимым освобождением процессоров пригодны для описания грид-систе-мы, в то время как одновременное освобождение более соответствует работе ВК. Вероятностные модели для времени ожидания в о черед Их Д заявки с номером г в классической системе С1/С/га, а также для вектора нагрузки 1Д = (ИД,. ИАП), состоящего из упорядоченной по возрастанию незавершенной работы на процессорах, впервые исследованы в работах [, ]. В предположении, что входной поток является процессом восстановления (величины 7* = ? Вопрос конечности моментов является особенно актуальным в связи с обнаружением распределений с тяжелым хвостом в процессах, описывающих функционирование МС, см. Распределения с тяжелым хвостом могут характеризоваться бесконечными значениями моментов с. Отдельно следует отметить модели, но связанные непосредственно с описанием ВК, однако позволяющие в той или иной степени отразить основные особенности его функционирования. Так, в предположении т шах,>1 (т. МС может быть описано моделью С/С/со с бесконечным числом процессоров и групповым поступлением заданий. Применимость таких моделей для описания МС с большим числом процессоров обсуждается в работах [1, 2]. В этой связи отметим работы [, ), в которых рассмотрены модели типа СГ/О/оо с групповым поступлением и независимым освобождением процессоров. Отмстим, что анализ МС, допускающих групповое обслуживание заявок с одновременным началом обслуживания, особенно труден, т. В данной работе выполнен анализ существующих моделей МС, приведены классические результаты, касающиеся стационарности и моментных свойств процесса, нагрузки МС. Основное внимание уделено новой модели на основе модели Кифера-Вольфовица для вектора нагрузки МС типа С1/С/щ, что позволяет обобщить известные результаты для модели, учитывающей существенные особенности функционирования ВК. Актуальность диссертационной работы подтверждается большим вниманием, которое уделяется моделям МС как при проведении теоретических исследований, так и при внедрении результатов моделирования в технологические процессы.