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


Current cloud computing systems, whether virtualization clouds or partitioned clouds, face the challenge of simultaneously satisfying user experience and system efficiency requirements. Both the industry and the academia are investigating next-generation cloud computing systems to address this problem. This paper points out a main cause of this problem: existing cloud systems have high computing system entropy (i.e., disorder and uncertainty), which manifest as four classes of disorders. We propose a new concept of “low-entropy cloud computing systems", and contrast them to virtualization clouds and partitioned clouds, in terms of user experience, application development efficiency, execution efficiency, and resource matching. We discuss four new features and techniques of low-entropy clouds: (1) a notion of production computability that, unlike Turing computability and algorithmic tractability, formalizes the user experience requirements of cloud computing practices; (2) a conjecture, named the DIP (differentiation, isolation, prioritization) conjecture, that tries to capture the necessary and sufficient conditions for a cloud computing system to realize production computability; (3) the labeled von Neumann architecture that has the potential to support the DIP capabilities and thus simultaneously satisfy user experience and system efficiency requirements; and (4) a co-design technique allowing a cloud computing system to adaptively match deep-learning workloads to neural network accelerator hardware.

Funded by




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


[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
    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

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号