View in EDS

A New Combinatorial Coded Design for Heterogeneous Distributed Computing.

Saved in:
Bibliographic Details
Title: A New Combinatorial Coded Design for Heterogeneous Distributed Computing.
Authors: Woolsey, Nicholas1 nicholas.woolsey@utah.edu, Chen, Rong-Rong1 rchen@ece.utah.edu, Ji, Mingyue1 mingyue.ji@utah.edu
Source: IEEE Transactions on Communications. Sep2021, Vol. 69 Issue 9, p5672-5685. 14p.
Subjects: Heterogeneous distributed computing, Grid computing, Distributed computing
Abstract: Coded Distributed Computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce and Spark. In particular, increasing the computation load in the Map phase by a factor of $r$ can create coded multicasting opportunities to reduce the communication load in the Shuffle phase by the same factor. However, the CDC scheme is designed for the homogeneous settings, where each node maps the same number of files and is assigned the same number of reduce functions. It requires an exponentially large number of input files (data batches), reduce functions and multicasting groups relative to the number of nodes to achieve the promised gain. We address the CDC limitations by proposing a novel CDC approach based on a combinatorial design, which accommodates heterogeneous networks and maintains a multiplicative computation-communication trade-off. In addition, the proposed approach requires an exponentially less number of input files compared to the original CDC scheme proposed by Li et al. Finally, we derive a new information theoretic converse for general heterogeneous CDC and show that the communication load of the proposed design is optimal within a constant factor. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 153710922
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A New Combinatorial Coded Design for Heterogeneous Distributed Computing.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Woolsey%2C+Nicholas%22">Woolsey, Nicholas</searchLink><relatesTo>1</relatesTo><i> nicholas.woolsey@utah.edu</i><br /><searchLink fieldCode="AR" term="%22Chen%2C+Rong-Rong%22">Chen, Rong-Rong</searchLink><relatesTo>1</relatesTo><i> rchen@ece.utah.edu</i><br /><searchLink fieldCode="AR" term="%22Ji%2C+Mingyue%22">Ji, Mingyue</searchLink><relatesTo>1</relatesTo><i> mingyue.ji@utah.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Communications%22">IEEE Transactions on Communications</searchLink>. Sep2021, Vol. 69 Issue 9, p5672-5685. 14p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Heterogeneous+distributed+computing%22">Heterogeneous distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Grid+computing%22">Grid computing</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Coded Distributed Computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce and Spark. In particular, increasing the computation load in the Map phase by a factor of $r$ can create coded multicasting opportunities to reduce the communication load in the Shuffle phase by the same factor. However, the CDC scheme is designed for the homogeneous settings, where each node maps the same number of files and is assigned the same number of reduce functions. It requires an exponentially large number of input files (data batches), reduce functions and multicasting groups relative to the number of nodes to achieve the promised gain. We address the CDC limitations by proposing a novel CDC approach based on a combinatorial design, which accommodates heterogeneous networks and maintains a multiplicative computation-communication trade-off. In addition, the proposed approach requires an exponentially less number of input files compared to the original CDC scheme proposed by Li et al. Finally, we derive a new information theoretic converse for general heterogeneous CDC and show that the communication load of the proposed design is optimal within a constant factor. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=153710922
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TCOMM.2021.3087628
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 14
        StartPage: 5672
    Subjects:
      – SubjectFull: Heterogeneous distributed computing
        Type: general
      – SubjectFull: Grid computing
        Type: general
      – SubjectFull: Distributed computing
        Type: general
    Titles:
      – TitleFull: A New Combinatorial Coded Design for Heterogeneous Distributed Computing.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Woolsey, Nicholas
      – PersonEntity:
          Name:
            NameFull: Chen, Rong-Rong
      – PersonEntity:
          Name:
            NameFull: Ji, Mingyue
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2021
              Type: published
              Y: 2021
          Identifiers:
            – Type: issn-print
              Value: 00906778
          Numbering:
            – Type: volume
              Value: 69
            – Type: issue
              Value: 9
          Titles:
            – TitleFull: IEEE Transactions on Communications
              Type: main
ResultId 1