Оценка эффективности параллельного алгоритма марковской модели кластерной системы
Авторы: Фельдман Л.П., Юсков А.Г.
Источник: Девятая Международная конференция по Неравновесным процессам в соплах и струях (NPNJ’2012)
В настоящее время широкое распространение получили кластеры различной архитектуры. По совместному использованию дискового пространства их можно классифицировать следующим образом: с совместным использованием дискового пространства и без предоставления доступа к ресурсам [1].
На основании методик [2,3] построены дискретные марковские модели кластеров с совместным использованием дискового пространства, так как дискретные марковские модели по сравнению с непрерывными отражают работу вычислительной системы более точно.
Для кластера без предоставления доступа к ресурсам (см. рис. 1) построен параллельный алгоритм дискретной марковской модели (см. рис. 2).
Рисунок 1 – Структура кластера без предоставления доступа к ресурсам
Теоретическое ускорение параллельного алгоритма стремится к количеству процессов, а эффективность – к единице. Эффективность параллельного алгоритма, реализованного на кластере, также приближается к единице (см. рис. 3), но медленнее теоретического из-за несовершенной коммуникации (в частности, использование последовательного коммуникатора и топологии вычислительных модулей «звезда»).
Рисунок 2 – Схема параллельного алгоритма Марковской модели
Используя стационарные вероятности можно вычислить основные характеристики вычислительной среды: загрузки устройств; среднее число занятых устройств в s-м узле; среднее число задач, находящихся в s-м узле; среднее числo задач, находящихся в очереди к s-му узлу; средние времена пребывания и ожидания в s-м узле; средние времена пребывания и ожидания в системе [2].
Если анализируется конкретный вид кластера для решения определенного класса задач, то с помощью этих характеристик можно определить эффективность вычислительной среды (в зависимости от критерия: равномерная загрузка всех узлов, минимальное время отклика и т.д.).
Для подбора оптимального коэффициента мультипрограммирования можно использовать методику [4], в которой предлагается критерий сбалансированности, составляющие которого цена простоя оборудования и штраф за задержку выполнения запроса.
Рассмотренные в [4] способы оптимизации состава и структур высокопроизводительных ВС можно использовать для проектирования ВС, причем при большом коэффициенте мультипрограммирования – только численным (градиентным) или c использованием метода средних.
Рисунок 3 – Зависимость эффективности параллельного алгоритма от размерности вычисляемой задачи
Таким образом, использование вероятностных моделей при проектировании, эксплуатации и оптимизации вычислительных систем позволяет вырабатывать рекомендации по рациональному использованию ресурсов этой вычислительной среды.
Список использованной литературы
1. Спортак М., Франк Ч., Паппас Ч. и др. Высокопроизводительные сети. Энциклопедия пользователя.-К.:«ДиаСофт», 1998.-432с.
2. Фельдман Л.П., Михайлова Т.В. Оценка эффективности кластерных систем с использованием моделей Маркова. //Известия ТРТУ. Тематический выпуск: Материалы Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности». – Таганрог: ТРТУ, 2002. – №2 (25). – С. 50–53.
3. Фельдман Л.П., Михайлова Т.В., Ролдугин А.В. Реализация параллельного алгоритма построения Марковских моделей// Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка (ІКОТ - 2009), випуск 10 (153): - Донецьк:ДонНТУ, 2009. - С. 17-20.
4. Фельдман Л.П., Михайлова Т.В. Способы оптимизации состава и структуры высокопроизводительных вычислительных систем //Научные труды Донецкого государственного технического университета. Серия «Информатика, кибернетика и вычислительная техника»(ИКВТ-2001).- Донецк: ДонГТУ.- 2000. C. 80-85.