Graphfire: Synergizing Fetch, Insertion, and Replacement Policies for Graph Analytics

Manocha, Aninda; Aragón, J.L.; Martonosi, Margaret

Publication:
Graphfire: Synergizing Fetch, Insertion, and Replacement Policies for Graph Analytics

dc.contributor.author	Manocha, Aninda
dc.contributor.author	Aragón, J.L.
dc.contributor.author	Martonosi, Margaret
dc.contributor.department	Ingeniería y Tecnología de Computadores
dc.date.accessioned	2024-01-31T09:54:17Z
dc.date.available	2024-01-31T09:54:17Z
dc.date.issued	2021
dc.description	©2021. This manuscript version is made available under the CC-BY 4.0 license http://creativecommons.org/licenses/by /4.0/ This document is the Accepted version of a Published Work that appeared in final form in IEEE IEEE Transactions on Computers. To access the final edited and published work see https://www.doi.org/10.1109/TC.2022.3157525
dc.description.abstract	Despite their ubiquity in many important big-data applications, graph analytic kernels continue to challenge modern memory hierarchies due to their frequent, long-latency, pointer indirect accesses to vertex property data. Such accesses exhibit poor locality and variable reuse that trouble cache replacement policies, and consequently increase memory bandwidth pressure. Specialized graph-tailored prefetching mechanisms, processor designs, and memory hierarchy engines have been developed to tolerate the long latencies of such accesses. However, these approaches are either too bandwidth-intensive, require invasive hardware changes that inhibit general-purpose computation flexibility, or rely on software preprocessing that limits true speedup. This work introduces Graphfire, a flexible memory hierarchy approach that learns different access patterns in graph processing and exploits the synergy of specialized fetch, insertion, and replacement optimizations for problematic indirect accesses without relying on software or ISA support. More specifically, Graphfire identifies when these irregular accesses occur and employs tailored access granularities, data-aware insertion, and frequency-based replacement accordingly. It achieves up to a 1.79× speedup (geomean 1.3×) and these improvements scale due to bandwidth efficiency; with 64 cores, Graphfire yields up to a 71.33× speedup (geomean 63.32×) over a single baseline core and allows memory-bound graph analytic codes to scale far beyond prior work.	es
dc.format	application/pdf	es
dc.format.extent	14	es
dc.identifier.citation	IEEE Transactions on Computers, vol. 72, issue 1, pp. 291-304, ISSN: 0018-9340, Enero 2023
dc.identifier.doi	https://www.doi.org/10.1109/TC.2022.3157525
dc.identifier.issn	0018-9340
dc.identifier.uri	http://hdl.handle.net/10201/138263
dc.language	eng	es
dc.publisher	IEEE	es
dc.relation	TÍTULO PROYECTO: "DECADES: Deeply-Customized Accelerator-Oriented Data Supply Systems Synthesis" Código: FA8650-18-2-7862 Organismo financiador: Defense Advanced Research Projects Agency (DARPA); Programa: Software Defined Hardware (SDH); País: E.E.U.U. TÍTULO PROYECTO: "Arquitectura de Sistemas de Computación Inteligentes, Ubicuos y Energéticamente Eficientes" Código: TIN2016-75344-R Organismo financiador: Ministerio de Economía y Competitividad (MINECO)	es
dc.rights	info:eu-repo/semantics/openAccess	es
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 Internacional	*
dc.rights	Atribución 4.0 Internacional	*
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	*
dc.subject	Cache	es
dc.subject	Graph analytics
dc.subject	Memory hierarchy
dc.title	Graphfire: Synergizing Fetch, Insertion, and Replacement Policies for Graph Analytics	es
dc.type	info:eu-repo/semantics/article	es
dspace.entity.type	Publication	es