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.
|