The Consequences of Fixed Time Performance Measurement*

The main reason we use computers is speed. True, they often produce work of higher quality and reliability than other means of doing a task, but these are really just forms of speed. With enough time, pencil-and-paper calculations can match the quality and reliability of a computer. It is the speed of computers that lets us do things we otherwise would not try.

The reason we use parallel computers instead of serial computers is also for speed. This seems so obvious that we seldom belabor the point. Yet, we base everything we do in parallel computing on this motive. The problem is that our usual definition of "speed" is not on very firm ground. Most papers skirt the issue of absolute speed and instead report "speedup," defining speedup strictly as time reduction.

The following cynical definition by Ambrose Bierce, from The Devil's Dictionary (1911), shows the absurdity of basing parallel performance on time reduction:

Logic, n. The art of thinking and reasoning in strict accordance with the limitations and incapacities of the human misunderstanding. The basis of logic is the syllogism, consisting of a major and a minor premise and a conclusion--thus:
Major Premise: Sixty men can do a piece of work sixty times at quickly as one man.
Minor Premise: One man can dig a post-hole in sixty seconds.
Conclusion: Sixty men can dig a post-hole in one second.

This may be called the syllogism arithmetical, in which, by combining logic and mathematics, we obtain a double certainty and are twice blessed.

Bierce used this reasoning as humor almost a century ago. Now we call the flaw in the reasoning "Amdahl's law" and treat it as a serious obstacle to parallel performance. By scaling the problem to sixty post-holes, the absurdity disappears and the sixty men are sixty times as productive as a single man. My thesis is that parallel performance should be measured by the work done in fixed time, and not by time reduction for a fixed problem.

It seems clear that speed, for a computer, is work divided by time. But, what is "work"? The following common "myths" of speed and performance measurement illustrate difficulties involved in defining work:

A Fortran example shows the fallacy of this idea:

The only floating point operations are in the DO 1 loop, which has order N complexity. By current convention for measuring MFLOPS, the work in this problem is 10³. However, the DO 2 loop has integer operations and is of order N² complexity. Even the oldest digital computers would be misjudged by ignoring the relative cost of 10⁶ integer operations, despite their much higher times for floating point operations. But, the DO 3 loop is the most troublesome since it has order N³ complexity and has no "operations" by common measures. Yet, memory operations are the most commonly-used instructions on computers.

The earliest computers were like humans in the respect that they took much longer to do arithmetic, especially multiplies, than to read operands or write results. The situation we now see, compute-intensive processors much faster at arithmetic than data motion, is not intuitive. In the early days of computing, gates (vacuum tubes) dominated both the system cost and the execution time; the wires connecting them were cheap by comparison. Current high-end computer costs and times are dominated by the connections, and the gates are cheap by comparison. Even recent numerical analysis texts base their complexity analysis on the economics of outdated arithmetic-bound machines.

The previous section illustrated some of the current difficulties in assessing computer performance. The following section discusses historical attempts to analyze performance, especially parallel speed improvement. The definitions at the end of this section represent an attempt to provide a new theoretical basis for performance analysis that avoids some of the classical dilemmas.

Although the goal of algorithm-independent, architecture-independent expressions for work is a laudable one, it is generally untenable.

The use of "speedup" as the ratio of times avoids the need for a rigorous definition of computational work, since the work in the numerators cancels out. To broaden the concept of speedup to variable problem sizes, we will need a practical definition of work. Operation count is an imperfect measure of computational work, since it does not standardize across computers. The counterexamples to Myths 1 and 2 illustrate this.

Even a simple word fetch from memory takes effort that varies with the computer. Is there error detection? Error correction? How large is the total memory containing the datum? Does the word size match the size of the data bus? Is the fetch word-aligned? In cache? Pipelined? Interleaved across memory banks?

Arithmetic is notoriously different from one computer to another. Specifying precision helps, but by no means creates a standard unit of "work." Computers with "64-bit arithmetic" might use from 47 to 56 bits for the mantissa, with the larger mantissas associated with more logic gates and precision. Not even use of the IEEE floating-point standard format promises fair comparison, since IEEE format does not ensure IEEE execution rules.

The most common approach is to pick a computer as representative, and define its execution time as the work. We see "VAX Units of Performance" and grand challenges that take work measured in "CRAY-centuries." As the counterexample to Myth 3 shows, picking a "standard computer" is hazardous business. In measuring the performance of homogeneous MIMD computers, one usually picks a single processor of the ensemble as the standard for comparison. Even then, system resources seldom scale perfectly with the number of processors.

There are always limits on N for the coefficient fit. A common simplification in performance evaluation is to assume the complexity measure applies beyond the set of measurable sizes. When N becomes so large that the problem no longer fits in main memory, the computer must use secondary storage (either explicitly, or automatically via virtual memory). The coefficients in the functional form appear to increase for larger N, which is another way of saying that the functional form is too simple. It needs more terms to distinguish different memory reference types. Data caches have the opposite effect on the coefficient values. Figure 3 shows typical behavior for a computer with a data cache and virtual memory.

The program listing probably does not reveal the functional form of caching or virtual memory costs, making analysis very difficult. Even explicit use of secondary storage is hard to quantify, since it is usually mechanical and has random latency. So, many authors implicitly make the following assumption:

The Flat Memory Approximation is like the assumption that the Earth is flat. For many everyday activities, like estimating short distances, a planar view of the world simplifies life at little cost of accuracy. If we scale up the problem to distances of thousands of miles or down to a few inches, the flat Earth assumption gets us into trouble.

The complexity of the algorithm chosen for a P-processor version of a program is C_P(N). Its functional form will usually be different from that of C(N), and the coefficients of like terms will almost surely be different. The fallacy of assuming C₁(N) = C(N) is well-known, but one still sometimes reads papers that ignore this distinction. Generally, C₁(N) > C(N) since the former incorporates parallel overhead.

The "canonical scalable problem" is one with time cost of the form

.

CP(N) = A + B(N) / P

(3)

In this simple model, all work is either completely serial or completely parallel, communication costs are constant as P increases, and all the work that scales with N is parallel work. Despite its simplicity, the canonical scalable problem model serves well to test definitions of speedup and efficiency.

With the definitions of the preceding section in place, we can compare and contrast the traditional definition of "speedup" with its more recent variants.

The fixed size speedup fixes the value of N as P is varied. N = N₀ is typically the size of the largest problem that conveniently fits into primary memory.

fixed size speedup (P) = C(N0 ) /CP (N0 )

(4)

Surprisingly few researchers recognize the two-dimensional nature of speedup data (dependence on both N and P). One reason might be the wish to measure the speedup of complicated programs strictly by experiment, and an analytic expression for the complexity might be difficult to find.

The traditional "speedup graph" is of the form

Sometimes, a family of curves is presented for different problem sizes, with the larger problems closer to the idealized "linear" speedup. Since not all problem sizes fit on all ensemble sizes, each curve will only cover a partial range of P values:

The treatment shown in Figure 4b is a struggling form of scaled speedup, but the use of a set of curves obscures the scaling. We suggest a more straightforward approach in the next section.

Not all computing problems scale. An example might be medical tomography, where a computer turns a set of x-ray readings into a three-dimensional density map for perusal by physicians. There is an upper limit to the performance demanded for such a task, imposed by the limit on how much data can be understood for purposes of medical decisions. More powerful computers can reduce execution time, but there is little medical point in reducing the time below a few seconds.

More common, however, is the case where added computing power allows us to tackle a more difficult version of the problem of interest. One might want more grid points in a finite difference model, higher-order numerical methods, or more detailed physics.

In the early days of hypercube computers, it was common to scale the problem with the number of processors, but measure the resulting speedup in an unclear manner. Researchers would calculate MFLOPS rates based on how fast a serial processor would run the problem if it had enough memory (the Flat Memory Approximation). Usually, they would assume the uniprocessor MFLOPS rate to be constant across all problem sizes. They would then declare the ratio of parallel to serial MFLOPS rate to be the speedup. This represents a conceptual leap from the traditional definition of speedup, however, and must be regarded differently.

In its usual sense, "scaled speedup" means that N increases with P. By how much? If N₀ is the size of problem that just fits in the local memory of a single processor, then N is usually scaled to just fit the total local memory of P processors. If the storage is proportional to N₀ , then P processors run a size PN₀ problem. The scaled speedup is

scaled speedup(P) = C(PN0) / CP (PN0 )

(5)

Note that measuring the denominator in (5) might require the Flat Memory Approximation, since PN₀ might be too large a problem for a single processor in the ensemble. For this example, and many scaled speedup formulas, there is no bound to speedup as P goes to infinity. This cheerful result must be accompanied with at least two major cautions. First, there is seldom a practical need for a problem size N = PN₀ beyond some limit. Eventually, the quality of the answer will reach a point where no further increase in complexity is justified. Second, the execution times usually increase for the parallel system when problem size is scaled linearly. It is typical in scientific problems that work grows superlinearly in the number of variables. Even with P times the processing power, a problem on P processors with PN₀ variables will take longer than on a single processor. This growth in execution time is unrealistic, since we tend to solve only those problems on computers that fit within the limits of human patience.

The scaled and fixed time speedup models are slightly more difficult to apply to experimental results than the traditional fixed size model, because of the need for a complexity formula. However, the extra effort is usually repaid by better insight into parallel scalability. To show how the different speedup models work in practice, the following section applies all three models to an application for which the complexity function is known.

Suppose a molecular mechanics simulation of size N has the following complexity:

Serial time C(N) = 1000000 + 1000N + 24N2 µs		(8)
Parallel time Cp(N) = 1500000 + 1050N /P + 24N2 / P µs		(9)
Serial storage = 100000 + 200N bytes		(10)
Parallel storage = 125000 + 200N/P bytes		(11)
(per processor)

where P is the number of processors. We can use this information to find, for P = 1, 2, 4, . . . , 1024:

1. Fixed size speedup for N = 1000.
2. Scaled (memory-bounded) speedup for N / P = 1000.
3. Fixed time speedup for a time of 26 seconds.

The fixed size speedup is simply the serial time divided by the parallel time for N = 1000:

(12)

This is a classic Amdahl model. As P goes to infinity, the speedup approaches 26 /2.55 10. The denominator is the time for the serial method, not the time for the parallel method run on one processor.

Table 2. Fixed Size (Traditional) Speedup

If N / P = 1000, then the time a single processor would have needed to solve a problem that size is found by using 1000P for N in the formula for serial time:

(13)

As is typical of scaled speedup formulas, equation (13) has no asymptotic limit as P goes to infinity. However, the execution time on the parallel computer increases almost linearly with P, a distortion of the way we would probably use the computer in practice.

Table 3. Scaled Speedup Example

The serial execution time for N = 1000 is about 26 seconds, so we pick this as the fixed time for the parallel version. We need to solve the following equation for N:

(14)

Complexity formulas are seldom this easy to invert; we usually need numerical methods to find the integer that comes closest to satisfying the fixed-time requirement. For each P, the resulting N gives the speedup from (7). The denominator will always be about 26 seconds. Storage per processor follows from the formula 125000 + 200N/P.

Table 4. Fixed Time Speedup Example

The table does not go far enough to show the theoretical limit to fixed time speedup, but at some point the storage per processor would have to be less than 125000 + 200, meaning that each processor internally stores less than the data for one particle. The problem cannot be divided further without a major algorithm change, and one cannot increase the problem size without increasing the execution time.

The examples show some salient features of the three types of speedup. The fixed size model shows we get little benefit beyond a few doublings of the number of processors. The scaled model shows near-linear speedup, but the execution time increases dramatically. The fixed time model shows excellent speedup, but decreasing storage per processor that limits the benefit from using more processors. If space permitted, we could add a term to C_p(N) that increases with P (e.g. for communication cost), and show the effect on the three speedups. In practice, terms that grow with P usually limit fixed time speedup, not the effect of too-fine problem subdivision.

In using fixed time benchmarking, my colleagues and I have discovered several surprising consequences of what appears to be a very simple idea. The next section gives a sampling of these consequences.

If we divide (16) by P to get the usual definition of efficiency for the canonical scalable problem, the formula has no dependence on B:

Canonical fixed time
efficiency = [A + P (t-A)] / Pt		(17)

This is surprising, since it suggests efficiency depends on the constant overhead alone, and not the processing speed! This is true for other definitions of "efficiency" as well. Consider the design of traditional vector arithmetic. To do n operations, there is a startup time a followed by a time per operation, b. Total time is a + bn. Since the work done is simply n ,

speed(n) = n / (a + bn)

~ 1 / b as n -----> .

The asymptotic speed is sometimes called r . Efficiency can be defined as the speed divided by r , or n / (a/b + n). A designer might wonder whether to double the number of pipeline stages, say, resulting in a time for n operations of a + ( b / 2)n. This doubles r, but reduces the efficiency to n / (2a/b + n):

The conventional wisdom is that too many pipeline stages eventually destroys efficiency. In practice, one cannot double the number of stages without increasing the clock rate. But, the above argument shows that even if it were possible to do so, it would lead to less efficient use of the hardware for a given value of n.

Instead, however, suppose we examine vector processing efficiency as a function of time instead of problem size. Since t = a + bn , we can state n in terms of the time: n = (a - t ) / b. Then

For a given execution time, efficiency does not depend on the value of b. See Figure 6. [Note that the graph has changed from one with a y-intercept to one with an x-intercept, since the execution time must be at least a, and efficiency is zero if t = a.]

This suggests a very different course of action to the computer engineer. If one really can reduce the value of b without affecting a, then the only consideration should be the hardware cost of that speed increase, not loss of "efficiency."

As a final example of a surprising result of fixed time performance evaluation, the fixed time model creates a new source of superlinear speedup. In this context, "speed" means operations per second for some type of operation; whatever the measure, we assume speed varies on each processor as a function of time. You can think of the speed as a function of the subtask. If there are two subtasks, each growing with problem size N, and each possible to run in parallel, then Figure 7 shows how the changing speed "profile" can increase performance superlinearly.

Amdahl predicted a limit of 1/s to parallel speedup, where s is a constant serial fraction. The revisionist view, "Just make the problem larger!" removes that limit, but is almost as unrealistic in practice. If problems are scaled in the number of variables, the work might grow faster than P and execution times will tend to infinity. Except for the canonical scalable problem, the fixed time model predicts that communication and other parallel overheads will eventually swamp the allotted time, setting a hard limit to the benefits of parallel processing. That limit is almost always much higher than 1 / s, however. Even if there are no terms in Cp(N) that increase in P, the fixed time model can imply problem decomposition of less than one variable per processor, creating another theoretical limit on parallelism. Example 5.3 illustrates this.

The fixed time model began as a means of discussing application performance for papers on parallel computing. In 1989, my colleagues and I decided to try to apply the concept to the notorious activity know as benchmarking. It seemed to us that much of what had been lacking in industry-standard benchmarks stemmed from the universal use of the traditional fixed size model. Also, we sought a full-scale application with which to test the fixed time analysis of the preceding sections.

The classic method of measuring performance for a fixed problem size has the advantage of basis on a precise physical quantity, time. It has the disadvantage that it leads to distortion effects, since large amounts of optimization create a mismatch between the problem and the hardware capacity. The fixed time method has the disadvantage that it requires a definition of "work" for measurement of performance, but it removes the distortion effects and allows comparison of very different computer systems. Unoptimized parts of a fixed time job become a larger part of the total execution time as the problem size grows, but more gradually and more realistically than for the fixed size model. For most parallel complexity models, fixed time implies a limit to the performance obtainable by using more processors, but this limit is more optimistic than the one claimed by Amdahl and more realistic than the one claimed by scaling the storage.

Our approach to measuring work is to get a functional form for the time on one processor, and use experimental measurements to determine the coefficients in the form. With the simplifying assumptions of flat memory and related hardware scaling issues, work can be defined for ensembles built of that processor type. Speedup becomes a function of both problem size and ensemble size. Fixed size, scaled, and fixed time models are one-dimensional subsets of that space. The fixed time model, unlike its predecessor, does not reward slower processors with higher speedup and efficiency in the canonical case that all the scalable work is parallel. For similar reasons, the efficiency of the canonical case, written as a function of time instead of problem size, does not depend on the number of processors or their speed.

I am indebted to several individuals at Ames Lab for their help with the concepts presented here. X.-H. Sun provided much feedback and clarifying discussions regarding performance paradigms. In particular, Sun was the first to show that fixed time lessens the tendency to award parallel ensembles of slower processors with higher "speedup" numbers. The careful work of M. Carter and N. Nayar made possible the discovery of the fixed time efficiency principle. D. Rover, S. Elbert, and M. Carter were indispensable in creating the SLALOM benchmark, and dozens of people around the world have contributed their fixed time measurements to the SLALOM database since its introduction.