Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of British Columbia

$46,000.00

Support for Massive Scale Graph Analytics

FY 2016-17

Summary
Graphs are the core data structure for problems in a wide set of domains form mining social networks, to genomics, to business and information analytics. In these domains, key to our ability to transform raw data into insights and actionable knowledge is the ability to process large graphs efficiently and at reasonable cost. Imagine for example a power transmission grid. Redundant transmission paths between network nodes exist and power can be routed on a path based on the characteristics of the path and the cost of power. Estimating the impact of line failures and of possible corrective actions is critical to minimize blackouts and equipment damage. This analysis, however, is predicated on efficient support for large-scale graph processing. Multiple characteristics make large-scale graph processing difficult: a large memory footprint, a memory access pattern with poor locality, data-dependent parallelism, and a low compute to memory access ratio. Additionally, most real-world graphs have a low diameter and a highly heterogeneous vertex degree distribution (i.e., they are 'power-law') thus partitioning these graphs to optimize for access locality and load-balancing is difficult. This project aims to explore three intertwined research directions: * Firstly, it aims to explore the feasibility of harnessing two recent advances at the hardware component level: massively parallel (co)processors (e.g., nVidia GPUs, Intel's Xeon Phi) and solid state memories, to both increase performance and reduce the energy footprint for graph analytic applications. * Secondly, uncover the domain-specific optimizations enabled by domain-specific graph-structures and frequent data access patterns and enable harnessing them transparently to programmers through domain-specific runtimes. * Finally, explore avenues to simplify the development of graph analytics applications through domain-specific languages. While the set of potential domains that benefit from graph analytics is huge we plan to focus on two high-impact areas: social-networks and bioinformatics. These domains offer challenging requirements in terms of problem scale, data diversity, and time-to-solution, and, at the same time, witness the rapid development of an increasingly diverse set of complex analytics algorithms which justifies our focus on application-development friendliness. To summarize: This project investigates the feasibility and the comparative advantages of supporting graph processing on (clusters of) nodes that host massively parallel accelerators and large solid-state memories. In the spirit of building abstractions to hide complexity, this project will explore the feasibility of application-domain specialized languages and runtime infrastructures to balance programmer productivity and efficient platform utilization.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-05203
Name nom
Ripeanu, Matei
Department département
Electrical and Computer Engineering
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
46000
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
2720
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Computer systems software
Research subject fr
Logiciel de systèmes informatiques
Partie
3
Nb partie
5
Application title
Support for Massive Scale Graph Analytics
Keyword
NSERC
Application summary
Graphs are the core data structure for problems in a wide set of domains form mining social networks, to genomics, to business and information analytics. In these domains, key to our ability to transform raw data into insights and actionable knowledge is the ability to process large graphs efficiently and at reasonable cost. Imagine for example a power transmission grid. Redundant transmission paths between network nodes exist and power can be routed on a path based on the characteristics of the path and the cost of power. Estimating the impact of line failures and of possible corrective actions is critical to minimize blackouts and equipment damage. This analysis, however, is predicated on efficient support for large-scale graph processing. Multiple characteristics make large-scale graph processing difficult: a large memory footprint, a memory access pattern with poor locality, data-dependent parallelism, and a low compute to memory access ratio. Additionally, most real-world graphs have a low diameter and a highly heterogeneous vertex degree distribution (i.e., they are 'power-law') thus partitioning these graphs to optimize for access locality and load-balancing is difficult. This project aims to explore three intertwined research directions: * Firstly, it aims to explore the feasibility of harnessing two recent advances at the hardware component level: massively parallel (co)processors (e.g., nVidia GPUs, Intel's Xeon Phi) and solid state memories, to both increase performance and reduce the energy footprint for graph analytic applications. * Secondly, uncover the domain-specific optimizations enabled by domain-specific graph-structures and frequent data access patterns and enable harnessing them transparently to programmers through domain-specific runtimes. * Finally, explore avenues to simplify the development of graph analytics applications through domain-specific languages. While the set of potential domains that benefit from graph analytics is huge we plan to focus on two high-impact areas: social-networks and bioinformatics. These domains offer challenging requirements in terms of problem scale, data diversity, and time-to-solution, and, at the same time, witness the rapid development of an increasingly diverse set of complex analytics algorithms which justifies our focus on application-development friendliness. To summarize: This project investigates the feasibility and the comparative advantages of supporting graph processing on (clusters of) nodes that host massively parallel accelerators and large solid-state memories. In the spirit of building abstractions to hide complexity, this project will explore the feasibility of application-domain specialized languages and runtime infrastructures to balance programmer productivity and efficient platform utilization.
University of British Columbia - $46,000 Grant (2016-… | Canada Spends