М.: ФИЗМАТЛИТ, 2004. 320 стр.
Монография обобщает результаты исследований в области распределенных вычислений в масштабируемых средах, к которым можно отнести мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и ресурсы метакомпьютинга. Основное внимание уделяется различным формам модели обмена сообщениями и ее реализуемости, в том числе архитектурами с общей памятью. Рассматриваются вопросы семантики, однозначности результата и блокировки вычислений. Изучаются методы анализа свойств распределенных программ на маркированных графах и исследуется проблема алгоритмической разрешимости задачи анализа. Обосновываются принципы прогнозирования времени выполнения программ и их отображения на целевую архитектуру. Предлагаются методы планирования параллельных процессов в распределенных средах на основе масштабируемых моделей обработки.
Для специалистов по распределенным и параллельным вычислениям.
Может быть полезна аспирантам и студентам, обучающимся по направлениям Информатика и вычислительная техника, Прикладная математика и информатика .
МОДЕЛИ ВЫЧИСЛЕНИЙ
Особенности обработки в системах с масштабируемой архитектурой
Масштабируемые параллельные системы.
Общая характеристика и типы
Мультикомпьютеры
Кластеры
Симметричные мультипроцессоры
Системы с распределенной разделяемой памятью
Массово-параллельные системы
Вычисления и обмен данными в масштабируемых системах
Модель обмена сообщениями
Модель общей памяти
Прямой доступ к удаленной памяти
Парадигмы программирования
Модели программирования
Управление ресурсами в распределенных средах.
Системы и службы управления доступом к ресурсам
Классификация задач и типы алгоритмов планирования
Планирование вычислений в среде Grid
Комментарий и краткий обзор
Масштабируемые вычислительные системы
Модели вычислений и модели программирования
Управление ресурсами и планирование распределенных вычислений
Событийные и потоковые модели обмена сообщениями
Процессы, события, сообщения.
Таксономия систем взаимодействующих процессов
Событийное описание взаимодействующих процессов
Асинхронный обмен сообщениями и связанные с ним проблемы
Однозначность и семантика вычислений в модели обмена сообщениями
Достаточное условие однозначности результата вычислений
Операционная семантика вычислений.
Инварианты в поведении программ
Согласованность операционной и денотационной семантик вычислений
Потоковые модели распределенных вычислений
Потоковые модели и проблема блокировки вычислений
Маркированные потоковые графы
Связь проблем недетерминизма и блокировки вычислений
Комментарий и краткий обзор
Обнаружение и предотвращение блокировок распределенных вычислений
Разметка М-сетей и анализ реализуемости распределенных вычислений.
Анализ свойств программ на размеченных графах
Методы анализа
Постановка задачи разметки М-сетей
Стационарность и неизбыточность разметки
Примеры разметки М-сетей.
Разметка элементарных фрагментов
Разметка параллельных ветвей
Альтернативные разметки
Недостижимость стационарной разметки
Разрешимость задачи анализа потоковых моделей распределенных программ
Формализация схемы анализа
Интерпретация схемы анализа
Решение задачи ПАСС
Проблема разрешимости задачи анализа
Комментарий и краткий обзор
Прогнозирование времени выполнения программ.
Статический и динамический анализ программ.
Уровни и этапы анализа
Погрешность оценок модельного кода
Влияние вида целевой архитектуры на оценки сложности кода
Прямые измерения времени выполнения программ
Средства измерений
Фрагментация исходного кода программы
Эксперименты с фрагментированной программой
Побочные эффекты в экспериментальных исследованиях программ
Влияние особенностей операционной системы и архитектуры процессора
Примеры исследования сложности программ
Погрешность прямых измерений
Комментарий и краткий обзор
МОДЕЛИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
Выбор целевой архитектуры.
Отображение программы на ресурсы.
Спецификация программы и ее представление целевой архитектурой
Локализация области поиска целевой архитектуры
Синтез архитектуры и генетические алгоритмы
Основные этапы синтеза целевой архитектуры
Критерий существования целевой архитектуры
Схема поиска частичного описания архитектуры
Начальное разбиение спецификации
Критерий существования описания архитектуры
Сложность поиска описания
Разбиение спецификации программы
Задача доопределения
Основные этапы доопределения
Обоснование процедуры оптимального доопределения
Комментарий и краткий обзор
Краткая сводка необходимых сведений по комбинаторике и теории графов
Методы выбора целевой архитектуры
Масштабирование ресурсов и распределение вычислений
Модели планирования и распределения вычислений
Особенности распределения ресурсов в масштабируемых системах
Компоненты моделей составления расписаний
Модели составления расписаний со свободными параметрами
Преобразование графовой модели программы
Планирование на основе масштабируемой модели вычислений
Основные компоненты моделей масштабирования
Общая схема масштабирования
Метод критических работ
Модельный пример: минимизация стоимости завершения обработки
Разрешение коллизий параллельных процессов
Постановка задачи
Условно оптимальное и приближенное разрешение коллизий
Погрешность планирования
Комментарий и краткий обзор
Модели составления расписаний
Масштабируемые модели планирования вычислений
Стратегии планирования процессов и распределения ресурсов
Стратегии распределенных вычислений
Зачем нужны стратегии планирования
Примеры стратегий распределенных вычислений
Задача порождения стратегии
Декомпозиция задачи поиска оптимальной стратегии
Генерация условно оптимальных стратегий
Модельные примеры поиска оптимальных стратегий вычислений
Генерация Парето-оптимальной стратегии по трем критериям
Стратегии для вычислений с регулярной структурой
Выбор стратегии обработки
Постановка задачи выбора
Обоснование базовой схемы выбора стратегии
Примеры выбора стратегий обработки
Обобщение базовой схемы синтеза стратегий
Комментарий и краткий обзор
Монография обобщает результаты исследований в области распределенных вычислений в масштабируемых средах, к которым можно отнести мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и ресурсы метакомпьютинга. Основное внимание уделяется различным формам модели обмена сообщениями и ее реализуемости, в том числе архитектурами с общей памятью. Рассматриваются вопросы семантики, однозначности результата и блокировки вычислений. Изучаются методы анализа свойств распределенных программ на маркированных графах и исследуется проблема алгоритмической разрешимости задачи анализа. Обосновываются принципы прогнозирования времени выполнения программ и их отображения на целевую архитектуру. Предлагаются методы планирования параллельных процессов в распределенных средах на основе масштабируемых моделей обработки.
Для специалистов по распределенным и параллельным вычислениям.
Может быть полезна аспирантам и студентам, обучающимся по направлениям Информатика и вычислительная техника, Прикладная математика и информатика .
МОДЕЛИ ВЫЧИСЛЕНИЙ
Особенности обработки в системах с масштабируемой архитектурой
Масштабируемые параллельные системы.
Общая характеристика и типы
Мультикомпьютеры
Кластеры
Симметричные мультипроцессоры
Системы с распределенной разделяемой памятью
Массово-параллельные системы
Вычисления и обмен данными в масштабируемых системах
Модель обмена сообщениями
Модель общей памяти
Прямой доступ к удаленной памяти
Парадигмы программирования
Модели программирования
Управление ресурсами в распределенных средах.
Системы и службы управления доступом к ресурсам
Классификация задач и типы алгоритмов планирования
Планирование вычислений в среде Grid
Комментарий и краткий обзор
Масштабируемые вычислительные системы
Модели вычислений и модели программирования
Управление ресурсами и планирование распределенных вычислений
Событийные и потоковые модели обмена сообщениями
Процессы, события, сообщения.
Таксономия систем взаимодействующих процессов
Событийное описание взаимодействующих процессов
Асинхронный обмен сообщениями и связанные с ним проблемы
Однозначность и семантика вычислений в модели обмена сообщениями
Достаточное условие однозначности результата вычислений
Операционная семантика вычислений.
Инварианты в поведении программ
Согласованность операционной и денотационной семантик вычислений
Потоковые модели распределенных вычислений
Потоковые модели и проблема блокировки вычислений
Маркированные потоковые графы
Связь проблем недетерминизма и блокировки вычислений
Комментарий и краткий обзор
Обнаружение и предотвращение блокировок распределенных вычислений
Разметка М-сетей и анализ реализуемости распределенных вычислений.
Анализ свойств программ на размеченных графах
Методы анализа
Постановка задачи разметки М-сетей
Стационарность и неизбыточность разметки
Примеры разметки М-сетей.
Разметка элементарных фрагментов
Разметка параллельных ветвей
Альтернативные разметки
Недостижимость стационарной разметки
Разрешимость задачи анализа потоковых моделей распределенных программ
Формализация схемы анализа
Интерпретация схемы анализа
Решение задачи ПАСС
Проблема разрешимости задачи анализа
Комментарий и краткий обзор
Прогнозирование времени выполнения программ.
Статический и динамический анализ программ.
Уровни и этапы анализа
Погрешность оценок модельного кода
Влияние вида целевой архитектуры на оценки сложности кода
Прямые измерения времени выполнения программ
Средства измерений
Фрагментация исходного кода программы
Эксперименты с фрагментированной программой
Побочные эффекты в экспериментальных исследованиях программ
Влияние особенностей операционной системы и архитектуры процессора
Примеры исследования сложности программ
Погрешность прямых измерений
Комментарий и краткий обзор
МОДЕЛИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
Выбор целевой архитектуры.
Отображение программы на ресурсы.
Спецификация программы и ее представление целевой архитектурой
Локализация области поиска целевой архитектуры
Синтез архитектуры и генетические алгоритмы
Основные этапы синтеза целевой архитектуры
Критерий существования целевой архитектуры
Схема поиска частичного описания архитектуры
Начальное разбиение спецификации
Критерий существования описания архитектуры
Сложность поиска описания
Разбиение спецификации программы
Задача доопределения
Основные этапы доопределения
Обоснование процедуры оптимального доопределения
Комментарий и краткий обзор
Краткая сводка необходимых сведений по комбинаторике и теории графов
Методы выбора целевой архитектуры
Масштабирование ресурсов и распределение вычислений
Модели планирования и распределения вычислений
Особенности распределения ресурсов в масштабируемых системах
Компоненты моделей составления расписаний
Модели составления расписаний со свободными параметрами
Преобразование графовой модели программы
Планирование на основе масштабируемой модели вычислений
Основные компоненты моделей масштабирования
Общая схема масштабирования
Метод критических работ
Модельный пример: минимизация стоимости завершения обработки
Разрешение коллизий параллельных процессов
Постановка задачи
Условно оптимальное и приближенное разрешение коллизий
Погрешность планирования
Комментарий и краткий обзор
Модели составления расписаний
Масштабируемые модели планирования вычислений
Стратегии планирования процессов и распределения ресурсов
Стратегии распределенных вычислений
Зачем нужны стратегии планирования
Примеры стратегий распределенных вычислений
Задача порождения стратегии
Декомпозиция задачи поиска оптимальной стратегии
Генерация условно оптимальных стратегий
Модельные примеры поиска оптимальных стратегий вычислений
Генерация Парето-оптимальной стратегии по трем критериям
Стратегии для вычислений с регулярной структурой
Выбор стратегии обработки
Постановка задачи выбора
Обоснование базовой схемы выбора стратегии
Примеры выбора стратегий обработки
Обобщение базовой схемы синтеза стратегий
Комментарий и краткий обзор