Patterns for Parallel Programming

Chapter 4The Algorithm Structure Design Space

4.1 INTRODUCTION

4.2 CHOOSING AN ALGORITHM STRUCTURE PATTERN

4.3 EXAMPLES

4.4 THE TASK PARALLELISM PATTERN

4.5 THE DIVIDE AND CONQUER PATTERN

4.6 THE GEOMETRIC DECOMPOSITION PATTERN

4.7 THE RECURSIVE DATA PATTERN

4.8 THE PIPELINE PATTERN

4.9 THE EVENT-BASED COORDINATION PATTERN

4.1 Introduction

The first phase of designing a parallel algorithm consists of analyzing the problem to identify exploitable concurrency, usually by using the patterns of the Finding Concurrency design space. The output from the Finding Concurrency design space is a decomposition of the problem into design elements:

• A task decomposition that identifies tasks that can execute concurrently

• A data decomposition ...