Predictive modeling and scalability analysis for large graph analytics

Sourav Medya, Ludmila Cherkasova, Ambuj Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Many HPC and modern large graph processing applications belong to a class of scale-out applications, where the application dataset is partitioned and processed by a cluster of machines. Assessing the application scalability is one of the primary goals during such application implementation. Typically, in the design phase, programmers are limited by a small size cluster available for their experiments. Therefore, predictive modeling is required for the analysis of the application scalability and its performance in a larger cluster. While in an increased size cluster, each node will process a smaller portion of the original dataset, a higher communication volume between a larger number of nodes may cripple the application scalability and provide diminishing performance benefits. One of the main challenges is the analysis of bandwidth demands due to an increased communication volume in a larger size cluster. In this paper1, we introduce a novel regression-based approach to assess the scalability and performance of a distributed memory program for execution in a large-scale cluster. Our solution involves 1) a limited set of traditional experiments performed in a small size cluster and 2) an additional set of similar experiments performed with an "interconnect bandwidth throttling" tool, which exposes the bandwidth impact on the application performance. These measurements are used in creating an ensemble of analytical models for performance and scalability analysis. Using a linear regression approach, step by step, we incorporate into the model the following important parameters: i) the number of cluster nodes and application processes, ii) the dataset size, and iii) interconnect bandwidth. We demonstrate our solution, its power, and accuracy using a popular Graph500 benchmark, which implements a Breadth First Search algorithm on large, synthetically generated graphs. By utilizing measurements collected in a 32-node cluster, we are able to project the program performance in a large size cluster with hundreds of nodes. The proposed approach and derived models help to provide an early feedback to programmers on the scalability and efficiency of their solution.

Original languageEnglish (US)
Title of host publicationProceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management
EditorsProsper Chemouil, Paulo Simoes, Edmundo Madeira, Stefano Secci, Edmundo Monteiro, Luciano Paschoal Gaspary, Carlos Raniery P. dos Santos, Marinos Charalambides
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages63-71
Number of pages9
ISBN (Electronic)9783901882890
DOIs
StatePublished - Jul 20 2017
Externally publishedYes
Event15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017 - Lisbon, Portugal
Duration: May 8 2017May 12 2017

Publication series

NameProceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management

Conference

Conference15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017
Country/TerritoryPortugal
CityLisbon
Period5/8/175/12/17

Funding

VIII. ACKNOWLEDGMENTS Research was partially supported by the IIS-1219254 grant from the NSF.

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Predictive modeling and scalability analysis for large graph analytics'. Together they form a unique fingerprint.

Cite this