Parallelization strategies for morph graph algorithms

变形图算法的并行化策略

• 批准号: RGPIN-2018-05082
• 负责人: Goswami, Dhrubajyoti
• 金额: $ 1.68万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679370
• 关键词: Parallelization; strategies; 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.

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