Communication-Avoiding Large Graph Algorithms for Flow Modeling
Event Type
ACM Student Research Competition: Graduate Poster
ACM Student Research Competition: Undergraduate Poster
Student Program
TP
TimeWednesday, 18 November 20203:17pm - 3:34pm EDT
LocationTrack 8
DescriptionLarge digital elevation models (DEMs) can be used in geographic information systems (GIS) to model hydrology across continents. Smaller DEMs, coupled with governing equations, can be used to distinguish between competing theories of landscape evolution. Two algorithms, depression filling and flow accumulation, are central to both applications, but existing implementations scale poorly and don't use accelerators like GPUs. Here, I model hydrology using graphs and develop new communication-avoiding algorithms which reduce I/O and communication to theoretic minimums. The new algorithms exhibit 60% strong and weak scaling up to 48 cores. The largest DEM tested has 2 trillion cells. On 48 cores processing took 4.8 hours wall-time. This test is 1000x larger than any previously performed. On datasets small enough for comparison against older algorithms, the new algorithms use 19x less bandwidth, 70x less communication time, and 7x less memory. Complete, well-commented source code and correctness tests are available at http://richdem.com.
