NDLI: Fast and Efficient Graph Traversal Algorithm for CPUs: Maximizing Single-Node Efficiency

Content Provider	IEEE Xplore Digital Library
Author	Chhugani, J. Satish, N. Changkyu Kim Sewall, J. Dubey, P.
Copyright Year	2012
Abstract	Graph-based structures are being increasingly used to model data and relations among data in a number of fields. Graph-based databases are becoming more popular as a means to better represent such data. Graph traversal is a key component in graph algorithms such as reach ability and graph matching. Since the scale of data stored and queried in these databases is increasing, it is important to obtain high performing implementations of graph traversal that can efficiently utilize the processing power of modern processors. In this work, we present a scalable Breadth-First Search Traversal algorithm for modern multi-socket, multi-core CPUs. Our algorithm uses lock- and atomic-free operations on a cache-resident structure for arbitrary sized graphs to filter out expensive main memory accesses, and completely and efficiently utilizes all available bandwidth resources. We propose a work distribution approach for multi-socket platforms that ensures load-balancing while keeping cross-socket communication low. We provide a detailed analytical model that accurately projects the performance of our single- and multi-socket traversal algorithms to within 5-10% of obtained performance. Our analytical model serves as a useful tool to analyze performance bottlenecks on modern CPUs. When measured on various synthetic and real-world graphs with a wide range of graph sizes, vertex degrees and graph diameters, our implementation on a dual-socket Intel (R) Xeon (R) X5570 (Intel micro architecture code name Nehalem) system achieves 1.5X -- 13.2X performance speedup over the best reported numbers. We achieve around 1 Billion traversed edges per second on a scale free R-MAT graph with 64M vertices and 2 Billion edges on a dual-socket Nehalem system. Our optimized algorithm is useful as a building block for efficient multi-node implementations and future exascale systems, thereby allowing them to ride the trend of increasing per-node compute and bandwidth resources.
Starting Page	378
Ending Page	389
File Size	782636
Page Count	12
File Format	PDF
ISBN	9781467309752
ISSN	15302075
DOI	10.1109/IPDPS.2012.43
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Sockets Arrays Bandwidth Instruction sets Partitioning algorithms bandwidth Graph traversal multi-socket single node efficient
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multi-threaded Graph Partitioning

Closed cube computation on multi-core CPUs

Performance analysis & improvement of SNPHAP on Multi-core CPUs

Main-memory hash joins on multi-core CPUs: Tuning to the underlying hardware

Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths

An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU

Continuous k-Nearest Neighbor Queries on Multi-core CPUs

A Novel Multithreaded Algorithm for Extracting Maximal Chordal Subgraphs

Work efficient parallel algorithms for large graph exploration

Fast and Efficient Graph Traversal Algorithm for CPUs: Maximizing Single-Node Efficiency

Similar Documents

Multi-threaded Graph Partitioning

Closed cube computation on multi-core CPUs

Performance analysis & improvement of SNPHAP on Multi-core CPUs

Main-memory hash joins on multi-core CPUs: Tuning to the underlying hardware

Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths

An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU

Continuous k-Nearest Neighbor Queries on Multi-core CPUs

A Novel Multithreaded Algorithm for Extracting Maximal Chordal Subgraphs

Work efficient parallel algorithms for large graph exploration

Fast and Efficient Graph Traversal Algorithm for CPUs: Maximizing Single-Node Efficiency