Hockney and Jesshope [13] introduced
two parameters to describe the performance of vector processors.
The first parameter is the theoretical peak performance, or
asymptotic performance, denoted 
. It is the
maximum possible rate
of computation, expressed as a number of floating point
operations per second. The parameter may be applied to a single
vector pipeline or to an entire system. Thus for a
single pipe
of the Cray Y-MP is 167 MFLOPS (6ns cycle, one result per cycle),
and approximately 2.6 GFLOPS for an 8-processor system with the
add and multiply units in operation simultaneously. The other
parameter, designated 
and known as the half
performance length,
is the length of the vector for which a system attains half of
its peak performance, i.e. 
. is
a function of vector startup
time and pipeline depth. As these values increase it becomes
harder and harder to achieve near peak performance for the system
because it requires algorithms with longer and longer vectors. As
we saw in section 2.2, the startup times for the CDC
vector computers were an order of magnitude greater than those
from Cray Research. This is reflected in for the two systems
differing also by an order of magnitude. Even though
was higher
for the CDC machines, the systems from Cray proved more popular
than those from CDC, so users seem to find lower more
important.
Perhaps the most fundamental performance question that can be asked of an algorithm running on a parallel system is ``does it run faster, and if so by how much?''. Ideally, if one uses P processors to solve a given problem, the execution time would be cut by a factor of P. This leads to a definition of speedup, which is the ratio of the execution time on one processor to the execution time on P processors:
For example, if a program takes
18 minutes to run on one processor, but only 4.7 minutes on four
processors, the speedup is a factor of 
.
The strength of such a
measure is that it uses observed execution time and thus takes
into account any overhead in the parallel system for breaking a
job into parallel tasks and intertask communication time.
Comparing time on one processor vs. time on 
processors can be
misleading, however. One might be tempted to write a program for
a -processor machine, time it first on one processor and then on
processors, and call the ratio the speedup. Plotted for
different values of this procedure gives an accurate measure of
the scalability of the algorithm used, but it does not answer the
question how much faster a problem may be solved using
processors since a parallel algorithm usually incurs overheads
that are not found in sequential algorithms.
Ortega and Voigt [24] defined speedup as the
ratio of the solution time for the
best serial algorithm with that required by the parallel
algorithm:
In the 1960's, Amdahl [1] noted that speedup is
limited by the size of the portion of a problem that is not
executed faster. For example, suppose a program that executes in
10.0 seconds contains a key subroutine that accounts for 80% of
the execution time. The rest of the program uses 20% of the total
time, or 2.0 seconds. If we use a more efficient version of the
subroutine that runs twice as fast, total execution time will
drop to 6.0 seconds (
seconds for the subroutine,
2.0 seconds for
the remainder of the program). If we find a parallel subroutine
that speeds up perfectly on P processors, and run the program on
an 8-processor machine, execution time will drop to 3.0 seconds
(
seconds for the parallel portion, 2.0 seconds for the
sequential portion). If we run on 100 processors, the
total execution time
will be 2.08 seconds. As more processors are used, the execution
time gets closer to the time required for the sequential part,
but it can never get lower than this. Since the fastest this
program will ever run is 2.0 seconds, no matter how many
processors are used, the maximum speedup is a factor of 5.0.
If we normalize the formula that defines speedup by letting the sequential execution time be 1 and expressing the other times as percentages of the sequential time, we derive the following formulation of Amdahl's law for parallel processors:
This
version of the equation makes the contribution of the sequential
portion of the computation more apparent. Here 
is the fraction
of the program that can be performed in parallel, and thus 
is the portion that is sequential. The denominator is the time to
execute the program in parallel, i.e. the sum of the time spent
in the sequential portion and the time spent in the parallel
part, where the parallel time is a function of the speedup factor
of the parallel portion. If the parallel portion exhibits perfect
speedup, i.e. a factor of when run on P processors, the
equation becomes:
The efficiency of a parallel computation is the ratio of the speedup to the number of processors used to obtain that speedup:
For example, if 10 processors are used and
the program runs 10 times faster, we are running at the maximum
possible speed, i.e. all processors are being used to their full
capacity. If the speedup is only a factor of 5, however, the
efficiency is 
, i.e. half the computing power is
lost in overhead or synchronization.
The above models do not try to characterize the execution of a parallel program. They simply measure the time required to execute a program on a given machine, and compare that time to sequential execution times. A simple model that breaks a parallel program into constituent parts is
The three
components of overall execution time are 
, the
computation time,
, the time spent in communication, and 
, the
time used to
synchronize the processors at appropriate points in the
algorithm. This type of analysis is very important for algorithms
that will run on distributed memory machines, where locality and
communication costs will play a major role in efficiency.
Expressions for communication complexity can range from very
simple, e.g. all communication requires the same amount of time
(a reasonable model in some cases for a shared memory system), to
very complex, as would be required for an accurate model of a
distributed memory system that communicates by message passing.
In the former case, the number of accesses to memory times the
average access time might suffice. In the latter case, a more
complex analysis is necessary for an accurate model. For example,
the time to send a message from processor 
to processor 
in a packet switched network is often modeled by
an expression such as
where is the overhead in setting up the message in the sending
processor (and, if necessary, storing a message in the receiving
processor), 
is the distance from to , and 
is
the length
of the message in packets. Again, this simple formula hides many
additional complexities that might or might not effect
performance: the existence of a separate processor at each
processing node to handle messages, contention at links or nodes,
whether or the routing is fixed or dynamic, etc.
The overhead for synchronization can also involve a number of issues depending on the algorithm and the type of synchronization mechanism used. For example, an SIMD system automatically synchronizes parallel subtasks and no further modeling is required. For MIMD systems, in addition to the overhead associated with the actual synchronization process, there is also the idle time created when processors wait at a synchronization point. A thorough discussion of synchronization mechanisms may be found in Andrews and Schneider [1983]. The development of a complexity model involving all three of the above factors in great detail may be found in Reed and Patrick [1985]. A general discussion of many of the issues relative to linear algebra algorithms may be found in Ortega [1988].