Observed speedup of a code which has been parallelized =

         wall-clock time of serial execution 
       --------------------------------------- 
        wall-clock time of parallel execution
    

One of the most widely used indicators of parallelizability, the calculation of observed speedup is both intuitively satisfying, and potentially misleading; the former because a well-parallelized code can be shown to run in a fraction of the time that it takes the serial version, the latter because, in many respects, this is a comparison of apples and oranges: the codes are different, they perform different tasks, the algorithms may be entirely distinct. Still, there is no discounting the fact that a good job of parallelization will be evident in the amount of wallclock time it has saved the user; what is debatable is the converse: if it is not evident that a lot of time has been saved, is it because the problem itself is not parallelizable, or because the parallelization simply wasn't done well? This, by the way, is where parallel profiling tools, covered later in this presentation, can help tremendously.

The temporal coordination of parallel tasks. It involves waiting until two or more tasks reach a specified point (a sync point) before continuing any of the tasks.

• Synchronization is needed to coordinate information exchange among tasks; e.g., the previous example finding minimum energy conformation: all of the conformations had to be completed before the minimum could be found, so any task that was dependent upon finding that minimum would have had to wait until it was found before continuing.

• Synchronization can consume wall-clock time because processor(s) sit idle waiting for tasks on other processors to complete.

• Synchronization can be a major factor in decreasing parallel speedup, because, as the previous point illustrates, the time spent waiting could have been spent in useful calculation, were synchronization not necessary.

Parallelization doesn't come free, and one of the most insidious costs is the time and cycles put into making sure that all of those separate tasks are doing what they're supposed to be doing. Things that are simply taken for granted in serial execution, or that don't apply, take on special significance when there are many tasks instead of just one; the three most commonly encountered coordination tasks are:

• Time to start a task

  This involves, among other things:

  1. identifying the task
  2. locating a processor to run it
  3. loading the task onto the processor
  4. putting whatever data the task needs onto the processor
  5. actually starting the task

• Time to terminate a task

  Termination isn't a simple chore, either: at the very least, results have to be combined or transferred, and operating system resources have to be freed before the processor can be used for other tasks.

• Synchronization time, as previously explained.

A measure of the ratio of the amount of computation done in a parallel task to the amount of communication.

• Scale of granularity ranges from fine-grained (very little computation per communication-byte) to coarse-grained (extensive computation per communication-byte).
• The finer the granularity, the greater the limitation on speedup, due to the amount of synchronization needed. Remember from the very beginning of this module about considering how hard it would be to coordinate the activities of 52 people, all trying to help sort a single deck of cards?

A parallel system with many processors. "Many" is usually defined as 1000 or more processors.

A parallel system to which the addition of more processors will yield a proportionate increase in parallel speedup. Whether or not this increase occurs typically depends on some combination of:

• Hardware

  One of the most significant bottlenecks to scalability lies in the capability of the communications network -- adding more processors to a network that is already filled to capacity will not yield the expected increase in speedup, and could in fact do just the reverse.

• Parallel Algorithm

  Some algorithms are better suited to parallelism (i.e., more scalable) than others, and there are even economies of scale within parallel ones, i.e., algorithms that work well at certain scales of parallelism work poorly at higher scales, and vice versa. Generally speaking, scalable implies O(n) growth ("on the order of n"; i.e., linear) with data-size n, and preferably the growth should be O(log n).

  It should be emphasized here that great care should be taken to match the algorithm with the actual problem, and both of these with the actual size of the machine on which the problem will be attacked using that particular algorithm. A particular algorithm may appear to work quite nicely on the given problem when run on a small number of nodes, or on a part of the problem over the entire target machine, but when all three production versions are brought together, you may find that your initial tests were in fact misleading, and what worked well at a small scale works not at all at the desired scale.

• Your actual code

  Even if you use an algorithm well suited to your purposes, the way you implement it can determine how much parallelism is actually expressed in your application. Easy ways to negate the usefulness of a good algorithm include using unsuitable data objects, or failing to take into consideration how your programming language structures things like multi-dimensional arrays in order to maximize the efficiency of addressing natural blocks of data.