Parallel and Concurrent Programming in Haskell

This book covers the breadth of Haskell's diverse selection of programming APIs for concurrent and parallel programming. It is split into two parts. The first part, on parallel programming, covers the techniques for using multiple processors to speed up CPU-intensive computations, including methods Parallel and concurrentProgramming in haskelSimon marlowORE|LLY°Beijing Cambridge. Farnham. KoIn. Sebastopol TokyoParallel and Concurrent Programming in Haskellby Simon MarlowCopyright o 2013 Simon Marlow. All rights reservedPrinted in the United States of americaPublished by o reilly media, InC., 1005 Gravenstein Highway North, Sebastopol, CA 95472OReilly books may be purchased for educational, business, or sales promotional use Online editions arealsoavailableformosttitles(http://my.safaribooksonline.com).fOrmoreinformation,contactourcorporateinstitutionalsalesdepartment800-998-9938orcorporate@oreilly.comEditors: Andy Oram and Maria GulickIndexer: Word Co Indexing ServicesProduction Editor Melanie YarbroughCover Designer: Randy comerCopyeditor: Gillian McGarveyInterior Designer: David FutatoProofreader: Julie Van Keurenstrator: Rebecca demarestJuly 2013First editionRevision History for the First Edition:2013-07-10 First releaseSeehttp://oreilly.com/catalog/errata.csp?isbn=9781449335946forreleasedetailsNutshell Handbook, the Nutshell Handbook logo, and the O Reilly logo are registered trademarks ofO ReillyMedia, Inc. Parallel and Concurrent Programming in Haskell, the image of a scrawled butterflyfish, andrelated trade dress are trademarks of o reilly media, IncMany of the designations used by manufacturers and sellers to distinguish their products are claimed astrademarks. Where those designations appear in this book, and O Reilly Media, Inc, was aware of a trademark claim, the designations have been printed in caps or initial capsWhile every precaution has been taken in the preparation of this book, the publisher and author assume noresponsibility for errors or omissions, or for damages resulting from the use of the information containedhereinISBN:978-1-449-335946Table of contentsPref1. IntroductionTerminology: Parallelism and ConcurrencyTools and resourcesSample code234Part. parallel haskell2. Basic Parallelism: The eval monadLazy Evaluation and Weak Head Normal FormThe Eval Monad, rpar, and rseq15Example: Parallelizing a Sudoku solver19Deepsea293. Evaluation Strategies31Parameterized strategies32A Strategy for Evaluating a List in Parallel34Example: The K-Means Problem35Parallelizing K-meansPerformance and analysisVisualizing Spark Activity46granularity47GCd sparks and speculative Parallelism48Parallelizing Lazy Streams with par Buffer51Chunking strategies54The Identity property4. Dataflow Parallelism: The par monadExample: ShortesthPaths in a grap6Pipeline Parallelism65Rate-Limiting the Producer68Limitations of Pipeline parallelism9Example: A Conference Timetable70Adding parallelism74Example: A Parallel Type InferencerUsing Different Schedulers82The Par Monad Compared to strategies825. Data Parallel Programming with Repa.....................8Arrays, Shapes, and Indices86Operations on arrays88Example: Computing Shortest PathsParallelizing the programFolding and Shape-Polymorphism9999Example: Image Rotation357Summary1016. GPU Programming with Accelerate鲁鲁鲁。鲁Overview104Arrays and IndiceRunning a simple accelerate computation106Scalar arrays108Indexing Arrays108Creating arrays Inside acc109Ipping Iwo Arrays111ConstantsExample: Shortest Paths112Running on the gpu115Debugging the CUDA Backend116Example: A Mandelbrot Set Generator116Part ll. Concurrent haskell7. Basic Concurrency: Threads and MVars.................... 125A Simple example: reminders126Communication: Mvars128MVar as a Simple Channel: A Logging ServiceMVar as a Container for shared State133MVar as a building block Unbounded channels135iv Table of ContentsFairness1408. Overlapping Input/Output.143Exceptions in haskell146Error Handling with Async151merging1529. Cancellation and timeoutsAsynchronous Exceptions156Masking Asynchronous Exceptions158The bracket Operation162Asynchronous Exception Safety for Channels162Timeouts164Catching Asynchronous Exceptions166mask and forkIo168Asynchronous Exceptions: Discussion17010. Software Transactional Memory.Running Example: managing windows173Blockingg177Blocking Until Something Changes179Merging with Stm181Async Revisited182Implementing Channels with STM184More Operations are possible185Composition of blocking Operations185Asynchronous Exception Safety186An Alternative Channel implementation187Bounded channels189What Can We not do with stm?191Performance193Summary19511. Higher-Level Concurrency abstractions,,197Avoiding Thread Leakage197Symmetric Concurrency Combinators199Timeouts Using race201Adding a Functor Instance202Summary: The async aPI20312. Concurrent Network Servers205A Trivial server205Table of ContentsExtending the simple server with State209Design One: One Giant Lock209Design Two: One Chan Per Server Thread210Design Three: Use a Broadcast Chan211Design Four: Use STM212The Implementation213a Chat server216Architecture217Client data217Server data218The server219Setting up a New client219Running the client222Recap22313. Parallel Programming Using Threads225How to Achieve Parallelism with Concurrency225Example: Searching for Files226Sequential version226Parallel version228Performance and Scalingng230Limiting the Number of Threads with a Semaphore231The ParIO monad23714. Distributed Programming241The Distributed-Process Family of Packages242Distributed Concurrency or Parallelism244A First Example: Pings244Processes and the process monad245Defining a message type245The Ping server Process246The master Process248The main function249Summing Up the Ping example250Multi-Node ping251Running with Multiple Nodes on One machine252Running on multiple machines253Typed Channels254Merging Channels257Handling failure258The Philosophy of Distributed failure261A Distributed chat server262ⅵi| Table of contentsData Types263Sending Messages265Broadcasting265Distribution266Testing the Server269Failure and Adding/Removing Nodes269Exercise: A Distributed Key-Value Store27115. Debugging, Tuning, and Interfacing with Foreign Code275Debugging Concurrent Programs275Inspecting the Status of a Thread275Event Logging and ThreadScope276Detecting Deadlock278Tuning Concurrent(and Parallel) Programs280Thread Creation and MVar Operations281Shared Concurrent Data Structures283RTS Options to Tweak284Concurrency and the Foreign Function Interface286Threads and Foreign Out-Calls286Asynchronous exceptions and Foreign Calls288Threads and Foreign In-calls289Index291Table of Contents