год издания — 2013, кол-во страниц — 328, ISBN — 978-5-211-06382-2, тираж — 1800, язык — русский, тип обложки — твёрд. 7БЦ матов., масса книги — 410 гр., издательство — МГУ

серия — Суперкомпьютерное образование

КНИГА СНЯТА С ПРОДАЖИ

Формат 60x84 1/16. Бумага офсетная №1. Печать офсетная

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

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

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

Учебное пособие основано на материалах лекций, читавшихся на протяжении многих лет в Московском физико-техническом институте (государственном университете).

Рекомендовано Советом учебно-методического объединения классических университетов по прикладной математике и информатике.

Глава 1. Введение	11

1.1. Современный компьютер — инструмент параллельной обработки данных	11
1.2. Области применения многопроцессорных систем	16
1.3. Рассматриваемые параллельные архитектуры	19
1.4. Пример параллельного алгоритма	20
1.4.1. Последовательный рекурсивный алгоритм	21
1.4.2. Параллельный рекурсивный алгоритм	21
1.4.3. Последовательное вычисление членов ряда	22
1.4.4. Последовательный матричный алгоритм	23
1.4.5. Параллельный матричный алгоритм	24

Глава 2. Основные понятия	28

2.1. Параллельная программа как ансамбль взаимодействующих
последовательных процессов	28
2.2. Внутренний параллелизм	29
2.2.1. Сложение многоразрядных чисел	30
2.3. Ускорение и эффективность параллельных алгоритмов	38
2.4. Ускорение и эффективность относительно наилучшего
последовательного алгоритма	41
2.4.1. Неравноправность условий выполнения — первая причина
сверхлинейного ускорения	43
2.4.2. Алгоритмическая причина сверхлинейного ускорения	44
2.4.3. Формальное преобразование параллельного алгоритма
в «наилучший» последовательный	47
2.5. Априорная оценка эффективности параллельного алгоритма	49

Глава 3. Модели параллельных программ	53

3.1. Вычислительные системы с распределённой памятью	54
3.2. Вычислительные системы с общей памятью	56
3.3. Гибридные архитектуры	58
3.4. Модель выполнения параллельной программы на распределённой
памяти	59
3.5. Модель выполнения параллельной программы на обшей памяти	60
3.6. Средства взаимодействия последовательных процессов	62
3.6.1. Свойства канала передачи данных	62
3.6.2. Методы передачи данных	63
3.6.3. Семафор	72
3.6.4. Барьерная синхронизация	75

Глава 4. Базовые параллельные методы	77

4.1. Метод сдваивания	78
4.1.1. Быстрый алгоритм выбора частичных сумм	84
4.1.2. Барьерная синхронизация на основе синхронных обменов	86
4.1.3. Стена Фокса	88
4.2. Метод геометрического параллелизма	88
4.3. Метод конвейерного параллелизма	98
4.4. Метод коллективного решения	107
4.5. Причины потери эффективности	114

Глава 5. Сортировка данных	117

5.1. Постановка задачи	117
5.2. Последовательные алгоритмы сортировки	120
5.2.1. Быстрая сортировка (runtime qsort, wsort)	123
5.2.2. Простое двухпутевое слияние (dsort) и слияние списков
(lsort)	124
5.2.3. Пирамидальная сортировка (hsort)	126
5.3 Свойства последовательных алгоритмов	128
5.3.1. Сортировка методом простого двухпутевого слияния	128
5.3.2. Пирамидальная сортировка	135
5.3.3. Наилучший последовательный алгоритм сортировки dhsort	139
5.4. Масштабируемые алгоритмы сортировки	141
5.4.1. Сети сортировки	141
5.4.2. Сеть чётно-нечётной сортировки	144
5.4.3. Сеть обменной сортировки со слиянием Бэтчера	145
5.4.4. Сортировка больших массивов	150
5.4.5. Сравнение алгоритмов сортировки	153
5.5. Результаты численных экспериментов	157

Глава 6. Генерация псевдослучайных чисел	161

6.1. Требования к генераторам псевдослучайных чисел для МВС	162
6.2. Линейно-конгруэнтные генераторы	168
6.3. M-последовательности	170
6.4. Проверка примитивности полиномов	176
6.5. Тестирование генераторов	177

Глава 7. Декомпозиция сеточных графов	180

7.1. Пример двумерной сетки	180
7.2. Критерии декомпозиции графов	182
7.2.1. Критерий 1: классический критерий декомпозиции графа	183
7.2.2. Критерий 2: выделение обособленных доменов	184
7.2.3. Критерий 3: минимизация максимальной степени домена	185
7.2.4. Критерий 4: обеспечение связности графов каждого
из доменов	186
7.3. Декомпозиция на основе исходной нумерации узлов	189
7.4. Рекурсивная бисекция	191
7.5. Декомпозиция регулярных графов	192
7.6. Методы декомпозиции произвольных графов	196
7.6.1. Иерархическая декомпозиция	196
7.6.2. Спектральная бисекция	205
7.6.3. Алгоритм инкрементного роста	210
7.7. Декомпозиция больших сеток	217
7.7.1. Координатная рекурсивная бисекция	218
7.7.2. Двухуровневая стратегия обработки и хранения сеток	220

Глава 8. Динамическая балансировка загрузки процессоров	223

8.1. Стратегии балансировки загрузки	223
8.2. Метод диффузной балансировки	224
8.3. Моделирование горения метанового факела	229
8.3.1. Постановка задачи динамической балансировки	235
8.3.2. Алгоритм серверного параллелизма	236
8.4. Адаптивное интегрирование	248
8.4.1. Последовательные алгоритмы	249
8.4.2. Параллельные алгоритмы	256

Глава 9. Визуализация сеточных данных	278

9.1. Клиент-серверная технология	280
9.2. Online или Offline-визуализация: плюсы и минусы	281
9.2.1. Online-визуализация Offline-визуализация	281
9.3. Этапы визуализации	285
9.4. Визуализация изоповерхностей	290
9.4.1. Аппроксимация изоповерхности	293
9.4.2. Виды данных, описывающих триангуляцию	296
9.4.3. Метод редукции	299
9.4.4. Заполняющие пространство триангуляции	302
9.4.5. Параллельные алгоритмы построения аппроксимирующих
триангуляций	303
9.4.6. Многоуровневое огрубление больших сеток	304
9.4.7. Примеры визуализации	306
9.5. Ввод-вывод сеточных данных	308
9.5.1. Соотношение времени чтения данных и времени их обработки	308
9.5.2. Распределённый ввод-вывод	309
9.5.3. Огрубление и сжатие скалярных сеточных функций	310

Список ссылок	317
Предметный указатель	323

Книги на ту же тему

Численные методы, алгоритмы и программы. Введение в распараллеливание: Учебное пособие для вузов, Карпов В. Е., Лобанов А. И., 2014
Технологии параллельного программирования MPI и OpenMP: Учебное пособие, Антонов А. С., 2012
Современные языки и технологии параллельного программирования: Учебник, Гергель В. П., 2012
Параллельное программирование в среде MATLAB для многоядерных и многоузловых вычислительных машин: Учебное пособие, Кепнер Д., 2013
Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
Введение в алгоритмы параллельных вычислений, Молчанов И. Н., 1990
Многоядерное программирование, Эхтер Ш., Робертс Д., 2010
Социальное моделирование — новый компьютерный прорыв (агент-ориентированные модели), Макаров В. Л., Бахтизин А. Р., 2013
Распределённые системы. Принципы и парадигмы, Таненбаум Э., ван Стеен М., 2003
Операционные системы. Параллельные и распределённые системы, Бэкон Д., Харрис Т., 2004
Параллельные вычислительные системы, Головкин Б. А., 1980
Параллельная обработка информации: Т. 5: Проблемно-ориентированные и специализированные средства обработки информации, Малиновский Б. Н., Грицык В. В., ред., 1990
Библиотека алгоритмов 151б—200б: Справочное пособие. Вып. 4, Агеев М. И., Алик В. П., Марков Ю. И., сост., 1981
Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
Суперкомпьютерное моделирование в физике климатической системы: Учебное пособие, Лыкосов В. Н., Глазунов А. В., Кулямин Д. В., Мортиков Е. В., Степаненко В. М., 2012

elapsed time 0.021 sec

/ИТ-книги

ОГЛАВЛЕНИЕ

Книги на ту же тему