BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210808T235336Z
LOCATION:Room A
DTSTART;TZID=America/Chicago:20210811T104500
DTEND;TZID=America/Chicago:20210811T110000
UID:icpp_ICPP 2021_sess112_pap474@linklings.com
SUMMARY:Communication Avoiding All-Pairs Shortest Paths Algorithm for Spa
rse graphs
DESCRIPTION:Conference Paper\n\nCommunication Avoiding All-Pairs Shortest
Paths Algorithm for Sparse graphs\n\nZhu, Hua, Jin\n\nIn this paper, we p
ropose a parallel algorithm for computing all-pairs shortest paths (APSP)
for sparse graphs on the distributed memory system with $p$ processors.
To exploit the graph sparsity, we first preprocess the graph by utilizing
several known algorithmic techniques in linear algebra such as fill-in red
ucing ordering and elimination tree parallelism. Then we map the preproces
sed graph on the distributed memory system for both load balancing and com
munication reduction. Finally, we design a new scheduling strategy to mini
mize the communication cost.\nThe bandwidth cost (communication volume) an
d the latency cost (number of messages) of our algorithm are $O(\frac{n^2
\log^2 p }{p}+|S|^2 \log^2 p)$ and $O(\log^2 p)$, respectively, where $S$
is a minimal vertex separator that partitions the graph into two component
s of roughly equal size. Compared with the state-of-the-art result for den
se graphs where the bandwidth and latency costs are $O(\frac{n^2}{\sqrt{p}
})$ and $O(\sqrt{p}\log^2 p$), respectively, our algorithm reduces the lat
ency cost by a factor of $O(\sqrt{p})$, and reduces the bandwidth cost by
a factor of $O(\frac{\sqrt{p}}{\log^2 p})$ for sparse graphs with $|S|=O(
\frac{n}{\sqrt{p}})$. \nWe also present the bandwidth and latency costs lo
wer bounds for computing APSP on sparse graphs, which are $\Omega(\frac{n
^2}{p}+|S|^2)$ and $\Omega(\log^2 p)$, respectively. This implies that the
bandwidth cost of our algorithm is nearly optimal and the latency cost is
optimal.
END:VEVENT
END:VCALENDAR