Support for Massive Scale Graph Analytics

支持大规模图形分析

• 批准号: RGPIN-2014-05203
• 负责人: Ripeanu, Matei
• 金额: $ 3.35万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=588270
• 关键词: Support; 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.

图是一系列广泛领域问题的核心数据结构，从挖掘社交网络到基因组学，再到商业和信息分析。在这些领域，我们将原始数据转化为洞察力和可操作知识的能力的关键是能够以合理的成本有效地处理大型图表。例如，想象一个电力传输网。网络节点之间存在冗余传输路径，并且可以基于路径的特性和功率成本在路径上路由功率。估计线路故障和可能的纠正措施的影响对于最大限度地减少停电和设备损坏至关重要。然而，这种分析是基于对大规模图形处理的有效支持。 多个特征使得大规模图处理困难：大的内存占用、具有差的局部性的内存访问模式、数据依赖的并行性以及低的计算到内存访问比率。此外，大多数真实世界的图具有低直径和高度异构的顶点度分布（即，它们是“幂律”），因此划分这些图以优化访问局部性和负载平衡是困难的。 该项目旨在探索三个相互交织的研究方向： * 首先，它旨在探索在硬件组件级别利用两个最新进展的可行性：大规模并行（协）处理器（例如，nVidia GPU、英特尔至强融核处理器（Xeon Phi）和固态存储器，以提高图形分析应用程序的性能并降低其能耗。 * 其次，揭示特定于域的图结构和频繁的数据访问模式所实现的特定于域的优化，并通过特定于域的运行时对程序员透明地利用它们。 * 最后，探索通过特定于领域的语言简化图形分析应用程序开发的途径。 虽然从图分析中受益的潜在领域是巨大的，但我们计划专注于两个高影响力的领域：社交网络和生物信息学。 这些领域在问题规模、数据多样性和解决时间方面提出了具有挑战性的要求，同时见证了日益多样化的复杂分析算法的快速发展，这证明了我们对应用程序开发友好性的关注。 总结一下：本项目研究的可行性和比较优势，支持图形处理（集群）的主机大规模并行加速器和大型固态存储器的节点。本着构建抽象以隐藏复杂性的精神，本项目将探索应用领域专用语言和运行时基础设施的可行性，以平衡程序员的生产力和有效的平台利用率。