Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Concordia University

$23,000.00

Parallelization strategies for morph graph algorithms

EF 2018-19

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2018-05082
Name nom
Goswami, Dhrubajyoti
Department département
Computer Science and Software Engineering
Organization id
70
Institution établissement
Concordia University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2018
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
1
Nb partie
5
Application title
Parallelization strategies for morph graph algorithms
Keyword
NSERC
Application summary
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.