The Library
Hierarchical coded matrix multiplication in heterogeneous multi-hop networks
Tools
Tools
Tools
Zhu, Hongtao, Chen, Li, Zhao, Nan, Chen, Yunfei, Wang, Weidong and Yu, F. Richard (2022) Hierarchical coded matrix multiplication in heterogeneous multi-hop networks. IEEE Transactions on Communications, 70 (6). pp. 3597-3612. doi:10.1109/TCOMM.2022.3164056 ISSN 0090-6778.
|
PDF
WRAP-hierarchical-coded-matrix-multiplication-heterogeneous-multi-hop-networks-Chen-2022.pdf - Accepted Version - Requires a PDF viewer. Download (5Mb) | Preview |
Official URL: https://doi.org/10.1109/TCOMM.2022.3164056
Abstract
The performance of distributed computing is restricted by the slowest worker nodes, known as stragglers, in the system. Coded computation has emerged as an efficient technique to mitigate the straggler effects in distributed computing. Most existing works only considered the computation straggler for single-hop networks. However, in multi-hop networks, the straggler effects will occur not only on worker nodes but also on relay nodes. In this paper, we consider a heterogeneous multi-hop network. The nodes in the network are heterogeneous, i.e., their computation capacities and transmission capacities are different. We propose a hierarchical coding scheme for such a network. Firstly, we reorganize it into a hierarchical network containing multiple layers. Each layer in the network consists of several groups. Then, a new hierarchical coding scheme is proposed, where coding is applied to each group to mitigate the stragglers. By taking both the computation time and transmission time into consideration, the overall task completion time is derived. To improve the performance of the network, heterogeneous hierarchical coded computation (HHCC) algorithm is proposed to provide an asymptotically optimal task allocation strategy. Compared with existing uniform uncoded, load balanced uncoded, and heterogeneous coded matrix multiplication schemes, HHCC has significant improvement.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Engineering > Engineering | |||||||||
| Library of Congress Subject Headings (LCSH): | Coding theory, Electronic data processing -- Distributed processing, Computer network protocols, Ad hoc networks (Computer networks) | |||||||||
| Journal or Publication Title: | IEEE Transactions on Communications | |||||||||
| Publisher: | IEEE | |||||||||
| ISSN: | 0090-6778 | |||||||||
| Official Date: | June 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 70 | |||||||||
| Number: | 6 | |||||||||
| Page Range: | pp. 3597-3612 | |||||||||
| DOI: | 10.1109/TCOMM.2022.3164056 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Reuse Statement (publisher, data, author rights): | © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 4 April 2022 | |||||||||
| Date of first compliant Open Access: | 5 April 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
