parallel programming with microsoft visual studio 2010 step by step

www.it-ebooks.info

www.it-ebooks.info

Parallel Programming with

Microsoft®

Visual Studio®

2010 Step by Step

Donis Marshall

www.it-ebooks.info

Published with the authorization of Microsoft Corporation by:

O’Reilly Media, Inc.

1005 Gravenstein Highway North

Sebastopol, California 95472

Copyright © 2011 by Donis Marshall

All rights reserved. No part of the contents of this book may be reproduced or transmitted in any form

or by any means without the written permission of the publisher.

ISBN: 978-0-7356-4060-3

1 2 3 4 5 6 7 8 9 QG 6 5 4 3 2 1

Printed and bound in the United States of America.

Microsoft Press books are available through booksellers and distributors worldwide. If you need support

related to this book, email Microsoft Press Book Support at [email protected]. Please tell us

what you think of this book at http://www.microsoft.com/learning/booksurvey.

Microsoft and the trademarks listed at http://www.microsoft.com/about/legal/en/us/

IntellectualProperty/Trademarks/EN-US.aspx are trademarks of the Microsoft group of companies.

All other marks are property of their respective owners.

The example companies, organizations, products, domain names, email addresses, logos, people,

places, and events depicted herein are fictitious. No association with any real company, organization,

product, domain name, email address, logo, person, place, or event is intended or should be inferred.

This book expresses the author’s views and opinions. The information contained in this book is provided

without any express, statutory, or implied warranties. Neither the authors, O’Reilly Media, Inc., Microsoft

Corporation, nor its resellers, or distributors will be held liable for any damages caused or alleged to

be caused either directly or indirectly by this book.

Acquisitions and Developmental Editors: Russell Jones and Devon Musgrave

Production Editor: Holly Bauer

Editorial Production: Online Training Solutions, Inc.

Technical Reviewer: Ashish Ghoda

Copyeditor: Kathy Krause, Online Training Solutions, Inc.

Proofreader: Jaime Odell, Online Training Solutions, Inc.

Indexer: Fred Brown

Cover Design: Twist Creative • Seattle

Cover Composition: Karen Montgomery

Illustrator: Jeanne Craver, Online Training Solutions, Inc.

www.it-ebooks.info

This book is dedicated to my mother, who is extremely proud that I am a published author.

She even gives my books to friends at her church—even though none of them are programmers.

But that does not matter. Thanks, Mom!

www.it-ebooks.info

www.it-ebooks.info

v

Contents at a Glance

1 Introduction to Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . 1

2 Task Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Data Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4 PLINQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5 Concurrent Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6 Customization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7 Reports and Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

www.it-ebooks.info

www.it-ebooks.info

vii

Table of Contents

Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

1 Introduction to Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . 1

Multicore Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Multiple Instruction Streams/Multiple Data Streams . . . . . . . . . . . . . . . 3

Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Speedup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Amdahl’s Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Gustafson’s Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Software Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

The Finding Concurrency Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

The Algorithm Structure Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

The Supporting Structures Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Task Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Introduction to Parallel Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

The Task Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Using Function Delegates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Unhandled Exceptions in Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Sort Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Pivot Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Using the Barrier Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Refactoring the Pivot Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

What do you think of this book? We want to hear from you!

Microsoft is interested in hearing your feedback so we can continually improve our

books and learning resources for you. To participate in a brief online survey, please visit:

microsoft.com/learning/booksurvey

www.it-ebooks.info

viii Table of Contents

Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Task Relationships . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Continuation Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Parent and Child Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

The Work-Stealing Queue..................................... 54

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3 Data Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Unrolling Sequential Loops into Parallel Tasks . . . . . . . . . . . . . . . . . . . . . . . 60

Evaluating Performance Considerations . . . . . . . . . . . . . . . . . . . . . . . . 63

The Parallel For Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Interrupting a Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Handling Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Dealing with Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Using the MapReduce Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

A Word Count Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4 PLINQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Introduction to LINQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

PLINQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

PLINQ Operators and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

The ForAll Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

ParallelExecutionMode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

WithMergeOptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

AsSequential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

AsOrdered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

WithDegreeOfParallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Handling Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Using MapReduce with PLINQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

www.it-ebooks.info

Table of Contents ix

5 Concurrent Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Concepts of Concurrent Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Producer-Consumers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Lower-Level Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

SpinLock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

SpinWait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

ConcurrentStack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

ConcurrentQueue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

ConcurrentBag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

ConcurrentDictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

BlockingCollection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

6 Customization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

Identifying Opportunities for Customization . . . . . . . . . . . . . . . . . . . . . . . 147

Custom Producer-Consumer Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

Task Partitioners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

Advanced Custom Partitioners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Using Partitioner<TSource> . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Using OrderablePartitioner<TSource> . . . . . . . . . . . . . . . . . . . . . . . . . 168

Custom Schedulers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

The Context Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

The Task Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

7 Reports and Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Debugging with Visual Studio 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Live Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Performing Post-Mortem Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Debugging Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Using the Parallel Tasks Window . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Using the Parallel Stacks Window . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

The Threads View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

The Tasks View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

www.it-ebooks.info

x Table of Contents

Using the Concurrency Visualizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

CPU Utilization View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

The Threads View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

The Cores View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

The Sample Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

What do you think of this book? We want to hear from you!

Microsoft is interested in hearing your feedback so we can continually improve our

books and learning resources for you. To participate in a brief online survey, please visit:

microsoft.com/learning/booksurvey

www.it-ebooks.info

Foreword

It started with the hardware, tubes, and wires that didn’t do anything overtly exciting. Then

software gave hardware the capability to do things—exciting, wonderful, confounding

things. My first software program was written to wait in queue for a moment of attention

from the one computer in school, after it finished the payroll, scheduling, and grading for the

entire school system. That same year, personal computing was born, putting affordable com￾putational capabilities—previously the purview of academia, banks, and governments—in

businesses and homes. A whole new world, and later a career, was revealed to me one deli￾cious line of code at a time, no waiting required. As soon as a program was written, I could

celebrate the outcome. So another program was written, then another, and another.

We learn linear solutions to math problems early in life, so the sequencing concept of

“do this, then that” is the zeitgeist of programmers worldwide. Because computers no

longer share the same computational bias of the human brain, bridging the gap between

linear, sequential programming to a design that leverages parallel processing requires new

approaches. In order to produce fast, secure, reliable, world-ready software, programmers

need new tools to supplement their current approach. To that end, Parallel Programming

with Microsoft Visual Studio 2010 Step by Step was written.

Donis Marshall has put together his expertise with a narrative format that provides a mix of

foundational knowledge and practical decision-making criteria for unleashing the capabilities

of parallel programming. Building on the backdrop of six previous programming titles, real￾world experience in a wide range of industries, and the authorship of dozens of programming

courses, Donis provides foundational knowledge to developers new to parallel programming

concepts. The Step by Step format, combined with Donis’s information-dissemination style,

provides continual value to readers as they grow in experience and capability.

The world of parallel programming is being brought to the desktop of every developer who

has the desire to more fully utilize the architectures of modern computers (in all forms).

Standing on the shoulders of giants, the Microsoft .NET Framework 4 continues its tradition

of systematically providing new capabilities to developers and system engineers. These new

tools provide great capabilities and a great challenge for how and where to best use them.

Parallel Programming with Microsoft Visual Studio 2010 Step by Step ensures that program￾mers worldwide can effectively add parallel programming to their design portfolios.

Tracy Monteith

www.it-ebooks.info

www.it-ebooks.info

xiii

Introduction

Parallel programming truly redefines the programming model for multicore architecture,

which has become commonplace. For this reason, parallel programming has been elevated to

a core technology in the Microsoft .NET Framework 4. In this version of the .NET Framework,

the Task Parallel Library (TPL) and the System.Threading.Tasks namespace contain the parallel

programming implementation. Microsoft Visual Studio 2010 has also been enhanced and now

includes several features to aid in creating and maintaining parallel applications. If you are a

Microsoft developer looking to decompose your application into parallel tasks that execute

over separate processor cores, then Visual Studio 2010 and the TPL are the tools you need.

Parallel Programming with Microsoft Visual Studio 2010 Step by Step provides an orga￾nized walkthrough of using Visual Studio 2010 to create parallel applications. It discusses

the TPL and parallel programming concepts in considerable detail; however, this book is still

introductory—it covers the basics of each realm of parallel programming, such as task and

data parallelism. Although the book does not provide exhaustive coverage of every paral￾lel programming topic, it does offer essential guidance in using the concepts of parallel

programming.

In addition to its coverage of core parallel programming concepts, the book discusses con￾current collections and thread synchronization, and it guides you in maintaining and debug￾ging parallel applications by using Visual Studio. Beyond the explanatory content, most

chapters include step-by-step examples and downloadable sample projects that you can

explore for yourself.

Who Should Read This Book

This book exists to help Microsoft Visual Basic and Microsoft Visual C# developers under￾stand the core concepts of parallel programming and related technologies. It is especially

useful for programmers looking to take advantage of multicore architecture, which is

the current trend in the industry. Readers should have a basic familiarity with the .NET

Framework but do not have to have any prior experience with parallel programming. The

book is also useful for those already familiar with the basics of parallel programming who

are interested in the newest features of the TPL.

www.it-ebooks.info