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

Elastic Resource Allocation for coded distributed computing Over Heterogeneous Wireless Edge Networks

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2023年第4期22卷 2636-2649页

作者： Nguyen, Cong T. Nguyen, Diep N. Hoang, Dinh Thai Phan, Khoa Tran Niyato, Dusit Pham, Hoang-Anh Dutkiewicz, Eryk Univ Technol Sydney Sch Elect & Data Engn Sydney NSW 2007 Australia Vietnam Natl Univ Ho Chi Minh City VNU HCM Ho Chi Minh City Univ Technol HCMUT Fac Comp Sci & Engn Ho Chi Minh City 700000 Vietnam La Trobe Univ Sch Engn & Math Sci Melbourne VIC 3086 Australia Nanyang Technol Univ Sch Comp Sci & Engn Singapore City 639798 Singapore

coded distributed computing (CDC) has recently emerged to be a promising solution to address the straggling effects in conventional distributed computing systems. By assigning redundant workloads to the computing nodes, CDC can significantly enhance the performance of the whole system. However, since the core idea of CDC is to introduce redundancies to compensate for uncertainties, it may lead to a large amount of wasted energy at the edge nodes. It can be observed that the more redundant workload added, the less impact the straggling effects have on the system. However, at the same time, the more energy is needed to perform redundant tasks. In this work, we develop a novel framework, namely CERA, to elastically allocate computing resources for CDC processes. Particularly, CERA consists of two stages. In the first stage, we model a joint coding and node selection optimization problem to minimize the expected processing time for a CDC task. Since the problem is NP-hard, we propose a linearization approach and a hybrid algorithm to quickly obtain the optimal solutions. In the second stage, we develop a smart online approach based on Lyapunov optimization to dynamically turn off straggling nodes based on their actual performance. As a result, wasteful energy consumption can be significantly reduced with minimal impact on the total processing time. Simulations using real-world datasets have shown that our proposed approach can reduce the system's total processing time by more than 200% compared to that of the state-of-the-art approach, even when the nodes' actual performance is not known in advance. Moreover, the results have shown that CERA's online optimization stage can reduce the energy consumption by up to 37.14% without affecting the total processing time.

关键词： Task analysis Servers Optimization distributed computing Wireless communication Energy consumption Codes coded distributed computing maximum distance separable code resource allocation INLP Lyapunov optimization edge computing straggling effects

来源：评论

学校读者我要写书评

暂无评论

FLCD: A Flexible Low Complexity Design of coded distributed computing

引用

IEEE TRANSACTIONS ON CLOUD computing 2023年第1期11卷 470-483页

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

We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) with empirical evaluation on Amazon Elastic Compute Cloud (Amazon EC2). CDC can expedite MapReduce like computation by trading increased map computations to reduce communication load and shuffle time. A main novelty of FLCD is to utilize the design freedom in defining map and reduce functions to develop asymptotic homogeneous systems to support varying intermediate values (IV) sizes under a general MapReduce framework. Compared to existing designs with constant IV sizes, FLCD offers greater flexibility in adapting to network parameters and significantly reduces the implementation complexity by requiring fewer input files and shuffle groups. The FLCD scheme is the first proposed low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. We perform empirical evaluations of the FLCD by executing the TeraSort algorithm on an Amazon EC2 cluster. This is the first time that theoretical predictions of the CDC shuffle time are validated by empirical evaluations. The evaluations demonstrate a 2.0 to 4.24x speedup compared to conventional uncoded MapReduce, a 12 to 52 percent reduction in total time, and a wider range of operating network parameters compared to existing CDC schemes.

关键词： Complexity theory Computational modeling Cloud computing distributed computing Indexes Benchmark testing Urban areas coded distributed computing communication load computation load coded multicasting heterogeneity low-complexity implementation Amazon EC2

来源：评论

学校读者我要写书评

暂无评论

Cascaded coded distributed computing Schemes Based on Symmetric Designs

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第11期70卷 7179-7190页

作者： Jiang, Jing Wang, Wenhan Zhou, Lingling Guangxi Normal Univ Guangxi Key Lab Multisource Informat Min & Secur Guilin 541004 Peoples R China

coded distributed computing (CDC) is an efficient method to reduce the communication load in general distributed computing frameworks such as MapReduce. In these systems, one usually needs to split the data set into disjoint files and design several output functions to complete a computational task. Li et al. provided some CDC schemes achieving optimal communication load. However, as the number of computing nodes increases, the numbers of input files and output functions of such schemes grow too fast to be applied in practice. In this paper, several infinite families of cascaded CDC schemes, where each output function is computed multiple times, are constructed by taking advantage of symmetric designs. Most importantly, the numbers of input files and output functions of each new scheme are linear with the number of computing nodes and the communication load of each new scheme approximates to that of the CDC scheme derived by Li et al. when the number of nodes becomes large.

关键词： coded distributed computing MapReduce communication load symmetric design

来源：评论

学校读者我要写书评

暂无评论

A Worst-Case Latency and Age Analysis of coded distributed computing With Unreliable Workers and Periodic Tasks

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY

引用

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY 2024年 5卷 5874-5889页

作者： Chiariotti, Federico Soret, Beatriz Popovski, Petar Univ Padua Dept Informat Engn I-35131 Padua Italy Univ Malaga Telecommun Res Inst Malaga 29010 Spain Aalborg Univ Dept Elect Syst DK-9220 Aalborg Denmark

Over the past decade, the deep learning revolution has led to ever-increasing demands for computing power and working memory to support larger and larger neural networks. As this coincided with the end of Moore's law, distributed solutions have emerged as a natural answer: in particular, the novel coded distributed computing (CDC) paradigm exploits results from coding theory to divide large tasks into redundant sets of smaller subtasks to be processed across multiple workers, making the computation more robust to stragglers and malicious worker nodes. Optimizing the use of these distributed computing resources is critical, as excessive redundancy might impact on performance and energy consumption. This work considers a CDC system receiving periodic tasks, deriving the full distribution of the latency, reliability, and Peak Age of Information (PAoI) under worker diversity and random failures. The CDC system is modeled as a fork-join D/M/(K, N)/L queue, where only K of the coded N subtasks are necessary to solve the overall task, and workers can hold up to L subtasks in their queues. Our results are useful for resource optimization, showing the relationship between system load, redundancy, and latency, as well as the trade-off between latency, reliability, and age performance.

关键词： Computational modeling distributed computing Reliability Queueing analysis Probability density function Solid modeling Optimization coded distributed computing latency analysis age of information fork-join queues

来源：评论

学校读者我要写书评

暂无评论

An Incentive Mechanism for Resource Allocation in coded distributed computing 15

An Incentive Mechanism for Resource Allocation in Coded Dist...

引用

9th IEEE International Conference on Smart City and Informatization (iSCI) / 15th IEEE International Conference on Big Data Science and Engineering (BigDataSE)

作者： Ng, Jer Shyuan Lim, Wei Yang Bryan Xiong, Zehui Garg, Sahil Niyato, Dusit Leung, Cyril Alibaba Grp Hangzhou Peoples R China Alibaba NTU JRI Singapore Singapore SUTD Singapore Singapore Ecole Technol Super Montreal PQ Canada Nanyang Technol Univ SCSE Singapore Singapore Nanyang Technol Univ LILY Res Ctr Singapore Singapore Univ British Columbia ECE Vancouver BC Canada

ISBN: (纸本)9781665400381

coded distributed computing (CDC) has emerged as a promising approach because it enables computation tasks to be carried out in a distributed manner while mitigating straggler effects, which often account for the long overall completion times. However, incentive issues have not been studied systematically for the edge servers to complete the CDC tasks. In this paper, we propose a tractable two-level game-theoretic approach to incentivize the edge servers to complete the CDC tasks. Specifically, in the lower level, a hedonic coalition formation game is formulated where the edge servers share their resources within their coalitions. In the upper level, given the CPU power of the coalitions of edge servers, an all-pay auction is designed to incentivize the edge servers to participate in the CDC tasks. Simulation results show that the edge servers are incentivized to allocate more CPU power when multiple rewards are offered, i.e. there are multiple winners, instead of rewarding only the edge server with the largest CPU power allocation. Besides, the utility of the cloud server is maximized when it offers multiple homogeneous rewards, instead of heterogeneous rewards.

关键词： coded distributed computing straggler effects hedonic game all-pay auction Bayesian Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Topological coded distributed computing

Topological Coded Distributed Computing

引用

IEEE Global Communications Conference (GLOBECOM) on Advanced Technology for 5G Plus

作者： Wan, Kai Ji, Mingyue Caire, Giuseppe Tech Univ Berlin D-10587 Berlin Germany Univ Utah Salt Lake City UT 84112 USA

ISBN: (纸本)9781728182988

This paper considers the MapReduce-like coded distributed computing framework originally proposed by Li et al., which uses coding techniques when distributed computing servers exchange their computed intermediate values, in order to reduce the overall traffic load. In their original model, servers are connected via an error-free common communication bus allowing broadcast transmissions. However, this assumption is one of the major limitations for practical implementations since real-world data centers may have network topologies far more involved than a single broadcast bus. We formulate a topological coded distributed computing problem, where the computing servers communicate with each other through some switch network. By using a special instance of fat-tree topologies, referred to as t-ary fat-tree proposed by Al-Fares et al. which can be built by some inexpensive switches, we propose a coded distributed computing scheme to achieve the optimal max-link communication load (defined as the maximum load over all links) over any network topology.

关键词： coded distributed computing network topology fat-tree

来源：评论

学校读者我要写书评

暂无评论

Learning Auction in coded distributed computing with Heterogeneous User Demands 27

Learning Auction in Coded Distributed Computing with Heterog...

引用

IEEE Symposium on Computers and Communications (ISCC)

作者： Liang, Jiawei Li, Juan Zhu, Kun Yi, Changyan Nanjing Univ Aeronaut & Astronaut Nanjing Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing Peoples R China

ISBN: (纸本)9781665497923

coded distributed computing(CDC) has shown great potentials to solve the unexpected delay caused by stragglers and communication load in distributed computing. We propose a novel learning auction to allocate computing resource efficiently in a CDC scenario. The user demand types are usually heterogeneous according to different variation trends of the value with finish time and workload, which can be modeled by deep learning. As the goal of social welfare maximizationthe platform would allocate computing resources according to inferred value functions of users. Due to the uncertain finish time and non-linear structures of deep learning models, the considered optimization problem is non-convex. We then reformulate the non-convex optimization problem into a mixed integer program(MIP). After analyzing the inference error caused by deep learning, a payment rule referred to VCG is designed to achieve incentive alignment and individual rationality. Besides, experiments have been performed to show the superiority of our mechanism.

关键词： coded distributed computing deep learning auction and pricing social welfare maximization MIP optimization

来源：评论

学校读者我要写书评

暂无评论

Secure coded distributed computing 25

Secure Coded Distributed Computing

引用

25th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)

作者： Sasi, Shanuja Giinlii, Onur Linkoping Univ Informat Theory & Secur Lab ITSL Linkoping Sweden

ISBN: (纸本)9798350393194;9798350393187

We consider two critical aspects of security in the distributed computing (DC) model: secure data shuffling and secure coded computing. It is imperative that any external entity overhearing the transmissions does not gain any information about the intermediate values (IVs) exchanged during the shuffling phase of the DC model. Our approach ensures IV confidentiality during data shuffling. Moreover, each node in the system must be able to recover the IVs necessary for computing its output functions but must also remain oblivious to the IVs associated with output functions not assigned to it. We design secure DC methods and establish achievable limits on the tradeoffs between the communication and computation loads to contribute to the advancement of secure data processing in distributed systems.

关键词： coded distributed computing MapReduce framework information-theoretic security secure computing.

来源：评论

学校读者我要写书评

暂无评论

Transmission Order Optimization of coded distributed computing in Heterogeneous Wireless Multiple-Access Network 19

Transmission Order Optimization of Coded Distributed Computi...

引用

19th IEEE International Wireless Communications and Mobile computing (IEEE IWCMC)

作者： Wu, Yaonan Gu, Shushi Zhang, Qinyu Zhang, Ning Xiang, Wei Harbin Inst Technol Shenzhen Guangdong Prov Key Lab Aerosp Commun & Networking Shenzhen 518055 Peoples R China Peng Cheng Lab Shenzhen 518052 Peoples R China Univ Windsor Windsor ON N9B 3P4 Canada La Trobe Univ Sch Comp Engn & Math Sci Melbourne Vic 3086 Australia

ISBN: (纸本)9798350333398

coded distributed computing (CDC) has been recently proposed as a promising technique to mitigate the straggler effect in the distributed computing cluster which consists of workers with different computing capabilities, and to reduce the end-to-end task execution latency. However, the heterogeneity of computing and transmission will critically impact the latency performance, especially in the wireless multiple-access network. In this paper, we use CDC over the heterogeneous wireless multiple-access network (HWMAN) including both computation stragglers and transmission stragglers with various capabilities. In order to reduce the computing task completion latency (computing latency and transmission latency), the optimal stop computing time of workers and the sorting order of result transmission back are obtained via two designed algorithms, namely straggler detection and ordered transmission (SDOT) and worker sorting and ordered transmission (WSOT), respectively, which not only fully utilize the computing results of stragglers, but also improve the total latency performance compared with other existing state-of-the-art algorithms.

关键词： heterogeneous wireless multiple-access network coded distributed computing straggler detection transmission order latency optimization

来源：评论

学校读者我要写书评

暂无评论

computing Resource Allocation for Heterogeneous coded distributed computing 31

Computing Resource Allocation for Heterogeneous Coded Distri...

引用

31st Wireless and Optical Communications Conference (WOCC)

作者： Dai, Mingjun Yuan, Jialong Tong, Yanli Wang, Lan Lin, Xiaohui Shenzhen Univ Coll Elect & Informat Engn Shenzhen Peoples R China

ISBN: (数字)9781665469500

ISBN: (纸本)9781665469500

Millions of matrix dimensions in matrix multiplication will have high requirements on node computing power and storage space. coded distributed computing (CDC) can solve this problem by dividing large-dimensional matrices into small matrices and then assigning them to machines in the computing cluster to perform matrix multiplication in parallel. In order to adapt to the reality that computer clusters are usually composed of heterogeneous workers with different computing capabilities, and overcome the performance limitations of CDC based on the isomorphism of computing power, coded Elastic computing (CEC) is proposed. However, the existing CEC discards the received information and directly starts a new round of computation after an elastic event occurs, resulting waste of computing time and resources. In this paper, we propose to employ the received information to redesign the allocation scheme. We first determine the offline machine number and the data segment it should have returned as the missing part of decoding that needs to be recomputed. We then count the total number of lost data for each segment of data and calculate the amount of tasks that each machine should undertake. Finally, the amount of tasks actually undertaken by each machine is calculated by solving the system of linear equations. Through experiments, we show the effectiveness of our proposed allocation scheme, in terms of saving resources and time, and accelerating the calculation speed, when compared with the original scheme.

关键词： coded distributed computing Heterogeneous Network coded Elastic computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：