  Graph search and sparse data-structure traversal workloads contain
challenging irregular memory patterns on global data structures that need to be
modified atomically. Distributed processing of these workloads has relied on
server threads operating on their own data copies that are merged upon global
synchronization. As parallelism increases within each server, the communication
challenges that arose in distributed systems a decade ago are now being
encountered within large manycore servers. Prior work has achieved scalability
for sparse applications up to thousands of PUs on-chip, but does not scale
further due to increasing communication distances and load-imbalance across
PUs. To address these challenges we propose Tascade, a hardware-software
co-design that offers support for storage-efficient data-private reductions as
well as asynchronous and opportunistic reduction trees. Tascade introduces an
execution model along with supporting hardware design that allows coalescing of
data updates regionally and merges the data from these regions through cascaded
updates. Together, Tascade innovations minimize communication and increase work
balance in task-based parallelization schemes and scales up to a million PUs.
We evaluate six applications and four datasets to provide a detailed analysis
of Tascade's performance, power, and traffic-reduction gains over prior work.
Our parallelization of Breadth-First-Search with RMAT-26 across a million PUs
-- the largest of the literature -- reaches over 7600 GTEPS.
