Содержание к диссертации
Введение
ГЛАВА 1. Архитектура распределенных вычислительных систем и сетей 12
1.1. Концептуальные основы построения болынемасштабных вычислительных систем (модель коллектива вычислителей) 12
1.1.1. Модель вычислителя 12
1.1.2. Модель коллектива вычислителей 13
1.1.3. Принципы построения вычислительных систем 13
1.1.4. Алгоритм функционирования вычислительной системы 15
1.1.5. Модель вычислительной системы 17
1.1.6. Принципы технической реализации модели коллектива вычислителей 17
1.1.7. Архитектурные свойства вычислительных систем 20
1.2. Структура сетей передачи информации 26
1.2.1. Требования, предъявляемые к структурам 26
1.2.2. Структурные характеристики 27
1.2.3. Оптимальные структуры 29
1.3. Семейство живучих распределенных вычислительных систем с программируемой структурой МИКРОС 33
1.3.1. Вычислительная система МИКРОС, МИКРОС-2, МИКРОС-Т 35
1.3.2. Функциональная структура ВС МИКРОС 36
1.3.3. Программное обеспечение МИКРОС 39
1.3.4. Архитектурные свойства систем семейства МИКРОС 43
1.4. Система обработки изображений 47
1.5. Кластерные вычислительные системы 48
1.5.1. Принципы построения кластерных вычислительных систем 48
1.5.2. Кластерная Grid-система 50
1.6. Выводы 53
ГЛАВА 2. Надежность и живучесть распределенных вычислительных систем 54
2.1. Надежность ЭВМ 54
2.1.1. Основные понятия надежности ЭВМ 54
2.1.2. Вероятность безотказной работы ЭВМ 56
2.1.3. Вероятность восстановления ЭВМ 59
2.2. Надежность ВС с программируемой структурой 60
2.2.1. Вычислительные системы со структурной избыточностью 60
2.2.2. Показатели надежности вычислительных систем 62
2.2.3. Расчет показателей надежности для переходного режима функционирования вычислительных систем 66
2.2.4. Расчёт показателей надёжности для стационарного режима работы вычислительных систем 68
2.2.5. Выводы 70
2.3. Живучесть вычислительных систем 70
2.3.1. Живучие вычислительные системы 70
2.3.2. Показатели потенциальной живучести вычислительных систем 72
2.3.3. О методике расчёта показателей живучести вычислительных систем 76
2.3.4. Расчёт функции потенциальной живучести вычислительных систем 79
2.3.5. Выводы 83
ГЛАВА 3. Осуществимость решения задач на распределенных вычислительных системах 84
3.1. Континуальный подход к анализу осуществимости решения задач 85
3.2. Дискретный подход к анализу осуществимости решения задач 87
3.2.1. Дифференциальный коэффициент ускорения решения параллельных задач на ВС 87
3.2.2. Сложная реконфигурация ВС 88
3.2.3. Оценка времени решения параллельных задач на распределенных ВС...90
3.2.4. Расчет функции осуществимости параллельного решения задач на В С... 93
3.2.5. Дискретный анализ осуществимости решения задач 94
3.3. Анализ осуществимости решения задач потока на ВС 96
3.3.1. Функция осуществимости решения последовательных задач потока 96
3.3.2. Функция осуществимости решения параллельных задач потока 98
3.4. Выводы 99
ГЛАВА 4. Отказоустойчивые параллельные вычисления 101
4.1. Показатели эффективности параллельных алгоритмов 101
4.2. Алгоритмы предварительной обработки изображений 103
4.2.1. Алгоритмы сглаживания и удаления помех изображения 103
4.2.2. Алгоритмы оконтуривания и контрастирования изображений 105
4.2.3. Параллельные алгоритмы предварительной обработки изображений... 108
4.2.4. Алгоритм вложения графа текущей конфигурации ВС в граф полной конфигурации 109
4.2.5. Численный анализ осуществимости реализации параллельных алгоритмов обработки изображений 111
4.3. Алгоритмы имитации изображений на основе волновой модели 112
4.3.1. Волновая модель 113
4.3.2. Параллельный алгоритм имитации изображений на основе волновой модели 117
4.4. Алгоритмы оценивания сдвигов и поворотов изображений на последовательности кадров 119
4.4.1. Модель межкадровых смещений 120
4.4.2. Псевдоградиентный алгоритм оценки сдвигов и поворотов 122
4.4.3. Параллельный алгоритм оценивания сдвигов и поворотов изображений на последовательности кадров 123
4.4.4. Параллельная реализация ускоренного псевдоградиентного алгоритма оценки сдвигов и поворотов изображений на последовательности кадров 123
4.4.5. Ускоренный последовательный псевдоградиентный алгоритм оценки сдвигов и поворотов изображений на последовательности кадров 126
4.5. Выводы 127
Заключение 128
Список литературы 130
- Принципы технической реализации модели коллектива вычислителей
- Вероятность безотказной работы ЭВМ
- Континуальный подход к анализу осуществимости решения задач
- Алгоритмы оконтуривания и контрастирования изображений
Введение к работе
Характерной особенностью современной индустрии информатики является создание распределенных вычислительных систем (ВС) высокой производительности (109 - 1015 опер./с, GigaFLOPS - PetaFLOPS). Архитектура распределенных ВС представляется в виде композиции множества элементарных машин или процессоров, соединенных телекоммуникационной системой. В таких системах все основные ресурсы (не только арифметико-логические устройства, но и память и средства управления) являются и логически и технически распределенными. Число элементарных машин (ЭМ) в распределенных ВС допускает варьирование и заключено в пределах от 10 до 106 [117]; например, это число в системе IBM Blue Gene может достигать 1 000 000. Именно поэтому подобные ВС относят к масштабируемым и большемас-штабным.
Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М. Глушков, В.В. Губарев, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, М.А. Карцев, Л.Н. Королев, Н.А. Кузнецов, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, В.К. Попков, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, A.M. Федотов, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н.Яненко и другие [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]:
решение одной сложной задачи,
обработка набора задач,
обслуживание потока задач.
7 Предлагаемые в этой работе подходы развивают методы теории осуществимости решения задач: позволяют провести анализ осуществимости параллельного решения задач на распределенных ВС в основных режимах их функционирования.
Цель и задачи работы
Целью диссертационной работы является разработка методов и алгоритмов анализа осуществимости параллельного решения задач на распределенных вычислительных системах и сетях.
В соответствии с поставленной целью определены следующие задачи исследования:
анализ архитектурных особенностей семейства вычислительных систем МИК-РОС и кластерных ВС;
построение стохастических моделей анализа функционирования распределенных ВС;
расчет показателей осуществимости параллельного решения задач;
параллельное моделирование осуществимости решения задач;
разработка отказоустойчивых параллельных алгоритмов решения сложных задач.
Для решения задач, поставленных в диссертации, используются стохастические модели и методы анализа эффективности функционирования распределенных вычислительных систем, аппарат теории вероятностей, случайных процессов и массового обслуживания, математический анализ, средства вычислительной математики.
Научная новизна
Предложены и развиты дискретные и континуальные стохастические модели функционирования распределенных вычислительных систем, позволившие рассчитать показатели осуществимости параллельного решения задач. Проведенные теоретические исследования позволяют создать алгоритмический и программный инструментарий анализа осуществимости параллельного решения задач на распределенных ВС:
1. Выведены формулы для расчета среднего времени решения сложных задач на распределенных ВС.
Построена система интегральных уравнений для расчета вероятности осуществления параллельного решения задач на Grid системах.
Получены формулы для расчета показателей осуществимости решения задач потока на распределенных ВС (Grid системах).
Сформулирована модель сложной реконфигурации ВС и произведен ее анализ.
Разработаны параллельные алгоритмы для расчета показателей осуществимости решения задач на распределенных ВС.
Предложены отказоустойчивые параллельные алгоритмы предварительной обработки изображений и ускоренный алгоритм оценивания сдвигов и поворотов на последовательности кадров изображения.
Проведены вычислительные эксперименты и осуществлено параллельное моделирование разработанных методов и алгоритмов на системах семейства МИКРОС и кластерной Grid-системе.
Практическая ценность
Параллельные алгоритмы для расчета вероятности решения задач на ВС характеризуются высокой эффективностью (ускорением, близким к линейному).
Полученные формулы для функции осуществимости решения параллельных задач потока позволяют оценить полезную нагрузку на ресурсы Grid-системы.
Оценки сложной реконфигурации ВС позволяют повысить точность расчета вероятности осуществления параллельного решения задач.
Пакет параллельных алгоритмов и программ предварительной обработки изображений обладает отказоустойчивостью (способностью адаптации под исправные ресурсы).
Разработанный ускоренный алгоритм сдвигов и поворотов на последовательности кадров изображения дает 2-6 кратное увеличение в скорости сходимости по сравнению с простым алгоритмом.
Средства визуализации структуры системы МИКРОС-Т основаны на рекурсивном алгоритме наложения графа текущей структуры ВС на исходную.
Созданные средства являются простыми и эффективными инструментами для анализа осуществимости параллельного решения задач на распределенных ВС (Grid-системах) и позволяют эффективно использовать их ресурсы.
Реализация работы
Результаты работы доведены до параллельных программ анализа осуществимости параллельного решения задач и отказоустойчивых алгоритмов и программ обработки изображений на распределенных ВС. Они были использованы при создании аппаратурно-программных средств семейства распределенных систем МИКРОС, а также при разработке кластерной Grid-системы.
Диссертант принимал непосредственное участие в работах, выполняемых по Федеральной целевой научно-технической программе «Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения" (приоритетное направление «Информационные технологии и электроника", подпрограммы «Перспективные информационные технологии" и «Информатизация России"). Кроме того, соискатель был одним из основных исполнителей проектов Российского фонда фундаментальных исследований: № 97-01-00883, № 97-01-05011, № 99-07-90206, № 99-01-05018, № 99-07-90438, № 00-01-00126, №02-01-06518, №02-07-90379, №02-07-90380.
Результаты исследований внедрены в Научно-учебном центре параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ).
Апробация работы
Основные положения диссертационной работы докладывались и обсуждались на:
Международных научно-технических конференциях "Информатика и проблемы телекоммуникаций", Новосибирск, 1994, 1995, 2001;
Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2000;
Пятом и Шестом международных семинарах «Распределенная обработка информации», Новосибирск, 10-12 октября 1995 г., 23-25 июня, 1998;
Международной научно-технической конференции «Информационные системы и технологии», Новосибирск, 8-11 ноября, 2000;
45. Internationales Wissenschafliches Kolloquium, Germany, Ilmenau, 04-06.10.2000.
- Международной конференции "Интеллектуальные и многопроцессорные сис
темы", 1-6 октября 2001 г., пос. Дивноморское Геленджикского района;
І - Региональная научная конференция студентов, аспирантов и молодых ученых
"Наука, техника, инновации", 5-8 декабря, 2002 г., Новосибирск.
Публикации
Содержание диссертации отражено в 14 печатных работах и 8 научных отчетах.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав и заключения. Содержит 161
Ф страница с приложением, 9 таблиц и 24 рисунка. Список литературы содержит 140
наименований.
Основные положения, выносимые на защиту:
стохастические модели функционирования распределенных вычислительных систем, методы и алгоритмы анализа осуществимости параллельного решения задач;
отказоустойчивые параллельные алгоритмы решения сложных задач, параллельное моделирование обработки изображений;
- программные средства анализа осуществимости параллельного решения задач,
* обработки изображений и поддержки отказоустойчивости и реконфигурируемости
вычислительных систем МИКРОС и кластерной Grid-системы.
Содержание работы
В первой главе изложены концептуальные основы построения распределённых вычислительных систем (в частности, ВС семейства МИКРОС, кластерных ВС, Grid-систем).
Во второй главе даны основы теории надежности и живучести ВС. Рассмотре
ны вычислительные системы со структурной избыточностью, являющиеся обобщени-
^ ем систем с резервом.
Рассмотрены показатели надёжности для переходного и стационарного режимов работы ВС, описаны методы их расчёта. Описаны живучие вычислительные системы как обобщение модели ВС со структурной избыточностью.
Рассмотрены показатели качества функционирования живучих ВС в переходном и стационарном режимах, описаны методы их расчёта.
В третьей главе рассмотрены показатели осуществимости решения задач на распределённых вычислительных системах. Описан континуальный подход к расчету функции осуществимости решения задач на распределенных ВС. Построена модель для анализа времени решения сложных задач на распределенных ВС. Предложена математическая модель анализа осуществимости решения за'дач потока.
В четвертой главе описаны алгоритмы предварительной обработки изображений и предложена их параллельная реализация на ВС МИКРОС-Т.
Описаны волновая модель и модель оценивания сдвигов и поворотов изображений на последовательности кадров. Предложен ускоренный алгоритм оценивания сдвигов и поворотов изображений на последовательности кадров.
В заключении приведены основные результаты диссертационной работы.
В приложении представлены фрагменты исходных программ и результаты эффективности исполнения параллельных программ предварительной обработки изображений на ВС МИКРОС-Т.
Принципы технической реализации модели коллектива вычислителей
Каноническое описание модели коллектива вычислителей (1.8), основополагающие принципы ее конструкции, а также состояние микроэлектроники и уровень развития (параллельной) вычислительной математики определяют принципы техни 18 ческой реализации модели или принципы построения вычислительных систем (ВС). Выделим "модульность" и "близкодействие" как главные принципы технической реализации модели коллектива вычислителей [33, 66, 117, 119].
Модульность - принцип, предопределяющий формирование вычислительной системы из унифицированных элементов (называемых модулями), которые функционально и конструктивно закончены, имеют средства сопряжения с другими элементами и разнообразие которых составляет полный набор. Функциональные и конструктивные возможности модулей, разнообразие их типов определяются исходя из требований, предъявляемых к ВС, и, безусловно, из возможностей микроэлектронной базы [34, 59].
Каждый модуль должен иметь средства автономного управления, располагать арифметико-логическим устройством и памятью и содержать локальный коммутатор - схему для связи с другими модулями. Модульность вычислительной системы обеспечивает: 1) возможность использования любого модуля заданного типа для выполнения любого соответствующего ему задания пользователя; 2) простоту замены одного модуля на другой однотипный; 3) масштабируемость, т.е. возможность увеличения или уменьшения количества модулей без коренной реконфигурации связей между остальными модулями; 4) открытость системы для модернизации, исключающую ее моральное старение. Следует заметить, что принцип модульности распространим и на средства программного обеспечения ВС. Близкодействие - принцип построения ВС, обусловливающий такую организацию информационных взаимодействий между модулями-вычислителями, при которой каждый из них может непосредственно (без "посредников") обмениваться информацией с весьма ограниченной частью модулей-вычислителей. Следовательно, структура ВС позволяет осуществлять информационные взаимодействия между удаленными вершинами-вычислителями лишь с помощью промежуточных вершин-вычислителей, передающих информацию от "точки к точке" (pointo-point). Удаленными считаются все те вершины в структуре ВС, расстояние между которыми более 1 (число ребер между которыми более 1). Вычислительные системы, основанные на принципах модульности и близко-действия, удовлетворяют также требованиям асинхронности, децентрализованности и распределенности [88, 91, 117, 119].
Асинхронность функционирования ВС обеспечивается, если порядок срабатывания ее модулей определяется не с помощью вырабатываемых тем или иным образом отметок времени, а достижением заданных значений определенных (как правило, логических) функций. Использование асинхронных схем позволяет достичь в системе алгоритмически предельного быстродействия: модули ВС срабатывают немедленно после достижения соответствующего условия. На уровне взаимодействий между вычислителями, применение асинхронных схем обмена исключает необходимость учитывать разброс частот работы взаимодействующих вычислителей и колебания времени задержки сигналов в линиях связи [30].
Децентрализованность управления ВС достигается, если в системе нет выделенного модуля, который функционирует как единый для всей системы центр управления. Децентрализованное управление системой основано на совместной работе всех исправных модулей системы, направленной на принятие решений, доставляющих оптимум выбранной целевой функции. Выполняя свою часть работы по выработке согласованного решения об управлении системой, каждый модуль пользуется только локальной информацией о системе. Децентрализованное управление системой (в отличие от централизованного) позволяет: 1) достичь живучести ВС, т.е способности ВС продолжать работу при отказах модулей в том числе и тех, которые предназначены для принятия решений; 2) избежать очередей при обслуживании "заявок" на управление. Распределенность ресурсов ВС. Под ресурсами ВС понимаются все объекты, которые запрашиваются, используются и освобождаются в ходе выполнения вычислений. В качестве ресурсов ВС выступают такие многократно используемые объекты как шины, модули оперативной памяти, внешние устройства, линии межмодульных связей, процессоры или даже модули, составляющие отдельные вычислители, файлы данных, компоненты программного обеспечения. Принято называть распределенной ВС, такую систему, в которой нет единого ресурса, используемого другими в режиме разделения времени. Вместе с этим каждый ресурс распределённой ВС рассматривается как общий, доступный любому потребителю [44, 91].
Вероятность безотказной работы ЭВМ
Современная ЭВМ - достаточно сложный объект с позиции теории надежности. ЭВМ - это ансамбль, включающий технические (Hardware) и программные средства (Software). Даже техническая часть ЭВМ далеко не проста при изучении ее надежности в зависимости от надежности входящих в нее устройств. Работа устройств и узлов в общем случае основывается на различных физических принципах. При изучении надежности ЭВМ как системы могут быть использованы известные методы теории массового обслуживания и теории надежности [37, 48, 49, 100, 117, 119]. Здесь мы отразим специфическую для ЭВМ сторону и будем рассматривать ЭВМ в целом, не вдаваясь в детальную ее структуру и архитектуру.
Важнейшими понятиями теории надежности ЭВМ являются отказ и восстановление [49, 59]. Отказом называется событие, при котором ЭВМ теряет способность выполнять заданные функции по переработке информации (включая функции по вводу и выводу информации, хранению и собственно преобразованию информации) [117]. Это событие может произойти вследствие выхода из установленных пределов (допусков) значений одного или нескольких физических параметров, нарушения контактов, возникновения электрических пробоев, порчи программного обеспечения и т.п.
Различают полный и частичный отказы ЭВМ. Полный отказ приводит к полному нарушению работоспособности ЭВМ, или, говоря иначе, к потере способности выполнять любые из заданных функций по переработке информации. (Это может произойти, например, вследствие аварийного отключения электропитания ЭВМ). Частичный отказ вызывает ухудшение качества функционирования или сокращение количества выполняемых функций ЭВМ. В данной работе полный и частичный отказы различать не будем. Отказы приводят к таким изменениям в функционировании ЭВМ, которые носят постоянный характер. Для подчеркивания этого постоянства часто вместо термина "отказ" используют термин "устойчивый отказ". Устойчивые отказы могут быть устранены только в результате восстановления машины. Наряду с отказами, как показывает опыт, в ЭВМ нередко происходят неожиданные изменения физических параметров, выходящие за допустимые пределы. Такие изменения носят временный характер, они самоустраняются и называются перемежающимися отказами. Ниже мы будем иметь дело, как правило, с устойчивыми отказами и для краткости использовать термин "отказ".
В случае, когда в машине произошел отказ и он не устранен, говорят, что ЭВМ находится в неработоспособном состоянии (в состоянии отказа) или ЭВМ отказавшая. При эволюционном развитии ЭВМ уменьшается вероятность состояния отказа, увеличивается период работоспособности ЭВМ. Так, в первом поколении ЭВМ работоспособность машины ограничивалась 10 мин, а в ЭВМ третьего поколения достигала тысячи и более часов, в машинах специального назначения - годы и десятки лет [117, 119].
Несмотря на достаточную редкость отказов современных ЭВМ, требуются средства для поддержания работоспособности машины, т.е. средства технического обслуживания, контроля, диагностики и устранения неисправностей (или самоконтроля, самодиагностики и самоустранения неисправностей). Среди этих средств имеются микропрограммные, аппаратурные, аппаратурно-программные и программные компоненты. Более того, в ЭВМ общего назначения контроль, диагностика и устранение неисправностей осуществляются с участием людей - бригад технического обслуживания.
Восстановлением называется событие, заключающееся в том, что отказавшая ЭВМ полностью приобретает способность выполнять заданные функции по обработке информации [49, 117, 119]. Восстановление отказавшей ЭВМ может быть осуществлено автоматически (в общем случае с помощью аппаратурно-программных средств) или полуавтоматически (с участием бригады технического обслуживания). Ниже мы не будем различать способ восстановления отказавшей машины, а будем считать, что оно производится средством, называемым восстанавливающим устройством (ВУ). Следовательно, переход отказавшей ЭВМ в работоспособное состояние может произойти лишь в результате работы ВУ или, говоря точнее, в результате ремонта машины восстанавливающим устройством.
Для характеристики качества работы ЭВМ используют систему показателей надежности, каждый из которых определяется через понятие отказа и (или) восстановления. Прежде чем дать определения показателей надежности ЭВМ, введем случайные функцию со(х) и величину [117, 119]. Пусть находится в неработоспособном состоянии; а(х) назовем производительностью ЭВМ в момент времени х 0. Пусть также является моментом, когда возникает первый отказ при работе ЭВМ в заданных условиях эксплуатации.
Континуальный подход к анализу осуществимости решения задач
Показатели потенциальной надёжности и живучести характеризуют качество функционирования вычислительных систем (ВС) вне связи с процессом поступления и решения задач [117, 119, 130]. Поэтому для оценки потенциальных возможностей ВС по достижению цели их функционирования (решения поступающих задач) используют показатели осуществимости решений задач. Эти показатели достаточно полно характеризуют качество функционирования систем с учётом их надёжности и параметров поступающих задач (в общем случае вероятностных). Говоря иначе, они характеризуют процесс решения задач на неабсолютно надёжных ВС.
При анализе осуществимости решения задач будем учитывать большемас-штабность и масштабируемость распределённых ВС.
Осуществимость решения задач на ВС изучается в моно- и мультипрограммных режимах. Монопрограммный режим функционирования ВС предопределяет использование всех исправных ресурсов - элементарных машин (ЭМ) для решения одной сложной задачи, представленной параллельной программой. Мультипрограммные режимы работы ВС предусматривают распределение всего множества (исправных) ЭМ между задачами (различной сложности, с различным числом параллельных ветвей в их программах). К последним режимам относятся обработка набора задач и обслуживание потока задач [88, 117, 119].
При организации функционирования ВС в случае набора задач учитывается не только количество задач, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени, решения и др. Алгоритмы организации функционирования ВС задают распределение задач по машинам и последовательность выполнения задач на каждой машине. В результате становится известным, в каком промежутке времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора. Этот режим, безусловно, является обобщением режима решения сложной задачи на ВС.
Вместе с тем с позиций теории осуществимости решения задач этот режим без нарушения общности сводится к первому. В самом деле, осуществимость решения любой задачи набора зависит от параметров заданной для неё подсистемы, а анализ эффективности работы последней ничем не отличается от анализа всей системы при решении одной сложной задачи. Поэтому в дальнейшем ограничимся рассмотрением только режима решения одной сложной задачи на ВС.
Третий режим - обслуживание потока задач на ВС - принципиально отличается от обработки задач набора: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключён [1, 48, 100].
Для режимов решения сложной задачи и обслуживания потока задач на ВС ниже будут введены показатели осуществимости решения задач и рассмотрены методы расчёта этих показателей.
Математическое ожидание Л/(/, /) числа работоспособных машин при условии, что в начальный момент времени было исправно /є EQ = {0,1,2,..., Щ ЭМ) достаточно точно говорит об уровне потенциальной производительности ВС в момент / 0. Это тем точнее, чем больше общее число N машин в системе; сделанное допущение оправданно на практике при JV 10. Далее, для сложных задач допустимо составление адаптирующихся параллельных программ, в которых нижняя граница п числа параллельных ветвей не превышает ожидаемого числа работоспособных машин в любой момент времени, т.е. в которых п Л/(/, /). Тогда осуществимость решения сложной задачи на живучей ВС целесообразно оценивать функцией
Из (3.1) видно, что функция Ф(/,/) является вероятностью того, что сложная задача, представленная адаптирующейся параллельной программой, будет решена за время / на ВС, начавшей функционировать в состоянии / є Е" и использующей для решения задачи все работоспособные ЭМ. Если же ВС функционирует достаточно долго (находится в стационарном режиме), то вероятность решения задачи может быть выражена просто [119]:
Функции (3.1) и (3.2) называются функциями осуществимости решения сложной задачи на живучей ВС или функциями потенциальной осуществимости. При этом Ф(/, /) и Ф(0 характеризуют осуществимость соответственно в переходном и стационарном режимах работы системы. Считают, что решение сложной задачи осуществимо на живучей ВС в промежутке времени [0,/), если выполняются неравенства для переходного режима и неравенства Ф(/) Ф\ t f для стационарного режима функционирования системы. Величины Ф" и ґ называются порогами потенциальной осуществимости решения сложной задачи на ВС.
Алгоритмы оконтуривания и контрастирования изображений
Показатели потенциальной надёжности и живучести характеризуют качество функционирования вычислительных систем (ВС) вне связи с процессом поступления и решения задач [117, 119, 130]. Поэтому для оценки потенциальных возможностей ВС по достижению цели их функционирования (решения поступающих задач) используют показатели осуществимости решений задач. Эти показатели достаточно полно характеризуют качество функционирования систем с учётом их надёжности и параметров поступающих задач (в общем случае вероятностных). Говоря иначе, они характеризуют процесс решения задач на неабсолютно надёжных ВС.
При анализе осуществимости решения задач будем учитывать большемас-штабность и масштабируемость распределённых ВС.
Осуществимость решения задач на ВС изучается в моно- и мультипрограммных режимах. Монопрограммный режим функционирования ВС предопределяет использование всех исправных ресурсов - элементарных машин (ЭМ) для решения одной сложной задачи, представленной параллельной программой. Мультипрограммные режимы работы ВС предусматривают распределение всего множества (исправных) ЭМ между задачами (различной сложности, с различным числом параллельных ветвей в их программах). К последним режимам относятся обработка набора задач и обслуживание потока задач [88, 117, 119].
При организации функционирования ВС в случае набора задач учитывается не только количество задач, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени, решения и др. Алгоритмы организации функционирования ВС задают распределение задач по машинам и последовательность выполнения задач на каждой машине. В результате становится известным, в каком промежутке времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора. Этот режим, безусловно, является обобщением режима решения сложной задачи на ВС.
Вместе с тем с позиций теории осуществимости решения задач этот режим без нарушения общности сводится к первому. В самом деле, осуществимость решения любой задачи набора зависит от параметров заданной для неё подсистемы, а анализ эффективности работы последней ничем не отличается от анализа всей системы при решении одной сложной задачи. Поэтому в дальнейшем ограничимся рассмотрением только режима решения одной сложной задачи на ВС.
Третий режим - обслуживание потока задач на ВС - принципиально отличается от обработки задач набора: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключён [1, 48, 100].
Для режимов решения сложной задачи и обслуживания потока задач на ВС ниже будут введены показатели осуществимости решения задач и рассмотрены методы расчёта этих показателей.
Математическое ожидание Л/(/, /) числа работоспособных машин при условии, что в начальный момент времени было исправно /є EQ = {0,1,2,..., Щ ЭМ) достаточно точно говорит об уровне потенциальной производительности ВС в момент / 0. Это тем точнее, чем больше общее число N машин в системе; сделанное допущение оправданно на практике при JV 10. Далее, для сложных задач допустимо составление адаптирующихся параллельных программ, в которых нижняя граница п числа параллельных ветвей не превышает ожидаемого числа работоспособных машин в любой момент времени, т.е. в которых п Л/(/, /). Тогда осуществимость решения сложной задачи на живучей ВС целесообразно оценивать функцией
Из (3.1) видно, что функция Ф(/,/) является вероятностью того, что сложная задача, представленная адаптирующейся параллельной программой, будет решена за время / на ВС, начавшей функционировать в состоянии / є Е" и использующей для решения задачи все работоспособные ЭМ. Если же ВС функционирует достаточно долго (находится в стационарном режиме), то вероятность решения задачи может быть выражена просто [119]:
Функции (3.1) и (3.2) называются функциями осуществимости решения сложной задачи на живучей ВС или функциями потенциальной осуществимости. При этом Ф(/, /) и Ф(0 характеризуют осуществимость соответственно в переходном и стационарном режимах работы системы. Считают, что решение сложной задачи осуществимо на живучей ВС в промежутке времени [0,/), если выполняются неравенства для переходного режима и неравенства Ф(/) Ф\ t f для стационарного режима функционирования системы. Величины Ф" и ґ называются порогами потенциальной осуществимости решения сложной задачи на ВС.
