中国种学技术大学 不 计算机组成原理 第一章概论 李曦 llxx@ustc.edu.cn
计算机组成原理 第一章 概论 李曦 llxx@ustc.edu.cn
计算机系统设计：313模型(LL Application >"hello Software world!" Operating 兵 Systems Architecture Applications Interfaces Micro- architecture 99 Logic Technology Machine Organization Digital Circuits Computer Analog >O Circuits Architect Software Measurement Evaluation Devices Requirements Physics 计算机的功能：算逻运算（狭义），信息计算（广义），实时控制 科学基础：“信息”是什么？什么是“计算”？什么问题能用计算机计算？ 计算机组成原理：什么是计算机？一计算机“硬件”的“ABC
计算机系统设计：313模型（LLXX） 计算机的功能：算逻运算（狭义），信息计算（广义），实时控制 科学基础：“信息”是什么？什么是“计算” ？什么问题能用计算机计算？ 计算机组成原理：什么是计算机？——计算机“硬件”的“ABC
本章教学内容 s》 ·计算机组成的科学基础及发展史 ·计算机系统概述 议程序设计语音编译技天了 指令集设计 -计算机软硬件 体系结构设计 一计算机系统的层次结构 算机组织 计算机实现 -计算机组成VS.计算机体系结构 说未微电子技术试评价模拟技术◆ 米轩彩业制渐半粥业 ·计算机的基本组成 -Von Neumann机的特征 一计算机的硬件构成 一计算机的工作过程 ·计算机硬件的性能指标 ·数电基础知识回顾
本章教学内容 • 计算机组成的科学基础及发展史 • 计算机系统概述 – 计算机软硬件 – 计算机系统的层次结构 – 计算机组成 VS. 计算机体系结构 • 计算机的基本组成 – Von Neumann机的特征 – 计算机的硬件构成 – 计算机的工作过程 • 计算机硬件的性能指标 • 数电基础知识回顾
信息？信息的载体？ USTC 信息、意思、语言、文字，编码系统？ - the Voyager spacecraft,USA,1977 Meaning,Messages,Information? - the central dogma of information theory ( Information is independent of the meaning that it expresses,and of the language used to express it. All that is needed to transfer information from one language to another is a coding system. - Language,word,编码 ·The story of the drum language:Each Kele(刚果 word is spoken by the drums as a sequence of ALPHA OLMEGA feat.SHEYI low and high beats. [ablo genito,zepherin salnt,trinidadian deep rmxs) ·文字：中文/英语（表音or表意） ·图形，0/1编码 The Information:A History,a Theory,a Flood) TRIB已017 ·2011年出版，10少李帅2015年推荐 。。 。。9 12345678910100100010000 0 2 345 6 7 8 9 一三三 三区∩十（光「因车 示宁台岩岩影亨荨 曾 18 19
信息？信息的载体？ • 信息、意思、语言、文字，编码系统？ – the Voyager spacecraft，USA，1977 • Meaning，Messages，Information？ – the central dogma of information theory（？） • Information is independent of the meaning that it expresses, and of the language used to express it. • All that is needed to transfer information from one language to another is a coding system. – Language，word，编码 • The story of the drum language：Each Kele（刚果 语）word is spoken by the drums as a sequence of low and high beats. • 文字：中文/英语（表音 or 表意） • 图形，0/1编码 – 《The Information: A History, a Theory, a Flood》 • 2011年出版，10少李帅2015年推荐
信息论 ·诺伯特·维纳(Norbert Wiener),1948 一《控制论》：“信息就是信息，既不是物质，也不是能量” 香农(Claude Shannon),“通信的数学理论”，1948 “信息是用来消除随机不定性的东西”一不彻底？ “信息的最小单位是比特（二值符号）” 任何复杂信息都可以根据其结构和内容，按照一定的编码规则进行 分割，最终成为一组二值数据。一没语言啥事？ 一度量信息量：一本五十万字的书有多少信息量？ ·任何信息都存在冗余 一冗余量与信息中各符号（数字、字母或单词）出现概率有关 ·信息熵：信息中排除了冗余后的平均信息量 一单位：比特 -熵大=复杂（中文9.65比特，英文4.03比特） ·xx:信息是意识的表现和物化（编码）
信息论 • 诺伯特·维纳(Norbert Wiener) ，1948 – 《控制论》： “信息就是信息，既不是物质，也不是能量” • 香农（Claude Shannon），“通信的数学理论”，1948 – “信息是用来消除随机不定性的东西”——不彻底？ – “信息的最小单位是比特（二值符号）” • 任何复杂信息都可以根据其结构和内容，按照一定的编码规则进行 分割，最终成为一组二值数据。——没语言啥事？ – 度量信息量：一本五十万字的书有多少信息量？ • 任何信息都存在冗余 – 冗余量与信息中各符号（数字、字母或单词）出现概率有关 • 信息熵：信息中排除了冗余后的平均信息量 – 单位：比特 – 熵大＝复杂（中文9.65比特，英文4.03比特） • llxx：信息是意识的表现和物化（编码）☺
计算机科学与计算机工程 ·与CE相关的三个经典问题 -巴贝奇(Charles Babbage)问题，1833 ·自动计算的实现：程序控制 ·建造“分析机”：三角函数、级数相乘、伯努利函数 ·Ada,第一位程序员，Ada语言1981 一图灵问题：智能的机械化 -布什(Vannevar Bush)问题，1945 ·“As We May Think'”:信息的广义互连？ ·计算机研究的两条路线 一计算机理论：图灵 ·Turing Machine,1936,可计算性，存储程序 一计算机工程：冯·诺依曼 ·von Neuman Machine,1945,存储程序
计算机科学与计算机工程 • 与CE相关的三个经典问题 – 巴贝奇（Charles Babbage）问题，1833 • 自动计算的实现：程序控制 • 建造“分析机”：三角函数、级数相乘、伯努利函数 • Ada，第一位程序员，Ada语言1981 – 图灵问题：智能的机械化 – 布什（Vannevar Bush）问题，1945 • “As We May Think”：信息的广义互连？ • 计算机研究的两条路线 – 计算机理论：图灵 • Turing Machine，1936，可计算性，存储程序 – 计算机工程：冯·诺依曼 • von Neuman Machine，1945，存储程序
能行计算理论(computability thed) ·计算：是对运算过程的一种高度抽象 ·算法 一对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 一将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 算法可计算性：判断一类数学问题是否机械可解 一可计算问题：算术逻辑运算 一非可计算问题：明天是否下雨？ ·计算模型(MoC) 一刻画“计算”概念的抽象的形式化系统或数学系统。 ·入演算（串行、递归）、π演算（并行、分布）等 -状态迁移系统(LTS) ·具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 一图灵机
能行计算理论(computability theory) • 计算：是对运算过程的一种高度抽象 • 算法 – 对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 – 将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 • 算法可计算性：判断一类数学问题是否机械可解 – 可计算问题：算术逻辑运算 – 非可计算问题：明天是否下雨？ • 计算模型（MoC） – 刻画“计算”概念的抽象的形式化系统或数学系统。 • λ演算(串行、递归)、π演算（并行、分布）等 – 状态迁移系统（LTS） • 具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 – 图灵机
MoC:图灵机(Turing Machine,1936) STC 自动计算机结构与行为 一一条两端可以无限延伸的纸带 01 -一个读写头（符号包括0、1、b) 一个控制器（执行控制读写头工作的命令） 五元组：（状态、读符号）（写符号、移动、状态》 状态集：开始状态，中间状态，结束状态 当进入结束状态时，停机(H) 六个操作原语(primitives):读、写、左、右、擦除、停止 控制命令示例： 00011101111100 qi01Rq 控制器 q10Rq q bbRq2 q2bbLq3 初始状态 中间状态 结束状态 q200Hq1 q211Hq1
MoC：图灵机(Turing Machine,1936) • 自动计算机结构与行为 – 一条两端可以无限延伸的纸带 – 一个读写头（符号包括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 控制命令示例：
关于MoC的两个重要原理 一计算复杂性是否与计算模型有关？ 一不同计算模型解决同一类问题所需资源是否相同？ 相似性原理 一相似性原理：所有计算模型的计算能力等同 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 ·Turing完备性 丘奇一图灵论题：可计算性等价于图灵机的可计 算性 ·对偶性原理 一在并行计算模型上，计算的时间与空间可以互换
关于MoC的两个重要原理 – 计算复杂性是否与计算模型有关？ – 不同计算模型解决同一类问题所需资源是否相同? • 相似性原理 – 相似性原理：所有计算模型的计算能力等同 • 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 • Turing完备性 – 丘奇－图灵论题：可计算性等价于图灵机的可计 算性 • 对偶性原理 – 在并行计算模型上，计算的时间与空间可以互换
图灵完备性Turing-complete/Turing-equivalent ·图灵机：六个基本原语 一如果某个系统能够模拟图灵机，那么就称该系 统是图灵完备的 Brainfuck ·图灵完备语言 > ++ptr; --ptr; + -最小图灵完备语言BF(1993) ++*ptr; --*ptr; ·机器模型+8种运算符 putchar(*ptr); *ptr =getchar(); ·非图灵完备语言 [ while (*ptr){ -HTML,XML... 在屏幕上打印"Hello World" ·算盘=计算机？ 1++++++++[>+++++>+++++++>++>+++.>+,+++++++..+++.>++..+++.-- ---.>+.>
图灵完备性Turing-complete/Turing-equivalent • 图灵机：六个基本原语 – 如果某个系统能够模拟图灵机，那么就称该系 统是图灵完备的 • 图灵完备语言 – 最小图灵完备语言BF（1993） • 机器模型+8种运算符 • 非图灵完备语言 – HTML，XML… • 算盘=计算机？ 在屏幕上打印"Hello World!
