Ratios of Predicted Time on 500 Mhz Alpha to Actual Time

The table below presents the ratio of the predicted time for one run of the named algorithm on our 500 Mhz Alpha processor (based on the normalization procedure described on the results page) to the actual measured time. Ratios less than 1 correspond to underestimates of the running time; ratios greater than 1 correspond to overestimates.

As one might expect, the accuracy of the normalization process differs from instance to instance, from algorithm to algorithm, and from source machine to source machine. Usually the estimate is within 50% (one way or the other), although in a few cases it is off by factors slightly bigger than 2, e.g., for random distance matrix instances and the Benchmark Greedy code. There are several possible causes for inaccurate predictions:

  1. Variability of running time from run to run, even on the same machine.
  2. For algorithms other than the Benchmark Greedy, the fact that instances with a given number of cities may need more memory than under the Benchmark Greedy Code.
  3. For instances given as distance matrices, the need for more memory than is required for geometric instances of the same size.
  4. Differences in instance structure (although in the case of geometric instances the Benchmark Greedy Code's running time is relatively immune to such differences).
  5. The fact that Machine Benchmark Runs, on which normalization is based, involve repeated runs. Although each run re-builds the data structures and so presumably flushes most of the memory cache, the instruction cache remains current, which might yield a speedup in average time over what can be expected for a standalone run.
  6. Although on repeated runs that data structures are rebuilt, the instance is only read once. Since differences in reading speed do not always correlate well with differences in processsing speed, this can cause added inaccuracies for algorithms that are sufficiently fast that reading time represents a significant fraction of overall time.
  7. Inaccuracies of the assumption that times scale linearly between Machine Benchmark data points.
These results thus suggest that factors of 2 in normalized running time between algorithms run on different machines may not be significant. Moreover, in comparing different algorithms (as opposed to implementations), even bigger running time multiples may be insignificant, because of differences in programming skill or time spent in optimizing the code. Nevertheless, if one IS to compare running times, these normalizations do appear to provide a way to (roughly) remove the machine and compiler from the equation.

Benchmark Greedy Code
Lin-Kernighan
Instance
400 Mhz MIPS ->
500 Mhz Alpha
196 Mhz MIPS ->
500 Mhz Alpha
196 Mhz MIPS ->
500 Mhz Alpha
E1k.0
1.00
1.00
1.37
E1k.1
1.00
1.00
1.42
E1k.2
1.00
1.00
1.24
E1k.3
1.00
1.00
1.33
E1k.4
1.00
1.00
1.50
E1k.5
1.00
1.00
1.33
E1k.6
1.00
1.00
1.37
E1k.7
1.00
1.00
1.53
E1k.8
1.00
1.00
1.53
E1k.9
1.00
1.00
1.37
E3k.0
0.86
0.86
1.47
E3k.1
0.86
0.86
1.42
E3k.2
0.86
0.86
1.50
E3k.3
0.86
0.86
1.48
E3k.4
0.86
0.86
1.51
E10k.0
0.84
0.80
1.46
E10k.1
0.84
0.80
1.46
E10k.2
0.84
0.80
1.48
E31k.0
0.84
0.81
1.11
E31k.1
0.84
0.81
1.09
E100k.0
0.94
0.90
0.83
E100k.1
0.90
0.90
0.87
E316k.0
0.98
1.06
0.57
E1M.0
1.04
1.13
0.64
E3M.0
1.05
1.08
--
E10M.0
1.00
1.09
--
C1k.0
1.00
1.00
1.29
C1k.1
1.00
1.00
1.24
C1k.2
1.00
1.00
0.90
C1k.3
1.00
1.00
1.60
C1k.4
1.00
1.00
1.04
C1k.5
1.00
1.00
1.92
C1k.6
1.00
1.00
1.14
C1k.7
1.00
1.00
1.34
C1k.8
1.00
1.00
1.46
C1k.9
1.00
1.00
1.12
C3k.0
0.86
0.86
1.77
C3k.1
0.86
0.86
1.84
C3k.2
0.86
0.86
1.40
C3k.3
0.86
0.86
0.99
C3k.4
0.86
0.86
1.26
C10k.0
0.84
0.80
1.06
C10k.1
0.84
0.80
1.26
C10k.2
0.84
0.80
1.14
C31k.0
0.86
0.93
1.06
C31k.1
0.87
0.94
0.79
C100k.0
0.94
0.95
0.54
C100k.1
0.96
0.95
0.64
M1k.0
0.47
0.47
1.00
M1k.1
0.46
0.47
0.99
M1k.2
0.46
0.47
0.96
M1k.3
0.46
0.47
0.96
M3k.0
0.51
0.54
1.06
M3k.1
0.51
0.52
1.10
M10k.0
0.55
0.63
1.19
dsj1000
1.00
1.00
1.65
pr1002
0.67
0.67
1.50
si1032
0.46
0.48
1.18
u1060
0.67
0.67
1.44
vm1084
1.00
1.00
1.30
pcb1173
0.67
0.67
1.52
d1291
0.67
0.67
1.28
rl1304
1.00
1.00
1.55
rl1323
1.50
1.50
1.57
nrw1379
1.00
0.67
1.57
fl1400
1.00
1.00
1.35
u1432
1.00
0.67
1.52
fl1577
1.00
1.00
1.46
d1655
0.75
0.75
1.31
vm1748
1.00
0.75
1.28
u1817
1.00
0.75
1.29
rl1889
0.80
0.60
1.64
d2103
1.00
0.75
1.32
u2152
0.80
0.80
1.30
u2319
0.80
0.60
1.52
pr2392
1.00
0.80
1.57
pcb3038
0.86
0.86
1.58
fl3795
0.88
0.88
1.46
fnl4461
0.80
0.80
1.56
rl5915
0.85
0.85
1.60
rl5934
0.85
0.85
1.63
pla7397
0.79
0.79
1.64
rl11849
0.81
0.75
1.16
usa13509
0.84
0.74
1.19
brd14051
0.83
0.74
1.44
d15112
0.82
0.72
1.44
d18512
0.81
0.79
1.32
pla33810
0.86
0.62
1.16
pla85900
0.77
0.51
0.85