Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment
<p>Implementation detail.</p> "> Figure 2
<p>Data collected during running WordCount on the same node. Different groups of data generated from four map tasks running on the same node when executing WordCount: (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4.</p> "> Figure 3
<p>Data collected during running Sort on the same node. Different groups of data generated from four map tasks running on the same node when executing Sort: (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4.</p> "> Figure 4
<p>Linear Regression calculated by direct regression algorithm during a lifetime. (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4 data and their values calculated by Linear Regression for WordCount sample.</p> "> Figure 5
<p>Linear Regression calculated by direct regression algorithm during a lifetime. (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4 data and their values calculated by Linear Regression for Sort sample.</p> "> Figure 6
<p>Accuracy with different value of <math display="inline"> <semantics> <mi>λ</mi> </semantics> </math>.</p> "> Figure 7
<p>Two-Phase Regression values. Error obtained by Abs (Regression Value–Actual value). (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4 data and their values calculated by Two-Phase Regression for WordCount sample.</p> "> Figure 8
<p>Two-Phase Regression values. Error obtained by Abs (Regression Value–Actual value). (<b>a</b>) Group 1; (<b>b</b>) Group 2; (<b>c</b>) Group 3; and (<b>d</b>) Group 4 data and their values calculated by Two-Phase Regression for Sort sample.</p> ">
Abstract
:1. Introduction
2. Related Work
3. A Two-Phase Regression Method
3.1. Gathering Detailed Information of Each Running Task
Algorithm 1: Data Collecting Method (GetDataSet) |
Input: |
TA: The task attempt |
TN: The name of the task attempt |
P: The progress of a running task |
TT: The type of the running task |
DM: The data map storing all the data lists of currently running tasks, whose key is TN and value is DL |
DL: The data list storing HisPro generated by a running task |
Steps: |
For each TA in the task pool |
If Current TA is Running |
Get the current HisPro |
Get the DL from DM according to TN |
If DL does not contain HisPro |
Add HisPro to the DL |
Else |
Update the DL using HisPro |
EndIf |
Update the DL in DM |
EndIf |
If P > α |
savetoHDFS (TA, DL, TT) |
EndIf |
EndFor |
3.2. Data Analysis
- Step 1: Data Preprocessing. The preprocessing function is shown in Equation (1), and final data structure can be expressed as (p, t). p represents progress and t is calculated according to Equation (1).
- Step 2: Data Smoothing. Smoothing method is used for errors filtering, through which preprocessed data are smoothed with a five-point approximation. Specific smoothing processes are shown in Equation (2). Given a group of data, e.g., {6, 4, 5, 4, 3, 5}, then, the following values can be obtained: T(0) = 6, T(1) = 5, T(2) = 4.4, T(3) = 4.2, T(4) = 4, T(5) = 5.
- Step 3: Data Regression. A mathematic model is shown in Equation (3), where and are two constants called regression parameters, while ε is a value near 0.
- Step 4: Data Prediction. Data are firstly divided into two equal parts, A and B. Top 1/3 of part A is dropped to avoid potential errors created by the initial phase. Then, Part A is used for training phase to find parameters (, ). The variable () in Equation (16) is calculated according to the mean value of data generated in the same node. Part B is used for validation.
4. Experiments and Results
4.1. Data Collection and Its Results
4.2. Data Analysis and Prediction
5. Conclusions
Acknowledgments
Author Contributions
Conflicts of Interest
References
- Dean, J.; Ghemawat, S. MapReduce: Simplified data processing on large clusters. Commun. ACM 2008, 51, 107–113. [Google Scholar] [CrossRef]
- Fu, Z.; Sun, X.; Liu, Q.; Zhou, L.; Shu, J. Achieving efficient cloud search services: Multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans. Commun. 2015, E98B, 190–200. [Google Scholar] [CrossRef]
- Toshniwal, A.; Taneja, S.; Shukla, A.; Ramasamy, K.; Patel, J.M.; Kulkarni, S.; Bhagat, N. Storm@ twitter. In Proceedings of the 2014 ACM International Conference on Management of Data(SIGMOD), Snowbird, UT, USA, 22–27 June 2014; pp. 147–156.
- Stoica, I. Conquering big data with spark and BDAS. In Proceedings of the 2014 ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), New York, NY, USA, 16–20 June 2014; p. 193.
- Rodríguez-Mazahua, L.; Sánchez-Cervantes, J.L.; Cervantes, J.; García-Alcaraz, J.L.; Alor-Hernández, G. A general perspective of big data: Applications, tools, challenges and trends. J. Supercomput. 2015. [Google Scholar] [CrossRef]
- Namiot, D. On big data stream processing. Int. J. Open Inf. Technol. 2015, 3, 48–51. [Google Scholar]
- Zaharia, M.; Das, T.; Li, H.; Hunter, T.; Shenker, S.; Stoica, I. Discretized streams: Fault-tolerant streaming computation at scale. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, Farmington, PA, USA, 3–6 November 2013; pp. 423–438.
- Armbrust, M.; Xin, R.S.; Lian, C.; Huai, Y.; Liu, D.; Bradley, J.K.; Meng, X.; Kaftan, T.; Franklin, M.; Zaharia, M. Spark SQL: Relational data processing in Spark. In Proceedings of the 2015 ACM International Conference on Management of Data (SIGMOD), Melbourne, Australia, 31 May–4 June 2015; pp. 1383–1394.
- Meng, X.; Bradley, J.; Yuvaz, B.; Sparks, E.; Venkataraman, S.; Liu, D.; Ghodsi, A.; Xin, D. MLlib: Machine learning in apache spark. J. Mach. Learn. Res. 2016, 17, 1–7. [Google Scholar]
- Gonzalez, J.E.; Xin, R.S.; Dave, A.; Crankshaw, D.; Franklin, M.J.; Stoica, I. Graphx: Graph processing in a distributed dataflow framework. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), Broomfield, Denver, CO, USA, 6–8 October 2014; pp. 599–613.
- Gu, L.; Li, H. Memory or time: Performance evaluation for iterative operation on Hadoop and Spark. In Proceedings of the 2013 IEEE International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC and EUC 2013), Zhangjiajie, China, 13–15 November 2013; pp. 721–727.
- Almeer, M.H. Cloud Hadoop Map Reduce for Remote Sensing Image Analysis. J. Emerg. Trends Comput. Inf. Sci. 2012, 3, 637–644. [Google Scholar]
- Xu, H.; Wang, L.; Xie, H. Design and experiment analysis of a Hadoop-based video transcoding system for next-generation wireless sensor networks. Int. J. Distrib. Sensor Netw. 2014, 2014, 151564. [Google Scholar] [CrossRef]
- Jung, I.Y.; Kim, K.H.; Han, B.J.; Jeong, C.S. Hadoop-based distributed sensor node management system. Int. J. Distrib. Sensor Netw. 2014, 2014, 601868. [Google Scholar] [CrossRef]
- Hussain, S.; Bang, J.H.; Han, M.; Ahmed, M.I.; Amin, M.B.; Lee, S.; Nugent, C.; McClean, S.; Scotney, B.; Parr, G. Behavior life style analysis for mobile sensory data in cloud computing through MapReduce. Sensors 2014, 14, 22001–22020. [Google Scholar] [CrossRef] [PubMed]
- Alghussein, I.I.; Aly, W.M.; El-Nasr, M.A. Anomaly detection using Hadoop and MapReduce technique in cloud with sensor data. Int. J. Comput. Appl. 2015, 125, 22–26. [Google Scholar]
- Ibrahim, S.; Jin, H.; Lu, L.; He, B.; Antoniu, G.; Wu, S. Maestro: Replica-aware map scheduling for MapReduce. In Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), Ottawa, ON, Canada, 13–16 May 2012; pp. 435–442.
- Verma, A.; Cherkasova, L.; Campbell, R.H. Orchestrating an ensemble of MapReduce jobs for minimizing their makespan. IEEE Trans. Dependable Secure Comput. 2013, 10, 314–327. [Google Scholar] [CrossRef]
- Tang, S.; Lee, B.S.; He, B. Dynamic MR: A dynamic slot allocation optimization framework for MapReduce clusters. IEEE Trans. Cloud Comput. 2014, 2, 333–347. [Google Scholar] [CrossRef]
- Yao, Y.; Tai, J.; Sheng, B.; Mi, N. LsPS: A job size-based scheduler for efficient task assignments in Hadoop. IEEE Trans. Cloud Comput. 2015, 3, 411–424. [Google Scholar] [CrossRef]
- Shi, X.; Chen, M.; He, L.; Xie, X.; Lu, L.; Jin, H.; Wu, S. Mammoth: Gearing Hadoop towards memory-intensive MapReduce applications. IEEE Trans. Parallel Distrib. Syst. 2015, 26, 2300–2315. [Google Scholar] [CrossRef]
- Zhang, Q.; Zhani, M.F.; Yang, Y.; Boutaba, R.; Wong, B. PRISM: Fine-grained resource-aware scheduling for MapReduce. IEEE Trans. Cloud Comput. 2015, 3, 182–194. [Google Scholar] [CrossRef]
- Mashayekhy, L.; Nejad, M.M.; Grosu, D.; Zhang, Q.; Shi, W. Energy-aware scheduling of MapReduce jobs for big data applications. IEEE Trans. Parallel Distrib. Syst. 2016, 26, 2720–2733. [Google Scholar] [CrossRef]
- Tang, S.J.; Lee, B.S.; Fan, R.; He, B.S. Dynamic job ordering and slot configurations for MapReduce workloads. IEEE Trans. Serv. Comput. 2016, 9, 4–17. [Google Scholar] [CrossRef]
- Zaharia, M.; Konwinski, A.; Joseph, A.D.; Katz, R.H.; Stoica, I. Improving MapReduce performance in heterogeneous environments. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI), San Diego, CA, USA, 8–10 December 2008; pp. 29–42.
- Chen, Q.; Liu, C.; Xiao, Z. Improving MapReduce performance using smart speculative execution strategy. IEEE Trans. Comput. 2014, 63, 954–967. [Google Scholar] [CrossRef]
- Wu, H.; Li, K.; Tang, Z.; Zhang, L. A heuristic speculative execution strategy in heterogeneous distributed environments. In Proceedings of the 2014 Sixth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP), Beijing, China, 13–15 July 2014; pp. 268–273.
- Huang, X.; Zhang, L.; Li, R.; Wan, L.; Li, K. Novel heuristic speculative execution strategies in heterogeneous distributed environments. Comput. Electrical Eng. 2016, 50, 166–179. [Google Scholar] [CrossRef]
- Liu, Q.; Cai, W.; Shen, J.; Fu, Z.; Linge, N. A smart strategy for speculative execution based on hardware Resource in a heterogeneous distributed environment. Int. J. Grid Distrib. Comput. 2016, 9, 203–214. [Google Scholar] [CrossRef]
- Liu, Q.; Cai, W.; Shen, J.; Fu, Z.; Linge, N. A smart speculative execution strategy based on node classification for heterogeneous hadoop systems. In Proceedings of the 18th International Conference on Advanced Communication Technology (ICACT), PyeongChang, Korea, 31 January–3 February 2016; pp. 223–227.
- Raju, R.; Amudhavel, J.; Pavithra, M.; Anuja, S. A heuristic fault tolerant MapReduce framework for minimizing makespan in hybrid cloud environment. In Proceedings of the International Conference on Green Computing Communication and Electrical Engineering, Coimbatore, India, 6–8 March 2014; pp. 1–4.
- Li, Y.; Yang, Q.; Lai, S.; Li, B. A new speculative execution algorithm based on C4.5 decision tree for Hadoop. In Proceedings of the International Conference of Young Computer Scientists, Engineers and Educators (ICYCSEE 2015), Harbin, China, 10–12 January 2015; pp. 284–291.
- Wang, Y.; Lu, W.; Lou, R.; Wei, B. Improving MapReduce performance with partial speculative execution. J. Grid Comput. 2015, 11, 587–604. [Google Scholar] [CrossRef]
- Yang, S.J.; Chen, Y.R. Design adaptive task allocation scheduler to improve MapReduce performance in heterogeneous Clouds. J. Netw. Comput. Appl. 2013, 57, 61–70. [Google Scholar] [CrossRef]
- Ananthanarayanan, G.; Kandula, S.; Greenberg, A.; Stoica, I.; Lu, Y.; Saha, B.; Harris, E. Reining in the outliers in Map-Reduce clusters using Mantri. In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Vancouver, BC, Canada, 4–6 October 2010; pp. 265–278.
- Xu, H.; Lau, W.C. Optimization for Speculative Execution in a MapReduce-Like Cluster. In Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 26 April–1 May 2015; pp. 1071–1079.
- Xu, H.; Lau, W.C. Task-cloning algorithms in a MapReduce cluster with competitive performance bounds. In Proceedings of the IEEE 35th International Conference on Distributed Computing Systems (ICDCS), Columbus, OH, USA, 29 June–2 July 2015; pp. 339–348.
- Marquardt, D.W. An algorithm for least-squares estimation of nonlinear parameters. J. Soc. Ind. Appl. Math. 2016, 11, 431–441. [Google Scholar] [CrossRef]
- Ahmad, F.; Chakradhar, S.T.; Raghunathan, A.; Vijaykumar, T.N. Tarazu: Optimizing MapReduce on heterogeneous clusters. ACM SIGARCH Comput. Archit. News 2012, 40, 61–74. [Google Scholar] [CrossRef]
- Fan, Y.; Wu, W.; Xu, Y.; Chen, H. Improving MapReduce performance by balancing skewed loads. China Commun. 2014, 11, 85–108. [Google Scholar] [CrossRef]
Node ID | Memory (GB) | Core Processors |
---|---|---|
Node 1 | 10 | 8 |
Node 2 | 8 | 4 |
Node 3 | 8 | 1 |
Node 4 | 8 | 8 |
Node 5 | 4 | 8 |
Node 6 | 4 | 4 |
Node 7 | 18 | 4 |
Node 8 | 12 | 8 |
Application | Input Data(GB) | Data Volume Collected (Groups) |
---|---|---|
Sort | 30 | 326 |
WordCount | 50 | 727 |
File Name | Size |
---|---|
attempt_1460032292591_0001_m_000000_0_ MAP | 588 B |
attempt_1460032292591_0002_m_000000_0_ MAP | 903 B |
attempt_1460032292591_0003_m_000000_0_ MAP | 1.46 KB |
attempt_1460032292591_0004_m_000000_0_ MAP | 840 B |
attempt_1460032292591_0005_m_000000_0_ MAP | 1.23 KB |
attempt_1460032292591_0006_m_000000_0_ MAP | 1.33 KB |
attempt_1460032292591_0007_m_000000_0_ MAP | 861 B |
attempt_1460032292591_0008_m_000000_0_ MAP | 630 B |
… | … |
Progress | Timestamp |
---|---|
0.068 | 1460095563715 |
0.112 | 1460095567625 |
0.202 | 1460095587516 |
0.231 | 1460095607664 |
0.240 | 1460095611976 |
0.249 | 1460095633288 |
0.265 | 1460095633289 |
0.292 | 1460095633295 |
0.305 | 1460094649633 |
… | … |
Group 1 | Group 2 | Group 3 | Group 4 | Group 5 | Group 6 | Group 7 | Group 8 | ||
RMSE (S) | 1.2 | 1.6 | 2.8 | 1.5 | 1.6 | 1.4 | 1.3 | 1.4 | |
MAPE (%) | 1.7 | 2.8 | 2.8 | 1.7 | 2.4 | 2.7 | 1.6 | 3.1 | |
Group 9 | Group 10 | Group 11 | Group 12 | Group 13 | Group 14 | Group 15 | Group 16 | ||
RMSE (S) | 2.4 | 1.4 | 1.0 | 1.9 | 1.7 | 1.7 | 1.3 | 1.2 | |
MAPE (%) | 3.3 | 2.4 | 1.1 | 5.3 | 5.5 | 2.4 | 1.7 | 2.0 | |
Group 17 | Group 18 | Group 19 | Group 20 | Group 21 | Group 22 | Group 23 | Group 24 | Average Value | |
RMSE (S) | 0.9 | 1.9 | 1.2 | 1.5 | 2.1 | 1.4 | 1.1 | 1.3 | 1.7 |
MAPE (%) | 1.7 | 3.8 | 1.3 | 2.2 | 4.9 | 3.0 | 2.0 | 2.4 | 2.8 |
Group 1 | Group 2 | Group 3 | Group 4 | Group 5 | Group 6 | Group 7 | Group 8 | ||
RMSE (S) | 1.6 | 1.5 | 1.4 | 1.1 | 1.6 | 2.4 | 1.7 | 1.5 | |
MAPE (%) | 1.4 | 1.2 | 1.0 | 0.8 | 1.3 | 7.3 | 1.8 | 1.4 | |
Group 9 | Group 10 | Group 11 | Group 12 | Group 13 | Group 14 | Group 15 | Group 16 | ||
RMSE (S) | 1.6 | 1.6 | 3.1 | 1.6 | 2.4 | 2.4 | 0.9 | 2.1 | |
MAPE (%) | 1.5 | 2 | 8 | 1.7 | 3.9 | 7.9 | 1.8 | 2.7 | |
Group 17 | Group 18 | Group 19 | Group 20 | Group 21 | Group 22 | Group 23 | Group 24 | Average Value | |
RMSE (S) | 1.7 | 0.6 | 2.3 | 1.6 | 1.3 | 1.8 | 1.4 | 1.6 | 1.5 |
MAPE (%) | 1.8 | 6.8 | 4.6 | 1.5 | 0.9 | 2.8 | 1.5 | 2.1 | 2.7 |
Group 1 | Group 2 | Group 3 | Group 4 | Group 5 | Group 6 | Group 7 | Group 8 | |||
RMSE (S) | 1.8 | 3.5 | 5.7 | 2.7 | 3.6 | 2.8 | 3.5 | 1.9 | ||
MAPE (%) | 1.7 | 5.6 | 4.9 | 3.3 | 5.6 | 3.5 | 5.1 | 2.4 | ||
Group 9 | Group 10 | Group 11 | Group 12 | Group 13 | Group 14 | Group 15 | Group 16 | |||
RMSE (S) | 10.9 | 6.7 | 3.7 | 5.2 | 2.7 | 4.4 | 3.1 | 1.9 | ||
MAPE (%) | 21 | 17.2 | 7.4 | 10.2 | 4.7 | 6.2 | 4.3 | 2.2 | ||
Group 17 | Group 18 | Group 19 | Group 20 | Group 21 | Group 22 | Group 23 | Group 24 | Average Value | Corrected Value | |
RMSE (S) | 3.1 | 7.4 | 3.2 | 10.0 | 11.4 | 7.4 | 9.4 | 1.8 | 4.9 | 3.6 |
MAPE (%) | 6.0 | 18.5 | 4.0 | 18.9 | 33.5 | 20.8 | 26.5 | 1.5 | 9.8 | 5.5 |
Group 1 | Group 2 | Group 3 | Group 4 | Group 5 | Group 6 | Group 7 | Group 8 | |||
RMSE (S) | 3.4 | 4.4 | 4.2 | 4.1 | 2.8 | 9.4 | 3.4 | 4.1 | ||
MAPE (%) | 2.7 | 3.7 | 4.5 | 5.4 | 2 | 78.0 | 3.6 | 4.9 | ||
Group 9 | Group 10 | Group 11 | Group 12 | Group 13 | Group 14 | Group 15 | Group 16 | |||
RMSE (S) | 4.3 | 3.7 | 9.3 | 7.8 | 10.9 | 3.7 | 13.6 | 5.0 | ||
MAPE (%) | 3.4 | 3.3 | 40.3 | 12 | 28.0 | 7.7 | 12.3 | 10.3 | ||
Group 17 | Group 18 | Group 19 | Group 20 | Group 21 | Group 22 | Group 23 | Group 24 | Average Value | Corrected Value | |
RMSE (S) | 3.8 | 7.6 | 10.4 | 3.7 | 9.4 | 6.7 | 10.8 | 3.7 | 6.3 | 4.8 |
MAPE (%) | 3.5 | 17.3 | 25.4 | 2.8 | 11 | 11.2 | 25.8 | 4.2 | 13.5 | 6.1 |
© 2016 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Liu, Q.; Cai, W.; Jin, D.; Shen, J.; Fu, Z.; Liu, X.; Linge, N. Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment. Sensors 2016, 16, 1386. https://doi.org/10.3390/s16091386
Liu Q, Cai W, Jin D, Shen J, Fu Z, Liu X, Linge N. Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment. Sensors. 2016; 16(9):1386. https://doi.org/10.3390/s16091386
Chicago/Turabian StyleLiu, Qi, Weidong Cai, Dandan Jin, Jian Shen, Zhangjie Fu, Xiaodong Liu, and Nigel Linge. 2016. "Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment" Sensors 16, no. 9: 1386. https://doi.org/10.3390/s16091386