Algorithm-Level Optimizations for Scalable Parallel Graph Processing

Efficiently processing large graphs is challenging, since parallel graph algorithms suffer from\npoor scalability and performance due to many factors, including heavy communication and load-imbalance.\nFurthermore, it is difficult to express graph algorithms, as users need to understand\nand effectively utilize the underlying execution of the algorithm on the distributed system. The\nperformance of graph algorithms depends not only on the characteristics of the system (such as\nlatency, available RAM, etc.), but also on the characteristics of the input graph (small-world scalefree,\nmesh, long-diameter, etc.), and characteristics of the algorithm (sparse computation vs. dense\ncommunication). The best execution strategy, therefore, often heavily depends on the combination\nof input graph, system and algorithm.\nFine-grained expression exposes maximum parallelism in the algorithm and allows the user to\nconcentrate on a single vertex, making it easier to express parallel graph algorithms. However,\nthis often loses information about the machine, making it difficult to extract performance and\nscalability from fine-grained algorithms.\nTo address these issues, we present a model for expressing parallel graph algorithms using a\nfine-grained expression. Our model decouples the algorithm-writer from the underlying details\nof the system, graph, and execution and tuning of the algorithm. We also present various graph\nparadigms that optimize the execution of graph algorithms for various types of input graphs and\nsystems. We show our model is general enough to allow graph algorithms to use the various graph\nparadigms for the best/fastest execution, and demonstrate good performance and scalability for\nvarious different graphs, algorithms, and systems to 100,000+ cores.