https://www.youtube.com/playlist?list=PL0j-r-omG7i0-mnsxN5T4UcVS1Di0isqf
计算机体系结构主要包括5个层级:
物理层级:硬件电路。
机器语言层级:计算机可以直接执行的机器指令。
汇编语言层级:低级语言,可以对应每个机器指令。
高级语言层级:如C语言,需要编译成机器指令才能运行。
操作系统层级:管理硬件资源和软件,提供接口供应用程序使用。
最早的计算机是机械式计算机,使用机械装置进行计算。
1940年, 第一台电子计算机ENIAC问世,使用真空管进行计算。
1947年,发明了个 transistor,进一步推动计算机发展。
1958年,发明了集成电路,包含多个耦合在一起的电路,从而落实了微电子计算机元器件。
1971年,Intel公司推出了世界上第一款4位处理器。
1980年代,个人计算机面世。
1990年代中期,互联网兴起。技术不断发展,计算机功能不断强大。
计算机运行的基本原理是:1) 输入指令与数据 2) 处理单元执行指令 3) 输出结果。各个处理单元按顺序完成任务,实现计算机对问题求解的处理能力。
计算机体系结构设计的目标是:高性能,低功耗,低成本。 striking a balance between these goals is an ongoing challenge。
计算机内部存储和处理的数据以数字形式表示。数字表示可以将真实世界中的任何事物转化为计算机可以识别和处理的形式。
将模拟信号转换为数字信号需要采样和量化两个步骤:
采样是定期询问模拟信号当前的值。音频CD采样频率为每秒44,100次。
量化把采样值量化为有限的数字量级。例如16位数字可以表示0-65535的范围内65,536个量级。采样值近似到最近的量级进行表示。
7位ASCII码可以表示26个字母和标点符号。但无法涵盖世界各国文字。
Unicode标准采用8/16/32位编码,可以表示所有国家文字及表情符号等符号。
通过确定比特(bit)个数,二进制可以表示任何事物。如果需要表示的物件数量为N,则需要的bit数为log2(N)的ceiling值。
例如26个字母需要log2(26)=4.something≈5bit,所以采用5bit编码每个字母。计算机内所有数据都可以用二进制表示。
计算机内部存储和处理的数据默认为二进制数。但是我们每个日常使用的数字系统有:
十进制数:0-9组成,我们日常使用。
八进制数:0-7组成,计算机硬件使用。
十六进制数:0-9及A-F组成,计算机软件开发使用。
因此需要数字之间进行转换:
十进制到二进制:使用二进制基数重复除法操作。
二进制到十进制:将每个二进制位数与其值(2的0次方、1次方等)相乘后相加。
八进制和十六进制也利用对应的基数重复除法或权值相乘运算实现转换。
计算机使用二进制补码表示整数,可以表示正负数:
正数相同表示法,最高位为0。
负数求原数字的反码后加1,最高位为1。
这种表示方案简化了计算机内部的算术运算处理。
当运算产生的结果超出表示范围时,会导致数值溢出。如8位二进制只能表现-128到127,128的计算会溢出。
使用最高位表示数值正负,其余位表示数值的绝对值。需要额外一位来区分0。
补码表示通过对负数取反加1简化了计算器件的设计,减少了冗余的0表示。
反码是将正数不变,负数取反。但无法直接计算两个负数之和。
相加:直接相加二进制数。
相减:将被减数视为正数, subtractor取反相加。
乘除:直接进行。
补码表示法同时简化了计算过程,成为计算机中主流的整数表示方法。
两补数是计算机使用的主要整数表示方法。
正数不变表示。
负数取其反码后加1。
这种方法简化了数字的加减运算。
有些场景需要表示更广范围的数值,但位数有限。
可以使用高位数来存储一个偏移量,实际值是存储值加上偏移量。
计算机使用二进制存储数值。
需要转换 zwischen不同进制。
两补数表示整数最为便利,可以表示正负数。
偏移量可以扩大表示范围。
字长决定了能表示的最大最小值。
溢出需要小心处理。
数值表示是计算机系统的基础,理解其原理对学习计算机很有帮助。这套知识点也将在后续课程中反复出现。
C语言是一种通用编程语言,开发历史几十年,影响很深远。
低级语言,跟底层系统交互近。
没有自动 memory management,需开发人员手动申请释放内存。
结构简单,语法像自然语言。
操作符清晰,类似算法语言。
运行效率高,适合系统程序和底层应用开发。
操作系统开发:大多数主流操作系统都是用C语言写的。
设备驱动: comunication with hardware更方便。
系统程序:编译器、调试器等。
高性能应用:数据库、游戏等。
Web开发:C是后端语言的基础。
1970s中期K&R论文描述了C语言。
1989年发布首个ANSI标准C语言。
1999年发布C99标准加入新特性。
2011年C11标准。ISO和IEC都认证C语言标准。
编译语言:源代码需要通过编译器转换成机器语言二进制代码再运行。C语言属于编译语言。
解释语言:源代码通过解释器语句一次解释并直接运行,无需提前编译。python属于解释语言。
编译后产生的二进制机器码通常运行速度更快。
解释语言通常编写和调试更方便,无需重新编译就可以运行代码。
编译语言产生的代码体积更小,解释语言需要随代码一起运行解释器。
预处理(.i):处理头文件引用和宏定义等。
编译(.s):将预处理代码转换成汇编语言代码。
汇编(.o):将汇编代码转换成目标文件,包含机器指令等。
链接:将多个目标文件链接成可执行文件。
C语言属于先编译后运行的典型编译语言,可以生成高效的二进制机器码运行。
C语言历史更久,语法结构更简单。
Java内存通过垃圾收集器自动管理,C语言需手动释放内存。
C标准库较小,操作系统交互力度大。Java标准库丰富,跨平台性好。
C语言效率高, closer to hardware,常用于系统编程。Java通常开发桌面和网络应用。
源文件以.c为后缀名。
以#include引入头文件。
内置数据类型包括整数、浮点数和字符。
varible定义用数据类型和变量名。
使用语句结束符”;”结束语句。
内置操作符包括算术、关系、逻辑、赋值等。
函数定义使用格式:返回类型 函数名(参数类型 参数名)
主函数为入口点开始执行。
C语法简单明了,各元素都以英文关键字出现,利于阅读与学习。
源文件以.c结尾,使用#include包含头文件。
变量定义使用数据类型和名称,如int a;
内置的数据类型包括整型、浮点型和字符型。
语句使用;结束,如printf(“hello”);
条件控制语句有if、switch等。
循环语句有while、for等。
函数使用格式:返回类型 函数名(参数列表){函数体}
数组使用[]访问元素,如array[i]
指针使用访问变量地址,如ptr
预处理指令以#开头,如#define
C语法结构清晰,各语句元素使用英文关键字,便于阅读和学习。语法规则严谨,提高了程序质量。
C语言提供了一些常用函数的标准实现,如输入输出函数、字符串函数、数学函数等,放在头文件中使用。
掌握C语法基础可以进行各种系统编程和应用开发。
指针使用不当可能导致许多难找的 bug:
使用未初始化的指针访问变量
指针越界访问非法内存
指针运算结果指向非法内存
引用已释放内存区
将指针值与地址混用
指针运算结果失真
指针变量用来存储其他变量的内存地址。
指针类型由符号”&”声明,如int *p;
使用符号”“访问指针指向的变量,如p = 10;
指针赋值可以是变量名或”&”变量名求地址运算。
指针本身也是一个变量, occupies some storage。
结合C语法,正确使用指针可以简化代码和提高效率,但也易导致难查的 bug,需要特别小心。
通过指针传参而非值拷贝可以避免重复复制数据
指针使函数可以修改调用者变量
指针访问数组元素比下标更高效
字符串通过指针实现,避免每个字符都保存值
交换两个整数值:传入地址不用值复制
求数组和:指针迭代计算更快
复制字符串:用指针迭代移动更简洁
函数接收字符数组:指向首元素指针更高效
动态内存:指针操作比值复制更高效管理内存
正确使用指针可以有效提高程序性能和简化编码。但也需谨记指针错误易难解。
数组使用[]访问元素,如array[i]。
数组名表示首元素内存地址,即指针常量。
数组元素存储连续空间,切整数倍增加、访问高效。
编译时或运行时可指定数组大小。
大小一经指定后固定不可改变。
数组各元素类型必须相同。
指针访问数组即*(array + i)。
求数组各元素之和、平均值等统计计算。
实现汇编指令寻址模式如index addressing。
字符串以\0结尾的字符数组实现。
数组存储结构简单高效,是数据结构中的基本概念。掌握数组使用方法对程序开发很重要。
定义两个简单函数x10和x2,分别实现整数乘10和乘2操作。
mutate_map()函数使用函数指针,将传入的变换函数应用于数组每个元素,直接在数组上修改元素值。
使用函数指针类型定义如int (*fp)(int),指定fp指针指向的函数返回int,并接收int参数。
建立包含3.14三个数字的数组
传入x10函数指针调用mutate_map(),数组元素均乘10
传入x2函数指针调用mutate_map(),数组元素均乘2
函数指针可以实现更通用的程序,不仅处理数据,还可以接收和使用其他函数。掌握函数指针的定义和使用方法。
C语言提供malloc和calloc函数从堆内存中动态分配内存。
返回值是void*类型,需要强制转换为正确类型使用。
使用free函数释放之前用malloc分配的内存,防止内存泄漏。
分配的内存大小需要 developers 计算并传入。可用sizeof运算符计算类型大小。
通过malloc分配一整块连续内存空间,实现动态大小数组存储。
使用指针操作动态内存,需要正确初始化指针,避免野指针错误。
动态内存管理解决了固定大小限制,但开发者需要谨记申请与释放,防止内存泄漏。它提高了程序的灵活性。
指针变量用来存储其他变量(pointy)的内存地址。
初始化时指针不指向任何变量。
使用malloc从堆中分配内存给pointy。
指针变量指向pointy的内存地址。
*操作符用于访问指针指向的pointy。
设置pointy的值时需要*操作符。
指针和pointy是独立的
指针 dereferencing使用*访问pointy
指针赋值实现指针共享同一个pointy
通过例子生动展示了指针的概念和使用方法。掌握了这三个规则可以正确操作指针。
链表由节点组成,每个节点包含数据和指向下一个节点的指针。
使用结构体定义节点结构,包含数据和指针成员。
使用malloc分配新节点,初始化节点数据和指针。
头节点next指针指向第一个节点。
分配新节点,设置数据值。
修改当前最后一个节点的next指针,指向新节点。
返回链表头节点指针。
定义节点结构体和链表typedef。
new_list函数返回初始空链表。
add_string函数向链表添加字符串节点。
指针操作简洁地实现了链表的创建和节点添加,可以通过此例理解C语言链表的基本原理和使用方法。
C程序使用三种内存区域:
栈存储:函数参数、变量,在进入/离开函数时自动分配/释放。
静态存储:全局变量和静态局部变量,程序运行期间保留。
堆存储:使用malloc/free动态分配,需要手动管理内存。
静态/本地指针:指向静态/栈内存。
动态指针:指向malloc分配的堆内存。
指针可以在不同区域之间进行转换。
不同内存区域物理上不一定连续,但通过指针逻辑上可以相连。
自动管理栈内存。
灵活管理堆内存。
避免变量访问冲突。
掌握C语言内存管理机制,可以更好使用指针和管理内存。
C语言程序中有三种内存区域:
静态存储区(static storage):用于保存全局变量和静态局部变量。程序运行期间不会改变。由操作系统管理。
栈(stack):用于保存函数调用时所需的本地变量、参数值等临时数据。每次函数调用时,栈向上的增长,函数返回时对栈进行缩减。由操作系统自动管理。
堆(heap):用于动态分配内存。通过malloc和free进行内存的动态申请和释放。需要程序员自己管理。
malloc函数申请内存后,返回的内存区域是连续的。但整个堆内存不一定是连续的,可能因先前内存释放而产生片断。
free函数释放内存后,会将相邻的已释放内存区域合并,以减少内存碎片。
malloc和free操作会对双向循环链表结构的空闲内存块列表进行修改,以追踪使用和可用内存。
常见的内存块回收算法有:
Best fit:搜索整个空闲内存块列表,选择尺寸最接近要求的块。
First fit:从列表开头开始搜索第一个尺寸满足要求的块。
Next fit:记录上次搜索位置,下次从该位置开始搜索。
这些算法在不同应用场景下,优劣不同。需要根据实际情况选择合适的算法。
程序员需要关注请求的内存大小,以及内存碎片问题带来的影响。但内存管理的核心运行机制与细节,是由操作系统在内存管理模组自动完成的。
C语言不检查数组下标和指针越界,容易导致错误:
使用未初始化指针
指针越界
野指针
多次free或忘记free
这些错误可能导致程序崩溃或非预期行为。
使用调试器查看内存值
添加检查代码
打印调试日志
启用内存泄漏检测
使用静态分析工具检查
这可以帮助定位内存错误发生的具体位置。
避免直接操作指针
添加边界检查
初始化所有指针
及时释放内存
禁止野指针访问
保守的内存管理习惯可以有效防范常见内存错误。
正确理解C内存管理机制,并运用合适的 debug技巧,有助于解决内存 bug。
浮点数使用单精度(32位)或双精度(64位)二进制格式表示。
格式包括:符号位、指数字段、尾数字段。能表示更广泛的数值范围。
但浮点数是近似值,会引入四舍五入误差。
加减乘除遵循FPU单指令执行的浮点数算法。
舍入误差会随运算accumulating。
精度损失导致某些运算结果非预期。
浮点数应避免用于条件判断。
RISC-V是开源ISA,支持32位和64位指令集。
支持浮点单指令的RISC-V F扩展。
RV32I基础指令集简洁高效完成各类计算任务。
RV64G指令集支持64位寻址更大内存空间。
理解浮点数表示和相关运算问题,以及RISC-V体系结构特点,有利于后续学习计算机组成原理知识。
浮点数使用单双 precision IEEE754 标准表示法:
指数表示对尾数的乘法偏移量
浮点数值 = (-1)^s × 2^e × 1.f
整数也可以用浮点数精确表示
浮点数近似存储有限位数值
四舍五入误差会随运算累加
精度损失导致结果与预期不同
浮点数不要用于判断相等
正负无穷:指数最大
NaN:非数字值
零:指数和尾数都为0
正确理解浮点数表示规则可以帮助解决因精度问题导致的错误。
正无穷大:指数最大,尾数非零
负无穷大:指数最大,带符号位
NaN:非数值,指数最大,尾数非零
正零:指数和尾数都为0
负零:-0,与正零计算结果相同
与任何数字计算结果都是无穷大
与自身计算结果还是无穷大
与任何数字计算结果都是NaN
与自身计算结果还是NaN
NaN不等于NaN
与任何数字计算结果都是该数字
与自身结果是零
正零等于负零
特殊浮点数可以表示特殊场景,正确处理可以避免错误。
将十进制数转换为浮点数要分解表示式,确定符号、指数和有效数字。
将浮点数转换为十进制数要根据指数将有效数字移动确定位置,然后叠加各位值。
无穷大与任何运算结果都为无穷大。
NaN与任何运算都为NaN,NaN不等于NaN。
正负零计算结果相同。
小数循环分式可以用无限小数表示。
根据各位权重求和确定浮点表示。
可以将有效数字理解为分数或编号位置。
配合指数移动考察其对位权重的贡献。
这个视频通过详细例子解析了浮点数与其他类型转换的方法,帮助深入理解其表示和计算规则。
理解浮点数的物理表示机制,可以有效识别和处理精度相关bug,是编程语言设计和应用的重要理论基础。
RISC-V是开源架构,支持32位RV32I和64位RV64G指令集
RV32I包含有限数量基本定长指令, RV64G支持64位寻址空间
指令为固定32位,分为操作码和操作数
操作码7位确定操作,后25位为操作数或立即数
x1-x31为通用寄存器
x0常为0,不可以写但可以读
每个寄存器均32/64位宽
R类型指令 conducted寄存器操作
I类型指令使用立即数
S类型指令执行存储操作
B类型指令为条件分支
RISC-V体系结构简洁高效,其Assembly语言具有代表性。掌握后有助于学习汇编编程。
使用注释标识代码,以#号开头。RISC-V通过32个通用寄存器快速访问核心资源,是其指令设计的关键元素。深入了解寄存器机制对学习汇编语言很重要。
地址、操作数间空格分隔,操作数顺序固定
ADD指令格式:add 操作目的寄存器,操作源寄存器1,操作源寄存器2
SUB指令格式:sub 操作目的寄存器,操作源寄存器1,操作源寄存器2
相加操作源寄存器1和源寄存器2的值,结果存入目的寄存器
相当于C语言 a=b+c
从操作源寄存器1中减去源寄存器2的值,结果存入目的寄存器
相当于C语言 a=b-c
通过临时寄存器连接多条指令实现复杂运算
顺序执行,中间结果保存到临时寄存器
RISC-V添加和减运算指令格式规律简单,通过多条指令实现高级语言一条语句。
立即数是机器语言常用的数值常量
RISC-V用ADDi指令支持添加立即数
ADDi源目的寄存器,源寄存器,立即数值
格式与ADD指令相似,最后一个操作数为立即数
X0寄存器内容固定为0,但无法改写
使用X0时结果不会改变,如ADDi X0,X1,X2仅移动X1内容到X0
RISC-V通过ADDi指令支持新增常用的立即运算,设计合理。理解立即数和特殊寄存器X0的作用对学习RISC-V汇编至关重要。
RISC-V指令类型、寻址方式与格式设计简洁而科学,有助于高性能实现。
RISC-V通过加载和存储指令实现程序与数据在寄存器和内存中的传送,寻址方式清晰高效。
RISC-V加载和存储指令实现程序与数据交互,通过基址寻址方式访问内存,提高效率。
bne rs1,rs2,offset
RISC-V条件决定指令可以实现选择和循环等基础流程控制,与加载和存储结合使用。
与(AND)、或(OR)、异或(XOR)指令,具有寄存器操作和立即数操作两个版本
用于掩码、数据组合等操作
RISC-V逻辑指令功能强大,操作简单,逻辑移位实现乘除运算。
汇编、链接转成机器码程序,CPU通过程序计数器顺序执行指令,实现程序运行。
将参数放在函数可以访问的位置
转移控制到函数
为函数获取需要的局部存储资源
执行函数任务
将返回值放在调用代码可以找到的位置
释放局部存储,还原寄存器状态
返回调用点
第一个8个寄存器a0-a7用于传参,a0-a1返回值,x1保存返回地址
主函数将参数放入s0-s1,将返回地址放入x1,通过jwl调用函数
函数执行任务后结果放回a0,通过jr返回主函数指定地址
jwl:跳转并链接,同时保存返回地址
jr:返回,跳转到返回地址处
函数调用需要保存上下文,传参传值,risc-v通过寄存器高效实现此功能。
函数调用的基本步骤包括:
主函数将参数放在函数可以访问的位置(指定寄存器)
使用jump和link指令转移控制至函数
函数获取需要的局部存储资源(栈空间)
执行任务并将返回值放置指定位置
恢复寄存器状态并释放存储资源
使用return指令返回至调用点
RISC-V中a0-a7寄存器用于参数传递,a0-a1返回值,x1保存返回地址。
leaf函数有4个参数g,h,i,j,一个返回值f。
参数通过a0-a3传入,临时变量使用s0-s1注册。首先为s0-s1腾出栈空间,计算函数值,然后释放栈空间,恢复寄存器,通过返回地址返回。
函数调用时利用栈来保存重要信息。栈是一个后入先出结构,利用x2寄存器记录当前栈指针位置。
每次函数调用都会在栈上创建一个栈桢,包含返回地址、参数、局部变量等。函数结束后恢复原始栈指针位置。
对于嵌套函数调用,唯一可以存放返回地址的寄存器是x1。但内层函数调用时会覆盖x1中的返回地址,造成返回地址丢失。
RISC-V在函数调用时将寄存器分为保留寄存器和临时寄存器两类:
调用者负责保存x1、a0-a7和需要保存的值临时寄存器; 被调函数负责任保留保留寄存器和堆栈指针的值。
若调用者的值位于临时寄存器,则需要事先保存到保留寄存器或堆栈中。函数返回后调用者负责恢复保存的值。
通过区分保留寄存器和临时寄存器,以及相关保存规则,实现RISC-V函数的嵌套调用。
C语言中的变量包括:
自动变量:函数内定义的局部变量,调用函数时分配,函数结束后释放。
静态变量:全局变量,整个程序生命周期内保持。
自动变量无法全部保存在寄存器中时,需要存储在栈中。
静态变量存储在数据段中。
函数调用时使用栈来保存返回地址、参数、局部变量等内容。栈为后进先出结构,使用x2寄存器记录栈指针位置。
每个函数调用都对应一个栈帧,包含内容依次入栈,函数结束后出栈回收空间。
栈从高地址开始,堆从低地址开辟,静态数据段在中间,程序代码段最低地址。
RISC-V约定固定内存区域:
以sum_square为例,分析函数调用时不同变量在栈和寄存器中的存储情况。
函数调用时变量存储采用栈来实现,并结合C语言三大内存区域如何在RISC-V中布局。
将RISC-V指令划分为不同组:
同一组指令格式相同,体现了处理器执行指令的方式。
下个模块将描述如何将RISC-V汇编指令转换成二进制机器码形式(0和1)。虽不需要记住机器码,但这就是处理器执行的真实形式。
本模块总结了RISC-V汇编语言模块的内容,并提前预告了下一模块将介绍指令的机器码级别表示形式,将深入了解处理器执行指令的物理原理。
通过例程说明RISC-V函数调用的具体过程:
理解汇编指令原理,有助于深入理解程序执行流程,以及指令优化的思路。
RISC-V指令以固定32位二进制形式存储在内存中,CPU依次读取和执行。
指令格式影响了指令如何由CPU解析和执行。
RISC-V定义了多种指令格式,促进了高性能指令解码。
指令格式决定其编码方式,指导CPU如何高效解析指令各字段。
RISC-V指令采用32位编码。R格式指令用于算数与逻辑操作,格式如下:
011100,表示R格式指令。rd。func3代码。rs1和第二个操作数寄存器rs2。func7代码。每个寄存器字段宽5位,刚好可以表示0-31号32个寄存器。操作码和功能码通过组合来区分不同指令。
加法指令add的编码示例:操作码011100,func3和func7全0,rd为目标寄存器,rs1和rs2分别为两个操作数寄存器。
shift右移指令srl的功能码第6位为1,表示需要进行有符号扩展。
减法指令sub与加法指令add的功能码设置相似,实际上 subtraction也可通过原数加两种补数实现。
以add x18, x19, x10为例:
所以add x18, x19, x10指令的32位编码为:
011100 100010 100011 001010 0000001
把每位转换为16进制即为完整的指令格式。
I格式指令用于支持立即数操作,如加减数、逻辑与算术运算。
I格式指令采用32位编码,格式如下:
使用rs2和funct7字段合成12位立即数字段,可以表示-2048~2047范围内的整数。
以addi x15 x1 -50为例:
共9类I格式指令,其中单目运算与逻辑运算func3与R格式相同。新增slt/slti用于比较运算。
位移指令仅支持5位移距;func7中区分算术右移与逻辑右移。I格式指令寻址范围为-2048~2047,支持汇编 tiempo常用常数。
RISC-V定义了一类加载指令,使用I格式。
I格式包含操作码、源寄存器、目的寄存器和12位有符号立即数。
加载指令使用新的操作码来标识,其他字段与I格式相同。
立即数表示基址寄存器与要加载地址的偏移量。
不同的加载包括加载字、加载字节和加载半字。字节和半字加载需要补码扩展。
以lw x14,8(x2)为例:
字为32位,字节为8位,半字为16位。加载实现从内存读取并扩展到寄存器全长。
RISC-V成功将加载指令编码在现有I格式中,省去新的指令格式定义。
RISC-V定义了一类存储指令。与加载不同,存储使用特定格式。
S格式包含操作码、两个源寄存器和12位有符号立即数。
存储需要两个源寄存器:数据寄存器和基址寄存器。立即数与基址相加形成存储地址。
S格式采用和R格式相同的源寄存器位置编码。立即数分为上7位和下5位组成12位。
如指令sw x14,8(x4)
支持存储字、半字和字节,不同类型存储不一样数量的位到内存。
S格式机智的利用源寄存器位置编码,成功将存储指令集成在RISC-V指令系统中。
RISC-V支持条件和非条件分支指令。
B格式用于条件分支,包含20位有符号立即数和6位条件代码。
首先测试条件码,若满足则跳转到立即数地址进行计算。
20位立即数可以直接表示偏移量的2的20次方范围,支持±1MB地址空间。
如bne x1,x0,12
J格式用于非条件跳转,类似B格式但没有条件码。 I格式内联条件跳转支持较小范围跳转。
B格式设计优雅,将分支条件和目标地址合成一个指令来实现条件分支功能。
lui指令用来加载上移立即数到目标寄存器的高20位,低12位清零。
例如,要将16进制的deadbeef加载到寄存器x10中:
deadc(上20位)加载到x10高20位addi指令将下面12位的beef加到x10中但是,有时候addi会出现问题。因为它是有符号扩展的,一个负数会导致高位溢出。
为解决上述问题,RISC-V定义了一个伪指令li,它会自动使用lui和addi指令加载长整型立即数。
例如:
li x10, deadbeef
就会正确地加载deadbeef到x10寄存器中。
auipc指令可以将上移立即数加到当前程序计数器值,结果放入目标寄存器。
例如:
auipc x10, 0
就把当前PC的值加载到x10寄存器中。这对调用返回地址很有用。
通过给auipc一个标签的偏移,也可以将该标签地址加载到寄存器中。
RISC-V定义了J格式来表示无条件跳转指令。
J格式包含7位操作码、5位目的寄存器寄存器编号rd和20位偏移量。
J指令会将下一条指令地址(PC+4)储存在目的寄存器rd中,并将程序计数器设置为(PC+偏移量)处。
J指令支持±2^18字节(1MB)的跳转范围。偏移量低位强制为0,确保跳转目标地址是双字节对齐。实际上跳转范围为±2^19字节。
例如指令“j label”会将PC+4放入rd寄存器,同时设置PC为标号label处。
JAL指令编码采用I格式,包含目的寄存器rd、源寄存器rs1和12位有符号立即数。它同时将返回地址写回rd
RISC-V指令集RV 32i包含六种指令格式:
R类型:寄存器操作类指令,操作数为两个源操作数寄存器和一个目标寄存器。
I类型:立即值操作类指令,一个源操作数寄存器和12位的立即字段。
S类型:存储类指令,一个源操作数寄存器,一个目标操作数寄存器和12位的立即字段。
B类型:条件分支类指令,一个源操作数寄存器,12位的立即偏移和条件码字段。
U类型:无条件跳转类指令,20位的立即字段。
J类型:调用跳转类指令,目标寄存器、源寄存器和20位的立即字段。
RISC-V采用固定的指令格式来简化硬件设计。寄存器和立即值字段的位置均定于一尘,使得处理器更容易找到。RISC-V指令集涵盖通用整数操作,足以实现任何C语言程序的编译。RISC-V指令集已经完成标准化,不再进行修改,提供了稳定的指令集架构用于学习计算机系统。
程序可通过解释执行和翻译执行两种方式运行在计算机上:
解释执行:程序首先通过编译或翻译成中间形式,例如字节码。然后在运行时,解释器依次读取和执行每条中间码指令。这种方式适用于脚本语言如Python。
翻译执行:程序首先通过编译过程翻译成目标机器语言的 object 文件或机器语言指令,然后链接生成可执行文件。运行时直接加载并执行已经翻译成的机器码,无需额外的解释过程。这种方式的程序通常运行速度更快。
本课将学习C语言通过翻译执行的整个流程:
预处理:处理头文件包含和宏等预处理 directives。
编译:将源代码翻译成目标文件(Object File),包含文档信息和机器码。
汇编:将目标文件中的机器码汇编成更易读的汇编语言。
链接:连接多个目标文件和程序库生成单一的可执行文件。
加载:操作系统从可执行文件加载程序到内存运行。
以上流程将C语言程序完全翻译成机器可执行的指令,在运行时直接执行已翻译结果。
编译器的输入是C语言源代码文件,输出是汇编语言源文件(.s文件)。
编译过程主要包括以下步骤:
预处理阶段处理头文件包含和宏定义等 preprocessing 指令。
编译阶段将C源代码翻译成目标文件中包含的机器代码和调试信息。
添加优化选项可以改变编译器的优化行为,生成不同的机器代码。
使用-S参数可以使编译器输出汇编文件供查看。这是编译器输出的中间文件。
汇编语言文件中可以包含伪指令,如move统一翻译成异或指令,简化汇编程序编写。
C代码也可以手动编写成汇编文件输入给编译器。这可以帮助理解编译 原理。
编译器的工作就是将C代码翻译成当前处理器ISA的汇编级指令,例如RISC-V指令。
编译器通过多阶段翻译与优化将高级语言程序转换成低级语言以便直接在机器上执行。
汇编器将汇编语言源文件(.s文件)转换成目标文件(.o文件)。
解析汇编指令并转换成机器码。
生成符号表存储符号名称与地址对应关系。
生成重定位信息,标记需要链接器处理的外部引用。
生成目标文件包含机器码、调试信息和重定位部分。
目标文件包含代码区、数据区、符号表、重定位信息等内容。
汇编器负责将高层次的伪指令翻译成实际的机器码指令。
生成重定位信息表明该文件需要链接器引用其他目标文件或库中的符号。
汇编器实现汇编语言到机器语言的翻译,帮助优化目标文件,生成链接需要的符号和重定位信息。
汇编器将汇编源文件翻译成机器可以直接执行的目标文件,为后续链接提供支持。
链接器将多个目标文件(.o文件)合并成一个可执行文件程序。
分析目标文件获取代码/数据段和未定义外部符号。
求解未定义符号,从目标文件或库文件中找到定义。
合并代码和数据段,解析重定位成地址。
生成可执行文件包含加载信息和入口点地址等。
目标文件包含代码段、数据段、符号表和重定位表等。
库文件提供符号定义实现代码/数据段重用。
链接器解决符号引用,合并代码段,生成单个可执行文件程序。
链接器最后生成一个完整可执行文件,消除多个目标文件之间的依赖,实现程序组件的重用。
加载器的实际工作是由操作系统完成的,它负责将可执行文件加载到内存中运行。
从可执行文件读取程序头获取文本、数据段大小等信息。
为程序分配地址空间,预留文本、数据和栈空间。
将文件内容拷贝到内存地址空间中。
将命令行参数复制到栈中。
初始化机器寄存器,包括清零部分寄存器和设置栈指针SP。
跳转到启动例程,将 argc/argv 从栈拷贝到寄存器中。
设置程序计数器PC指向主函数入口,开始执行程序。
返回值通过系统调用返回至操作系统。
加载器负责设置好运行环境,使预编译好的可执行文件能在内存中直接运行。它是连接编译过程和真正执行之间的重要环节。
今天我们通过一个示例程序来演示整个编译、汇编、链接、加载的过程:
一个简单的C程序,打印”Hello World”。
使用gcc预处理并编译源代码,生成目标文件hello.o。
用objdump反汇编目标文件,查看机器码和汇编指令。
链接器ld将目标文件链接生成可执行文件a.out。
再次用objdump反汇编可执行文件查看。
在终端直接运行可执行文件,打印输出结果。
该示例清晰展示了整个编译流程:
C代码经过编译成目标文件。
汇编器将目标文件转换成汇编语言。
链接器生成单个可执行文件。
加载器在运行时加载执行二进制代码。
通过实际例子,助理理解高级语言程序如何被翻译和链接成机器可直接运行的二进制代码。
C语言使用malloc等函数动态分配内存,主要包括:
堆内存不在进程创建时分配,而是根据程序需要动态分配释放。
C结构体使用结构描述符(Structure Descriptor, SDS)来保存结构体中各成员的信息:
编译器根据SDS生成访问结构体成员的机器码。
C语言实现动态内存分配需要使用链表来表示可回收内存块:
加入/删除内存块时使用链表操作修改表头等指针域。
C语言动态内存和链表机制实现了程序中的内存管理功能。了解其机理对学习操作系统同样很重要。
数字电路系统使用二进制信号表示0和1电平状态。
时脉信号是一个周期性切换电平的信号,用于协同整个系统的操作和同步各组件。
波形是表示信号在时间上的变化曲线。数字信号 only有两种电平,波形为方形波。
时钟信号的一个完整高低电平转换周期。
时钟信号在给定时间内的周期数,也称作系统时钟频率。
两个相邻时钟边沿之间的时间间隔。
数字系统的组件在同一时钟周期内同时操作,利用时钟的正、反沿同步和协调组件之间的信号传播。
时钟信号体系构成数字系统的基础结构,协同各组件的同步工作。理解时钟概念对学习计算机体系结构很重要。
目标是构建一个电路,可以实现将一个整数数组所有元素求和的功能。
直接使用加法器实现累加,但是存在以下问题:
没有机制控制每次输入;
没有方法初始化状态和赋初值。
使用寄存器可以记录状态信息,解决了上述问题:
时钟信号控制寄存器的读取和写入;
重置信号可以将寄存器状态初始化为零。
输入信号 x 按顺序传递每个数组元素;
使用寄存器记录输出累加值,上一时钟段输出作为下一时钟段输入;
时钟边沿触发寄存器进行读取和累加操作。
通过结合组合逻辑和有限状态机,设计出可以实现累加功能的数字电路。状态寄存器扮演了关键角色,记录和控制电路状态信息。
累加器电路包括加法器和寄存器:
加法器实现数组元素与前一个求和结果的累加;
寄存器记录和提供前一个求和结果,作为下一个循环的输入。
时钟的一个完整周期作为一个循环;
指定一个重置脉冲初始化寄存器状态为0;
第一项数组元素随后输入,实现第一个求和结果。
每个时钟周期:
通过加法器和寄存器的协同工作,实现了累加功能。状态寄存器记录状态信息,驱动电路的循环运行。
一个时序电路的最大时钟频率取决于时钟到Q输出的延迟、组合逻辑的延迟和设置时间三个参数的总和。
如果将一个大型组合逻辑电路分成多个较小阶段,并利用寄存器在每个阶段之间同步和传递数据,就可以解决大延迟问题,提高时钟频率。
将一个具有加法器和移位器的时序电路通过插入寄存器分成两个阶段,每个阶段只完成一个小任务。
此时每个阶段的延迟较小,且可以并行工作,整体时钟周期可以减小。
单个数据通过整个电路需要更长时间;但由于每个时钟可以有多个数据同时在不同阶段计算,总的输出频率提高。
时钟信号、设置时间、时钟到Q延迟、组合逻辑延迟、寄存器、管线等。寄存器是实现状态机和数据传递的重要组成部分。
组合逻辑电路的输出仅依赖于输入,不考虑时序因素。
真值表记录所有可能的输入组合及相应的输出,完全描述组合逻辑行为。
AND真值表:当且仅当所有输入为1时,输出为1。
OR真值表:当且仅当至少有一个输入为1时,输出为1。
NOT真值表:当输入为0时,输出为1;输入为1时,输出为0。
对于N输入门,需要考虑2^N种可能的输入组合情况。
可以将简单门继续组合成更复杂门,对应的复合门也可以写出真值表。
真值表可以表示任何组合电路,也可以从中推导出电路实现需要的硬件细节。
逻辑门实现组合逻辑电路,能够完成布尔运算。
AND门:仅当所有输入为1时输出为1。
OR门:当且仅当至少有一个输入为1时输出为1。
NOT门:对单一输入进行非运算。
NAND门:与非门,结合AND和NOT门实现。
NOR门:或非门,结合OR和NOT门实现。
PMOS和NMOS场效应管按电路连接实现AND、OR和NOT门。
CMOS结构实现的AND、OR和NOT门,由PMOS和NMOS构成,工作速度快、功耗小。
可以利用基本门级再组合实现更复杂的多输入逻辑,如全加器或复杂Decoder等。
逻辑门的工作状态与输入脉冲无关,仅依赖于输入电平状态,即具有组合逻辑属性。逻辑门实现了基本布尔函数。
布尔代数研究二进制数的代数运算规律,许多定律对逻辑电路设计很重要。
AND、OR逻辑门满足交换律:AAND/OR B = B AND/OR A。
A AND (B OR C) = (A AND B) OR (A AND C) A OR (B AND C) = (A OR B) AND (A OR C)
A AND A = A A OR A = A
A AND B 的对偶是A OR B;A OR B 的对偶是A AND B。
A AND (A OR B) = A A OR (A AND B) = A
A AND 1 = A A OR 0 = A
A AND NOT A = 0 A OR NOT A = 1
NOT(A AND B) = NOT A OR NOT B NOT(A OR B) = NOT A AND NOT B
了解这些定律有助于电路优化和最小化。
典型形式是从真值表推导出来的一种逻辑表达式的标准形式,能够唯一代表该真值表。
对真值表中每一行输出为1的情况:
连接所有这样得到的输入项,即为该行的条件串联式
详细通过一个3输入真值表,步步说明如何得到其总和和式形式表达式。
应用分配律、交换律等布尔代数规则,将总和和式进一步简化为最简形式。
根据表达式中逻辑运算符,对应绘制与门、或门和非门,实现该表达式。
真值表到布尔表达式到电路图,构成一个完整的转换流程。可以系统化地为任意真值表推导其标准形式表达式。
多路复用器是一种选择性传输数目限定信号的组合逻辑电路。根据选择信号,选择其中一个数据输入输出。
二路多路复用器根据选择信号S的电平值0或1,选择数据输入A或B输出。
多路多路复用器 generalization。根据n比特的选择信号,选择2^n个数据输入中的一个输出。
多路复用器可以通过组合逻辑电路或者继续结合逻辑门实现。
总而言之,多路复用器能从有限个信号中选择一个输出,广泛应用于数字系统中需要进行选择的场景。
ALU是执行算术和逻辑运算的组合逻辑块,用于处理计算机指令集中的运算。
ALU由加法器、减法器、与门和或门等组件组成。选择信号线选择执行加/减/与/或操作。
将基本组合逻辑块如多路复用器、加法器等组合在一起,设计出可执行多种运算的ALU组合逻辑模块。
加法器实现两数之和,减法器实现减法运算。
采用全加器組合实现。全加器输入A,B, Ci,输出两位,求和S,进位Co。
减法使用加法器加上一位借位实现。如A-B等于A+(负B)+1。对B取反,再与A相加。
通过4位加法器和减法器 truth table 以及电路图,说明其工作原理。
将加法器和减法器作为基本块,结合ALU裁判信号线,完成ALU中加减运算的实现。该模块对CPU指令集的支持很重要。
设计一个减法器,并尽可能复用整数加法器的结构。
A - B等价于A + (-B),其中-B表示B的负数。
两补数制下,整数的负数表示为该整数的二进制补码。将整数的每一比特取反,然后加1。
利用选择信号S条件反转输入Y,构成一个条件反转电路。当S=0时输出Y,当S=1时取反Y。
使用条件反转电路对被减数B的每一比特进行条件取反,获得B的负数表示。
然后将A和取反后的B作为加法器的两个输入进行加法运算,即实现了A - B。
利用加法器的进位出来线C实现符号溢出和无符号溢出检测。
将负数生成、加法运算和溢出检测分离,利用网络结构和多路复用器安排连接,从而最大限度利用加法器的结构实现减法。
以上方法充分利用了数值在补码下的等价性,将减法问题转换为加法问题,实现了减法器的模块化设计。
在微处理器设计中追求不同层次的并行性,包括逻辑门级、功能单元级和指令级并行性。
微处理器内主要包含数据通路和控制单元两部分。数据通路负责执行指令,控制单元负责控制数据通路执行指令的流程。
RISC-V定义了一整套32位和64位指令集,本课程集中介绍32位整数指令集RISC-V RV32I。
数据通路内主要包含注册文件和算术逻辑单元 ALU 等功能单元。 registering 存储中间结果,ALU负责执行算术运算。
控制单元控制数据通路设置,以便优化执行各个指令。一个数据通路可以完成ISA中的所有指令执行。
本课程将带领同学设计符合RISC-V RV32I规范的单周期CPU,其中数据通路和控制单元相互配合,能正确执行RV32I指令集中的各条指令。
设计数据通路时以执行速度和易部署为目标,最小化功能单元数量和复杂度。
作为数据通路重要组件,用于暂存和传输指令/数据。RISC-V定义32个通用寄存器x1-x31。
ALU为执行算术及逻辑运算的基础单元,用零地址模式访问第二个操作数。
PC指示当前执行的指令地址,单独划分为一个寄存器,作为数据来源。
用来传输指令码和操作数,连接不同功能单元。应能高效支持并行传输。
明确数据通路在每个时钟周期内不同组件的读写权限和数据传输路径。
设计控制单元产生周期性控制信号,协调数据通路组件的工作,正确执行各条指令。
以上原则构建支持RISC-V RV32I指令集的单周期CPU数据通路,体现优化设计理念。控制单元实现正确时序和路径控制。
数据通路是CPU执行指令的基石,主要包含程序计数器、指令存储器、寄存器堆和算术逻辑单元等组成部分。
单周期CPU内各组件工作是根据时钟脉冲的上升沿而同步的。在每一个时钟周期内完成一次指令的执行。
add指令从寄存器文件读取源操作数rs1和rs2,在ALU中加和,结果写入目标寄存器rd。指令中的不同寄存器编号直接连接到寄存器文件对应的读写端口。
在时钟的第一个上升沿,新一个pc地址写入程序计数器,同时指令存储器输出该地址对应的指令。指令解码后从寄存器文件读取操作数,ALU执行加法操作。结果在下一个时钟发送写回寄存器文件。
控制单元产生控制信号控制寄存器文件在接收到ALU结果后写入新值的时机,实现指令正确执行的时序控制。
单周期CPU的数据通路设计实现了对add指令的支持,其他类型指令的支持需要扩展数据通路和控制单元以适应不同指令格式。
R格式指令包括add、sub等算术指令以及逻辑指令,表示方式相同仅在funct3和funct7字段有区别。
减法等效于加法符号取反,即A-B等同于A+ (-B)。负数在补码表示法下,将正数的二进制码进行反码后加1。
原单纯加法ALU改为完整ALU,根据funct7字段选择进行加法或减法运算。控制ALU进行正号运算或符号取反运算。
为ALU增加一个控制信号,指示ALU执行加法或减法。根据指令不同将该信号设置为0或1,实现对加减两类R指令的支持。
通过完善ALU和控制信号,同一数据通道可以正确执行add和sub两类R格式指令。进一步可支持所有R类型指令指令。
单周期CPU数据通路通过对ALU的改进,实现了对减法指令sub的支持,同时为扩展至其他R指令奠定基础。
I类型指令含一个源操作数rs1和立即数,无第二源操作数rs2。不同于R类型,指令中含12位立即数字段而非rs2和funct7字段。
原数据通路支持R类型,将ALU第二输入端口rs2改为一个多路选择器,选择rs2值或立即数输入。通过b选线控制选择器选择端口。
从指令中提取12位立即数字段扩展为32位,低12位直接连接,高20位填充最高有效位以实现补码。多路选择器输出至ALU第二输入端口。
控制单元产生需要的控制信号,读取rs1值、生成立即数、选择立即数作为ALU输入并执行计算,将结果写回寄存器文件实现I类型指令执行。
通过添加多路选择器和立即数生成逻辑,原数据通路实现支持I类型指令,统一执行R类型和I类型指令,扩展指令集支持能力。
原数据通路支持R和I类型指令,但不包含存储器访问阶段。为支持L类型指令,需增加数据存储器组件和相应控制。
L类型指令与I类型相同,都含一个源操作数rs1和立即数字段。不同之处在于立即数用于表示内存地址,而非直接写入目标寄存器。
在原数据通路基础上增加数据存储器组件。通过多路选择器选择ALU或存储器输出写入目标寄存器,实现指令执行与存储器访问相结合。
指令解码后设置相应控制信号,计算内存地址,从存储器读取数据,写入目标寄存器完成执行。执行各阶段需协同工作,实现指令流水化执行。
同一数据通路通过逻辑电路改进,可支持其它加载格式,如半字或字节加载。整个单周期CPU数据通路完成对所有RISC-V基础指令集的支持。
S类型指令用于存储器访问,读取两个寄存器rs1和rs2,同时从指令提取立即数。
需要修改数据存储器添加写端口,并设置读写控制信号。设置右回选择信号以优化控制逻辑。
计算内存地址,将rs2内容写入存储器写端口。不回写寄存器,保证写操作顺序执行。
支持I和S类型不同立即格式,采用多路选择器选择源,其余逻辑不变。
数据通路基础不变,通过逻辑门限制写入范围防止覆盖错误。
字节和半字存储指令数据通路相同,仅限制写入以避免错误。
通过添加存储器端口和控制优化,单周期CPU数据通路实现了对所有存储指令的支持。
分支指令通过比较寄存器rs1和rs2的值,来决定是否更新程序计数器的值。如果满足分支条件,就将程序计数器的值更新为当前值加上立即数偏移量。如果不满足条件,就将程序计数器加4,指向下一条指令。
分支指令有6种:
为了支持分支指令,需要向单周期datapath增加以下部分:
在程序计数器前增加多路选择器,可以选择计数器加4或计数器加立即数作为下一个值。
增加分支比较器,用于比较寄存器rs1和rs2的值,输出等于或小于结果。
增加多路选择器,可以选择将rs1值或者程序计数器值送入ALU的A端口。
ALU继续用来计算程序计数器加立即数值。
写回程序计数器的新值。
为分支类型增加立即数解码。
控制分支比较器是否进行有符号或无符号比较。
控制多路选择器的选择。
分支比较器是对rs1和rs2的值进行逻辑比较的电路,输出等于或小于两个结果信号。支持6种分支类型的比较。
与I型和S型指令类似,B型指令也使用12位编码一个31/32位立即数。不同的是将第7位移到不同位置,其他位保持不变。只需要一个2输入多路选择器来在S型和B型间转换。
获取rs1和rs2值
进行分支比较
ALU计算程序计数器与立即数之和
根据分支结果选择更新程序计数器
更新程序流水线状态
通过增加相应组件,单周期datapath支持了分支指令。这为后续支持完整指令集奠定基础。
jalr指令为I格式指令,含有源寄存器rs1和立即数。功能为将rs1内容加上立即数加载到PC,并将PC+4写入目的寄存器rd,实现函数调用。
原数据通路缺少写入rd的路径。需要增加右回选择多路选择器输入端,引入PC+4信号。选择器选0/1/2三个端口。
与I类型指令相同,从指令中提取12位立即数扩展为32位,与rs1相加。ALU计算结果加载到PC。
控制单元产生需要的控制信号,设置右回选择多路选择器选择PC+4写入rd,ALU计算结果加载PC,实现jalr指令执行。
详细说明数据通路各组件和信号在jalr指令执行各阶段的工作状态。
单周期CPU数据通路通过增加返回地址路径和控制优化,实现了对jalr指令的支持,从而扩展到RISC-V基础指令集的完整支持。
JAL为J格式指令,含20位宽立即数字段和目的寄存器rd字段。
JAL指令执行两个操作:1. 将PC+4保存到目的寄存器rd,作为返回地址。2. 将PC的值加上立即数偏移量加载到PC,实现无条件跳转。
JAL指令采用JALR指令保存返回地址的机制,将PC+4写入rd。同时使用分支指令的机制,ALU将PC和立即数相加,结果加载PC实现跳转。
J格式立即数采用类似B格式的编码方法,编码20位跳转偏移量。
设置相关控制信号,右回选择器选择PC+4写入rd,ALU输出结果加载PC,实现JAL指令功能。
详细说明JAL指令在各个时钟周期内数据通路的工作状态。
单周期CPU通过采用现有机制,实现了对JAL指令的支持,从而向RISC-V基本指令集添加了无条件跳转指令。
U类型指令在指令最高位编码20位宽的上部立即数,下面为目的寄存器及操作码字段。
loui指令将上部立即数加载到目的寄存器,auipc指令将上部立即数加上PC值加载到目的寄存器。
只需添加多路选择器,将上部立即数20位直接送入立即数输入即可,无需扩展为32位。
ALU直接将B输入(立即数)复制到输出,写入目的寄存器完成加载。
ALU将程序计数器和立即数相加,结果写入目的寄存器。
详细示出U类型指令在各个时钟周期内数据通路的工作状态。
单周期CPU通过添加选择器,实现了对上部立即数的支持,从而完整支持RISC-V基础指令集。
设计完成了可以执行RISC-V RV32I指令集所有指令的单周期CPU数据通路。
数据通路可以在单周期内执行任何C语言程序经编译后的汇编指令。
数据通路执行分为指令获取、译码、执行、内存访问和写回五个阶段,不同指令在不同阶段活跃。
每个单元在某一指令中都有使用,完成各自功能。
设计控制单元,输出控制信号配置数据通路正确执行各类指令。
数据通路设计工作完成,实现了RISC-V基本指令集在单周期CPU上的支持,下一步将着手控制单元设计。
回顾单周期CPU的组成:数据路径、控制单元和时钟。数据路径包含执行各个阶段所需的组件,控制单元产生控制信号配置数据路径。
概述RISC-V指令集的6种类型:R、I、S、B、J、U型。各种类型指令格式和功能的区别。
详细介绍如何针对各指令类型设计数据路径组件,包括寄存器文件、ALU、多路选择器等。设计目标是支持RISC-V基础指令集RV32I。
着重解析ALU、程序计数器、立即数合成单元等数据路径的关键组件,以及它们在执行不同指令时的功能。
介绍数据路径在每个时钟周期内各组件的工作状态,以及控制单元需要输出的时序控制信号,确保指令正确执行。
通过上述设计,实现了一个可以执行所有RISC-V RV32I指令的单周期CPU数据路径。
CSR是独立于通用寄存器的一组专门寄存器,用于监控处理器状态和性能,与外设设备通信。
RISC-V架构支持的CSR数量最大为4096个。
统计执行周期数和指令个数,与浮点单元和外设通信,设置状态标志位。
采用I格式,前12位为CSR地址,其余与I型指令相同。支持源寄存器和立即数两种读写方式。
通过与通用寄存器交换值实现读写。例如csrrw指令先将CSR值读入目的寄存器,然后将源寄存器值写入CSR。
仅写入CSR,相当于csrrw但目的寄存器为x0。csrwi使用立即数写入CSR。
以组块寄存器方式实现,需要时钟和写使能控制以防误改。
CSR是处理器重要组成部分,通过专用指令实现与其读写, extracting用于监控和通信功能。
单周期CPU的控制部件是控制数据通路工作的逻辑电路。它通过设置多个选路器的选择信号,配置数据通路来执行指令。
每个指令的执行都从时钟的上升沿开始。程序计数器的值将在下一个时钟沿更新,但更新后的值需要一段时间通过选路器传播。
在执行指令的同时,程序计数器值同时增加4,新的指令也从指令存储器读取。这两个操作的传播延迟相当。
控制单元读取指令码后,同时设置多个控制信号来配置数据通路。例如存储指令会设置程序计数器选择信号为加4,使新程序计数器值通过选路器。
控制单元也允许并发获取多个操作数。例如存储指令可以并发获取寄存器对应的值和立即数。
数据通路内各个功能单元的操作也能够部分重叠执行。例如在ALU执行加法的同时,寄存器值已经准备就绪。
条件分支指令在判断条件的同时,也会预备下一条指令的程序计数器值。条件满足时选择该值,否则选择加4后的值。
整个单指令执行周期都依靠时钟的下一个沿完成状态更新,但数据通路内各个步骤可以部分重叠执行,提高指令并行度。
每个指令都需要一个时钟周期完成执行,但不同阶段可以部分重叠。
获取指令码-译码-执行-写入,各阶段操作可以同时进行。
时钟的上升沿标志一个周期开始,下降沿更新所有状态。
第二条指令可以在第一个指令执行期间提前获取,但结果写回需要等待第一个指令结束。
在判断条件的同时预取两条指令,条件满足选择一条指令执行。
各功能单元之间存在时滞,但控制单元可以利用重叠执行隐藏时延。
整个单周期执行依靠复杂的时序控制,实现不同指令各部分步骤的重叠执行。
控制单元根据不同指令产生控制信号配置数据通路。
包括多路选择器选择线、存储器读写使能等工作在每次时钟的不同阶段。
利用时钟脉冲产生具体控制时序,如译码阶段、执行阶段等定时信号。
根据指令码产生针对该指令的所有控制信号,比如ALU运算操作码。
采用组合逻辑设计指令译码器和时钟格式化器,输出控制信号。
所有操作都在时钟边沿同步,确保指令执行的正确性和顺序性。
控制单元的组合逻辑设计是实现单周期CPU时序控制的关键。它通过译码和时钟组合逻辑电路产生各类控制信号实现指令执行。
从高层语言到低层逻辑门,设计出可以执行C程序的单周期CPU,实现了软硬件接口。
设计完成了支持RISC-V基础指令集的单周期数据通路,以及产生控制信号的控制单元。
指令获取、译码、执行、访存和写回阶段的工作原理。
通过时钟脉冲和控制信号,隐藏数据传输延时,实现不同阶段重叠执行。
通过指令译码和时钟格式化逻辑,产生需要的选择器控制信号完成指令控制。
优化设计以提高性能,增加功能模块并学习相关知识,完善单周期CPU设计。
通过系统地设计,实现了软硬件接口,标志着计算机系列课设计工作的一个里程碑。
用单周期CPU执行一个指令需要的最小周期时间作为性能测量标准。
程序执行时间、每单位时间完成的任务数、耗电量等都是常见的性能测量标准。
以运输汽车和公交车为例,阐述在不同场景下其性能标准的区别。
程序执行时间、每单位时间完成的任务数(如页面请求)、每任务耗电量等。
降低程序执行时间,提高每单位时间完成的任务数,减少耗电量。
将深入研究CPU的流水线技术,来优化CPU性能,减少程序执行时间和提高任务吞吐量。
该课程概述了计算机体系结构课程设计的重要思想—性能测量和提升,阐述了计算机领域更广泛的性能标准,为后续介绍流水线技术奠定基础。
计算机系统性能的标准包括程序执行时间、每单位时间完成的任务数量以及耗电量。
根据铁律定律,程序执行时间可以分解为指令数量、每指令周期数和每周期时间三个基本参数的乘积关系。
取决于任务算法和实现、编程语言层级、编译器效率等因素。高级语言描述更简洁但翻译成汇编指令可能更多。
取决于 Instruction Set Architecture(ISA) 规范,同一 ISA 内不同实现也可能不同。一般 Complex Instruction(CISC)需要的周期数更多。
由微架构实现决定,主要因素包括技术节点、时钟频率以及功耗预算。时钟频率高但功耗大的处理器相对时钟低功耗小的来说,每周期时间短。
单独看某个参数无法判断总性能好坏。例子说明,时钟低但每指令周期数优异的处理器,可能最终性能表现比其他参数部分较好但综合效果较差的处理器更好。
通过分解各基本参数,有助于深入理解影响处理器性能的各个方面,为后续流水线优化奠定基础。
处理器功耗主要由动态功耗和静态功耗组成。
取决于时钟频率和电压平方。降低电压可以显著减少动态功耗。
主要由晶体管漏电引起,随技术进程下降但仍占比重大。
在保持性能水平的前提下,降低时钟频率和电压,减少动态和静态功耗。
手机处理器相对PC处理器采用更低频率但电压,以平衡性能和功耗。
功耗与时钟频率成反比,降低频率会增加每周期时间从而影响整体性能,需要综合考虑各因素平衡。
通过分析影响处理器功耗的主要组成部分,初步介绍提高能效需要在性能和功耗之间取得平衡,为后续流水线优化奠定能效论基础。
周日晚上,四个学生(阿维、波拉、卡罗琳、丹)需要在宿舍洗衣。
洗衣机30分钟,烘干机30分钟,折叠30分钟,收衣30分钟。
一个个完成各阶段,总用时8小时。
overlap各个任务,总用时缩短到3.5小时。
通过洗衣例子,介绍计算机流水线的基本概念和原理。
计算机指令也可以流水线执行,优化性能。
随着时间推进,不同指令在各流水线级别同时运行。
流水线中的数据依赖及相关技术解决方案。
在管线处理器中,多个指令会同时执行不同阶段,可能造成依赖性问题。
结构性悖论:两个指令争用同一个资源
数据悖论:指令之间存在数据依赖关系
控制悖论:后继指令依赖否决分支的结果
通过增加更多硬件资源,或插入暂停结点(stall),使指令能并行执行。
RISC-V 指令一次可以读取2次和写入1次寄存器,寄存器文件需支持3个访问口。
需提供独立的指令缓存和数据缓存,避免冲突访问主内存。
由于指令数据依赖导致,后继指令依赖前驱指令计算结果。
分支指令前的指令可能会因为分支结果而无效。
管道处理器设计的关键在于识别和妥善解决不同类型的管道悖论问题。
指令之间存在数据依赖关系,后继指令依赖前驱指令的计算结果。
后继指令使用前驱指令写入目标寄存器的值,但值尚未写入。
后继指令读取与前驱指令写入同一目标寄存器的值。
两个指令会同时修改同一目标寄存器的值。
指令重排
暂停结点插入
执行部分重组
移动指令顺序,避免RAW依赖。
插入暂停结点,延迟依赖指令的执行。
修改执行顺序,先执行写指令,再执行读指令。
数据悖论通过指令调整、插入暂停结点或者执行阶段重组等方法来解决依赖关系问题。
在内存层次结构的不同层次之间增加缓存,利用计算机程序的数据局部性,提高访问速度。
包含缓存块(line)、标签(tag)和状态位,以减少对主存的访问频率。
多个处理器内核共享缓存时,需要解决一致性问题,保证任何处理器都能读取到最新数据。
根据虚拟地址直接索引和选取缓存块,适用于单核单线程程序。
将较大缓存划分成较小组,每组拥有独立的标签和状态位,提高性能。
当处理器访问的地址不在缓存中时,该请求为缓存失效,需访问主存加载新数据。
当缓存满时,需选择一块缓存行进行替换,最常用的策略为LRU。
缓存利用数据局部性,通过提高内存层次结构的访问速度来加快程序执行效率。设计有效的缓存组织和替换算法至关重要。
加载指令在较晚阶段产生数据,后继指令使用该数据可能提前执行。
加载指令需要多阶段访问内存,其他指令可能会提前使用尚未获取的数据。
结果低延迟法(Result Bypass):将加载结果直接传送给后继指令。
暂停结点插入法(Stall):延迟过早使用数据的指令执行。
多周期执行法(Multicycle):将加载指令拆分为多个周期执行。
加载指令在译码阶段广播要写入的寄存器编号。
后继指令从加载器的寄存器绕过线路直接获取数据。
插入暂停结点延迟后继指令,直到加载完成将数据写入寄存器文件。
加载使用数据悖论通过低延迟接线或暂停结点方法保证数据依赖关系的正确性。
后继指令在分支结果确定前进入pipeline,可能导致错误执行。
分支预测
当预测正确时,无需插入延迟槽
当预测错误时,将后继指令转换为软件结点
根据上次分支是否跳转预测本次分支。
执行两个后继指令后校验预测结果,如果错误转换为软件结点。
通过分支预测提前加载程序计数器值,开窗期间校验预测结果。正确预测可以减少pipeline延迟,提升性能。
指令级并行处理多个独立指令。
嵌入并行指令级运算能力。
提高R.I.S.C架构资源利用率。
通过并行执行提高每周期指令执行量。
结构性障碍
数据依赖障碍
控制依赖障碍
提供更多处理器核心。
减少限制条件执行顺序的限制。
增强分支预测精度。
提高退load和缓存吞吐量接口带宽。
增大可用通用寄存器集。
引入指令重排功能模块。
通过增加并行资源和提高指令调度能力,实现同时执行多个独立指令,提高单位时间指令执行量。
二进制前缀是学习Cache和处理计算机存储单位时一个重要的概念。
早期,人们使用国际单位制(SI)来表示计算机存储单位,例如使用“千字节”表示1000个字节。但这与计算机的二进制存储单位(2的幂)不符。后来,硬盘制造商开始采用二进制单位来表示硬盘容量,例如“10兆字”表示2的20字节。
1999年,国际电工委员会(IEC)正式引入了二进制前缀,弥补了国际单位制在计算机存储单位描述上的不足。二进制前缀与国际单位制保持了同样的前缀字母表示(K、M、G等),但在前缀字母前添加字母“i”,且读音中加入“bi”表示二进制,例如“1KiB”读作“1ки比”。
这个视频中还介绍了许多助记符,可以记住二进制前缀的顺序,例如“Kind Man Gives Ten Percent Extra Zestfully”。视频中也讲解了如何通过掌握二进制前缀顺序快速计算2的指数论和转换计算机存储单位。
此外,视频还提到了8位可以表示256个颜色通道、计算机寻址空间的大小等基础知识。整体视频内容系统而详细,是学习Cache和处理计算机存储单位时很好的起步资料。
假设需要在大图书馆找一本书,首先需要在宏大的卡片目录中查找书的位置,这个过程越久耗时越长。然后需要花时间 physically 去找到书并取回,整个过程的耗时与图书馆的规模正相关。
计算机中的内存层次结构也存在这种问题。寻访更高层次的内存(如主内存)与访问图书馆更深层区域找到书的类似,速度更慢。
对CPU来说,距离越近的内存(如寄存器)速度最快。但与图书馆相比,不同内存层次的速度下降幅度更大。
随着时间的推移,CPU性能提升幅度远超内存,导致两者速度差距不断扩大。如果直接访问内存,CPU需要花费越来越长时间等待结果。
在后续课程中,将探讨缓存是否能在较快速度下提供大容量的内存,以缓解CPU和内存速度差距导致的性能问题。
计算机系统中存在不同等级的内存在距离CPU越近速度越快的内存层次结构。
随时间 CPU速度提升远超内存,导致两者速度差距持续扩大,如果直接访问内存将严重影响性能。
后续课程将探讨如何利用缓存机制,在较大容量的同时提供接近CPU速度的内存访问,从而缓解CPU和内存速度差距问题。
程序在执行过程中,会重复访问同一段数据或指令。这就是数据与时间局部性。
利用局部性,在距离CPU近的高速缓存中暂存可能被重复访问的数据块,以提高访问速度。
当缓存满时需要替换数据块。最常用的有LRU算法,最近最久未使用的数据块优先替换。
多CPU系统中同时写缓存需要解决一致性问题,确保程序读到最新数值。
当访问的数据不在缓存中时称为缓存失效,需从较慢的后级存储中加载数据。
利用局部性设计高效缓存组织与管理机制,有效缓解CPU和内存速度差距问题,提升系统整体性能。
通过将物理地址中的部分位直接映射到缓存,简化缓存寻址。
包含缓存块(line)、标签(tag)和状态位。物理地址的高位作为标签,低位作为缓存行内偏移量。
当缓存满时,旧数据块需要替换。直接映射缓存容易导致切换性能下降。
实现简单 höÜ奉违、访问速度快。
由于只能映射到唯一块, utilizes率较低。局部性不高的程序性能较差。
直接映射缓存通过简化寻址实现了高效访问,但利用率较低是其主要问题所在。
假设有4个缓存块的直接映射缓存。
| 物理地址格式:tag(8位) | 偏移量(4位) |
共4行,每行包含:
地址0x1234访问:
地址0x1238访问:没有命中,需要从主存装入块0。
当需要替换时,直接映射下只能替换当前行中的数据块。
直接映射缓存通过示例可直观了解其组织和访问过程。
缓存每次能读写的字节数。影响缓存性能。
缓存未命中(miss)的概率。较高表示低效利用。
缓存命中(hit)的概率。与差错率成反比。
缓存每行存储空间的大小,一般为2的幂次方。
直接 mapped缓存中的行数。间接缓存中的组数。
多级缓存结构中,每个级别的缓存数目。
从缓存或后备存储读取数据需要的时钟周期数量。
向缓存或后备存储写入数据需要的时钟周期数量。
决定缓存满时数据行替换顺序的策略,如LRU。
这些术语描述了缓存结构与性能表征的关键面,有助于分析和优化缓存系统。
缓存存放最近或即将需要的数据,以提升性能。计算机系统中广泛存在缓存机制。
随计算能力增强,主内存速度进步不足,导致 CPU 和内存速度差距不断扩大。缓存应运而生以解决这个问题。
直接映射缓存、置相缓存、组相缓存等。利用数据局部性原理提高命中率。
LRU 及其近似算法广泛应用。决定满缓存时数据行替换顺序。
多核系统中同时读写缓存的数据一致性问题及解决方案。
与替换算法、缓存参数(行大小、组数等)相关。用命中率、差错率等指标衡量性能。
利用多级结构充分利用不同层次存储资源。提高整体系统性能。
缓存机制是计算机体系结构中重要组成部分。系统地学习其原理对深入理解计算机架构很有帮助。
假设缓存有4行,其中:
地址0x1234访问:
地址0x3456访问:
地址0x1238访问:
直接映射缓存通过具体示例说明其访问流程。
直接写入缓存可能导致主存数据丢失,需写回策略或写入缓冲区解决。
过小浪费带宽,过大可能带来不必要周转。一般为2的幂次方,避免内存对齐问题。
通过调整块大小、组数等参数,减少特定失效类型,提升整体性能。
系统地了解和分析缓存机制各个方面,对优化缓存性能非常重要。
缓存中任一行都可以存储任何地址的数据块。
用请求地址的标签和块内偏移量进行全缓存比较。
如标签命中,访问相关数据块。
如未命中,需要替换一行后从主存加载新块。
需要支持动态选择每次替换的目标行,如LRU。
每次都能找到最佳匹配行,利用率高。
地址搜索难度大,实现复杂度高,访问时间长。
缓存规模小,追求最高缓存利用率时使用。
相比直接映射,全相联缓存利用率高但实现难度大,在平衡利用率和性能时一般以分组相联为主流选择。 对不起,您提供的标题和上一个笔记相同。请提供一个新的标题。
集合关联缓存(Set Associative Cache)位于直接映射缓存和完全关联缓存之间。它用索引指向某个集合,在该集合内任意块可以映射。n路集合关联缓存中,每个集合内有n个块。
以4路集合关联缓存为例:
集合关联缓存提高了对冲突块的利用率,使得在较小尺寸下也能获得良好的性能。它的工作原理结合了直接映射和完全关联两种方式的优点。
假设4路集合关联缓存:
所有块状态位清零。
按LRU常用程度排序:
块1>块0
选择状态位最小的块0替换。
FIFO、随机替换等,但LRU性能通常最佳。
通过例子说明集合关联缓存访问流程和替换策略,有助于理解其工作原理。
衡量内存层次结构总体性能的关键指标。
AMAT = 命中时间 × 命中率 + 缺页时间 × 缺页率
较低的AMAT代表内存访问更高效。AMAT可以作为优化缓存参数和层次结构的参考指标。
正确理解和应用AMAT对系统性能评估至关重要。
Motorola的PowerPC架构中,L1缓存分为指令缓存和数据缓存,大小均为32KB。外加一个外部L2缓存接口。
Pentium M中,L1指令缓存和数据缓存各32KB,内置L2缓存。
Intel Core i7中,每个核心内置有L1缓存和L2缓存,所有核心共享一个L3缓存。
PowerPC和Pentium M中,L1指令缓存和数据缓存布局在不同单元。L2缓存标签单独布在芯片上进行快速比较。
Core i7架构每个核心大致有L1和L2缓存区域。可能L3缓存布在几何结构相同的区域。
PowerPC支持最多3条执行单元同时运行,包括加载/存储单元、整数单元和浮点单元。
Pentium M支持2个整数单元和1个双精度浮点单元的并行运行。
缓存总容量、块大小、关联度、替换策略、写策略、多级缓存结构等参数都会影响缓存的性能,需要根据工作负载进行调优。
计算机结构包括处理器、缓存、内存、存储器和输入输出设备。
操作系统将硬件资源进行抽象和管理,使软件可以更方便地使用计算机。
单板电脑如树莓派上也包含处理器、内存、存储和输入输出设备,可以运行操作系统如Linux开展学习。
现实计算机可以同时运行多个程序,这需要操作系统进行资源调度和管理。
操作系统通过虚拟内存实现了内存和存储间的虚拟映射,实现 seemingly “无限”的内存空间。这需要探讨内存和存储的工作原理。
本模块将介绍操作系统的基本功能和原理,以及虚拟内存的实现方法,探讨内存和存储器如何协同工作。
操作系统主要功能包括:资源管理、程序管理、安全管理。
操作系统管理计算机硬件资源,如处理器时间、存储空间、输入输出设备等。保证资源能够高效地被各个程序共享和使用。
操作系统负责程序的加载、执行、结束。多进程操作系统能够同时运行多个程序,需要进行程序调度。
操作系统管理主内存和辅助存储,实现内存管理中的页式存储管理策略。
操作系统管理外设设备驱动,屏蔽硬件差异,实现统一的输入输出访问方法。
操作系统提供文件系统抽象,管理磁盘空间,实现文件创建、读取、修改等操作。
软件与操作系统通信的接口,用于实现资源请求、状态查询等功能。不同操作系统的系统调用接口不同。
常见操作系统如Windows、Linux、Android等,采用不同的设计模式,面向不同领域。
操作系统可以同时运行多个进程。进程管理包含进程调度、状态转换、同步、通信和管理内存分配。
线程是操作系统内部的基本运行单元,一个进程可以包含多个执行流称为线程。线程管理涉及线程创建、调度和同步。
内存管理实现了逻辑地址与物理地址的映射,还实现了内存保护机制。采用分页管理策略。
文件系统将存储设备抽象为文件和目录,实现了文件创建、打开、读写、删除等操作。
I/O管理实现了对外设的统一访问接口,屏蔽硬件差异。包括安装设备驱动程序和完成I/O请求。
程序加载将程序从二进制存储格式加载到内存中,链接器将共享库与程序关联起来。
系统调用接口规定了进程与操作系统间的交互方法。常用系统调用有读写文件、内存管理和进程管理等。
会计管理跟踪各个进程的资源消耗量,实现公平的资源分配和计费。
虚拟内存通过内存管理硬件将逻辑地址映射到物理地址,使每个进程看起来有独立的内存空间。
操作系统将主内存进行逻辑划分为固定尺寸的页面,每个进程也划分为同样尺寸的页面。
页表记录每个进程页面的物理地址映射,由MMU参考页表进行地址转换。每个进程有自己的页表。
若访问的页面未在主存中,需要选择一页用新页面替换,由操作系统负责管理这一动作。
只需扩展地址空间部分位进行转换,效率更高,是现代操作系统不可或缺的一环。
主存由存储单元和外围设备组成,是运行程序的直接硬件。
包括硬盘、固态盘等外部设备,容量大但访问速度慢。
管理进程地址空间与主存页映射,将进程看做在无限的虚拟内存中运行。
当本进程需要的页面不在主存中时,操作系统选择一页进行替换,将其写入存储设备。
存储设备读取写入可能出错,需要采取冗余和错误校验措施防止数据损坏。
相邻访问的页面通常还在 caches和存储设备中的缓存中,可大幅提升访问速度。
主存大小、存储性能和页面置换算法都会影响虚拟内存的整体性能。
内存管理器负责实现虚拟地址与物理地址的映射,提供权限保护机制。
每个进程看到自己独享内存空间,但实际上内存地址会被内存管理器翻译成不同的物理内存区域。
内存管理器将每个进程的虚拟地址转换为对应的物理地址部分,实现多个进程隔离共享内存。
内存管理器根据进程ID划分进程私有内存,防止进程访问其他进程内存或操作系统数据区,实现内存安全。
物理内存空间不足时,内存管理器将部分物理页面内容换出到磁盘,实现动态扩容功能。
内存管理器会将驱动器作为后备存储,将页面内容缓存在Dram中,保证访问速度。
内存管理器需要管理页面读写磁盘的算法,如LRU算法实现更高缓存效率。
此模块主要介绍内存管理器在虚拟内存中的关键作用及其实现原理。
操作系统使用固定大小的页面作为移动虚拟内存和磁盘之间的数据单元。页面大小通常为4KB,是磁盘最小读写单元512字节的整数倍。
每个进程都对应一张页面表,由操作系统负责管理。页面表记录了进程虚拟地址映射到物理页面中的情况。访问内存时,首先通过页面表查找相应物理页地址。
页面表除了记录物理页地址外,还包含一些标志位来表示页面特性,如是否可以共享、是否只读等。这可以实现地址间的保护机制。
处理器根据活动进程提取其页面表,将虚拟地址中的页号部分用于查找页面表,获取实际物理页地址。页内偏移不变,与物理页地址连接后获得最终的物理地址。
页面表太大无法完全缓存,但频繁访问Entry会被CPU缓存,避免多次查找。这样一来,大部分内存访问仅需一次即可取得物理地址。
操作系统按需将页面内容从内存存入磁盘或读回,实现用户程序对内存的动态管理。页面表由操作系统在内核模式下管理,用户空无法直接访问。
页面机制是虚拟内存实现的基础,它通过页面表完成内存与磁盘之间的数据交换以及不同进程地址空间的保护。
操作系统使用固定大小的页面作为虚拟内存和磁盘之间的数据单元。每个进程都对应一张页面表,记录页面是否分配、当前状态等信息。
处理器根据进程提取页面表,将虚拟地址中的页号部分用于查找页面表获得对应物理页地址。如页表有效且页面在内存,直接进行读写;否则触发页错误异常。
页错误异常由操作系统内核模式下的页错误服务程序进行处理。它会更新页面表,若页面在磁盘将其加载到内存;若内存空间不足,需要驱逐页面到磁盘腾出位置。并释放被中断的指令,待有效页面加载后重执行。
如果驱逐页面需要较长时间与磁盘交互,处理器便会触发上下文切换,将CPU时间授予其他待执行进程,以提高整体并行度。页面错误处理完成后,重启原进程继续执行。
虚拟内存体系结构看似无限,但实际受限于物理内存和磁盘存储限额。若应用程序申请超出限额的内存空间,会触发内存不足异常。
页面驱逐写入磁盘采用延迟写回策略,避免频繁磁盘读写带来的性能压力。这与CPU内核缓存采用的写策略有明显区别。
页错误机制实现虚拟内存各类访问的统一处理,是操作系统支撑虚拟内存的重要组成部分。它通过页面表和异常机制完成内存与磁盘间的动态管理。
操作系统使用分层页表管理虚拟内存,解决单级页表导致页表过大的问题。32位环境下常见的两级页表,64位则采用4级页表。
虚拟地址分为偏移与各级页号。页表项存储下一级页表指针或物理页号,采用读写执行权限位控制访问权限。如果所有权限位为0,表示指向下一级页表;否则为页框本身。
RISC-V 32位环境下采用两级页表。虚拟地址分为12位偏移与两10位页号。页表项为32位,高10位存储上级页号,低10位存储下级页号,低12位设置访问权限等位。页表基址寄存器指向首级页表位置。
分层页表布局更充分利用程序内存分布的稀疏性,大多数高级页表项为空,节约页表空间。只需保存根页表基址,即可根据页表结构快速定位物理内存。上下文切换只需修改页表基址寄存器值。
处理器内置TLB缓存最近访问的虚拟到物理地址映射,大大提高页表查找效率。发生缺页时需软件刷新TLB,又引入多级查找加速缓存进一步提高效能。这是分层页表的关键优势。
分层页表机制通过有效利用程序分布特点,很好解决了单级页表空间问题,同时提供了硬件加速优化点,是现代虚拟内存系统的主流方案。
程序使用虚拟地址,通过页表将虚拟地址转换为物理地址访问内存。这个过程很慢,需要多次访问内存。
TLB是任务找到表缓存,位于处理器内部。它缓存了最近的内存到物理地址转换,以加速地址翻译过程。
处理器使用虚拟页号访问TLB,如果命中则直接获取物理页号;如果未命中需要走页表查找Translation,更新TLB和页表。TLB命中率通常超过99.9%。
TLB大小一般为32-512条目,采用全通配或 Set通配搜索。替换算法主要为FIFO。TLB reach决定可以同时映射的最大虚拟地址空间。
TLB位于寄存器和 cache之间,使用虚拟地址访问TLB,得到物理地址后再访问cache。如果cache未命中,需要从内存取数据后更新cache。
处理器使用VPN将地址分成tag和index访问TLB,命中则输出PPN与页偏移衔接形成物理地址,再以TEO格式访问cache。
为五级流水线结构增加两个TLB,分别用于指令缓存和数据缓存的地址翻译。
处理器使用虚拟地址首先查找TLB,如果命中直接获取物理地址;否则需要软件或硬件根据页表进行转换,并更新TLB。
TLB会报告是否存在缺页异常、页面错误或防护违规情况。这需要相应 trap 处理。
缺页需要通过硬件或软件页表走读,更新TLB完成转换。如果页面不在内存,则触发页错误 trap。
页面错误需要取消原指令,通过 trap 机制调用操作系统进行上下文切换等处理。
由操作系统响应并终止产生错误的进程。
通过状态机实现TLB缺页和页表走读。通过信号标识各类异常,并在控制器与 Cache 之间加入 TLB。
TLB机制是虚拟内存系统的重要组成,它通过软硬件协作提升地址转换效率,并处理各类内存访问异常。
缓存块对应虚拟内存页,缓存未命中对应页错误。缓存块大小32-64字节,页大小通常4KB。缓存直接映射或组联相联,虚拟内存页全匹配相联。
缓存用LRU或随机替换,虚拟内存最好LRU但近似FIFO或随机。
缓存可写回写贯通,虚拟内存只写回避免写贯通高开销。
用周期/指令和平均内存访问时间来衡量,考虑TLB、主存、磁盘访问延迟。
给出缓存层级访问延迟和命中率,计算无分页和有分页情况下的平均内存访问时间。
低页面未命中率影响小,高于1/10000;否则性能下降明显,严重情况下程序运行时间延长100-1000倍。
提高页面命中率,避免物理内存不足导致频繁交换页到磁盘,引起系统碎片。
虚拟内存性能主要取决于页面替换算法和页面未命中率,后者决定是否出现Thrashing现象导致明显性能下降。
I/O设备能够连接外部输入和输出设备,实现计算机与外界的交互,如显示屏、键盘、鼠标等。
I/O设备通过标准化的接口与计算机系统通信,接口包含命令寄存器和状态寄存器以及数据寄存器。操作系统负责检查设备状态并管理进程对设备的访问。
I/O设备通过层级总线连接到处理器和内存系统。总线类似高速公路,I/O设备作用类似出入口。
RISC-V使用内存映射I/O,将部分地址空间映射到I/O设备的寄存器,程序通过加载和存储指令访问I/O。
不同I/O设备的数据速率差异很大,键盘几百字节/秒,声卡几百KB/秒,而处理器可达GB/秒。I/O设备速率通常低于处理器。
I/O设备通过标准接口与系统交互,为程序提供外部连接。但I/O设备速率远低于处理器,需要机制解决不匹配问题。
I/O设备通过内存映射寄存器与计算机交互,包含控制寄存器和数据寄存器。
处理器周期性检查控制寄存器的准备信号位,用于判断设备是否可以进行读写操作。
控制寄存器包含准备信号位,用于告知处理器设备是否准备好接收数据或有数据待传输。
数据寄存器用于输入输出设备的数据传输,读入输出数据的位置。
程序循环执行加载控制寄存器,判断准备位状态以决定对数据寄存器的读写操作。
给出设备数据速率和轮询开销,计算轮询所占进程器工作时间比例。
但对产量大数据的设备如硬盘,轮询开销可能超过处理器总时间,需要改进方法。
轮询是简单实现I/O操作的方式,但对高数据量设备效率低,需要更好的协作机制。
I/O设备通过内存映射的控制和数据寄存器与计算机进行通信。
I/O设备在有数据或事件需要报告时,会向处理器发出中断请求,进入中断服务程序进行处理。
轮询效率低下,中断可以避免浪费CPU资源。但高发率中断也会影响性能。
I/O设备有新数据时,或需要通知特定事件时,会引发中断。
中断发生后,当前程序会被挂起,中断服务程序运行,处理I/O请求后恢复原程序。
低速设备直接使用中断,高速设备先中断传输请求,再通过DMA直接内存访问传输大数据。
早期ATA方式,CPU通过加载存储顺序控制I/O,带来一定开销。现在DMA取代其作用。
中断机制最大限度发挥CPU及I/O设备性能,是目前常用的I/O交互方式。高数据设备利用DMA进一步提效。
之前只有CPU能控制数据传输,这给CPU带来很大开销。
提出DMA引擎这个独立的硬件设备,由它取代CPU进行大块数据的传输。
CPU将传输参数写入DMA控制器,DMA自行与I/O设备和内存进行数据传输,传输完成后中断CPU。
大大减轻CPU负担,CPU在DMA传输期间可进行其他工作。
包含传输地址、字节数、设备号、传方向等参数。
以磁盘读写为例,说明DMA如何配合I/O设备和内存进行高效数据传输。
DMA上下文如何与cache体系结合,如果太近会驱逐CPU工作集,如果太远需要实现新的协同机制。
DMA是利用独立硬件补充CPU shortcoming的解决方案,大大提高I/O效率。但其与CPU/cache的集成关系也需要仔细解决。
网络最初是为了在不同计算机之间共享设备,如打印机。后来发展为可以在机器之间传输文件。
文件传输协议(FTP)使得可以直接通过网络传输文件。电子邮件的出现让人们能够在网络上交流。
20世纪60年代,ARPA提出构建连接计算机的网络研究计划(ARPANET)。1969年实现四台计算机的连接,标志着因特网的诞生。
TCP用来实现机器之间的通信,它是互联网协议族的一部分。定义了数据包交换的格式。
80年代提出万维网概念,90年代通过HTTP和浏览器得到广泛应用。极大促进了互联网的普及。
网络层次采用数据包形式的传输,每个包带有地址、校验信息等,保证数据传输的可靠性。
网络卡负责将数据从操作系统通过DMA传输到网络,或从网络接收数据传给操作系统。实现计算机与网络的物理连接。
网络技术使得计算机能够连接在一起,通过标准化的传输协议实现多种应用,极大推动了计算机及信息技术的发展。 抱歉,提供的文档没有为这个标题相关的内容。当前无法根据要求生成知识笔记。
Flynn提出的计算机体系结构分类法,根据指令流和数据流是否独立进行分类。
单指令单数据,指常规顺序计算机。
单指令多数据,使用相同指令同时处理多个数据元素。
多指令单数据,不太常见。
多指令多数据,代表大部分并发和分布式计算机。
利用数据级并行性,同时处理多个数据元素,针对向量/矩阵计算效率提升明显。
x86架构支持SSE和AVX指令集,提供比特、字、双字级运算 unidades,实现向量化。
一个SIMD指令可以同时对四个浮点数进行加法运算。
矩阵乘法内部元素乘加计算可以完全并行执行,符合SIMD模式利用。
SIMD充分利用数据并行性,通过标准指令实现高效向量/矩阵计算。Flynn分类法总结了计算机体系结构的基本模式。
矩阵C是矩阵A和B相乘得到,通过逐个元素相乘累加得到。
采用三层循环遍历各元素,初始化结果为0,内层累加相应元素相乘。
使用相同的三层循环累加算法。利用time.h获取运行时间,计算速度(GFLOPS)。
C语言实现速度快240倍,原因是C无解释执行开销小。
速度保持恒定,超过一定规模后下降,可能与缓存大小有关。
针对矩阵乘法,掌握基础实现和性能测试方法。C语言由于低级特征效率远超Python,指出进一步提速方向。
斯坦福大学教授Michael Flynn提出的计算机体系结构分类方法。
单指令单数据,代表顺序计算机。
单指令多数据,有多个处理单元,一个指令同时处理多个数据元素。
多指令单数据,不常见。
多指令多数据,代表多核处理器和分布式系统。每个处理器都执行不同指令。
单程序多数据,运行同一程序但在不同的数据集上。
Flynn分类法定义的SISD、SIMD、MISD、MIMD体现硬件层面并行计算能力。
软件可以顺序或并发运行,与硬件独立。操作系统采用多任务运行多个进程。
利用专用硬件同时处理向量/矩阵元素,在神经网络和科学计算等领域性能好。
Flynn分类法从指令流和数据流两个维度对计算机体系结构进行分类,为硬件并行设计提供理论基础。
SIMD架构为了利用数据级并行性,一次提取一条指令并应用到多个数据上。
如向量加法会对两个向量的每个元素进行相加,而不是两个标量操作数的加法。同理也可以进行向量乘法。
可以将一个系数矢量与一个数据矢量相乘,实现一些滤波效果。下一步再进行结果加法。
只需要提取一次指令,就可以对多个数据对进行操作,而不是单独提取每条指令。
只要数据从内存或缓存读取的带宽足够大,可以一次获取多个数据,即可发挥SIMD的优势。
20世纪50年代实现第一台SIMD机器TX-2。90年代Intel推出MMX扩展独立指令集。之后SSE、AVX等扩充指令宽度和数目,更好支持SIMD。
从MMX开始在x87浮点/整型/扩展寄存器模式下支持SIMD。SSE增加XMM注册器,进一步提升SIMD执行效率。
利用现代处理器SIMD指令可实现每条指令4次乘法,相比标量指令可提速4倍。但尚未达到理论峰值。
SIMD体系架构通过独立指令集和寄存器,有效支持对向量/矩阵等数据流进行高效并行计算。
SISD separately处理每个数组元素,一次一个;SIMD同时处理多个数组元素。
如求数组元素的平方根,SISD逐个加载、运算、存储;SIMD一次加载4个元素,并行运算后存储。
如SSE加载4 floats到register,并行计算4个平方根操作。
加载两矢量、使用一条指令将它们加在一起,写回到结果矢量中。
使用MOVPS/ADDPS/MOVAPS完成单精度矢量加法,可以从内存取数据并写回。
通过内嵌 intrinsics函数实现单条SSE指令替换,比编译优化有更好性能。
加载/存储和算数指令分别使用_mm_load/_mm_store和_mm_add等前缀。
SIMD通过并行指令提升数据处理效率,Flynn分类法总结了计算机体系结构并行原理。内嵌汇编是开发SIMD程序的常用方法。
授课者使用2×2的矩阵A、B来示意矩阵乘法C=A×B的计算过程。
数据以列式存储格式存储,即同一列元素相邻存储。
使用MOVAPS指令加载A矩阵第一个元素a11和a21到XMM寄存器相应部分。
B矩阵元素存储顺序不同,使用两条指令分别读取b11和b12。
利用FMA指令一次执行乘法和加法,将a11×b11和a21×b12结果累加到C矩阵相应位置。
重复上述步骤计算出C矩阵更多元素,每次指令均对 vectors 进行运算,实现 SIMD 并行计算。
使用C内嵌汇编的方式调用SSE/AVX intrinsic函数,实现矩阵乘法SIMD编程。
总体利用SIMD指令集优势,通过并行计算提高矩阵乘法效率。该示例帮助理解SIMD并行原理和编程方法。
根据Flynn分类法,计算机可以是SISD、SIMD、MISD和MIMD结构。
单指令单数据,代表顺序计算机。
单指令多数据,通过并行处理向量和矩阵来提升效率。
多指令多数据,代表使用多个CPU的并行机。每个CPU独立运行不同的程序。
UMA系统内存对所有CPU同等可达。NUMA系统每个CPU有本地内存,访问非本地内存速度较慢。
GPU采用SIMD并行架构,适合批处理计算。一台GPU上可以有成千上万个并行计算核。
多处理器机、共享内存机、分布式系统等按内存结构和进程交互方式有不同分类。
Flynn将计算问题分为数据并行、任务并行和混合并行三种,对并行算法设计提供参考。
计算机硬件结构类型丰富,层出不穷。Flynn分类法从计算模型角度总结了主流结构,为后续并行编程奠定基础。
将单核CPU中的各组件如控制器、执行单元等复制多个,形成多核结构。
多核系统中每个核都有单独的高速缓存。缓存一致性协议保证缓存数据的一致性。
多核CPU系统采用共享内存,所有核访问同一物理内存,避免传递数据开销。
对称多处理器,多个处理器对等访问共享内存。操作系统支持SMP,将进程调度到多个处理器上运行。
在多核CPU上创建多个轻量级进程线程,操作系统自动进行线程间的映射和调度。
定义多线程编程接口,通过编译器指令实现数据并行的多线程程序。
多个线程操作共享资源时,需要使用锁机制避免竞争条件错误。
线程上下文切换开销、缓存一致性协议开销等影响并行性能。
多核CPU通过较细粒度的并行化来提升单频率性能,但需要管理好并发操作。
线程是比进程更轻量级的计算单元,它共享进程的代码和数据空间。
提高 CPU 利用率,隐藏 I/O延迟。
线程可能处于运行、就绪、阻塞三种状态之间转换。
多个线程访问共享资源需采用锁、信号量、读写锁等方式同步。
POSIX 线程接口 pthread_create 创建新线程;Win32 接口 CreateThread。
pthread_join 等待线程结束;pthread_exit 终止线程;pthread_cancel 取消线程。
pthread_mutex_lock 获取锁;pthread_mutex_unlock 释放锁;pthread_cond_wait 等待条件。
使用 omp parallel 来指定区块中创建线程;使用排他锁 omp critical 同步访问共享资源。
线程引入更细粒度并行单位。线程管理需要控制并发冲突,接口提供了丰富的同步原语来实现。
服务器应用、图形操作、科学计算都适合使用多线程实现。
操作系统将应用程序逻辑线程映射到物理CPU核上执行。
操作系统根据线程优先级动态调度执行顺序。
频繁切换会导致开销,需要合理利用时间片避免开销。
使用锁、条件变量、信号量等同步原语保证线程安全。
CAS操作等原子指令保证对共享数据的并发访问一致性。
每个线程可以有自己的栈空间和私有变量,避免竞争。
并行度过高反而降低效率,需要匹配计算资源数量。
多线程充分发挥多核CPU优势,但需要解决同步争用问题,谨慎设计便能提高效率。
Flynn分类法下的并行计算类型包括SISD、SIMD、MISD和MIMD。
现代CPU采用Pipeline、超标量技术实现指令级并行(ILP)。
多核CPU采用UMA或NUMA模型,保证多个核对内存的一致访问。
线程创建、同步原语如锁、条件变量、信号量等保证线程安全。
使用pragma注解来指定并行区域和线程数,简化多线程编程。
GPU采用SIMD架构,适用于数据并行和单指令流任务。CUDA规定GPU编程接口。
多个节点合作完成同一任务,需要任务分配和节点通信支持。
考虑工作量均衡、最小通信成本等原则来提升算法并行性。
总结了计算机体系结构多个层级的并行方式,并指出如何利用这些并行资源进行高性能计算。
介绍目前主流的并行编程语言,包括C/C++、OpenMP、MPI、MapReduce等。
Go语言在并行设计上较清晰,专家认为可能是未来路径。但作者本人只进行过简单尝试。
内置函数是直接插入汇编指令的方式,因为编译器不支持自动生成这类指令。
编译器在单线程优化上表现出色,但自动并行化代码仍然是个开放问题。
将C/C++代码自动并行化难度大,需要编译器理解程序并行度及优化依赖关系。
不同语言针对不同规模场景进行优化,如科学计算、分布式计算等。
先介绍OpenMP,再介绍MapReduce框架,为高性能计算培养基础。
总体介绍主流并行编程语言特点,以及自动并行化C/C++代码的难点。
OpenMP是一个用来进行多语言并行编程的应用程序接口(API)。
1 明确并行区域:使用#pragma omp parallel来标识。2 动态线程:线程数由系统管理。
使用#pragma omp parallel for构造中,for循环按线性顺序分块给线程执行。
omp_get_num_threads()获取线程数;omp_get_thread_num()获取当前线程ID。
数据默认共享所有线程,解决数据依赖问题。private变量线程私有。
使用#pragma omp barrier同步线程;#pragma omp critical进入临界区保护共享数据。
使用#pragma omp simd指示SIMD向量计算优化for循环。
OpenMP提供接口获取运行信息,帮助分析和调优程序性能。
OpenMP提供高层次的并行编程模型,简化多线程编程难点。它允许以增量方式加入并行能力。
利用圆周率π可以用整数集合求和表示:π/4 = 1 - 1/3 + 1/5 - 1/7 + …
使用for循环逐项累加求和估算π的值。
将for循环使用#pragma omp parallel for并行化,每个线程计算一部分求和项。
以4个线程为例,原问题分成4份平分给每个线程处理。
定义执行时间和π值的全局变量,避免在线程里定义局部变量导致发生race condition错误。
并行程序利用多核CPU,与增加线程数成正比提升计算速度,但超出核数后效率下降。
以Pi值估算为例,说明OpenMP如何实现算法并行化,克难数据争用问题,以及线程数对性能的影响。
在并行编程中,如何协调多个线程访问共享资源,防止竞争条件(race condition)产生错误结果。
利用锁(lock)和信号量(semaphore)实现资源互斥访问,一个线程获取锁后执行,释放锁让其他线程执行。
利用while循环检测锁状态,上锁修改共享资源后解锁,但这种方式可能还是存在竞争条件。
展示了如果两个线程同时检查锁状态并上锁,都可能错误地认为已获取锁的情况。
处于C代码层级无法完全避免竞争条件,需要在指令层级实现原子操作来保证同步正确性。
打开并行编程的重要一课。以后的课将介绍如何在指令层面实现原子锁机制来完美解决同步问题。
在软件层级实现同步存在竞争条件问题,需要依靠硬件实现原子性操作来保证正确性。
现代CPU内部拥有多个执行单元可以并行执行操作,但只允许原子性的读写操作。
原子操作是一次性、不可打断地完成的基本任务,无论在硬件或软件层面都不允许中断。
操作系统调度器负责管理多个线程并发执行,决定何时屏障线程和切换上下文。
CPU引入特殊寄存器对内存进行并发访问控制,包括比较交换指令实现原子锁机制。
线程等待锁的同时进入休眠状态,被唤醒后再检查锁状态实现同步。
本次课说明了同步问题需借助CPU的原子指令硬件支持,并介绍了操作系统调度在线程同步中的关键作用。
SMP系统由多个相同的CPU核心组成,共享同一内存空间。每个核心都有多个级别的私有缓存。
缓存通过将最近和频繁使用的数据缓存在本地,来减少访问主内存的延迟。只有在缓存未命中时才需要访问主内存。
示意两个CPU核心同时从地址1000处读取整数20,过程中检查私有缓存,在缓存未命中时访问主内存。
当CPU0核心对地址1000写入整数40时,私有缓存和主内存都被更新。但CPU1和CPU2核心缓存中数据依然是旧值20,产生一致性问题。
多个CPU核心对共享内存进行读写时,由于存在私有缓存,可能会导致内存值在不同核心中的视图不一致。
本次课说明了SMP系统结构,并通过示例讨论了缓存带来的内存一致性问题。
在SMP系统中,每个CPU核心都有自己的缓存。修改共享内存值后,其他CPU核心缓存中的值可能会保持不一致。
硬件通过缓存一致性协议,来确保在共享内存系统中,缓存中的数据能及时反映主内存中的最新值。
MESI协议是一种缓存一致性模型。缓存块状态可能是:Modified(修改)、Exclusive(独占)、Shared(共享)、Invalid(无效)。
缓存块在进行读写操作时,状态会进行转换。例如写入后转为Modified状态,其他CPU读取时进入Invalid状态。
CPU核心之间通过总线或交换机共享缓存信息。地址比较可以检测状态变化,需要时 invalidates 或 updates其他缓存。
缓存一致性协议保证任何时刻,系统中对同一地址的缓存只有一个有效拷贝,实现了内存的一致性视图。
本次课介绍了缓存一致性问题及MESI协议,说明硬件如何通过状态机制管理缓存,保证系统内存一致性。
阿姆达尔定律描述了通过并行化改进系统性能的限制。它考虑了任务中的串行部分和并行部分。
总速度提升=1/(s+((1-s)/p))
其中,s表示任务的串行部分比例,1-s表示并行部分比例,p表示并行部分的加速比。
如果任务的80%可以并行化且加速16倍,则串行部分是20%,并行部分加速16倍,总速度提升是4倍。
如果并行部分可以趋近100%,随着核心/进程数量增加,最大速度提升趋于1/s。
要最大限度提升性能,需要尽量减少任务的串行设置和汇总部分,使任务达到“令人尴尬的并行”状态。
本课介绍了阿姆达尔定律,说明系统提升性能存在上限,应追求尽量减少任务的串行部分来最大限度地利用资源。
处理多个独立请求,每个请求可以并行执行。例如web服务器可以同时处理来自不同用户的请求。
同一大型计算任务可以划分为多个小任务并行处理。例如计算π可以分配给多个进程每个计算一个片段的和,最后汇总结果。
MapReduce支持数据级并行计算。它把一个大计算任务分割成多个独立的map任务和reduce任务。
map任务处理键值对并产生中间结果。reduce任务把中间结果汇总为最终输出。框架负责任务调度和汇总。
请求级并行:处理多个完全独立的应用程序。
数据级并行:把一个应用程序的计算拆分为多个任务处理不同数据片段。每个任务可以并行运行。
Spark支持把数据和计算进行物理分离。任务可以在不同节点上运行,同时访问共享的数据集,实现更高并行度。
本课介绍了请求级和数据级并行两种模式,MapReduce和Spark支持数据级并行 计算大型数据集。Spark支持请求级并行并可以分离数据和计算提高利用率。
MapReduce进程包括Map和Reduce阶段,框架管理任务调度和数据移动。
应用程序发送Map任务进行数据切分处理,产生<key,value>对输出到磁盘临时文件。
框架将Map输出中间结果根据key进行分组,排序后写到磁盘分区文件。
应用程序发送Reduce任务来处理对应的分区文件,按Key进行汇总计算最终结果输出。
自动化资源管理,隐藏复杂细节。支持高负载并行计算。
将文档映射成<词,文档Id>对,使用词为Key进行分组,统计各词出现文档列表。
MapReduce定义了通用的并行计算模型,于应用程序隔离资源管理细节。
内存计算框架,用户程序在内存中运行,速度快于MapReduce。支持迭代算法。
Resilient Distributed Dataset,弹性分布式数据集,Spark的主要抽象。
转换操作可以计算新的RDD(映射、过滤等)。行动操作会真正触发计算(收集结果)。
RDD可以在内存中进行计算,或存储在磁盘上。Spark自动管理数据位置。
Spark会将RDD操作转化为DAG图,统一交由驱动程序协调节点执行,动态调度任务运行。
RDD记录依赖关系可以重新计算丢失部分。支持认为计算。
本地模式运行一个驱动程序。集群模式运行在多个节点上的分布式程序。
Spark简化了分布式计算,驱动内存计算和容错能力,适合互联网大规模数据处理。
WSC(Web Search Challenge)项目通过构建搜索引擎来学习分布式系统及MapReduce模型。
倒入BBC新闻数据集,构建倒排索引。通过词搜索文档。支持顺序分页以及根据日期搜索结果排序。
Map阶段将文档分割,输出<词,文档Id>对。Reduce阶段聚合词,输出<词,包含该词文档Id列表>。
使用Hadoop实现MapReduce任务执行。任务在集群中并行计算。整个过程在HDFS文件系统上保存中间数据。
提供HTTP接口获取搜索结果词条总数、每页文档Id列表等。连接数据库存储索引数据实现动态更新。
WSC项目实践中应用MapReduce模型进行大规模数据处理,理解了分布式系统各个组件的协作。
1950-1960年代:计算机体积巨大,主要部件需要人体大小。只部署在大公司和研究机构。
1970年代:带来C语言和UNIX操作系统。计算机价格下降到每台几万美元。
1980-2000年代:个人电脑时代兴起,计算机开始进入家庭。价格下降到每台几千美元。
2000年后:智能移动设备时代。苹果、诺基亚等公司推出手机,价格下降到每台几百美元。
摩尔定律推动了VLSI微积管技术和多核处理器的应用,提升了单个处理器性能。
存储层次结构发展带来程序局部性原理,提升了内存访问速度。
软件与硬件的互相驱动使计算机应用范围不断扩大。
1950-1960年代计算机主要部件如CPU需要人体大小,包含大量磁带驱动等外部I/O设备。
本课介绍了计算机硬件发展历史及技术驱动因素,从巨大机器到个人智能设备的变迁。
通用指企业建设的中型-大型数据中心,机房规模以万+服务器规模计。
Google数据中心一般包含10万+个服务器。单独机房可达数万服务器。
Facebook数据中心也包含10万+服务器。亚马逊云计算中心服务器数量达数十万。
通过海量低成本标准化硬件,实现极高规模的计算能力。
自动化管理软件控制整个数据中心实时运行状态。
冗余设计可以容错,基础架构24小时运行。
支持企业IT系统,搜集互联网大数据,推动人工智能和机器学习等新技术研发。
提供云计算能力,用户通过网络访问随需provision的IT资源服务。
极大降低IT资源采购和运行成本。推动云原生应用开发。
极大扩展企业IT能力边界,引领新一波计算机革命。
本课介绍了大规模仓储级计算概念,数据规模和特点,在云计算等领域产生的影响。
PUE(Power Usage Effectiveness)用于衡量数据中心的能源利用效率,它是一个非绝对的指标。
PUE = 整个数据中心的总功率/IT设备(服务器等)实际消耗的功率
通常认为1.5以下的PUE值已经相对优秀。一线大型互联网公司数据中心PUE在1.1-1.3之间。
通过优化电源系统、冷却系统设计,利用供热回收;采用更高效服务器硬件;提升IT资源调度效率等措施来降低非IT设备消耗比例。
有效降低数据中心运行成本,节约能源开支。与环保目标相匹配。
但PUE本身并不能完全衡量数据中心绿色效益,还需考虑电源来源发电方式等因素。
本课介绍了评估数据中心能源效率的重要指标PUE,以及如何通过技术手段优化PUE水平。
系统可靠性指在给定时间和条件下,系统正确地完成功能的能力。关键在于识别并纠正系统失效的根本原因。
设计系统需要考虑不同因素对可靠性的影响,并采取措施使系统不断运行的可能性最大化。
硬件故障、软件错误、操作失误、意外情况都可能导致系统失效。无法预测的失效最难处理。
冗余设计、错误检查、容错处理、安全机制设计、日志记录、自动修复、灾备切换等。
WSC搜索引擎项目加入日志记录功能,通过分析错误日志找出问题所在并修复代码缺陷,提高系统稳定性。
MTBF(平均故障间隔时间)、MTTR(平均修复时间)、可用时间率等指标用于描述系统在特定条件下的可靠性水平。
本视频总结介绍了系统可靠性基本概念、目标、影响因素以及提高可靠性的常用方法。
随着计算机应用范围广泛,系统可靠性成为重要一环。计算机可能会出现暂时或永久性故障。
软件错误、硬件错误、极端环境等都可能导致计算机失败。硬件错误可能由于组件老化或施工质量问题引起。
使用多个计算单元并行工作,通过投票机制避免单点故障影响系统。GPU芯片中的冗余内核即采用这一设计。
DRAM中带有额外的校验芯片,通过奇偶校验检测和纠正错误。磁盘阵列RAID也采用冗余设计提高可靠性。
数据中心或硬盘阵列通过冗余设计可容忍临时性组件故障,系统整体性能不受影响。
本课介绍了计算系统可靠性的重要性,以及通过冗余设计提高可靠性常用方法,为后续内容奠定基础。
可用时间率=系统成功运行时间/总运行时间。衡量系统在一定时间内可靠运行的能力。
MTBF=总运行时间/出现故障的次数。指系统在没有故障的平均运行时间。
系统出现故障后,恢复成功运行状态的平均时间。
λ=故障次数/总时间。以每单位时间发生故障的概率来表示系统故障频率。
PFD=λ*MTTR。指系统未正常工作的概率,体现了容错设计带来的可靠性提升效果。
通过冗余设计减少MTTR,降低λ,从而提高系统可用时间率和MTBF,降低PFD,即提升系统整体可靠性。
以上指标在设计和评估系统可靠性时提供了定量参考。
奇偶校验是一种最简单的错误检测方法。计算数据和的奇偶位进行校验,可检测单位错误。
4比特数据:0110,奇偶位为0。错误为0111,奇偶位不匹配,发现错误。
通过计算多组数据在不同位上的奇偶位,可以检测多个位错误。
ECC通过添加冗余校验位,可实现单个错误更正或多个错误检测。BCH码、汉明码等都是ECC的实现方法。
DRAM中加入ECC校验位,可在读取前进行校验并更正单位错误,大幅提升可靠性。
通过磁盘块数据间奇偶校验,RAID1等级实现跨磁盘检测。RAID6级支持多个磁盘错误检测。
以上方法通过添加冗余校验信息实现硬件组件的错误检测功能,为后续容错提供依据。
通过计算数据和的奇偶位实现单个错误检测。但无法定位错误位置。
增加冗余校验位,构建足够大的哈密顿距离。可实现单个错误定位与更正,或多个错误检测。
以8个编码字为例,通过cube形式直观表示不同编码字与其距离。
选择部分编码字构成ECC码。其他编码字视为错误字,与最近有效字的距离为1。
取3bit编码空间中两种距离最大编码字构成ECC码。可定位单 bit错误并更正。
扩展到多字节情况,通过划分子码来实现多bit错误更正。
读取编码字->判断有效性->若非有效,选择距离最小有效字进行更正。
本节从原理入手,通过图解例子解析ECC原理及其实现错误更正的能力。
将数据位和奇偶位交错排列形成码字,奇偶位对应的二进制位为2的幂次。
第一位奇偶校验P1覆盖所有奇数位,第二位P2覆盖相邻数据位对,第三位P3覆盖4位组等。
给出8位数据,计算4位奇偶校验后形成12位码字。明确各奇偶位对应的包络数据位。
接收码字后按奇偶位定义检查各组合,发现错误后计算错误位进行更正。
改进的哈密顿码支持2位错误校正或更多错误检测能力。但不在本课程范围内。
如循环冗余校验等应用于比如网络传输中错误更为严重的场景,提供不同的容错机制。
本节通过实例详细解释了ECC编码和码字检验验证的过程,为后续内容奠定基础。
我们可以使用额外的硬件来实现空间冗余,如使用额外的比特或校验位来检测和纠正错误。
使用单个额外比特即可实现奇偶校验,判断数据是否包含奇数个1。如果检测到奇数个1,那么校验位为1,否则为0。这样可以检测单个错误。
哈米尔顿码使用3的距离,可以检测单个错误并纠正它。此外添加一个校验位可以实现双错误检测。
RAID(冗余磁盘阵列)是一种使用多个独立磁盘来实现数据冗余的技术。RAID1使用镜像来提供冗余,RAID3和RAID4使用带奇偶校验的条带化,RAID5将校验信息分散到所有磁盘上以提高吞吐量。如果任何一块磁盘发生故障,系统可以使用冗余信息重建失效磁盘的数据。RAID技术可以提高可用性,避免单点故障对系统服务的影响。RAID还可以实现并行I/O操作以改善性能。
递归可以把一个复杂问题分解成子问题的 Repeated call 解决,实现 Top-down 设计。递归需要基本情况和递归情况两种情况。
函数调用和返回会使用栈来保存相关信息。函数调用时会将参数等信息压入栈,函数返回时弹出栈———.
斐波那契数列、阶乘、目录遍历等问题都可以使用递归或迭代两种方式进行解决。需要考虑基本情况和递归情况。
将问题划分为子问题求解,再合并结果。快速排序就使用分治思想,将数组分区后递归调用。
使用记忆化搜索避免重复计算,滚动数组等方法降低时间复杂度。背包问题、最短路径等问题使用动态规划。
Python使用异常处理实现错误处理。try-except捕获异常,finally执行清理操作。编码时需要预料异常情况。
模块达到复用和解耦的目的。增加可维护性。包进一步组织模块,使用同一个顶层包装起来。
总结视频重点梳理了递归、栈、分治、动态规划等算法思想,以及Python中的异常处理与模块设计原则。