Модели распределенных вычислений, Топорков В.В., 2004

Модели распределенных вычислений, Топорков В.В., 2004.
    
   Монография обобщает результаты исследований в области распределенных вычислений в масштабируемых средах, к которым можно отнести мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и ресурсы метакомпьютинга. Основное внимание уделяется различным формам модели обмена сообщениями и ее реализуемости, в том числе архитектурами с общей памятью. Рассматриваются вопросы семантики, однозначности результата и блокировки вычислений. Изучаются методы анализа свойств распределенных программ на маркированных графах и исследуется проблема алгоритмической разрешимости задачи анализа. Обосновываются принципы прогнозирования времени выполнения программ и их отображения на целевую архитектуру. Предлагаются методы планирования параллельных процессов в распределенных средах на основе масштабируемых моделей обработки.
Для специалистов по распределенным и параллельным вычислениям. Может быть полезна аспирантам и студентам, обучающимся по направлениям «Информатика и вычислительная техника», «Прикладная математика и информатика».




Системы с распределенной разделяемой памятью.
DSM-системы могут быть реализованы различными способами. Общим является наличие, помимо кэша, локальной памяти в каждом процессорном узле. Узел может состоять из нескольких процессоров и иметь архитектуру SMP. Поддерживается общее адресное пространство памяти. Однако при этом память является распределенной по узлам, и время доступа зависит от места расположения данных. Поэтому некоторые DSM-системы получили название NUMA (Non-Uniform Memory Access), что означает неоднородный доступ к памяти.

Один из способов реализации NUMA-архитектур — отказ от аппаратных средств поддержки когерентности кэшей. Наиболее известные примеры таких систем — это суперкомпьютеры Cray T3D/T3E. Процессорные узлы в таких системах объединяются сетью, в узлах которой размещаются специальные контроллеры, анализирующие адрес обращения к памяти. Если данные размещаются в памяти удаленного узла, то его контроллеру посылается сообщение для обращения к этим данным. Разделяемые данные не заносятся в кэши, что снимает проблему когерентности. Однако по сравнению с SMP-системами программирование таких NUMA-архитектур усложняется. Механизмы программной поддержки компилятором когерентности данных ограничены, и существующие методы применимы к программам с хорошо структурированным параллелизмом на уровне циклов.

ОГЛАВЛЕНИЕ.
Предисловие.
ЧАСТЬ I МОДЕЛИ ВЫЧИСЛЕНИЙ.
Глава 1. Особенности обработки в системах с масштабируемой архитектурой.
§1.1. Масштабируемые параллельные системы.
1.1.1. Общая характеристика и типы (11). 1.1.2. Мультикомпьютеры (12). 1.1.3. Кластеры (13). 1.1.4. Симметричные мультипроцессоры (14). 1.1.5. Системы с распределенной разделяемой памятью (16). 1.1.6. Массово-параллельные системы (20).
§ 1.2. Вычисления и обмен данными в масштабируемых системах.
1.2.1. Модель обмена сообщениями (21). 1.2.2. Модель общей памяти (27). 1.2.3. Прямой доступ к удаленной памяти (33). 1.2.4. Парадигмы программирования (34). 1.2.5. Модели программирования (37).
§ 1.3. Управление ресурсами в распределенных средах.
1.3.1. Системы и службы управления доступом к ресурсам (40).
1.3.2. Классификация задач и типы алгоритмов планирования (46). 1.3.3. Планирование вычислений в среде Grid (53).
§ 1.4. Комментарий и краткий обзор к главе 1.
1.4.1. Масштабируемые вычислительные системы (56). 1.4.2. Модели вычислений и модели программирования (56). 1.4.3. Управление ресурсами и планирование распределенных вычислений (57).
Глава 2. Событийные и потоковые модели обмена сообщениями.
§ 2.1. Процессы, события, сообщения.
2.1.1. Таксономия систем взаимодействующих процессов (59). 2.1.2. Событийное описание взаимодействующих процессов (63). 2.1.3. Асинхронный обмен сообщениями и связанные с ним проблемы (69).
§ 2.2. Однозначность и семантика вычислений в модели обмена сообщениями.
2.2.1. Достаточное условие однозначности результата вычислений (71). 2.2.2. Операционная семантика вычислений (75). 2.2.3. Инварианты в поведении программ (77). 2.2.4. Согласованность операционной и денотационной семантик вычислений (80).
§ 2.3. Потоковые модели распределенных вычислений.
2.3.1. Потоковые модели и проблема блокировки вычислений (82). 2.3.2. Маркированные потоковые графы (86). 2.3.3. Связь проблем недетерминизма и блокировки вычислений (92).
§ 2.4. Комментарий и краткий обзор к главе 2.
Глава 3. Обнаружение и предотвращение блокировок распределенных вычислений.
§3.1. Разметка М-сетей и анализ реализуемости распределенных вычислений.
3.1.1. Анализ свойств программ на размеченных графах (99). 3.1.2. Методы анализа (101). 3.1.3. Постановка задачи разметки М-сетей (106). 3.1.4. Стационарность и неизбыточность разметки (111).
§3.2. Примеры разметки М-сетей.
3.2.1. Разметка элементарных фрагментов (113). 3.2.2. Разметка параллельных ветвей (114). 3.2.3. Альтернативные разметки (116). 3.2.4. Недостижимость стационарной разметки (118).
§ 3.3. Разрешимость задачи анализа потоковых моделей распределенных программ.
3.3.1. Формализация схемы анализа (122). 3.3.2. Интерпретация схемы анализа (125). 3.3.3. Решение задачи ПАСС (126). 3.3.4. Проблема разрешимости задачи анализа (128).
§3.4. Комментарий и краткий обзор к главе 3.
Глава 4. Прогнозирование времени выполнения программ.
§ 4.1. Статический и динамический анализ программ.
4.1.1. Уровни и этапы анализа (134). 4.1.2. Погрешность оценок модельного кода (138). 4.1.3. Влияние вида целевой архитектуры на оценки сложности кода (144).
§4.2. Прямые измерения времени выполнения программ.
4.2.1. Средства измерений (147). 4.2.2. Фрагментация исходного кода программы (151). 4.2.3. Эксперименты с фрагментированной программой (159).
§4.3. Побочные эффекты в экспериментальных исследованиях программ.
4.3.1. Влияние особенностей операционной системы и архитектуры процессора (162). 4.3.2. Примеры исследования сложности программ (163). 4.3.3. Погрешность прямых измерений (167).
§ 4.4. Комментарий и краткий обзор к главе 4.
ЧАСТЬ II МОДЕЛИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ.
Глава 5. Выбор целевой архитектуры.
§ 5.1. Отображение программы на ресурсы.
5.1.1. Спецификация программы и ее представление целевой архитектурой (171). 5.1.2. Локализация области поиска целевой архитектуры (175). 5.1.3. Синтез архитектуры и генетические алгоритмы (182). 5.1.4. Основные этапы синтеза целевой архитектуры (186).
§ 5.2. Критерий существования целевой архитектуры.
5.2.1. Схема поиска частичного описания архитектуры (188). 5.2.2. Начальное разбиение спецификации (190). 5.2.3. Критерий существования описания архитектуры (196). 5.2.4. Сложность поиска описания (200).
§ 5.3. Разбиение спецификации программы.
5.3.1. Задача доопределения (202). 5.3.2. Основные этапы доопределения (203). 5.3.3. Обоснование процедуры оптимального доопределения (205).
§ 5.4. Комментарий и краткий обзор к главе 5.
5.4.1. Краткая сводка необходимых сведений по комбинаторике и теории графов (207). 5.4.2. Методы выбора целевой архитектуры (211).
Глава 6. Масштабирование ресурсов и распределение вычислений.
§ 6.1. Модели планирования и распределения вычислений.
6.1.1. Особенности распределения ресурсов в масштабируемых системах (214). 6.1.2. Компоненты моделей составления расписаний (217). 6.1.3. Модели составления расписаний со свободными параметрами (224). 6.1.4. Преобразование графовой модели программы (226). 6.1.5. Планирование на основе масштабируемой модели вычислений (229). 6.1.6. Основные компоненты моделей масштабирования (232).
§ 6.2. Общая схема масштабирования.
6.2.1. Метол критических работ (239). 6.2.2. Модельный пример: минимизация стоимости завершения обработки (243).
§ 6.3. Разрешение коллизий параллельных процессов.
6.3.1. Постановка задачи (250). 6.3.2. Условно оптимальное и приближенное разрешение коллизий (253). 6.3.3. Погрешность планирования (257).
§ 6.4. Комментарий и краткий обзор к главе 6.
6.4.1. Модели составления расписаний (259). 6.4.2. Масштабируемые модели планирования вычислений (260).
Глава 7. Стратегии планирования процессов и распределения ресурсов.
§7.1. Стратегии распределенных вычислений.
7.1.1. Зачем нужны стратегии планирования (262). 7.1.2. Примеры стратегий распределенных вычислений (264). 7.1.3. Задача порождения стратегии (268). 7.1.4. Декомпозиция задачи поиска оптимальной стратегии (270). 7.1.5. Генерация условно оптимальных стратегий (271).
§ 7.2. Модельные примеры поиска оптимальных стратегий вычислений.
7.2.1. Генерация Парето-оптимальной стратегии по трем критериям (273). 7.2.2. Стратегии для вычислений с регулярной структурой (278).
§ 7.3. Выбор стратегии обработки.
7.3.1. Постановка задачи выбора (281). 7.3.2. Обоснование базовой схемы выбора стратегии (285). 7.3.3. Примеры выбора стратегий обработки (287). 7.3.4. Обобщение базовой схемы синтеза стратегий (291).
§ 7.4. Комментарий и краткий обзор к главе 7.
Заключение.
Список литературы.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Модели распределенных вычислений, Топорков В.В., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по информатике :: информатика :: компьютеры :: Топорков