{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T18:40:41Z","timestamp":1785955241373,"version":"3.56.0"},"reference-count":57,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2011,5,19]],"date-time":"2011-05-19T00:00:00Z","timestamp":1305763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>This paper presents a scalable high-performance software library to be used for graph analysis and data mining. Large combinatorial graphs appear in many applications of high-performance computing, including computational biology, informatics, analytics, web search, dynamical systems, and sparse matrix methods. Graph computations are difficult to parallelize using traditional approaches due to their irregular nature and low operational intensity. Many graph computations, however, contain sufficient coarse-grained parallelism for thousands of processors, which can be uncovered by using the right primitives. We describe the parallel Combinatorial BLAS, which consists of a small but powerful set of linear algebra primitives specifically targeting graph and data mining applications. We provide an extensible library interface and some guiding principles for future development. The library is evaluated using two important graph algorithms, in terms of both performance and ease-of-use. The scalability and raw performance of the example applications, using the Combinatorial BLAS, are unprecedented on distributed memory clusters.<\/jats:p>","DOI":"10.1177\/1094342011403516","type":"journal-article","created":{"date-parts":[[2011,5,19]],"date-time":"2011-05-19T20:35:32Z","timestamp":1305837332000},"page":"496-509","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":292,"title":["The Combinatorial BLAS: design, implementation, and applications"],"prefix":"10.1177","volume":"25","author":[{"given":"Ayd\u0131n","family":"Bulu\u00e7","sequence":"first","affiliation":[{"name":"High Performance Computing Research, Lawrence Berkeley National Laboratory, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John R","family":"Gilbert","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2011,5,19]]},"reference":[{"key":"bibr1-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.1"},{"key":"bibr2-1094342011403516","doi-asserted-by":"publisher","DOI":"10.2172\/5604546"},{"key":"bibr3-1094342011403516","unstructured":"Asanovic K., Bodik R., Catanzaro B., Gebis J., Husbands P., Keutzer K. (2006). The landscape of parallel computing research: A view from Berkeley. Technical Report UCB\/EECS-2006-183 EECS Department, University of California at Berkeley. http:\/\/www.eecs.berkeley.edu\/Pubs\/TechRpts\/2006\/EECS-2006-183.html."},{"key":"bibr4-1094342011403516","unstructured":"Bader D., Feo J., Gilbert J., Kepner J., Koester D., Loh E. (a) HPCS scalable synthetic compact applications #2. Version 1.1. http:\/\/www.highproductivity.org\/SSCABmks.htm."},{"key":"bibr5-1094342011403516","unstructured":"Bader D., Gilbert J., Kepner J., Madduri K. (b) HPC graph analysis benchmark. http:\/\/www.graphanalysis.org\/benchmark."},{"key":"bibr6-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_10"},{"key":"bibr7-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.57"},{"key":"bibr8-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.34"},{"key":"bibr9-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536261"},{"key":"bibr10-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1986-6_8"},{"key":"bibr11-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161102"},{"key":"bibr12-1094342011403516","volume-title":"Scientific and Engineering C++: An Introduction with Advanced Techniques and Examples","author":"Barton J. J.","year":"1994"},{"key":"bibr13-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2007.370685"},{"key":"bibr14-1094342011403516","volume-title":"Vector Models for Data-Parallel Computing","author":"Blelloch GE.","year":"1990"},{"key":"bibr15-1094342011403516","volume-title":"Technical Report CSD-02-1207, Computer Science Division","author":"Bonachea D.","year":"2002"},{"key":"bibr16-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"bibr17-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505"},{"key":"bibr18-1094342011403516","volume-title":"HotPar\u201909: Proceedings of the 1st USENIX Workshop on Hot Topics in Parallelism","author":"Brodman J. C.","year":"2009"},{"key":"bibr19-1094342011403516","unstructured":"Bulu\u00e7 A. (2010). Linear Algebraic Primitives for Parallel Computing on Large Graphs. PhD thesis, University of California, Santa Barbara."},{"key":"bibr20-1094342011403516","first-page":"233","volume-title":"Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Bulu\u00e7 A","year":"2009"},{"key":"bibr21-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2008.45"},{"key":"bibr22-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"bibr23-1094342011403516","unstructured":"Bulu\u00e7 A., Gilbert J. R. (2010). Highly parallel sparse matrix\u2013matrix multiplication. Technical Report UCSB-CS-2010-10, Computer Science Department, University of California Santa Barbara. http:\/\/arxiv.org\/abs\/1006.2183."},{"key":"bibr24-1094342011403516","volume-title":"Proceedings of the Workshop on Multiple Paradigm with OO Languages (MPOOL)","author":"Burrus N.","year":"2003"},{"key":"bibr25-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/6041.6042"},{"key":"bibr26-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"bibr27-1094342011403516","first-page":"24","volume":"7","author":"Coplien J. O.","year":"1995","journal-title":"C++ Report"},{"key":"bibr28-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"bibr29-1094342011403516","volume-title":"Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide","author":"Dongarra J.","year":"2000"},{"key":"bibr30-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567810"},{"key":"bibr31-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/HIPC.2010.5713180"},{"key":"bibr32-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918.ch5"},{"key":"bibr33-1094342011403516","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"bibr34-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2008.45"},{"key":"bibr35-1094342011403516","volume-title":"Introduction to Parallel Computing: Design and Analysis of Algorithms","author":"Grama A.","year":"2003"},{"key":"bibr36-1094342011403516","volume-title":"Workshop on Parallel Object-Oriented Scientific Computing (POOSC)","author":"Gregor D.","year":"2005"},{"key":"bibr37-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089021"},{"key":"bibr38-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39815-8_14"},{"key":"bibr39-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718126"},{"key":"bibr40-1094342011403516","unstructured":"Kirsch C., Payer H., R\u00f6ck H (2010). Scal: Non-linearizable computing breaks the scalability barrier. Technical Report 2010-07, Department of Computer Sciences, University of Salzburg."},{"key":"bibr41-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"bibr42-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"bibr43-1094342011403516","doi-asserted-by":"publisher","DOI":"10.2172\/951102"},{"key":"bibr44-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"bibr45-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1177\/1094342006064503"},{"key":"bibr46-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1177\/1094342006064504"},{"key":"bibr47-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/1048935.1050204"},{"key":"bibr48-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918.ch6"},{"key":"bibr49-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"bibr50-1094342011403516","doi-asserted-by":"crossref","unstructured":"Shah V., Gilbert J. R. (2004). Sparse matrices in Matlab*P: Design and implementation. Lecture Notes in Computer Science 3296: 144\u2013155. URL http:\/\/gauss.cs.ucsb.edu\/publication\/dsparse.pdf.","DOI":"10.1007\/978-3-540-30474-6_20"},{"key":"bibr51-1094342011403516","volume-title":"The Boost Graph Library User Guide and Reference Manual (With CD-ROM)","author":"Siek J. G.","year":"2001"},{"key":"bibr52-1094342011403516","first-page":"1","author":"Tan G.","year":"2009","journal-title":"The Journal of Supercomputing"},{"key":"bibr53-1094342011403516","unstructured":"University of Texas (2011). Lonestar User Guide. http:\/\/services.tacc.utexas.edu\/index.php\/lonestar-user-guide.\n."},{"key":"bibr54-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"bibr55-1094342011403516","unstructured":"Van Dongen S. (2000). MCL \u2013 a cluster algorithm for graphs. http:\/\/www.micans.org\/mcl\/index.html."},{"key":"bibr56-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1137\/040608635"},{"key":"bibr57-1094342011403516","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161014"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342011403516","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342011403516","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342011403516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:19:02Z","timestamp":1777450742000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342011403516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,19]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.1177\/1094342011403516"],"URL":"https:\/\/doi.org\/10.1177\/1094342011403516","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,19]]}}}