Scaling Triangle Counting and K-Truss on the UpDown Architecture

UpDown is a novel computing architecture that features accelerators with a custom architecture to make fine-grained parallel algorithms possible. It integrates into a system with a global shared memory address space that was designed to be extremely flat in terms of system resources, with off-node data access comparable to on-node access. This setup enables algorithms and software to scale from single nodes to an entire cluster easily. We demonstrate that UpDown’s performance on the Graph Isomorphism Graph Challenge benchmark, utilizing a system designed under IARPA’s AGILE program, fulfills this promise. For TC, simulation of the UpDown system predicts excellent scaling to over 900-fold speedup while using only a single global copy of the graph. For K-truss, on a single node, we are faster than a comparable GPU, and again with a single global copy of the graph, report the first scale-out performance, scaling to up to 16-fold performance on 16 nodes, and 232-fold on 256 nodes.