检索结果-内蒙古大学图书馆

Secure and Flexible coded distributed Matrix Multiplication Based on Edge computing for Industrial Metaverse

IEEE TRANSACTIONS ON CLOUD computing 2024年第4期12卷 1026-1041页

作者： Qiu, Houming Zhu, Kun Niyato, Dusit Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

The Industrial Metaverse is driving a new revolution wave for smart manufacturing domain by reproducing the real industrial environment in a virtual space. Real-time synchronization and rendering of all industrial factors result in numerous time-sensitive and computation-intensive tasks, especially matrix multiplication. distributed edge computing (DEC) can be exploited to handle these tasks due to its low-latency and powerful computing. In this paper, we propose an efficient and reliable coded DEC framework to compute large-scale matrix multiplication tasks. However, an existence of stragglers causes high computation latency that seriously limits the application of DEC in the Industrial Metaverse. To mitigate the impact of stragglers, we design a secure and flexible PolyDot (SFPD) code, which enables information theoretic security (ITS) protection. Several improvements can be achieved with the proposed SFPD. First, it can achieve a smaller recovery threshold than that of the existing codes in almost all settings. And compared with the original PolyDot codes, our SFPD code considers the extra workers required to add ITS protection. It also provides a flexible tradeoff between recovery threshold and communication & computation loads by simply adjusting two given storage parameters p and t. Furthermore, as an important application scenario, the SFPD code is employed to secure model training in machine learning, which can alleviate the straggler effects and protect ITS of raw data. The experiments demonstrate that the SFPD code can significantly speed up the training process while providing ITS of data. Finally, we provide comprehensive performance analysis which shows the superiority of the SFPD code.

关键词： Codes Metaverse Task analysis Servers Training Polynomials Encoding coded distributed computing edge computing machine learning matrix multiplication metaverse recovery threshold security stragglers tradeoff

来源：评论

学校读者我要写书评

暂无评论

A New Combinatorial coded Design for Heterogeneous distributed computing

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第9期69卷 5672-5685页

作者： Woolsey, Nicholas Chen, Rong-Rong Ji, Mingyue Univ Utah Dept Elect Engn Salt Lake City UT 84112 USA

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.

关键词： coded distributed computing communication load computation load coded multicasting heterogeneity low-complexity

来源：评论

学校读者我要写书评

暂无评论

On Batch-Processing Based coded computing for Heterogeneous distributed computing Systems

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2021年第3期8卷 2438-2454页

作者： Wang, Baoqian Xie, Junfei Lu, Kejie Wan, Yan Fu, Shengli San Diego State Univ Dept Elect & Comp Engn San Diego CA 92182 USA Univ Calif San Diego San Diego CA 92182 USA Univ Puerto Rico Dept Comp Sci & Engn Mayaguez PR 00681 USA Univ Texas Arlington Dept Elect Engn Arlington TX 76019 USA Univ North Texas Dept Elect Engn Denton TX 76201 USA

In recent years, coded distributed computing (CDC) has attracted significant attention, because it can efficiently facilitate many delay-sensitive computation tasks against unexpected latencies in distributed computing systems. Despite such a salient feature, many design challenges and opportunities remain. In this paper, we focus on practical computing systems with heterogeneous computing resources, and design a novel CDC approach, called batch-processing based coded computing (BPCC), which exploits the fact that every computing node can obtain some coded results before it completes the whole task. To this end, we first describe the main idea of the BPCC framework, and then formulate an optimization problem for BPCC to minimize the task completion time by configuring the computation load. Through formal theoretical analyses, extensive simulation studies, and comprehensive real experiments on the Amazon EC2 computing clusters, we demonstrate promising performance of the proposed BPCC scheme, in terms of high computational efficiency and robustness to uncertain disturbances.

关键词： Task analysis distributed computing Encoding Optimization Computational modeling Heterogeneous networks Resource management coded distributed computing heterogeneous computing cluster batch-processing asymptotic optimality latency

来源：评论

学校读者我要写书评

暂无评论

coded Reactive Stragglers Mitigation in distributed computing Systems

Coded Reactive Stragglers Mitigation in Distributed Computin...

引用

IEEE International Conference on Communications (IEEE ICC)

作者： Ardakani, Maryam Haghighi Ardakani, Masoud Tellambura, Chintha Univ Alberta Dept Elect & Comp Engn Edmonton AB Canada

ISBN: (纸本)9781538674628

In distributed computing systems, to mitigate the adverse effect of stragglers on the computation time, computation redundancy is used. The redundancy can be added proactively at the beginning, or reactively after some time based on the delay pattern of the workers. While most of the existing work with reactive mitigation strategy only considered task replication, we propose a coded reactive straggler mitigation with an uncoded and a coded phase for distributed matrix-matrix multiplication. Specifically, in the uncoded phase of the proposed reactive strategy, the master distributes the computational job without redundancy among workers and waits for some time. After the waiting time, the master cancels the remaining tasks. It then encodes the remaining tasks and distributes them among the workers that have already completed their computations. The expected execution time of the proposed method is analytically obtained. Furthermore, the optimal waiting time for the uncoded phase and the optimal code rate for the coded phase are investigated. Our simulation results demonstrate that the proposed coded reactive mitigation strategy significantly decreases the execution time in comparison with the proactive mitigation strategy or repetition-based reactive mitigation strategy.

关键词： coded distributed computing stragglers mitigation reactive stragglers mitigation MatDot coded matrix-matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Folded Polynomial Codes for coded distributed AA^{inverted perpendicular}-Type Matrix Multiplication

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2023年第9期71卷 5051-5064页

作者： Xu, Jingke Zhang, Yaqian Wang, Libo Shandong Agr Univ Sch Informat Sci & Engn ing Tai An 271018 Peoples R China Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China Hubei Univ Sch Cyber Sci & Technol Wuhan 430062 Peoples R China

In this paper, due to the important value in practical applications, we consider the coded distributed matrix multiplication problem of computing AA(inverted perpendicular) in a distributed computing system with N worker nodes and a master node, where the input matrices A and A(inverted perpendicular) are partitioned into m-by-p and p-by-m blocks of equal-size sub-matrices respectively. For effective straggler mitigation, we propose a novel computation strategy, named folded polynomial code, which is obtained by modifying the entangled polynomial codes. Moreover, we characterize a lower bound on the optimal recovery threshold among all linear computation strategies when the underlying field is the real number field, and our folded polynomial codes can achieve this bound in the case of m = 1. Compared with all known computation strategies for coded distributed matrix multiplication, our folded polynomial codes outperform them in terms of recovery threshold, download cost, and decoding complexity.

关键词： coded distributed computing matrix multiplication recovery threshold folded polynomials

来源：评论

学校读者我要写书评

暂无评论

Optimal Load Allocation for coded distributed Computation in Heterogeneous Clusters

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第1期69卷 44-58页

作者： Kim, Daejin Park, Hyegyeong Choi, Jun Kyun Samsung Elect Suwon 16677 South Korea Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA Korea Adv Inst Sci & Technol KAIST Sch Elect Engn Daejeon 34141 South Korea

Recently, coding has been a useful technique to mitigate stragglers' effect in distributed computing. However, coding in this context has been mainly explored assuming homogeneous workers, although real-world clusters often consist of heterogeneous workers with different computing capabilities. The uniform load allocation without considering the heterogeneity possibly causes a significant loss in latency. In this article, we suggest the optimal load allocation for coded distributed computing with heterogeneous workers. Specifically, we focus on the scenario that there exist workers having the same computing capability, which can be regarded as a group for analysis. We rely on the lower bound on the expected latency and obtain the optimal load allocation by showing that our load allocation achieves the minimum of the lower bound for a sufficiently large number of workers. Given the proposed optimal load allocation, we derive the optimal code rate to achieve the minimum expected latency. From numerical simulations, when assuming the group heterogeneity, our load allocation reduces the expected latency by orders of magnitude over the existing scheme. Furthermore, from experiments on Amazon EC2 for scenarios with distinct straggler/heterogeneity patterns, we observe that our scheme outperforms the competing schemes reducing the total finishing time by up to 52%.

关键词： coded distributed computing heterogeneous clusters optimal load allocation

来源：评论

学校读者我要写书评

暂无评论

RANDOM SAMPLING FOR distributed coded MATRIX MULTIPLICATION 44

RANDOM SAMPLING FOR DISTRIBUTED CODED MATRIX MULTIPLICATION

引用

44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Chang, Wei-Ting Tandon, Ravi Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA

ISBN: (纸本)9781479981311

Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower computations). In many scenarios, instead of exact computation, approximate matrix multiplication, i.e., allowing for a tolerable error is also sufficient. Such approximate schemes make use of randomization techniques to speed up the computation process. In this paper, we initiate the study of approximate coded matrix multiplication, and investigate the joint synergies offered by randomization and coding. Specifically, we propose two coded randomized sampling schemes that use (a) codes to achieve a desired recovery threshold and (b) random sampling to obtain approximation of the matrix multiplication. Tradeoffs between the recovery threshold and approximation error obtained through random sampling are investigated for a class of coded matrix multiplication schemes.

关键词： Matrix multiplication Random sampling coded distributed computing

来源：评论

学校读者我要写书评

暂无评论

On distributed computing With Heterogeneous Communication Constraints

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2022年第6期30卷 2776-2787页

作者： Shakya, Nishant Li, Fan Chen, Jinyuan Louisiana Tech Univ Dept Elect Engn Ruston LA 71272 USA Home Depot Inc Kansas City MO 64086 USA Louisiana Tech Univ Dept Elect Engn Ruston LA 71272 USA

We consider a distributed computing framework where the distributed nodes have different communication capabilities, motivated by the heterogeneous networks in data centers and mobile edge computing systems. Following the structure of MapReduce, this framework consists of Map computation phase, Shuffle phase, and Reduce computation phase. The Shuffle phase allows distributed nodes to exchange intermediate values, in the presence of heterogeneous communication bottlenecks for different nodes (heterogeneous communication load constraints). For this setting, we characterize the minimum total computation load and the minimum worst-case computation load in some cases, under the heterogeneous communication load constraints. While the total computation load depends on the sum of the computation loads of all the nodes, the worst-case computation load depends on the computation load of a node with the heaviest job. We show an interesting insight that, for some cases, there is a tradeoff between the minimum total computation load and the minimum worst-case computation load, in the sense that both cannot be achieved at the same time. The achievability schemes are proposed with careful design on the file assignment and the data shuffling. Beyond the cut-set bound, a novel converse is proposed using the proof by contradiction. For the general case, we identify two extreme regimes in which both the scheme with coding and the scheme without coding are optimal, respectively.

关键词： distributed computing heterogeneous com-munication constraints MapReduce coded distributed computing worst-case computation load proof by contradiction information-theoretical bound

来源：评论

学校读者我要写书评

暂无评论

A Double Auction Mechanism for Resource Allocation in coded Vehicular Edge computing

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第2期71卷 1832-1845页

作者： Ng, Jer Shyuan Lim, W. Lim Bryan Xiong, Zehui Niyato, Dusit Leung, Cyril Miao, Chunyan Nanyang Technol Univ Alibaba Grp Singapore 639798 Singapore Nanyang Technol Univ Alibaba NTU Joint Res Inst Singapore 639798 Singapore Singapore Univ Technol & Design Pillar Informat Syst Technol & Design Singapore 487372 Singapore Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Joint NTU UBC Res Ctr Excellence Act Living Elder Singapore Singapore Univ British Columbia Vancouver BC V6T 1Z4 Canada Nanyang Technol Univ Joint NTU UBC Res Ctr Excellence Act Living Elder Singapore 639798 Singapore

The development of smart vehicles and rich cloud services have led to the emergence of vehicular edge computing. To perform the distributed computation tasks efficiently, coded distributed computing (CDC) was proposed to reduce communication costs and mitigate the straggler effects through the use of coding techniques. In this paper, we propose a double auction mechanism to allocate the resources of the edge servers to the vehicles in order to complete the CDC tasks. Specifically, the vehicles use the PolyDot codes to manage the tradeoff between communication costs and recovery threshold. Given the requirements of various vehicles, the double auction mechanism matches the edge servers with the required resources to the vehicles. Besides, the double auction mechanism also determines the prices that the vehicles need to pay for the resources of the edge servers. The analyses show that the double auction mechanism satisfies the properties of individual rationality, incentive compatibility and budget-balance. From the simulation, the utility of auctioneer increases when the number of vehicles and edge servers increases.

关键词： Servers Task analysis Costs Encoding Edge computing Codes Computational modeling coded distributed computing double auction resource allocation straggler effects

来源：评论

学校读者我要写书评

暂无评论

Edge computing-Aided coded Vertical Federated Linear Regression

引用

IEEE TRANSACTIONS ON COGNITIVE COMMUNICATIONS AND NETWORKING 2022年第3期8卷 1543-1551页

作者： Dai, Mingjun Zheng, Ziying Hong, Zhaoyan Zhang, Shengli Wang, Hui Shenzhen Univ Coll Elect & Informat Engn Guangdong Prov Engn Ctr Ubiquitous Comp & Intelli Shenzhen 518060 Peoples R China Shenzhen Univ Coll Math & Stat Shenzhen 518060 Peoples R China Shenzhen Inst Informat Technol Commun Engn Dept Shenzhen 518109 Peoples R China

For the training process of federated linear regression (FLR), which is the simplest form of federated learning, the integrated computation at each company is slowed down either by huge volume data or by time-consuming homomorphic encryption. Targetted at accelerating the training process of FLR, through the incorporation of edge computing aided coded distributed computing (CDC) into intensive computation (matrix multiplication), a novel coded FLR framework is proposed where several edge nodes aid the computing of one company. Two schemes, including linear combination (LC)-based vertical FLR and Matdot-based vertical FLR, are proposed and designed, which enjoy in-parallel computation and homomorphic encryption at the edge nodes. Since workload at each edge node is reduced significantly, the training runtime of these two schemes may be reduced significantly. Numerical studies show that our proposed coded schemes outperform traditional uncoded schemes significantly in terms of overall runtime (sum of encoding, computing, and decoding phases) of the training process. Besides, among the two proposed coded schemes, LC-based scheme and Matdot-based scheme each has its own advantage scenarios which conforms with the analysis.

关键词： Vertical federated learning federated linear regression coded distributed computing edge computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：