{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T20:40:01Z","timestamp":1741034401780,"version":"3.38.0"},"reference-count":25,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2014,2,28]],"date-time":"2014-02-28T00:00:00Z","timestamp":1393545600000},"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":[[2014,8]]},"abstract":"<jats:p> Data-intensive applications have drawn more and more attention in the last few years. The basic graph traversal algorithm, the breadth-first search (BFS), a typical data-intensive application, is widely used and the Graph 500 benchmark uses it to rank the performance of supercomputers. The Intel Many Integrated Core (MIC) architecture, which is designed for highly parallel computing, has not been fully evaluated for graph traversal. In this paper, we discuss how to use the MIC to accelerate the BFS. We present some optimizations for native BFS algorithms and develop a heterogeneous BFS algorithm. For the native BFS algorithm, we mainly discuss how to exploit many cores and wide-vector processing units. The performance of our optimized native BFS implementation is 5.3 times that of the highest published performance for graphics processing units (GPU). For the heterogeneous BFS algorithm, the performance of the general processing unit (CPU) and MIC cooperative computing can gain an increase in speed of approximately 1.4 times than that of a CPU for graphs with 2M vertices. This work is valuable for using a MIC to accelerate the BFS. It is also a general guidance for a MIC used for data-intensive applications. <\/jats:p>","DOI":"10.1177\/1094342014524240","type":"journal-article","created":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T05:32:54Z","timestamp":1393651974000},"page":"255-266","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":26,"title":["Using the Intel Many Integrated Core to accelerate graph traversal"],"prefix":"10.1177","volume":"28","author":[{"given":"Tao","family":"Gao","sequence":"first","affiliation":[{"name":"State Key Laboratory of High Performance Computing, China"},{"name":"School of Computer Science, National University of Defense Technology, China"}]},{"given":"Yutong","family":"Lu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of High Performance Computing, China"},{"name":"School of Computer Science, National University of Defense Technology, China"}]},{"given":"Baida","family":"Zhang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of High Performance Computing, China"},{"name":"School of Computer Science, National University of Defense Technology, China"}]},{"given":"Guang","family":"Suo","sequence":"additional","affiliation":[{"name":"State Key Laboratory of High Performance Computing, China"},{"name":"School of Computer Science, National University of Defense Technology, China"}]}],"member":"179","published-online":{"date-parts":[[2014,2,28]]},"reference":[{"key":"bibr1-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"key":"bibr2-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"bibr3-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.34"},{"key":"bibr4-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"bibr5-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.50"},{"key":"bibr6-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1007\/s10827-007-0038-6"},{"key":"bibr7-1094342014524240","first-page":"65","volume-title":"2011 ACM\/IEEE international conference for high performance computing, networking, storage and analysis (SC11)","author":"Bulu\u00e7 A","year":"2011"},{"key":"bibr8-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"bibr9-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.25"},{"key":"bibr10-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.43"},{"key":"bibr11-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1126\/science.1081058"},{"key":"bibr12-1094342014524240","doi-asserted-by":"crossref","unstructured":"Duran A, Klemm M (2011) The Intel Many Integrated Core architecture, Intel Corporation.","DOI":"10.1109\/HPCSim.2012.6266938"},{"key":"bibr13-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"bibr14-1094342014524240","first-page":"985","volume":"11","author":"Leskovec J","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"bibr15-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"bibr16-1094342014524240","unstructured":"Manyika J, Chui M, Brown B, (2011) Big data: the next frontier for innovation, competition, and productivity, McKinsey Global Institute."},{"key":"bibr17-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"key":"bibr18-1094342014524240","unstructured":"Murphy RC, Wheeler KB, Barrett BW, (2010) Introducing the Graph 500, Cray User\u2019s Group (CUG)."},{"key":"bibr19-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.70"},{"key":"bibr20-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.204"},{"key":"bibr21-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.197"},{"key":"bibr22-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"bibr23-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-010-0383-x"},{"key":"bibr24-1094342014524240","doi-asserted-by":"publisher","DOI":"10.4028\/www.scientific.net\/AMR.709.555"},{"key":"bibr25-1094342014524240","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2005.4"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342014524240","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342014524240","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342014524240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T20:02:24Z","timestamp":1741032144000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342014524240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,28]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1177\/1094342014524240"],"URL":"https:\/\/doi.org\/10.1177\/1094342014524240","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2014,2,28]]}}}