{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T16:10:19Z","timestamp":1689351019005},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,6,26]],"date-time":"2014-06-26T00:00:00Z","timestamp":1403740800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1007\/s11227-014-1239-1","type":"journal-article","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T12:57:04Z","timestamp":1403701024000},"page":"1462-1490","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exploiting fine-grained parallelism in graph traversal algorithms via lock virtualization on multi-core architecture"],"prefix":"10.1007","volume":"69","author":[{"given":"Jie","family":"Yan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guangming","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ninghui","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,6,26]]},"reference":[{"key":"1239_CR1","doi-asserted-by":"crossref","unstructured":"Asanovic K, Bodik R, Demmel J, Keaveny T, Keutzer K, Kubiatowicz J et al (2009) A view of the parallel computing landscape. In: Proceedings of communications of the ACM, p 52","DOI":"10.1145\/1562764.1562783"},{"key":"1239_CR2","unstructured":"National Research Council (2013) Frontiers in massive data analysis. The National Academies Press, Washington"},{"issue":"1","key":"1239_CR3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1142\/S0129626407002843","volume":"7","author":"A Lumsdaine","year":"2007","unstructured":"Lumsdaine A, Gregor D, Hendrickson B, Berry JW (2007) Challenges in parallel graph processing. Parallel Process Lett 7(1):5\u201320","journal-title":"Parallel Process Lett"},{"key":"1239_CR4","doi-asserted-by":"crossref","unstructured":"Malewicz G, Austern M, Bik A, Dehnert J, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceeding of SIGMOD\u201910, Indianapolis, USA, 2010","DOI":"10.1145\/1807167.1807184"},{"key":"1239_CR5","unstructured":"Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) PowerGraph: distributed graph-parallel computation on natural graphs. In: Proceedings of the 10th OSDI, Hollywood, Oct 2012"},{"key":"1239_CR6","doi-asserted-by":"crossref","unstructured":"Shun J, Belloch G (2013) Ligra: a lightweight graph processing framework for shared memory. In: Proceeding of PPoPP\u201913, Shenzhen, China, Feb 2013","DOI":"10.1145\/2442516.2442530"},{"key":"1239_CR7","unstructured":"Gregor D, Lumsdaine A (2005) The parallel BGL: a generic library for distributed graph computations. In: Proceeding of POOSC\u201905, Bloomington, July 2005"},{"key":"1239_CR8","unstructured":"Graph500 benchmark (2010). http:\/\/www.graph500.org . Accessed 23 June 2014"},{"key":"1239_CR9","unstructured":"Bader D, Feo J, Gilbert J, Kepner J, Koester D, Loh E, Madduri K, Mann W, Meuse T (2007) HPCS scalable synthetic compact applications #2 graph analysis (ssca#2 v2.2 specification), Sep 2007"},{"issue":"1","key":"1239_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2008","unstructured":"Leskovec J, Lang K, Dasgupta A, Mahoney W (2008) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29\u2013123","journal-title":"Internet Math"},{"key":"1239_CR11","unstructured":"Bader DA, Madduri K (2008) SNAP, small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks. In: Proceedings of IPDPS, pp 1\u201312"},{"key":"1239_CR12","doi-asserted-by":"crossref","unstructured":"Tu D, Tan G (2009) Characterizing betweenness centrality algorithm on multi-core architectures. In: Proceedings of international symposium on parallel and distributed processing with applications, pp 182\u2013189","DOI":"10.1109\/ISPA.2009.18"},{"key":"1239_CR13","unstructured":"Cray XMT (2014). http:\/\/www.cray.com\/Assets\/PDF\/products\/xmt\/CrayXMTBrochure.pdf . Accessed 23 June 2014"},{"key":"1239_CR14","doi-asserted-by":"crossref","unstructured":"Zhu W, Sreedhar VC, Hu Z, Gao GR (2007) Synchronization state buffer: supporting efficient fine-grain synchronization on many-core architectures. In: Proceedings of ISCA \u201907 San Diego, USA, 2007","DOI":"10.1145\/1250662.1250668"},{"key":"1239_CR15","doi-asserted-by":"crossref","unstructured":"Fraser K, Harris T (2007) Concurrent programming without locks. In: Proceedings of ACM transactions on computer systems, vol 25, issue 2, May 2007","DOI":"10.1145\/1233307.1233309"},{"key":"1239_CR16","unstructured":"Michael MM, Scott ML (1996) Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the 15th annual ACM symposium on principles of distributed computing, PODC \u201996"},{"key":"1239_CR17","doi-asserted-by":"crossref","unstructured":"Herlihy M, Moss JEB (1993) Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th annual international symposium on computer architecture, ISCA \u201993","DOI":"10.1145\/165123.165164"},{"key":"1239_CR18","doi-asserted-by":"crossref","unstructured":"Harris T, Larus J, Rajwar R (2010) Transactional memory. In: Proceedings of synthesis lectures on computer architecture. Morgan & Claypool Publisher, San Rafael, USA, June 2010","DOI":"10.1007\/978-3-031-01728-5"},{"key":"1239_CR19","doi-asserted-by":"crossref","unstructured":"Kulkarni M, Pingali K, Walter B, Ramanarayanan G, Bala K, Chew LP (2007) Optimistic parallelism requires abstractions. In: Proceedings of PLDI \u201907, vol 7, San Diego, USA, June 2007","DOI":"10.1145\/1250734.1250759"},{"key":"1239_CR20","doi-asserted-by":"crossref","unstructured":"Hammond L, Wong V, Chen M, Carlstrom BD, Davis JD, Hertzberg B, Prabhu MK, Wijaya H, Kozyrakis C, Olukotun K (2004) Transactional memory coherence and consistency. In: Proceedings of the 31st annual international symposium on computer architecture, ISCA \u201904","DOI":"10.1109\/ISCA.2004.1310767"},{"key":"1239_CR21","unstructured":"Yan J, Tan G, Zhang X, Yao E, Sun N (2013) vLock: lock virtualization mechanism for exploiting fine-grained parallelism in graph traversal algorithms. In: Proceedings of IEEE\/ACM symposium on code generation and optimization (CGO \u201913), pp 141\u2013150"},{"key":"1239_CR22","unstructured":"Intel Corporation (2014) Intel 64 and IA-32 architectures optimization reference manual. pp c1\u2013c26"},{"key":"1239_CR23","doi-asserted-by":"crossref","unstructured":"Bertsekas DP, Guerriero F, Musmanno R (1996) Parallel asynchronous label correcting methods for shortest paths. J Optim Theory Appl 88(2):297\u2013320","DOI":"10.1007\/BF02192173"},{"key":"1239_CR24","doi-asserted-by":"crossref","unstructured":"Pearce R, Gokhale M, Amato NM (2010) Multithreaded asynchronous graph traversal for in-memory and semi-external memory. In: Proceeding of SC\u201910, New Orleans, Louisiana, USA, Nov 2010","DOI":"10.1109\/SC.2010.34"},{"key":"1239_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y Shiloach","year":"1982","unstructured":"Shiloach Y, Vishkin U (1982) An o(log n) parallel connectivity algorithm. J Algorithms 3:57\u201367","journal-title":"J Algorithms"},{"key":"1239_CR26","doi-asserted-by":"crossref","unstructured":"Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. In: Proceedings of computer networks and ISDN systems. Elsevier Science Publishers, Oxford, UK pp 107\u2013117","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"1239_CR27","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: Proceedings of SDM\u201904, Toronto, Canada, August 2004","DOI":"10.1137\/1.9781611972740.43"},{"key":"1239_CR28","doi-asserted-by":"crossref","unstructured":"Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media?. In: Proceedings of www\u201910, Raleigh, NC, USA pp 591\u2013600","DOI":"10.1145\/1772690.1772751"},{"issue":"2","key":"1239_CR29","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1480506.1480511","volume":"42","author":"P Boldi","year":"2008","unstructured":"Boldi P, Codenotti B, Santini M, Vigna S (2008) A large time-aware graph. SIGIR Forum 42(2):33\u201338","journal-title":"SIGIR Forum"},{"key":"1239_CR30","unstructured":"LAWS datasets (2014). http:\/\/law.di.unimi.it\/datasets.php . Accessed 23 June 2014"},{"key":"1239_CR31","unstructured":"Yan J, Tan G, Sun N (2013) Graphine: programming graph-parallel computation of large natural graphs on multicore cluster, technical report, ICT-HPC-2013-2"},{"key":"1239_CR32","unstructured":"UPC Consortium (2013) UPC language and library specifications v1.3, Lawrence Berkeley National Lab, technical report LBNL-6623E, Nov 2013"},{"key":"1239_CR33","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1023\/A:1019751632622","volume":"7","author":"BE Akgul","year":"2002","unstructured":"Akgul BE, Mooney VJ (2002) The system-on-a-chip Lock Cache. Int J Des Autom Embed Syst 7:139\u2013174","journal-title":"Int J Des Autom Embed Syst"},{"key":"1239_CR34","doi-asserted-by":"crossref","unstructured":"Feo J, Harper D, Kahan S, Konecny P (2005) Eldorado. In: Proceedings of the 2nd conference on computing frontiers, CF \u201905, New York, NY, USA, pp 28\u201334","DOI":"10.1145\/1062261.1062268"},{"key":"1239_CR35","doi-asserted-by":"crossref","unstructured":"Steffan JG, Colohan CB, Zhai A, Mowry TC (2000) A scalable approach to thread-level speculation. In: Proceedings of the 27th annual international symposium on computer architecture, ISCA \u201900","DOI":"10.1145\/339647.339650"},{"key":"1239_CR36","doi-asserted-by":"crossref","unstructured":"Afek Y, Dauber D, Touitou D (1995) Wait-free made fast. In: Proceedings of the twenty-seventh annual ACM symposium on theory of computing (STOC \u201995)","DOI":"10.1145\/225058.225271"},{"key":"1239_CR37","doi-asserted-by":"crossref","unstructured":"Valois JD (1995) Lock-free linked lists using compare-and-swap. In: Proceedings of the 14th annual ACM symposium on principles of distributed computing, PODC \u201995","DOI":"10.1145\/224964.224988"},{"key":"1239_CR38","doi-asserted-by":"crossref","unstructured":"Michael MM (2002) High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th annual ACM symposium on parallel algorithms and architectures, SPAA \u201902","DOI":"10.1145\/564870.564881"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-014-1239-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-014-1239-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-014-1239-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T15:29:52Z","timestamp":1689348592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-014-1239-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,26]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["1239"],"URL":"https:\/\/doi.org\/10.1007\/s11227-014-1239-1","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,26]]}}}