Slalom Update: The Race Continues

Last November, we introduced in these pages a new kind of computer benchmark: a complete scientific problem that scales to the amount of computing power available and always runs in the same amount of time--one minute. SLALOM assigns no penalty for novelty in language or architecture, and runs on computers as different as an Alliant, a MasPar, an NCUBE and a Toshiba notebook PC.

Since that time, there have been several developments:

• The number of computer systems in the list has more than doubled.
• The algorithms have improved.
• An annual award for SLALOM performance has been announced.
• SLALOM is the judge for at least one competitive supercomputer procurement.
• The massively parallel contenders are starting to unseat the low-end Cray computers.
• All but a few major scientific computer manufacturers are represented in our report.
• Many of the original numbers have improved significantly.

Most-Wanted List

We're still waiting to hear results for a few major players in supercomputing: Thinking Machines, Convex, MEIKO and Stardent haven't sent anything to us, nor have any of their customers. We'd also very much like numbers for the WaveTracer and Active Memory Technology computers. Our Single-Instruction, Multiple Data (SIMD) version has been improved since the last Supercomputing Review article, so the groups working on those machines might want to check it out as a better starting point (see inset). The only IBM mainframe measurements are nonparallel and nonvector, so we expect big improvements to its performance.

We're awaiting word from the Japanese computer makers: NEC, Hitachi Data Systems and Fujitsu. We also welcome entries from small systems. Anything over 137 FLOPS should be able to finish a small run in less than 60 seconds.

The Superlinear Speedup Effect

A marvelous thing happens with fixed-time benchmarking, not mentioned in our previous report. Many parallel machines more than double their MFLOPS rate when they double the number of processors used. The reason for this is illustrated by the figure below:

Most scientific computers achieve their highest MFLOPS rate doing matrix operations, and lower MFLOPS rate doing setup and miscellaneous tasks. Input/output might not score any MFLOPS at all! As the problem size grows, the matrix operations become a larger and larger fraction of the one-minute run, so the average speed per processor increases. One reason the MFLOPS entries in the table increase so nicely when the number of processors increases is because this effect compensates for some of the usual losses of parallel efficiency.

This is one reason one shouldn't use MFLOPS (or MIPS) to measure performance, of course. Right now we provide MFLOPS in the table to help people translate the performance to something for which they have a feel, but ultimately the only number that matters is the size of the problem solved, here measured by the number of patches.

Preserving Integrity

To answer one question we've been asked repeatedly, we will not accept money in return for optimizing SLALOM performance. But we will provide, for free, unbiased advice and suggestions to anyone trying to get the best possible performance out of their system.

We also do not allow use of these results in advertising without our prior consent. Too often, benchmark data has been "excerpted" in lists that conveniently eliminate certain competing machines or crucial footnotes that tell the full story. If you suspect that SLALOM information is being misused, please contact us immediately. SLALOM is designed to resist "benchmark rot," and we'll fight to preserve its integrity.

Improving the SLALOM Algorithm

A bit of folklore in this business goes something like this: "Half the improvements in computing speed come from hardware advances, and the other half come from algorithm advances." That is, if an application runs 10^8 times faster than it did 35 years ago, it's probably the result of 10^4 times faster hardware and 10^4 times faster algorithms. Starting in 1990, SLALOM began what may be a decades-long experiment to test this aphorism.

At Cray Research, Inc. and elsewhere, a technique known as Strassen multiplication was used in the matrix solver. The idea is that 2 by 2 matrix multiplication can be done with 7 multiplications rather than the usual 23 = 8, and this can be applied recursively to n by n matrices to allow general matrix multiplication in order n^log27 (about n^2.8) floating-point operations. More recent methods take the exponent down as low as 2.4, but are only advantageous for very large n. So we now have "blocked" versions of SLALOM that use matrix-matrix multiplication as the kernel (similar to LAPACK), and you can adjust the size of the matrix and the method used to whatever works best. That was the first major improvement to the SLALOM algorithm.

James B. Shearer, of the IBM T.J. Watson Research Center, has provided a number of ideas for SLALOM, especially in the "SetUp" routines. He discovered a way to reduce the number of calls to the logarithm function, and found ways to re-use some quantities without loss of generality. For very large numbers of patches, he points out, the rounding error in our coupling function will make mathematically approximate formulas computationally more accurate. Fortunately, that will offer only a slight improvement because the setup is only a small part of the one-minute run for such large numbers of patches.

Shearer also suggests that iterative methods for solving the matrix will beat our direct method, at least for the suggested input data. He may be right, but we reserve the right to evaluate systems based on their worst-case-input behavior. If all the walls in the radiosity problem are highly reflective, iterative methods converge very slowly. But we invite the experiment.

These algorithm improvements are another reason not to use MFLOPS to compare performance. These improvements might allow larger problems without higher MFLOPS, and post-mortem operation counts are very difficult with these clever optimizations. For now, we will continue to estimate the minimal operations for the best serial version of the program, which will be accurate to a few percent in most cases.

SLALOM will absorb these changes and others that arise. An upper bound on advances occurs if finer problem decomposition yields no improvement in answer accuracy, for some problem size that can be solved in less than a minute on some machine. This would mean the end of the rate for this first SLALOM experiment, and we would seek different scalable problems on which to base a fixed-time performance comparison. But for now, the SLALOM benchmark looks like it may last for a while.

A "(v)" after the name of the person who made the measurement indicates a vendor. Vendors frequently have access to compilers, libraries, and other tools that make their performance higher than that achievable by a customer.

The CRAY Y-MP runs failed the old SetUp3 tolerance of 5.E-10, but passed with a tolerance of 5.E-8; special LOG and ATAN functions were used with only 11-decimal precision for higher speed. We will enforce the current tolerance uniformly in our next report.

The CRAY 2 figures are low because blocking methods were not used; future runs will use matrix-matrix multiply as the kernel, as was done for the Y-MP.

Contact: John Gustafson john.gustafson@sun.com