Engineering a Scalable High Quality Graph Partitioner
-
Autor:
Manuel Holtgrewe, Peter Sanders, Christian Schulz
-
Quelle:
IPDPS'10
- Datum: April 2010
Links
Ergebnisse unseres Parallelen Graph Partitionierer Kappa im WalshawBenchmark (Stand 16.4.2010)
Results with up to 0% imbalance
| graph | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|
| data | - | 383 (713) | - | - | - | - |
| uk | - | 43 (1206) | - | - | - | - |
| add32 | - | - | - | - | - | 493 (78) |
| bcsstk29 | - | 8159 (3498) | - | - | - | - |
| bcsstk32 | - | 9492 (11153) | - | - | - | - |
| fe_tooth | - | 7142 (19534) | 11935 (9767) | 18382 (4884) | - | - |
| fe_rotor | - | 7480 (24905) | 13292 (12453) | - | - | - |
| 598a | - | 8154 (27743) | - | 26427 (6936) | - | - |
| fe_ocean | - | 1902 (35860) | 4299 (17930) | - | - | - |
| 144 | - | 15804 (36163) | 26175 (18082) | - | 58462 (4521) | - |
| wave | - | 17475 (39080) | 30511 (19540) | - | - | - |
| m14b | - | 13391 (53692) | - | - | - | - |
| auto | - | 28048 (112174) | - | - | - | - |
Results with up to 1% imbalance
| graph | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|
| data | - | 383 (713) | - | - | - | - |
| add32 | - | - | - | - | - | 493 (78) |
| bcsstk29 | - | 8159 (3498) | - | - | - | - |
| memplus | - | 9559 (4442) | - | - | - | - |
| fe_pwt | - | 704 (9220) | - | - | 5612 (1149) | - |
| bcsstk32 | - | 9492 (11153) | - | - | - | - |
| fe_body | - | 636 (11308) | - | 1931 (2833) | - | - |
| fe_tooth | - | - | 11935 (9767) | - | - | - |
| fe_rotor | - | 7480 (24905) | - | - | - | - |
| 598a | - | 8154 (27743) | 16467 (13875) | 26427 (6936) | 40674 (3470) | - |
| fe_ocean | - | - | - | 8432 (8987) | 13660 (4487) | 21548 (2253) |
| wave | - | 17475 (39080) | 30511 (19540) | 44611 (9771) | 64551 (4886) | - |
| m14b | - | 13391 (53692) | 26666 (26847) | 43975 (13424) | - | - |
| auto | - | - | 47650 (56088) | 79847 (28045) | - | - |
Results with up to 3% imbalance
| graph | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|
| add32 | - | - | - | - | - | 493 (78) |
| wing_nodal | - | 3561 (2817) | - | - | - | - |
| bcsstk30 | - | 16537 (7385) | 34513 (3724) | - | - | - |
| bcsstk31 | - | 2676 (18127) | 7181 (9161) | - | - | - |
| fe_pwt | - | 704 (9220) | 1419 (4698) | - | - | - |
| bcsstk32 | - | 8799 (11471) | 21023 (5689) | 36613 (2872) | - | - |
| fe_body | - | 601 (11543) | 1054 (5789) | 1800 (2902) | 2947 (1451) | - |
| brack2 | - | 2839 (16126) | - | - | - | - |
| fe_tooth | - | 6946 (20094) | 11662 (10038) | 17760 (5030) | - | - |
| fe_rotor | 1963 (51254) | 7222 (25488) | 12852 (12748) | - | - | - |
| 598a | - | 7955 (28525) | 25966 (7143) | 39829 (3572) | - | |
| fe_ocean | - | 1698 (36802) | 3974 (18462) | - | - | 21033 (2309) |
| 144 | - | - | 25491 (18621) | - | - | - |
| wave | - | 16936 (40173) | 28839 (20118) | 43063 (10062) | 62743 (5031) | 87325 (2516) |
| m14b | - | 13136 (55296) | 26057 (27620) | 42783 (13809) | 67326 (6913) | 100286 (3456) |
| auto | - | 26379 (115523) | 45525 (57768) | 77611 (28884) | 122902 (14442) | - |
Results with up to 5% imbalance
| graph | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|
| add32 | - | - | - | - | - | 493 (78) |
| cti | - | 890 (4420) | - | - | - | - |
| bcsstk30 | - | 16332 (7592) | 34350 (3755) | - | - | - |
| bcsstk31 | 2676 (18127) | 7152 (9298) | - | - | - | - |
| fe_pwt | - | 701 (9490) | 1409 (4761) | 2777 (2394) | 5546 (1199) | - |
| bcsstk32 | - | 4644 (23384) | 8481 (11710) | 35965 (2928) | - | - |
| fe_body | - | 601 (11543) | 1054 (5789) | 1784 (2958) | 2887 (1479) | 4888 (740) |
| brack2 | - | 2739 (16440) | 6781 (8220) | - | - | - |
| fe_tooth | - | 6864 (20398) | 11662 (10038) | 17603 (5128) | - | - |
| fe_rotor | 1955 (51715) | 7045 (26150) | 12566 (13074) | 20132 (6537) | - | - |
| 598a | - | 7851 (29080) | 15721 (14563) | 25808 (7280) | 39369 (3639) | 58031 (1820) |
| fe_ocean | - | 1697 (37639) | 3941 (18782) | 7722 (9413) | - | 20667 (2354) |
| 144 | - | - | 25259 (18975) | 38225 (9492) | 56926 (4746) | - |
| wave | - | 16820 (41030) | 28700 (20483) | 42800 (10258) | 62520 (5129) | 86663 (2565) |
| m14b | - | 13136 (55296) | 25679 (28169) | 42608 (14093) | 66793 (7046) | 99063 (3523) |
| auto | - | 25883 (117519) | 45039 (58860) | 76488 (29446) | 122378 (14723) | 173968 (7361) |