16.1 Introduction

In this chapter we show how to decompose certain kinds of problems into components that can be executed in parallel. Some applications break down naturally into parallel threads. For example, when a request arrives at a web server, the server can just create a thread (or assign an existing thread) to handle the request. Applications that can be structured as producers and consumers also tend to be easily parallelizable. In this chapter, however, we look at applications that have inherent parallelism, but where it is not obvious how to take advantage of it. Let us start by thinking about how to multiply two matrices in parallel. Recall that if a ^ij is the value at position (i,j) of matrix A, then the product C of two n n matrices A and B is given by:

As a first step, we could put one thread in charge of computing each c _ij. Fig. 16.1 shows a matrix multiplication program that creates an n x n array of Worker threads (Fig. 16.2), where the worker thread in position (i,j) computes c _ij. The program starts each task, and waits for them all to finish. ^[1]

In principle, this might seem like an ideal design. The program is highly parallel, and the threads do not even have to synchronize. In practice, however, while this design might perform well for small matrices, it would perform very poorly...