Параллельное и конкурентное программирование на языке Haskell
Покупка
Новинка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Марлоу Саймон
Перевод:
Брагилевский Виталий Николаевич
Год издания: 2017
Кол-во страниц: 373
Возрастное ограничение: 12+
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Дополнительное профессиональное образование
ISBN: 978-5-97060-560-8
Артикул: 487676.03.99
Если вы уже владеете программированием на языке Haskell, эта книга научит вас использованию множества интерфейсов и библиотек, предназначенных для написания параллельных и конкурентных программ. Вы узнаете, как распараллеливание на многоядерные процессоры позволяет ускорять вычислительно нагруженные программы и как конкурентность облегчает написание программ с активно взаимодействующими между собой и с другими программами потоками.
Автор Саймон Марлоу проведёт вас по этому пути, сопровождая его большим количеством примеров, с которыми можно самостоятельно экспериментировать, запуская, изменяя и расширяя. Книга делится на две части, посвящённые таким инструментам, как Parallel Haskell и Concurrent Haskell, включённые в неё упражнения позволят вам научиться:
• выражать параллелизм в языке Haskell средствами монады Eval и стратегий вычислений;
• распараллеливать обычный код на языке Haskell в монаде Par;
• организовывать параллельные вычисления с массивами на основе библиотеки Repa;
• использовать библиотеку Accelerate для запуска вычислений на графических процессорах;
• работать с базовыми интерфейсами для написания конкурентного кода;
• реализовывать высокопроизводительные конкурентные сетевые серверы;
• писать распределённые программы, запускающиеся на множестве машин сети.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Саймон Марлоу Параллельное и конкурентное программирование на языке 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 года мы решили сделать параллельную реализацию си