计算导论
计算导论
第一次数学危机
- 毕达哥拉斯学派（公元前500年）
- 数是万物本原，事物的性质是由某种数量关系决定的，万物按照一定数量的比例构成和谐的秩序
- 一切数均可以表示成整数或整数比
- 毕达哥拉斯证明了勾股定理，同时发现直角三角形的三边比不能用整数表达。他的学生，希帕索斯考虑了一个问题：边长为1的正方形其对角线长度是多少？无理数的出现挑战了人们的信仰，希帕索斯被处死。
- 两百年后欧多克索斯建立了一套完整的比例论，巧妙的避开了无理数，缓解了数学危机，推动了几何学的发展
- 19世纪下半叶，实数理论正式确立后猜得到解决。
第二次数学危机
- 17世纪，牛顿和莱布尼茨各自独立发现了微积分，但两人理论都是建立在无穷小的分析之上。贝克莱提出质疑，无穷小有时为0，有时又不为0。是怎么回事。
- 19世纪实数理论的提出，引出极限理论
- 19世纪下半叶，康托尔创立了著名的集合论
- 伯特兰罗素，讲了一个故事，质疑了集合论:
塞尔维亚有一位理发师：他只给所有不给自己理发的人理发，不给那些给自己理发的人理发。问：他要不要给自己理发？
- 罗素悖论：s由一切不是自身元素的集合所组成，罗素问:
s是否属于s呢？。证明集合论存在问题。 - 1931年哥德尔不完备性定理：
任何一个数学系统，只要它是从有限的公理和基本概念中推导出来的，并且从中能推证出自然数系统，就可以在其中找到一个命题，对于它我们既没办法证明，也没办法推翻
哥德尔不完全定理的证明结束了关于数学基础的争论，宣告了把数学彻底形式化的愿望是不可能的
可计算问题
那么对于一个系统中的可证问题和不可证问题的边界在哪里呢？
- 设函数
f的定义域是D，值域是R，如果存在一种算法，对D中任意给定的x都能计算出f(x)，则称函数是可计算的。 - 研究思路
- 为计算建立一个数学模型，称为计算建模，然后证明，凡是这个计算模型能够完成的任务，就是可计算任务。
图灵机
- 1936年,图灵在其著名的论文《论可计算数在判定问题中的应用》一文种提出了一种理想的计算机数学模型，图灵机
- 美国计算机协会ACM于1966年设立图灵奖
- 图灵机的构成
- 一条存储带
- 双向无限延长
- 上有一个个小方格
- 每个小方格可存储一个数字/字母
- 一个控制器
- 包含一个读写头，可以读写，更改存储带上
- 可以接受设定好的程序语句
- 可以改变自身的状态
- 可以沿着存储带一格一格的左移右移
- 一条存储带
- 图灵机的工作准备：
- 存储带上符号初始化
- 控制器设置好自身的状态
- 控制器位于起始位置
- 准备好工作程序
- 图灵机的工作步骤
- 读写头读出存储带上当前方格中的字符/数字
- 根据自身状态和读入的字符，找到响应的程序语句
- 根据响应的程序，做三个动作：
- 在当前存储带放个上写入一个相应的字母/数字
- 变更自身状态至新状态
- 读写头向左，或向右移动一步
- 图灵机停机
- 标识计算完毕，表示当前存储带上保留的是计算结果，停机意味着计算得出结果
- 也就是说：
- 对于一个问题的输入A,能否推证出B，如果能找到一个个图灵机并得到B，那么A到B就是可计算的。
- 图灵机收到重视:
- 简单
- 强大
- 可实现：http://aturingmachine.com
- 图灵机的意义：
- 可计算性的判定
- 给出了一个通用的计算模型
- 引入了通过读写符号和状态改变来进行运算的思想
- 实现了基于简单的字母表，完成复杂运算的能力
- 引入了存储器，程序，控制器等概念的原型
计算机为什么能计算
-
“数”在计算机种如何表示？
- 字母表中的符号越多，读入移动次数减少，但程序数量就越多
- 字母表中符号越少，程序量会减少，但读入移动次数就越多
- 字母表中符号的最优数量，可能是
欧拉常数e(2.7182818284590...)取整后为3。 - 与具有两个状态的电子元件相比，具有三个状态的电子元件在制造上更困难，可靠性更低。
-
逻辑上“数”是如何计算的？
- 布尔代数
-
1854年，布尔发表<思维规律的研究——逻辑与概率的数学理论基础>，并综合其另一篇文章《逻辑的数学分析》，创立了一门全新的学科——布尔代数。
- 为计算机的电路设计提供了重要的数学方法和理论基础。
- 基本的逻辑运算: 与或非
- 符合逻辑运算：同或，异或，与非，或非，与或非
-
- 用二进制实现加法
- 本位：A和B的亦或运算
- 进位: A和B的与运算
-
所有基本的逻辑运算都可以用电路表示，与门，非门，或门，与或门。。。
- 结论：
- 参与运算的数可以转换为 二进制
- 二进制的运算可以用布尔运算实现
- 基本的布尔运算都可以由电路实现
- 布尔代数
计算机的历史与未来
历史
- 手工计算器， 1200年 ~ 1600年
- 算盘
- Oughtred计算尺，1621
- Napier乘除器 ，1617
- 机械计算器，1600年 ~ 1930年
- 帕斯卡加法器(1642)
- 齿轮组成装置，依靠发条转动，用铁笔拨动转轮输入数字
- 6位加减法
- 契克卡德(1623)
- 德国科学家，天文学，数学
- 1623年为开普勒制作计算机
- 6位加减法
- 莱布尼茨(1646-1716)
- 德国伟大数学家，提出”二进制”概念
- 1673年改进帕斯卡加法器，进行四则运算
- 16位加减法
- 帕斯卡加法器(1642)
- 计算机原型，1937年 ~ 1946年
- 巴贝奇差分机(1822年)
- 处理3个不同的5位数
- 计算精度达到6位小数
- 巴贝奇分析机(1834年)
- 堆栈，运算器，控制器
- 计算用的程序和数据存储于穿孔卡片上
- Ada Augusta
- 分析编制了人类历史上第一批计算机程序
- Hollerith
- 统计学家，Founder of IBM
- 人口普查
- 1880年人口普查1887年才完成，1890年的可能需要1900年完成
- 发明”制表机”，6个月完成1890年人口普查
- 1896年成立”计算制表记录公司”，1924年改名”国际商用机器公司”
- 1935年: IBM制造了IBM601穿孔卡片式计算机，一秒内计算乘法
- ENIAC(Electronic Numeric Integrator and Computer)电子数字积分计算机
- 宾西法尼亚大学摩尔学院，J. Mauchly, J.Eckert
- 1943年~1945年研制。1946年2月14日正式启动
- 17468只电子管，7200个二极管，7000多个电阻器，10000多只电容和6000只继电器；174000W功耗
- 30米长，3米高，30吨重，占地面积170平方米
- 10位数乘法，5000次加法在3/1000秒内完成
- 和Atansasoff有专利之争，到底谁发明了第一台计算机。
- 1941年6月， Mauchly拜访了Atanasoff并参观了已经接近完成的ABC
- 缺点：
- ENIAC还不是存储程序计算机
- 编程是通过手工接线的方式进行
- EDVAC(Electronic Discrete Varable Automatic Computer)电子离散变量计算机
- 1945年3月冯.诺依曼(John von Neumann)同J. Mauchly, J.Eckert在摩尔学院进行两天讨论，指定了存储式计算机的方案。于1945年6月发表——存储程序控制原理
- EDVAC于1952年制造完成
- EDVAC是第一套存储程式计算机
- 是现代计算机的原型和范本
- 巴贝奇差分机(1822年)
- 现代计算机
- 电子管计算机，1946年
- 使用真空管存储数据
- 真空管是一种控制真空中电子流动的电子装置
- 两个电极表示0/1
- 体积大，能耗高，易烧坏
- ENIAC有18000个真空管，第一年运行就替换了19000个
- 只能用0/1进行编程
- 使用真空管存储数据
- 晶体管计算机，20世纪50年代后期
- 贝尔实验室1947年发明晶体管
- 更小，更便宜，功耗低，可靠
- 产生操作系统
- 标准化的硬件资源管理
- 不可移植
- 产生高级编程语言
- Fortran
- Cobol
- 贝尔实验室1947年发明晶体管
- 集成电路计算机，1965年
- 使用集成电路，1958年德州仪器发明
- 操作系统可移植
- C语言
- 超大规模集成电路，20世纪70年代早起
- 超大规模集成电路
- 第一块CPU，1971年Intel 4004
- 2400个晶体管，计算能力与ENIAC相当
- 尺寸：3mmx2mm
- 计算机发展出现瓶颈
- 摩尔定律
- 1965年Intel创始人之一，Moore提出
- 芯片密度每18个月增加1倍
- CPU性能价格比大约18个月翻一番
- 1965年Intel创始人之一，Moore提出
- 电子管计算机，1946年
未来
- 摩尔定律的挑战
- 晶体管大小限制
- 晶体管持续变小很快会达到原子大小，任何纳米管和传统工艺都无法解决这种情况
- 1999年 180nm，2011年 22nm
- 电泄漏
- 随着晶体管体积不断缩小，电泄漏的情形也不断增加
- 散热
- 晶体管密度与速度的增加导致芯片消耗更多的电力产生更多的热能
- Intel CTO Partric Gelsinger
- 2005年一个高端处理器每平方厘米散热量和一个核反应堆外壳持平
- 2010年和火箭助推器相提并论
- 2015年太阳表面温度
- Intel CTO Partric Gelsinger
- 晶体管密度与速度的增加导致芯片消耗更多的电力产生更多的热能
- 晶体管大小限制
- 量子计算机
- 1982年物理学家Richard Feynman提出”利用量子理论进行通用计算”
- 使用现有计算机去模拟计算量子运动计算量太大
- 使用一个已有的可控的量子系统（比如一台量子计算机）去计算另一个感兴趣的量子系统（如宇宙）会很高效
- 量子计算机原理
- 存储方面
- 经典存储：一个晶体管某一个时刻只能表示一个比特，0或1
- 2个比特，某一个时刻，只能存储1对0或1，只能表示1个数
- N个比特，某一个时刻，只能存储2的N次方个数中的某一个
- 量子存储：一个量子比特可以同时保持多种状态
- 2个量子比特，某一个时刻，能同时存储4对0或1，能表示4个数
- N个量子比特，某时刻可以同时存储2的N次方个二进制数
- 经典存储：一个晶体管某一个时刻只能表示一个比特，0或1
- 计算方面
- 经典计算：
- 输入N个二进制数，输出一个结果
- 量子计算
- 输入N个二进制数，输出2的N次方个结果，类似并行计算
- 经典计算：
- 存储方面
- 挑战
- 量子状态不稳定
- 300个量子比特能承载的数据是2的300次方，超过全宇宙的原子数量总和。现实中，需要1000个物理量子比特来保证足够数量的逻辑量子比特
- 量子与外界环境隔离才能保持良好的相干性，但作为计算机，需要观察量子的状态，这回带来与量子的耦合，因此是一对矛盾
- 量子状态不稳定
- 当前成就
- 2009年11月美国NIST研制一台2个量子比特的计算机
- 2个镁离子+2个铍离子被限定在3.5mm长200微米宽的离子井中
- 铍离子用于存储量子比特，镁离子做稳定剂，使用激光脉冲量子逻辑门对量子比特进行操作
- 每个量子逻辑门准确率达到90%以上，但整体准确率仅为79%
- 只有准确率达到99.999%以上才能商用
- 2011年11月IBM组建团队，5年研究计划
- 使用”金属超导性原理”制作量子bit
- 在硅基质上使用铝和铌合成的金属冷却到非常低的温度，他们表现出零电阻
- 构建循环闭合电路，同一时间电流可以流向两个方向，顺时针为1，逆时针为0
- 同年，基于金属超导性原理，加拿大公司生产D-Wave
- 有争议，不是真正意义的量子计算机
- 使用”金属超导性原理”制作量子bit
- 2009年11月美国NIST研制一台2个量子比特的计算机
- 1982年物理学家Richard Feynman提出”利用量子理论进行通用计算”
程序运行原理
思路整理
- 电路可以完成运算，但是通用性没法保证，对于各种运算没法定义统一的电路。
- ENIAC通过插拔电路来实现不同的运算
- 冯诺依曼，提出了新的思路：
- 通过命令来控制计算机
- 命令可以存放在计算机
- 修改命令，功能就改了
- 制造新计算机EDVAC
什么是存储程序计算机
- 冯诺依曼EDVAC:
- 输入输出设备
- 总线
- 运算器
- 控制器
- 存储器
- 工作过程
- 在控制器的指挥下，从存储器上取出指令
- 分析指令，得到计算命令和待操作数
- 从存储器上取出待计算得数放入运算器
- 运算器计算结果
- 输出到存储器或者输出设备
存储
- 寄存器
- CPU内部，用于存放操作数和结果
- 工作速度与CPU运算节拍保持一致
- 一次存取数据大约花费0.x纳秒
- 寄存器与运算部件直接连接，运算部件直接对寄存器进行读写操作
- 寄存器制作成本高，一般CPU芯片中通常只有少数寄存器
- 高速缓存
- 可以在CPU内部，用作数据缓冲区
- 也可以在CPU外部
- 通常分为多级，不同级之间的工作频率不同
- 一般在纳秒内读写一次
- 容量大小不同(nK-nM)
- 内存
- CPU里想放但是放不下的
- 工作频率越来越接近CPU频率，但仍有差距
- RAM
- DRAM：可随机存取，但必须周期性的刷新以保持存储内容
- SDRAM： 工作在CPU外部总线频率上，与CPU的时钟保持同步
- DDR SDRAM:从理论上讲 ，可以把RAM的速度提升一倍，它在始终的上升沿和下降沿都可以读取数据。
- DDR2 电压1.8v，高端频率可达1000MHz
- DDR3 电压1.5v，频率可达2000MHZ 8bit预读
- DDR4 电压1.2v，数据传输速率3.2GT/s
- DRAM：可随机存取，但必须周期性的刷新以保持存储内容
-
外存
- 存储的原理是什么？
原理：
- T1和T2组成一个双稳态触发器，用于保存数据。T3，T4为负载管
- 如A点为高电平，则B点为低电平
- 行选择有效电平时，AB处的数据信息通过门控管T5，T6送至C,D点
- 列选择有效电平时，CD处的数据信息通过门控管T7,T8送至芯片数据引脚I/O
CPU指令的执行
- 问题？
- CPU能够识别正确的程序吗
- 指令是什么？
- 指令如何执行的
- 指令集
- CPU中能够执行指令的集合
- 在CPU设计时就先定义好的
- Intel X86指令集
- ARM 指令集
- 指令
- 表现形式都是二进制码
- 长度随CPU类型不同而不同
- 包含一个或多个字节
- 包含指令码和操作数： ADD 1 2
- CPU工作方式
- 运算器ALU
- 专门进行算术和逻辑运算的电路
- 寄存器
- 累加器AC：暂时存放计算结果
- 状态寄存器PSR：ALU运算结果，系统工作状态信息
- 数据寄存器MAR：数据缓存
- 控制器
- 程序计数器PC：保存下一条指令的地址
- 指令寄存器IR：存放当前正在执行的指令
- 地址寄存器MAR：存放要访问的主存地址
- 运算器ALU
- 指令执行过程:
程序
-结论： - 程序必须要经过编译才转换成CPU所能接手的指令 - 一句程序有可能转换为多句指令 - 在控制器的协调下连续，依次进行相应的指令 - 程序执行过程是在内存中完成的 - 程序在执行过程中，在内存中的不同区域，存放代码和相关数据
语言
语言分类
- 低级语言 之 机器语言
00000001000000001000:将数据装入寄存器
- 低级语言之汇编语言
load 0 a：将数据装入寄存器0mult 0 1：将数据装入寄存器1- …
- 高级语言之C
d = a*b+c
语言历史
- Fortran
- 1954 - 1956 年IBM的 John Backus和他的研究小组开发了FORTRAN(FORmula TRANslation)
- Algol 60
- 1960年1月，Alan J. Perlis发表《算法语言Algol60》（A语言）
- 计算科学里程碑
- BCPL
- 1963年剑桥大学在ALGOL 60的基础上推出了CPL，但是规模较大，难以实现
- 1967年剑桥大学的Martin Richards对CPL进行了简化，推出了BCPL
- C
- 1970年贝尔实验室，Ken Thompson在PDP-7上写操作系统，缺乏语言，于是他简化了BCPL，发明了B语言，同时用B语言写出了UNIX
- 1972-1973，Dennis Ritchie加入，在B语言上完善出C语言，并重写了UNIX
语言构成
- 数据
- 数据类型
- 运算
- 运算符号
- 运算规则
- 控制
- 条件控制语句
- IO
- 输入输出