Разработка средств анализа функционирования распределенных вычислительных систем и сетей тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Павский, Кирилл Валерьевич

• Павский, Кирилл Валерьевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Павский, Кирилл Валерьевич

ВВЕДЕНИЕ

ГЛАВА 1. АРХИТЕКТУРА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ

СИСТЕМ И СЕТЕЙ

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

1.1.1. Модель вычислителя.

1.1.2. Модель коллектива вычислителей.

1.1.3. Принципы построения вычислительных систем.

1.1.4. Алгоритм функционирования вычислительной системы.

1.1.5. Модель вычислительной системы.

1.1.6. Принципы технической реализации модели коллектива вычислителей

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

1.2. Структура сетей передачи информации.

1.2.1. Требования, предъявляемые к структурам.

1.2.2. Структурные характеристики.

1.2.3. Оптимальные структуры.

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

1.3.1. Вычислительная система МИКРОС, МИКРОС-2, МИКРОС-Т.

1.3.2. Функциональная структура ВС МИКРОС.

1.3.3. Программное обеспечение МИКРОС.

1.3.4. Архитектурные свойства систем семейства МИКРОС.

1.4. Система обработки изображений.

1.5. Кластерные вычислительные системы.

1.5.1. Принципы построения кластерных вычислительных систем.

1.5.2. Кластерная Опс1-система.

1.6. Выводы.

ГЛАВА 2. НАДЕЖНОСТЬ И ЖИВУЧЕСТЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

2.1. Надежность ЭВМ.

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

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

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

2.2. Надежность ВС с программируемой структурой.

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

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

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

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

2.2.5. Выводы.

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

2.3.1. Живучие вычислительные системы.

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

2.3.3. О методике расчёта показателей живучести вычислительных систем.

2.3.4. Расчёт функции потенциальной живучести вычислительных систем.

2.3.5. Выводы.

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

3.1. Континуальный подход к анализу осуществимости решения задач.

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

3.2.1. Дифференциальный коэффициент ускорения решения параллельных задач на ВС.

3.2.2. Сложная реконфигурация ВС.

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

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

3.2.5. Дискретный анализ осуществимости решения задач.

3.3. Анализ осуществимости решения задач потока на ВС.

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

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

3.4. Выводы.

ГЛАВА 4. ОТКАЗОУСТОЙЧИВЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

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

4.2. Алгоритмы предварительной обработки изображений.

4.2.1. Алгоритмы сглаживания и удаления помех изображения.

4.2.2. Алгоритмы оконтуривания и контрастирования изображений.

4.2.3. Параллельные алгоритмы предварительной обработки изображений.

4.2.4. Алгоритм вложения графа текущей конфигурации ВС в граф полной конфигурации.

4.2.5. Численный анализ осуществимости реализации параллельных алгоритмов обработки изображений.

4.3. Алгоритмы имитации изображений на основе волновой модели.

4.3.1. Волновая модель.

4.3.2. Параллельный алгоритм имитации изображений на основе волновой модели

4.4. Алгоритмы оценивания сдвигов и поворотов изображений на последовательности кадров.

4.4.1. Модель межкадровых смещений.

4.4.2. Псевдоградиентный алгоритм оценки сдвигов и поворотов.

4.4.3. Параллельный алгоритм оценивания сдвигов и поворотов изображений на последовательности кадров.

4.4.4. Параллельная реализация ускоренного псевдоградиентного алгоритма оценки сдвигов и поворотов изображений на последовательности кадров.

4.4.5. Ускоренный последовательный псевдоградиентный алгоритм оценки сдвигов и поворотов изображений на последовательности кадров.

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка средств анализа функционирования распределенных вычислительных систем и сетей»

Характерной особенностью современной индустрии информатики является создание распределенных вычислительных систем (ВС) высокой производительности (109 - 1015 опер./с, GigaFLOPS - PetaFLOPS). Архитектура распределенных ВС представляется в виде композиции множества элементарных машин или процессоров, соединенных телекоммуникационной системой. В таких системах все основные ресурсы (не только арифметико-логические устройства, но и память и средства управления) являются и логически и технически распределенными. Число элементарных машин (ЭМ) в распределенных ВС допускает варьирование и заключено в пределах от 10 до 106 [117]; например, это число в системе IBM Blue Gene может достигать 1 ООО ООО. Именно поэтому подобные ВС относят к масштабируемым и большемас-штабным.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков, В.В. Губарев, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, М.А. Карцев, J1.H. Королев, H.A. Кузнецов, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, В.К. Попков, ДА. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, A.M. Федотов, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко и другие [4-12, 14-18, 22-24, 30-37, 40-47, 55, 57, 58, 60-62,67, 68, 85-87, 90-92, 95-97, 99, 105, 108, 111, 114, 115, 117, 125, 129-134, 139, 140].

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

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

Объединение вычислительных систем в пространственно распределенную среду рассматривается как одна из альтернатив построения сверхвысокопроизводительных средств обработки информации. Использование Grid технологий помогает решить эту задачу. В качестве коммуникационной среды Grid-систем используется сеть Интернет и стандартные протоколы передачи данных (в настоящее время эти протоколы основаны на TCP/IP) [29]. Состав и структура Grid-систем может изменяться во времени, например, ресурсы могут быть неожиданно выведены из состава системы (по желанию владельца или отказа). Следовательно, в силу своей природы такие системы являются сложными стохастическими объектами. Глубокий анализ и моделирование поведения Grid-систем позволяют прогнозировать их работу и организовывать управление, близкое к оптимальному.

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

- осуществимость решения задач на ВС;

- отказоустойчивые вычисления.

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

В зависимости от сложности задач и характера их поступления выделяются следующие основные режимы работы распределенных ВС [117, 119]:

- решение одной сложной задачи,

- обработка набора задач,

- обслуживание потока задач.

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

Цель и задачи работы

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

В соответствии с поставленной целью определены следующие задачи исследования:

- анализ архитектурных особенностей семейства вычислительных систем МИК-РОС и кластерных ВС;

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

- расчет показателей осуществимости параллельного решения задач;

- параллельное моделирование осуществимости решения задач;

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

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

Научная новизна

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

1. Выведены формулы для расчета среднего времени решения сложных задач на распределенных ВС.

2. Построена система интегральных уравнений для расчета вероятности осуществления параллельного решения задач на Grid системах.

3. Получены формулы для расчета показателей осуществимости решения задач потока на распределенных ВС (Grid системах).

4. Сформулирована модель сложной реконфигурации ВС и произведен ее анализ.

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

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

7. Проведены вычислительные эксперименты и осуществлено параллельное моделирование разработанных методов и алгоритмов на системах семейства МИКРОС и кластерной Grid-системе.

Практическая ценность

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

2. Полученные формулы для функции осуществимости решения параллельных задач потока позволяют оценить полезную нагрузку на ресурсы Grid-системы.

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

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

5. Разработанный ускоренный алгоритм сдвигов и поворотов на последовательности кадров изображения дает 2-6 кратное увеличение в скорости сходимости по сравнению с простым алгоритмом.

6. Средства визуализации структуры системы МИКРОС-Т основаны на рекурсивном алгоритме наложения графа текущей структуры ВС на исходную.

7. Созданные средства являются простыми и эффективными инструментами для анализа осуществимости параллельного решения задач на распределенных ВС (Grid-системах) и позволяют эффективно использовать их ресурсы.

Реализация работы

Результаты работы доведены до параллельных программ анализа осуществимости параллельного решения задач и отказоустойчивых алгоритмов и программ обработки изображений на распределенных ВС. Они были использованы при создании аппаратурно-программных средств семейства распределенных систем МИКРОС, а также при разработке кластерной Grid-системы.

Диссертант принимал непосредственное участие в работах, выполняемых по Федеральной целевой научно-технической программе «Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения" (приоритетное направление «Информационные технологии и электроника", подпрограммы «Перспективные информационные технологии" и «Информатизация России"). Кроме того, соискатель был одним из основных исполнителей проектов Российского фонда фундаментальных исследований: № 97-01-00883, № 97-01-05011, № 99-07-90206, № 99-01-05018, № 99-07-90438, № 00-01-00126, №02-01-06518, №02-0790379, №02-07-90380.

Результаты исследований внедрены в Научно-учебном центре параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ).

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на:

- Международных научно-технических конференциях "Информатика и проблемы телекоммуникаций", Новосибирск, 1994, 1995, 2001;

- Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2000;

- Пятом и Шестом международных семинарах «Распределенная обработка информации», Новосибирск, 10-12 октября 1995 г., 23-25 июня, 1998;

- Международной научно-технической конференции «Информационные системы и технологии», Новосибирск, 8-11 ноября, 2000;

- 45. Internationales Wissenschafliches Kolloquium, Germany, Ilmenau, 0406.10.2000.

- Международной конференции "Интеллектуальные и многопроцессорные системы", 1-6 октября 2001 г., пос. Дивноморское Геленджикского района;

- Региональная научная конференция студентов, аспирантов и молодых ученых "Наука, техника, инновации", 5-8 декабря, 2002 г., Новосибирск.

Публикации

Содержание диссертации отражено в 14 печатных работах и 8 научных отчетах.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав и заключения. Содержит 161 страница с приложением, 9 таблиц и 24 рисунка. Список литературы содержит 140 наименований.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Павский, Кирилл Валерьевич

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

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

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

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

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

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

6. Разработаны параллельные алгоритмы анализа осуществимости решения задач для распределенных ВС. Моделирование на системе МИКРОС-Т и кластерной ВС показало, что алгоритмы характеризуются ускорением, близким к линейному.

7. Создан комплекс параллельных отказоустойчивых программ предварительной обработки изображений. Разработаны средства отображения структуры ВС МИКРОС-Т, основанные на рекурсивном алгоритме наложения текущего графа межмашинных связей на исходный.

8. Построены параллельные алгоритмы имитации изображений на основе волновой модели и алгоритмы оценивания сдвигов и поворотов на последовательности кадров. Предложен ускоренный алгоритм оценивания сдвигов и поворотов изображений на последовательности кадров, который характеризуется 2-6 кратным ускорением сходимости по сравнению с обычным.

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

130

Список литературы диссертационного исследования кандидат технических наук Павский, Кирилл Валерьевич, 2004 год

1. Авен О.И., Турин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

2. Аляутдинов Д.А., Далевич А.Н. Параллельный Си. М., 1991. -111 с.

3. Бакут П. А., Колмогоров Г.С. Сегментация изображений: Методы выделения границ областей.//Зарубежная радиоэлектроника. 1987. - № 10. - С.25-46.

4. Балашов Е.П., Григорьев B.JI., Петров Г.А. Микро и мини-ЭВМ. Уч. пос. для ВУЗов. -JL: Энергоатомиздат. Ленинградское отд., 1984. 376 с.

5. Балашов Е.П., Пузанков Д.В. Микропроцессоры и микропроцессорные системы: уч. пособие для ВУЗов / В.Б.Смолов. М.: Радио и связь, 1981. - 326 с.

6. Бетелин В.Б., Грузипова Е.В., Кольцова A.A. и др. Архитектура цифровых процессоров обработки сигналов. М.: РАН. Научный совет по комплексной проблеме «Кибернетика», 1994. - 20 с.

7. Бурцев B.C. О необходимости создания супер-ЭВМ в России// Информационные технологии и вычислительные системы. 1995. - №1. - С.5-11.

8. Бурцев B.C. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ. М.: ИВВС РАН, 1997.

9. Бурцев B.C. Принципы построения многопроцессорных вычислительных комплексов «Эльбрус». М.: ИТМ и ВТ, 1977. - 53 с.

10. Бурцев B.C. Тенденция развития супер-ЭВМ// В сб. трудов: Вычислительные машины с нетрадиционной архитектурой супер-ВМ. М.: Наука, 1990. - С. 3-26.

11. Васильев В.В., Додонов А.Г. Многопроцессорные вычислительные структуры для анализа экстремальных задач на сетях. В кн.: Проблемы электроники вычислительной техники. - К., «Наукова думка», 1976. - С. 85-97.

12. Васильев В.В., Кузьмук В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем. К.: Наук. Думка, 1990. — 216 с.

13. Васильев К.К., Крашенинников В.Р. Методы фильтрации многомерных случайных полей. Саратов: Изд-во Сарат. ун-та, 1990. - 128 с.

14. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука, 1988.-480с.

15. Вентцель Е.С. Исследование операций. М.: Сов. радио, 1972. - 551 с.

16. Вишневский В.М. Задачи оптимального управления в телеавтоматических системах массового обслуживания. Автореф. дис. на соиск. научн. ст. к.т.н. (05.13.01). — М., 1974.-23 с.

17. Водяхо А.И., Горпец H.H., Пузанков Д.В. Высокопроизводительные системы обработки данных: уч. пос. для ВУЗов. М.: Высшая шк., 1997. - 304 с.

18. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Петербург: БХВ, 2002г. -609 с.

19. Воробьев В.А. Простейшие структуры однородных вычислительных систем. В кн.: Вычислительные системы, вып. 60. Новосибирск, Изд-во СО РАН СССР, 1974.20