Support for Massive Scale Graph Analytics

点击翻译按钮获取中文摘要

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.