Reminder: Your problem statements are due today.
Now that we have created a model of the steady state heat flow problem
using the finite difference approximation, and discussed various models
of both machine architecture as well as parallel programming, we are
ready to talk about which of these models are most appropriate for
our problem.
Granularity: It is easy to see that we are dividing up the
original problem into many small tasks-we are talking about thousands
of grid points, each of which compute local temperature based on their
neighbors. Each of these smaller tasks requires a small amount of
computational power (each grid point computes an average of its four
nearest neighbors). Thus, based on our discussion on granularity,
this problem exploits parallelism on a fine level.
Machine model: Notice that at each grid point, we are
carrying out the same computation-each point exchanges current
temperatures with it's neighbors, and updates its temperature by computing
an average. This makes this kind of computation ideal for implementation
on an SIMD machine, where the computations occur in lockstep. One grid
point is mapped onto one processor, and each processor executes the
same instructions synchronously (under the command of a controller).
Parallel Programming model: As was discussed earlier, the
data parallel programming model is best suited for SIMD machines.
The above are of course ideal choices. Often times, we will not have
the right number of processors available in our SIMD machine, or we
might not even have an SIMD machine available to us. In such
real-life situations, we have to optimally map our ideal situation to
the real situation. We will discuss how to go about doing this later
in the course.
Method
Now that we have chosen the best machine and programming model to
implement our solution, we are ready to design and theoretically
analyze the method we will use to solve the problem.
To provide you with the basic skills to analyze your solution
design, we need to take a detour and learn about the formal
design and analysis of algorithms. This will be a brief
introduction, and you are invited to look up some of the more
detailed texts on the subject, or take a course on algorithms.
What is an algorithm? An algorithm is a well-defined sequence of computational steps that solve a given problem. Executing these steps on a given input set results in the desired outputs being generated. It is obvious that a careful design of an algorithm can lead to substantial efficiency in solving a problem. Often times, there are a number of different algorithms available to solve a problem. It is then necessary to analyze the various algorithms to determine which of these is the ``better'' algorithm.
One way to analyze an algorithm is to compute the ``cost'' of solving the problem using that algorithm. This cost is referred to as the complexity of the algorithm. There are two different costs that one might be interested in: the time complexity and the space complexity. The time complexity provides a measure of how much time the algorithm requires to complete, and the space complexity provides a measure of the storage requirements of the algorithm. One of these can be more important than the other depending on a given situation.
What factors does complexity depend on? The complexity of an
algorithm is typically described as the rate of growth of the time and
memory requirements to solve larger and larger problems. These
quantities are therefore functions of n, the ``size'' of the
given instance of the problem. For instance, for a matrix inversion
problem, we can define n to be the number of rows in the square
matrix, and T(n) then defines the time complexity of a
given algorithm to solve the problem. In addition, we are usually
concerned with worst case complexities-how long does the
algorithm take given the input set that results in the longest
possible time. Also, we are usually interested in asymptotic
complexity-what happens to the complexity function in the limit as
the size of the problem approaches infinity.
Why do we do this? We are interested in the general
behavior of the algorithm, and this usually shows up better in the limit.
However, it is important to pay attention to the caveats to this rule.
Thus, the worst case asymptotic time complexity provides the algorithm designer with an idea of how the algorithm will perform in real life. To look at the asymptotic complexity of an algorithm, one needs formalisms that accurately represent the limiting performance of the algorithm. One particular set of notations provide information about the bounds on the complexity of an algorithm. Three different kind of analyses can be carried out on an algorithm, and each is represented by a different symbol:
Transparency to graphically describe the three notations.
Mathematically, these bounds are represented as: