Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication

Kuikui Li; Meixia Tao; Jingjing Zhang; Osvaldo Simeone

doi:10.1109/TCOMM.2021.3053018

Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication

Kuikui Li, Meixia Tao, Jingjing Zhang, Osvaldo Simeone

King's College London

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

Abstract

Consider a multi-cell mobile edge computing network, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix. This is done through task offloading by means of input uploading, distributed computing at edge nodes (ENs), and output downloading. Task offloading may suffer long delay since servers at some ENs may be straggling due to random computation time, and wireless channels may experience severe fading and interference. This paper aims to investigate the interplay among upload, computation, and download latencies during the offloading process in the high signal-to-noise ratio regime from an information-theoretic perspective. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for a sufficiently large upload time. By investing more time in uplink transmission, the policy creates data redundancy at the ENs, which can reduce the computation time, by enabling the use of coded computing, as well as the download time via transmitter cooperation. Moreover, the policy allows computation time to be traded for download time. Numerical examples demonstrate that the proposed policy can improve over existing schemes by significantly reducing the end-to-end execution time.

Original language	English
Article number	9328810
Pages (from-to)	2224-2239
Number of pages	16
Journal	IEEE TRANSACTIONS ON COMMUNICATIONS
Volume	69
Issue number	4
DOIs	https://doi.org/10.1109/TCOMM.2021.3053018
Publication status	Published - Apr 2021

Keywords

Coded Computing
Downlink
Edge Computing
Encoding
Interference
Matrix Multiplication
Redundancy
Servers
Straggler
Task analysis
Transmission Cooperation
Uplink

Access to Document

10.1109/TCOMM.2021.3053018

Cite this

@article{d8381b6141ce46f4a46c14cfa9dacf57,

title = "Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication",

abstract = "Consider a multi-cell mobile edge computing network, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix. This is done through task offloading by means of input uploading, distributed computing at edge nodes (ENs), and output downloading. Task offloading may suffer long delay since servers at some ENs may be straggling due to random computation time, and wireless channels may experience severe fading and interference. This paper aims to investigate the interplay among upload, computation, and download latencies during the offloading process in the high signal-to-noise ratio regime from an information-theoretic perspective. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for a sufficiently large upload time. By investing more time in uplink transmission, the policy creates data redundancy at the ENs, which can reduce the computation time, by enabling the use of coded computing, as well as the download time via transmitter cooperation. Moreover, the policy allows computation time to be traded for download time. Numerical examples demonstrate that the proposed policy can improve over existing schemes by significantly reducing the end-to-end execution time.",

keywords = "Coded Computing, Downlink, Edge Computing, Encoding, Interference, Matrix Multiplication, Redundancy, Servers, Straggler, Task analysis, Transmission Cooperation, Uplink",

author = "Kuikui Li and Meixia Tao and Jingjing Zhang and Osvaldo Simeone",

note = "Funding Information: The work by K. Li and M. Tao is supported by the National Key R&D Project of China under grant 2020YFB1406802 and the National Natural Science Foundation of China under grant 61941106. The work by J. Zhang and O. Simeone is supported by the European Research Council under the European Union's Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731). Funding Information: Manuscript received July 4, 2020; revised December 1, 2020; accepted January 11, 2021. Date of publication January 20, 2021; date of current version April 16, 2021. The work by K. Li and M. Tao is supported by the National Key R&D Project of China under grant 2020YFB1406802 and the National Natural Science Foundation of China under grant 61941106. The work by J. Zhang and O. Simeone is supported by the European Research Council under the European Union{\textquoteright}s Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731). This article was presented in part at the 2020 IEEE International Symposium on Information Theory (IEEE ISIT 2020). The associate editor coordinating the review of this article and approving it for publication was R. Thobaben. (Corresponding author: Meixia Tao.) Kuikui Li and Meixia Tao are with the Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: [email protected]; [email protected]). Publisher Copyright: {\textcopyright} 1972-2012 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

month = apr,

doi = "10.1109/TCOMM.2021.3053018",

language = "English",

volume = "69",

pages = "2224--2239",

journal = "IEEE TRANSACTIONS ON COMMUNICATIONS",

issn = "0090-6778",

publisher = "I E E E",

number = "4",

}

TY - JOUR

T1 - Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication

AU - Li, Kuikui

AU - Tao, Meixia

AU - Zhang, Jingjing

AU - Simeone, Osvaldo

N1 - Funding Information: The work by K. Li and M. Tao is supported by the National Key R&D Project of China under grant 2020YFB1406802 and the National Natural Science Foundation of China under grant 61941106. The work by J. Zhang and O. Simeone is supported by the European Research Council under the European Union's Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731). Funding Information: Manuscript received July 4, 2020; revised December 1, 2020; accepted January 11, 2021. Date of publication January 20, 2021; date of current version April 16, 2021. The work by K. Li and M. Tao is supported by the National Key R&D Project of China under grant 2020YFB1406802 and the National Natural Science Foundation of China under grant 61941106. The work by J. Zhang and O. Simeone is supported by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731). This article was presented in part at the 2020 IEEE International Symposium on Information Theory (IEEE ISIT 2020). The associate editor coordinating the review of this article and approving it for publication was R. Thobaben. (Corresponding author: Meixia Tao.) Kuikui Li and Meixia Tao are with the Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: [email protected]; [email protected]). Publisher Copyright: © 1972-2012 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/4

Y1 - 2021/4

N2 - Consider a multi-cell mobile edge computing network, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix. This is done through task offloading by means of input uploading, distributed computing at edge nodes (ENs), and output downloading. Task offloading may suffer long delay since servers at some ENs may be straggling due to random computation time, and wireless channels may experience severe fading and interference. This paper aims to investigate the interplay among upload, computation, and download latencies during the offloading process in the high signal-to-noise ratio regime from an information-theoretic perspective. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for a sufficiently large upload time. By investing more time in uplink transmission, the policy creates data redundancy at the ENs, which can reduce the computation time, by enabling the use of coded computing, as well as the download time via transmitter cooperation. Moreover, the policy allows computation time to be traded for download time. Numerical examples demonstrate that the proposed policy can improve over existing schemes by significantly reducing the end-to-end execution time.

AB - Consider a multi-cell mobile edge computing network, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix. This is done through task offloading by means of input uploading, distributed computing at edge nodes (ENs), and output downloading. Task offloading may suffer long delay since servers at some ENs may be straggling due to random computation time, and wireless channels may experience severe fading and interference. This paper aims to investigate the interplay among upload, computation, and download latencies during the offloading process in the high signal-to-noise ratio regime from an information-theoretic perspective. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for a sufficiently large upload time. By investing more time in uplink transmission, the policy creates data redundancy at the ENs, which can reduce the computation time, by enabling the use of coded computing, as well as the download time via transmitter cooperation. Moreover, the policy allows computation time to be traded for download time. Numerical examples demonstrate that the proposed policy can improve over existing schemes by significantly reducing the end-to-end execution time.

KW - Coded Computing

KW - Downlink

KW - Edge Computing

KW - Encoding

KW - Interference

KW - Matrix Multiplication

KW - Redundancy

KW - Servers

KW - Straggler

KW - Task analysis

KW - Transmission Cooperation

KW - Uplink

UR - http://www.scopus.com/inward/record.url?scp=85099730771&partnerID=8YFLogxK

U2 - 10.1109/TCOMM.2021.3053018

DO - 10.1109/TCOMM.2021.3053018

M3 - Article

AN - SCOPUS:85099730771

SN - 0090-6778

VL - 69

SP - 2224

EP - 2239

JO - IEEE TRANSACTIONS ON COMMUNICATIONS

JF - IEEE TRANSACTIONS ON COMMUNICATIONS

IS - 4

M1 - 9328810

ER -

Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this