IBM - Personal communication

This web page discusses the performance of the programs grs1, grs2 and grs3 (available here ) which find all Golomb rulers with n marks and length at most k by exhaustive backtrack search.

Table 1 shows the time on various machines to complete a specific test problem, finding the unique ruler with 13 marks and length 106. See below for instructions on how to run this problem.

Table 1 - Golomb ruler search program performance - by machine
Machine and compiler information Times (in seconds)
model chip Mhz compiler options who grs1 grs2 grs3
IBM RS/6000® 44P-170 630 400 xlf 8.01 -O -qarch=pwr3 jbs 13.34 11.20 10.31
IBM RS/6000® 43P-140 604e 332 xlf 3.02 -O jbs 21.17 18.29 15.61
IBM SP2® node 630 200 xlf 5.01 -O3 -qarch=pwr3 jbs 27.47 23.61 20.94
IBM SP2® node P2SC 135 xlf 6.01 -O jbs 48.17 41.80 33.86
IBM Intellistation PIII 933 g77 (win) -O jbs 12.96 11.65 13.32
IBM Aptiva® E34 AMD K6 233 g77 (win) -O jbs 50.30 39.40 46.30
IBM Aptiva® E34 AMD K6 233 g77 (emx) -O jbs 55.83 47.30 55.66
IBM Thinkpad® 755cx pentium 75 g77 (win) -O jbs 181.21 155.17 190.12
IBM Thinkpad® 755cx pentium 75 g77 (emx) -O jbs 192.91 184.29 187.36
IBM S/390® 9672-R66 G5 ? vsf 2.6 opt(3) jbs 49.50 50.12 58.07
IBM S/390® 9021-9x2 n/a 140? vsf 2.6 opt(3) jbs 98.58 84.97 105.14

The results in table 1 were obtained by:

Table 2 below shows how the solution times vary with problem size. Times are for the grs3 program running on a IBM 43P-140. Relative performance for other cases should be similar to that shown in table 1 above.

Table 2 - Golomb ruler search program performance - by problem size
n=marks k=length solutions nodes searched time(seconds) nodes/microsecond
10 55 1 56265 .02 ?
11 72 2 994323 .29 3.43
12 85 1 2585331 .85 3.04
13 106 1 49441242 15.61 3.17
14 127 1 421952981 140.97 2.99
15 151 1 6316962547 2140.84 2.95

Instructions for running the Table 1 test problem.

In order to run the test you may have to modify the source to use a timing subroutine appropriate for your system. Then compile (you may wish to experiment with optimization options) and start the program. Enter from the terminal (unit 5) 

0001300106
You should see the following written to the terminal (unit 6). This may take a few hundred seconds on a slow machine. The first two lines will be written first, then the third line a bit later. 
      0     7     8    17    21    36    47    63    69    81
    101   104   106
 n= 13 k= 106 solutions=       1 time=     xxx.xxxxxx nodes=      49441242.
You can now terminate the program by entering 
0
At this point there should be a disk file (fortran unit 1) containing the Golomb ruler found. It should look like this: 
        13       106
     0     7     8    17    21    36    47    63    69    81
   101   104   106
         0         0
(The program grver will independently verify that this is a Golomb ruler.)

Of course the time output (in seconds) will be system dependent, the rest of the output should be exactly as shown above (or something is wrong).

[ IBM Research home page | James B. Shearer's home page ]
[ IBM home page | Order | Search | Contact IBM | Legal ]