Algorithm Design: Parallel and Sequential PDF

Preview

Summary

Algorithm Design: Parallel and Sequential September 2016 2 October 2, 2016 (DRAFT, PPAP) Contents I Introduction and Preliminaries 1 1 Introduction 3 1.1 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Work and Span . . . . . . . . . . . . . . . . . . . . . ...

Description

Accelerat ing t he world's research.

Algorithm Design: Parallel and Sequential Xiuquan Lv

Related papers A Shubham Gupt a

Download a PDF Pack of t he best relat ed papers 

Algorithm Design: Parallel and Sequential

September 2016

2

October 2, 2016 (DRAFT, PPAP)

Contents I

Introduction and Preliminaries

1

1

Introduction

3

1.1

Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Work and Span . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3

Specification, Problem, Implementation . . . . . . . . . . . . . . . . . . .

9

1.4

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2

3

Mathematical Preliminaries

15

2.1

Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2

Relations and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3

Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3.1

Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3.2

Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.3.3

Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.3.4

Connectivity and Connected Components . . . . . . . . . . . . .

22

2.3.5

Graph Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.3.6

Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

SPARC: A Strict Language for Parallel Computing

27

3.1

Functional Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2

The SPARC Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2.1

Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2.2

Type System of SPARC . . . . . . . . . . . . . . . . . . . . . . . . .

41

3

4

CONTENTS

II Fundamentals

43

4

Algorithm Design and Analysis

45

4.1

Asymptotic Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.2

Cost Models: Machine and Language Based . . . . . . . . . . . . . . . . .

48

4.2.1

The RAM Model for Sequential Computation . . . . . . . . . . .

50

4.2.2

The Parallel RAM Model . . . . . . . . . . . . . . . . . . . . . . .

51

4.2.3

The Work-Span Model . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.2.4

Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Design Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

4.3.1

Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

4.3.2

Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4.3.3

Inductive Techniques . . . . . . . . . . . . . . . . . . . . . . . . . .

62

4.3.4

Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

4.4

Cost Analysis with Recurrences . . . . . . . . . . . . . . . . . . . . . . . .

66

4.5

What makes a good solution? . . . . . . . . . . . . . . . . . . . . . . . . .

71

4.6

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

4.3

5

6

Example: Genome Sequencing

77

5.1

The Shotgun Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

5.2

Defining the Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

5.3

Brute-Force Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

5.4

Understanding the Structure of the Problem . . . . . . . . . . . . . . . . .

81

5.5

Brute Force Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.6

Reduction to the Traveling-Salesperson Problem . . . . . . . . . . . . . .

85

5.7

Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

5.8

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

Sequences

95

6.1

Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

6.2

The Sequence Abstract Data Type

97

October 2, 2016 (DRAFT, PPAP)

. . . . . . . . . . . . . . . . . . . . . .

CONTENTS

7

8

6.3

Sequence Comprehensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.4

Cost Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.4.1

Array Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.4.2

Tree Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.4.3

List Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.5

An Example: Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

6.6

Single-Threaded Array Sequences . . . . . . . . . . . . . . . . . . . . . . 129

6.7

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Algorithm-Design Technique: Contraction

135

7.1

Example 1: Implementing Reduce with Contraction . . . . . . . . . . . . 136

7.2

Example 2: Implementing Scan with Contraction . . . . . . . . . . . . . . 137

7.3

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Divide and Conquer

143

8.1

Example I: Sequence Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . 144

8.2

Example II: MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

8.3

Example III: Sequence Scan . . . . . . . . . . . . . . . . . . . . . . . . . . 146

8.4

Example IV: Euclidean Traveling Salesperson Problem . . . . . . . . . . 147

8.5

Strengthening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 8.5.1

8.6 9

5

Divide and Conquer with Reduce . . . . . . . . . . . . . . . . . . 151

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

Maximum Contiguous Subsequences

155

9.1

The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

9.2

Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

9.3

Brute Force Refined with a Reduction . . . . . . . . . . . . . . . . . . . . 158

9.4

Reduction and Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

9.5

Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

9.6

Divide And Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

9.7

Divide And Conquer with Strengthening . . . . . . . . . . . . . . . . . . 168

October 2, 2016 (DRAFT, PPAP)

6

III

CONTENTS

Randomization

10 Probability Theory

173 175

10.1 Probabilistic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 10.2 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 10.3 Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 10.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11 Randomized Algorithms

197

11.1 Expectation versus High Probability . . . . . . . . . . . . . . . . . . . . . 198 11.2 Finding The Two Largest . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 11.3 Order statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 11.4 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12 Binary Search Trees

219

12.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 12.2 The BST Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.3 Implementation via Balancing . . . . . . . . . . . . . . . . . . . . . . . . . 224 12.4 A Parametric Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 226 12.5 Cost Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 12.6 Treaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 12.7 Augmenting Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 12.7.1 Augmenting with Key-Value Pairs . . . . . . . . . . . . . . . . . . 239 12.7.2 Augmenting with Size . . . . . . . . . . . . . . . . . . . . . . . . . 240 12.7.3 Augmenting with Reduced Values . . . . . . . . . . . . . . . . . . 241 12.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 13 Sets and Tables

247

13.1 Sets: Interface and Specification . . . . . . . . . . . . . . . . . . . . . . . . 248 13.2 Cost Specification for Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 13.3 Tables: Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 October 2, 2016 (DRAFT, PPAP)

CONTENTS

7

13.4 Cost Specification for Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 259 13.5 Example: Indexing and Searching a Collection . . . . . . . . . . . . . . . 260 13.6 Ordered Sets and Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 13.7 Ordered Tables with Augmented with Reducers . . . . . . . . . . . . . . 267 13.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

IV

Graphs

14 Graphs and their Representation

273 275

14.1 Graphs and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 14.2 Representing Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 14.2.1 Traditional Representations for Graphs . . . . . . . . . . . . . . . 280 14.3 Weighted Graphs and Their Representation . . . . . . . . . . . . . . . . . 281 14.4 Applications of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 15 Graph Search 15.1 Breadth-First Search (BFS)

287 . . . . . . . . . . . . . . . . . . . . . . . . . . 289

15.2 Shortest Paths and Shortest-Path Trees . . . . . . . . . . . . . . . . . . . . 292 15.3 Cost of BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 15.4 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 15.5 DFS Numbers and the DFS Tree . . . . . . . . . . . . . . . . . . . . . . . . 302 15.6 Applications of DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 15.7 Cost of DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 15.8 Priority-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 16 Shortest Paths

315

16.1 Shortest Weighted Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 16.2 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 16.2.1 Implementing Dijkstra’s Algorithm with a Priority Queue . . . . 321 16.3 The Bellman Ford Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 325 16.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 October 2, 2016 (DRAFT, PPAP)

8

CONTENTS

17 Graph Contraction and Connectivity

333

17.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 17.2 Graph Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 17.2.1 Edge Partitioning and Edge Contraction . . . . . . . . . . . . . . . 336 17.2.2 Star Partitioning and Star Contraction . . . . . . . . . . . . . . . . 341 17.3 Connectivity via Graph Contraction . . . . . . . . . . . . . . . . . . . . . 346 17.4 Tree Contraction and Tree Partitioning . . . . . . . . . . . . . . . . . . . . 351 17.5 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 18 Minimum Spanning Trees

355

18.1 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 18.2 Algorithms for Minimum Spanning Trees . . . . . . . . . . . . . . . . . . 357 18.2.1 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 359 18.2.2 Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 ˚ 18.2.3 Boruvka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 362 18.3 Minimum Spanning Trees and the Travel Salesperson Problem

. . . . . 367

18.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

V Parallelism in Practice 19 Dynamic Programming

373 375

19.1 Subset Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 19.2 Minimum Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 19.3 Top-Down Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . 387 19.4 Bottom-Up Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . 390 19.5 Optimal Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 391 19.6 Coding optimal BST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 19.7 Problems with Efficient Dynamic Programming Solutions . . . . . . . . . 396 20 Hashing

399

20.1 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 October 2, 2016 (DRAFT, PPAP)

CONTENTS

9

20.2 Separate Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 20.3 Open Address Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 404 20.3.1 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 20.3.2 Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 20.3.3 Double Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 20.4 Hash Table Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 20.5 Parallel Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 20.6 Comparison to Tree Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 21 Priority Queues

415

21.1 Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 21.2 Meldable Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 21.3 Leftist Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 21.4 Summary of Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . 425 A Algorithm-Design Technique: Partitioning

427

A.1 Example 1: Partitioning into Two . . . . . . . . . . . . . . . . . . . . . . . 428 A.2 Example 2: Partitioning into Many . . . . . . . . . . . . . . . . . . . . . . 429 A.3 Example 3: Partitioning into Not as Many . . . . . . . . . . . . . . . . . . 430

October 2, 2016 (DRAFT, PPAP)

10

October 2, 2016 (DRAFT, PPAP)

CONTENTS

Part I Introduction and Preliminaries

1

Chapter 1 Introduction parallel The topic of this book might best be described as problem solving with computers. ∧

The idea is you have some problem to solve (e.g. finding the shortest path from your room to your first class), and you want to use your computer to solve it for you. Your primarily concern is probably that your answer is correct (e.g. you would likely be unhappy to find yourself at the wrong class). However, you also care that you can get the answer reasonably quickly (e.g. it would not be useful if your computer had to think about it until next semester). This book is therefore about different aspects of problem solving with computers. It is about defining precisely the problem you want to solve. It is about learning the different techniques that can be used to solve such a problem, and about designing algorithms using these techniques. It is about designing abstract data types that can be used in these algorithms, and data structures that implement these types. And, it is about analyzing the cost of those algorithms and comparing them based on their cost. Unlike traditional books on algorithms and data structures, which are concerned with sequential algorithms (ones that are correct and efficient on sequential computers), in this book we are concerned with parallel algorithms (ones that are correct and efficient on parallel computers). However, in the approach we take in this book , sequential and parallel algorithms are not that different. Indeed the book covers most of what is covered in a traditional sequential algorithms course. In the rest of this chapter we discuss why it is important to study parallelism, why it is important to separate interfaces from implementations, and outline some algorithm-design techniques.

1.1

Parallelism

The term “parallelism” or “parallel computing” refers the ability to run multiple computations (tasks) at the same time. 3

4

CHAPTER 1. INTRODUCTION

Parallel systems. Over the past several decades, the computer scientists have developed many different forms of parallel systems. On the one hand, hardware manufacturers have developed multicore chips that contain multiple processors on the same chip, allowing the processors to communicate quickly and efficiently. Today such chips contain anywhere from a couple of processors to as many as couple of dozens. We refer to the form of parallelism that arises in such multicore chips as, small-scale parallelism, as it involves smaller numbers of processors packed into a relatively small area. While multicore chips were initially used only in laptops and desktops and servers, they are now used in almost all smaller mobile devices such as phones (ma...