中国种学技术大学 不 计算机组成原理 第一章概论 李曦 llxx@ustc.edu.cn
计算机组成原理 第一章 概论 李曦 llxx@ustc.edu.cn
本章教学内容 s》 ·计算机组成的科学基础及发展史 ·计算机系统概述 议程序设计语音编译技天了 指令集设计 -计算机软硬件 体系结构设计 一计算机系统的层次结构 算机组织 计算机实现 -计算机组成VS.计算机体系结构 “花农做电子技术则试平价模拟技术 米轩彩业制渐半粥业 ·计算机的基本组成 -Von Neumann机的特征 一计算机的硬件构成 一计算机的工作过程 ·计算机硬件的性能指标 ·数电基础知识回顾
本章教学内容 • 计算机组成的科学基础及发展史 • 计算机系统概述 – 计算机软硬件 – 计算机系统的层次结构 – 计算机组成 VS. 计算机体系结构 • 计算机的基本组成 – Von Neumann机的特征 – 计算机的硬件构成 – 计算机的工作过程 • 计算机硬件的性能指标 • 数电基础知识回顾
信息、意思、语言、文字，编码 STC 莫尔斯 (Morse)电码 2写 eee 0 3 8 9 =÷三兰兽三兰目 曾 10111213141516 17 18 19 象形文字(pictograph):表音？表意？ -距今5000多年，古埃及 天 话 ⊙ CH 骑 92 VAUTOUR PIED D 5文 奢 文三 文三3 SUPPOR MAIN A CORNES DE JARR正 H D ESSEE SERPENT PLACENTA LION HIBOU 千三讲水 OFFE 以正癸压口医志排日回未志平 SIEGE LEVRES PLIEE 能蛋 ●0RD POUSSIN VE RROU 一纳西族的东巴文（上）和水族的水书（下）仍在使用
信息、意思、语言、文字，编码？ • 莫尔斯（Morse）电码 • 象形文字（pictograph）：表音？表意？ – 距今5000多年，古埃及 – 纳西族的东巴文（上）和水族的水书（下）仍在使用
信息论 ·诺伯特·维纳(Norbert Wiener'）,1948 《控制论》：“信息就是信息，既不是物质，也不是能量” 香农(Claude Shannon),“通信的数学理论”，1948 “信息是用来消除随机不定性的东西”？ “信息的最小单位是比特（二值符号）” 任何复杂信息都可以根据其结构和内容，按照一定的编码规则进行 分割，最终成为一组二值数据。一没语言啥事？ 一度量信息量：一本五十万字的书有多少信息量？ ·任何信息都存在冗余 一冗余量与信息中各符号（数字、字母或单词）出现概率有关 ·信息熵：信息中排除了冗余后的平均信息量 一单位：比特 -熵大=复杂（中文9.65比特，英文4.03比特） ·x:信息是意识的表现和物化（编码）
信息论 • 诺伯特·维纳(Norbert Wiener) ，1948 – 《控制论》： “信息就是信息，既不是物质，也不是能量” • 香农（Claude Shannon），“通信的数学理论”，1948 – “信息是用来消除随机不定性的东西” ？ – “信息的最小单位是比特（二值符号）” • 任何复杂信息都可以根据其结构和内容，按照一定的编码规则进行 分割，最终成为一组二值数据。——没语言啥事？ – 度量信息量：一本五十万字的书有多少信息量？ • 任何信息都存在冗余 – 冗余量与信息中各符号（数字、字母或单词）出现概率有关 • 信息熵：信息中排除了冗余后的平均信息量 – 单位：比特 – 熵大＝复杂（中文9.65比特，英文4.03比特） • llxx：信息是意识的表现和物化（编码）☺
能行计算理论(computability thed) ·计算：是对运算过程的一种高度抽象 ·算法 一对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 一将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 算法可计算性：判断一类数学问题是否机械可解 一可计算问题：算术逻辑运算 一非可计算问题：明天是否下雨？ 计算模型(MoC) 一刻画“计算”概念的抽象的形式化系统或数学系统。 ·入演算（串行、递归）、T演算（并行、分布）等 -状态迁移系统(LTS) ·具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 一图灵机
能行计算理论(computability theory) • 计算：是对运算过程的一种高度抽象 • 算法 – 对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 – 将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 • 算法可计算性：判断一类数学问题是否机械可解 – 可计算问题：算术逻辑运算 – 非可计算问题：明天是否下雨？ • 计算模型（MoC） – 刻画“计算”概念的抽象的形式化系统或数学系统。 • λ演算(串行、递归)、π演算（并行、分布）等 – 状态迁移系统（LTS） • 具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 – 图灵机
MoC:图灵机(Turing Machine,1936) STC 自动计算机的结构与行为(ABC) 一一条两端可以无限延伸的纸带 一个读写头（符号包括0、1、b) 01( 一个控制器（执行控制读写头工作的命令） 五元组：（状态、读符号）→（写符号、移动、状态） -状态集：开始状态，中间状态，结束状态 当进入结束状态时，停机(H) 六个操作原语(primitives):读、写、左、右、擦除、停止 控制命令示例： 00011101111100 qi01Rq 控制器 q10Rq q bbRq2 q2bbLq3 初始状态 中间状态 结束状态 q200Hq1 q211Hq1
MoC：图灵机(Turing Machine,1936) • 自动计算机的结构与行为（ABC） – 一条两端可以无限延伸的纸带 – 一个读写头（符号包括0、1、b） – 一个控制器（执行控制读写头工作的命令） • 五元组：（状态、读符号）→（写符号、移动、状态） – 状态集：开始状态，中间状态，结束状态 – 当进入结束状态时，停机(H) – 六个操作原语（primitives）：读、写、左、右、擦除、停止 0 0 0 1 1 1 0 1 1 1 1 1 0 0 控制器 q101Rq1 q110Rq1 q1bbRq2 q2bbLq3 q200Hq1 q211Hq1 控制命令示例：
图灵完备性Turing-complete/.Turing-equivalent ·图灵机：六个基本原语 如果某个系统能够模拟图灵机，那么就称该系统是 图灵完备的 一读、写、擦除、左移、右移、停机 Brainfuck C > ++ptr; 图灵完备语言 --ptr; + ++*ptr; -最小图灵完备语言BF(1993) --*ptr; ·机器模型+8种运算符 putchar(*ptr); *ptr =getchar(); 非图灵完备语言 [ while (*ptr) 一数据描述语言 ·HTML,XML.. 在屏幕上打印"Hello World!"" 算盘=计算机？ 1 +++++++[>++++++>+++++++>++>+++.>+,+++++++..+++.>++..+++.-- ---.>+.>
图灵完备性Turing-complete/Turing-equivalent • 图灵机：六个基本原语 – 如果某个系统能够模拟图灵机，那么就称该系统是 图灵完备的 – 读、写、擦除、左移、右移、停机 • 图灵完备语言 – 最小图灵完备语言BF（1993） • 机器模型+8种运算符 • 非图灵完备语言 – 数据描述语言 • HTML，XML… • 算盘=计算机？ 在屏幕上打印"Hello World!
关于MoC的两个重要原理 一计算复杂性是否与计算模型有关？ 一不同计算模型解决同一类问题所需资源是否相同？ 相似性原理 一相似性原理：所有计算模型的计算能力等同 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 ·Turing完备性 丘奇一图灵论题：可计算性等价于图灵机的可计 算性 ·对偶性原理 一在并行计算模型上，计算的时间与空间可以互换
关于MoC的两个重要原理 – 计算复杂性是否与计算模型有关？ – 不同计算模型解决同一类问题所需资源是否相同? • 相似性原理 – 相似性原理：所有计算模型的计算能力等同 • 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 • Turing完备性 – 丘奇－图灵论题：可计算性等价于图灵机的可计 算性 • 对偶性原理 – 在并行计算模型上，计算的时间与空间可以互换
计算机科学与计算机工程 ·计算机研究的两条路线 一计算机理论：图灵 ·Turing Machine,1936 -可计算性，计算复杂性 -图灵问题：智能的机械化 ·存储程序 一计算机工程：冯诺依曼 von Neuman Machine,1945 ·存储程序：p44 一“指令和数据都存储在存储器中，易于更改
计算机科学与计算机工程 • 计算机研究的两条路线 – 计算机理论：图灵 • Turing Machine，1936 – 可计算性，计算复杂性 – 图灵问题：智能的机械化 • 存储程序 – 计算机工程：冯·诺依曼 • von Neuman Machine，1945 • 存储程序：p44 – “指令和数据都存储在存储器中，易于更改
第一台现代电子计算机，真空管，1946用 唐$2.1 ENIAC(Electronic Numerical Integrator and Computer),1946年宾夕法尼亚大学 运算速度5000次/秒，功耗150kw/h,占地170m2,造价100万美元。用于测定氢弹可靠性。 ·不具备“存储程序”能力一不可编程，且程序无法共享 程序要通过外接电路板输入(wied)。对于不同类型的计算，需要设计相应的外接插板。 十进制并行计算机（同时处理10个数）
第一台现代电子计算机，真空管，1946启用 • ENIAC( Electronic Numerical Integrator and Computer)，1946年宾夕法尼亚大学 – 运算速度 5000次/秒，功耗150kw/h，占地170m2 ，造价100万美元。用于测定氢弹可靠性。 • 不具备“存储程序”能力——不可编程，且程序无法共享 – 程序要通过外接电路板输入（wired）。对于不同类型的计算，需要设计相应的外接插板。 – 十进制并行计算机（同时处理10个数）。 唐$2.1