4. Parallel Computing 14. Introduction

Figure 298: Parallel mapping a function over a list for independent execution.

Each copy of f can be simultaneously executing.

Exercises

Which of the following programs can exploit parallelism for improved performance over

sequential execution? Informally describe how.

1 •• finding the maximum element in an array

---

592

Parallel Computing

2 •• finding an element in a sorted array

3 •• merge sort

4 •• insertion sort

5 •• Quicksort

6 ••• finding a maximum in a uni-modal array (an array in which the elements are

increasing up to a point, then decreasing)

7 •• finding the inner-product of two vectors

8 •• multiplying two matrices