图灵机的应用(云计算).ppt

计算机模型与体系架构的发展 从图灵机 到云计算机,一个非常简单的图灵机例子：,从左至右扫描一串二进制数字，如果该数字能够被3整除（是3的倍数）则在该数字串的末尾写出Y，否则写出N，然后停机。, | 有限状态读写头 | | / | 10101 （无限长）存储带 ,按照图灵（Alan Turing）给出的计算机模型，计算机是由一个有限状态读写头和一个存储器构成。有限状态读写头从一个初始状态开始，对存储器上的（输入）数据进行读或写操作，经过有限步操作之后停机，此时存储器上的（输出）数据就是计算结果。这样的计算机模型叫做图灵机。,这个读写头共有3个状态： “状态一”为初始状态，按如下方法从左至右扫描存储带上的数字或写出字符：, | 有限状态读写头 | | / | 10101 （无限长）存储带 ,状态一：读入为0，留在状态一，读入为1，进入状态二， 读入为空，写Y, 停机。,状态二：读入为0，进入状态三，读入为1，进入状态一， 读入为空，写N, 停机。,状态三：读入为0，进入状态二，读入为1，留在状态三， 读入为空，写N, 停机。,存储带上的输入二进制字符串代表十进制数21，是3的倍数，的确读写头扫描完毕后会写出Y并停机。,图灵机模型对于一大类有限步数可计算问题给出了一个普适性的定义。每一个这样的问题都存在一个图灵机可对其进行计算给出答案。 我们知道对有些问题随机方法比确定的方法要快。随机计算方法的图灵机模型可以在基本图灵机上外加上一条存储带，存储着随机数串供 有限状态读写头读取。,有限状态读写头机器的程序执行代码 存储带处理被处理的数据 Universal（通用）机器把有限状态指令存放在存储带上 让读写头根据读入的指令进行下一步操作 这样存储有指令的通用图灵机能够实现任何一个图灵机，比如我们在上面给出的专用图灵机，也就是说可以解决任意一个图灵可计算问题。 我们广泛使用的计算机的确就是采用了存储指令这一原理因而可以解决“万能”计算问题的。,实现方法：,待解决问题,软件编制程序,程序数据存放,中央处理器,指令数据操作,这样的机器也叫做“存储程序计算机”。 在为第一台存储程序计算机EDVAC研发计划做顾问时，约翰冯诺伊曼写了一个草案报告描述了这种带有中央处理器、内存、I/O、总线的存储程序计算机。 所以存储程序计算机还有另外一个学名，叫做冯诺伊曼体系架构（Von Neumann Architecture）。,内存：中央处理器直接发生操作关系的存储器 读写速度快，能够与中央处理器的速度相匹配，但是价格昂贵，而且是挥发式的，即断电时所存储的内容立刻丢失。 外存：穿孔纸带、卡片、磁带，后来又有软、硬磁盘、光盘，如今发展到半导体固态外存（如闪存）。 低速、大容量、非挥发、廉价，对应于内存是一个非常有效的补充。 两者通过I/O进行交互。 图灵本来给出的计算模型就根本没有内、外存储器之分的概念。,猜想：未来的计算机是否还需要有内、外存储器之分呢？,图灵可计算：一个问题是否可以由一个图灵机在有限步数内完成。 单个机器与两（多）台互相通信的机器要么都可以计算某个问题，要么都不可以。 输入为一个二进制数字，输出为该数字的一进制编码 计算时间与所需空间复杂度可以用输入中含有比特数目的指数函数来表示 很低效的算法，但是它的确是一个图灵可计算问题。,我们日常要计算的问题不光都是图灵可计算的，但是大量的问题是多项式步数内可以解决的问题。 易解问题：即算法时间空间复杂度是输入比特数的一个多项式 二进制转换为一进制问题具有指数复杂度，是难解问题 易解问题都可以采用并行计算方法来加速求解（好的并行算法甚至可以达到线性（理想）加速，即使用p台处理器解决该问题的计算用时是使用1台处理器计算用时的1/p） 快速排序（quicksort）,快速排序（quicksort）是一个可以线性加速的问题 “分而攻之”（divide-and-conquer）的方法来求解 一个大问题可以分成p个彼此无关的小问题用p个处理器并行处理。 现今很有名的（由于Google的推广工作）MapReduce函数编程方法是一个可以对任何大型可分解计算问题先做分解，将分解而得的许多小问题发出（Map function）到许多分布机器上并行处理，然后对返回的非完整结果做组合（Reduce function）得到完整结果的一个通用程序设计方法。用MapReduce方法可以对许多大型数据处理问题作有效的并行加速处理。,云计算的兴起使得超算中心不再那么遥远不可及。 MapReduce方法的推广也使得采用并行计算方法来解决大型、大量数据处理的问题变得不再那么专门化了。 Google在推广MapReduce上起到了很有益的作用。然而Google的MapReduce可以说是Google工程师们自用的工具，而不是一项服务。开源社区的Apache Hadoop项目实现了开放源代码的MapReduce工具。 Amazon推出了Amazon Elastic MapReduce服务（也是用Hadoop实现的）。 也就是说一般用户都可以使用该服务对自己的大型计算、数据处理问题定制自己