Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Параллельное и конкурентное программирование на языке Haskell

Покупка
Новинка
Артикул: 487676.03.99
Доступ онлайн
479 ₽
В корзину
Если вы уже владеете программированием на языке Haskell, эта книга научит вас использованию множества интерфейсов и библиотек, предназначенных для написания параллельных и конкурентных программ. Вы узнаете, как распараллеливание на многоядерные процессоры позволяет ускорять вычислительно нагруженные программы и как конкурентность облегчает написание программ с активно взаимодействующими между собой и с другими программами потоками. Автор Саймон Марлоу проведёт вас по этому пути, сопровождая его большим количеством примеров, с которыми можно самостоятельно экспериментировать, запуская, изменяя и расширяя. Книга делится на две части, посвящённые таким инструментам, как Parallel Haskell и Concurrent Haskell, включённые в неё упражнения позволят вам научиться: • выражать параллелизм в языке Haskell средствами монады Eval и стратегий вычислений; • распараллеливать обычный код на языке Haskell в монаде Par; • организовывать параллельные вычисления с массивами на основе библиотеки Repa; • использовать библиотеку Accelerate для запуска вычислений на графических процессорах; • работать с базовыми интерфейсами для написания конкурентного кода; • реализовывать высокопроизводительные конкурентные сетевые серверы; • писать распределённые программы, запускающиеся на множестве машин сети.
Марлоу, С. Параллельное и конкурентное программирование на языке Haskell : практическое руководство / С. Марлоу ; пер. с англ. В. Н. Брагилевского. – Москва : ДМК Пресс, 2017. - 373 с. – ISBN 978-5-97060-560-8. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2260249 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Саймон Марлоу
Параллельное и конкурентное
программирование на языке
Haskell
Москва, 2017


Parallel and Concurrent
Programming in Haskell
Simon Marlow
Beijing • Cambridge • Farnham • K¨oln • Sebastopol • Tokyo


Параллельное и конкурентное
программирование на языке
Haskell
Саймон Марлоу
Перевод с английского
В. Н. Брагилевского
Москва, 2017


УДК
004.432.42 Haskell
ББК
32.973.28-018.1
М28
М28
Саймон Марлоу
Параллельное и конкурентное программирование на языке Haskell / Пер.
с англ. В. Н. Брагилевского. – М.: ДМК Пресс, 2017. — 372 с.: ил.
Если вы уже владеете программированием на языке Haskell, эта книга научит вас использованию множества интерфейсов и библиотек, предназначенных
для написания параллельных и конкурентных программ. Вы узнаете, как распараллеливание на многоядерные процессоры позволяет ускорять вычислительно
нагруженные программы и как конкурентность облегчает написание программ с
активно взаимодействующими между собой и с другими программами потоками.
Автор Саймон Марлоу проведёт вас по этому пути, сопровождая его большим количеством примеров, с которыми можно самостоятельно экспериментировать, запуская, изменяя и расширяя. Книга делится на две части, посвящённые
таким инструментам, как Parallel Haskell и Concurrent Haskell, включённые в неё
упражнения позволят вам научиться:
• выражать параллелизм в языке Haskell средствами монады Eval и стратегий вычислений;
• распараллеливать обычный код на языке Haskell в монаде Par;
• организовывать параллельные вычисления с массивами на основе библиотеки Repa;
• использовать библиотеку Accelerate для запуска вычислений на графических процессорах;
• работать с базовыми интерфейсами для написания конкурентного кода;
• реализовывать высокопроизводительные конкурентные сетевые серверы;
• писать распределённые программы, запускающиеся на множестве машин
сети.
УДК 004.432.42 Haskell
ББ 32.973.28-018.1
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы
то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев
авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок всё равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не
несёт ответственности за возможные ошибки, связанные с использованием книги.
ISBN 978-1-449-33594-6 (англ.)
© 2013 Simon Marlow
ISBN 978-5-97060-560-8 (рус.)
© Перевод на русский язык, оформление,
ДМК Пресс
ISBN 978-5-97060-560-8


Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
Терминология: параллелизм и конкурентность . . . . . . . . . . .
17
Инструменты и документация . . . . . . . . . . . . . . . . . . . . .
19
Примеры программ . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Часть I.
Parallel Haskell . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.
Простейший параллелизм: монада Eval . . . . . . . . . . . . . . .
26
Ленивые вычисления и слабая головная нормальная форма . . .
26
Монада Eval, rpar и rseq . . . . . . . . . . . . . . . . . . . . . . . .
33
Пример: распараллеливание решателя судоку
. . . . . . . . . . .
37
Модуль DeepSeq . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.
Стратегии вычислений . . . . . . . . . . . . . . . . . . . . . . . . .
51
Параметризованные стратегии
. . . . . . . . . . . . . . . . . . . .
53
Стратегия для параллельного вычисления списка . . . . . . . . .
55
Пример: задача k-средних . . . . . . . . . . . . . . . . . . . . . . .
56
Распараллеливание k-средних . . . . . . . . . . . . . . . . . .
62
Производительность и анализ . . . . . . . . . . . . . . . . . .
63
Визуализация активности нитей . . . . . . . . . . . . . . . . .
68
Размеры заданий
. . . . . . . . . . . . . . . . . . . . . . . . .
68
Сборка мусора для нитей и спекулятивный параллелизм . . . . .
71
Распараллеливание ленивых потоков посредством parBuffer
. . .
74
Стратегии разбиения на фрагменты . . . . . . . . . . . . . . . . .
79
Свойство тождественности . . . . . . . . . . . . . . . . . . . . . . .
79
4.
Параллелизм по данным: монада Par . . . . . . . . . . . . . . . .
81
Пример: кратчайшие пути на графе
. . . . . . . . . . . . . . . . .
86
Конвейерный параллелизм . . . . . . . . . . . . . . . . . . . . . . .
91
Ограничение скорости производителя
. . . . . . . . . . . . .
96
Ограничения конвейерного параллелизма . . . . . . . . . . .
96


Оглавление
Пример: расписание конференции
. . . . . . . . . . . . . . . . . .
97
Распараллеливание . . . . . . . . . . . . . . . . . . . . . . . .
103
Пример: параллельный вывод типов . . . . . . . . . . . . . . . . .
107
Использование разных планировщиков
. . . . . . . . . . . . . . .
113
Сравнение монады Par и стратегий вычислений
. . . . . . . . . .
113
5.
Параллельное программирование с библиотекой Repa
. . . . . .
115
Массивы, формы и индексы . . . . . . . . . . . . . . . . . . . . . .
116
Операции над массивами . . . . . . . . . . . . . . . . . . . . . . . .
119
Пример: вычисление кратчайших путей . . . . . . . . . . . . . . .
122
Распараллеливание . . . . . . . . . . . . . . . . . . . . . . . .
125
Свёртки и полиморфизм форм
. . . . . . . . . . . . . . . . . . . .
128
Пример: поворот изображения
. . . . . . . . . . . . . . . . . . . .
130
Резюме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
135
6.
Программирование GPU с библиотекой Accelerate . . . . . . . . .
136
Обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
137
Массивы и индексы . . . . . . . . . . . . . . . . . . . . . . . . . . .
138
Запуск простого Accelerate-вычисления
. . . . . . . . . . . . . . .
140
Скаляры как массивы
. . . . . . . . . . . . . . . . . . . . . . . . .
142
Индексация массивов . . . . . . . . . . . . . . . . . . . . . . . . . .
143
Создание массивов внутри Acc
. . . . . . . . . . . . . . . . . . . .
143
Склеивание массивов . . . . . . . . . . . . . . . . . . . . . . . . . .
145
Константы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
146
Пример: кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . .
146
Запуск на GPU
. . . . . . . . . . . . . . . . . . . . . . . . . .
150
Отладка CUDA
. . . . . . . . . . . . . . . . . . . . . . . . . .
151
Пример: генератор множества Мандельброта . . . . . . . . . . . .
152
Часть II. Concurrent Haskell . . . . . . . . . . . . . . . . . . . . . . . .
159
7.
Простейшая конкурентность: потоки и изменяемые
переменные
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162
Простой пример: напоминания
. . . . . . . . . . . . . . . . . . . .
163
Передача данных: переменные MVar . . . . . . . . . . . . . . . . .
166
MVar как простой канал: служба журнализации . . . . . . . . . .
168
MVar как контейнер для разделяемого состояния
. . . . . . . . .
172
MVar как строительный блок: неограниченные каналы
. . . . . .
175
Справедливость . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
180
8.
Ввод-вывод в фоновом режиме . . . . . . . . . . . . . . . . . . . .
182
Исключения в Haskell . . . . . . . . . . . . . . . . . . . . . . . . . .
185
Обработка ошибок в Async . . . . . . . . . . . . . . . . . . . . . . .
191
Слияние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
193


Оглавление
9.
Аннулирование и тайм-ауты
. . . . . . . . . . . . . . . . . . . . .
197
Асинхронные исключения . . . . . . . . . . . . . . . . . . . . . . .
198
Маскирование асинхронных исключений
. . . . . . . . . . . . . .
201
Функция bracket . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
205
Безопасность по асинхронным исключениям для каналов . . . . .
206
Тайм-ауты
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
208
Перехват асинхронных исключений
. . . . . . . . . . . . . . . . .
211
Функция mask и вызов forkIO . . . . . . . . . . . . . . . . . . . . .
213
Асинхронные исключения: обсуждение
. . . . . . . . . . . . . . .
215
10. Программная транзакционная память . . . . . . . . . . . . . . . .
217
Основной пример: управление окнами . . . . . . . . . . . . . . . .
218
Блокирование
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
222
Блокирование до момента изменения условия . . . . . . . . . . . .
225
Слияние средствами STM . . . . . . . . . . . . . . . . . . . . . . .
227
Возвращение к Async . . . . . . . . . . . . . . . . . . . . . . . . . .
228
Реализация каналов средствами STM
. . . . . . . . . . . . . . . .
230
Возможность других операций
. . . . . . . . . . . . . . . . .
232
Комбинирование блокируемых операций . . . . . . . . . . . .
232
Безопасность асинхронных исключений . . . . . . . . . . . .
233
Альтернативная реализация каналов . . . . . . . . . . . . . . . . .
234
Ограниченные каналы
. . . . . . . . . . . . . . . . . . . . . . . . .
237
Чего нельзя делать с STM?
. . . . . . . . . . . . . . . . . . . . . .
239
Производительность
. . . . . . . . . . . . . . . . . . . . . . . . . .
241
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
243
11. Высокоуровневые конкурентные абстракции . . . . . . . . . . . .
245
Избежание утечки потоков . . . . . . . . . . . . . . . . . . . . . . .
245
Комбинаторы симметричной конкурентности . . . . . . . . . . . .
247
Тайм-ауты с помощью race . . . . . . . . . . . . . . . . . . . .
250
Добавляем экземпляр класса Functor . . . . . . . . . . . . . . . . .
251
Итоги: интерфейс Async . . . . . . . . . . . . . . . . . . . . . . . .
253
12. Конкурентные сетевые серверы . . . . . . . . . . . . . . . . . . . .
254
Простейший сервер . . . . . . . . . . . . . . . . . . . . . . . . . . .
254
Расширяем простой сервер состоянием . . . . . . . . . . . . . . . .
259
Первое решение: одна глобальная блокировка
. . . . . . . .
259
Второе решение: один канал на серверный поток . . . . . . .
260
Третье решение: широковещательный канал
. . . . . . . . .
261
Четвёртое решение: использование STM . . . . . . . . . . . .
262
Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
263
Чат-сервер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
267
Архитектура . . . . . . . . . . . . . . . . . . . . . . . . . . . .
268


Оглавление
Данные клиента . . . . . . . . . . . . . . . . . . . . . . . . . .
Данные сервера . . . . . . . . . . . . . . . . . . . . . . . . . .
271
Сервер
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
271
Добавление нового клиента
. . . . . . . . . . . . . . . . . . .
272
Запуск клиента
. . . . . . . . . . . . . . . . . . . . . . . . . .
274
Резюме
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
276
13. Параллельное программирование на потоках . . . . . . . . . . . .
278
Как распараллелить программу посредством конкурентности . .
279
Пример: поиск файлов . . . . . . . . . . . . . . . . . . . . . . . . .
279
Последовательная версия . . . . . . . . . . . . . . . . . . . . .
280
Параллельная версия . . . . . . . . . . . . . . . . . . . . . . .
282
Производительность и масштабируемость . . . . . . . . . . .
284
Ограничение количества потоков с помощью семафора . . .
285
Монада ParIO . . . . . . . . . . . . . . . . . . . . . . . . . . .
292
14. Распределённое программирование
. . . . . . . . . . . . . . . . .
295
Семейство пакетов distributed-process
. . . . . . . . . . . . . . . .
296
Распределённая конкурентность или параллелизм?
. . . . . . . .
298
Первый пример: пинг-понг . . . . . . . . . . . . . . . . . . . . . . .
299
Процессы и монада Process
. . . . . . . . . . . . . . . . . . .
299
Определение типа сообщения
. . . . . . . . . . . . . . . . . .
300
Серверный процесс . . . . . . . . . . . . . . . . . . . . . . . .
301
Ведущий процесс
. . . . . . . . . . . . . . . . . . . . . . . . .
303
Функция main . . . . . . . . . . . . . . . . . . . . . . . . . . .
304
Итоги примера . . . . . . . . . . . . . . . . . . . . . . . . . . .
305
Пинг-понг на нескольких узлах . . . . . . . . . . . . . . . . . . . .
306
Запуск нескольких узлов на одной машине
. . . . . . . . . .
307
Запуск на нескольких машинах . . . . . . . . . . . . . . . . .
308
Типизированные каналы . . . . . . . . . . . . . . . . . . . . . . . .
309
Слияние каналов
. . . . . . . . . . . . . . . . . . . . . . . . .
313
Обработка отказов
. . . . . . . . . . . . . . . . . . . . . . . . . . .
315
Философия распределённых отказов . . . . . . . . . . . . . .
318
Распределённый чат-сервер
. . . . . . . . . . . . . . . . . . . . . .
319
Типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . .
320
Отправка сообщений
. . . . . . . . . . . . . . . . . . . . . . .
323
Широковещание . . . . . . . . . . . . . . . . . . . . . . . . . .
324
Распределение . . . . . . . . . . . . . . . . . . . . . . . . . . .
325
Тестирование сервера . . . . . . . . . . . . . . . . . . . . . . .
328
Отказы и добавление/удаление узлов
. . . . . . . . . . . . .
328
Упражнение: распределённое хранилище пар «ключ–значение» .
330


Оглавление
15. Отладка, настройка и вызов внешнего кода . . . . . . . . . . . . .
Отладка конкурентных программ . . . . . . . . . . . . . . . . . . .
334
Проверка статуса потока . . . . . . . . . . . . . . . . . . . . .
334
Запись событий в журнал и ThreadScope
. . . . . . . . . . .
335
Обнаружение тупиков
. . . . . . . . . . . . . . . . . . . . . .
338
Настройка конкурентных (и параллельных) программ
. . . . . .
341
Создание потоков и операции с MVar
. . . . . . . . . . . . .
342
Разделяемые конкурентные структуры данных . . . . . . . .
344
Настройка системы времени исполнения . . . . . . . . . . . .
346
Конкурентность и интерфейс внешних функций . . . . . . . . . .
348
Потоки и исходящие внешние вызовы
. . . . . . . . . . . . .
348
Асинхронные исключения и внешние вызовы . . . . . . . . .
351
Потоки и входящие внешние вызовы . . . . . . . . . . . . . .
351
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . .
353


Предисловие
Как один из разработчиков компилятора языка Haskell GHC (Glasgow
Haskell Compiler) на протяжении почти 15 лет я наблюдал его развитие от
нишевого, чисто исследовательского языка до богатейшей процветающей
экосистемы. Большая часть этого времени была потрачена на реализацию
поддержки параллелизма и конкурентности. Первое, что я сделал в GHC
в 1997 году, было переписывание системы времени исполнения, в то время
мы приняли ключевое решение встроить конкурентность непосредственно в ядро системы, отказавшись от её реализации в виде дополнительной
библиотеки. Мне нравится думать, что это решение основывалось на гениальном предвидении, хотя в действительности на него сильно повлияло
обнаружение нами способа снизить накладные расходы на конкурентность
почти до нуля (прежде они составляли порядка 2%; мы всегда были одержимы производительностью). Сделать конкурентность обязательной уже
означало, что она автоматически станет важнейшей частью реализации,
и я убеждён, что принятое решение поспособствовало появлению в GHC
надёжной и быстрой её поддержки.
Haskell уже давно ассоциируется с параллелизмом. Достаточно вспомнить такие проекты, как pH, вариант языка Haskell, построенный на основе специально спроектированного с поддержкой параллелизма языка Id,
система GUM, обеспечивавшая запуск параллельных программ на языке
Haskell на нескольких машинах вычислительного кластера, система GRip,
полная компьютерная архитектура, предназначенная для запуска параллельных функциональных программ. Все эти проекты имели место задолго
до распространения многоядерных процессоров и связанной с ними революции в программировании, проблема заключалась в том, что в те времена закон Мура ещё позволял получать всё более быстрые компьютеры.
Достижение параллелизма было трудной задачей, в которой не было большого смысла в условиях, когда компьютеры становились экспоненциально
быстрее.
Около 2004 года мы решили сделать параллельную реализацию си
Доступ онлайн
479 ₽
В корзину