.png){kind=icon}
.png){kind=icon}
Return
Coded Computation Over Heterogeneous Workers With Random Task Arrivals
.png){kind=icon}
PRE
AI
DOI：10.1109/LCOMM.2021.3067888.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Considering the scheduling and allocation of tasks among multiple servers, distributed machine learning faces the problem of the straggler effect as well as system heterogeneity, e.g., the computation time of the slowest worker can be much longer than that of the normal workers. This letter studies the distributed online tasks assignment problem under heterogeneous conditions where different workers have different computing capacities, in order to minimize the task completion time. We consider the task scheduling with random task arrivals, and introduce task cancellation after completion scheme to clear the unfinished parts after the completion of the task to further reduce redundant calculations. To address the challenge of finding the optimal solution, we propose an approximate online algorithm based on convex optimization and time recursion. Simulation results show that the proposed algorithm can reduce the completion delay by over 30x0025; as compared with the one-shot counterpart, and maintain a relatively stable delay in the case of fluctuating arrival rates.
Keywords:
Task analysis
Encoding
Delays
Approximation algorithms
Machine learning
Computational modeling
Sun
Coded computation
online task assignment
heterogeneous system
convex optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.