logo

SCIENTIA SINICA Informationis, Volume 47 , Issue 9 : 1149-1163(2017) https://doi.org/10.1360/N112017-00069

Low-entropy cloud computing systems

More info
  • ReceivedApr 8, 2017
  • AcceptedJul 3, 2017
  • PublishedSep 6, 2017

Abstract


Funded by

国家重点研发计划(2016YFB1000200)

国家自然科学基金重点项目(61532016)


Acknowledgment

感谢匿名评审人对本文提出问题和建议, 他们辛勤的工作对改善本文的内容与表达有实质性的启发. 感谢中国科学院计算技术研究所软件定义 云计算课题组与寒武纪团队对本文的贡献和 支持.


References

[1] Fox A. Cloud computing — what's in it for me as a scientist? Science, 2011, 331: 406--407. Google Scholar

[2] Panitkin S. Look to the clouds and beyond. Nat Phys, 2015, 11: 373-374 CrossRef ADS Google Scholar

[3] Asanovic K, Patterson D. FireBox: a hardware building block for 2020 warehouse-scale computers. In: Proceedings of the 12th USENIX Conference on File and Storage Technologies, Santa Clara, 2014. Google Scholar

[4] Bao Y G, Wang S. Labeled von Neumann Architecture for Software-Defined Cloud. J Comput Sci Technol, 2017, 32: 219-223 CrossRef Google Scholar

[5] Barroso L A, Clidaras J, Hölzle U. The Datacenter as A Computer: An Introduction to the Design of Warehouse-Scale Machines. San Rafael: Morgan & Claypool Publishers, 2013. Google Scholar

[6] Cai B L, Zhang R Q, Zhou X B. Experience Availability: Tail-Latency Oriented Availability in Software-Defined Cloud Computing. J Comput Sci Technol, 2017, 32: 250-257 CrossRef Google Scholar

[7] Dean J, Barroso L A. The tail at scale. Commun ACM, 2013, 56: 74--80. Google Scholar

[8] Ma J Y, Sui X F, Sun N H, et al. Supporting differentiated services in computers via programmable architecture for resourcing-on-demand (PARD). ACM SIGPLAN Notice, 2015, 50: 131--143. Google Scholar

[9] Krushevskaja D, Sandler M. Understanding latency variations of black box services. In: Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, 2013. 703--714. Google Scholar

[10] Smith J, Nair R. Virtual Machines: Versatile Platforms for Systems and Processes. San Francisco: Morgan Kaufmann Publishers, 2005. Google Scholar

[11] Kivity A, Kamay Y, Laor D, et al. kvm: the Linux virtual machine monitor. Proc Linux symp, 2007, 1: 225--230. Google Scholar

[12] Merkel D. Docker: lightweight Linux containers for consistent development and deployment. Linux J, 2014, 239: 2. Google Scholar

[13] Delimitrou C, Kozyrakis C. Quasar: resource-efficient and QoS-aware cluster management. ACM SIGPLAN Notice, 2014, 49: 127--144. Google Scholar

[14] Barham P, Dragovic B, Fraser K. Xen and the art of virtualization. SIGOPS Oper Syst Rev, 2003, 37: 164-177 CrossRef Google Scholar

[15] Chung H, Nah Y. Performance comparison of distributed processing of large volume of data on top of xen and docker-based virtual clusters. In: Proceedings of International Conference on Database Systems for Advanced Applications. Berlin: Springer, 2017. 103--113. Google Scholar

[16] Chen T, Guo Q, Temam O. Statistical Performance Comparisons of Computers. IEEE Trans Comput, 2015, 64: 1442-1455 CrossRef Google Scholar

[17] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters. Commun ACM, 2008, 51: 107--113. Google Scholar

[18] Chang F, Dean J, Ghemawat S, et al. Bigtable: a distributed storage system for structured data. ACM Trans Comput Syst, 2008, 26: 1--26. Google Scholar

[19] Malewicz G, Austern M H, Bik A J C, et al. Pregel: a system for large-scale graph processing. In: Proceedings of the ACM SIGMOD International Conference on Management of data, Indianapolis, 2010. 135--146. Google Scholar

[20] Gonzalez J E, Xin R S, Dave A, et al. GraphX: graph processing in a distributed dataflow framework. In: Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, Broomfield, 2014. 599--613. Google Scholar

[21] Huang J, Mozafari B, Wenisch T F. Statistical analysis of latency through semantic profiling. In: Proceedings of the 12th European Conference on Computer Systems, Belgrade, 2017. 64--79. Google Scholar

[22] Lu X Y, Liang F, Wang B, et al. DataMPI: extending MPI to hadoop-like big data computing. In: Proceedings of International Parallel and Distributed Processing Symposium, Phoenix, 2014. 829--838. Google Scholar

[23] DeCandia G, Hastorun D, Jampani M. Dynamo. SIGOPS Oper Syst Rev, 2007, 41: 205-220 CrossRef Google Scholar

[24] Hindman B, Konwinski A, Zaharia M, et al. Mesos: a platform for fine-grained resource sharing in the data center. In: Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, Boston, 2011. 295-308. Google Scholar

[25] Zaharia M, Chowdhury M, Tathagata D, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, San Jose, 2012. Google Scholar

[26] Xu Z, Chi X, Xiao N. High-performance computing environment: a review of twenty years of experiments in China. Nat Sci Rev, 2016, 3: 36-48 CrossRef Google Scholar

[27] Xu Z W. Cloud-Sea Computing Systems: Towards Thousand-Fold Improvement in Performance per Watt for the Coming Zettabyte Era. J Comput Sci Technol, 2014, 29: 177-181 CrossRef Google Scholar

[28] Byma S, Steffan J G, Bannazadeh H, et al. FPGAs in the cloud: booting virtualized hardware accelerators with OpenStack. In: Proceedings of the 22nd Annual International Symposium on Field-Programmable Custom Computing Machines, Boston, 2014. 109--116. Google Scholar

[29] Jouppi N P, Young C, Patil N, et al. In-datacenter performance analysis of a tensor processing unit. In: Proceedings of the 44th International Symposium on Computer Architecture, Toronto, 2017. Google Scholar

[30] Putnam A, Jan G, Michael G. A reconfigurable fabric for accelerating large-scale datacenter services. SIGARCH Comput Archit News, 2014, 42: 13-24 CrossRef Google Scholar

[31] Caulfield A M, Chung E S, Putnam A, et al. A cloud-scale acceleration architecture. In: Proceedings of IEEE/ACM International Symposium on Microarchitecture, Taipei, 2016. 1--13. Google Scholar

[32] Nyberg C, Barclay T, Cvetanovic Z. Alphasort: A cache-sensitive parallel external sort. VLDB J, 1995, 4: 603-627 CrossRef Google Scholar

[33] Popek G J, Goldberg R P. Formal requirements for virtualizable third generation architectures. Commun ACM, 1974, 17: 412-421 CrossRef Google Scholar

[34] Brewer E A. Towards robust distributed systems. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, Portland, 2000. Google Scholar

[35] Gilbert S, Lynch N. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 2002, 33: 51-59 CrossRef Google Scholar

[36] Herlihy M, Shavit N. The topological structure of asynchronous computability. J ACM, 1999, 46: 858-923 CrossRef Google Scholar

[37] Herlihy M. Topology approach in distributed computing. In: Encyclopedia of Algorithms. Berlin: Springer, 2008. 2239--2242. Google Scholar

[38] Herlihy M, Rajsbaum S. A classification of wait-free loop agreement tasks. Theor Comp Sci, 2003, 291: 55-77 CrossRef Google Scholar

[39] Liu X, Xu Z, Pan J. Classifying rendezvous tasks of arbitrary dimension. Theor Comp Sci, 2009, 410: 2162-2173 CrossRef Google Scholar

[40] Rich E. Automata, Computability and Complexity: Theory and Applications. Upper Saddle River: Pearson Prentice Hall, 2008. Google Scholar

[41] Liu Y H, Sun X H. Optimizing Memory Concurrency at Each Memory Layer in a Multi-Tasking Environment. Illinois Institute of Technology Technical Report, 2015. Google Scholar

[42] Xu M, Phan L T, Choi H Y, et al. vCAT: dynamic cache management using CAT virtualization. In: Proceedings of IEEE Real-Time and Embedded Technology and Applications Symposium, Pittsburgh, 2017. Google Scholar

[43] Herdrich A, Verplanke E, Autee P, et al. Cache QoS: from concept to reality in the Intel® Xeon® processor E5-2600 v3 product family. In: Proceedings of IEEE International Symposium on High Performance Computer Architecture, Barcelona, 2016. 657--668. Google Scholar

[44] Chen Y, Chen T, Xu Z. DianNao family. Commun ACM, 2016, 59: 105-112 CrossRef Google Scholar

[45] Chen Y J, Luo T, Liu S L, et al. DaDianNao: a machine-learning supercomputer. In: Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, Cambridge, 2014. 609--622. Google Scholar

[46] Liu S L, Du Z D, Tao J H, et al. Cambricon: an instruction set architecture for neural networks. In: Proceedings of the 43rd International Symposium on Computer Architecture, Seoul, 2016. 393--405. Google Scholar

[47] Lan H Y, Wu L Y, Zhang X. DLPlib: A Library for Deep Learning Processor. J Comput Sci Technol, 2017, 32: 286-296 CrossRef Google Scholar

  • Figure 1

    (Color online) Three types of cloud computing techniques. (a) Virtualization cloud; (b) partitioned cloud;protectłinebreak (c) low-entropy cloud

  • Figure 2

    (Color online) The trends of speed, energy efficiency, and power consumption of the world's fastest computers

  • Figure 3

    (Color online) Comparison of phase spaces in (a) (b) partitioned cloud and (c) (d) low-entropy cloud. protectłinebreak (a) Partitioned cloud; (b) phase spaces in partitioned cloud; (c) low-entropy cloud; (d) phase spaces in low-entropy cloud

  • Figure 4

    (Color online) Accessing memory in the labeled von Neumann architecture

  • Figure 5

    Using the Cambricon neural network processor in low-entropy cloud

  • Table 1   Comparison among three types of computability
    Computability Deciding reason Example Concerned
    elements
    Theoretic Turing computability Halting problem Problem
    computability is not decidable
    Algorithmic Polynomial time Gaussian elimination Problem &
    computability complexity to solve equation algorithm
    Production User experience Search engine service Problem & algorithm
    computability (tail latency) in the cloud platform & system