An adaptive switching scheme for iterative computing in the cloud

doi:10.1007/s11704-014-3472-4

Front. Comput. Sci.

2014, Vol. 8

Issue (6) : 872-884 https://doi.org/10.1007/s11704-014-3472-4

RESEARCH ARTICLE

An adaptive switching scheme for iterative computing in the cloud

Yu ZHANG, Xiaofei LIAO(

), Hai JIN, Li LIN, Feng LU

Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology,Wuhan 430074, China

Download: PDF(678 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Delta-based accumulative iterative computation (DAIC) model is currently proposed to support iterative algorithms in a synchronous or an asynchronous way. However, both the synchronous DAIC model and the asynchronous DAIC model only satisfy some given conditions, respectively, and perform poorly under other conditions either for high synchronization cost or for many redundant activations. As a result, the whole performance of both DAIC models suffers fromthe serious network jitter and load jitter caused bymultitenancy in the cloud. In this paper, we develop a system, namely HybIter, to guarantee the performance of iterative algorithms under different conditions. Through an adaptive execution model selection scheme, it can efficiently switch between synchronous and asynchronous DAIC model in order to be adapted to different conditions, always getting the best performance in the cloud. Experimental results show that our approach can improve the performance of current solutions up to 39.0%.

Keywords iterative algorithm computational skew communication skew cloud delta-based accumulative iterative computation

Corresponding Author(s): Xiaofei LIAO

Issue Date: 27 November 2014

Cite this article:

Yu ZHANG,Xiaofei LIAO,Hai JIN, et al. An adaptive switching scheme for iterative computing in the cloud[J]. Front. Comput. Sci., 2014, 8(6): 872-884.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3472-4
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I6/872

1	D Horowitz, S D Kamvar. The anatomy of a large-scale social search engine. In: Proceedings of the 19th International Conference on World Wide Web. 2010, 431−440 https://doi.org/10.1145/1772690.1772735
2	H Song, T Cho, V Dave, Y Zhang, L Qiu. Scalable proximity estimation and link prediction in online social networks. In: Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference. 2009, 322−335 https://doi.org/10.1145/1644893.1644932
3	B Gao, T Liu, W Wei, T Wang, H Li. Semi-supervised ranking on very large graphs with rich metadata. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 96−104
4	S Baluja, R Seth, D Sivakumar, Y Jing, Y Jay, S Kumar, R Deepak, M Aly. Video suggestion and discovery for youtube: taking random walks through the view graph. In: Proceedings of the 17th International Conference on World Wide Web. 2008, 895−904 https://doi.org/10.1145/1367497.1367618
5	T Zhou, Z Kuscsik, J Liu, M Medo, J R Wakeling, Y Zhang. Solving the apparent diversity-accuracy dilemma of recommender systems. Proceedings of the National Academy of Sciences, 2010, 107(10): 4511−4515 https://doi.org/10.1073/pnas.1000488107
6	L N David, K Jon. The link prediction problem for social networks. In: Proceedings of the 12th International Conference on Information and Knowledge Management. 2003, 556−559
7	G M Shroff. A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix. Numerische Mathematik, 1990, 58(1): 779−805 https://doi.org/10.1007/BF01385654
8	J Ekanayake, H Li, B Zhang, T Gunarathne, S H Bae, J Qiu, G Fox. Twister: a runtime for iterative MapReduce. In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. 2010, 810−818 https://doi.org/10.1145/1851476.1851593
9	Y Bu, B Howe, M Balazinska, M D Ernst. HaLoop: efficient iterative data processing on large clusters. Proceedings of the VLDB Endowment, 2010, 3(1): 285−296 https://doi.org/10.14778/1920841.1920881
10	M Zaharia, M Chowdhury, M J Franklin, S Shenker, I Stoica. Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. 2010, 1−10
11	Y Low, J Gonzalez, A Kyrola, D Bickson, C Guestrin, J M Hellerstein. Graphlab: a new framework for parallel machine learning. In: Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence. 2010, 1−10
12	Y Zhang, Q Gao, L Gao, C Wang. Maiter: an asynchronous graph processing framework for delta-based accumulative iterative computation. IEEE Transactions on Parallel and Distributed System, 2013,
13	T Zou, G Wang, M V Salles, D Bindel, A Demers, J Gehrke, W White. Making time-stepped applications tick in the cloud. In: Proceedings of the 2nd ACM Symposium on Cloud Computing. 2011, 1−20 https://doi.org/10.1145/2038916.2038936
14	Y Zhang, Q Gao, L Gao, C Wang. Imapreduce: a distributed computing framework for iterative computation. In: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum. 2011, 1112−1121
15	R Power, J Li. Piccolo: building fast, distributed programs with partitioned tables. In: Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. 2010, 1−14
16	D Logothetis, C Olston, B Reed, K C Webb, K Yocum. Stateful bulk processing for incremental analytics. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 51−62 https://doi.org/10.1145/1807128.1807138
17	D G Murray, M Schwarzkopf, C Smowton, S Smith, A Madhavapeddy, S Hand. CIEL: a universal execution engine for distributed dataflow computing. In: Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. 2011, 1−9
18	G Malewicz, M H Austern, A Bik, J C Dehnert, I Horn, N Leiser, G Czajkowski. Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 2010, 135−146 https://doi.org/10.1145/1807167.1807184
19	D Chazan, W Miranker. Chaotic relaxation. Linear Algebra and Its Applications, 1969, 2(2): 199−222 https://doi.org/10.1016/0024-3795(69)90028-7
20	G M Baudet. Asynchronous iterative methods for multiprocessors. Journal of the ACM, 1978, 25(2): 226−244 https://doi.org/10.1145/322063.322067
21	D P Bertsekas. Distributed asynchronous computation of fixed points. Mathematical Programming, 1983, 27(1): 107−120 https://doi.org/10.1007/BF02591967
22	K Kambatla, N Rapolu, S Jagannathan, A Grama. Asynchronous algorithms in mapreduce. In: Proceedings of the 2010 IEEE International Conference on Cluster Computing. 2010, 245−254 https://doi.org/10.1109/CLUSTER.2010.30
23	Y Low, D Bickson, J Gonzalez, C Guestrin, A Kyrola, J M Hellerstein. Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 2012, 5(8): 716−727 https://doi.org/10.14778/2212351.2212354
24	Y Zhang, Q Gao, L Gao, C Wang. Accelerate large-scale iterative computation through asynchronous accumulative updates. In: Proceedings of the 3rdWorkshop on Scientific Cloud Computing Date. 2012, 13−22
25	Stanford. Stanford Large Network Dataset Collection. , 2013
26	G Takács, I Pilászy, B Németh, D Tikk. Scalable collaborative filtering approaches for large recommender systems. The Journal of Machine Learning Research, 2009, 10: 623−656
27	K Haewoon. What is Twitter, a Social Network or a New Media? 2013
28	Y Zhang, Q Gao, L Gao, C Wang. PrIter: a distributed framework for prioritized iterative computations. In: Proceedings of the 2nd ACM Symposium on Cloud Computing. 2011, 1−14 https://doi.org/10.1145/2038916.2038929

[1]	Sedigheh KHOSHNEVIS. A search-based identification of variable microservices for enterprise SaaS[J]. Front. Comput. Sci., 2023, 17(3): 173208-.
[2]	Changbo KE, Fu XIAO, Zhiqiu HUANG, Fangxiong XIAO. A user requirements-oriented privacy policy self-adaption scheme in cloud computing[J]. Front. Comput. Sci., 2023, 17(2): 172203-.
[3]	Rong ZENG, Xiaofeng HOU, Lu ZHANG, Chao LI, Wenli ZHENG, Minyi GUO. Performance optimization for cloud computing systems in the microservice era: state-of-the-art and research opportunities[J]. Front. Comput. Sci., 2022, 16(6): 166106-.
[4]	Qingqing GAN, Joseph K. LIU, Xiaoming WANG, Xingliang YUAN, Shi-Feng SUN, Daxin HUANG, Cong ZUO, Jianfeng WANG. Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage[J]. Front. Comput. Sci., 2022, 16(6): 166820-.
[5]	Wei SHI, Dan TANG, Sijia ZHAN, Zheng QIN, Xiyin WANG. An approach for detecting LDoS attack based on cloud model[J]. Front. Comput. Sci., 2022, 16(6): 166821-.
[6]	Hongbin XU, Weili YANG, Qiuxia WU, Wenxiong KANG. Endowing rotation invariance for 3D finger shape and vein verification[J]. Front. Comput. Sci., 2022, 16(5): 165332-.
[7]	Zhengxiong HOU, Hong SHEN, Xingshe ZHOU, Jianhua GU, Yunlan WANG, Tianhai ZHAO. Prediction of job characteristics for intelligent resource allocation in HPC systems: a survey and future directions[J]. Front. Comput. Sci., 2022, 16(5): 165107-.
[8]	Bowen ZHAO, Shaohua TANG, Ximeng LIU, Yiming WU. Return just your search: privacy-preserving homoglyph search for arbitrary languages[J]. Front. Comput. Sci., 2022, 16(2): 162801-.
[9]	Zhangjie FU, Yan WANG, Xingming SUN, Xiaosong ZHANG. Semantic and secure search over encrypted outsourcing cloud based on BERT[J]. Front. Comput. Sci., 2022, 16(2): 162802-.
[10]	Huiqun WANG, Di HUANG, Yunhong WANG. GridNet: efficiently learning deep hierarchical representation for 3D point cloud understanding[J]. Front. Comput. Sci., 2022, 16(1): 161301-.
[11]	Arpita BISWAS, Abhishek MAJUMDAR, Soumyabrata DAS, Krishna Lal BAISHNAB. OCSO-CA: opposition based competitive swarm optimizer in energy efficient IoT clustering[J]. Front. Comput. Sci., 2022, 16(1): 161501-.
[12]	Yao QIN, Hua WANG, Shanwen YI, Xiaole LI, Linbo ZHAI. A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds[J]. Front. Comput. Sci., 2021, 15(5): 155105-.
[13]	Wei ZHENG, Ying WU, Xiaoxue WU, Chen FENG, Yulei SUI, Xiapu LUO, Yajin ZHOU. A survey of Intel SGX and its applications[J]. Front. Comput. Sci., 2021, 15(3): 153808-.
[14]	Abhishek MAJUMDAR, Arpita BISWAS, Atanu MAJUMDER, Sandeep Kumar SOOD, Krishna Lal BAISHNAB. A novel DNA-inspired encryption strategy for concealing cloud storage[J]. Front. Comput. Sci., 2021, 15(3): 153807-.
[15]	Edje E. ABEL, Muhammad Shafie Abd LATIFF. The utilization of algorithms for cloud internet of things application domains: a review[J]. Front. Comput. Sci., 2021, 15(3): 153502-.

Viewed

Full text

Abstract

Cited

Shared

Discussed