Parallelization strategies for morph graph algorithms

研究了异质并行计算平台上涉及动态不规则任务图的应用程序的并行化策略。这些应用程序涉及复杂的数据结构，例如具有不规则内存访问模式的树和图以及动态数据共享。在这项拟议的研究中，我特别关注变形图算法，这是不规则算法的一个子集，它以不可预测的方式改变底层的图结构。以图为数据结构的变形算法的例子有：Boruvka的最小生成森林(MSF)算法、多层图划分算法、测量传播、Delaunay网格细化(DMR)，以及提案中列出的更多算法。这些算法具有广泛的实用价值。与(固定的)不规则算法不同，变形算法在不同平台(如CPU-GPU系统、集群、计算云)上的并行化研究是有限的。在这种变形算法的基于GPU的实现中，由于具有锁的极端同步开销、由于诸如分支发散和由图拓扑中的动态变化引起的负载不平衡等问题而导致的空闲、以及由于死锁的可能性而导致的不可靠性而引起的复杂性。现有的方法中很少有方法使用原子操作(如“比较和交换”)以无锁的方式处理同步；然而，某些代数属性(例如单调性)必须由应用程序的特征来满足，这样才能应用无锁方法，从而限制了其适用性。有一些方法根本不使用同步(例如，无原子方法)，但它可能会使算法非常复杂，因此容易出现编程错误，此外可伸缩性要差得多。最近，我一直在探索一种基于软件事务存储器(STM)的方法来处理一类在GPU上的Morph算法的同步问题，并取得了令人满意的结果。与当前的方法相比，这种方法没有死锁和活锁，更可靠，更不容易出现程序员错误。我还一直在研究一类Morph算法(例如，MSF)中STM和无锁操作的组合，结果令人振奋。目前，这些方法是针对特定应用程序量身定做的。在这项研究中，我建议调查其他类型的变形图算法(例如，我正在进行的研究是关于多级图划分)，调查处理分支分歧和动态负载平衡的方法，调查可能不满足所需代数性质的应用程序(例如，在某些网络应用程序中)，并识别/分类这些算法的共同特征，以促进在异质并行计算平台上开发定义良好的变形算法方法和开发框架。

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.