Parallel and Concurrent Programming in Haskell.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：18.22M 资料格式：pdf 举报版权申诉

wchpjx-9998204-4744302542935184111.pdf-第1页.png

第1页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第2页.png

第2页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第3页.png

第3页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第4页.png

第4页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第5页.png

第5页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第6页.png

第6页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第7页.png

第7页 / 共321页

wchpjx-9998204-4744302542935184111.pdf-第8页.png

第8页 / 共321页

Table of Contents

Preface

Audience

How to Read This Book

Conventions Used in This Book

Using Sample Code

Safari® Books Online

How to Contact Us

Acknowledgments

Chapter 1. Introduction

Terminology: Parallelism and Concurrency

Tools and Resources

Sample Code

Part I. Parallel Haskell

Chapter 2. Basic Parallelism: The Eval Monad

Lazy Evaluation and Weak Head Normal Form

The Eval Monad, rpar, and rseq

Example: Parallelizing a Sudoku Solver

Deepseq

Chapter 3. Evaluation Strategies

Parameterized Strategies

A Strategy for Evaluating a List in Parallel

Example: The K-Means Problem

Parallelizing K-Means

Performance and Analysis

Visualizing Spark Activity

Granularity

GC’d Sparks and Speculative Parallelism

Parallelizing Lazy Streams with parBuffer

Chunking Strategies

The Identity Property

Chapter 4. Dataflow Parallelism: The Par Monad

Example: Shortest Paths in a Graph

Pipeline Parallelism

Rate-Limiting the Producer

Limitations of Pipeline Parallelism

Example: A Conference Timetable

Adding Parallelism

Example: A Parallel Type Inferencer

Using Different Schedulers

The Par Monad Compared to Strategies

Chapter 5. Data Parallel Programming with Repa

Arrays, Shapes, and Indices

Operations on Arrays

Example: Computing Shortest Paths

Parallelizing the Program

Folding and Shape-Polymorphism

Example: Image Rotation

Summary

Chapter 6. GPU Programming with Accelerate

Overview

Arrays and Indices

Running a Simple Accelerate Computation

Scalar Arrays

Indexing Arrays

Creating Arrays Inside Acc

Zipping Two Arrays

Constants

Example: Shortest Paths

Running on the GPU

Debugging the CUDA Backend

Example: A Mandelbrot Set Generator

Part II. Concurrent Haskell

Chapter 7. Basic Concurrency: Threads and MVars

A Simple Example: Reminders

Communication: MVars

MVar as a Simple Channel: A Logging Service

MVar as a Container for Shared State

MVar as a Building Block: Unbounded Channels

Fairness

Chapter 8. Overlapping Input/Output

Exceptions in Haskell

Error Handling with Async

Merging

Chapter 9. Cancellation and Timeouts

Asynchronous Exceptions

Masking Asynchronous Exceptions

The bracket Operation

Asynchronous Exception Safety for Channels

Timeouts

Catching Asynchronous Exceptions

mask and forkIO

Asynchronous Exceptions: Discussion

Chapter 10. Software Transactional Memory

Running Example: Managing Windows

Blocking

Blocking Until Something Changes

Merging with STM

Async Revisited

Implementing Channels with STM

More Operations Are Possible

Composition of Blocking Operations

Asynchronous Exception Safety

An Alternative Channel Implementation

Bounded Channels

What Can We Not Do with STM?

Performance

Summary

Chapter 11. Higher-Level Concurrency Abstractions

Avoiding Thread Leakage

Symmetric Concurrency Combinators

Timeouts Using race

Adding a Functor Instance

Summary: The Async API

Chapter 12. Concurrent Network Servers

A Trivial Server

Extending the Simple Server with State

Design One: One Giant Lock

Design Two: One Chan Per Server Thread

Design Three: Use a Broadcast Chan

Design Four: Use STM

The Implementation

A Chat Server

Architecture

Client Data

Server Data

The Server

Setting Up a New Client

Running the Client

Recap

Chapter 13. Parallel Programming Using Threads

How to Achieve Parallelism with Concurrency

Example: Searching for Files

Sequential Version

Parallel Version

Performance and Scaling

Limiting the Number of Threads with a Semaphore

The ParIO monad

Chapter 14. Distributed Programming

The Distributed-Process Family of Packages

Distributed Concurrency or Parallelism?

A First Example: Pings

Processes and the Process Monad

Defining a Message Type

The Ping Server Process

The Master Process

The main Function

Summing Up the Ping Example

Multi-Node Ping

Running with Multiple Nodes on One Machine

Running on Multiple Machines

Typed Channels

Merging Channels

Handling Failure

The Philosophy of Distributed Failure

A Distributed Chat Server

Data Types

Sending Messages

Broadcasting

Distribution

Testing the Server

Failure and Adding/Removing Nodes

Exercise: A Distributed Key-Value Store

Chapter 15. Debugging, Tuning, and Interfacing with Foreign Code

Debugging Concurrent Programs

Inspecting the Status of a Thread

Event Logging and ThreadScope

Detecting Deadlock

Tuning Concurrent (and Parallel) Programs

Thread Creation and MVar Operations

Shared Concurrent Data Structures

RTS Options to Tweak

Concurrency and the Foreign Function Interface

Threads and Foreign Out-Calls

Asynchronous Exceptions and Foreign Calls

Threads and Foreign In-Calls

Index

About the Author

Parallel and Concurrent Programming in Haskell Simon Marlow

Parallel and Concurrent Programming in Haskell by Simon Marlow Copyright © 2013 Simon Marlow. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://my.safaribooksonline.com). For more information, contact our corporate/ institutional sales department: 800-998-9938 or corporate@oreilly.com. Editors: Andy Oram and Maria Gulick Production Editor: Melanie Yarbrough Copyeditor: Gillian McGarvey Proofreader: Julie Van Keuren Indexer: WordCo Indexing Services Cover Designer: Randy Comer Interior Designer: David Futato Illustrator: Rebecca Demarest July 2013: First Edition Revision History for the First Edition: 2013-07-10: First release See http://oreilly.com/catalog/errata.csp?isbn=9781449335946 for release details. Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarks of O’Reilly Media, Inc. Parallel and Concurrent Programming in Haskell, the image of a scrawled butterflyfish, and related trade dress are trademarks of O’Reilly Media, Inc. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and O’Reilly Media, Inc., was aware of a trade‐ mark claim, the designations have been printed in caps or initial caps. While every precaution has been taken in the preparation of this book, the publisher and author assume no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein. ISBN: 978-1-449-33594-6 [LSI]

Table of Contents Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Terminology: Parallelism and Concurrency 2 Tools and Resources 3 Sample Code 4 Part I. Parallel Haskell 2. Basic Parallelism: The Eval Monad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Lazy Evaluation and Weak Head Normal Form 9 The Eval Monad, rpar, and rseq 15 Example: Parallelizing a Sudoku Solver 19 Deepseq 29 3. Evaluation Strategies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Parameterized Strategies 32 A Strategy for Evaluating a List in Parallel 34 Example: The K-Means Problem 35 Parallelizing K-Means 40 Performance and Analysis 42 Visualizing Spark Activity 46 Granularity 47 GC’d Sparks and Speculative Parallelism 48 Parallelizing Lazy Streams with parBuffer 51 Chunking Strategies 54 The Identity Property 55 4. Dataflow Parallelism: The Par Monad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 iii

Example: Shortest Paths in a Graph 61 Pipeline Parallelism 65 Rate-Limiting the Producer 68 Limitations of Pipeline Parallelism 69 Example: A Conference Timetable 70 Adding Parallelism 74 Example: A Parallel Type Inferencer 77 Using Different Schedulers 82 The Par Monad Compared to Strategies 82 5. Data Parallel Programming with Repa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Arrays, Shapes, and Indices 86 Operations on Arrays 88 Example: Computing Shortest Paths 90 Parallelizing the Program 93 Folding and Shape-Polymorphism 95 Example: Image Rotation 97 Summary 101 6. GPU Programming with Accelerate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Overview 104 Arrays and Indices 105 Running a Simple Accelerate Computation 106 Scalar Arrays 108 Indexing Arrays 108 Creating Arrays Inside Acc 109 Zipping Two Arrays 111 Constants 111 Example: Shortest Paths 112 Running on the GPU 115 Debugging the CUDA Backend 116 Example: A Mandelbrot Set Generator 116 Part II. Concurrent Haskell 7. Basic Concurrency: Threads and MVars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 A Simple Example: Reminders 126 Communication: MVars 128 MVar as a Simple Channel: A Logging Service 130 MVar as a Container for Shared State 133 MVar as a Building Block: Unbounded Channels 135 iv | Table of Contents

Fairness 140 8. Overlapping Input/Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Exceptions in Haskell 146 Error Handling with Async 151 Merging 152 9. Cancellation and Timeouts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Asynchronous Exceptions 156 Masking Asynchronous Exceptions 158 The bracket Operation 162 Asynchronous Exception Safety for Channels 162 Timeouts 164 Catching Asynchronous Exceptions 166 mask and forkIO 168 Asynchronous Exceptions: Discussion 170 10. Software Transactional Memory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Running Example: Managing Windows 173 Blocking 177 Blocking Until Something Changes 179 Merging with STM 181 Async Revisited 182 Implementing Channels with STM 184 More Operations Are Possible 185 Composition of Blocking Operations 185 Asynchronous Exception Safety 186 An Alternative Channel Implementation 187 Bounded Channels 189 What Can We Not Do with STM? 191 Performance 193 Summary 195 11. Higher-Level Concurrency Abstractions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Avoiding Thread Leakage 197 Symmetric Concurrency Combinators 199 Timeouts Using race 201 Adding a Functor Instance 202 Summary: The Async API 203 12. Concurrent Network Servers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 A Trivial Server 205 Table of Contents | v

Extending the Simple Server with State 209 Design One: One Giant Lock 209 Design Two: One Chan Per Server Thread 210 Design Three: Use a Broadcast Chan 211 Design Four: Use STM 212 The Implementation 213 A Chat Server 216 Architecture 217 Client Data 217 Server Data 218 The Server 219 Setting Up a New Client 219 Running the Client 222 Recap 223 13. Parallel Programming Using Threads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 How to Achieve Parallelism with Concurrency 225 Example: Searching for Files 226 Sequential Version 226 Parallel Version 228 Performance and Scaling 230 Limiting the Number of Threads with a Semaphore 231 The ParIO monad 237 14. Distributed Programming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 The Distributed-Process Family of Packages 242 Distributed Concurrency or Parallelism? 244 A First Example: Pings 244 Processes and the Process Monad 245 Defining a Message Type 245 The Ping Server Process 246 The Master Process 248 The main Function 249 Summing Up the Ping Example 250 Multi-Node Ping 251 Running with Multiple Nodes on One Machine 252 Running on Multiple Machines 253 Typed Channels 254 Merging Channels 257 Handling Failure 258 The Philosophy of Distributed Failure 261 A Distributed Chat Server 262 vi | Table of Contents

Data Types 263 Sending Messages 265 Broadcasting 265 Distribution 266 Testing the Server 269 Failure and Adding/Removing Nodes 269 Exercise: A Distributed Key-Value Store 271 15. Debugging, Tuning, and Interfacing with Foreign Code. . . . . . . . . . . . . . . . . . . . . . . . . 275 Debugging Concurrent Programs 275 Inspecting the Status of a Thread 275 Event Logging and ThreadScope 276 Detecting Deadlock 278 Tuning Concurrent (and Parallel) Programs 280 Thread Creation and MVar Operations 281 Shared Concurrent Data Structures 283 RTS Options to Tweak 284 Concurrency and the Foreign Function Interface 286 Threads and Foreign Out-Calls 286 Asynchronous Exceptions and Foreign Calls 288 Threads and Foreign In-Calls 289 Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Table of Contents | vii

分享到：

赞收藏

资料库

Parallel and Concurrent Programming in Haskell.pdf

相关推荐

开发技术

热门标签

最新资料