Final Project Write-up, Part 1: The Problem

1. What problem are you addressing?

We address the problem of automatically splitting up a sequential program into components that can be run in parallel.

2. Why this problem is hard.

We can give two reasons for why it is difficult to convert sequential programs into parallel programs. First, focus shifts from the natural algorithm for solving a problem to how to get the parallel algorithm. It may be difficult to force parallism into the abstractions used to solve the problem. Second, the implementation may require a lot of overhead. A programmer would have to deal with constructs for parallelism, such as threads and mutexes, and the issues that arise with them, such as when to join threads or lock mutexes.

3. Why this problem is worth solving.

People have come to expect processor performance to increase exponentially each year, in other words, to follow Moore's Law. However, because processors are beginning to reach the power wall, where the doubling of the power required for doubling performance is the limiting factor, the trend in processor design is to parallize. That is, multiple slow processors working in parallel are used rather than a single fast processor.

However, unlike the case when writing sequential programs, the hardware currently cannot be abstracted away for programmers writing parallel programs. Thus, taking advantage of the benefits of parallism is hard for programmers. If converting sequential programs into parallel programs can be done automatically, programmers will be free to concentrate on solving problems with high-level thinking rather than be bogged down by the low-level details of managing threads. Such code would be easier to maintain, especially when it is adapted to new requirements.