HPC Lab

BMI - OSU





HPC Lab

matchmaker2: Framework for Maximum Cardinality Matching on Bipartite Graphs

Supplementary Materials

This document contains supplementary materials for "Mehmet Deveci, Kamer Kaya, Bora Uçar, Ümit V. Çatalyürek: GPU Accelerated Maximum Cardinality Matching Algorithms for Bipartite Graphs. Euro-Par 2013: pp. 850-861".

Run times of the algorithms for original graphs

Graph#Rows#Non Zeros# Initial Match# Maximum MatchGPUPFPHKP-DBFS
scircuit 170998 958936 170956 170998 0.000 0.000 0.000 0.000
ohne2 181343 11063545 181343 181343 0.000 0.001 0.001 0.000
sls 1748122 6804304 62729 62729 0.000 0.001 0.003 0.215
af_shell9 504855 17588875 504855 504855 0.000 0.002 0.003 0.001
Rucci1 1977885 7791168 109900 109900 0.000 0.002 0.003 0.168
apache2 715176 4817870 715176 715176 0.002 0.003 0.004 0.120
tmt_sym 726713 5080961 726713 726713 0.000 0.003 0.004 0.001
ldoor 952203 46522475 952203 952203 0.000 0.004 0.005 0.001
audikw_1 943695 77651847 943695 943695 0.000 0.004 0.005 0.001
ecology2 999999 4995991 999999 999999 0.000 0.005 0.005 0.002
GL7d17 1548650 25978098 954861 954861 0.000 0.005 0.006 0.318
hollywood-2009 1139905 113891327 1139905 1139905 0.000 0.005 0.006 0.001
thermal2 1228045 8580313 1228045 1228045 0.000 0.005 0.006 0.001
atmosmodl 1489752 10319760 1489752 1489752 0.000 0.006 0.007 0.122
Flan_1565 1564794 117406044 1564794 1564794 0.000 0.007 0.007 0.002
af_shell10 1508065 52672325 1508065 1508065 0.000 0.006 0.007 0.002
G3_circuit 1585478 7660826 1585478 1585478 0.000 0.007 0.007 0.002
GL7d18 1955309 35590540 1548497 1548499 0.003 0.007 0.010 0.779
hvdc2 189860 1347273 189790 189860 0.004 0.010 0.001 0.005
FullChip 2987012 26621990 2986993 2987012 0.002 0.011 0.012 0.006
nlpkkt120 3542400 96845792 3542400 3542400 0.001 0.014 0.014 0.003
circuit5M_dc 3523317 19194193 3523317 3523317 0.001 0.013 0.015 0.004
Freescale1 3428755 18920347 3428755 3428755 0.001 0.013 0.015 0.003
internet 124651 207214 64689 66679 0.002 0.011 0.015 2.607
relat9 12360060 38955420 274667 274667 0.000 0.017 0.015 1.484
delaunay_n17 131072 786352 124344 131072 0.009 0.019 0.009 0.011
rajat31 4690002 20316253 4688751 4690002 0.004 0.018 0.021 0.007
circuit5M 5558326 59524291 5557120 5558326 0.004 0.021 0.022 0.421
n4c6-b8 198895 1790055 95685 163215 0.006 0.015 0.025 0.117
adaptive 6815744 27248640 6815744 6815744 0.001 0.026 0.027 0.006
nlpkkt160 8345600 229518112 8345600 8345600 0.002 0.031 0.030 0.093
soc-sign-epinions 131828 841372 44823 52876 0.019 0.032 0.033 0.061
delaunay_n19 524288 3145646 497106 524288 0.027 0.114 0.050 6.942
web-NotreDame 325729 1497134 100083 105177 0.133 0.065 0.161 0.063
delaunay_n20 1048576 6291372 993174 1048576 0.041 0.286 0.109 0.089
channel-500x100x100-b050 4802000 85362744 4801976 4802000 0.003 0.503 0.018 0.010
delaunay_n21 2097152 12582816 1987326 2097152 0.129 0.558 0.203 0.214
web-Stanford 281903 2312497 182637 192557 0.256 0.081 0.644 0.380
web-Google 916428 5105039 418303 453105 0.096 0.338 0.695 0.448
wiki-Talk 2394385 5021410 63552 76421 0.039 0.796 0.257 0.053
com-youtube 1134890 5975248 456406 551025 0.082 0.811 0.633 0.594
web-BerkStan 685230 7600595 405749 425001 0.764 0.082 0.988 0.899
roadNet-PA 1090920 3083796 916444 1059398 0.143 0.504 1.224 0.290
roadNet-TX 1393383 3843320 1158420 1342440 0.135 0.485 1.471 0.326
eu-2005 862664 19235140 642027 652328 1.536 1.863 2.072 0.943
flickr 820878 9837214 285241 367147 0.222 2.178 1.018 0.349
hugetrace-00000 4588484 13758266 4581148 4588484 1.955 2.195 0.647 0.835
in-2004 1382908 16917053 781063 804245 1.442 0.396 2.347 2.162
kron_g500-logn20 1048576 89239674 431854 513334 0.602 2.380 2.108 8.191
GL7d19 1911130 37322725 1904144 1911130 0.579 1.593 2.423 0.381
roadNet-CA 1971281 5533214 1668268 1913589 0.335 0.946 2.484 0.526
delaunay_n23 8388608 50331568 7950070 8388608 0.965 2.677 1.111 1.261
coPapersDBLP 540486 30491458 510992 540226 0.422 3.110 1.617 6.272
kron_g500-logn21 2097152 182082942 812883 964679 0.990 5.368 4.733 1.500
amazon-2008 735323 5158388 587877 641379 0.111 6.106 1.849 0.183
delaunay_n24 16777216 100663202 15892194 16777216 1.976 6.427 2.222 2.406
as-Skitter 1696415 22190596 891280 1035521 0.491 7.787 3.555 1.893
amazon0505 410236 3356824 332972 395397 0.180 9.054 1.870 22.705
wikipedia-20070206 3566907 45030389 1623931 1992408 1.090 11.976 6.521 5.244
Hamrle3 1447360 5514242 1211049 1447360 1.362 0.036 12.605 2.697
hugetrace-00020 16002413 47997626 15535760 16002413 7.895 15.952 15.016 393.135
hugebubbles-00000 18318143 54940162 18303614 18318143 13.161 19.806 5.562 3.548
wb-edu 9845725 57156537 4810825 5000334 33.824 3.375 20.355 8.606
rgg_n_2_24_s0 16777216 265114400 16772932 16777215 3.680 25.402 0.121 2.246
patents 3774768 14970767 1892820 2011083 0.883 92.029 16.182 0.842
italy_osm 6686493 14027956 6438492 6644390 5.863 1.016 122.002 1.195
soc-LiveJournal1 4847571 68993773 2831783 3835002 3.322 243.908 21.163 14.353
ljournal-2008 5363260 79023142 3941073 4355699 2.371 360.314 17.659 10.297
europe_osm 50912018 108109320 48217070 50367444 57.535 14.149 1911.564 11.211
com-livejournal 3997962 69362378 2577642 3608272 4.576 2879.362 34.282 22.456

Run times of the algorithms for permuted graphs

Graph#Rows#Non Zeros# Initial Match# Maximum MatchGPUPFPHKP-DBFS
Rucci1 1977885 7791168 109900 109900 0.000 0.002 0.003 0.449
sls 1748122 6804304 62729 62729 0.000 0.002 0.003 0.208
GL7d17 1548650 25978098 954708 954861 0.002 0.006 0.016 0.611
n4c6-b8 198895 1790055 161158 163215 0.001 0.001 0.016 0.054
internet 124651 207214 64759 66679 0.003 0.013 0.019 0.004
relat9 12360060 38955420 274667 274667 0.000 0.021 0.019 1.616
soc-sign-epinions 131828 841372 48605 52876 0.016 0.020 0.028 0.054
delaunay_n17 131072 1572642 124060 131072 0.011 0.013 0.070 0.040
GL7d18 1955309 35590540 1543717 1548499 0.008 0.012 0.169 0.845
scircuit 170998 958936 158102 170998 0.050 0.115 0.171 0.076
hvdc2 189860 1347273 177692 189860 0.028 0.053 0.237 0.065
wiki-Talk 2394385 5021410 72662 76421 0.036 0.274 0.362 0.047
web-NotreDame 325729 1497134 98867 105177 0.191 0.072 0.372 0.060
af_shell9 504855 35176450 499731 504855 0.166 0.033 0.448 0.175
delaunay_n19 524288 6291249 496883 524288 0.047 0.095 0.532 0.202
apache2 715176 9635703 682712 715176 0.064 0.156 0.657 0.266
web-Google 916428 5105039 419926 453105 0.088 0.280 0.659 0.604
ohne2 181343 11063545 178522 181343 0.143 0.026 0.693 0.326
tmt_sym 726713 10161880 694033 726713 0.071 0.146 0.800 0.266
web-Stanford 281903 2312497 173537 192557 0.291 0.084 0.982 0.469
ecology2 999999 9991944 942078 999999 0.085 0.234 1.049 0.397
audikw_1 943695 155296863 938778 943695 0.570 0.078 1.056 0.487
delaunay_n20 1048576 12582723 993808 1048576 0.103 0.271 1.074 0.489
thermal2 1228045 17160567 1173108 1228045 0.127 0.266 1.200 0.521
ldoor 952203 93042488 944653 952203 0.389 0.097 1.254 0.411
coPapersDBLP 540486 60979678 531774 540486 0.383 0.288 1.259 1.251
com-youtube 1134890 11950452 745185 865787 0.161 1.596 1.489 0.558
af_shell10 1508065 105343470 1492515 1508065 0.356 0.177 1.778 0.635
G3_circuit 1585478 15321629 1490474 1585478 0.140 0.487 1.881 0.722
web-BerkStan 685230 7600595 386209 425001 0.694 0.242 2.654 1.073
roadNet-PA 1090920 6167574 982015 1090910 0.224 1.880 2.668 1.016
flickr 820878 9837214 329996 367147 0.288 2.747 1.005 0.317
delaunay_n21 2097152 25165604 1988001 2097152 0.210 0.541 2.822 1.047
Flan_1565 1564794 234806292 1557177 1564794 0.781 0.130 3.066 0.790
GL7d19 1911130 37322725 1838758 1911130 0.700 1.980 3.671 0.458
roadNet-TX 1393383 7686623 1250208 1393238 0.332 3.505 3.925 10.662
nlpkkt120 3542400 193690832 3497214 3542400 0.623 0.831 4.348 2.090
roadNet-CA 1971281 11066410 1774432 1971264 0.391 3.047 4.893 1.885
eu-2005 862664 19235140 610512 652328 3.749 4.942 5.104 1.482
hollywood-2009 1139905 227772548 1116052 1139905 2.331 1.987 5.484 5.822
in-2004 1382908 16917053 743247 804245 3.763 1.591 5.998 10.435
channel-500x100x100-b050 4802000 170725123 4711180 4802000 0.696 0.806 6.550 2.826
circuit5M 5558326 59524291 5274741 5558326 47.808 2.205 7.048 47.960
hugetrace-00000 4588484 27516519 4198857 4588484 0.412 2.023 8.552 2.337
wikipedia-20070206 3566907 45030389 1736912 1992408 1.054 9.744 5.727 5.990
adaptive 6815744 54497261 6346591 6815744 0.676 2.417 10.668 3.450
atmosmodl 1489752 10319760 1381826 1489752 0.315 0.847 12.705 1.047
delaunay_n23 8388608 100663083 7952837 8388608 0.904 3.266 14.344 5.557
nlpkkt160 8345600 459035470 8239242 8345600 1.256 2.288 15.635 5.840
amazon0505 410236 3356824 343350 395397 0.241 17.591 2.232 15.234
FullChip 2987012 26621990 2740015 2987012 25.280 2.961 18.301 3.196
italy_osm 6686493 28055899 5958031 6686493 0.697 6.244 18.340 3.973
circuit5M_dc 3523317 19194193 3294410 3523317 6.844 4.592 20.651 2.175
Freescale1 3428755 18920347 3211857 3428755 0.686 3.715 25.721 2.087
rgg_n_2_24_s0 16777216 530228520 16399978 16777216 2.196 5.715 31.784 12.501
delaunay_n24 16777216 201326364 15902215 16777216 1.861 6.922 35.243 12.835
hugetrace-00020 16002413 95995246 14646483 16002413 1.519 8.676 38.268 9.966
hugebubbles-00000 18318143 109880310 16763441 18318143 1.798 10.031 38.970 10.907
wb-edu 9845725 57156537 4639459 5000334 17.428 9.491 51.143 20.098
Hamrle3 1447360 5514242 1243848 1447360 3.850 37.712 57.001 7.394
amazon-2008 735323 7046944 612163 698827 0.414 61.325 4.695 1.370
kron_g500-logn21 2097152 364157891 1309150 1609466 3.714 64.289 16.084 4.008
rajat31 4690002 20316253 4297395 4690002 1.754 6.057 69.545 2.524
kron_g500-logn20 1048576 178470699 684190 846526 2.372 95.982 8.542 2.261
patents 3774768 14970767 1820594 2011083 0.910 101.763 18.299 0.974
com-lj 3997962 138724427 3634946 3997962 5.883 165.324 29.396 17.190
ljournal-2008 5363260 79023142 3695167 4355699 6.898 176.686 23.454 7.580
europe_osm 50912018 216218635 45342901 50912018 7.211 68.184 197.028 37.929
soc-LiveJournal1 4847571 68993773 3228978 3835002 3.726 343.936 20.713 7.142
as-Skitter 1696415 44381027 1299610 1566909 3.268 472.635 29.629 5.739