SC13 Research Highlight: Large Graph Processing Without the Overhead

By Dr. Ling Liu and Kisung Lee

November 16, 2013

Many real world information networks consist of millions or billions of vertices representing heterogeneous entities and billions or trillions of edges representing heterogeneous types of relationships among entities.

Image Source: Max Delbrück Center for Molecular Medicine

For example, the crawled Web graph is estimated to have more than 20 billions of pages (vertices) with 160 billions hyperlinks (edges). Facebook user community exceeds 1 billion users (vertices) with more than 140 billion friendship relationships (edges) in 2012.  The billion triple challenges from the Semantic Web community have put forward large collection of RDF datasets with hundreds of millions of vertices and billions of edges.

As the size and variety of information networks continue to grow in many science and engineering domains, graph computations often exceed the processing capacity of conventional hardware, software systems and tools for a number of reasons. First, graph data often exhibits higher data correlations through both direct and indirect edges and such high correlation tends to generate large size of intermediate results during graph computations. When the size of intermediate results exceeds the available memory, the out of memory problem is unavoidable. Second, the graph datasets are growing in volume, variety and velocity. The bigger the size of the graphs gets, the worse the performance will be for most of the graph computations. One open challenge in this space is how to effectively partition a large graph to enable efficient parallel processing of complex graph operations.

One of the papers to be presented at the ACM/IEEE SC13 conference, titled “Efficient data partitioning model for heterogeneous graphs in the Cloud”, proposes a flexible graph partitioning framework, called VB-partitioner. This work is co-authored by the doctorate student Kisung Lee and Prof. Dr. Ling Liu from the school of Computer Science at Georgia Institute of Technology. To make parallel graph computations highly efficient, an important design goal of VB-Partitioner is to devise graph partitioning techniques that can effectively minimize the inter-partition communication overhead and maximize the intra-partition computation capacity (local processing).

Concretely, the first prototype of the VB-Partitioner focuses on efficient processing of graph queries, namely finding all the subgraphs matching a given subgraph pattern. VB-Partitioner partitions a large graph in three steps.

  • First, it constructs three types of Vertex Blocks (in-VBs, out-VBs and bi-VBs) to capture the general graph processing locality.  Each vertex block has an anchor vertex.
  • Second, it constructs three types of k-hop Extended Vertex Blocks (in-EVBs, out-EVBs and bi-EVBs) to distribute vertex blocks with better query locality. Each EVB has one anchor vertex. It achieves query locality by employing controlled edge replication. The setting of k is determined by the radius of frequent query graphs in order to ensure that most frequently requested queries can be processed in parallel at all partitions with minimized inter-partition communication overhead.
  • Third, it partitions a graph by grouping its vertex blocks and EVBs to maximize parallelism in graph processing while ensuring load balance, controlled edge replication and fast grouping.

Four techniques are considered and compared in the context of grouping and placement of VBs and EVBs to partitions: random grouping, hash-based grouping, min-cut based grouping and high degree vertex-based grouping.  As an integral part of the VB-Partitioner, a data partition-aware query partitioning model is also developed to handle the cases where the radius of a query is larger than k. The experimental results reported in the paper demonstrate the effectiveness of VB-Partitioner in terms of query processing efficiency, data loading time and partition distribution balance.

Graph computations can be broadly classified into two categories, graph queries that find matching subgraphs of a given pattern and iterative graph algorithms that find clusters, orderings, paths or correlation patterns. The former targets at subgraph matching problems over large static graphs and the later targets at graph inference kernels that traverse the graph by iteratively updating the weight of vertices or edges, such as PageRank, shortest path algorithms, spanning tree algorithms, topological sort, and so forth.

Although the first generation of the VB-Partitioner is tailored primarily for efficient parallel processing of graph queries, the ongoing work on VB-Partitioner includes exploring the feasibility and effectiveness of VB-Partitioner in the context of iterative graph algorithms. For example, to minimize inter-partition communications and maximize parallelism in graph computation, it is crucial to optimize the shared memory by minimizing parallel overhead of synchronization barriers. It is equally important to optimize the distributed memory by bounding message buffer sizes, bundling messages, overlapping communication with computation to amortize the overhead of barriers.

image1
Image Source: Giot et al., “A Protein Interaction Map of Drosophila melanogaster”, Science 302, 1722-1736, 2003.”

In addition to exploring parallel computation opportunities through graph partitioning using multi-threads, multi-cores, multiple workers, one can also exploit and combine with other performance optimization techniques to scale large graph analytics. Example techniques include

  • Compression to provide compact storage and in-memory processing,
  • Data placements on disk and in memory to balance computation with storage, and to maximize sequential access and minimize random access,
  • Indexing at vertex and/or edge level to utilize sequential access and minimize unnecessary random access,
  • Caching at vertex, edge or query level to gain performance for repeated access.

Please come hear more on Tuesday, November 19, 2013 10:30AM – 11:00AM (Location: Room 205/207)

http://sc13.supercomputing.org/schedule/event_detail.php?evid=pap708

About the Authors

LingLing Liu is a Professor in the School of Computer Science at Georgia Institute of Technology. She directs the research programs in Distributed Data Intensive Systems Lab (DiSL), examining various aspects of large scale data intensive systems. Prof. Ling Liu is an internationally recognized expert in the areas of Cloud computing, Distributed Computing, Big Data technologies, Database systems and Service oriented computing. Prof. Liu is a recipient of IEEE Computer Society Technical Achievement Award in 2012. Currently Prof. Liu is the editor in chief of IEEE Transactions on Service Computing, and serves on the editorial board of half dozen international journals, including Journal of Parallel and Distributed Computing (JPDC), ACM Transactions on Internet Technology (TOIT), ACM Transactions on Web (TWEB). Dr. Liu’s current research is primarily sponsored by NSF, IBM, and Intel.

 

luiKisung Lee is a Ph.D student in the School of Computer Science at Georgia Tech. He received his BS and MS degree in computer science from KAIST in 2005 and 2007 respectively. He had worked for ETRI as a researcher from 2007 to 2010. He is conducting research in distributed and parallel processing of big data in the Cloud, mobile computing and social network analysis.

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

Data West Brings Technology Leaders to SDSC

December 6, 2018

Data and technology enthusiasts from around the world descended upon the San Diego Supercomputing Center (SDSC) for the third annual Data West conference, which is taking place this week on the campus of the University o Read more…

By Alex Woodie

Topology Can Help Us Find Patterns in Weather

December 6, 2018

Topology--–the study of shapes-- seems to be all the rage. You could even say that data has shape, and shape matters. Shapes are comfortable and familiar concepts, so it is intriguing to see that many applications are Read more…

By James Reinders

What’s New in HPC Research: Automatic Energy Efficiency, DNA Data Analysis, Post-Exascale & More

December 6, 2018

In this bimonthly feature, HPCwire highlights newly published research in the high-performance computing community and related domains. From exascale to quantum computing, the details are here. Read more…

By Oliver Peckham

HPE Extreme Performance Solutions

AI Can Be Scary. But Choosing the Wrong Partners Can Be Mortifying!

As you continue to dive deeper into AI, you will discover it is more than just deep learning. AI is an extremely complex set of machine learning, deep learning, reinforcement, and analytics algorithms with varying compute, storage, memory, and communications needs. Read more…

IBM Accelerated Insights

Five Steps to Building a Data Strategy for AI

Our data-centric world is driving many organizations to apply advanced analytics that use artificial intelligence (AI). AI provides intelligent answers to challenging business questions. AI also enables highly personalized user experiences, built when data scientists and analysts learn new information from data that would otherwise go undetected using traditional analytics methods. Read more…

Zettascale by 2035? China Thinks So

December 6, 2018

Exascale machines (of at least a 1 exaflops peak) are anticipated to arrive by around 2020, a few years behind original predictions; and given extreme-scale performance challenges are not getting any easier, it makes sense that researchers are already looking ahead to the next big 1,000x performance goal post: zettascale computing. Read more…

By Tiffany Trader

Topology Can Help Us Find Patterns in Weather

December 6, 2018

Topology--–the study of shapes-- seems to be all the rage. You could even say that data has shape, and shape matters. Shapes are comfortable and familiar conc Read more…

By James Reinders

Zettascale by 2035? China Thinks So

December 6, 2018

Exascale machines (of at least a 1 exaflops peak) are anticipated to arrive by around 2020, a few years behind original predictions; and given extreme-scale performance challenges are not getting any easier, it makes sense that researchers are already looking ahead to the next big 1,000x performance goal post: zettascale computing. Read more…

By Tiffany Trader

Robust Quantum Computers Still a Decade Away, Says Nat’l Academies Report

December 5, 2018

The National Academies of Science, Engineering, and Medicine yesterday released a report – Quantum Computing: Progress and Prospects – whose optimism about Read more…

By John Russell

Revisiting the 2008 Exascale Computing Study at SC18

November 29, 2018

A report published a decade ago conveyed the results of a study aimed at determining if it were possible to achieve 1000X the computational power of the the Read more…

By Scott Gibson

AWS Debuts Lustre as a Service, Accelerates Data Transfer

November 28, 2018

From the Amazon re:Invent main stage in Las Vegas today, Amazon Web Services CEO Andy Jassy introduced Amazon FSx for Lustre, citing a growing body of applicati Read more…

By Tiffany Trader

AWS Launches First Arm Cloud Instances

November 28, 2018

AWS, a macrocosm of the emerging high-performance technology landscape, wants to be everywhere you want to be and offer everything you want to use (or at least Read more…

By Doug Black

Move Over Lustre & Spectrum Scale – Here Comes BeeGFS?

November 26, 2018

Is BeeGFS – the parallel file system with European roots – on a path to compete with Lustre and Spectrum Scale worldwide in HPC environments? Frank Herold Read more…

By John Russell

DOE Under Secretary for Science Paul Dabbar Interviewed at SC18

November 21, 2018

During the 30th annual SC conference in Dallas last week, SC18 hosted U.S. Department of Energy Under Secretary for Science Paul M. Dabbar. In attendance Nov. 13-14, Dabbar delivered remarks at the Top500 panel, met with a number of industry stakeholders and toured the show floor. He also met with HPCwire for an interview, where we discussed the role of the DOE in advancing leadership computing. Read more…

By Tiffany Trader

Quantum Computing Will Never Work

November 27, 2018

Amid the gush of money and enthusiastic predictions being thrown at quantum computing comes a proposed cold shower in the form of an essay by physicist Mikhail Read more…

By John Russell

Cray Unveils Shasta, Lands NERSC-9 Contract

October 30, 2018

Cray revealed today the details of its next-gen supercomputing architecture, Shasta, selected to be the next flagship system at NERSC. We've known of the code-name "Shasta" since the Argonne slice of the CORAL project was announced in 2015 and although the details of that plan have changed considerably, Cray didn't slow down its timeline for Shasta. Read more…

By Tiffany Trader

IBM at Hot Chips: What’s Next for Power

August 23, 2018

With processor, memory and networking technologies all racing to fill in for an ailing Moore’s law, the era of the heterogeneous datacenter is well underway, Read more…

By Tiffany Trader

House Passes $1.275B National Quantum Initiative

September 17, 2018

Last Thursday the U.S. House of Representatives passed the National Quantum Initiative Act (NQIA) intended to accelerate quantum computing research and developm Read more…

By John Russell

CERN Project Sees Orders-of-Magnitude Speedup with AI Approach

August 14, 2018

An award-winning effort at CERN has demonstrated potential to significantly change how the physics based modeling and simulation communities view machine learni Read more…

By Rob Farber

Summit Supercomputer is Already Making its Mark on Science

September 20, 2018

Summit, now the fastest supercomputer in the world, is quickly making its mark in science – five of the six finalists just announced for the prestigious 2018 Read more…

By John Russell

AMD Sets Up for Epyc Epoch

November 16, 2018

It’s been a good two weeks, AMD’s Gary Silcott and Andy Parma told me on the last day of SC18 in Dallas at the restaurant where we met to discuss their show news and recent successes. Heck, it’s been a good year. Read more…

By Tiffany Trader

US Leads Supercomputing with #1, #2 Systems & Petascale Arm

November 12, 2018

The 31st Supercomputing Conference (SC) - commemorating 30 years since the first Supercomputing in 1988 - kicked off in Dallas yesterday, taking over the Kay Ba Read more…

By Tiffany Trader

Leading Solution Providers

SC 18 Virtual Booth Video Tour

Advania @ SC18 AMD @ SC18
ASRock Rack @ SC18
DDN Storage @ SC18
HPE @ SC18
IBM @ SC18
Lenovo @ SC18 Mellanox Technologies @ SC18
NVIDIA @ SC18
One Stop Systems @ SC18
Oracle @ SC18 Panasas @ SC18
Supermicro @ SC18 SUSE @ SC18 TYAN @ SC18
Verne Global @ SC18

TACC’s ‘Frontera’ Supercomputer Expands Horizon for Extreme-Scale Science

August 29, 2018

The National Science Foundation and the Texas Advanced Computing Center announced today that a new system, called Frontera, will overtake Stampede 2 as the fast Read more…

By Tiffany Trader

HPE No. 1, IBM Surges, in ‘Bucking Bronco’ High Performance Server Market

September 27, 2018

Riding healthy U.S. and global economies, strong demand for AI-capable hardware and other tailwind trends, the high performance computing server market jumped 28 percent in the second quarter 2018 to $3.7 billion, up from $2.9 billion for the same period last year, according to industry analyst firm Hyperion Research. Read more…

By Doug Black

Nvidia’s Jensen Huang Delivers Vision for the New HPC

November 14, 2018

For nearly two hours on Monday at SC18, Jensen Huang, CEO of Nvidia, presented his expansive view of the future of HPC (and computing in general) as only he can do. Animated. Backstopped by a stream of data charts, product photos, and even a beautiful image of supernovae... Read more…

By John Russell

Germany Celebrates Launch of Two Fastest Supercomputers

September 26, 2018

The new high-performance computer SuperMUC-NG at the Leibniz Supercomputing Center (LRZ) in Garching is the fastest computer in Germany and one of the fastest i Read more…

By Tiffany Trader

Houston to Field Massive, ‘Geophysically Configured’ Cloud Supercomputer

October 11, 2018

Based on some news stories out today, one might get the impression that the next system to crack number one on the Top500 would be an industrial oil and gas mon Read more…

By Tiffany Trader

Intel Confirms 48-Core Cascade Lake-AP for 2019

November 4, 2018

As part of the run-up to SC18, taking place in Dallas next week (Nov. 11-16), Intel is doling out info on its next-gen Cascade Lake family of Xeon processors, specifically the “Advanced Processor” version (Cascade Lake-AP), architected for high-performance computing, artificial intelligence and infrastructure-as-a-service workloads. Read more…

By Tiffany Trader

Google Releases Machine Learning “What-If” Analysis Tool

September 12, 2018

Training machine learning models has long been time-consuming process. Yesterday, Google released a “What-If Tool” for probing how data point changes affect a model’s prediction. The new tool is being launched as a new feature of the open source TensorBoard web application... Read more…

By John Russell

The Convergence of Big Data and Extreme-Scale HPC

August 31, 2018

As we are heading towards extreme-scale HPC coupled with data intensive analytics like machine learning, the necessary integration of big data and HPC is a curr Read more…

By Rob Farber

  • arrow
  • Click Here for More Headlines
  • arrow
Do NOT follow this link or you will be banned from the site!
Share This