Performance optimization of Hadoop workflows in public clouds through adaptive task partitioning

Tong Shu, Chase Q. Wu

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

7 Scopus citations

Abstract

Cloud computing provides a cost-effective computing platform for big data workflows where moldable parallel computing models such as MapReduce are widely applied to meet stringent performance requirements. The granularity of task partitioning in each moldable job has a significant impact on workflow completion time and financial cost. We investigate the properties of moldable jobs and design a big-data workflow mapping model, based on which, we formulate a workflow mapping problem to minimize workflow makespan under a budget constraint in public clouds. We show this problem to be strongly NP-complete and design i) a fully polynomial-time approximation scheme (FPTAS) for a special case with a pipeline-structured workflow executed on virtual machines in a single class, and ii) a heuristic for a generalized problem with an arbitrary directed acyclic graph-structured workflow executed on virtual machines in multiple classes. The performance superiority of the proposed solution is illustrated by extensive simulation-based results in Hadoop/YARN in comparison with existing workflow mapping models and algorithms.

Original languageEnglish (US)
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509053360
DOIs
StatePublished - Oct 2 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: May 1 2017May 4 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

Other2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States
CityAtlanta
Period5/1/175/4/17

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Performance optimization of Hadoop workflows in public clouds through adaptive task partitioning'. Together they form a unique fingerprint.

Cite this