冯.诺依曼计算机-机器级程序及其执行

大学计算机-计算思维导论

李旻先 minxianli@

南京理工大学计算机科学与工程学院

第3讲 冯.诺依曼计算机： 机器级程序及其执行理解“程序和数据如何被存储、如何被执行的”,有助 于构造和设计可执行的算法和程序，有助于复杂环境下 程序执行机制的理解

内容提要基本目标:

3/38

理解程序及其硬件实现思维

基本思维：机器级算法与程序 机器指令与指令系统 存储器 存储程序 运算器与 控制器 机器级程序的执行；算法程序化 程序指令化 指令存储化 执行信号化

冯.诺依曼计算机：机器级程序及其执行 2.2.1 图灵机的思想与模型简介

4/38

图灵机的思想与模型简介----图灵的贡献 ----图灵机：计算机的理论模型 ----指令、数据、程序与程序执行

图灵是谁?

5/38

图灵及其贡献 图灵(Alan Turing, 1912~1954),出生于英国伦敦，19 岁入剑桥皇家学院，22 岁当选为皇家学会会员。 1937 年，发表了论文《论可计算数及其在判定问题中的应 用》,提出了图灵机模型，后来，冯〃诺依曼根据这个模型设 计出历史上第一台电子计算机。

1950 年，发表了划时代的文章：《机器能思考吗?》,成为了人工智能的开山之作。 计算机界于1966年设立了最高荣誉奖：ACM

图灵奖。

你能查阅一下哪些人获得图灵奖了吗？ 因为什么贡献而获奖呢？

图灵认为什么是计算?

6/38

计算 所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串 0或1,执行指令一步一步地改变纸带上的0或1,经过有限步骤最后得到 一个满足预先规定的符号串的变换过程。

0110101

程 序

通用机器

…10001110110输入

由“程序”控制， 一步步将输入 “转换”为输出

10001…输出

0110101

7/38 图灵机的思想是关于数据、指令、程序及程序/指令自动执行的基本思想。 输入被制成一串0和1的纸带，送入机器中----数据。如00010000100011… 机器可对输入纸带执行的基本动作包括：“翻转0为1”,或 “翻转1为0”, “前移一 位”, “停止”。 对基本动作的控制----指令，机器是按照指令的控制选择执行哪一个动作，指令也可以 用0和1来表示：01表示“翻转0为1”(当输入为1时不变),10表示“翻转1为0”(当输入0时 不变), 11表示“前移一位”, 00表示“停止”。 输入如何变为输出的控制可以用指令编写一个程序来完成, 如: 011110110111011100… 机器能够读取程序，按程序中的指令顺序读取指令， 读一条指令执行一条指令。由此实现自动计算。

图灵机是什么?

8/38

图灵机模型 基本的图灵机模型为一个七元组,如右图示意 几点结论: (1) 图灵机是一种思想

模型，它由一个控制器(有

限状态转换器),一条可无限延伸的带子和一个在带子上左右移动的读写头构成。 (2) 程序是五元组<q,X,Y,R(或L或N),p>形式

的指令集。其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方 格中写入符号Y, 然后向右移一格R (或向左移一格L 或不移动N), 同时将机器状态设为p供下一条指令

使用。

9/38(S1,0,0,R,S1)

图灵机模型示例。 (注:圆圈内的是状态，箭线上的是<X,Y,R>,其含义见前页)

0 0 1 1 1 1 0 0 0 (S1,1,1,R,S2)

(S1,0,0,R,S1) (S1,1,1,R,S2) (S2,1,1,R,S2) (S2,0,1,L,S3) (S3,1,1,L,S3) (S3,0,0,N,S4) 控制器

0,0,R S1 1,1,R

1,1,R

0 0 1 1 1 1 0 0 0 (S2,1,1,R,S2) 0 0 1 1 1 1 0 0 0 执 行 过 程

S20,1,L 1,1,L

S4

0,0,N

(S2,0,1,L,S3)0 0 1 1 1 1 0 0 0 (S3,1,1,L,S3) 0 0 1 1 1 1 1 0 0

S3

0 0 1 1 1 1 0 0 0

S1:开始状态 S2:右移状态 S3:左移状态 S4:停机状态功能：将一串1的后面再加一位1

(S3,0,0,N,S4)0 0 1 1 1 1 1 0 0

10/38 几点结论(续): (3)图灵机模型被认为是计算机的基本理论模型 ----计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种离散的、有 穷的、构造性的问题求解思路，一个问题的求解可以通过构造其图灵机(即程

序)来解决。 (4)图灵认为：凡是能用算法方法解决的问题也一定能用图灵机解决; 凡是

图灵机解决不了的问题任何算法也解决不了----图灵可计算性问题。

冯.诺依曼计算机：机器级程序及其执行 2. 2. 2 冯.诺依曼计算机: 思想与构成

11/38

冯.诺依曼计算机: 思想与构成----存储程序原理 ----冯.诺依曼计算机的构成

什么是冯.诺依曼计算机?

12/38

冯.诺依曼(Von.Neumann)计算机 1944~1945年间，冯.诺伊曼提出 “存储程序”的计算机设计思想，并进 行了实践，现代计算机普遍来讲属于冯.诺伊曼机体系。

冯.诺伊曼机的基本思想：

运算和存储分离 存储程序：指令和数据以同等地位事先存于存储器, 可按地址寻访, 连续自动执行。 五大部件构成：运算器、控制器、存储器、输入设备和输出设备 指令和数据用二进制表示，指令由操作码和地址码组成 以运算器为中心，控制器负责解释指令，运算器负责执行指令

冯.诺依曼计算机的结构是怎样的? 部件有哪些? 部件的关系怎样?

13/38

以运算器为中心的冯.诺依曼计算机构成图

存储器为中心与运算器为中心相比的优点在哪里?

14/38

以存储器为中心的现代计算机构成图

同样是五个部件，以不同的结构来连接，便体现了不同的性能----这就是 “系统”:强调“结构”,强调部件连接后的整体性、协同性

冯.诺依曼计算机的工作原理是怎样的?

15/38

工作原理 运算器(9) (

5) (10) (1) (7) (3)

控制台

控制器(2)(4)(6) (8)

存储器

(1)启动控制器工作 (2)发送第1条指令地址 (3)取出指令并分析指令

(6)发送下一条指令地址 (7)取出指令并分析指令

(8)执行指令：发送操作数a所在地址(9)执行指令：取出操作数a (10)执行指令：通知运算器计算a乘x (11)继续后续指令的取指、执行

(4)执行指令：发送操作数x所在地址(5)执行指令：取出操作数x

什么是CPU? 现代计算机的几大部件是什么?

16/38

计算机的基本部件 CPU:中央处理单元(Central Process Unit),将运算器和控制器集成在一块 芯片上，形成微处理器。

CPU、主存储器、I/O设备及总线成为现代计算机的四大核心部件。

总线

现代计算机里面，一个微处理器(芯片)可能包含多个CPU,即多核.

冯.诺依曼计算机：机器级程序及其执行 2.2.3 自动存取：存储器的工作原理

17/38

自动存取：存储器的工作原理----存储器的自动读写

什么是存储器?

18/38

存储器的基本结构存 储 器 电 路 结 构 概 念 图宿舍楼房间 床位(住人/不住人) 房间号 房间钥匙

概念映射存储器存储单元 存储位(存0或存1) 地址编码An-1…A0 单元控制线Wi

输出缓冲器…

公共的走廊及大门……

从存储器与宿舍楼的概念对比 中，你能发现什么异同吗？

存储器是怎样存储0和1的? 又是怎样控制存取的?

19/38

存储器内部的实现示例 当地址线和数据线间连接有 二极管时，则存储的是 1 ,否 则，存储的是0 当地址线和数据线间连接有 二极管时，由地址线决定其是 输出1或0,即：当地址线为高 电平时，则输出 1 ,而当 …… 此处隐藏：1900字，全部文档内容请下载后查看。喜欢就下载吧 ……