Algorithms and Parallel Computing

8.1 INTRODUCTION

We discussed in Chapter 1 that algorithms can be classified broadly as

1. serial algorithms,

2. parallel algorithms,

3. serial–parallel algorithms (SPAs),

4. nonserial–parallel algorithms (NSPAs), and

5. regular iterative algorithms (RIAs).

This chapter discusses how to extract parallelism from NSPAs so we can implement them on parallel computer platforms. Serial, parallel, and SPAs are all relatively simple to implement on parallel computer platforms. Chapters 9–11 are all dedicated to the software and hardware implementations of RIAs. That leaves NSPA as an interesting problem that requires a formal technique to deal with them.

Chapter 1 mentioned that an NSPA can contain cycles or can be cycle free. NSPAs can be represented by its associated directed graph (DG) or its associated adjacency matrix A. When the DG contains no cycles, we get what is called directed acyclic graph (DAG). When a cycle is present or detected in the NSPA, we have a directed cyclic graph (DCG). A DCG operates on a different principle compared to other algorithms.