Графическая объектная модель параллельных процессов и ее применение в программных комплексах численного моделирования

• Автор: Востокин, Сергей Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2007
• Место защиты: Самара
• Количество страниц: 307 с. : ил.

СОДЕРЖАНИЕ

ШСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

1. ОБЗОР МЕТОДОВ, МОДЕЛЕЙ И ПРОГРАММНЫХ СИСТЕМ В

ОБЛАСТИ ПАРАЛЛЕЛЬНОГО И РАСПРЕДЕЛЕННОГО ПРОГРАММИРОВА1ШЯ

1.1. Теоретические основы параллельного и распределенного

программирования

1.1.1. Формальные методы в области параллельных и распределенных

вычислений

1.1.2. Классификация моделей распределенных систем

1.1.3. Основные параллельные и распределенные алгоритмы

1.2. Системное программное обеспечение параллельных и
распределенных вычислений
1.2.1. Прикладные интерфейсы операционных систем
1.2.2. Стандарт МР
1.2.3. Библиотеки стандарта I и V
1.2.4. Сокеты и средства удаленного вызова процедур
1.2.5. Гридтехнологии и подобное промежуточное программное
обеспечение
1.2.5.1.редпосылки исследований по гридтехнологиям
1.2.5.2. Определение гридсистемы
1.2.5.3. Архитектура гридсистсм
1.2.5.4. Программное обеспечение гридсистем
1.3. Средства и методы разработки параллельных вычислительных
приложений
1.3.1. Языковые средства
1.3.2. Повторное использование кода в виде библиотек
1.3.3. Повторное использование типовых схем вычислений
1.3.4. Автоматизированное распараллеливание
1.3.5. Средства визуального проектирования параллельных программ
1.4. Выводы
2. ОБЪЕКТНАЯ ГРАФИЧЕСКАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ И
РАСПРЕДЕЛЕННЫХ ВБ1ЧИСЛЕНИЙ
2.1. Спецификация модели вычислений
2.1.1. Принцип моделирования вычислительных процессов. Основные
определения
2.1.2. Метод описания дискретных систем с использованием
темпоральной логики
2.1.3. Специализация темпоральной логики по Лампорту
2.1.4. Спецификация модели
2.2. Примеры спецификаций вычислительных процессов
2.2.1. Конкурентное взаимодействие вычислительных процессов
2.2.2. Кооперативное взаимодействие вычислительных процессов
2.3. Визуализация модели вычислительных процессов
2.3.1. Представление функциональных отношений модели в виде
диаграмм Робъсктов
2.3.2. Построение алгоритмов, реализующих функциональные
отношения модели по диаграммам Робъектов
2.4. Выводы
3. МЕТОД ОПИСАНИЯ ПРОСТРАНСТВЕННОРАСПРЕДЕЛЕННЫХ
ПАРАЛЛЕЛЬ 1ЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
3.1. Язык моделирования
3.1.1. Словарь и представление
3.1.2. Структура модели файлы, модули и структурные элементы
3.1.3. Пространства имен, объявления и области их действия
3.1.4. Использование параметров модулей
3.1.5. Описание типов и переменных
3.1.6. Описание действий, портов и условий
3.1.7. Описание работ и процессов
3.2. Особенности синтаксического анализа моделей
3.2.1. Метод преобразования текстового представления модели
в машинноориентированный формат
3.2.2. Команды описания модульной структуры
3.2.3. Конструкторы структурных элементов модели
3.2.4. Команды записи атрибутов структурных элементов модели
3.2.5. Пример преобразования модели в последовательность команд,
строящих сеть структурных элементов
3.3. Выводы
4. ПОСТРОЕНИЕ БИБЛИОТЕК ЧИСЛЕННЫХ МЕТОДОВ НА
ОСНОВЕ ГРАФИЧЕСКОГО ОБЪЕКТНОГО ПРЕДСТАВЛЕНИЯ СХЕМ ТИПОВЫХ
АРАЛЛЕЛЪНЫХ АЛ1 ОРИТМОВ
4.1. Принцип описания семейства алгоритмов на примере схемы
применить ко всем МАР
4.1.1. Определение объектов схемы МАР и эквивалентной
последовательной схемы
4.1.2. Определение схемы МАР с использованием графического
объектного представления
4.1.3. Пример реализации алгоритма умножения матриц
4.2. Схема портфель задач
4.2.1. Определение объектов схемы и эквивалентной
последовательной схемы
4.2.2. Определение схемы с использованием графического
объектного представления
4.2.3. Примеры реализации алгоритмов с использованием
схемы
4.2.3.1. Аппроксимация интеграла непрерывной функции методом адаптивной квадратуры
4.2.3.2. Сканирование параметрического пространства в
задачах межвидовой конкуренции
4.3. Схема цепь из асинхронно взаимодействующих
процессов I
4.3.1. Принцип распараллеливания последовательного
алгоритма по схеме I I
4.3.2. Определение объектов схемы I и эквивалентной
последовательной схемы
4.3.3. Определение схемы I с использованием графического
объектного представления
4.3.4. Примеры реализации алгоритмов с использованием
схемы I
4.3.4.1. Решение уравнения Лапласа методом ГауссаЗсйделя
4.3.4.2. Задача о распространении световых воли в диэлектрике
4.4. Выводы
5. РЕАЛИЗАЦИЯ ПРОГРАММНОГО КОМПЛЕКСА И ПРИКЛАДНЫХ
ПРОГРАММ ЧИСЛЕННОГО МОДЕЛИРОВАНИЯ
5.1. Инструменты программного комплекса
5.1.1. Общие сведения об архитектуре программного комплекса
5.1.2. Особенности реализации транслятора моделей алгоритмов
5.1.3. Особенности работы интерпретатора моделей алгоритмов
5.2. Экспериментальная проверка эффективности среды
исполнения моделей
5.2.1. Требования к среде времени исполнения моделей
вычислительных процессов
5.2.2. Реализация алгоритма управления вычислениями на основе
патгерна ПостоялецПосетитель
5.2.3. Результаты нагрузочного тестирования алгоритма по схеме
I на многопроцессорных машинах с общей памятью
5.2.4. Результаты нафузочного тестирования алгоритма по схеме
в гридсреде
5.3. Исследование эффективности численною моделирования
имитационным методом
5.3.1. Имитационная модель для исследования эффективности
исполнения вычислительных процессов
5.3.2. Результаты имитационного моделирования вычислительного
процесса по схеме I в распределенной гетерогенной
5.4. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Простейшая топология коммуникации представляет собой полносвязанный коммуникационный граф, где каждый процесс может посылать сообщения непосредственно любому другому процессу. Для реализации такой модели при помощи модели с более слабыми допущениями используются алгоритмы трассировки. Синхронность. По критерию синхронности различают следующие виды моделей. Полностью асинхронная модель это такая модель, в которой нет понятия реального времени. Она предполагает, что сообщения доставляются в произвольное время, и процессы отвечают в произвольное время. При этом не делается никаких допущений, сколько времени занимает доставка и ответ. Другие модели вводят понятие времени. В них считается известной верхняя граница времени передачи сообщений и время отклика процесса все временные условия рассматриваются в отсутствии отказов. Простейшая форма этого допущения заключается в том, что сообщение, сгенерированное в ответ на событие в произвольное время , приходит в точку назначения во время , где 6 известная константа. Для того чтобы использовать это предположение, процессы должны уметь измерять время. Простейший измеритель это таймер, который измеряет промежутки времени. При этом мгновенные значения таймеров в разных процессах независимы друг от друга. Таймеры используются для обнаружения отказов. Отказ произошел, если ответ на сообщение не получен в течение 2секунд с момента отправки этого сообщения. Более строгое допущение состоит в том, что процесс имеет синхронизированные часы, которые идут с приблизительно одинаковой скоростью относительно реальных часов. Простейшая форма допущения заключается в следующем. В каждый момент времени часы любых двух процессов отличаются по крайней мере на е, где е некоторая известная константа. Синхронизированные часы используются для уменьшения числа пересылаемых сообщений. Здесь б обозначает время передачи, а е разницу показаний часов. Следовательно, отказ можно проверять, посылая единственное сообщение, в то время как запросответ с использованием таймера требует двух сообщений. Если известны ограничения на скорость хода таймеров двух различных процессов и ограничения на время посылки и обработки сообщений, существуют алгоритмы построения синхронных часов из таймеров. Наиболее строги синхронные модели, в которых вычисления выполняются как последовательность циклов. В течение цикла каждый процесс посылает сообщения возможно, каждому другому процессу, основанные на сообщениях, полученных в предыдущих циклах, то есть процессы работают как процессоры в синхронном компьютере. Такая модель легко реализуется с использованием синхронизированных часов. Отказы. В моделях обмена сообщениями рассматриваются отказы процессов и коммуникационные отказы. Обычно допускается, что коммуникационные отказы заключаются в потере сообщений. Модели, в которых может происходить доставка некорректных сообщений, изучаются редко, потому что на практике использование избыточной информации контрольных сумм позволяет обнаруживать и удалять искаженные сообщения. Модели могут допускать ошибки, разрушающие отдельные сообщения или отказы линков. Отказ линка может вызвать потерю всех сообщений, проходящих по линку, а в моделях с часами или таймерами поврежденный линк может доставлять сообщения слишком поздно. Так как алгоритмы, которые используют таймеры или часы обычно удаляют запоздавшие сообщения, нет необходимости различать запаздывание и потерю сообщений. Особые случаи отказов линков заключаются в возможности разрыва сети, когда коммуникационный граф становится несвязанным, и некоторые пары узлов не могут взаимодействовать друг с другом. Самое слабое допущение об отказе процессов заключается в том, что отказ одного процесса не может повлиять на взаимодействие по линку, соединяющему два других процесса, но возможно любое другое поведение отказавшего процесса. Такие модели называют моделями с византийским отказом. Более строгие модели допускают отказы в виде пропусков, в которых поврежденный процесс не может посылать некоторые сообщения. Гак как запоздавшие сообщения обычно удаляются, отказы, приводящие к задержке посылок сообщений, можно рассматривать как пропуски.