metadata.tex

\def \codeURL{https://github.com/lecfab/rescience-gorder}
\def \codeDOI{}
\def \dataURL{}
\def \dataDOI{}
\def \editorNAME{}
\def \editorORCID{}
\def \reviewerINAME{}
\def \reviewerIORCID{}
\def \reviewerIINAME{}
\def \reviewerIIORCID{}
\def \dateRECEIVED{}
\def \dateACCEPTED{}
\def \datePUBLISHED{}
\def \articleTITLE{[Re] Speedup Graph Processing by Graph Ordering}
%{Cache speedup with various orderings in~graph~algorithms}
% Run-time of various orderings in massive networks
\def \articleTYPE{Replication}
\def \articleDOMAIN{Algorithmics}
\def \articleBIBLIOGRAPHY{bibliography.bib}
\def \articleYEAR{2021}
\def \reviewURL{}
\def \articleABSTRACT{\added{Cache systems keep data close to the processor to access it faster than main memory would. Graph algorithms benefit from this when a cache line contains highly related nodes. Hao Wei \textit{et al.} propose to reorder the nodes of a graph to optimise the proximity of nodes on a cache line. Their contribution, Gorder, creates such an ordering with a greedy procedure. In this replication, we implement ten different orderings and measure the execution time of nine standard graph algorithms on nine real-world datasets. We monitor cache performances to show that runtime variations are caused by cache management. We confirm that Gorder leads to the fastest execution in most cases due to cache-miss reductions. Our results show that simpler procedures are yet almost as efficient and much quicker to compute. This replication validates the initial results but highlights that generating a complex ordering like Gorder is time-consuming.}}

% # Information about the original article that has been replicated
% replication:
%  - cite: # Full textual citation
%  - bib:  # Bibtex key (if any) in your bibliography file
%  - url:  # URL to the PDF, try to link to a non-paywall version
%  - doi:  # Regular digital object identifier
\def \replicationCITE{ by Hao Wei, Jeffrey Xu Yu, Can Lu, and Xuemin Lin, in Proceedings of SIGMOD 2016}
\def \replicationBIB{\cite{gorder}}
\def \replicationURL{https://raw.githubusercontent.com/datourat/Gorder/master/paper.pdf}
\def \replicationDOI{}
\def \contactNAME{Fabrice Lécuyer}
\def \contactEMAIL{fabrice.lecuyer@lip6.fr}
\def \articleKEYWORDS{graph algorithm, cache optimisation, node ordering, gorder}
\def \journalNAME{ReScience C}
\def \journalVOLUME{}
\def \journalISSUE{}
\def \articleNUMBER{}
\def \articleDOI{}
\def \authorsFULL{Fabrice Lécuyer and Maximilien Danisch and Lionel Tabourier}
\def \authorsABBRV{F. Lécuyer, M. Danisch and L. Tabourier}
\def \authorsSHORT{Lécuyer, Danisch and Tabourier}
\title{\articleTITLE}
\date{}
\author[1]{Fabrice Lécuyer}
\author[1]{Maximilien Danisch}
\author[1,\orcid{0000-0002-9160-8083}]{Lionel Tabourier}
\author[.]{}

\affil[1]{Sorbonne Université, CNRS, LIP6, F-75005 Paris, France}