автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Методы расчета показателей и анализ эффективности функционирования большемасштабных распределенных вычислительных систем

На правах рукописи

ПАВСКИЙ КИРИЛЛ ВАЛЕРЬЕВИЧ

МЕТОДЫ РАСЧЕТА ПОКАЗАТЕЛЕЙ И АНАЛИЗ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ БОЛЫНЕМАСШТАБНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность: 05.13.15 - Вычислительные машины, комплексы и компьютерные сета

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

2 и ЬлР?0М

Новосибирск — 2013

005546084

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте физики полупроводников им. А.В. Ржанова Сибирского отделения РАН (ИФП СО РАН)

Научный консультант — доктор технических наук профессор

член-корреспондент РАН

заслуженный деятель науки РФ_

| Хорошевский Виктор Гаврилович

Официальные оппоненты: Каляев Игорь Анатольевич

доктор технических наук, профессор, член-корреспондент РАН

ФГАОУ ВПО «Южный федеральный университет», Научно-исследовательский институт

многопроцессорных вычислительных систем им. Академика А. В. Каляева, директор;

Попков Владимир Константинович

доктор физико-математических наук, профессор ФГБУН Институт вычислительной математики и математической геофизики СО РАН, Лаборатория прикладных систем, главный научный сотрудник;

Зыкин Сергей Владимирович

доктор технических наук, профессор ФГБУН Институт математики им. C.JI. Соболева СО РАН, Омский филиал, Лаборатория методов представления и преобразования информации, заведующий лабораторией.

Ведущая организация — Федеральное государственное унитарное предприятие «Научно-исследовательский институт «Квант»

Защита состоится 17 апреля 2014 г. в 15.00 часов на заседании Диссертационного совета Д 219.005.02 при ФГОБУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625; e-mail: sovet@sibsutis.ru.

С диссертацией и авторефератом можно ознакомиться в библиотеке ФГОБУ ВПО «СибГУТИ», на официальном сайте Минобрнауки РФ (vak.ed.gov.ru), на сайте СибГУТИ (http://www.sibsutis.ru/?item_id=259).

Автореферат разослан «¿»7 » Ученый секретарь

диссертационного совета Д 219.005.02 кандидат технических наук

2014 г.

И.И. Резван

Общая характеристика работы

Актуальность темы. Распределенные вычислительные системы (ВС) относятся к высокопроизводительным вычислительным средствам. Архитектура распределенных ВС представляется в виде композиции множества элементарных машин или процессоров, соединенных телекоммуникационной сетью. В таких системах все основные ресурсы (не только арифметико-логические устройства, но и память, и средства управления) являются и логически, и технически распределенными. Количество ядер в таких ВС может достигать нескольких миллионов. Именно поэтому подобные ВС относят к масштабируемым и большемасштабным. Проектирование и развитие распределенных большемасштабных вычислительных систем, в ряду вычислительных средств высокой производительности, занимает одно из приоритетных направлений науки и техники.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские, российские и зарубежные учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков,

B.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, И.А. Каляев, JI.H. Королев, В.Г. Лазарев,

C.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. -Яненко, S. Cray, D. Slotnick, I. Foster, M. Flynn, С. Kesselman, J. Dongara, L. Lamport, M. Livny и другие.

По архитектурным возможностям промышленные ВС достаточно близки к вычислительным системам с программируемой структурой, концептуальные основы построения которых сформировались в Сибирском отделении РАН к началу 70-х годов 20 столетия.

Примером отечественных ВС с программируемой структурой могут служить: первая система "Минск - 222" (1965 г.); мультиминимашинные ВС МИНИМАКС (1975 г.) и СУММА (1976 г.); мультипроцессорные живучие системы семейства МИКРОС (МИКРОС-1, 1986 г., МИКРОС-2, 1992 г. МИКРОС-Т 1998 г.); суперкомпьютеры семейства МВС (МВС-100 и МВС-1000, 1999 г.).

Объединение ВС в пространственно распределенную среду рассматривается как одна из альтернатив построения сверхпроизводительных средств обработки информации. К ним относятся большемасштабные вычислительные системы, важньм архитектурным свойством которых является надежность, живучесть. Отказ или восстановление элементарной машины может приводить лишь к изменению производительности ВС и не допускать аварийного завершения решения задач пользователей. Для таких систем важна и организация функционирования в основных режимах (режим решения сложной задачи, обработки наборов задач, обслуживание потоков задач).

Поэтому перспективным является разработка средств анализа и оптимизации живучего функционирования распределенных ВС.

В силу своей болыыемасштабности современные распределенные ВС требуют создания сложных многопараметрических моделей их функционирования, а это приводит к тому, что оценка меры адекватности моделей становится трудновыполнимой. Построение же простых моделей приводит, скорее, к качественным, чем количественным оценкам функционирования систем. Следовательно, создание одновременно простых и эффективных математических моделей с параметрами, основанными на качественной или достоверной, потенциально возможной, статистике, является актуальным.

Цель и задачи исследования

Целью исследования является разработка средств анализа эффективности функционирования большемасштабных распределенных (однородных) вычислительных систем.

Для достижения цели поставлены следующие задачи исследования:

• разработать подходы для расчета показателей эффективности функционирования большемасштабных распределенных (однородных) вычислительных систем;

• построить модели для расчета показателей надежности и живучести большемасштабных распределенных (однородных) вычислительных систем;

• построить модели для расчета показателей осуществимости решения задач на большемасштабных распределенных (однородных) вычислительных системах в моно и мультипрограммных режимах;

• получить формулы или эффективные оценки для показателей эффективности функционирования ВС, применимые для инженерных расчетов.

Методы исследования. Для решения поставленных задач использовались методы теории вероятностей, случайных процессов, массового обслуживания (ТМО), математического анализа, теории функции комплексного переменного. Экспериментальные исследования осуществлялись путём моделирования на пространственно-распределённой мультикластерной ВС.

Научная новизна. Предложены новые и развиты имеющиеся стохастические модели функционирования распределенных (однородных) вычислительных систем, позволившие рассчитать показатели надежности, живучести и осуществимости решения задач на распределенных ВС.

1. Разработана методика применения случайного процесса, описывающего функционирование распределенных ВС со структурной избыточностью.

2. Получена функция распределения времени нахождения распределенных ВС в состоянии низкой производительности.

3. Разработан алгоритмический и программный инструментарий анализа эффективности решения задач на распределенных ВС.

Практическая значимость и реализация работы. Разработанные модели и методы, полученные формулы и алгоритмы являются практическим

инструментом анализа эффективности функционирования большемасштабных распределенных (однородных) ВС.

Основные результаты исследований нашли применение в работах по развитию программного обеспечения для пространственно-распределенной мультикластерной ВС Центра параллельных вычислительных технологий (ЦПВТ) ФГОБУ ВПО «СибГУТИ» и Лаборатории ВС ИФП СО РАН. Основные этапы работы выполнены в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (ГК № 02.514.11.0002, Разработка программных технологий для развития российского сегмента Грид систем параллельного программирования, систем компьютерной графики) и «Научные и научно-педагогические кадры инновационной России» (ГК № 02.740.11.0006, Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ»; грант в виде субсидий №8228, Разработка алгоритмических и программных средств моделирования наноструктур с квантовыми точками на информационно-вычислительных системах), при поддержке грантов Российского фонда фундаментальных исследований №№ 97-01-00883, 99-07-90206, 00-01-00126, 01-01-06246, 02-01-06518, 02-07-90379, 05-07-90009, 06-07-01817, 07-07-00142, 08-08-00300, 09-07-00185, 10-07-00157, 12-07-00145, 13-07-00160, Совета Президента РФ по поддержке ведущих научных школ №№ НШ-9505.2006.9, НШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9 и ФГОБУ ВПО «СибГУТИ» (2008-2013).

Получено три Свидетельства о государственной регистрации программ для ЭВМ (Яи) №№ 2012614642,2012613763, 2013613353.

Результаты работы внедрены в учебный процесс ФГОБУ ВПО «СибГУТИ», в систему мультипрограммирования пространственно-распределенной мультикластерной ВС ЦПВТ ФГОБУ ВПО «СибГУТИ», в проект Сибнет ОАО «Ростелеком», что подтверждается соответствующими актами.

Автор защищает

1. Модели и методы расчета показателей надежности и живучести болыыемасштабных распределенных вычислительных систем со структурной избыточностью и без. Функцию распределения времени пребывания ВС в состоянии низкой производительности.

2. Модели и методы расчета показателей осуществимости параллельного решения задач на большемасштабных ВС в основных режимах функционирования (решения сложной задачи, решения задач набора, обслуживания потоков задач).

Личный вклад автора заключается в проведении теоретических исследований, обосновании путей их практической реализации и авторском сопровождении при внедрении.

В диссертации обобщен комплекс исследований, выполненных ведущей научной школой в области анализа и организации функционирования большемасштабных распределенных вычислительных систем (руководитель —

чл. корр. РАН Хорошевский В.Г.), лично автором или при участии сотрудников ФГОБУ ВПО «СибГУТИ» и ИФП СО РАН.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих международных, всероссийских, российских и региональных конференциях: Bialystok, Poland (2006), Germany, Ilmenau (2000), пос. Кациавели, Крым, Украина (2006, 2008), Киев, Украина (2008), Минск, Беларусь (2012), пос. Дивноморское Геленджикского района (2001, 2007, 2009, 2010, 2012, 2013), Новосибирск (1994, 1995, 1998, 2000 -2002, 2006-2013), Томск (2009, 2010, 2012).

Публикации. По теме диссертации опубликовано 65 работ, в том числе 1 монография, 20 статей (14 из перечня ВАК), 3 свидетельства о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, 5 глав, основных результатов и выводов, списка литературы (332 наименования) и приложений. Основное содержание работы изложено на 234 страницах, содержит 7 таблиц и 88 рисунков.

Содержание работы

Во введении обоснована актуальность направления исследования, приведена общая характеристика работы, сформулированы научная новизна, практическая значимость диссертационной работы; представлены положения, выносимые на защиту.

В первой главе, изложены концептуальные основы построения распределенных ВС, методы исследования.

В основу аппаратурно-программных конструкций ВС и их функционирования положена модель коллектива вычислителей (Евреинов Э.В., Хорошевский В.Г.):

S =< C,G,A(P(D)) >, где С = {c¡} -множество вычислителей c¡, i = 0,1,..., Лг -1; G - структура сети межмашинных связей (граф, вершины которого представляют вычислители се С, я ребра - линии связи между ними); А - алгоритм работы множества С вычислителей, взаимосвязанных через G, при реализации параллельной программы Р обработки данных D.

Конструкция коллектива вычислителей Н-<C,G> есть отражение следующих основополагающих архитектурных принципов:

1) параллелизма при обработке информации (параллельного выполнения операций на множестве С вычислителей, взаимодействующих через связи структуры G);

2) программируемости структуры (настраиваемости структуры G, достигаемой программными средствами);

3) однородности конструкции Н (однородности вычислителей c¡ е С и макроструктуры G).

Рекомендуемая методика распараллеливания сложных задач — крупноблочное, позволяющее за счет минимизации затрат на межмашинные

взаимодействия достичь почти линейной зависимости производительности ВС от числа элементарных машин (ЭМ).

Требуемый уровень производительности, емкости памяти, надежности и живучести ВС достигается путем подбора числа ЭМ и их состава, выбора (виртуальной) структуры сети межмашинных связей.

Под надежностью ВС понимается свойство системы сохранять заданный уровень производительности путем программной настройки ее структуры и программной организации функционального взаимодействия между ее ресурсами.

Под живучестью понимается способность ВС в любой момент функционирования использовать суммарную производительность всех исправных ресурсов для решения задач (для реализации параллельных программ сложных задач).

Рассматриваются ВС со структурной избыточностью и живучие. Первые являются обобщением систем с резервом. Такие ВС, со стороны пользователя, выглядят как виртуальные системы, способные реализовать программы с фиксированным числом ветвей (равным числу машин). Живучие ВС способны реализовать адаптирующие параллельные программы, число ветвей в которых указано в некотором диапазоне.

Показатели живучести ВС должны учитывать то обстоятельство, что при решении задач используются все исправные ЭМ, число которых не является постоянным.

При анализе эффективности функционирования распределенных ВС используются показатели осуществимости решения задач. В зависимости от сложности задач и вида их поступления выделяются следующие режимы работы ВС: а) решение сложной задачи; б) обработка набора задач; в) обслуживание потока задач.

Эффективность функционирования ВС оценивается тройкой называемой (Л, 5Ь б'г) - реализацией решения, где - надежность (живучесть) системы, 52 - осуществимость решения задач. Надежность и живучесть (5[) анализируются показателями, определяющими качество функционирования ВС; потенциальные возможности - показателями, характеризующими процесс решения задач (52). Показатели надежности, живучести и осуществимости, представленные в функциональном виде, образуют совокупность показателей эффективности функционирования ВС. Основным математическим аппаратом является аппарат ТМО и случайных процессов.

При исследовании функционирования многомашинных распределенных ВС применяются показатели, характеризующие функционирование системы в среднем (математическое ожидание, дисперсия и другие моменты), обычно, полученные из распределения вероятностей. Часто ограничиваются лишь вычислениями базовых показателей - вероятностей состояний ВС, громоздкие выражения которых, а также отсутствие их компактных эффективных оценок, применимых для инженерных расчетов, не относятся к достоинствам существующих подходов.

В работе особое внимание уделено созданию моделей, позволяющих получить формулы, удобные для применения в инженерных расчетах, и используемые при вычислении показателей эффективности (и/или их эффективных оценок) функционирования многомашинных вычислительных систем.

Вторая глава содержит описание основных этапов, объектов и методов исследования. Одним из вариантов повышения надежного и живучего функционирования вычислительных систем является введение в ее состав системы структурной избыточности. Предлагается подход для анализа функционирования распределенных вычислительных систем, как со структурной избыточностью, так и без.

Объект исследования. Многомашинные вычислительные системы, состоящие из N достаточно высоконадежных элементарных машин (ЭМ), из которых структурную избыточность составляют п ЭМ. Относительно быстрая замена ЭМ машинами структурной избыточности позволяет поддерживать необходимую производительность в течение длительного промежутка времени. Это означает, что пока множество ЭМ, составляющих структурную избыточность, не пусто, считается, что ВС имеет высокую производительность, иначе она переходит в состояние низкой производительности с сохранением работоспособности других функций ВС. Такой подход позволяет получить дополнительную информацию относительно времени нахождения ВС в состоянии высокой производительности и, не усложняя модели, дать рекомендации относительно ее эффективной работы.

Итак, объектом исследования является структурная избыточность, исследовав состояния которой мы получили оценки для показателей, численно характеризующих функционирование данной ВС.

В рамках ТМО сформулирован марковский процесс со счетным числом состояний п, п = 1,2,3,..., содержащий в себе конечный процесс, и с постулатами пуассоновского процесса. Процесс формализован в виде системы дифференциальных уравнений, которые описывают связь вероятностей того, что в момент времени I в системе массового обслуживания (СМО) находится то или иное число требований, ожидающих обслуживания:

^о (0 = -Ао (/) • Р0 (0 + 2>* (0' Л (0.

к=\

■ К (0 = -(А (0 + ^ (')) ■ Рк (0 + V, (0 • (0, * = 1>2,..., и -1, (1) Р'п (0 = -Мп (0 • Рп (0 + 4-1 (0 • Рп-1 (0,

с условием нормировки

¿/>,(0 = 1, V/е[0,со),

к= 0

и начальными условиями

Р,(0) = 1, Рк(0) = 0, к*г, к = 0,1,2,...,«,

где Рк(/) - вероятность того, что в момент времени t СМО находится в состоянии/, ЯА (Г), рк(1) - параметры процесса.

Процесс описывает различные режимы функционирования ВС: живучих, со структурной избыточностью, резервом, дублированием, а также при решении задач потока, набора, пакета и т.д. Устанавливая определенные значения параметров системы (1) получили описание различных систем массового обслуживания.

Пусть ротх - вероятность перехода ВС в состояние низкой производительности; кср ~ среднее число ЭМ, составляющих структурную избыточность; /<"(/) - вероятность того, что ВС вошла в состояние низкой производительности и будет в нем находиться в течение времени не меньшего / е [0, со). В моделях потоки событий с постоянной интенсивностью предполагаются простейшими.

Третья глава посвящена развитию теории вычислительных систем, включает расчет показателей надежности, живучести и их эффективных оценок для многомашинных распределенных вычислительных систем.

1. Стохастическая модель функционирования распределенных вычислительных систем со структурной избыточностью (неограниченное число состояний). На систему массового обслуживания поступает поток требований интенсивностью N ■ X. Число к требований, поступивших в систему за время I, является случайной величиной удовлетворяющей пуассоновскому

закону, к = 0,1,2.....Требование, поступившее в СМО, вместе с другими к — 1

требованиями ждет начала обслуживания. Через случайное время начинается обслуживание сразу всех к требований с интенсивностью ¡л, независимо от числа требований в системе.

Пусть Рк (/) — вероятность того, что в момент времени / в СМО находится £ требований, / е [0,со), к = 0,1,2,.... Полагаем в системе (1)

Л,(/) = ЛГА, = о,

(2)

начальные условия

Р, (0) = 1; Рк (0) = 0, кФг

(3)

со

и условие нормировки Рк (/) = 1, V/ 6 [0, °о).

*=0

Найдено решение (1), с учетом (2) и (3)

Л <;,

В стационарном случае, рк = lim Рк (/) > 0, из (4) получаем

J-+KI

Ро=-

Рк

NX

{N-X + ц

к = 1,2,....

(5)

Условие сохранения высокой производительности распределенной ВС. По состоянию восстанавливающей системы (системы восстанавливающих устройств - СВУ) можно оценить требуемый объем (число ЭМ) структурной избыточности (резерва) для поддержки высокой производительности ВС. Следовательно, варьируя ее объем можно определить значение вероятности невыхода системы из состояния низкой производительности. Если п — размер структурной избыточности, то, учитывая условие нормировки, имеем

2^(0+£ад=1,

к=0 к=п

следовательно, за вероятность Ротх(0 перехода ВС в состояние низкой производительности в момент времени /, примем

Рассмотрим

Ротк = Ротк

стационарный (0 > 0 и

к=о режим

5>* =

к=п

функционирования

NX

NX +

ВС, тогда

(6)

Увеличение объема структурной избыточности от 0,01 до 0,025% числа N ЭМ ВС, при N = 2-Ю4 ЭМ - от 2 до 5 ЭМ резерва, приводит к уменьшению значения вероятности нахождения ВС в состоянии низкой производительности на 95,3% и 15,8% при суммарном восстановлении отказавших машин в течение 2 и 10 часов, соответственно (рис.1).

0.8 О.б

во 100 120 140

а) б)

Рис. 1. Зависимость вероятности невыхода ВС в состояние высокой производительности от объема структурной избыточности: N = 2-104 ЭМ, X = 10"4 1/ч, / = 0 ЭМ: а) ¡1 = 0,5 1/ч; б) ц = 0,1 1/ч

Более того, из рисунка видно, что, начиная с и равного 28 и 140 ЭМ, соответственно для а) и б), дальнейшее увеличение числа ЭМ структурной избыточности экономически нецелесообразно.

Оценим, по заданной вероятности ротк, величину п1 резерва, гарантирующего сохранение высокой производительности ВС. Из формулы (6) получим

+ 1.

Зададим доверительную вероятность у того, что ВС находится состоянии высокой производительности, тогда средний объем резерва

ьа-г)

+ь

(7)

ьт-щк-л+д) где [х] — целая часть числа х.

Результаты расчета по формуле (7) позволяют утверждать, что при А = 10"* 1/ч и надежности ВС 99% достаточен размер резерва до 0,4% и 0,8% от числа элементарных машин ВС, при надежности 95% — до 0,3% и 0,6% при суммарном восстановлении отказавших машин в течение 2 и 10 часов, соответственно (табл. 1). Следовательно, превышение объема ВС относительно надежности ЭМ более, чем на 2 порядка, нецелесообразно

Таблица 1

Необходимый объем структурной избыточности для сохранения высокой производительности ВС заданной надежности 1-^ = 0,01 1-^ = 0,05

\N И \ 103 104 105 103 ю4 ю5

0,5 4 13 96 3 9 63

0,1 8 50 464 6 33 303

Для нахождения среднего числа машин M(t) в восстанавливающей системе и соответствующей дисперсии D{t), введем производящую функцию

= Е -ад. (8)

к=0

Из системы (1), с учетом (2), (3) и (8) получаем уравнение

г\

— ^(г, 0 = -{N1 + 0 + г) + ц. (9)

81

Дифференцируя уравнение (9) по г последовательно два раза, имеем два уравнения в частных производных 2-го и 3-го порядков, соответственно, из которых, после приведения подобных, будем иметь систему уравнений

+ И ~ 0= 2МЛ • -J- F(l, 0.

oz oz

Замечая, что —F(l,t) = M(t), —-dz dz

систему

F( 1,/) = D{t) -M(t) + M (t), получим

-M(t) + fi-M(t) = NX, dt

—{D{t) - M(t) + M(t)2) + fi(D(t) - M(t) + M(t)2) = 2Ж ■ M(t). dt

Решение, при начальных условиях М(0) = /, D(0) = О, имеет вид

Dit) = 2 • (да/ /и)2(1 - е-"-') + 2NX(i - NÀ / ц) ■ t ■ е'"* + + (i2 - i)-е-"' + M(t) - M2(t).

(10)

Аналогично, если M = lim M(t) и D = lim D(t), то

t->x, /->00

M = NX / ß, D^{NXIpf +mi ц.

Среднее число отказавших машин, ожидающих восстановления, с учетом соответствующего среднего квадратичного отклонения для ВС, состоящей из N = 2-104 ЭМ, при / = О ЭМ, Я = Ю-4 1/ч приведены на рис. 2. Из рисунка видно, что при суммарном восстановлении отказавших машин в течение 2 или 10 часов ожидают восстановления до 9 и 40 ЭМ из 2-Ю4 ЭМ ВС (в среднем ждет восстановления 4 и 20 ЭМ), соответственно. Т.е., при /л > 0,5 1/ч среднее число отказавших ЭМ с учетом дисперсии не более 9, а при ¡л < ОД 1/ч - не менее 40. Следовательно, среднее время восстановления одной ЭМ составляет приблизительно t =15 мин, что вполне приемлемо для эффективного

функционирования ВС, поэтому

избыточности необходимости нет.

M(t) ,_

M(t) + 4Щ)

увеличении объема структурной

M(t) M{t) + 4W)

Рис. 2. Зависимость среднего числа отказавших машин в СБУ от времени при А = 10^1/4, N = 2-104, / = 0: а) ц=0,5 1/ч; б) ц=0,1 1/ч Оценка вероятности Пусть Т] - случайная величина,

характеризующая время восстановления элементарных машин в

восстанавливающей системе, тогда нахождение ВС в состоянии низкой производительности в течение времени t соответствует продолжительности восстановления всех вышедших ЭМ из строя, t е [0, go) , т.е.

F{t)»F(t) = P{r1>t}.

Так как в модели рассматривается стационарный режим функционирования ВС, то Р{т] = 0} = рош (в точке / = 0, F(0) имеет разрыв), то есть, в этом случае, для любого момента времени pomK = const.

И ( NX

Предположим, что резерв состоит из п ЭМ и рк =-----

N-Х + ß \N-Л + ß

- вероятность того, что к ЭМ ожидают обслуживания, тогда

т

p{ti>t}=T,PfPk{v>t},

к=п

где Pk{n>t} - вероятность того, что за время t восстановлено к ЭМ, а т (n<m<N) — число, используемое при оценке погрешности функции F(l).

Поскольку в стационарном режиме поток восстановления ЭМ простейший, то

lk'jQ-4u-tY

Рк(П><}= t ■ cxp(~ß ■ /).

г=0 Г\

где [£/и] целая часть от к/п. Тогда

¡Z,NÄ+ ß \ж+ßj r=0 n

По предположению n«N, поэтому N—><x>, и, тем самым, m— положим по определению

+ ß [m + ßj и

В результате, после соответствующих преобразований, в работе получено выражение

F(t) = Ротк • «р(- (1 - Рот J • ß ■ t). (11)

Функция G(/)=l — F(t)/ротк является функцией распределения времени нахождения ВС в состоянии низкой производительности.

Применим формулу (11) для анализа эффективности функционирования ВС. Пусть ВС состоит из N = 2-104 ЭМ, при Я = 101/ч и суммарном восстановлении в течение 2 и 10 часов (рис. 3 а, б) с объемом структурной избыточности 1-6 ЭМ и 5 - 30 ЭМ. Тогда для её выхода на состояние высокой производительности понадобится около 21 и 100 ч, соответственно. Увеличение объема структурной избыточности с 6 до 10 и с 30 до 47 ЭМ приводит к тому, что значение вероятности пребывания ВС в состоянии низкой производительности не превосходит 0,1. Увеличение структурной избыточности до 32 и 145 ЭМ, соответственно, делает ВС высоконадежной

(вероятность менее 0,001). Дальнейшее увеличение объема структурной избыточности нецелесообразно.

1 - и=1; 2 - л=3; 3 - л=6; 4 - л=10

1 - и=5; 2 - и=10; 3 - л=30; 4 - и=47

Рис. 3. Зависимость F{t) от продолжительности функционирования t при X = 10"41/ч, N = 2 • 104 ЭМ: а) ц = 0,5 //ч; ф ^ = 0,1 1/ч

Погрешность функции F(t). Приведем оценку погрешности Д(г, от) функции F(t), связанную с допущением о бесконечности объема резерва и, следовательно, с условием т-><*>. Имеем

ц ( NX

A (_t,m)= I

r=o г!

M + я l^M + jUy

После преобразований, аналогичных выводу функции (11), получено Д(/, m) = (NX/{NX + fi))"""* • F{t).

Таким образом, число m есть то число, на которое нужно увеличить объем резерва, чтобы ВС оставалась в состоянии высокой производительности практически достоверно. При числовых значениях параметров рисунка 3 уже при от = 28 имеем A(t,m)< 0,0038 -F(t).

2. Стохастическая модель функционирования вычислительных систем со структурной избыточностью (конечное число состояний). Пусть ВС состоит из N ЭМ, п из них составляют структурную избыточность, а остальные N — п образуют основную подсистему. Любая из ЭМ основной подсистемы может выйти из строя. Вышедшая из строя ЭМ меняется на одну из структурной избыточности, а сама вместе с другими машинами, число которых не более чем п — 1, ждет завершения восстановления. Все восстановленные ЭМ возвращаются в вычислительную систему. Если из строя выходит очередная ЭМ, а структурная избыточность пуста, то ВС переходит из состояния высокой в состояние низкой производительности, то есть основная подсистема работает в пониженном режиме функционирования.

Построение модели основано на допущениях: n«N, ВС высокопроизводительная, по окончании восстановления ЭМ считаются принадлежащими структурной избыточности.

В терминологии ТМО сформулируем модель. На СМО поступает пуассоновский поток требований интенсивностью N ■ X. Требование,

поступившее в СМО, вместе с другими 0<к<п требованиями ждет начала обслуживания. Если в системе уже находится и требований, то поступившее новое требование не обслуживается. Через случайное время начинается обслуживание сразу всех к +1 требований с интенсивностью ц. Требуется вычислить — вероятность того, что в момент времени I в СМО находится к требований, [0,оо), к = 0,1,...,п.

В системе дифференциальных уравнений (1) полагаем

АД0=ла, = (12)

начальные условия

/>(0) = 1,Р*(0) = 0, 0<к<п, (13)

условие нормировки, являющееся следствием постановки задачи

¿^(0 = 1, ^6[0,со). (14)

к= О

Для вероятностей Рк (/) выполняются формулы (4), к = 0,1,..., и -1, а при

А = и

р = (А^Я)" -(«и,* . "у1 ,

" (N1 + ц)" (ИХ+цУ т + ц £а^Х)к -(п-к-\)\

+ • "у---+

+ (тГ'1иент+")'УУ-т---]. (15)

Таким образом, имеем РотК(0-Р„{1), анализ которой дает возможность оценить скорость вхождения ВС в состояние низкой производительности. В стационарном режиме функционирования ВС

( NX

Ротк _ ..

■■ftj

(16)

Для нахождения среднего числа машин M(t), ожидающих восстановления в СВУ, и дисперсии D(t) воспользуемся аппаратом производящих функций, тогда

4- t) = ц ■ (1- F(z, t)) + NX • (z -1 )(F(z, t)-z"-Pn (t)). ot

Отсюда, аналогично ранее приведенной методике, в работе получена система уравнений для M(t) и D(t)

4-ЩО + M ■ M(0 = NX ■ (Г- Р„ (t)), at

4 в(0 + Ц ■ Q(0 = 2NX ■ {M{t) - пР„ (t)), (17)

ai

Q(t) = D{t)-M(t) + M\t).

Среднее число отказавших машин, ожидающих восстановления (с учетом среднего квадратичного отклонения для ВС, состоящей из N -2-104 ЭМ, при /' = 0 ЭМ, Я = 10"* 1/ч), приведены на рис. 5. При увеличении структурной избыточности от 4 до 20 ЭМ (0,02 - 0,1% объема ВС) и от 20 до 110 ЭМ (0,1 -0,55%) в среднем ожидает восстановления 3-4 ЭМ и 15 - 20 ЭМ при восстановлении отказавших машин в течение 2 и 10 часов, соответственно. При этом если ц > 0,5 1/ч, то среднее число отказавших ЭМ с учетом дисперсии не более 8, а при р. < 0,1 1/ч - не менее 30, поэтому необходимо рекомендовать объем резерва приблизительно 0,04% и 0,3% при суммарном восстановлении отказавших ЭМ в течение 2 и 10 часов, соответственно. Хотелось бы отметить, что увеличение и объема резерва влечет за собой увеличение среднего числа отказавших машин до определенного предела, поэтому дальнейший рост резерва не желателен.

в) г)

Рис. 5. Зависимость среднего числа отказавших машин в СБУ от времени / при А = 10"41/ч, // = 2-104, ¿ = 0:а) я = 4, ^ = 0,5 1/ч; б) « = 20, = 0,5 1/ч; в) « = 20, р. = ОД 1/ч; г) « = 110, ^ = 0,1 1/ч.

В условиях сформулированной задачи рассмотрим случай, когда через достаточно длительный промежуток времени не происходит восстановления вышедших из строя ЭМ, т.е. по каким-либо причинам восстанавливающая система не приступила к восстановлению, т.е. рк (/) = р. = 0. Тогда вероятность того, что резерв пуст (ВС находится в состоянии низкой производительности), равна

*=0 л!

Заметим, что Рат$) = Рп(1) - вероятность вхождения ВС в состояние низкой производительности. Рис. 6 иллюстрирует зависимость входа ВС в состояние низкой производительности от времени функционирования: при Я = 10"* 1/ч, и = 20 ЭМ, при объеме ВС 103 и 2-Ю4 ЭМ и несостоятельной СВУ, понадобится более 300 и 15 часов, при этом с вероятностью близкой к единице, ВС может находиться в состоянии высокой производительности при пустом резерве до 100 и 5 ч, соответственно.

а) б)

Рис. 6. Зависимость вероятности вхождения ВС в состояние отказа от времени tnpu Я = Ю-4 1/ч, п = 20 ЭМ: а) Лг = 103 ЭМ; б) N = 2 • 104 ЭМ

Оценим скорость уменьшения объема структурной избыточности при отсутствии восстановления. Для этого введем обозначения M(t) - среднее число машин в резерве, D(t) — соответствующая дисперсия. Тогда после необходимых преобразований, получаем систему

at

dt

(D(t) + M2 (/)- M(t)) = -2 • (N - ri) • Я • M(t),

(19)

с начальными условиями

М(0) = п, £(0) = 0. (20)

Подставим Р„ (?) из (18) в (19) с учетом (20). Итак, в работе получено решение

((ЛГ-и).Я-?Г*

Л/(0 = ехр(-(ЛГ-«)-Я-/)-2>

*=i (и - *)! *=1 (и-Л)!

п-к

-(Л/(0)2.

Приближенное решение для оценки состояния резерва. Получено более простое

и

выражение решения для (21) при / <-

(ЛГ-и)А \б(1) = (¿V - и) • Я • Л

Погрешность использования приближенного решения (22), вместо точного (21), определяется равенством

которое можно записать в виде

(22)

&(t) = M(t)-M(t) = exp(-(N — «) • А • /) • X (¿-и)

*=я+1 А!

На рис. 7 представлено сравнение точного и приближенного значения среднего объем резерва с учетом соответствующего отклонения.

М(1)

20

* «

V « к ч ч

ч s \ > ч ч ч

ч ч ч ч ч ч

100 150 200 , 250

t,4

а)

МВД 20

15

10

M(t) 20

15

10

0 5 10 -1 .......2

15 20

t,4

10

- 5 '

15 6

20 t4

б)

Рис. 7. Зависимость среднего числа машин резерва от времени t при А = КГ4 1/ч, и = 20 ЭМ: а) N = 103 ЭМ; б) N = 2 • 104 ЭМ; 1 - M{t) ; 2 -

Отметим, что на протяжении до —-—1ср ч, где Г - среднее время

N-п

выхода ЭМ из строя, для оценки скорости уменьшения объема резерва использование формул (22) дает достаточно точное значение, равное в среднем 0,098 ЭМ/ч и 1,998 ЭМ/ч. Поэтому при объеме ВС 103 и 2-Ю4 ЭМ и отсутствии возможности восстановления структурная избыточность будет равна нулю по истечении приблизительно минимум 200 и 10 часов (с учетом отклонения до 300 и 15 ч) функционирования, соответственно, далее ВС входит в состояние низкой производительности. Рис. 7 иллюстрирует оценку состояния резерва распределенной ВС по точному (21) и приближенному (22) решениям. Отметим, что при надежности ЭМ сравнимой с объемом ВС, можно использовать формулу (22).

3. Стохастическая модель функционирования без структурной избыточности. Пусть ВС состоит из N ЭМ. Любая из ЭМ системы может выйти из строя, тогда она вместе с другими машинами ждет восстановления. Восстановленные ЭМ возвращаются в вычислительную систему.

Описание модели. На СМО из бесконечного источника поступает пуассоновский поток требований интенсивностью (Ы-к)-Л, 0<k<N. Требование, поступившее в СМО, вместе с другими к -1 требованиями ждет начала обслуживания. Через случайное время начинается обслуживание сразу всех к требований, с интенсивностью ц. Пусть Рк(1) - вероятность того, что в момент времени / в СМО находится £ требований, /е[0,°о), к = 0,1,..., N.

Полагаем в системе (1)

Хк =(ЛГ-£)А, цк =ц, и = 0, (23)

начальные условия

РД0) = 1, Р*(0) = 0, (24)

и условие нормировки

ЕА0) = 1. 'е[о,°°).

*=о

Пусть М({) - среднее число отказавших машин ВС, !>(/) - соответствующая дисперсия. После необходимых преобразований получена система

—Л/(0 + + Х)М{1) = М, Л

■ 4-ею++2Я> • ем=-• м(я> (25>

ш

начальные условия определяем из (24)

Л/(0) = /, В(0) = 0. (26)

С учетом начальных условий (26), найдено решение для (25)

Ж

ц-г-ЦЫ-г)

/л-А . /л + Х

ти- 1)Я2 + (27)

0| + АХ^ + 2А) /* + А

+ М(1)-М2(1),

где Св/а

+ А)(// + 2А) /Л- А

На рис. 8 представлен расчет среднего числа отказавших машин находящихся в СВУ и дисперсии при А = 10"4 1/ч, N = 2-104 ЭМ, /' = 0 ЭМ. При отсутствии структурной избыточности в среднем ожидает восстановления до 9 и 40 ЭМ при суммарном восстановлении отказавших машин в течение 2 и 10 часов, соответственно. Стабилизация числа ЭМ, ожидающих восстановления, происходит в течение 32 ч и 153 ч, соответственно. Если учесть среднее квадратичное отклонение, обслуживания ожидает в среднем менее 1 ЭМ до 11 мин функционирования ВС, далее хотя бы одна машина ожидает восстановления, поэтому ВС находится в состоянии низкой производительности.

МЮ+л/Щ)

Ж®

МХО

а) б)

Рис. 8. Зависимость среднего числа отказавших машин в СВУ от времени I при 1 = 1^1/4, N = 2-104, / = 0: а) ц~0,5 1/ч; б) ц=0,1 1/ч Отметим, в сравнении со случаем, когда ВС обладает непустой структурной избыточностью, до 4 ЭМ и до 60 ЭМ ВС находится в состоянии низкой производительности не более 10 и 60 ч при суммарном восстановлении в течение 2 и 10 ч, соответственно.

Таким образом, анализ построенных моделей, позволяет утверждать, что для высокопроизводительной работы ВС необходимо обеспечить наличие резерва (приблизительно 0,3% от объема, не более 105 ЭМ ВС) и эффективной восстанавливающей системы (суммарное восстановление не более 10 ч), причем уменьшение продолжительности восстановления вышедших из строя ЭМ, позволяет уменьшить объем резерва без потери качества функционирования вычислительной системы.

В четвертой главе рассматриваются средства (математические модели, подходы и алгоритмы) для расчета показателей осуществимости параллельного решения на распределенных ВС. Для высоконадежных ВС рассматриваются показатели осуществимости решения задач (S2), то есть система предполагается абсолютно надежной. Если рассматриваются потенциальные возможности ВС с учетом ее надежности (живучести), то вычисляются показатели осуществимости решения задач в реализации (SltS2).

1. Расчет показателей осуществимости решения задач на распределенных вычислительных системах с накопителем. По своей природе ВС - это стохастический объект, обслуживающий вероятностные потоки задач со случайными параметрами. Естественно при изучении функционирования ВС применять аппарат ТМО. Использование классической теории массового обслуживания обычно приводит к трудоемким вычислениям, либо необходимости применения численных методов. Для получения формул, удобных в инженерных расчетах, обычно рассматривают стационарный режим и ограничиваются числовыми показателями эффективности, что недостаточно для качественного анализа функционирования ВС.

Рассмотрим многомашинную ВС, на которую поступают задачи для решения. Поступившая задача попадает в накопитель. Из задач формируется пакет, количество задач в пакете ограничено числом ЭМ решающих задачи. Если пакет сформирован, то вновь поступившая задача остается в накопителе и ждет обслуживания.

Описание модели. На СМО поступает поток требований интенсивностью а, из которых формируется пакет объема п. Если пакет сформирован, то требование получает отказ. Как только СМО освобождается, она приступает к обслуживанию с интенсивностью ß очередного пакета, пусть даже и не до конца сформированного. По окончанию обслуживания СМО переходит к обслуживанию очередного пакета.

Требуется найти Pk(t) - вероятность того, что в момент времени t е [0,оо) пакет состоит из к нерешенных задач, при условии, что в начальный момент времени пакет был пустым; к = 0,1,2......

Полагаем в системе (1)

Л*(0 = «.М0 = Ж0, (28)

а начальные условия

^о(0) = 1, Pt{0) = 0, к*0. (29)

Условие нормировки, являющееся естественным следствием системы уравнений (1), имеет вид:

SPt(/) = l, V/e[0,co).

В стационарном режиме limРк(<) = рк >0, limPk'(t)~0, получаем

/—>£*> I—» ОО

„ ____ß ___а 'ß_ t-n-j nm

Как следует из (30), вероятности рк, к = 0,1,2,..... составляют ряд

распределения и, следовательно, представляют базис, через который выражаются показатели, характеризующие эффективность функционирования (осуществимость решения задач) ВС в момент времени г, / е [0,°о).

Обозначим Ма (I) - среднее число нерешенных задач в пакете и £>а(/) соответствующую дисперсию. Положим Р = /?(/), тогда, с учетом (28) и (29), в работе получены уравнения для рассматриваемых характеристик из модели (1)

4ма(/)+д(0-л/а(<) = «.

и (31)

4(Д,(0 - ма( о+ма\0) + № ■ Ш0 - ма(0+ма2с 0) = 2« • ма(0,

.ш

с начальными условиями Ма (0) = 0, £>а (0) = 0.

Пусть у(А0 — производительность системы при решении задач набора,

которые забираются из накопителя, на ВС из N ЭМ. Тогда

ЛО-^-Л (32)

где ¡3 — интенсивность решения задач на ВС из N ЭМ, функционирование которой описывается (1), (28), (29).

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

= (32-0

N

Положим в (27), N - г = ], тогда

Л,(0 = Лг-М(0

или

■щ) = + е<к+Ъ<>

р+к ц+Х

где у — число исправных машин в начальный момент времени, Я и ц — соответствующие интенсивности.

Найдены аналитические решения для математического ожидания и дисперсии (31) при условии (29) и /?(/) = р, которые записываются в виде

А/в(0 = |(\-е-><). А, <0'= 2 • |- а ■ г ■ е-" ) + 2^У • е+ Ма Ц) -Ма\г).

Р

(33)

Пусть ВС состоит из N = 2 • 104 ЭМ, выход из строя которых происходит с интенсивностью Я = КГ4 1/н и суммарным восстановлением в течение 2 и 10 часов. В случайные моменты времени ВС обращается в накопитель и забирает все, поступившие с интенсивностью а =10 1/ч, задачи, и формирует пакет. Решение задач пакета осуществляется в течение времени 1//?(<) вне зависимости от объема пакета. Результат расчетов по формулам (31) и (33), приведен на рис. 9. Чем меньше времени тратится на восстановление вышедших из строя ЭМ, тем меньше разница между значениями, определенными формулами (31) и (33), однако при ухудшении качества СВУ, формула (31) позволяет отметить скачок по накопившимся задачам, который, в данном случае, практически, в два раза больше, чем среднее значение в стационарном режиме.

г 4 б в ю 1г х*

а)

мт

б)

ЛМО

Г"

В)

Рис.9. Зависимость наполненности накопителя задачами с учетом дисперсии от продолжительности функционирования / при а = 10 1/ч, Р = 1 1/ч, Л = 10~4 //ч, ЛГ = 2-104: а) ^ = 0,5 1/ч, /3(0 = Р-ЩО/И,) = 500; б) /¿ = 0,17/4, /?(/) =_/' = 200; п) /?« = /?

С учетом замечания, определим наполненность накопителя сверх заданного числа задач. Пусть число таких задач будет п0, и назовем это число критическим уровнем. Это могут быть системы, где нежелательно использование памяти для хранения задач сверх определенного уровня.

1. Вероятность того, что накопитель не пуст

р>. =1-»0 = 1--^— = — «0,91.

Уг1 Уо 10 + 1 11

2. Вероятность, того, что наполнение накопителя превысит критический уровень из п0 задач (пакет полон), как и ранее,

19996

к=о \а + Р) ио + 1 3. Расчет критического уровня по заданной вероятности его превышения

hPo

+ 1 =

In 0,01

_ln(10/ll)

\па~\п(а + р) где [х] — целая часть числам;

4. Среднее число задач в накопителе с учетом дисперсии

+ 1 = 49,

+ 1 =

+ 1 = 42.

Оценка вероятности F(t) того, что накопитель наполнен сверх критического уровня задачами и будет находиться в таком состоянии в течение времени не меньшего заданного. На основании построенной математической модели для ВС со структурной избыточностью, найдена функция F(t) того, что накопитель наполнен, сверх критического уровня п0, задачами и будет находиться в таком состоянии в течение времени не меньшего заданного (определяемого малой вероятностью, задающей порог выхода на высокую производительность : 0.05 — 0.1), которая имеет вид

Ротх ■ ехр(-(1 -ротк)-Р-1).

Оценка погрешности для функции F(t) имеет вид

т - заданный параметр ограничения накопителя.

Пусть критический уровень щ = 30. Зависимость вероятности F(t) нахождения ВС в состоянии низкой производительности от продолжительности функционирования t для и = 30 и и = 42 приведена на рис. 10, время нахождения ВС в состоянии низкой производительности (с вероятностью 0,01) составляет не более 19 ч и не более 7 ч, соответственно.

т «.06

Рис. 10. Зависимость F(t) от продолжительности функционирования t при а = 10 1/ч;Р = 1 1/ч: / -и = 30; 2 - и = 42

2. Модель для оценки функции осуществимости параллельного решения сложных задач. Одно из преимуществ большемасштабных распределенных вычислительных систем с программируемой структурой состоит в том, что путем увеличения количества Ñ ЭМ можно достичь заданной производительности и высокой живучести. Цель функционирования ВС -решение задач, представленных адаптирующимися параллельными программами, как в монопрограммном, так и в мультипрограммном режимах. В качестве показателя здесь возьмем вероятность решения параллельной задачи за время Т на ВС.

Пусть P(T,ts,ri) - вероятность решения сложной задачи (представленной параллельной программой) за время Т на распределенной ВС состоящей из п исправных ЭМ при общим числе машин - N; ts - время решения задачи на одной ЭМ; - это часть задачи, которая решается на одной машине за

время (tk,tM], keEs0={0,l,-,s}, ieE*'k ={0,W-*}; P{T,tk,ts,n) вероятность решения части Q(,í/3l сложной задачи за время Т на распределенной ВС состоящей из п исправных ЭМ при общем числе машин -N, тогда при к = 0 получаем, что P(T,is,n) = P(T,tl,ts,rí); f(tk) - время решения на ВС части задачи; &f(tk) = f(tk+i)-f(tk) - время решения части fi(,t j; pflt (л, t, т) - вероятность возникновения отказа в ВС, состоящей из п исправных ЭМ за время /, при условии, что этот отказ наступит после времени т; prs, (п, t, т) - вероятность восстановления п отказавших ЭМ системы за время t, при условии, что это восстановление наступит после времени г, ТШп -время реконфигурации системы на исправное число машин.

Если отказы и восстановление ЭМ происходят по модели функционирования ВС без структурной избыточности, то для расчета вероятности P(T,tk>ts,ri) предлагается следующее выражение:

Г(1 - Pj¡,(n, A/(/J, /&))(1- ргЛп, bf{tk),f(ty)))P(T-hf{tk), tM, t„ п) + + Pjll(n, A/fe),Ж))P(T-Af(tk)~Tlu„,tk,l,ts,n-l) + + pm(n, Af(tk), f(tk))P(T-Áf(tk)-Tm„,t,_k_uN),

1 <n<N-,

(1 - Pj¡, («, A/(tt), f(tk ))P(T - ДД/Д tk+l ,t„ri) + P(Tt t rí) = - ■+Pp(",mt),f(tk))P(T-AAtk)-TM,ts_k_l,n-l), (34)

(1 - pm (n, Af(ík ), f(tk)))P(T - A/fe), tM ,/„«) +

+ pr„(n, Af(tk), f(tt))P(T - A/fe) - T^t^, N),

и = 1;

1, k = s & T>0;

0, T< 0.

На рис. 11 представлен расчет по (34) вероятности решения сложной задачи на ВС.

Р

0,2

и--,-,t

1,0 1,075 1,1

Рис. 11. Вероятность решения сложной задачи на ВС за время t 7; =1000 ч; iV = 1000; / = 1000; ß = 0 l/4;K(i) = i, Тш =0,02 v:

1 - А = 10"4 7/v; 2 - Я = 5 ■ 10"4 1/ч; 3 - А = 10_3//ч

В пятой главе описана архитектура пространственно-распределенной мультикластерной вычислительной системы Учреждения Российской академии наук Института физики полупроводников им. A.B. Ржанова СО РАН (ИФП СО РАН) и Центра параллельных вычислительных технологий ФГОБУ ВПО «Сибирский государственный университет телекоммуникаций и информатики» (ЦПВТ ФГОБУ ВПО «СибГУТИ»). Действующая конфигурация ВС (рис. 12, декабрь 2013 г.) объединяет 10 пространственно-рассредоточенных вычислительных кластеров, включает более 300 процессорных ядер и имеет пиковую производительность несколько TeraFLOPS.

Рис. 12. Конфигурация пространственно-распределённой мультикластерной вычислительной системы (декабрь 2013 года)

Любой из кластеров способен функционировать как автономно, так и в составе распределённой ВС. Коммуникационные сети кластеров построены на базе технологии GigabitEthernet и технологии InfiniBandQDR. Для объединения кластеров используется сеть Internet (технология VPN). Мультикластерная ВС

допускает масштабирование путём организации взаимодействия с множеством других систем.

Данная мультикластерная ВС входит в состав глобальной сети программы «Университетский кластер» (Минобрнауки РФ, Институт системного программирования РАН, ЗАО «Синтерра», Hewlett-Packard).

Основное назначение пространственно-распределенной

мультикластерной ВС - исследование архитектуры распределенных ВС, отработка инструментария параллельного мультипрограммирования, моделирование сложных физико-технических процессов и природных явлений и подготовка специалистов и научных и научно-педагогических кадров высокой квалификации в области распределенных вычислительных технологий.

На рис. 13 показана структура программного обеспечения пространственно-распределенной мультикластерной ВС.

; II Средства разработки параллельных программ MPI: MPICH2, OpenMPI, Торо МИ PGAS: Unified Parallel С OpenMP: GNU GCC, Intel Compilers, Oracle Compilers, PathScale Средства анализа параллельных программ: MPIPerf, VampirTrace

8.< я а Ш с . Tss р & ■ i; - еда» о- редйз.1 " ; (G broker, dqucued, GridWav)

н ! Подсистема параллельного мультипрограммирования ■ MOJOS,TORQUE,MAl.l * Срмсгп» формнровнияя резерва, mpiexec)_

i« 1 Подсистема самокотпроля, самодиагностики ЗС и организации отказоустойчивого выполнения параллельных программ 1 ' .•',.(.., ...... ,..... Ь

Операционная система GNU/Linux

• Подсистема параллельного мультипрограммирования Рис. 13. Структура программного обеспечения пространственно-распределенной мультикластерной ВС

Стандартные компоненты программного обеспечения представлены: -сетевой операционной системой GNU/Linux (дистрибутивы CentOS, Fedora);

- средствами разработки, отладки и анализа последовательных и параллельных программ, среди которых:

- компиляторы GCC, Intel, Oracle, PathScale EKOPath; -математические библиотеки GNU Scientific Library, AMD Core Math

Library, Intel Math Kernel Library;

- библиотеки передачи сообщений между ветвями параллельных программ, а именно:

- распределенные приложения — MPI: MPICH2, OpenMPI, Intel MPI;

-параллельные программы - OpenMP: GCC, Intel, Oracle, PathScale

EKOPath;

-средства отладки и анализа программ: GDB, VampirTrace, Vampir, prof, oprofile, gprof.

- программным обеспечением организации взаимодействия пространственно-распределенных кластерных ВС и диспетчеризации пользовательских заданий: Globus Toolkit, GridWay.

Программные компонента!, созданные коллективом ведущей научной школы (№№ НШ-9505.2006.9, НШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9, руководитель чл.корр.РАН В.Г. Хорошевский):

- средства организации распределенной очереди задач;

- подсистема параллельного мультипрограммирования (одним из компонентов которой являются средства формирования резерва основанные на стохастических моделях функционирования распределенных ВС со структурной избыточностью)',

- подсистема самоконтроля, самодиагностики ВС и организации отказоустойчивого выполнения параллельных программ;

- средства мониторинга и организации удаленного доступа к ресурсам

ВС.

Также в 5-й главе предлагаются параллельные алгоритмы, которые реализованы на одном из сегментов пространственно-распределенной мультикластерной ВС,

На рис.14 показана эффективность исполнения на кластерной ВС параллельного алгоритма для вычисления вероятности (34) решения сложной задачи, где K(j) = t^/tj , t} - время решения задачи на j ЭМ системы. Алгоритм характеризуется ускорением, близким к линейному.

КО)

120

100 -

80 -

60 -

40 ■

20 -

18 40 72 96 120

Рис. 14. Эффективность исполнения на кластерной ВС параллельного алгоритма расчета вероятности (34) решения сложной задачи.

РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1. Рассмотрен и формализован системой дифференциальных уравнений марковский процесс со счетным числом состояний и содержащий в себе конечный процесс.

Процесс применен для описания функционирования большемасштабных распределенных вычислительных систем со структурной избыточностью в различных режимах. В рамках процесса разработаны стохастические модели и рассчитаны показатели эффективности функционирования ВС. Получены их аналитические выражения. Для применения в инженерных расчетах приведены оценки показателей эффективности с указанием величины погрешности.

1.1. Построены модели для расчета показателей надежности и живучести распределенных ВС со структурной избыточностью. Составлены и решены системы дифференциальных уравнений как для вероятностей состояний ВС, так и для математического ожидания и дисперсии.

Показано, что при надежности элементарной машины (наработка на отказ) 104 - 5-104 ч, при объеме ВС 2-Ю4 - 105 ЭМ объем структурной избыточности составляет 0,01-0,1%.

1.2. Получена функция распределения времени нахождения ВС в состоянии низкой производительности. Показано, что при надежности ЭМ 10 ч и объеме ВС 2-Ю4 ЭМ, суммарном времени восстановления отказавших ЭМ менее 10 ч, значение вероятности вхождения ВС в состояние низкой производительности менее 0,1, а время пребывания в состоянии низкой производительности менее 3 ч, при объеме резерва 42 ЭМ. Если объем резерва более составляет 50 ЭМ, то с вероятностью близкой к единице ВС будет находиться в состоянии высокой производительности достаточно долго.

1.3. Получена система дифференциальных уравнений для непосредственного нахождения математического ожидания случайной величины характеризующей надежность ВС и дисперсии. Решение найдено в аналитическом виде.

Показано, что при условиях, накладываемых на параметры ВС п. 1.1 - 1.2, среднее число отказавших ЭМ стабилизируется, в зависимости от суммарного восстановления 2 - 10 ч, в пределах от 9 до 45 ЭМ. Это и определяет объем резерва. Дальнейшее его наращивание нецелесообразно.

2. Для расчета показателей осуществимости решения задач использован марковский процесс, как с постоянными, так и переменными параметрами.

2.1. Для расчета показателей осуществимости решения задач на большемасштабных распределенных ВС рассмотрены системы с накопителем. Найдены характеристики, описывающие состояние накопителя. Вычислены среднее число и дисперсия числа нерешенных задач. Предложена оценка вероятности того, что накопитель наполнен сверх критического уровня задачами и будет находиться в таком состоянии в течение времени не меньшего заданного.

2.2 Построены модели оценки функции осуществимости параллельного решения сложных задач. Предложены алгоритмы нахождения функции осуществимости решения задач с учетом отказов и восстановления ЭМ ВС. 3. Предложенные алгоритмы реализованы на пространственно-распределенной мультикластерной системе Института физики полупроводников им. А.В. Ржанова СО РАН и ФГОБУ ВПО «СибГУТИ» и показали высокую эффективность распараллеливания.

Предложенные алгоритмические и программные средства формирования резерва вычислительной системы включены в состав инструментария параллельного мультипрограммирования пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ФГОБУ ВПО "СибГУТИ".

ПЕРЕЧЕНЬ ОСНОВНЫХ ПУБЛИКАЦИЙ

Книги

1. Курносов, М.Г. Вычислительные методы, алгоритмы и аппаратурно-программный инструментарий параллельного моделирования природных процессов / М.Г. Курносов, В.Г. Хорошевский, С.Н. Маймоленко, К.В. Павский и др.: под ред. В.Г. Хорошевского. - Новосибирск: СО РАН, 2012. - 430 с.

Журналы, рекомендованные ВАК РФ

2. Pavsky, K.V. Analysis of the time of solution of parallel problems on programmable structure computer systems / K.V. Pavsky II Optoelectronics, instrumentation and data processing. - 2000. - №2. - P. 54-62.

3. Павский, K.B. Анализ времени решения параллельных задач на вычислительных системах с программируемой структурой / К.В. Павский // Автометрия. - 2000. - №2. - С. 60-69.

4. Хорошевский, В.Г. Методика расчета показателей эффективности функционирования вычислительных систем / В.Г. Хорошевский, В.А. Павский, К.В. Павский II Вестник компьютерных и информационных технологий. 2008. - №2. - 2008. - С.47-55.

5. Хорошевский, В.Г. Расчет показателей эффективности функционирования большемасштабных распределенных вычислительных систем / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Вестник компьютерных и информационных технологий. - 2009. - №6. - С.25-30.

6. Павский, В.А. Анализ эффективности функционирования распределенных вычислительных систем в режиме решения задач потока с отказами / В.А. Павский, К.В. Павский // Вестник СибГУТИ - Новосибирск - 2010. -№2(10).-С. 42-47.

7. Хорошевский, В.Г. Расчет показателей живучести распределенных вычислительных систем / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2011. - №2(15). - С. 81-88.

8. Хорошевский, В.Г. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных

систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, К.В. Павский и др. // Вестник СибГУТИ - 2011. - №4. - С. 3-19.

9. Павский, В.А. Оценки показателей осуществимости решения задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Вестник СибГУТИ. - 2012.-№ 1. - С. 51-55.

10. Павский, В.А. Оценки показателей функционирования вычислительных систем со структурной избыточностью / В.А. Павский, К.В. Павский // Вестник СибГУТИ. - 2012. -№ 2. - С.71-76.

11. Павский К.В. Ускоренный алгоритм оценивания сдвигов и поворотов изображений на последовательности кадров / К.В. Павский // Вестник СибГУТИ. - 2012. - № 3. - С.81-85.

12. Павский, В.А Вероятностная модель оценки показателей функционирования высоконадежных вычислительных систем с резервом / В.А. Павский, К.В. Павский // Техника и технология пищевых производств. -2012. - № 3. - С. 80-87.

13. Хорошевский, В.Г. Математическая модель и расчет показателей функционирования вычислительных систем со структурной избыточностью / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Известия ЮФУ. Технические науки. - 2012. - № 5 (130). - С. 37 - 41.

14. Павский, В.А. Стохастическая модель и оценки показателей функционирования вычислительных систем со структурной избыточностью /

B.А. Павский, К.В. Павский // Вестник томского государственного университета. - 2012.- №4 (21). - С. 100-107.

15. Павский, К.В. Стохастические модели дня оценок размера структурной избыточности болыпемасштабных вычислительных систем/ К.В. Павский // Вестник СибГУТИ. -2013. - № 2. - С.16-21.

Статьи в журналах, сборниках трудов, материалах конференций

16. Павский К.В. Осуществимость параллельного решения задачи и потока задач на распределенных вычислительных системах. / К.В. Павский // Искусственный интеллект. — 2001. - №3. - С. 251-259.

17. Павский, В.А. Вычисление показателей живучести распределенных вычислительных систем и осуществимости решения задач / В.А. Павский, К.В. Павский, В.Г. Хорошевский // Искусственный интеллект. - 2006. - №4. -

C. 28-34.

18. Павский, В.А. Оценка показателей осуществимости решения задач на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2008. - №4(5). - С.61-68.

19. Khoroshevsky, V.G. Technical and Economic Indices of Functioning Distributed Computer Systems and Readability Function of Solving Complex Problems / V.G. Khoroshevsky, K.V. Pavsky, D.S.Nikitin // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2008. - № 2(3). - С. 70-76.

20. Павский, В.А. Расчет показателей осуществимости решения набора сложных задач на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Искусственный интеллект. - 2008. - №4. - С. 682-685.

21. Хорошевский, В.Г. Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Искусственный интеллект. - 2009,- №4. - С.92-99.

22. Pavsky, K.V. Realizability of parallel solving complex problems on distributed computer systems / K.V. Pavsky П Internationales Wissenschaftliches Kolloquium: in Proceedings. - Ilmenau: Technische Universitaet, 2000. -P. 823-828.

23. Павский, K.B. Анализ реконфигурации на распределенных вычислительных системах / К.В. Павский // Информационные системы и технологии: в 3 т. - Т.З.: мат-лы межд. науч.-техн. конф. - Новосибирск: НГТУ, 2000. - С. 468-470.

24. Pavsky, K.V. Stochastic analysis of solving complex problem on distributed computer systems / K.Y. Pavsky // Proceed of PARELEC 2006: International Symposium on Parallel Computing in Electrical Engineering. - Bialystok, Poland: IEEE Computer Society press, 2006. -P.271-274.

25. Павский, B.A. Вычисление показателей осуществимости решения задач на вычислительных системах 1 В.А. Павский, В.Г. Хорошевский, К.В. Павский // Искусственный интеллект. Интеллектуальные и многопроцессорные системы 2006: в 2 т. - Т.2.: мат-лы 7-ой межд. науч.-техн. конф. - Украина: изд-во ТРТУ, 2006. — С.14 -17.

26. Павский, В.А. Вычисление показателей осуществимости решения задач на вычислительных системах / В.А. Павский, В.Г. Хорошевский, К.В. Павский // Высокопроизводительные вычислительные системы: матчлы 3-ой межд. науч. молодежной школы. - Украина, 2006. - С.16-19.

27. Павский, К.В. Исполнение параллельных программ на неоднородной вычислительной системе / К.В. Павский // Информатика и проблемы телекоммуникаций: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2006. - С.

327-328.

28. Павский, К.В. Эффективность исполнения параллельных программ на кластерной ВС / К.В. Павский, A.C. Посохов // Информатика и проблемы телекоммуникаций: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2006. - С.

328-329.

29. Хорошевский, В.Г. Модель для расчета показателей живучести вычислительных систем со структурной избыточностью/ В.Г.Хорошевский, В.А. Павский, К.В. Павский // Многопроцессорные вычислительные и управляющие системы: в 2 т. - Т.1.: мат-лы межд. науч.-техн. конф. - Таганрог: Изд-во ТТИ ЮФУ, 2007. - С.152-157.

30. Павский, В.А. Расчет показателей осуществимости решения задач на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Системный анализ и информационные технологии: мат-лы второй межд. конф. - Обнинск, 2007. - 2 т., - С. 174-178.

31. Павский, К.В. Модель для расчета функции осуществимости параллельного решения задач на распределенных вычислительных системах / К.В. Павский // Информатика и проблемы телекоммуникаций: в 2. - Т.1.: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2008. - С. 151-152.

32. Павский, В.А. Условие осуществимости решения сложных задач на живучих распределенных вычислительных системах / В.А. Павский, К.В. Павский // Информатика и проблемы телекоммуникаций: в 2 т. - Т.1.: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2008. - С. 149-150.

33. Хорошевский, В.Г. Модель для расчета показателей надежности распределенных вычислительных систем / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Моделирование-2008: в 2 т. - Т.2.: труды межд. науч.-техн. конф. - Киев, 2008. - С. 483-488.

34. Павский, В.А. Расчет показателей осуществимости решения набора сложных задач на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Системы и средства искусственного интеллекта (ССИИ-2008): мат-лы межд. науч. Школы. - Украина: пос. Кацивели, 2008. - С. 170 - 173.

35. Хорошевский, В.Г. Расчет показателей осуществимости решения задач потока на распределенных вычислительных системах / В.Г. Хорошевский, В.А. Павский, К.В. Павский // ММГ-2008: труды межд. конф. по математическим методам в геофизике. - Новосибирск: ИВМиМГ СО РАН, 2008 -CD-ROM.

36. Павский, В.А. Оценки показателей осуществимости решения задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // ММГ-2008: труды межд. конф. по математическим методам в геофизике. -Новосибирск: ИВМиМГ СО РАН, 2008 - CD-ROM.

37. Павский, В.А. Расчет показателей эффективности решения задач потока с отказами на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Многопроцессорные вычислительные и управляющие системы (МВУС-2009): мат-лы межд. науч.-техн. конф.: в 2 т. - Т.2. - Таганрог: ТТИ ЮФУ, 2009. - С. 65 - 67.

38. Павский, В.А., Модель для расчета осуществимости решения сложных задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Информатика и проблемы телекоммуникаций: в 2 т. - Т.1.: Росс, науч.-техн. конф. - Новосибирск, 2009. - С. 129-130.

39. Павский, В.А. Расчет показателей эффективности функционирования распределенных вычислительных систем при решении задач потока с отказами / В.А. Павский, К.В. Павский // Мат-лы 5-ой Сибирской конф. по параллельным вычислениям. - Томск: ТГУ, 2009. - С. 145-148.

40. Павский, В.А. Осуществимость решения задач потока с потерями на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Информатика и проблемы телекоммуникаций: мат-лы Росс, науч.-техн. конф. -Новосибирск, 2010. - С. 170-171.

41. Павский, К.В. Эффективность исполнения параллельных программ предварительной обработки изображений на кластерных вычислительных системах / К.В. Павский, Л.Н. Чирва // Информатика и проблемы

телекоммуникаций: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2010. - С. 172-173.

42. Павский, В.А. Математическая модель для расчета показателей функционирования вычислительных систем со структурной избыточностью / В.А. Павский, К.В. Павский // Суперкомпьютерные технологии. Разработка, программирование, применение: в 2 т. - Т.2.: мат-лы межд. науч.-техн. конф. -Таганрог: Изд-во ТТИ ЮФУ, 2010. - С. 71 - 73.

43. Хорошевский, В.Г. Методы анализа эффективности функционирования распределенных вычислительных систем / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Распределенные информационные и вычислительные ресурсы (DICR'2010): мат-лы XIII Росс. конф. с участием иностранных ученых. -Новосибирск, 2010. - CD-ROM.

44. Павский, В.А. Оценки показателей функционирования вычислительных систем со структурной избыточностью / В.А. Павский, К.В. Павский // Информатика и проблемы телекоммуникаций: мат-лы Росс, науч.-техн. конф." -Новосибирск, 2011. - С. 209-210.

45. Павский, В.А. Стохастическая модель функционирования распределенных вычислительных систем при решении сложных задач / В.А. Павский, К.В. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2012. - С. 164166.

46. Хорошевский, В.Г. Стохастическое моделирование распределенных вычислительных систем с резервом / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Суперкомпьютерные технологии» (СКТ-2012): мат-лы 2-й Всеросс. науч.-техн. конф. - Ростов-на-Дону: Изд. ЮФУ, 2012. - С. 330-333.

47. Павский, В.А. Расчет показателей эффективности решения задач потока с отказами на распределенных вычислительных системах с накопителем / В.А. Павский, К.В. Павский // Танаевские чтения: мат-лы докладов пятой межд. науч. конф. - Минск: ОИПИ HAH Беларуси, 2012. - С. <50-83.

48. Павский, К.В. Имитационная модель функционирования большемасштабных распределенных вычислительных систем со структурной избыточностью/ К.В. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2013-С. 135-136.

49. Павский, К.В. Математическая модель для оценки функции осуществимости решения сложной задачи на распределенных вычислительных системах / К.В. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2013.-С. 136-137.

50. Ефимов, A.B. Средства формирования резерва для отказоустойчивого выполнения параллельных программ / A.B. Ефимов, К.В. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2013. - С. 162-163.

51. Павский, В.А. Оценка вероятности пребывания распределенных вычислительных систем в состоянии низкой производительности/ В.А.

Павский, K.B. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2013.-С. 165-166.

52. Павский, К.В. Модель функционирования распределенных вычислительных систем с отказами и полным восстановлением / К.В. Павский, В.А. Павский // Обработка информационных сигналов и математическое моделирование: мат-лы Росс, науч.-техн. конф. - Новосибирск, 2013. - С. 167168.

53. Павский, В.А. Аналитический анализ функционирования вычислительных систем со структурной избыточностью / В.А. Павский, К.В. Павский // 6-я Всеросс. мультиконф. по проблемам управления (МКПУ-2012): в 4 т. - Т.4: мат-лы 6-й Всеросс. мультиконф. - Ростов-на-Дону: Изд-во ЮФУ, 2013. - С. 6670.

Авторские свидетельства

54. Свидетельство о государственной регистрации программы для ЭВМ №2012613763. Средства вложения и отказоустойчивого выполнения параллельных программ для вычислительных систем экзафлопсного уровня производительности / В.Г.Хорошевский, М.Г. Курносов, О.В. Молдованова,

A.A. Пазников, А.Ю. Поляков, К.В Павский, С.Н. Мамойленко; заявитель и правообладатель ФГОБУ ВПО «СибГУТИ», зарег. 20.04.2012.

55. Свидетельство о государственной регистрации программы для ЭВМ №2012614642. Программа для расчета функции осуществимости решения параллельных задач на распределенных вычислительных системах /

B.Г. Хорошевский, К.В. Павский; заявитель и правообладатель ИФП СО РАН, зарег. 24.05.2012.

56. Свидетельство о государственной регистрации программы для ЭВМ № 2013613353. Программа стохастическая модель для расчета среднего времени решения параллельных задач на распределенных вычислительных системах / К.В. Павский, В.А. Павский; заявитель и правообладатель ИФП СО РАН, зарег. 02.04.2013.

Личный вклад автора в совместные публикации

Все основные результаты, выносимые на защиту, получены диссертантом лично, либо в составе коллектива Лаборатории вычислительных систем ИФП СО РАН под руководством член-корр. РАН Хорошевского В.Г.

Лично, либо в составе группы авторов выполнены постановка задачи [2, 3, 6, 7, 9, 10, 12-16], разработка методов нахождения числовых характеристик случайной величины и оценки погрешности расчета показателей [4-6], нахождение аналитических решений полученных дифференциальных уравнений [6, 7, 10, 12-15], разработка конфигурации пространственно-распределенной мультикластерной ВС и инструментария параллельного мультипрограммирования [1, 8, 54].

Павский Кирилл Валерьевич

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

Автореферат диссертации на соискание ученой степени доктора технических наук

Подписано в печать "24" декабря 2013 г. Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л.2,25, заказ № 90, тираж 170 экз., ФГОБУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ФИЗИКИ ПОЛУПРОВОДНИКОВ ИМ. A.B. РЖАНОВА СИБИРСКОГО ОТДЕЛЕНИЯ РАН

0520'i 450770

На правах рукописи

Павский Кирилл Валерьевич

МЕТОДЫ РАСЧЕТА ПОКАЗАТЕЛЕЙ И АНАЛИЗ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ БОЛЫНЕМАСШТАБНЫХ РАСПРЕДЕЛЕННЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность:

05.13.15 - Вычислительные машины, комплексы и компьютерные сети

ДИССЕРТАЦИЯ

на соискание ученой степени доктора технических наук

Научный консультант -доктор технических наук профессор

член-корреспондент РАН заслуженный деятель науки РФ В. Г. Хорошевский

Новосибирск - 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..............................................................................................................7

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР. АРХИТЕКТУРА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.................................12

1.1. Концептуальные основы построения большемасштабных вычислительных систем (модель коллектива вычислителей)......................12

1.1.1. Архитектурные свойства вычислительных систем......................12

1.2. Распределенные вычислительные системы......................................19

1.2.1. Система IBM Sequoia.......................................................................21

1.2.2. Система Cray ХК7 Titan...................................................................21

1.2.3. Система МВС-ЮОК..........................................................................22

1.2.4. Семейство живучих распределенных вычислительных систем с программируемой структурой МИКРОС.....................................................23

1.2.5. Система управления заданиями TORQUE.....................................26

1.2.6. Планировщик заданий MAUI..........................................................26

1.2.7. Пакет MOJOS поддержки мультипрограммных режимов обработки наборов масштабируемых задач.................................................27

1.2.8. Средства создания контрольных точек..........................................28

1.3. Надежность распределенных вычислительных систем..........................29

1.3.1. Основные понятия надежности ЭМ....................................................29

1.3.2. Вероятность безотказной работы ЭМ.................................................31

1.3.3. Вероятность восстановления ЭМ........................................................34

1.3.4. Вычислительные системы со структурной избыточностью.............35

1.3.5. Показатели надёжности вычислительных систем.............................37

1.3.6. Расчёт показателей надёжности для переходного режима функционирования вычислительных систем...............................................42

1.3.7. Расчёт показателей надёжности для стационарного режима работы вычислительных систем..................................................................................44

1.4. Живучесть вычислительных систем.........................................................45

1.4.1. Живучие ВС...........................................................................................45

1.4.2. Показатели потенциальной живучести вычислительных систем ....47

1.5. Осуществимость решения задач на вычислительных системах............52

1.5.1. Функция осуществимости решения задач на живучих вычислительных системах..............................................................................53

1.6. Направления исследования эффективности функционирования распределенных вычислительных ВС, цель и задачи исследований...........55

ГЛАВА 2. СТРУКТУРА РАБОТЫ И ОРГАНИЗАЦИЯ ПРОВЕДЕНИЯ ИССЛЕДОВАНИЙ................................................................................................58

2.1. Организация и схема исследований..........................................................58

2.2. Объекты исследований...............................................................................63

2.3. Методы исследований................................................................................67

2.3.1. Метод производящих функций............................................................67

2.3.2. Методы операционного исчисления...................................................68

2.3.3. Метод составления дифференциальных уравнений..........................70

2.3.4. Методы распараллеливания решения задач.......................................71

ГЛАВА 3. СТОХАСТИЧЕСКИЕ МОДЕЛИ ФУНКЦИОНИРОВАНИЯ И РАСЧЕТ ПОКАЗАТЕЛЕЙ НАДЕЖНОСТИ И ЖИВУЧЕСТИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.................................74

3.1. Модель функционирования распределенных вычислительных систем со структурной избыточностью.......................................................................74

3.1.1. Расчет вероятностей состояний восстанавливающей системы........74

3.1.2. Условие сохранения высокой производительности распределенной ВС......................................................................................................................75

3.1.3. Математическое ожидание и дисперсия числа машин в восстанавливающей системе..........................................................................79

3.1.4. Функция F(t) - вероятности времени нахождения вычислительной системы в состоянии низкой производительности......................................86

3.1.5. Погрешность функции F(t)................................................................96

3.2. Модель функционирования вычислительных систем со структурной избыточностью (произвольное число состояний)..........................................96

3.2.1. Вероятности состояний восстанавливающей системы.....................97

3.2.2. Математическое ожидание и дисперсия числа машин в восстанавливающей системе..........................................................................98

3.3. Модель функционирования вычислительных систем со структурной избыточностью без восстанавливающей системы.......................................104

3.3.1. Вероятности состояний резерва, математическое ожидание и дисперсия числа машин в восстанавливающей системе...........................105

3.3.2. Приближенное решение для оценки среднего числа машин резерва .........................................................................................................................108

3.4. Модель функционирования распределенных вычислительных систем со структурной избыточностью (конечное число состояний)....................110

3.4.1. Вероятности состояний восстанавливающей системы...................111

3.4.2. Математическое ожидание числа отказавших машин и его дисперсия........................................................................................................122

3.5. Модель функционирования ВС без структурной избыточности........127

3.5.1. Математическое ожидание отказавших машин и его дисперсия... 127

3.6. Модель функционирования ВС со структурной избыточностью (произвольное число состояний, усложненный процесс)...........................133

3.6.1. Модель функционирования вычислительных ВС...........................135

3.6.2. Функция F{t) - вероятности времени нахождения вычислительной системы в состоянии низкой производительности....................................144

3.6.3. Погрешность функции F{t)...............................................................149

3.7. Выводы по третьей главе.........................................................................151

ГЛАВА 4. СТОХАСТИЧЕСКИЕ МОДЕЛИ И РАСЧЕТ ПОКАЗАТЕЛЕЙ ОСУЩЕСТВИМОСТИ РЕШЕНИЯ ЗАДАЧ НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ................................................................153

4.1. Модель для расчета показателей осуществимости решения задач на

распределенных вычислительных систем с накопителем...........................153

4.1.1. Вычисление вероятностей состояний накопителя, математическое ожидание и дисперсия числа задач в накопителе......................................153

4.1.2. Оценка наполненности накопителя...................................................154

4.1.3. Оценка вероятности того, что накопитель наполнен сверх критического уровня задачами и будет находиться в таком состоянии в течение времени не меньшего заданного....................................................161

4.2. Модель для оценки осуществимости решения задач потока...............162

4.3. Модель для оценки функции осуществимости параллельного решения сложных задач..................................................................................................163

4.3.1. Коэффициент ускорения решения части задачи на ВС...................164

4.3.2. Оценка времени решения параллельных задач на распределенных ВС....................................................................................................................164

4.3.3. Оценка функции осуществимости параллельного решения задач на ВС (система интегральных уравнений. Отказы и восстановления происходят согласно процессу рождения и гибели)..................................164

4.3.4. Оценка функции осуществимости параллельного решения задач на ВС (система интегральных уравнений. Отказы и восстановления происходят согласно модели функционирования ВС без структурной избыточности)................................................................................................167

4.3.5. Оценка функции осуществимости параллельного решения задач на ВС (Отказы и восстановления происходят согласно процессу рождения и гибели)............................................................................................................167

4.3.6. Оценка функции осуществимости параллельного решения задач на ВС (модель функционирования ВС без структурной избыточности).....168

4.3.7. Расчет и анализ функции осуществимости параллельного решения задач................................................................................................................169

4.4. Выводы по четвертой главе.....................................................................173

ГЛАВА 5. МУЛЬТИКЛАСТЕРНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА И ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ....................................................................174

5.1. Мультикластерная вычислительная система.........................................174

5.1.1. Конфигурация пространственно-распределённой мультикластерной вычислительной системы.............................................................................174

5.1.2. Структура программного обеспечения пространственно-распределенной мультикластерной вычислительной системы................175

5.1.3. Средства формирование резерва для отказоустойчивого выполнения параллельных программ на кластерных вычислительных системах.......177

5.2. Показатели эффективности параллельных алгоритмов.......................178

5.3. Имитационная модель функционирования распределенной вычислительной системы со структурной избыточностью........................180

5.3.1. Численное моделирование.................................................................180

5.3.2. Параллельный алгоритм.....................................................................183

5.4. Параллельные алгоритмы расчета функции осуществимости решения задач на ВС.......................................................................................................186

5.4.1. Параллельные алгоритмы расчета функции осуществимости решения задач на ВС (интегральный вид)..................................................186

5.4.2. Параллельные алгоритмы расчета функции осуществимости решения задач на ВС.....................................................................................190

5.5. Выводы по пятой главе............................................................................195

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ......................................................196

СПИСОК ЛИТЕРАТУРЫ...................................................................................198

ПРИЛОЖЕНИЯ...................................................................................................235

ПРИЛОЖЕНИЕ 1.............................................................................................236

ПРИЛОЖЕНИЕ 2.............................................................................................242

ПРИЛОЖЕНИЕ 3.............................................................................................243

ПРИЛОЖЕНИЕ 4.............................................................................................244

ВВЕДЕНИЕ

Актуальность темы. Распределенные вычислительные системы (ВС) относятся к высокопроизводительным вычислительным средствам. Архитектура распределенных ВС представляется в виде композиции множества элементарных машин или процессоров, соединенных телекоммуникационной сетыо. В таких системах все основные ресурсы (не только арифметико-логические устройства, но и память, и средства управления) являются и логически, и технически распределенными. Количество ядер в ВС может достигать миллионов. Именно поэтому подобные ВС относят к масштабируемым и большемасштабным. Проектирование и развитие распределенных болыиемасштабных вычислительных систем, в ряду вычислительных средств высокой производительности, занимает одно из приоритетных направлений науки и техники.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские, российские и зарубежные учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, И.А. Каляев, JI.H. Королев, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко, S. Cray, D. Slotnick, I. Foster, M. Flynn, С. Kesselman, J. Dongara, L. Lamport, M. Livny и другие [1-116].

По архитектурным возможностям промышленные ВС достаточно близки к вычислительным системам с программируемой структурой, концептуальные основы построения которых сформировались в Сибирском отделении РАН к началу 70-х годов 20 столетия [13, 16, 63, 64].

Примером отечественных ВС с программируемой структурой могут служить: первая система "Минск - 222" (1965 г.); мультиминимашинные ВС

7

МИНИМАКС (1975 г.) и СУММА (1976 г.); мультипроцессорные живучие системы семейства МИКРОС (МИКРОС-1, 1986 г., МИКРОС-2, 1992 г. МИКРОС-Т 1998 г.); суперкомпьютеры семейства МВС (МВС-100 и МВС-1000, 1999 г.) [13,31, 16,41-43].

Объединение ВС в пространственно распределенную среду рассматривается как одна из альтернатив построения сверхпроизводительпых средств обработки информации. К ним относятся большемасштабные вычислительные системы, важным архитектурным свойством которых является надежность, живучесть [16, 67, 68, 70, 146-156]. Отказ или восстановление элементарной машины может приводить лишь к изменению производительности ВС и не допускать аварийного завершения решения задач пользователей. Для таких систем важна и организация функционирования в основных режимах (режим решения сложной задачи, обработки наборов задач, обслуживание потоков задач) [16, 68, 69, 71, 141-143, 157-162]. Поэтому перспективным является разработка средств анализа и оптимизации живучего функционирования распределенных ВС [83-86, 116-145].

В силу своей болынемасштабности современные распределенные ВС требуют создания сложных многопараметрических моделей их функционирования, а это приводит к тому, что оценка меры адекватности моделей становится трудновыполнимой. Построение же простых моделей приводит, скорее, к качественным, чем количественным оценкам функционирования систем. Следовательно, создание одновременно простых и эффективных математических моделей с параметрами, основанными на качественной или достоверной, потенциально возможной, статистике, является актуальным.

Методы исследования. Для решения поставленных задач использовались методы теории вероятностей, случайных процессов, массового обслуживания (ТМО), математического анализа, теории функции комплексного переменного [163-192]. Экспериментальные исследования осуществлялись путём моделирования на пространственно-распределённой мультикластерной ВС [74].

Научная новизна. Предложены новые и развиты имеющиеся стохастические модели функционирования распределенных (однородных) вычислительных систем, позволившие рассчитать показатели надежности, живучести и осуществимости решения задач на распределенных ВС.

1. Разработана методика применения случайного процесса, описывающего функционирование распределенных ВС со структурной избыточностью.

2. Получена функция распределения времени нахождения распределенных ВС в состоянии низкой производительности.

3. Разработан алгоритмический и программный инструментарий анализа эффективности решения задач на распределенных ВС.

Практическая значимость и реализация работы. Разработанные модели и методы, полученные формулы и алгоритмы являются практическим инструментом анализа эффективности функционирования большемасштабных распределенных ВС.

Основные результаты исследований нашли применение в работах по развитию программного обеспечения для пространственно-распределённой мультикластерной ВС Центра параллельных вычислительных технологий (ЦПВТ) Федерального государственного образовательного бюджетного учреждения высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО «СибГУТИ») и Лаборатории ВС ИФП СО РАН. Основные этапы работы выполнены в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 20072013 годы». ГК № 02.514.11.0002, Разработка программных технологий для развития российского сегмента Грид систем параллельного программирования, систем компьютерной графики и «Научные и научно-педагогические кадры инновационной России». ГК № 02.740.11.0006, Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ».грант в виде субсидий №8228, Разработка алгоритмических и

программных средств моделирования наноструктур с квантовыми точками на информационно-вычислительных системах), при поддержке грантов Российского фонда фундаментальных исследований №№ 97-01-00883, 99-0790206, 00-01-00126, 01-01-06246, 02-01-06518, 02-07-90379, 05-07-90009, 06-0701817, 07-07-00142, 08-08-00300, 09-07-00185, 10-07-00157, 12-07-00145, 13-0700160, Совета Президента РФ по поддержке ведущих научных школ №№ НШ-9505.2006.9, НШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9 и ФГОБУ ВПО «СибГУТИ» (2008-2013).

Получено три Свидетельства о государственной регистрации программ для ЭВМ (ЬШ) №№ 2012614642, 2012613763, 2013613353.

Результаты работы внедрены в учебный процесс ФГОБУ ВПО «СибГУТИ», в систему мультипрограммирования пространственно-распределенной мультикластерной ВС ЦПВТ ФГОБУ ВПО «СибГУТИ», в проект Сибнет ОАО «Ростелеком», что подтверждается соответствующими актами.

Автор защищает

1. Модели и методы расчета показателей надежности и жив�