{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:31:17Z","timestamp":1760369477785,"version":"3.37.3"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2018,8,11]],"date-time":"2018-08-11T00:00:00Z","timestamp":1533945600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2017YFB1003103"],"award-info":[{"award-number":["2017YFB1003103"]}]},{"name":"Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China","award":["18XNLG07"],"award-info":[{"award-number":["18XNLG07"]}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2017M620992"],"award-info":[{"award-number":["2017M620992"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s11227-018-2525-0","type":"journal-article","created":{"date-parts":[[2018,8,11]],"date-time":"2018-08-11T15:15:17Z","timestamp":1534000517000},"page":"6135-6155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["An adaptive breadth-first search algorithm on integrated architectures"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1983-7321","authenticated-orcid":false,"given":"Feng","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Heng","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Jidong","family":"Zhai","sequence":"additional","affiliation":[]},{"given":"Jie","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Dingyi","family":"Xiang","sequence":"additional","affiliation":[]},{"given":"Jizhong","family":"Li","sequence":"additional","affiliation":[]},{"given":"Yunpeng","family":"Chai","sequence":"additional","affiliation":[]},{"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,11]]},"reference":[{"key":"2525_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal V, Petrini F, Pasetto D, Bader DA (2010) Scalable graph exploration on multicore processors. In: Proceedings of the 2010 ACM\/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, pp 1\u201311","DOI":"10.1109\/SC.2010.46"},{"key":"2525_CR2","doi-asserted-by":"crossref","unstructured":"Ashari A, Sedaghati N, Eisenlohr J, Parthasarath S, Sadayappan P (2014) Fast sparse matrix\u2013vector multiplication on GPUs for graph applications. In: International Conference for High Performance Computing, Networking, Storage and Analysis, SC14. IEEE, pp 781\u2013792","DOI":"10.1109\/SC.2014.69"},{"key":"2525_CR3","unstructured":"AMD (2018) AMD Ryzen 5 2400G with Radeon RX Vega 11 Graphics. https:\/\/www.amd.com\/en\/products\/apu\/amd-ryzen-5-2400g"},{"issue":"3\u20134","key":"2525_CR4","first-page":"137","volume":"21","author":"S Beamer","year":"2013","unstructured":"Beamer S, Asanovi\u0107 K, Patterson D (2013) Direction-optimizing breadth-first search. Sci Program 21(3\u20134):137\u2013148","journal-title":"Sci Program"},{"key":"2525_CR5","doi-asserted-by":"crossref","unstructured":"Bouvier D, Sander B (2014) Applying AMDs Kaveri APU for heterogeneous computing. In: Hot Chips: A Symposium on High Performance Chips (HC26)","DOI":"10.1109\/HOTCHIPS.2014.7478810"},{"issue":"2","key":"2525_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163\u2013177","journal-title":"J Math Sociol"},{"issue":"2","key":"2525_CR7","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/MM.2012.2","volume":"32","author":"A Branover","year":"2012","unstructured":"Branover A, Foley D, Steinman M (2012) AMD fusion APU: Llano. IEEE Micro 32(2):28\u201337","journal-title":"IEEE Micro"},{"issue":"1","key":"2525_CR8","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","volume":"33","author":"A Broder","year":"2000","unstructured":"Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J (2000) Graph structure in the web. Comput Netw 33(1):309\u2013320","journal-title":"Comput Netw"},{"key":"2525_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: SDM, vol 4. SIAM, pp 442\u2013446","DOI":"10.1137\/1.9781611972740.43"},{"key":"2525_CR10","doi-asserted-by":"crossref","unstructured":"Chhugani J, Satish N, Kim C, Sewall J, Dubey P (2012) Fast and efficient graph traversal algorithm for CPUs: maximizing single-node efficiency. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS). IEEE, pp 378\u2013389","DOI":"10.1109\/IPDPS.2012.43"},{"key":"2525_CR11","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH (2009) Introduction to algorithms. MIT Press, Cambridge"},{"key":"2525_CR12","doi-asserted-by":"crossref","unstructured":"Daga M, Nutter M, Meswani M (2014) Efficient breadth-first search on a heterogeneous processor. In: 2014 IEEE International Conference on Big Data (Big Data). IEEE, pp 373\u2013382","DOI":"10.1109\/BigData.2014.7004254"},{"key":"2525_CR13","first-page":"89","volume":"13","author":"JJ Dongarra","year":"1997","unstructured":"Dongarra JJ, Meuer HW, Strohmaier E et al (1997) Top500 supercomputer sites. Supercomputer 13:89\u2013111","journal-title":"Supercomputer"},{"key":"2525_CR14","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"R\u00e9nyi Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s R\u00e9nyi (1959) On random graphs I. Publ Math Debr 6:290\u2013297","journal-title":"Publ Math Debr"},{"key":"2525_CR15","doi-asserted-by":"crossref","unstructured":"Hong S, Kim SK, Oguntebi T, Olukotun K (2011) Accelerating CUDA graph algorithms at maximum warp. In: ACM SIGPLAN Notices, vol 46. ACM, pp 267\u2013276","DOI":"10.1145\/2038037.1941590"},{"key":"2525_CR16","doi-asserted-by":"crossref","unstructured":"Hong S, Oguntebi T, Olukotun K (2011) Efficient parallel graph exploration on multi-core CPU and GPU. In: 2011 International Conference on Parallel Architectures and Compilation Techniques (PACT). IEEE, pp 78\u201388","DOI":"10.1109\/PACT.2011.14"},{"key":"2525_CR17","unstructured":"Intel Corporation (2014) The compute architecture of Intel processor graphics Gen7.5. https:\/\/software.intel.com\/"},{"key":"2525_CR18","volume-title":"Graph coloring problems","author":"TR Jensen","year":"2011","unstructured":"Jensen TR, Toft B (2011) Graph coloring problems, vol 39. Wiley, London"},{"key":"2525_CR19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918","volume-title":"Graph algorithms in the language of linear algebra","author":"J Kepner","year":"2011","unstructured":"Kepner J, Gilbert J (2011) Graph algorithms in the language of linear algebra. SIAM, Philadelphia"},{"issue":"1","key":"2525_CR20","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"RE Korf","year":"1985","unstructured":"Korf RE (1985) Depth-first iterative-deepening: an optimal admissible tree search. Artif Intell 27(1):97\u2013109","journal-title":"Artif Intell"},{"key":"2525_CR21","unstructured":"Korf RE, Schultze P (2005) Large-scale parallel breadth-first search. In: Association for the Advancement of Artificial Intelligence (AAAI), vol 5, pp 1380\u20131385"},{"key":"2525_CR22","doi-asserted-by":"crossref","unstructured":"Kumar P, Huang HH (2016) G-store: high-performance graph store for trillion-edge processing. In: International Conference for High Performance Computing, Networking, Storage and Analysis, SC16. IEEE, pp 830\u2013841","DOI":"10.1109\/SC.2016.70"},{"key":"2525_CR23","doi-asserted-by":"crossref","unstructured":"Li J, Tan G, Chen M, Sun N (2013) SMAT: an input adaptive auto-tuner for sparse matrix\u2013vector multiplication. In: ACM SIGPLAN Notices, vol 48. ACM, pp 117\u2013126","DOI":"10.1145\/2499370.2462181"},{"key":"2525_CR24","doi-asserted-by":"crossref","unstructured":"Liu H, Huang HH (2015) Enterprise: breadth-first graph traversal on GPUs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. ACM, p\u00a068","DOI":"10.1145\/2807591.2807594"},{"key":"2525_CR25","unstructured":"Liu H, Huang HH (2017) Graphene: fine-grained IO management for graph computing. In: USENIX Conference on File and Storage Technologies (FAST), pp 285\u2013300"},{"key":"2525_CR26","doi-asserted-by":"crossref","unstructured":"Liu H, Huang HH, Hu Y (2016) iBFS: concurrent breadth-first search on GPUs. In: Proceedings of the 2016 International Conference on Management of Data. ACM, pp 403\u2013416","DOI":"10.1145\/2882903.2882959"},{"issue":"9","key":"2525_CR27","doi-asserted-by":"publisher","first-page":"1290","DOI":"10.1016\/j.microrel.2015.06.078","volume":"55","author":"T Liu","year":"2015","unstructured":"Liu T, Chen CC, Kim W, Milor L (2015) Comprehensive reliability and aging analysis on SRAMs within microprocessor systems. Microelectron Reliab 55(9):1290\u20131296","journal-title":"Microelectron Reliab"},{"key":"2525_CR28","doi-asserted-by":"crossref","unstructured":"Liu T, Chen CC, Wu J, Milor L (2016) Sram stability analysis for different cache configurations due to bias temperature instability and hot carrier injection. In: 2016 IEEE 34th International Conference on Computer Design (ICCD). IEEE, pp 225\u2013232","DOI":"10.1109\/ICCD.2016.7753284"},{"key":"2525_CR29","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jpdc.2015.06.010","volume":"85","author":"W Liu","year":"2015","unstructured":"Liu W, Vinter B (2015) A framework for general sparse matrix\u2013matrix multiplication on GPUs and heterogeneous processors. J Parallel Distrib Comput 85:47\u201361","journal-title":"J Parallel Distrib Comput"},{"key":"2525_CR30","doi-asserted-by":"crossref","unstructured":"Liu W, Vinter B (2015) CSR5: an efficient storage format for cross-platform sparse matrix\u2013vector multiplication. In: Proceedings of the 29th ACM on International Conference on Supercomputing. ACM, pp 339\u2013350","DOI":"10.1145\/2751205.2751209"},{"key":"2525_CR31","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.parco.2015.04.004","volume":"49","author":"W Liu","year":"2015","unstructured":"Liu W, Vinter B (2015) Speculative segmented sum for sparse matrix\u2013vector multiplication on heterogeneous processors. Parallel Comput 49:179\u2013193","journal-title":"Parallel Comput"},{"key":"2525_CR32","doi-asserted-by":"crossref","unstructured":"Luo L, Wong M, Hwu W (2010) An effective GPU implementation of breadth-first search. In: Proceedings of the 47th Design Automation Conference. ACM, pp 52\u201355","DOI":"10.1145\/1837274.1837289"},{"key":"2525_CR33","doi-asserted-by":"crossref","unstructured":"Merrill D, Garland M, Grimshaw A (2012) Scalable GPU graph traversal. In: ACM SIGPLAN Notices, vol 47. ACM, pp 117\u2013128","DOI":"10.1145\/2370036.2145832"},{"key":"2525_CR34","unstructured":"Murphy RC, Wheeler KB, Barrett BW, Ang JA (2010) Introducing the Graph 500. In: Cray Users Group (CUG) Proceedings"},{"key":"2525_CR35","unstructured":"YOKOGAWA (2017) WT210\/WT230 digital power meters. http:\/\/tmi.yokogawa.com\/products\/digital-power-analyzers\/"},{"key":"2525_CR36","doi-asserted-by":"crossref","unstructured":"Nikolskiy VP, Stegailov VV, Vecher VS (2016) Efficiency of the Tegra K1 and X1 systems-on-chip for classical molecular dynamics. In: 2016 International Conference on High Performance Computing and Simulation (HPCS). IEEE, pp 682\u2013689","DOI":"10.1109\/HPCSim.2016.7568401"},{"key":"2525_CR37","doi-asserted-by":"crossref","unstructured":"Pearce R, Gokhale M, Amato NM (2013) Scaling techniques for massive scale-free graphs in distributed (external) memory. In: 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS). IEEE, pp 825\u2013836","DOI":"10.1109\/IPDPS.2013.72"},{"key":"2525_CR38","unstructured":"Saad Y (1990) SPARSKIT: a basic tool kit for sparse matrix computations. NASA technical report, NASA, pp 1\u201330"},{"key":"2525_CR39","doi-asserted-by":"crossref","unstructured":"Satish N, Sundaram N, Patwary MMA, Seo J, Park J, Hassaan MA, Sengupta S, Yin Z, Dubey P (2014) Navigating the maze of graph analytics frameworks using massive graph datasets. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. ACM, pp 979\u2013990","DOI":"10.1145\/2588555.2610518"},{"issue":"10","key":"2525_CR40","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1109\/TPDS.2007.70811","volume":"19","author":"DP Scarpazza","year":"2008","unstructured":"Scarpazza DP, Villa O, Petrini F (2008) Efficient breadth-first search on the Cell\/BE processor. IEEE Trans Parallel Distrib Syst 19(10):1381\u20131395","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"2525_CR41","doi-asserted-by":"crossref","unstructured":"Sedaghati N, Mu T, Pouchet LN, Parthasarathy S, Sadayappan P (2015) Automatic selection of sparse matrix representation on GPUs. In: Proceedings of the 29th ACM on International Conference on Supercomputing, ICS \u201915, pp 99\u2013108","DOI":"10.1145\/2751205.2751244"},{"issue":"6","key":"2525_CR42","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/3128571","volume":"50","author":"X Shi","year":"2018","unstructured":"Shi X, Zheng Z, Zhou Y, Jin H, He L, Liu B, Hua QS (2018) Graph processing on GPUs: a survey. ACM Comput Surv 50(6):81","journal-title":"ACM Comput Surv"},{"issue":"3","key":"2525_CR43","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/MCSE.2010.69","volume":"12","author":"JE Stone","year":"2010","unstructured":"Stone JE, Gohara D, Shi G (2010) OpenCL: a parallel programming standard for heterogeneous computing systems. Comput Sci Eng 12(3):66\u201373","journal-title":"Comput Sci Eng"},{"key":"2525_CR44","unstructured":"Su BY, Keutzer K (2012) clSpMV: a cross-platform OpenCL SpMV framework on GPUs. In: Proceedings of the 26th ACM International Conference on Supercomputing. ACM, pp 353\u2013364"},{"key":"2525_CR45","doi-asserted-by":"crossref","unstructured":"Wang X, Liu W, Xue W, Wu L (2018) swSpTRSV: a fast sparse triangular solve with sparse level tile layout on sunway architectures. In: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, pp 338\u2013353","DOI":"10.1145\/3178487.3178513"},{"key":"2525_CR46","doi-asserted-by":"crossref","unstructured":"Wang Y, Davidson A, Pan Y, Wu Y, Riffel A, Owens JD (2016) Gunrock: a high-performance graph processing library on the GPU. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, p\u00a011","DOI":"10.1145\/2851141.2851145"},{"key":"2525_CR47","doi-asserted-by":"crossref","unstructured":"Yan S, Li C, Zhang Y, Zhou H (2014) yaSpMV: yet another SpMV framework on GPUs. In: ACM SIGPLAN Notices, vol 49. ACM, pp 107\u2013118","DOI":"10.1145\/2692916.2555255"},{"key":"2525_CR48","doi-asserted-by":"crossref","unstructured":"Yang C, Buluc A, Owens JD (2018) Implementing push\u2013pull efficiently in GraphBLAS. In: International Conference on Parallel Processing (ICPP)","DOI":"10.1145\/3225058.3225122"},{"key":"2525_CR49","doi-asserted-by":"crossref","unstructured":"Yasui Y, Fujisawa K (2015) Fast and scalable NUMA-based thread parallel breadth-first search. In: 2015 International Conference on High Performance Computing and Simulation (HPCS). IEEE, pp 377\u2013385","DOI":"10.1109\/HPCSim.2015.7237065"},{"key":"2525_CR50","doi-asserted-by":"crossref","unstructured":"Zhang F, Zhai J, Chen W, He B, Zhang S (2015) To co-run, or not to co-run: a performance study on integrated architectures. In: 2015 IEEE 23rd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). IEEE, pp 89\u201392","DOI":"10.1109\/MASCOTS.2015.27"},{"key":"2525_CR51","doi-asserted-by":"crossref","unstructured":"Zhang F, Wu B, Zhai J, He B, Chen W (2017) FinePar: irregularity-aware fine-grained workload partitioning on integrated architectures. In: International Symposium on Code Generation and Optimization (CGO). IEEE Press, pp 27\u201338","DOI":"10.1109\/CGO.2017.7863726"},{"issue":"3","key":"2525_CR52","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1109\/TPDS.2016.2586074","volume":"28","author":"F Zhang","year":"2017","unstructured":"Zhang F, Zhai J, He B, Zhang S, Chen W (2017) Understanding co-running behaviors on integrated CPU\/GPU architectures. IEEE Trans Parallel Distrib Syst 28(3):905\u2013918","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"2525_CR53","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.microrel.2017.06.040","volume":"76","author":"R Zhang","year":"2017","unstructured":"Zhang R, Liu T, Yang K, Milor L (2017) Analysis of time-dependent dielectric breakdown induced aging of SRAM cache with different configurations. Microelectron Reliab 76:87\u201391","journal-title":"Microelectron Reliab"},{"issue":"6","key":"2525_CR54","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1109\/TPDS.2013.111","volume":"25","author":"J Zhong","year":"2014","unstructured":"Zhong J, He B (2014) Medusa: simplified graph processing on GPUs. IEEE Trans Parallel Distrib Syst 25(6):1543\u20131552","journal-title":"IEEE Trans Parallel Distrib Syst"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-018-2525-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-018-2525-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-018-2525-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T09:01:14Z","timestamp":1693818074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-018-2525-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,11]]},"references-count":54,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["2525"],"URL":"https:\/\/doi.org\/10.1007\/s11227-018-2525-0","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2018,8,11]]},"assertion":[{"value":"11 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}