1. What problem are you addressing?
We will address the problem of automatically converting sequential programs into parallel programs.
We will address two ways to achieve this. First, we will create a tool that will analyze an abstract syntax tree (AST) generated from code written in the 164 langauge to generate a structure where parts of it could be run in parallel by a hypothetical interpreter. (The actual interpreter written to simulate this hypothetical interpreter will, of course, be sequential.) The basic idea in the analysis is to create a directed acyclical graph (DAG) to describe how statements that perform read operations are dependent on statements that perform write operations. The interpreter will then run the program by traversing this DAG starting from all its source nodes. Thus, the first technique creates a structure that defines how the program is parallelized before it is given to the interpreter.
In contrast, the second technique parallelizes the program while it is interpreted. This will, like the first technique, require analysis of the AST before it is given to the interpreter, but the structure for parallelizing the procedure will not be explicit. In particular, consider a function that makes two recursive calls to itself, as merge sort does. Although there is no way to explicitly generate the tree structure this algorithm represents at compile time without knowing what the input is, what can be determined is that the two recursive calls can be done concurrently.
Thus, the first technique is suited for parallelizing sequences of statements while the second is suited for parallelizing recursive procedures.
However, it is debatable whether these two techniques are actually the same technique. What ultimately matters is the dependences of the read operations on the completion of write operations, as the first technique addresses. Therefore, given the first technique, the second technique may come for free. In fact, the first technique may be required for the second technique to work.
Instance of the problem: Parallelizing the merging of the results of two computations (first technique).
Consider the following pseudocode:
# Read set: {}
# Written set: {a}
def a = compute1()
# Read set: {}
# Written set: {b}
def b = compute2()
# Read set: {a, b}
# Written set: {c}
def c = combine(a, b)
The first two lines can be parallized, but doing so using pthreads would require overhead that will obsfucate this code. Instead, a DAG where an arc is drawn to a statement that reads a variable from the last statement that wrote to the variable reviews how this code can be parallized (see the following figure).
2. Argue why this problem is hard.
We can give two reasons for why is 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 algorithm to be parallel. 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. Argue 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.
No comments:
Post a Comment