Авторы: Фельдман Л.П., Юсков А.Г.
Источник: ІІІ міжнародна науково-технічна конференція студентів, аспірантів та молодих вчених "Інформаційні управляючі системи та комп'ютерний моніторінг" (ІУС та КМ - 2012), стр. 747-751
Фельдман Л.П., Юсков А.Г. Дискретная марковская модель кластера с совместным использованием дискового пространства. Предлагается марковская модель кластера с постоянным количеством задач, которая обобщает ранее моделированные модели аналогичных кластеров.
В современном мире существует большое количество задач, требующих применения мощных вычислительных систем (ВС).
Одним из примеров вычислительных систем с распределенной обработкой являются кластеры [1,2,3]. Кластерные вычислительные системы по критерию совместного использования дискового пространства классифицируются следующим образом: с совместным использованием дискового пространства и без предоставления доступа к ресурсам [4].
При проектировании и эксплуатации распределенных ВС возникает проблема рационального использования ресурсов вычислительной среды. Для эффективного решения этой проблемы используются непрерывные [5,6,7] или дискретные аналитические модели [8], и для каждого класса решаемых задач определяются основные параметры вычислительной среды.
Непрерывные модели являются менее трудоемкими и применяются для сложного класса исследуемых структур. Дискретная модель Маркова, в сравнении с непрерывной – более точно отражает работу вычислительной среды и позволяет эффективно распараллелить вычислительные структуры [9].
Анализ кластерных систем с помощью дискретной модели при большом количестве решаемых задач на ВС требует больших временных затрат, так как количество состояний дискретной Марковской модели комбинаторно возрастает при увеличении количества задач. В работе представлена марковская модель кластера с совместным использованием дискового пространства, которая является обобщением модели, представленной в [9].
В данной модели каждый узел в кластере имеет свою собственную память, все узлы используют дисковую подсистему. Узлы в кластере обращаются к дисковой подсистеме по системной шине. Вычислительные задачи равномерно распределяются по нескольким объединенным в сеть компьютерам.
В упрощенной структуре кластера с совместным использованием дискового пространства (см. рис. 1) время передачи данных по шине включили во время обслуживания на серверах и дисках, соответственно. Структура состоит из M рабочих станций пользователей, N1 серверов, выполняющие различные приложения, N2 дисков, на которых хранится база данных.
Представим серверы и диски приборами, время обслуживания которых имеет геометрическое распределение со средним параметром qi (i=1,…,N1+N2+1) – вероятностью завершения обслуживания заявки (соответственно, ri=1-qi – вероятность продолжения обслуживания заявки).
Управляющий сервер распределяет пользовательские заявки каждого из М пользователей и с вероятностью 
посылает запрос к одному из N1 серверов,
Рисунок 1 – Структурная схема кластера без предоставления доступа к ресурсам
которые, в свою очередь, обрабатывая этот запрос обращаются к одному из N2 дисков с вероятностью 
Предположим, что рассматриваемая вычислительная система – замкнутая, т.е. в системе обслуживается постоянное количество требований М.
Для построения дискретной модели такой вычислительной системы определим все возможные состояния. За состояние системы примем размещение М заявок по N1+N2+1 узлам
– количество задач в -ом узле (всего узлов N=N1+N2+1). Обозначим множество состояний через
Число L всевозможных состояний системы равно числу размещений M задач по N узлам и определяется по формуле:
Количество устройств в каждом узле задается вектором 
Определим переходные вероятности для каждой пары состояний 
, т.е. вероятности перехода из состояния Si, в котором она находилась на (k-1)-м шаге, в состояние Sj на k-м шаге.
Для произвольного состояния 
введем вектор 
, s-я компонента которого
определяет число загруженных устройств в s-м узле обработки задач. Для определения возможности перехода из произвольного состояния в произвольное состояние
найдем вектор
каждая компонента 
которого представляет изменение числа задач в s-ом узле.
Если >0, то на рассматриваемом переходе из узла s должны уйти минимум
задач. Если < 0, то в узел s должны прийти
|| задач. При любом переходе из
число задач, обслуженных s-м узлом обработки, не может быть больше 
, т.е.
Определим множество J номеров узлов обработки, в которых < 0, т.е.
Если 
, то величины 
определяют минимально возможное
число программ, которые поступают к тем узлам обработки, номера s которых принадлежат множеству J. Число программ, поступивших в
один из таких узлов s равно ||. Количество поступивших задач к главному серверу от серверов не может превышать количества работающих серверов
Аналогично, количество поступивших задач к дискам от серверов не может превышать количества работающих серверов
От серверного узла задачи поступают и к управляющему серверу, и к дискам, поэтому общее количество ушедших задач не превышает количества работающих серверов
Количество поступивших задач к серверам не превышает количества работающих дисков и задачи, поступившей от управляющего сервера
Если 
, то 
Рассмотрим частный случай:
N = 5 – количество устройств,
N1 = 2 – количество вычислительных серверов
N2 = 2 – количество дисков
M = 5 – количество задач.
Определим число L всевозможных состояний системы:
Переход 
возможен, если соблюдаются условия (6-9).
Рассмотрим случай i5=1 – управляющий сервер завершил обработку одной задачи, следовательно, обработка требуется на одном из вычислительных серверов.
Допустим, другие устройства продолжают обработку задач, и обмен не требуется, тогда вероятность перехода между двумя состояниями:
Рассмотрим второй вариант, когда i5=1 – управляющий сервер завершил обработку одной задачи, другие устройства также завершили обработку задач, следовательно, необходимо учесть возможность обмена задачами между вычислительными серверами и дисковыми устройствами.
Сформулируем условия формирования множества для обмена задачами:
Множество Is1 содержит номера вычислительных серверов, а множество Is2 – номера дисков, которые в данном такте могут завершить обработку задачи.
Обмен может быть осуществлен при условии (13):
Построим множество событий для обмена задачами:
Элемент множества I имеет следующий вид:
где l1 - номер серверного узла,
l2 - номер дискового узла.
Тогда вероятность перехода между двумя состояниями:
Рассмотрим случай i5=0, возможны три варианта обмена задачами:
1) между управляющим сервером и вычислительными серверами;
2) между вычислительными серверами и дисковыми устройствами;
3) между управляющим сервером и вычислительными серверами, а также вычислительными серверами и дисковыми устройствами.
Сформулируем условия формирования множества для обмена задачами:
Множество Is1 содержит номер управляющего сервера, Is2 – номера вычислительных серверов, а множество Is3 – номера дисков, которые в данном такте могут завершить обработку задачи.
Обмен может быть осуществлен при условии (21):
Построим множество событий для обмена задачами:
Элемент множества I имеет следующий вид:
где l1 – номер управляющего сервера,
l2 – номер серверного узла,
l3 – номер дискового узла.
Для определения вектора стационарных состояний надо решить систему линейных алгебраических уравнений (СЛАУ)
соответствующую рассмотренной марковской модели.
Основные характеристики моделируемой ВС определяются с использованием стационарных вероятностей [5].
Среднее число занятых устройств в s-м узле определяется по формуле:
Загрузка устройств определяется по следующей формуле:
Среднего числа задач, находящихся в s-м узле:
Среднее число задач, находящихся в очереди к s-му узлу:
Предложена обобщенная модель кластерной вычислительной системы с совместным использованием дискового пространства, которая может использоваться для повышения качества работы вычислительного кластера.
Алгоритм построения элемента матрицы переходных вероятностей и определения вектора стационарных вероятностей позволяет их легко распараллелить на многопроцессорные вычислительные структуры.
1. Шнитман В. Современные высокопроизводительные компьютеры. Информационно-аналитические материалы центра информационных технологий / В. Шнитман [Электронный ресурс]. Режим доступа: http://www.citforum.ru/hardware/svk/contents.shtml.
2. Corbalan J., Martorell X., Labarta J. Performance-Driven Processor Allocation //IEEE Transactions on Parallel and Distributed Systems, vol. 16, No. 7, July 2005, PP.599-611
3. Oleszkiewicz J., Xiao L., Liu Y. Effectively Utilizing Global Cluster Memory for Large Data-Intensive Parallel Programs //IEEE Transactions on Parallel and Distributed Systems, vol. 17, No. 1, Jan. 2006, PP.66-77
4. Спортак М., Франк Ч., Паппас Ч. и др. Высокопроизводительные сети. Энциклопедия пользователя. – К.: «ДиаСофт», 1998.-432с.
5. Авен О. И. и др. Оценка качества и оптимизация вычислительных систем. – М.: Наука, 1982.-464с.
6. Cremonesi P., Gennaro C. Integrated Performance Models for SPMD Applications and MIMD Architectures //IEEE Transactions on Parallel and Distributed Systems, vol. 13, No. 7, Jul. 2002, PP.745-757
7 Varki Е. Response Time Analysis of Parallel Computer and Storage Systems //IEEE Transactions on Parallel and Distributed Systems, vol. 12, No. 11, Nov. 2001, PP.1146-1161
8. Клейнрок Л. Вычислительные системы с очередями. – М.:Мир, 1979, 600с. Последовательно - параллельные вычисления: Пер. с англ. - М.: Мир, 1985.-456 с.
9. Фельдман Л.П., Михайлова Т.В. Параллельный алгоритм построения дискретной марковской модели /Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. /Под редакцией член-корреспондента РАН В.А. Сойфера. – Самара, 2004. – С. 249–255.