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算法中STM和无锁操作的组合（例如，无国界医生组织（MSF）取得了可喜的成果。目前，这些方法是针对特定应用而定制的。在这项研究中，我建议研究其他类型的变形图算法，具有广泛的用途（例如，我正在进行的研究是关于多级图划分），研究处理分支发散和动态负载平衡的方法，研究可能不满足所需代数属性的应用（例如，在某些网络应用中），并识别/分类这些算法的共同特征，以便于开发用于异构并行计算平台上的变形算法的定义明确的方法和开发框架。