ISPD98 Benchmark

Here are 2% actual area results of PaToH compared to UCLA MLPart and hMeTiS. First column (hMeTiS result cut result) and third column (MLPart result) are from MLPart's web site. We have used their "Configuration 1". We have run PaToH using PATOH_SUGPARAM_QUALITY parameter settings. The reported numbers are average of 100 independent runs. If time permits I'll try do more experiments corresponding the other configurations reported in UCLA MLPart's web site.

 

  Cut Sizes
name hMeTiS local hMeTiS run MLPart PaToH
ibm01 267 268 250 263
ibm02 320 317 348 345
ibm03 885 898 903 978
ibm04 550 550 592 562
ibm05 1777 1766 1841 1748
ibm06 728 709 696 866
ibm07 855 849 846 834
ibm08 1246 1229 1354 1213
ibm09 591 598 555 587
ibm10 1310 1329 1419 1409
ibm11 914 933 926 817
ibm12 2304 2323 2676 2154
ibm13 1110 1094 1247 974
ibm14 2092 2092 2043 1964
ibm15 2435 2423 2486 2640
ibm16 2165 2153 2040 1962
ibm17 2610 2599 2437 2517
ibm18 1833 1829 2002 1948
#wins 3 3 4 8

 


I've repeated hMeTiS experiment locally, in order to compare execution times of the heuristics. As you can see out of 18 test cases, 6 best partitioning computed by hMeTiS (3 result reported by UCLA's experiment and 3 by local runs) and 4 of them found by MLPart. PaToH produced 8 of best results out of 18!

 

 

Percent improvement over hMeTiS
local hMeTiS run MLPart PaToH
0% 6% 1%
1% -9% -8%
-1% -2% -11%
0% -8% -2%
1% -4% 2%
3% 4% -19%
1% 1% 2%
1% -9% 3%
-1% 6% 1%
-1% -8% -8%
-2% -1% 11%
-1% -16% 7%
1% -12% 12%
0% 2% 6%
0% -2% -8%
1% 6% 9%
0% 7% 4%
0% -9% -6%
overall 0% -3% 0%

 

The second table displays percent improvement over hMeTiS. As seen in the table, PaToH results are comparable with hMeTiS on the overall average whereas MLPart results are 3% worse than hMeTiS.

 

 

The third table shows the execution times of the heuristics. In our experiments we've used 10 PIII-933MHz Linux boxes. We've computed that, on the average, our hMeTiS runs were 3.13 times faster than the numbers reported on MLPart's web site in which they used 200MHz Sun Sparc-Ultra2 workstation. The execution time of MLPart displayed in the table are scaled proportional to hMeTiS execution time.

 

 

  Average Execution Time (seconds) Normalized Exec Time wrt hMeTiS
name local hMeTiS run MLPart (scaled) PaToH MLPart PaToH
ibm01 1.72 1.40 1.25 0.82 0.72
ibm02 3.39 2.55 1.95 0.75 0.58
ibm03 5.39 3.19 3.19 0.59 0.59
ibm04 4.61 3.82 3.36 0.83 0.73
ibm05 7.01 5.42 4.35 0.77 0.62
ibm06 8.64 4.46 5.02 0.52 0.58
ibm07 14.06 6.37 6.41 0.45 0.46
ibm08 15.47 7.96 6.99 0.51 0.45
ibm09 11.15 7.01 6.88 0.63 0.62
ibm10 24.17 10.51 9.88 0.44 0.41
ibm11 21.74 10.19 9.98 0.47 0.46
ibm12 35.07 10.19 14.72 0.29 0.42
ibm13 30.93 13.06 13.38 0.42 0.43
ibm14 60.07 25.49 21.13 0.42 0.35
ibm15 84.38 27.08 28.31 0.32 0.34
ibm16 88.19 33.13 31.29 0.38 0.35
ibm17 128.70 36.00 34.29 0.28 0.27
ibm18 90.48 40.78 29.20 0.45 0.32
    overall 0.52 0.48

 

 

 

As seen in the table, on the overall average, both MLPart and PaToH runs almost twice as fast as hMeTiS, where PaToH runs slightly (4%) faster than MLPart.