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 Match | GPU | PFP | HK | P-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 Match | GPU | PFP | HK | P-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 |