Оптимизация распределения запросов в системе кластеров при сочетании аналитического и имитационного моделирования

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

4. Заявка на изобретение. Способ построения спектра «-мерных неразделимых цифровых сигналов. Гришенцев А. Ю., Коробейников А. Г. № 2 011 126 856, от 29. 06. 2011.
5. Смит С. Цифровая обработка сигналов. Практическое руководство для инженеров и научных работников. — М.: Додека-ХХ1, 2011. — 720 с.
6. Оппенгейм А., Шафер Р. Цифровая обработка сигналов. — 2-е изд. — М.: Техносфера, 2009. — 856 с.
7. Лайонс Р. Цифровая обработка сигналов. — 2-е изд. Пер. с англ. — М.: Бином пресс, 2009.- 656 с.
Гришенцев Алексей Юрьевич — Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, кандидат технических наук, доцент, tigerpost@ya. ru
УДК 004. 75
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ В СИСТЕМЕ КЛАСТЕРОВ ПРИ СОЧЕТАНИИ АНАЛИТИЧЕСКОГО И ИМИТАЦИОННОГО
МОДЕЛИРОВАНИЯ И. Ю. Голубев, В.А. Богатырев
Предложена многоэтапная процедура оптимизации распределения потока запросов между кластерами вычислительной системы, использующая аналитическое и имитационное моделирование. Процедура позволяет найти оптимальную долю перераспределяемого потока запросов при различных законах распределения интервалов между поступающими в систему запросами и времени их обслуживания.
Ключевые слова: распределение нагрузки, имитационное моделирование, кластер, оптимизация.
Введение
Основными требованиями, предъявляемыми к распределенным вычислительным системам, являются их надежность, отказоустойчивость и производительность [1]. Высокая отказоустойчивость и производительность распределенных систем достигается в результате эффективного распределения запросов (нагрузки) между их узлами [2−8]. В распределенных вычислительных системах, объединяющих множество кластеров, перераспределение запросов может осуществляться между узлами как одного, так и различных кластеров, соединенных через сеть. Во втором случае увеличиваются издержки на межмашинный обмен, но возрастают возможности балансировки загрузки и сохранения работоспособности при накоплении отказов, что обусловливает актуальность оптимизации процесса распределения запросов и разработки соответствующих процедур оптимизации. д
Постановка задачи
Цель представленной работы — разработка процедуры оптимизации распределения запросов между кластерами вычислительной системы при различных законах распределения интервалов между поступающими в систему запросами и времени их обслуживания.
Структура исследуемой распределенной вычислительной системы кластеров представлена на
рис. 1.
Рис. 1. Структура распределенной вычислительной системы
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ В СИСТЕМЕ КЛАСТЕРОВ…
В системе имеется M локальных кластеров (по n серверов в каждом) и группа из m общедоступных серверов (общий кластер), обеспечивающая возможность адаптации системы к перегрузкам отдельных локальных кластеров в случае отказов входящих в их состав серверов или к возрастанию потока запросов к локальным кластерам. Компьютеры кластеров связывает сеть, включающая N резервированных коммутационных узлов (маршрутизаторов или коммутаторов). Распределение потока запросов осуществляется диспетчерами (Д), направляющими запросы на выполнение внутри кластера или через сеть в общий кластер.
Ставится задача оптимизации процесса распределения потока запросов между кластерами при различных законах распределения интервалов между поступающими в систему запросами и времени их обслуживания. В результате оптимизации распределения запросов для заданной структуры системы требуется найти их долю gt, перераспределяемую через сеть в общий кластер, при которой достигается минимум времени пребывания запросов T в системе кластеров. Поиск проводится для заданных вариантов значений интенсивностей запросов (kt) и их вероятностей (b,).
Оптимизация процесса распределения запросов
При проектировании вычислительных систем применяется как аналитическое, так и имитационное моделирование. Результаты аналитического моделирования при законах распределения интервалов между поступающими в систему запросами и времени их обслуживания общего вида могут иметь существенную погрешность, а имитационное моделирование не ориентировано на решение оптимизационных задач и требует значительного времени и ресурсов компьютера для проведения имитационных экспериментов [9].
Для решения оптимизационной задачи, если законы распределения интервалов между поступающими в систему запросами и времени их обслуживания — не экспоненциальные, предлагается комбинированный подход, предполагающий совместное применение аналитических и имитационных моделей.
В рамках комбинированного подхода разработана процедура оптимизации распределения запросов, включающая следующие этапы:
— предварительное определение оптимальной доли перераспределяемых через сеть запросов в предположении простейшего потока запросов и экспоненциального распределения времени обслуживания с использованием аналитического моделирования-
— уточнение результатов оптимизации на основе проведения имитационных экспериментов в области значений, полученных в ходе аналитического моделирования.
Если законы распределения интервалов между поступающими в систему запросами и времени их обслуживания известны, то эксперименты проводятся в условиях соответствующих законов распределения- в противном случае эксперименты проводятся при варьировании законов распределения нагрузочных параметров- решение определяется по среднему результату или по известным критериям принятия решений.
Аналитическая модель системы с перераспределением запросов
При оптимизации на основе аналитического моделирования воспользуемся результатами работы [4], в которой показана эффективность динамической оптимизации процесса перераспределения запросов между кластерами вычислительной системы.
Критерий оптимальности определен как
T = min? b, T (gt, к,),
(а) ~п
f ,
(
T (g, к,) = g,
1 — g tktv0/ n
+(1 — а)
2vi
1 — ((1 — g,) + ?) 2к,-vi / N 1 — ((1 — gt) + ?) к,. V2 / n
Здесь h — число возможных значений интенсивности входного потока- v0, v1, v2 — средние времена выполнения запросов в серверах локального кластера, в коммутационных узлах и в серверах общего кластера. Нагрузка общедоступного кластера от множества локальных кластеров моделировалась потоком запросов с интенсивностью Л,=?k, N — число (кратность резервирования) коммутационных узлов в сети, через которые возможно перераспределение запросов.
Оптимизация проводилась для t = 0, 1,…, h и при условии стационарности:
(Vo /n & lt- 1) л (((1 — gt) + ?) 2k* /N & lt- 1) л (((1 — gt) + ?) kv /m & lt- 1).
В предположении простейшего потока запросов и экспоненциального распределения времени обслуживания определяется зависимость значений доли перераспределяемых через сеть запросов gt от интенсивности запросов kt, при которой среднее время пребывания запросов в системе минимально [4].
В результате оптимизации на аналитической модели найден [4] вектор значений доли перераспределяемых запросов (0,721- 0,494- 0,456- 0,446- 0,446- 0,451).
Построение имитационной модели
На втором этапе оптимизации в среде AnyLogic 6 построена имитационная модель рассматриваемой системы, изображенная на рис. 2.
Параметры модели
Q timeObrabotki
Диспетчер запросов
Q L1 0 И
QL2 (3 ?1
О L3 С? рз
Ф L4 (у Р4
(c)L5 0Р5
О L6 0 Р6
-д out 5erver32
out servers
-H out server^
out server35
-0 out serverB6
Рис. 2. Создание имитационной модели
Серия оптимизационных экспериментов проведена в области значений, полученных в результате аналитического моделирования, при следующих законах распределения интервалов между поступающими в систему запросами: экспоненциальный закон- равномерный закон- закон Эрланга 2-го порядка- гиперэкспоненциальный закон (с коэффициентом вариации 1,202).
Оптимизация проведена для п = 10 шт., N = 5 шт., т = 30 шт.- у0 = 10 с, VI = 1 с, v2 = 10 с, в = 1. Варианты возможных значений интенсивностей запросов и их вероятности представлены векторами (0,1- 0,3- 0,5- 0,7- 0,9- 1,1) и (0,1- 0,1- 0,15- 0,15- 0,2- 0,3), а вероятности соответствия закона распределения интервалов между поступающими в систему запросами моделируемым законам — (0,2- 0,25- 0,25- 0,3).
Сравнение аналитической и имитационной моделей
Результаты анализа моделей при экспоненциальном распределении интервалов между поступающими в систему запросами и времени их обслуживания представлены на рис. 3, а, б. Кривые 1 соответствуют интенсивности входного потока 0,1 с-1, кривые 2 — 0,3 с-1, кривые 3 — 0,5 с-1, кривые 4 — 0,7 с-1, кривые 5 -0,8 с-1. Из представленных графиков видно, что существует оптимальное значение доли запросов (§), перераспределяемых через сеть на выполнение в общий кластер, и для построенных моделей оно совпадает.
а б
Рис. 3. Среднее время пребывания запроса в системе: аналитическая модель (а) и имитационная модель (б). Кривые 1−5 соответствуют интенсивности входного потока 0,1- 0,3- 0,5- 0,7- 0,8 с-1.
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ В СИСТЕМЕ КЛАСТЕРОВ.
Результаты второго этапа оптимизации представлены в таблице. Согласно критерию Гермейера, оптимальным является решение в строке 4.
№ Вектор значений доли перераспределяемых запросов (g) Среднее время пребывания запросов в системе T, c
Закон распределения интервалов между поступающими в систему запросами Результат (критерий Гермейера)
Экспоненциальный Равномерный Эрланга Гиперэкспоненциальный
1 (0,716- 0,508- 0,454- 0,453- 0,447- 0,464) 20,985 20,748 20,786 21,433 6,4299
2 (0,72- 0,484- 0,464- 0,47- 0,445- 0,458) 21,101 20,722 20,917 21,378 6,4134
3 (0,738- 0,576- 0,452- 0,455- 0,457- 0,459) 21,013 20,807 20,76 21,369 6,4107
4 (0,724- 0,505- 0,485- 0,467- 0,468- 0,475) 21,052 20,739 20,883 21,367 6,4101
Таблица. Результаты второго этапа оптимизации
На рис. 4 показаны отклонения е результатов, полученных в ходе имитационных экспериментов, от результатов аналитического моделирования: кривая 1 соответствует серии экспериментов для экспоненциального закона распределения интервалов между поступающими в систему запросами- кривая 2 -для равномерного закона- кривая 3 — для закона Эрланга, кривая 4 — для гиперэкспоненциального закона.
Максимальное отклонение результатов аналитического и имитационного моделирования при рассмотренных законах распределения интервалов между поступающими в систему запросами на всей рассматриваемой области значений интенсивности входящего потока запросов составило 16,6%, а среднее отклонение — 2,9% (0,082 и 0,015 в абсолютных значениях соответственно). Сужение области поиска оптимального значения до двух максимальных отклонений (0,164) на этапе уточнения результатов позволило сократить время, затраченное на имитационное моделирование, в 6 раз. ?, %
i 3%
/ ! / / *
1 / / / '- 4
/ г (fTi* --- 1
ОД 0,3 0,5 0,7 0,9 1ДА. 1/С
Рис. 4. Отклонения результатов имитационного моделирования. Кривые 1−4 соответствуют экспоненциальному, равномерному, эрланговскому, гиперэкспоненциальному законам распределения интервалов между поступающими в систему запросами
Заключение
Предложена процедура оптимизации процесса распределения потока запросов между кластерами вычислительной системы при различных законах распределения интервалов между поступающими в систему запросами и времени их обслуживания.
Предложенная процедура оптимизации предусматривает выполнение этапа оптимизации на основе аналитического моделирования для простейшего входного потока и экспоненциального распределения времени обслуживания и уточнение результатов моделирования на основе имитационных экспериментов при реальных законах распределения интервалов между поступающими в систему запросами и длительности их обслуживания.
Литература
1. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. — СПб: Питер. — 2003. — 877 с.
2. Gaeta M., Konovalov M., Shorgin S. Development of mathematical models and methods of task distribution in distributed computing system // Reliability: Theory & amp- Applications. — 2006. — V. 1. — № 4. — P. 16−21.
О.А. Кузнецова
3. Богатырев В. А., Богатырев С. В. К анализу и оптимизации серверных систем кластерной архитектуры с балансировкой нагрузки // Приборы и системы. Управление, контроль, диагностика. — 2010. — № 2. -С. 4−9.
4. Bogatyrev V.A., Bogatyrev S.V., Golubev I. Yu. Optimization and the Process of Task Distribution between Computer System Clusters // Automatic Control and Computer Sciences. — 2012. — V. 46. — № 3. — P. 103−111.
5. Богатырев В. А. К повышению надежности вычислительных систем на основе динамического распределения функций // Изв. вузов. Приборостроение. — 1981. — С. 62−64.
6. Богатырев В. А. Децентрализованное динамическое распределение запросов в многомашинных вычислительных системах // Электронное моделирование. — 1994. — Т. 16. — № 3. — С. 38.
7. Богатырев В. А., Богатырев С. В. Критерии оптимальности многоустойчивых отказоустойчивых компьютерных систем // Научно-технический вестник СПбГУ ИТМО. — 2009. — № 5 (63). — С. 92−97.
8. Богатырев В. А. Оптимальное резервирование системы разнородных серверов // Приборы и системы. Управление, контроль, диагностика. — 2007. — № 12. — С. 30−36.
9. Алиев Т. И. Основы моделирования дискретных систем: Учебное пособие. — СПб: СПбГУ ИТМО. -2009. — 363 с.
Голубев Иван Юрьевич — Санкт-Петербургский национальный исследовательский университет
информационных технологий, механики и оптики, аспирант, www. golubev@mail. ru
Богатырев Владимир Анатольевич — Санкт-Петербургский национальный исследовательский университет
информационных технологий, механики и оптики, доктор технических наук, профессор, Vladimir. bogatyrev@gmail. com
УДК 629.7. 017
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОЦЕНКИ НАДЕЖНОСТИ ИЗДЕЛИЯ АВИОНИКИ С «ХОЛОДНЫМ» РЕЗЕРВОМ О.А. Кузнецова
Построена математическая модель оценки безотказности изделия авионики, представленного в виде нагруженного дублирования с дополнительным «холодным» резервом. Модель учитывает неполный контроль работоспособности входящих устройств и время задержки во включении «холодного» устройства. Выполнен сравнительный анализ вариантов структурного резервирования.
Ключевые слова: надежность, безотказность, «холодный» резерв, контроль работоспособности.
Введение
Учитывая требования по отказобезопасности гражданской авиации в части недопущения возникновения на борту самолета сложной ситуации, показатель отказобезопасности аппаратуры самолета (вероятность отказа за 1 ч полета) должен быть не выше 10−5. Для обеспечения указанного требования, учитывая современные показатели безотказности авионики, в проектных решениях структур изделий необходимо предусматривать не менее чем двукратное резервирование. Структурное резервирование в простейшем варианте может быть реализовано в виде постоянно включенной группы изделий, резервирующих друг друга по выполняемым функциям, либо с применением «холодного» резерва. В обоих вариантах резервирования равной кратности резервированные группы состоят из одного основного и двух резервирующих изделий, отличающихся тем, что в одной из групп второе резервное изделие до момента возникновения первого отказа находится в выключенном состоянии, т. е. используется в режиме «холодного» резерва (рис. 1). Применение избыточности как способа повышения надежности имеет широкое применение при проектировании сложных технических систем [1−4]. Учитывая, что за время полета ремонт возникших отказов авионики не может быть выполнен сразу после обнаружения, на первый взгляд, для рассматриваемой резервированной группы с «холодным» резервом необходимо было бы воспользоваться моделью оценки надежности невосстанавливаемых систем из справочников [1, 2]. Но эта модель позволяет оценить надежность системы без учета того, что у основного устройства, помимо «холодного» резерва, имеется нагруженный резерв. При попытке заменить группу с нагруженным резервом на нерезервированное устройство с аналогичным показателем безотказности возникает трудность в использовании предлагаемой модели, так как интенсивности отказов входящих устройств становятся неравными (что противоречит исходным условиям применения модели [1, 2]). Наличие же задержки во включении «холодного» резерва ведет к еще большему затруднению, так как в этом случае предлагается перейти к рассмотрению восстанавливаемой системы без резерва, у которой время восстановления равно времени переключения на резерв. Учитывая изложенные недостатки имеющейся модели, для анализа применения «холодного» резерва возникла необходимость построения более точной модели оценки вероятности отказа группы с «холодным» резервом, учитывающей время задержки включения в работу «холодного» резерва и полноту контроля работоспособности устройств в резервных группах, так как включение «хо-

ПоказатьСвернуть
Заполнить форму текущей работой