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

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

УДК 681.324

ПАВСКИЙ Кирилл Валерьевич

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

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

05.13.13 - "Телекоммуникационные системы и компьютерные сети" 05.13.15 - "Вычислительные машины и системы"

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

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

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

Научный руководитель -

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

член-корреспондент РАН Хорошевский Виктор Гаврилович

Официальные оппоненты:

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

Губарев Василий Васильевич

доктор физико-математических наук, профессор

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

Ведущая организация -

Институт автоматики и электрометрии СО РАН

Защита состоится " {?" ^¿^О^ 200_г. в_часов на заседании

Специализированного диссертационного совета Д 219.005.01 при ГОУ ВПО "Сибирский государственный университет телекоммуникации и информатики", по адресу: г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО "СибГУТИ". Автореферат разослан 2004 г.

Учёный секретарь

диссертационного совета Д219.005.01 кандидат технических наук, профессор

Б.И. Крук

Wf/fj

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

А.В. Забродин, Л.Н. Королев, Г.И. Марчук, Прангишвили,

Актуальность темы

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

сти Архитектура распределенных В

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

пределах от 10 до 10 ; например, это число в системе IBM Blue Gene может достигать 1 000 000. Именно поэтому подобные ВС относят к масштабируемым и боль-шемасштабным.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков, В.В. Губарев, В.Ф. Евдокимов, Э.В. Евреинов, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, М.А. Карцев, Н.А. Кузнецов, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Ю.И. Митропольский, В.К. Попков, Д.А. Поспелов, И.В: Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, A.M. Федотов, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко и другие.

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

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

Объединение вычислительных систем в пространственно распределенную среду рассматривается как одна из альтернатив построения сверхвысокопроизводительных средств обработки информации. Использование Grid технологий помогает решить эту задачу. В качестве коммуникационной среды Grid-систем используется сеть Интернет и стандартные протоколы передачи данных (в настоящее время эти протоколы основаны на TCP/IP). Состав и структура Grid-систем может изменяться во времени, например, р " «тут быть Д'-ГР'*Т*Ч1-' систе-

м ы (по желанию владельца»! отказ ¡ОРв^бНШШДОМпу своей д ы такие

системы являются сложными

iecK

1ТЕКА

ОЭ 1907 акт

KA J

jbmh. Цлубокий

анализ и моде-

лирование поведения Grid-систем позволяют прогнозировать их работу и организовывать управление, близкое к оптимальному.

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

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

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

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

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

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

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

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

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

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

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

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

- анализ архитектурных особенностей семейства вычислительных систем

МИКРОС и кластерных ВС;

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

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

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

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

задач.

Методы исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 45. Internationales Wissenschafliches Kolloquium, Germany, Ilraenau, 04.06.10.2000.

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

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

Публикации.

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

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

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

Основные положения, выносимые на защиту:

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

5=<С',С,/1(Л(0))>,

где С = {с(}- множество в ы чтедей щ, и=Ф,^д1;е <й - структура сети межмашинных связей (граф, вершинам которого сопоставлены вычислители , а ребрам линии связи между ними); А -алгоритм работы множества С вычислителей, взаимосвязанных через G, при реализации параллельной программы Р обработки данных D.

Конструкция коллектива вычислителей есть отражение сле-

дующих основополагающих архитектурных принципов:

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

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

3) однородности конструкции // (однородности вычислителей с, еС и макроструктуры в).

Итак, вычислительная система это средство обработки информации, основанные на модели коллектива вычислителей. Архитектурные возможности ВС определяются степенью воплощения принципов рассмотренной модели. Наиболее общим и архитектурно совершенным классом вычислительных систем являются распределенные ВС с программируемой структурой. В первой главе описываются ВС семейства МИКРОС и распределенная мультипроцессорная кластерная система, созданные под руководством В.Г. Хорошевского.

Семейство вычислительных систем МИКРОС

Работы по научно-исследовательскому проекту МИКРОС инициированы в начале 80-х годов 20 столетия. Целью этих работ было создание

Микропроцессорных Систем с программируемой структурой (МИКРОС). Созданы следующие модели семейства МИКРОС: МИКРОС-1 (1986г.), МИКРОС-2 (1992г.), МИКРОС-Т (1997г.). Разработка моделей семейства МИКРОС осуществлялась Отделом вычислительных систем СО АН СССР (СО РАН) в содружестве, в частности, с подразделениями Научно-производственного объединения «Алмаз» и Научно-исследовательского института «Квант» Министерства радиопромышленности СССР (г. Москва).

Архитектура семейства систем МИКРОС:

- MIMD-архитектура;

- распределешюсть средств управления, обработки и памяти;

- массовый параллелизм (при обработке данных и управления процессами);

- возможность программной трансформации архитектуры-MIMD в SIMD и MISD;

- приемлемость структур в виде произвольных графов;

- программируемость структуры сети межмашинных связей;

- децентрализация ресурсов;

- асинхронность и близкодействие;

- масштабируемость, модульность и однородность.

Конфигурация элементарной машины (ЭМ) любой модели МИКРОС допускает варьирование в широких пределах. В моделях МИКРОС-1 и МИКРОС-2 минимальная конфигурация ЭМ представляется композицией из центрального процессора и памяти семейства микроЭВМ «Электроника 60» и локального коммутатора для организации межмашинных связей.

В модели МИКРОС-Т простейшая конфигурация ЭМ представляется транспьютером Inmos T805 с памятью, а в развитой конфигурации элементарная машина может включать в себя высокопроизводительные микропроцессоры или Intel 860, или PowerPC, или Alpha, а также дополнительную память. Производительность такой ЭМ оценивается величиной в пределах: 102 MFLOPS - 10 GFLOPS, а емкость памяти 108-10'° байт.

В основу операционной системы МИКРОС положены принципы:

- независимость от структуры ВС и числа машин в ней;

- модульность построения;

- децептрализованность (распределенность модулей по машинам ВС);

- локальность связей между модулями;

- асинхронность взаимодействия модулей;

- развиваемость (изменяемость и пополняемость состава модулей);

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

- преемственность с операционными системами базовых микропроцессорных средств (либо микроЭВМ «Электроника" либо транспьютеров, в зависимости от моделей семейства ВС МИКРОС).

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

Число элементарных машин в моделях МИКРОС не фиксировано, что обеспечивает принципиально неограниченное наращивание производительности ВС.

Живучая кластерная Grid-система

Работы по созданию живучих распределенных масштабируемых кластерных ВС начаты в 2000 году и выполняются на Кафедре вычислительных систем СибГУ-ТИ и в Лаборатории вычислительных систем ИФП СО РАН.

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

На практике получило широкое распространение конфигурирование кластеров из аппаратурно-программных средств IBM PC; главный принцип такого конфигурирования - максимальное использование массовопроизводимых компонентов. Говоря иначе, современный кластер это, как правило, компьютерная сеть, дополненная аппаратурно-программными средствами для параллельных вычислительных технологий.

Grid-система представляет собой некий 'виртуальный суперкомпьютер', в котором удаленные вычислительные устройства совместно образуют мощную обрабатывающую среду. В основе Grid-системы лежат программные технологии, использующие новые стандарты и протоколы совместно с известными сетевыми и Internet-протоколами

Рассматриваемая кластерная вычислительная система является объединением * вычислительных машин, расположенных в ЦПВТ СибГУТИ и ИФП СО РАН. Таким образом, построенная географически распределенная кластерная ВС является Grid-системой.

Отметим архитектурные особенности созданной кластерной Grid-системы. Число элементарных машин не фиксировано ( в реализации оно равно 64). В конфигурацию ЭМ включается процессор Intel Celeron 667, память DIMM SDRAM 128 Mb, жесткий диск Segate 10.2 Go/Quantum 30Gb, сетевая карта 3 Com 905C-TXM. Для связи машин используется коммутатор Switch 3 Com 16735B lOOMbps, модемное устройство и сеть INTERNET.

Программное обеспечение кластера включает:

- операционную систему ASPLinux v.7.3 (ядро 2.4.18);

- языки программирования: FORTRAN;

- библиотеку передачи сообщений - MPI (Message Passing Interface);

- протокол обмена сообщениями - TCP/IP;

- специальные компоненты (для поддержки живучести, самодиагностики, мультипрограммных режимов, формирования виртуальных структур).

Режимы функционирования моделей МИКРОС и кластерной Grid-системы:

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

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

- Способы обработки данных в ВС:

- распределенный, когда однородно расчлененные данные и ветви параллельной программы их обработки рассредоточиваются по ЭМ;

- матричный, при котором программа вычислений размещается в одной или нескольких ЭМ, а данные (однородно) распределяются по всем машинам;

- конвейерный, когда сегментированная программа размещается по машинам предварительно настроенного конвейера (или "кольца" или «линейки") и обеспечивается последовательное «пропускание" данных через все ЭМ конвейера.

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

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

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

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

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

где N - общее число ЭМ в ВС, X - интенсивность потока отказов в каждой ЭМ, т<Ы - число восстанавливающих устройств (ВУ), /1 - интенсивность восстановления отказавших ЭМ одним восстанавливающим устройством (ВУ).

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

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

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

Объектом исследования является распределенная ВС с программируемой структурой, состоящая из N неабсолютно надежных ЭМ. Пусть Х(/) - среднее

число исправных ЭМ в момент времени 1 при условии, что К(0) = /, /е {о,1,..,ЛТ} (см. (1)). Отказ или восстановление ЭМ инициируют выполнение процедуры реконфигурации ВС. Под реконфигурацией ВС понимается программирование виртуальной (под)системы с учетом отказавших ресурсов; - среднее время реконфигурации ВС. Допустимо построение распределенных и децентрализованных средств реконфигурации ВС, использование оптимальных структур (например, Бп или Ьп графов): следовательно, для простоты считаем, что время реконфигурации не зависит от количества ЭМ. В связи с тем, что время реконфигурации ВС не является величиной бесконечно малой, то естественно считать, что отказы и (или) восстановления ЭМ могут иметь место и во время программирования виртуальной системы. Описанный процесс назовем сложной реконфигурацией ВС.

Введем функцию

1, есливсистемепроизошелотказзавремя А/, О, иначе',

Ы), есливсистемепроизошелi-ыйотказзавремя&, Iе{2,3,4...}, О, иначе.

тогда - суммарное число отказов, произошедших в системе в

промежутке времени то имеет место сложная реконфи-

гурация ВС.

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

ем:

<5 (/,Д/)> =

(2)

а{8 С,Л')) =-

(3)

где <5(/,Д/)> - математическое ожидание ¿(/,Д/); д-(у^)-вероятность отказа или восстановления одной ЭМ за время Тып > а - вероятность отказа или вос-

становления за время Д/ одной ЭМ системы с программируемой структурой (в момент времени имеется К(/) исправных машин)

Формулы (2), (3) позволяют оценить среднюю «длину» сложной реконфигурации {<5Д/) >) и могут быть использованы при моделировании и анализе распределенных ВС.

Через Т определим время решения задачи на одной абсолютно надежной ЭМ. Сопоставим начало решения задачи времени 1 = 0, тогда время / е (ОХ] будет указывать на этап, в котором находится ЭМ при решении задачи. Часть задачи, решенная за время í+Aí, складывается из частей решенных в промежутках (0,1] и (//+Д/]. Через 0((>,+Л/] обозначим часть задачи, находящуюся в решении на одной ЭМ в промежутке времени. (г/+Д/]. Тогда время решения части С1(0,] задачи на ВС будем рассматривать, как функцию от времени решения на одной ЭМ:

Пусть А(1) - время решения на ВС части П(0 (} задачи при условии, что в

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

Если допустить, что за время Д/ не происходит отказов или восстановлений и часть о^д,] задачи решается н равных ЭМ за время • , то диффе-

ренциальный коэффициент ускорения решения задачи на. ВС будет равен = Д*/г . Если функция К(1) в точке t не имеет разрыва, то исходя из определения имеем

*(0=1//'(0-

В случае отказа или восстановления

/'(0 = г'/(1+Щ/)), /(0) = 0, К(0) = /, (4)

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

т < ЛГ-К(/(0), -К(/(0))А тЖ-^Ш

С учетом оценки сложной геконсЬигуоапии (2) получаем, что

£/(0 = (ДК(/(0)+а)^, где А =

сложной пеконсЬигтоапии (2) получаем.1

Решение уравнения (4) производится численными методами. Для расчета f(t) предлагается рекуррентная формула:

А. = fj+ kn,W + UС/АЛ /о = °>ио = ,> 0<У<Л/. (5)

где fj = f(jh), kn=k(jh), Mh = T, itj=N(fj). Значения п, моделируются по

функциям распределения времени отказов и восстановлений ЭМ.

Пример. Используем формулу (5) для оценки времени решения задачи на ВС. Положим Г-1000ч., Ж=30ЭМ, i = 29ЭМ, Л = 0.0011/ч., // = 0.9 1/ч., от = 1. Графическое отображение функций fit) представлено на рис.1. Значения функции /1(t) соответствует Т0 = 0.2 ч., а для/2(t) ТШп = 0 ч.

т. «

О 300 600 900 4

Рис. 1. Время решения задачи на ВС

Исследования показали, что малое Ттп и небольшое число отказов и восстановлений I (/Геи «У) за время Тзаметно не влияют на ДТ).

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

Континуальный подход. Пусть известно - число работоспособных ма-

шин в системе в момент времени / при условии, что в начальный момент времени исправно /6 (0,1,..., ЭМ. Считаем, что N>10, N>К(/)^Мтм . где -нижняя граница. Тогда осуществимость параллельного решения сложной задачи оценивается при помощи функции:

ФО,/) = 1-ехр[-у0}к(г)/г], (6)

где УР - среднее время решения задачи на одной ЭМ.

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

ф(0 = 1 - ехр(-/? К/), К = lim КО).

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

Используя результаты В. Г. Хорошевского для K(/,i) , получаем:

Дискретный подход. Требуется рассчитать вероятность решения задачи Р(Ю)М) на ВС с программируемой структурой за время f(T) при числе отказов и восстановлений, не превышающим 1.

Пусть P„(f{t),l,i)-вероятность того, что к моменту времени f(t) на ВС будет решена п{0,«) часть задачи при появлении 1 отказов и восстановлений ЭМ и наличии п исправных ЭМ в момент времени f(t) (при условии, что в начальный момент времени было i рабочих ЭМ);

- вероятность восстановления одной неисправной ЭМ за время f(t) при отказе (N-n) ЭМ и наличии т <N восстанавливающих устройств; Pji,(n,f(t))- вероятность отказа любой ЭМ из п исправных ЭМ за время f(t);

-вероятность безотказной работы ВС из п исправных ЭМ за вреМЯ f(ty,

- вероятность невосстановления любой неисправной ЭМ за время f(t) при отказе (N - п) -ой ЭМ и наличии т N- восстанавливающих устройств;

- вероятность того, что в течение интервала времени t не произойдут отказы или восстановления в системе из п ЭМ.

Для вероятностей P„(f(t),l,i) получена система интегральных уравнений:

ЛСЛ'М 0=/Л(/(г),/-1,<)»'1(»-Г)С/(/'А(2,/(Г))К»(2,ЛО)),

о о о

/>, (Л0,Л»)=//\-.(Л»-),'-О)»\ ф-г)к-Мрг.ЛХ-\,Дт))у^-\№)\

о

Р.(Лг)Д>)=

.о, (г*;'>Лг)М«#о

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

(8)

Р(ЯШ,0 = 11/>„(ДШ>').

Автором найдено решение системы уравнений численными методами.

Параллельный алгоритм. Вычисление каждого из интегралов для Р„(/(0,1,0 системы уравнений (7) разбиваем на X частей (например, по числу ЭМ в системе), Далее, каждая часть обрабатывается на соответствующей ей ЭМ.

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

Параллельный алгоритм был реализован на транспьютерной вычислительной системе с программируемой структурой МИКРОС-Т и кластерной ВС. Эффективность исполнения параллельного алгоритма на кластерной ВС отражена рис.2 , где = ^ - время решения задачи (8) на ] машинах ВС.

Осуществимости решения задач потока. Пусть имеем систему, состоящую из п ЭМ, на которую поступает интенсивный поток требований на обслуживание (например, для обработки и построения изображений). Каждая ЭМ в любой момент времени обслуживает не более одного требования с интенсивностью Р . Если тре-

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

Обозначим через а - интенсивность движения очереди (для абсолютно надежных систем можно считать а = пр). Требуется вычислить Рк(Т)- вероятность того, что за время /<Г0 , требование, стоящее в очереди под номером к, будет обслужено. Пусть /?(<)- функция распределения времени обслуживания требования одной ЭМ, а ЩО - функция распределения продвижения очереди на одно требование. Тогда вероятность того, что требование, стоящее в очереди под номером к, за время / будет первым на обслуживании:

Искомая вероятность:

РЛО=Ж(/-г)<ОД.

В частном слу. у

а~р ма~р а-р у-ю 1»о у! а-р

Когда а — Р , получаем:

1=0

Если на системе очередь движе,г',гт ^ ятность для (г-\)п<к<грк(()х =

Р'

возможно оценить веро-

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

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

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

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

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

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

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

Изображения поступают с фотоприемной матрицы на транспьютерный модуль ГГО^4 для последующей рассылки по всем ЭМ (рис. 3). Предварительная обработка последовательности изображений состоит из следующих этапов: сглаживание, оконтуривание и контрастирование. Целью сглаживания на предварительном этапе является удаление шума с сохранением перепадов яркости на границах областей. Использованы методы: локальное усреднение в окрестности точки окна 3x3, медианная фильтрация в окне 3x3. Целью оконтуривания является выделение граничных точек. Использовались градиентные методы, в основе которых лежит анализ скорости изменения функции яркости. Перепады яркости вычислялись через 3x3 операторы Превитта и Собеля. Для контрастирования использовались однопо-роговая и двухпороговая фильтрации. Фильтрация позволяла нормировать значения точек изображения до 0 и 1 или 0, 1 и 2, путем сравнивая значений яркости точек с заданным порогом.

Хостаомпыокр

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

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

Таблица 1

/ (ЭМ) 1 2 3 4 5 6 7 8

Т„ [сек] 11,50 5,84 3,86 2,95 2,31 1,94 1,67 1,49

к„ = т{/т„ 1 1,97 2,98 3,9 4,99 5,92 6,87 7,71

Е„ = К,/п 1 0,99 0,99 0,98 0,99 0,99 0,98 0,96

Проведенные моделирование и анализ осуществимости решения параллельной предварительной обработки изображений на ВС МИКРОС-Т показали высокую живучесть и эффективность системы. На рис 4. для представлен расчет осуществимости решения сложной задачи со следующими параметрами (см. (4), (5), (7) и (8) ): Ки=Т/п, Т = 310 ч., ЛГ = 32ЭМ, /=32ЭМ, // = 0. Расчет функции /] проведен для ВС, в которой интенсивность отказов каждой ЭМ Л = 0.00001 ; для /2 Л = 0.00005 ; для /j Л = 0.0001.

Р{ 0

0997 0992 0997 0,982 0977 0972 0967

97 97« 9 06 9,94 №02 10.1 Ц1в '

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

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

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

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

2) возможностью имитировать изображения и их последовательности на конечной области определения;

3) высокой эффективностью использования ресурсов параллельных ВС.

Ввиду того, что каждый отсчет кадра X* (к- кадр из последовательности; х* - яркость точки кадра Хк с координатами i и j) формируется независимо

.m » 'А и /г к 1«-« ЭР* ттг ■vrvr •vrv ITS

j¿

- л!

И У —

Ьг*

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

Межкадровые смещения изображений возникают из-за меняющегося от кадра к кадру взаимного пространственного положения сюжета и приемника, например, в результате движения фотоприемной камеры относительно объекта. Требуется оценить вектор параметров смещений между двумя изображениями Под а можно понимать сдвиги по вертикали и горизонтали, а также поворот изображения Хк относительно . Для решения этой задачи применяется псевдоградиентный алгоритм:

ат = + (9)

где Ат~ гт~Ит - предсказанное местоположение кадра Z со значениями 2тУ-> /(гт> а т-0 - функция прогноза; - убывающие коэффициенты.

Распараллеливание алгоритма осуществляется путем независимого выбора, случайных точек (пикселей) в каждой ЭМ системы и вычислении значения /(.гпчССт-д в этих точках. Полученные и значений /(г»»««,-!) усредняются, после

чего применяется (9) с усредненным градиентом. Сходимость а я ат ускоряется за счет распараллеливания и усреднения по последовательности нескольких точек (пар, троек и т.д.).

1 2 3 4 $

Рис. 5 Эффективность исполнения параллельного ускоренного псевдоградиентного алгоритма оценивания сдвигов и поворотов на последовательности кадров для ТВС

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

Экспериментально показано, что, имея всего одну ЭМ, за счет усреднения можно ускорить выполнение алгоритма. В случае усреднения по двум-трем точкам время выполнения алгоритма сокращается в 2-6 раз.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Панский К. 13. Моделирование осуществимости решения задач на распределенных ВС // Материалы локладоп региональном научной конференции студентов, аспирантов и молодых ученых "Паука, чехника, инновации", Новосибирск, 5-8 декабря, 2002г., С. 17-19. .

2. Хорошевский В.Г., Павский К.11. и др. Живучая кластерная вычислительная система // Материалы Межрегиональною семинара но распределенным кластерным вычислениям, Красноярск, 4-6 декабря, 2001, С. 109-113.

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

4. Pavsky K.V. Analysis of the time of Solution of parallel problems on programmable structure Computer systems // Optoelectronics, instrumentation and data processing, 2000, №2, pp. 54-62.

5. Павскии К.13. Анализ реконфигурации на распределенных вычислительных системах // Материалы Международной научно-технической конференции "Информационные системы и технологии", Новосибирск, 11Г1У, 2000, т. 3, С. 468-470.

6. Павскии К.В. Оценка времени решения параллельных задач на распределенных вычислительных системах // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2000, С. 113.

7. Pavsky K.V. Realizability of parallel solving complex problems on distributed computer systems // In Proceedings "45. Internationales Wissenschaftlich.es Kolloquium", Technische Universitaet Ilmenau, 2000, pp. 823-828.

8. Павскии К.В. Осуществимость параллельного решения задачи и потока задач па распределенных вычислительных системах.// Искусственный интеллект, ДонД!Ш1 «Наука i оевгга», 2001, №3, С. 251-259.

9. Павскии К.В. Осуществимость параллельного решения задачи и потока задач па распределенных вычислительных системах //1езисы докладов Международной конференции "Интеллектуальные и многопроцессорные системы", 1-6 октября, 2001, пос. Дивноморское, С. 120*123.

10. Павскии П.А., Павскии К.В. Опенка показателей осуществимости в условиях реального времени // 1руды 5-го международного семинара "Распределенная обработка информации", Новосибирск, СО рАн, 1995, С. 212-213.

11. Хорошевский В.Г., Павскии К.В., Павскии В.А. Расчет функции осуществимости решения параллельных задач на распределенных вычислительных системах //1руды Шестого международного семинара "Распределённая обработка информации", Новосибирск, СО РАН, 1998, С. 218-222.

12. Павскии К.В. Осуществимость реализации параллельных алгорпгмоп обработки изображений // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 26-27 апреля, 2001, Новосибирск, С. 84-85.

13. ПавскиИ К.В. Реализация параллельного алгоритма оценивания сдвигов и поворотов изображений на транспьютерной системе // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 1995, т. I., С. 122-123.

14. Тарков М.С., Павский К.В. Исследование эффективности вычислительной системы МИКРОС-2 и транспьютерной системы при выполнении параллельного умножения матриц // Тезисы докладов Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 1994, С. 39.

ПАВСКИЙ Кирилл Валерьевич

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

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

Подписано в печать " 12 " января 2004 г.

Формат бумаги 62x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 1,3, заказ № 13, тираж - 150 экз., ГОУ ВПО «СибГУТИ». 630102, г. Новосибирск, ул. Кирова, 86.

ВВЕДЕНИЕ

ГЛАВА 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

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