Parallelization strategies for morph graph algorithms

点击翻译按钮获取中文摘要

I conduct research on parallelization strategies of applications involving dynamic irregular task graphs on heterogeneous parallel computing platforms. These applications involve complex data-structures such as trees and graphs with irregular memory access patterns and dynamic data sharing. In this proposed research, my specific focus is on morph graph algorithms, a subset of irregular algorithms, that change the underlying graph structures in unpredictable ways. Examples of morph algorithms with graph as data-structure are: Boruvka's Minimum Spanning Forest (MSF) algorithm, multi-level graph partitioning algorithms, Survey Propagation, Delaunay Mesh Refinement (DMR), and many more listed in the proposal. These algorithms have widespread practical uses. Unlike (fixed) irregular algorithms, research on parallelization of morph algorithms on heterogeneous platforms (e.g., CPU-GPU systems, clusters, computational clouds) is limited. In a GPU-based implementation of such morph algorithms, complexity arises due to extreme synchronization overheads with locks, idling due to issues like branch divergence and load imbalances resulting from dynamic changes in graph topology, and unreliability due to possibility of deadlocks. Few of the existing approaches handle synchronization in lock-free ways using atomic operations like "compare and swap"; however certain algebraic properties (e.g., monotonicity) have to be satisfied by the application's characteristics so that lock-free approach can be applied, thus limiting its applicability. There are approaches that use no synchronization at all (e.g., atomic-free approach), but it could make the algorithm very complex and hence error prone to program, in addition to being much less scalable. Recently I have been exploring a Software Transactional Memory (STM) based approach to handle the synchronization issues of a class of Morph algorithms on GPUs with promising results. The approach is deadlock- and livelock-free, much more reliable, and less prone to programmer errors as compared to contemporary approaches. I have also been investigating a combination of STM and lock-free operations in a class of Morph algorithms (e.g., MSF) with promising results. Currently these approaches are tailored to a specific application. In this research, I propose to investigate other types of morph graph algorithms that have widespread uses (e.g., my ongoing research is on multi-level graph partitioning), investigate approaches to handle branch divergence and dynamic load balancing, investigate applications that may not satisfy the required algebraic properties (e.g., in certain networking applications), and identify/classify the common characteristics for such algorithms to facilitate developing a well-defined methodology and development framework for morph algorithms on heterogeneous parallel computing platforms.