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!

Hyperion: HPC Server Market Ekes 1 Percent Gain in 2020, Storage Poised for ‘Tipping Point’

May 12, 2021

The HPC User Forum meeting taking place virtually this week (May 11-13) kicked off with Hyperion Research’s market update, covering the 2020 period. Although the HPC server market had been facing a 6.7 percent COVID-re Read more…

Finland’s CSC Chronicles the COVID Research Performed on Its ‘Puhti’ Supercomputer

May 11, 2021

CSC, Finland’s IT Center for Science, is home to a variety of computing resources, including the 1.7 petaflops Puhti supercomputer. The 682-node, Intel Cascade Lake-powered system, which places about halfway down the T Read more…

IBM Debuts Qiskit Runtime for Quantum Computing; Reports Dramatic Speed-up

May 11, 2021

In conjunction with its virtual Think event, IBM today introduced an enhanced Qiskit Runtime Software for quantum computing, which it says demonstrated 120x speedup in simulating molecules. Qiskit is IBM’s quantum soft Read more…

AMD Chipmaker TSMC to Use AMD Chips for Chipmaking

May 8, 2021

TSMC has tapped AMD to support its major manufacturing and R&D workloads. AMD will provide its Epyc Rome 7702P CPUs – with 64 cores operating at a base clock of 2.0GHz – implemented in HPE's single-socket ProLian Read more…

Supercomputer Research Tracks the Loss of the World’s Glaciers

May 7, 2021

British Columbia – which is over twice the size of California – contains around 17,000 glaciers that cover three percent of its landmass. These glaciers are crucial for the Canadian province, which relies on its many Read more…

AWS Solution Channel

FLYING WHALES runs CFD workloads 15 times faster on AWS

FLYING WHALES is a French startup that is developing a 60-ton payload cargo airship for the heavy lift and outsize cargo market. The project was born out of France’s ambition to provide efficient, environmentally friendly transportation for collecting wood in remote areas. Read more…

Meet Dell’s Pete Manca, an HPCwire Person to Watch in 2021

May 7, 2021

Pete Manca heads up Dell's newly formed HPC and AI leadership group. As senior vice president of the integrated solutions engineering team, he is focused on custom design, technology alliances, high-performance computing Read more…

Hyperion: HPC Server Market Ekes 1 Percent Gain in 2020, Storage Poised for ‘Tipping Point’

May 12, 2021

The HPC User Forum meeting taking place virtually this week (May 11-13) kicked off with Hyperion Research’s market update, covering the 2020 period. Although Read more…

IBM Debuts Qiskit Runtime for Quantum Computing; Reports Dramatic Speed-up

May 11, 2021

In conjunction with its virtual Think event, IBM today introduced an enhanced Qiskit Runtime Software for quantum computing, which it says demonstrated 120x spe Read more…

AMD Chipmaker TSMC to Use AMD Chips for Chipmaking

May 8, 2021

TSMC has tapped AMD to support its major manufacturing and R&D workloads. AMD will provide its Epyc Rome 7702P CPUs – with 64 cores operating at a base cl Read more…

Fast Pass Through (Some of) the Quantum Landscape with ORNL’s Raphael Pooser

May 7, 2021

In a rather remarkable way, and despite the frequent hype, the behind-the-scenes work of developing quantum computing has dramatically accelerated in the past f Read more…

IBM Research Debuts 2nm Test Chip with 50 Billion Transistors

May 6, 2021

IBM Research today announced the successful prototyping of the world's first 2 nanometer chip, fabricated with silicon nanosheet technology on a standard 300mm Read more…

LRZ Announces New Phase of SuperMUC-NG Supercomputer with Intel’s ‘Ponte Vecchio’ GPU

May 5, 2021

At the Leibniz Supercomputing Centre (LRZ) in München, Germany – one of the constituent centers of the Gauss Centre for Supercomputing (GCS) – the SuperMUC Read more…

Crystal Ball Gazing at Nvidia: R&D Chief Bill Dally Talks Targets and Approach

May 4, 2021

There’s no quibbling with Nvidia’s success. Entrenched atop the GPU market, Nvidia has ridden its own inventiveness and growing demand for accelerated computing to meet the needs of HPC and AI. Recently it embarked on an ambitious expansion by acquiring Mellanox (interconnect)... Read more…

Intel Invests $3.5 Billion in New Mexico Fab to Focus on Foveros Packaging Technology

May 3, 2021

Intel announced it is investing $3.5 billion in its Rio Rancho, New Mexico, facility to support its advanced 3D manufacturing and packaging technology, Foveros. Read more…

Julia Update: Adoption Keeps Climbing; Is It a Python Challenger?

January 13, 2021

The rapid adoption of Julia, the open source, high level programing language with roots at MIT, shows no sign of slowing according to data from Julialang.org. I Read more…

AMD Chipmaker TSMC to Use AMD Chips for Chipmaking

May 8, 2021

TSMC has tapped AMD to support its major manufacturing and R&D workloads. AMD will provide its Epyc Rome 7702P CPUs – with 64 cores operating at a base cl Read more…

Intel Launches 10nm ‘Ice Lake’ Datacenter CPU with Up to 40 Cores

April 6, 2021

The wait is over. Today Intel officially launched its 10nm datacenter CPU, the third-generation Intel Xeon Scalable processor, codenamed Ice Lake. With up to 40 Read more…

CERN Is Betting Big on Exascale

April 1, 2021

The European Organization for Nuclear Research (CERN) involves 23 countries, 15,000 researchers, billions of dollars a year, and the biggest machine in the worl Read more…

HPE Launches Storage Line Loaded with IBM’s Spectrum Scale File System

April 6, 2021

HPE today launched a new family of storage solutions bundled with IBM’s Spectrum Scale Erasure Code Edition parallel file system (description below) and featu Read more…

10nm, 7nm, 5nm…. Should the Chip Nanometer Metric Be Replaced?

June 1, 2020

The biggest cool factor in server chips is the nanometer. AMD beating Intel to a CPU built on a 7nm process node* – with 5nm and 3nm on the way – has been i Read more…

Saudi Aramco Unveils Dammam 7, Its New Top Ten Supercomputer

January 21, 2021

By revenue, oil and gas giant Saudi Aramco is one of the largest companies in the world, and it has historically employed commensurate amounts of supercomputing Read more…

Quantum Computer Start-up IonQ Plans IPO via SPAC

March 8, 2021

IonQ, a Maryland-based quantum computing start-up working with ion trap technology, plans to go public via a Special Purpose Acquisition Company (SPAC) merger a Read more…

Leading Solution Providers

Contributors

Can Deep Learning Replace Numerical Weather Prediction?

March 3, 2021

Numerical weather prediction (NWP) is a mainstay of supercomputing. Some of the first applications of the first supercomputers dealt with climate modeling, and Read more…

AMD Launches Epyc ‘Milan’ with 19 SKUs for HPC, Enterprise and Hyperscale

March 15, 2021

At a virtual launch event held today (Monday), AMD revealed its third-generation Epyc “Milan” CPU lineup: a set of 19 SKUs -- including the flagship 64-core, 280-watt 7763 part --  aimed at HPC, enterprise and cloud workloads. Notably, the third-gen Epyc Milan chips achieve 19 percent... Read more…

Livermore’s El Capitan Supercomputer to Debut HPE ‘Rabbit’ Near Node Local Storage

February 18, 2021

A near node local storage innovation called Rabbit factored heavily into Lawrence Livermore National Laboratory’s decision to select Cray’s proposal for its CORAL-2 machine, the lab’s first exascale-class supercomputer, El Capitan. Details of this new storage technology were revealed... Read more…

African Supercomputing Center Inaugurates ‘Toubkal,’ Most Powerful Supercomputer on the Continent

February 25, 2021

Historically, Africa hasn’t exactly been synonymous with supercomputing. There are only a handful of supercomputers on the continent, with few ranking on the Read more…

GTC21: Nvidia Launches cuQuantum; Dips a Toe in Quantum Computing

April 13, 2021

Yesterday Nvidia officially dipped a toe into quantum computing with the launch of cuQuantum SDK, a development platform for simulating quantum circuits on GPU-accelerated systems. As Nvidia CEO Jensen Huang emphasized in his keynote, Nvidia doesn’t plan to build... Read more…

New Deep Learning Algorithm Solves Rubik’s Cube

July 25, 2018

Solving (and attempting to solve) Rubik’s Cube has delighted millions of puzzle lovers since 1974 when the cube was invented by Hungarian sculptor and archite Read more…

The History of Supercomputing vs. COVID-19

March 9, 2021

The COVID-19 pandemic poses a greater challenge to the high-performance computing community than any before. HPCwire's coverage of the supercomputing response t Read more…

HPE Names Justin Hotard New HPC Chief as Pete Ungaro Departs

March 2, 2021

HPE CEO Antonio Neri announced today (March 2, 2021) the appointment of Justin Hotard as general manager of HPC, mission critical solutions and labs, effective Read more…

  • arrow
  • Click Here for More Headlines
  • arrow
HPCwire