ISPD98 - Circuit Benchmark Errata

The Circuit Benchmarks Suite paper published in ISPD98 contains two major errors regarding the hMETIS partitioning results that were quoted.

  1. The size bounds for 4- and 8-way partitioning are incorrect. In the paper, the 4-way cluster size bounds were quoted as 22.5-27.5% of the total area. Similarly, the 8-way cluster size bounds were quoted as 11.25%-13.75%. The actual bounds are 20.25-30.25% for 4-way partitioning and 9.1125%-16.6375%. The reason for the error was my misinterpretation of the hMETIS manual. These bounds are derived by using (0.45)^2 - (0.55)^2 for 4-way and (0.45)^3 - (0.55)^3 for 8-way partitioning. Thanks to Sung Lim for pointing this out to me.
  2. A slight error in my script caused all the results for actual areas to be wrong. Some are only slightly incorrect, while other cut results are off by an order of magnitude. I have re-run the actual area experiments using a correct script. The complete results are given in the table below. These runtimes are for a 135 Mhz IBM RS6000 S/595.
Since ISPD98, George Karypis has made some slight enhacements to hMETIS. Please use both the table for actual areas and the table for unit areas when quoting the hMETIS algorithm in any publications. These tables were provided courtesy of Dr. Karypis. The runtimes given are for a Pentium Pro 4-way SMP @ 200Mhz.

More recent results for the ISPD-98 benchmarks can be found in the Partitioning Slot of the MARCO/GSRC bookshelf for VLSI CAD algorithms.

Back to the ISPD98 Circuit Benchmark Page

A comparison of hMetis and UCLA MLPart: 2%, 10% (actual area, limited-runtime mode)

(a comparison of MLPart best-seen results will be posted soon)

New hMETIS table for Actual Areas

This table is intended to replace the actual areas partitioning data in the ISPD98 paper. The version of hMETIS used to generate this data is from December, 1997.

2 partitions

4 partitions

8 partitions

10% dev

2% dev

UBFactor 5

UBFactor 5

Cut

CPU

Cut

CPU

Cut

SOD

CPU

Cut

SOD

CPU

ibm01 221 2.2 237 2.2 344 717 4.0 636 1382 5.8
ibm02 279 3.9 280 4.4 530 1118 6.9 855 1866 11.0
ibm03 836 4.5 923 4.6 1513 3358 9.3 2229 5222 14.7
ibm04 440 5.7 503 5.4 1393 2937 10.2 2528 5547 14.9
ibm05 1733 8.8 1739 9.7 3094 6877 15.2 4503 11559 19.6
ibm06 506 7.6 799 8.4 1278 2699 15.1 1986 4737 21.0
ibm07 735 12.7 748 13.3 1581 3446 23.5 3004 6596 32.5
ibm08 1159 20.1 1203 21.4 2209 4656 33.0 3495 8104 43.7
ibm09 523 12.0 523 12.2 1486 3036 21.6 2532 5481 30.6
ibm10 777 22.5 1208 24.9 1849 3772 41.9 3088 6668 56.4
ibm11 713 17.2 802 17.3 2040 4106 32.3 3282 6822 46.3
ibm12 1992 25.4 1997 25.3 3582 7408 42.9 5047 10591 57.7
ibm13 853 24.2 905 24.2 1739 3758 41.8 2542 6021 57.3
ibm14 1570 61.6 1886 64.1 3298 6994 106.8 5030 11360 141.1
ibm15 2245 56.0 2625 60.8 4502 9544 108.3 6572 14582 142.9
ibm16 1696 71.8 1660 81.0 3630 7585 135.2 5893 12879 180.5
ibm17 2392 108.3 2495 112.4 4671 9686 186.8 8288 17880 252.3
ibm18 1522 89.3 1654 113.7 3106 6919 160.0 4916 11380 223.3

Latest Actual Area Results for hMETIS

This table is the actual area data from the latest version of hMETIS (May, 1998). Use this table when quoting results in future publications. The runtimes given are for a Pentium Pro 4-way SMP @ 200Mhz.


2 partitions

4 partitions

8 partitions

10% dev

2% dev

UBFactor 5

UBFactor 5

Cut

CPU

Cut

CPU

Cut

SOD

CPU

Cut

SOD

CPU

ibm01 215 2.9 230 2.9 344 706 5.3 598 1288 7.6
ibm02 269 4.8 266 5.2 510 1091 9.4 823 1756 15.2
ibm03 681 6.6 748 6.8 1358 2796 12.6 1947 4343 17.6
ibm04 440 7.9 506 7.6 1311 2757 13.4 2446 5257 18.9
ibm05 1722 10.3 1727 11.3 2994 6477 18.5 4405 11109 23.6
ibm06 367 8.7 550 9.5 1150 2371 19.1 1859 4288 27.0
ibm07 737 14.7 739 14.1 1570 3274 28.0 2930 6267 40.5
ibm08 1157 17.3 1188 17.4 2132 4509 34.8 3306 7144 53.8
ibm09 524 15.0 523 14.9 1406 2892 34.5 2277 4889 49.9
ibm10 756 27.9 1133 29.7 1829 3718 50.2 3108 6623 67.1
ibm11 695 24.9 781 25.6 1947 3953 43.1 3001 6263 63.7
ibm12 1976 30.4 1998 29.0 3585 7446 54.8 4966 10336 76.3
ibm13 833 27.1 902 28.3 1678 3561 52.1 2408 5541 73.5
ibm14 1527 64.9 1772 70.2 3069 6562 117.4 4884 10615 160.9
ibm15 1801 65.8 2099 64.2 4435 9135 125.5 6001 12941 160.9
ibm16 1668 81.7 1692 87.4 3707 7591 160.2 5400 11354 203.4
ibm17 2257 113.8 2396 114.4 4562 9392 206.2 7838 16461 315.1
ibm18 1522 95.3 1664 107.7 3106 6912 202.2 4833 11033 295.3

Latest Unit Area Results for hMETIS

This table is the unit area data from the latest version of hMETIS (May, 1998). Use this table when quoting results in future publications. The runtimes given are for a Pentium Pro 4-way SMP @ 200Mhz.

2 partitions

4 partitions

8 partitions

10% dev

2% dev

UBFactor 5

UBFactor 5

Cut

CPU

Cut

CPU

Cut

SOD

CPU

Cut

SOD

CPU

ibm01 180 2.7 203 2.8 496 1004 5.2 755 1606 7.5
ibm02 262 6.1 354 6.8 615 1302 11.3 1874 3978 16.6
ibm03 956 7.0 957 7.4 1682 3600 11.3 2396 5580 15.6
ibm04 542 7.5 595 7.4 1711 3616 14.2 2782 6167 19.6
ibm05 1715 10.8 1733 10.9 3040 6537 18.0 4443 11383 23.7
ibm06 888 10.6 978 10.7 1592 3620 18.6 2257 5685 25.5
ibm07 853 16.6 951 16.7 2168 4572 30.2 3284 7480 40.2
ibm08 1142 20.5 1141 20.9 2426 5214 37.8 3462 7973 49.8
ibm09 624 15.7 629 15.0 1685 3463 34.9 2664 5788 49.0
ibm10 1256 27.4 1333 30.7 2280 4828 52.1 3799 8270 67.5
ibm11 960 28.9 1071 30.5 2300 4713 46.7 3543 7491 61.8
ibm12 1918 37.0 1982 37.2 3799 8099 60.4 6024 12984 80.7
ibm13 840 28.6 859 31.4 1760 3818 54.6 2858 6251 77.6
ibm14 1837 63.2 1865 65.2 3249 7019 116.2 4795 10447 157.4
ibm15 2625 74.6 2833 76.8 5014 10398 141.5 6610 14425 189.9
ibm16 1755 82.7 2059 95.3 3847 7818 139.3 6203 12682 228.2
ibm17 2238 105.7 2403 116.9 5398 11014 192.1 8695 18441 288.9
ibm18 1541 92.9 1587 113.8 2872 5992 196.0 5210 11861 267.3




Chuck Alpert's Home Page | ISPD98 Circuit Benchmark Suite | MCNC Benchmarks in net format | Partitioning Codes | Publications | UCSD VLSI CAD Laboratory