数字系统逻辑设计 Digital System Logic Design 佟冬 tongdong@pku.edu.cn http://mprc.pku.edu.cn/courses/digital/2017spring
人工智能 - 大数据 - 物联网 - 云计算 - 网络安全 Cloud/Flog 云 / 雾 2
课程介绍 欢迎进入数字世界! 3
4 2016: 人工智能 AI 元年
5 AlphaGo 的硬件基础 : 超计算机 +TPU
6 2016 中国 : 量子卫星 ( 量子通讯 )
7 未来 : 量子计算 通用加速器
异构多核的时代 : 处理器 加速器 FPGA 本课程是 FPGA 硬件设计的基础 8
Apple iphone7 中的 FPGA FPGA 9
为什么学习逻辑设计? 显而易见的原因 本课程是计算机科学和计算机工程课程的一部分 是所有现代计算设备的实现基础 用小部件实现更大的系统 提供计算机如何工作的基础模型 更重要的原因 硬件内在的并行性让我们第一次涉及到并行计算 本课程提供了一个与软件设计相对应的的有趣知识, 有利于进一步大体上理解 计算 Computation 最新的原因 可重构计算 : 基于 FPGA 的加速器计算 10
课程介绍 课程名称 : 数字系统逻辑设计 课程类型 : 本科生限选课 学生专业 : 计算机科学与技术 学时与学分 :48 学时,3 学分 主讲教师 : 佟冬 办公室地址 : 理科 1 号楼 1818 房间 电话 :62765828-802 预备知识 : 数学, 物理, 电路 11
12 上课方式 上课时间 周四 ( 每周 ) 7-9 节 ( 二教 411) 课程网址 学校教学网 http://mprc.pku.edu.cn/courses/digital/2017spring 关于答疑 学校教学网讨论,Email 答疑 考试答疑 : 考试前一天 助教 陈鑫宇 :xinyuc@pku.edu.cn 付天怡 :tianyifu@pku.edu.cn
教材和参考书 主要参考书 Digital Design: a System Approach, by William J. Dally. [ 教学网 pdf] 现代逻辑设计 Contemporary Logic Design, by R. H. Katz and G. Borriello, 罗嵘等译, 第二版, 电子工业出版社 ( 中文版 ) 白中英, 数字逻辑与数字系统, 第四版 立体化教材, 科学出版社,2007 Digital Design Principles and Practices, by J. F. Wakerly, 第三版, 高等教育出版社 ( 影印版 ) 13
课程考核 平时成绩 (15%) 课程参与情况 5% 书面作业 10% 期中考试 (20%)4 月 27 日 FPGA 设计大作业 (15%) 期末考试 (50%)6 月 22 日 相关实验类课程 数字逻辑实验 : 周三 周五 周日晚 14
15 课程结构 概述 基础理论知识 数字系统和编码 布尔代数基础 数字电路基础 数字电路分析与设计 组合电路分析与设计 同步时序电路分析与设计 可编程逻辑器件和设计软件实践 原理图 Verilog 设计 Xilinx BASYS2 开发板实践
学习收获 掌握数字电路设计的基础理论 了解实现数字电路的工艺器件基本原理 掌握数字电路的分析方法 重点掌握数字电路设计方法和实现方法 培养对计算机硬件设计的兴趣 了解数字系统设计的现状 掌握用可编程器件实现数字电路的方法 学习简单的并行的思维方式 16
17 Xilinx BASYS2 实验板
最终课程项目 : 简单计算器 十进制输入 十进制输出 加法 减法 除法 原理图和 Verilog 设计 输入 FPGA 输出 18
人是如何计算的? 简单的模型? 感知 : 眼 耳等 判断 命令 : 行为 记忆 大脑 19
如何做出一个能计算的设备? 模拟数据 人的计算方法 模拟数据? 数据? 计算设备 数据? 20
绪论 佟冬 tongdong@mprc.pku.edu.cn http://mprc.pku.edu.cn/courses/digital/2017spring
一个简单的模型 传感器 sensors 模拟世界 A/D 数字世界 D/A 执行器 actuators 22
模拟和数字 (Analog vs. Digital) 模拟量 时间上和量上都是连续的 缺点 : 很难度量, 容易受噪声的干扰, 难以保存 优点 : 用精确的值表示事物 真实的世界是模拟的! 数字量 时间上和量上都是离散的 ( 非连续的 ) 优点 : 更多的灵活性, 更快 更精确 更复杂的计算 容易实现存储设备, 误差监测和修正, 容易最小化 可避免噪声累积干扰 二进制编码 23
模拟信号和数字信号之间的转换 模 / 数转换 (A/D) 采样 -> 量化 -> 编码 数字序列 数 / 模转换 (D/A) 模拟低通滤波器 近似的模拟信号 失真 0000000000000000 0111111100000111 1000100011111000 1011011010001011 (a) 模拟形式 (b) 采样后的模拟形式 (c) 数字形式 24
数字系统设计 数字系统 以数字的形式对信息进行存储 处理和传输的系统 什么是设计? 给定一个问题的表述, 从可用功能部件集合中从优选择, 得到一种解决问题的办法 分而治之的方法 工具 方法学 满足一定的约束 (Constraint) 性能, 价格, 质量, 美观等等 25
逻辑设计 (Logic Design) 决定数字逻辑元件的集合, 执行一个指定的控制过程 数据加工或者通信功能, 并决定逻辑元件间的互连 选择什么逻辑元件 实现技术 固定功能的芯片器件 芯片内部的晶体管 可编程器件 FPGA 设计需要优化或改造以满足设计约束 性能 面积 功耗 成本 26
现代逻辑设计 现代逻辑设计的特点 设计复杂 要求很短的开发时间 数字硬件成本很低, 性能却很高 现代逻辑设计的趋势 用软件工具自动生成数字电路 (EDA ESL) 采用已经设计好的数字元件 (IP) 更加关注规格说明书的制作 (Specification) 硬件和软件协同设计 27
计算 : 抽象和实现 (0 1 = 与或非 ) 本课程是关于物理上如何实现计算, 采用物理器件并用电压来表示逻辑值 计算的基本单元 : 表示 : 连线上的 0 和 "1" 赋值 :x = y 数据操作 :x + y 5 控制 : 顺序结构 : 条件结构 : 循环结构 : A; B; C if x == 1 then y for ( i = 1 ; i == 10, i++) 过程结构 : A; proc(...); B; 本课程将学习这些如何用硬件实现并组成计算设备 28
数据的数字表示 二进制数 基数 :r = 2 数字集 :(0, 1) (1010110000110100) 2 bit 比特 29
选择二进制数的数学意义 数的表示能力 n 位 r 进制数共有 N =r n 个不同的数 选择二进制的原因 两个状态的材料最容易获得 数学的证明 表示 n 位 r 进制所用的材料与 nr 成正比 log n nr N log N log r r log( r log log N r n ) n log r Cr log N ( ) log r r e 0 2.71828 30
编码 (Code) 二进制 1824, 路易 布莱尔 Louis Braille 盲文, 国际通称 布莱尔 (braille) 31
摩斯码 二进制 1844 Samuel Morse 电报 编码和解码 航海信号灯的开和关表示信息 哈夫曼编码 : 对越频繁出现的字符采用越短的码 32
用数字信号表示信息 二值信息 : 灯的开 / 关 :1/0 集合的元素 : 000 白色 001 红色 010 蓝色 011 黄色 100 紫色 101 桔色 110 绿色 111 黑色 连续量 : 000 68 001 70 010 72 011 74 100 76 101 78 110 80 111 82 0000000 68 0000001 70 0000011 72 0000111 74 0001111 76 0011111 78 0111111 80 1111111 82 33
计算机编码 编码 (Code) 利用给定符号集合对信息的一种系统的 标准化的表示 采用二进制编码 : N 2 n,n=log2(n) 编码的可计算性 计算机中的编码 数字编码 字符编码 检错码和纠错码 其他编码 ( 汉字 多媒体 ) 如何用二进制表示年 月 日 小时 分钟 秒? 34
二进制的信号表示 电信号和逻辑值 在电路中, 用电压的高低来表示逻辑值 高电压 H 不稳定 低电压 L 电信号 V max V H V L V min 正逻辑 1( 真 ) 0( 假 ) 逻辑值 负逻辑 0( 假 ) 1( 真 ) 一个信号被置为逻辑 1 称为有效的或者真 一个信号被清为逻辑 0 称为无效的或者假 高有效信号 ( 正逻辑 ) 和低有效信号 ( 负逻辑 ) 信号的极性 (Polarity) 表示信号是高有效或是低有效 35
数字计算机的数学基础 1850s, George Boole 将逻辑表述映射到符号 采用数学的方法处理逻辑推理 An investigation into the Laws of Thought 1938s, Claude Elwood Shannon 将布尔代数和硬件开关相联系 第一次提出 bit( 比特 ) 表示信息 A Symbolic Analysis of Relay and Switching Circuits(1938) Master thesis in MIT. 1941 香农加入 AT&T Bell 实验室 The mathematical theory of communication, 1948 36
如何做一个能计算的设备? 模拟数据 人的计算方法 布尔代数 模拟数据 0101010 0,1? 信号电压 二进制数据 开关电路 计算设备 电压高低 二进制数据 37
逻辑门符号 通行的组合逻辑系统采用被称为 逻辑门 的标准符合表示 Buffer, NOT A Z AND, NAND A B Z OR, NOR A B Z 38
开关 : 数字系统物理实现的基本单元 简单电路的实现 A Z 关开关 ( 如果 A 是 1 ) 电灯泡亮 A Z 打开开关 ( 如果 A 是 0 ) 电灯泡不亮 Z A 39
开关 ( 续 ) 用开关构造更复杂的功能 ( 布尔函数 ): AND A B Z A and B A OR Z A or B B 40
布尔代数和开关电路 : 与非门 (NAND) a b f NAND (a, b) = ab A B Y 0 01 0 10 1 11 L LH L HL H HH 布尔代数 1 1 (a) 0 H H (b) L 逻辑门 A B Y A B Y A B & Y (c) 高 (d) A (e) B 高 开关电路 A Z A Z B B 41 低 低
数字设计的表示法 物理器件 Physical devices (transistors, relays) 开关 Switches 真值表 Truth tables 布尔代数 Boolean algebra 门 Gates 波形图 Waveform 有穷状态行为 Finite state behavior 寄存器传输行为 Register-transfer behavior 并发抽象描述 Concurrent abstract specification 42
组合电路和时序电路 数字系统的简单模型是有输入和输出的部件 输入 系统 输出 43
人是如何计算的? 简单的模型? 感知 : 眼 耳等 判断 命令 : 行为 记忆 大脑 44
数字逻辑电路 简单的模型 输入信号 组合电路 输出信号 存储元件 时序电路 45
组合电路和时序电路 组合电路 输出值是输入值的逻辑函数 输入值变化后一段时间后出现新的输出值 电路没有记忆功能 电路中没有循环反馈 (feedback loop) 和时钟 时序电路 输出值是输入值和电路状态的函数 输入变化后新的输出出现在下一个时钟事件或者其他事件发生 电路有循环反馈, 存在存储元件 46
组合电路举例 日历子系统, 计算每个月的天数 用来在显示器上显示 输入 : 月份 闰年标志 输出 : 天数 47
软件的实现 integer number_of_days ( month, leap_year_flag) { } switch (month) { } case 1: return (31); case 2: if (leap_year_flag == 1) then return (29) else return (28); case 3: return (31);... case 12: return (31); default: return (0); 48
组合数字系统硬件实现 问题 : 输入输出的数量? 月的二进制表示? 4 个输出线 电路行为 : 组合电路 真值表 month leap d28 d29 d30 d31 month leap d28 d29 d30 d31 0000 0001 0 0 0 1 0010 0 1 0 0 0 0010 1 0 1 0 0 0011 0 0 0 1 0100 0 0 1 0 0101 0 0 0 1 0110 0 0 1 0 0111 0 0 0 1 1000 0 0 0 1 1001 0 0 1 0 1010 0 0 0 1 1011 0 0 1 0 1100 0 0 0 1 1101 111 49
组合电路实现 本课程讲学习如何设计? 50
时序电路举例 组合门锁 : 连续输入 3 个正确的密码, 才能打开门 ; 只要有一个密码不对, 门锁将复位, 不接受任何密码 ; 知道特殊的复位操作才能打开门 输入 : 输入值序列, 复位信号 reset 输出 : 门开 / 关 存储 : 必须记住密码组合 51
软件实现 integer combination_lock ( ) { integer v1, v2, v3; integer error = 0; static integer c[3] = 3, 4, 2; while (!new_value( )); v1 = read_value( ); if (v1!= c[1]) then error = 1; while (!new_value( )); v2 = read_value( ); if (v2!= c[2]) then error = 1; while (!new_value( )); v3 = read_value( ); if (v2!= c[3]) then error = 1; 52 } if (error == 1) then return(0); else return (1);
实现 : 时序电路实现 new value reset clock state open/closed 53
实现 : 时序电路实现 closed ERR reset closed S1 C1=value & new C1!=value & new closed S2 C2=value & new C2!=value & new S3 closed C3=value & new C3!=value & new open OPEN not new not new not new 54
实现 : 时序电路实现 数据通路 :Datapath 存储预设密码 比较器 控制器 :Controller 有穷状态机控制 ; 状态 控制数据通路 value comparator 数据通路 C1 C2 C3 multiplexer mux control new 控制器 equal controller reset clock equal open/closed 55
数字系统 数字系统 数据通路 控制器 代码寄存器 算逻部件 ALU 多选器 状态寄存器 译码器 寄存器 组合逻辑 开关网络 56
Verilog HDL 硬件描述语言 Modules: 说明输入, 输出, 双向和内部信号 连续赋值 : 一个门的输出任何时刻都是输入的函数结果 ( 不需要调用 ) 传播延迟 : 输入影响输出的时间和延迟的概念 构成 Composition: 通过线将模块连接在一起 层次化 : 模块分解成一些功能模块 57
Verilog HDL 和编程语言的关系 程序结构 Program Structure 多次例化相同类型的模块 通过原理图表明模块之间的连接关系 模块的层次化结构 赋值 Assignment 连续赋值 continuous assignment ( 逻辑始终计算 ) 传播延迟 propagation delay ( 计算耗费时间 ) 信号时序非常重要 ( 计算的结果何时产生效果 ) 数据结构 Data structures 位宽显式的拼写出来, 不支持动态结构 不支持指针 并行性 Parallelism 硬件是自然地并行运行 ( 必须支持多线程 ) 赋值并行的发生 ( 不仅仅是串行执行的 ) 58
日历子系统组合电路的 Verilog 实现 59 确定一个月的天数 ( 控制钟表的显示 ) module num_of_days(month, leap_f, days) input [3:0] month; input leap_f; output [4:0] days always @(month, leap_f) begin case (month) 4 b0001: days = 31; 4 b0010: days = 28 + leap_f; default: days = 0; endcase end endmodule
当前数字设计的趋势 越来越复杂的设计 性能越来越高, 能效性是关键 越来越短的推向市场时间 (Time to Market) 越来越低的价格 大量使用计算机辅助设计工具 多层次的设计描述 大量使用复用技术 IP(Intellectual Property) 验证技术成为关键 (60%-80% 的时间 ) 60
课程重点 在设计层次上以门级 (Gate Level) 为主 是一门关于逻辑门和连接线的艺术 A/D -> 数字处理和存储 -> D/A 数字处理 原理 方法 ( 分析 设计和优化 ) 实现 ( 器件 ) 掌握数字设计中的 最基础的知识 最基本的方法 Verilog 和 FPGA 设计 61
计算的简史 ( 硬件部分 ) 从人脑到电脑
63 人是如何计算的? 计数 count 计算 calculate 通过数学过程来判定 to determine by mathematical processes 计算器 Calculator, 可以执行数学计算的电子设备 an electronic device for performing mathematical calculations 计算机 computer 计算的人 一种可以存储 查询和处理数据的可编程电子设备, a programmable usually electronic device that can store, retrieve, and process data
计算的历史 计算机历史只有 70 多年? 不对! 数字电子计算机的历史只有 70 多年! 计算机革命发生在过去的 70 多年中而且还正在进行 计算和计算机的历史源远流长 把握历史 时间 地点 人物 重要事件 计算的历史伴随着计算机的发展和器件的发展 64
数字的出现 数字的出现 数字在各个古代文明中都独立的存在 数字都以十进制数为基础 阿拉伯数字 Digit 的解释 人的手指或脚趾 指宽 阿拉伯数字符号从 0 到 9 中的任意一个 用在计算系统中的符号 65
早期的计算工具 计算的出现 计算的需求 原始的计算方法 最早的 计算机 算盘 ( 按位记数法 ) 1612-1614 John Napier 发明对数 数字和带数字的木条进行计算 1633 Oughtred 发明计算尺 66
机械计算机 1642-1643 Blaise Pascal 加法器 1673 Leibniz 四则运算计算器 19 世纪 Charles Babbage 齿轮 差分机 (difference engine) 构思了一台由存储装置和算术装置组成的分析机 (Analytical engine) 由于工艺水平的限制当时没有能够实现 第一台计算机 67
68 最早的计算器公元前 80-60 年
穿孔卡片和程序 1804 Joseph Jacquard 穿孔卡片式织布机 1815-52 Ada Byron aka Lady Lovelace 概念性的程序 指令存储 实用穿孔卡片 打印的能力 Computer 词的出现 到 1940 前 Computer 指雇佣来负责计算数字的人 69
齿轮 + 穿孔卡片 机械计算器 1886 Burroughs 纪录式加法器 1889 Hollerith 穿孔卡片系统 1911, CTR 公司 1924, IBM 公司 70
布尔代数和开关电路 : 与非门 (NAND) a b f NAND (a, b) = ab A B Y 0 01 0 10 1 11 L LH L HL H HH 布尔代数 1 1 (a) 0 H H (b) L 逻辑门 A B Y A B Y A B & Y (c) 高 (d) A (e) B 高 开关电路 A Z A Z B B 71 低 低
电磁时代 : 继电器 1835 Joseph Henry 继电器 (relay) 1876 Alexander Bell 电话 AT&T 公司 电话开关网络 72
机电计算机 Konrad Zuse s Z-1 (1935) 1937,George Slibitz of Bell Laboratory Model-K 使用继电器设计自动计算器 1944, IBM/Harvard Mark-I 73
ABC- 第一台数字电子计算机 1942 John Atanasoff Clifford Berry 爱荷华州立学院 (Iowa State College) ABC: Atanasoff-Berry Computer 二进制 280 真空管 315 公斤 74
第一代数字电子计算机 - 真空管 1904 John A Fleming diode vacuum tube 1906 Lee de Forest threeelectrode vacuum tube 1943 Colossus Mark I 1946 第一台通用的数字电子计算机 ENIAC 十进制 18000 个真空管 ( 电子管 ) Presper Eckert John Mauchly 75
第二代数字电子计算机 - 晶体管 1947.12.23 Bell Labs John Bardeen Walter Brattain William Shockley 发明晶体管 (Transistor) 1956 年诺贝尔物理学奖 1951 William Shockley invents the junction transistor( 结型晶体管 ). 1954 Texas Instruments silicon transistor 76
第三代数字电子计算机 - 集成电路 集成电路 (Integrated Circuit, IC) 1958, 德州仪器 (TI) Jack Kilby 用线连接 5 个元件 2000 年诺贝尔物理学奖 Robert Noyce, 仙童 (Fairchild) 1959, 德州仪器 (TI),Jack Kilby Flip-flop IC 双极型晶体管 (TTL, ECL) 77
第三代数字电子计算机 ( 续 ) 1961, 仙童 第一个单片平面集成电路,set/reset flip-flop 1962, 仙童 NPN 晶体管 1969, 仙童 MOS 管 双极性晶体管集成电路 (TTL, ECL) SSI(Small Scale IC) and MSI(Medium Scale IC) 1963 7-bit ASCII 78
第四代计算机 - 大规模集成电路 微处理器 集成电路工艺的发展 大规模集成电路 (Large Scale IC, LSI) 超大规模集成电路 (Very Large Scale IC, VLSI) 1971,Intel, 微处理器,4004 Ted Hoff 2300 晶体管, 3x4 mm 2 Intel 8008, 8080, Z-80, 68000 1979,Carver Mead and Lynn Conway An Introduction to VLSI systems 79
Moore 定律 Dr. Gordon E. Moore is Chairman Emeritus of Intel Corporation. He co-founded Intel in 1968, serving initially as Executive Vice President. He became President and Chief Executive Officer in 1975 and held that post until being elected Chairman and Chief Executive Officer in 1979. He remained CEO until 1987 and served as Chairman until being named Chairman Emeritus in 1997. The number of transistors per integrated circuit would double every 18 month. 这个论断是在第一块平面集成电路产生 4 年以后的 1965 年做出的 当时认为这个发展趋势将持续到 1975 年 事实上, 这个发展规律在目前仍是正确的 按目前发展趋势, 这个规律仍将有效至少 10 年 80
81 Moore s law 2015
82
83
84 集成电路工艺发展 ( 来源 :IBM)
85 集成电路工艺发展 ( 来源 :IBM)
86 集成电路的发展
87 集成电路的发展 (2015): 规模
88 集成电路的发展 (2016): 频率
Intel Xeon E5-2600 v3 22nm 18-Core 16 双线程 Haswell 核 45MB L3 缓存 4 DDR4 通道 5.56B 晶体管 22nm CMOS 55-165W 1.6~3.8GHz 89
集成电路工艺的新进展 Intel 3D tri-gate CMOS 3D-stack Chip 90
集成电路工艺最新进展 2010 年 2 月 自然纳米技术 91
纳电子 Nanoelectronic 碳纳米管 Carbon nanocube 碳纳米线 Carbon nanowire 92
石墨烯 Graphene 2010 年诺贝尔物理奖 A. K. Geim K. S. Novoselov Electric field effect in atomically thin carbon films, Science, Oct.22, 2004. 93
94 忆组器 Memristor
下一代计算机? 量子计算机 分子计算机 生物计算机 仿生计算机 类脑计算机 脑机合作计算机 95
设计方法和工具的发展 手工 物理层设计 CAD 门级和开关级 EDA 硬件描述语言 (Verilog and VHDL) 综合工具 验证工具 布局布线工具 ESL 高级描述语言 (SystemC, C++) 下一代设计方法 处理器生成器 (Generator)? 96
课程小结 数字系统 对数字处理和存储的系统 模拟世界 模拟量 A/D 数字世界? D/A 97