A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
Source abstract
Abstract
In this paper, we consider the problem of estimating the time-dependent ability of workers participating in distributed matrix-vector multiplication over heterogeneous clusters. Specifically, we model the workers’ ability as a latent variable and introduce a log-normally distributed working rate as a function of the latent variable with parameters so that the working rate increases as the latent ability of workers increases, and takes positive values only. This modeling is motivated by the need to reflect the impact of time-dependent external factors on the workers’ performance. We estimate the latent variable and parameters using the expectation-maximization (EM) algorithm combined with the particle method. The proposed estimation and inference on the working rates are used to allocate tasks to the workers to reduce expected latency. From simulations, we observe that our estimation and inference on the working rates are effective in reducing expected latency.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Complex Network Analysis Techniques · Cloud Computing and Resource Management · Distributed and Parallel Computing Systems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Samsung Electronics, Suwon 16677, Republic of Korea
Department of Statistics, Sungshin Women’s University, Seoul 02844, Republic of Korea
Data Science Center, Sungshin Women’s University, Seoul 02844, Republic of Korea
Funding
National Research Foundation of Korea (NRF)
References (28)
Show source-provided references
1. Large scale distributed deep networks
2. The tail at scale10.1145/2408776.2408794 ↗
3. Speeding up distributed machine learning using codes10.1109/TIT.2017.2736066 ↗
4. Lee, K., Suh, C., and Ramchandran, K. (2017, January 25–30). High-dimensional coded matrix multiplication. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.10.1109/ISIT.2017.8006963 ↗
5. Yu, Q., Maddah-Ali, M., and Avestimehr, S. (2017, January 4–9). Polynomial codes: An optimal design for high-dimensional coded matrix multiplication. Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), Los Angeles, CA, USA.
6. Park, H., Lee, K., Sohn, J.-Y., Suh, C., and Moon, J. (2018, January 17–22). Hierarchical coding for distributed computing. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.10.1109/ISIT.2018.8437669 ↗
7. Tandon, R., Lei, Q., Dimakis, A.G., and Karampatziakis, N. (2017, January 6–11). Gradient coding: Avoiding stragglers in distributed learning. Proceedings of the International Conference Machine Learning, Sydney, Australia.
8. Raviv, N., Tandon, R., Dimakis, A., and Tamo, I. (2018, January 10–15). Gradient coding from cyclic MDS codes and expander graphs. Proceedings of the International Conference Machine Learning, Stockholm, Sweden.
9. Ozfaturay, E., Gündüz, D., and Ulukus, S. (2019, January 7–12). Speeding up distributed gradient descent by utilizing non-persistent stragglers. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.10.1109/ISIT.2019.8849684 ↗
10. Dutta, S., Cadambe, V., and Grover, P. (2017, January 25–30). Coded convolution for parallel and distributed computing within a deadline. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.10.1109/ISIT.2017.8006960 ↗
11. Learning-Based Coded Computation
12. Coding for distributed fog computing10.1109/MCOM.2017.1600894 ↗
13. Analysis on cascading reliability of edge-assisted Internet of Things10.1016/j.ress.2022.108463 ↗
14. Zaharia, M., Konwinski, A., Joseph, A.D., Katz, R.H., and Stoica, I. (2008, January 8–10). Improving mapreduce performance in heterogeneous environments. Proceedings of the USENIX Symposium on Operating Systems Design Implement (OSDI), San Diego, CA, USA.
15. Coded computation over heterogeneous clusters10.1109/TIT.2019.2904055 ↗
16. Optimal load allocation for coded distributed computation in heterogeneous clusters10.1109/TCOMM.2020.3030667 ↗
17. Gao, J. (2023, April 06). Machine Learning Applications for Data Center Optimization. Google White Pap. Available online: https://research.google/pubs/pub42542/.
18. Probabilistic transformer for time series analysis
19. Lin, Y., Koprinska, I., and Rana, M. (2021, January 7–10). SSDNet: State space decomposition neural network for time series forecasting. Proceedings of the 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand.10.1109/ICDM51629.2021.00048 ↗
20. Hu, Y., Jia, X., Tomizuka, M., and Zhan, W. (2022, January 23–27). Causal-based time series domain generalization for vehicle intention prediction. Proceedings of the 2022 International Conference on Robotics and Automation (ICRA), Philadelphia, PA, USA.10.1109/ICRA46639.2022.9812188 ↗
21. On the analysis of fitness change: Fitness-popularity dynamic network model with varying fitness10.1088/1742-5468/ab7754 ↗
22. Monte Carlo filter and smoother for non-Gaussian nonlinear state space models10.1080/10618600.1996.10474692 ↗
23. On particle methods for parameter estimation in state-space models10.1214/14-STS511 ↗
24. Filtering via simulation: Auxiliary particle filters10.1080/01621459.1999.10474153 ↗
25. Improved particle filter for nonlinear problems10.1049/ip-rsn:19990255 ↗
26. Doucet, A., De Freitas, N., and Gordon, N. (2001). An introduction to sequential Monte Carlo methods. Seq. Monte Carlo Methods Pract., 3–14.10.1007/978-1-4757-3437-9_1 ↗
27. A tutorial on particle filtering and smoothing: Fifteen years later
28. Adaptive rejection sampling for Gibbs sampling10.2307/2347565 ↗