冯.诺依曼计算机-机器级程序及其执行PPT参考课件.ppt

,*,/38,大学计算机-计算思维导论,李旻先,minxianli,南京理工大学计算机科学与工程学院,第,3,讲 冯,.诺依曼计算机,：,机器级程序及其执行,理解,“,程序和数据如何被存储、如何被执行的,”,，有助于,构造和设计可执行的算法和程序，有助于复杂环境下程序执行机制的理解,基本目标,:,理解程序及其硬件实现思维,基本思维：,机器级算法与程序,机器指令与,指令系统,存储器,存储程序,运算器与控制器,机器级程序的执行,；算法程序化,程序指令化,指令存储化,执行信号化,内容提要,图灵机的思想与模型简介,-,图灵的贡献,-,图灵机：计算机的理论模型,-,指令、数据、程序与程序执行,冯,.,诺依曼计算机：机器级程序及其执行,2.2.1,图灵机的思想与模型简介,图灵及其贡献,图灵,(Alan Turing,19121954),，,出生于英国伦敦，19 岁入剑桥皇家学院，22 岁当选为皇家学会会员。,1937 年，发表了论文论可计算数及其在判定问题中的应用，提出了,图灵机模型,，后来，冯,诺依曼根据这个模型设计出历史上第一台电子计算机。,1950 年，发表了划时代的文章：机器能思考吗,?,成为了人工智能的开山之作。,计算机界于,1966,年,设立了最高荣誉奖：,ACM 图灵奖,。,图灵是谁,?,你能查阅一下哪些人获得图灵奖了吗？因为什么贡献而获奖呢？,所谓,计算,就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的,变换过程,。,计算,10001110110,0110101,10001,0110101,由“程序”控制，一步步将输入“转换”为输出,输入,输出,程序,通用机器,图灵认为什么是计算,?,图灵机的思想,是关于数据、指令、程序及程序,/,指令自动执行的基本思想。,输入被制成一串,0,和,1,的纸带，送入机器中,-,数据,。如,00010000100011,机器可对输入纸带执行的,基本动作,包括：,“,翻转,0,为,1,”,，或,“,翻转,1,为,0,”,“,前移一位,”,“,停止,”,。,对基本动作的控制,-,指令,，机器是按照指令的控制选择执行哪一个动作，指令也可以用,0,和,1,来表示,：,01,表示,“,翻转,0,为,1,”,(,当输入为,1,时不变,),，,10,表示,“,翻转,1,为,0,”,(,当输入,0,时不变,),11,表示,“,前移一位,”,00,表示,“,停止,”,。,输入如何变为输出的控制可以用指令编写一个,程序,来完成,如,:,01,11,10,11,01,11,01,11,00,机器能够读取程序，按程序中的指令顺序读取指令，,读一条指令,执行,一条指令。由此实现,自动计算,。,基本的,图灵机模型,为一个七元组,如右图示意,几点结论,:,(1)图灵机是一种思想模型，它由一个控制器(,有限状态转换器,)，一条可无限延伸的带子和一个在带子上左右移动的读写头,构成。,(2),程序是五元组,形式的指令集,。其定义了机器在一个特定状态,q,下从方格中读入一个特定字符,X,时所采取的动作为在该方格中写入符号,Y,然后向右移一格,R(,或向左移一格,L,或不移动,N),同时将机器状态设为,p,供下一条指令使用。,图灵机是什么,?,图灵机模型,图灵机模型示例,。,(,注,:,圆圈内的是状态，箭线上的是,，其含义见前页,),执行过程,功能：将一串,1,的后面再加一位,1,0 0 1 1 1 1 0 0 0,控制器,(S,1,0,0,R,S,1,),(S,1,1,1,R,S,2,),(S,2,1,1,R,S,2,),(S,2,0,1,L,S,3,),(S,3,1,1,L,S,3,),(S,3,0,0,N,S,4,),S,1,S,2,S,3,S,4,1,1,R,1,1,R,0,1,L,1,1,L,0,0,N,S,1,：开始状态,S,2,：右移状态,S,3,：左移状态,S,4,：停机状态,0,0,R,0 0 1 1 1 1 0 0 0,0 0 1 1 1 1 0 0 0,(S,1,0,0,R,S,1,),(S,1,1,1,R,S,2,),0 0 1 1 1 1 0 0 0,(S,2,1,1,R,S,2,),0 0 1 1 1 1 0 0 0,(S,2,0,1,L,S,3,),0 0 1 1 1 1 1 0 0,(S,3,1,1,L,S,3,),0 0 1 1 1 1 1 0 0,(S,3,0,0,N,S,4,),几点结论,(,续,):,(3),图灵机模型,被认为是计算机的基本理论模型,-,计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种离散的、有穷的、,构造性的,问题求解思路，,一个问题的求解可以通过构造其图灵机,(,即程序,),来解决,。,(4),图灵认为：,凡是能用算法方法解决的问题也一定能用图灵机解决,;,凡是图灵机解决不了的问题任何算法也解决不了,-,图灵可计算性问题。,冯,.,诺依曼计算机,:,思想与构成,-,存储程序原理,-,冯,.,诺依曼计算机的构成,冯,.,诺依曼计算机：机器级程序及其执行,2.2.2,冯,.,诺依曼计算机,:,思想与构成,19441945年间，冯,.,诺伊曼提出,“,存储程序,”,的计算机设计思想,，并进行了实践，,现代计算机普遍来讲属于冯,.,诺伊曼机体系。,冯,.,诺伊曼机,的基本思想,：,运算,和,存储,分离,存储程序,：,指令和数据,以同等地位,事先,存于存储器,可按地址寻访,连续自动执行。,五大部件构成：,运算器,、,控制器,、,存储器,、,输入设备,和,输出设备,指令和数据用,二进制,表示,，,指令由操作码和地址码组成,以运算器为中心，控制器负责解释指令,，运算器负责执行指令,什么是冯,.,诺依曼计算机,?,冯,.诺依曼,(Von.Neumann),计算机,以运算器为中心的冯,.,诺依曼计算机构成图,冯,.,诺依曼计算机的结构是怎样的,?,部件有哪些,?,部件的关系怎样,?,以存储器为中心的现代计算机构成图,存储器为中心与运算器为中心相比的优点在哪里,?,同,样是五个部件，以不同的结构来连接，便体现了不同的性能,-,这就是,“,系统,”,：强调,“,结构,”,，强调部件连接后的整体性、协同性,运算器,存储器,控制台,控制器,(1),(3),(10),(5),(2),(4),(6),(1),启动控制器工作,(2),发送第,1,条指令地址,(3),取出指令并分析指令,(4),执行指令：发送操作数,x,所在地址,(5),执行指令：取出操作数,x,(10),执行指令：通知运算器计算,a,乘,x,(11),继续后续指令的取指、执行,(6),发送下一条指令地址,(7),取出指令并分析指令,(8),执行指令：发送操作数,a,所在地址,(9),执行指令：取出操作数,a,(7),(8),(9),冯,.,诺依曼计算机的工作原理是怎样的,?,工作原理,计算机的基本部件,CPU,：,中央处理单元,(Central Process Unit),，将运算器和控制器集成在一块芯片上，形成微处理器。,CPU,、主存储器、,I/O,设备及总线成为现代计算机的四大核心部件。,总线,什么是,CPU?,现代计算机的几大部件是什么,?,现代计算机里面，一个微处理器,(,芯片,),可能包含多个,CPU,，即多核,.,自动存取：存储器的工作原理,-,存储器的自动读写,冯,.,诺依曼计算机：机器级程序及其执行,2.2.3,自动存取：存储器的工作原理,存储器的基本结构,存储器电路结构概念图,什么是存储器,?,存储器,宿舍楼,存储单元,房间,存储位,(,存,0,或存,1),床位,(,住人,/,不住人,),地址编码,A,n-1,A,0,房间号,单元控制线,W,i,房间钥匙,输出缓冲器,公共的走廊及大门,概念映射,从存储器与宿舍楼的概念对比中，你能发现什么异同吗？,存储器内部的实现示例,当地址线和数据线间连接有二极管时，则存储的是,1,，否则，存储的是,0,当地址线和数据线间连接有二极管时，由地址线决定其是输出,1,或,0,，即：当地址线为高电平时，则输出,1,，而当地址线为低电平时，则输出,0,；,没有连接的，则不受地址线影响，始终输出低电平,0,；,二极管,ROM,结构示例,(2,位地址控制,4,个信息单元,每个信息单元是,4,位,0/1,码,),存储器是怎样存储,0,和,1,的,?,又是怎样控制存取的,?,二极管,ROM,结构示例,(2,位地址控制,4,个信息单元,每个信息单元是,4,位,0/1,码,),1,1,1,0,1,0,1,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,1,存储器内部的实现示例,2-4,地址译码器,0,1,0,1,存储矩阵的逻辑控制关系示例,1,1,0,0,1,0,0,0,0,1,0,1,同一条数据线上各连接点之间是“或”关系,同一地址线上各连接点之间是“与”关系,D,j,是数据线,W,i,是地址线,地址编码线与地址线有点连接，无点不连接,A,k,是地址编码线,地址线与数据线有点连接，无点不连接,高,/,低电平信号，即,0,1,，通过连接点相互传递,上半区通过“与”关系产生地址线上的最终信号传递到下半区,D,3,=W,0,OR W,2,D,2,=W,1,OR W,2,OR W,3,D,1,=W,1,OR W,2,D,0,=W,0,OR W,1,OR W,3,W,0,=(NOT A,0,)AND(NOT A,1,),W,1,=A,0,AND (NOT A,1,),W,2,=(NOT A,0,)AND A,1,W,3,=A,0,AND A,1,用多个存储器芯片可搭建容量更大的存储器,利用,4,个,256x8,存储器芯片扩展出,1024x8,存储器的电路图,半导体存储器芯片示例,存储器芯片容量不够了怎么办,?,问：从概念的角度，你能说说存储器扩展要解决什么问题吗,?,提示：地址编码空间,存储字长,.,机器级程序,-,机器指令,-,机器级算法与程序,冯,.,诺依曼计算机：机器级程序及其执行,2.2.4,机器级程序,算法,-,从,冯.诺依曼计算机,的角度,可在机器上执行的求解问题的操作规则及步骤,被称为可执行的算法。,2.2.4,机器级程序,什么是算法,?,问：怎么看待算法节省的步数,?-,算法需要,“,优化,”,机器指令,机器指令是,CPU,可以直接分析并执行的指令，一般由,0,和,1,的编码表示。,指令,操作码,+,地址码,；,机器语言,000001,0000000100,000001,0000001100,000001,0000001000,机器指令是怎样的,?,机器级程序,8,3,2,+2,3,+6;,a,x,2,+b,x,+c,。,怎样用机器指令表达算法,?,高级语言程序的示例,计算,a,x,2,+b,x,+c,其中,a,x,b,c,是变量。,变量的地址是由编译程序在编译,过程中自动分配的，也即是说编,译器根据当时编译的情况，分配,a,x,b,c,为,8,号，,9,号，,10,号，,11,号,存储单元，并产生上述的机器指,令程序,高级语言程序和机器有什么关系呢,?,机器级程序的执行机制,-,运算部件与控制部件,-,指令的信号化与节拍化,冯,.,诺依曼计算机：机器级程序及其执行,2.2.5 机器级程序的执行机制,计算机各部件内部的简单构成关系,运算器、控制器里面有什么,?,寄存器,算术逻辑部件,程序计数器,PC,指令寄存器,信号控制器,时钟与信号发生器,存储单元地址,存储单元内容,不同的指令，由一组不同的电信号构成,同一指令的电信号在时钟与节拍的控制下按次序产生与传输,一条指令占用一个或多个机器周期，一个机器周期又分为多个节拍,最小的时间区隔单位,-,时钟周期,指令是怎样被执行的,?,指令执行,时钟周期、节拍与机器周期,问：机器的,“,主频,”,指的是什么,?,机器级程序的执行过程模拟,-,程序的硬件执行过程,机器级程序的执行过程模拟,第,1,条指令在一个机器周期内完成。其中读取,和执行分别在,T,0,、,T,1,和,T,2,、,T,3,节拍内完成。,(,示意,),一条指令是怎样被执行的,?,一条指令的执行,一条指令的执行,第,1,条指令在一个机器周期内完成。其中读取,和执行分别在,T,0,、,T,1,和,T,2,、,T,3,节拍内完成。,(,示意,),一条指令是怎样被执行的,?,一段程序又是怎样被执行的,?,程序中指令的逐条执行,程序中指令的逐条执行,程序中指令的逐条执行,基本目标,:,理解程序及其硬件实现思维,基本思维：,机器级算法与程序,机器指令与,指令系统,存储器,存储程序,运算器与控制器,机器级程序的执行,；算法程序化,程序指令化,指令存储化,执行信号化,本讲小结,2014,Questions&Discussion?,第,3,讲 冯,.诺依曼计算机,：,机器级程序及其执行,