Planet X

《体系结构》复习笔记

第一章 引言

1.1 计算机体系结构的研究内容

  • 为什么按一下键盘,PPT会翻一页?

    ​ 按一下键盘,键盘会产生一个信号送到南桥芯片南桥芯片键盘的编码保存在一个寄存器中,并向处理器发送一个外部中断信号

    外部中断信号传到CPU,把CPU内部的一个称为Cause控制寄存器的某一位置为1,表示收到了外部中断CPU中另一个称为Status控制寄存器屏蔽位来确定是否处理这个外部中断信号。

    ​ 经过屏蔽处理后的中断信号被附在一条译码指令上送到重排序缓冲(Re-Order Buffer),当这条指令成为ROB里的第一条指令时,CPU处理例外(外部中断是例外的一种)。

    ​ 重排序缓冲为了给操作系统一个精确的例外现场,处理例外前要把例外指令前面的指令都执行完,后面的指令都取消掉。

    ​ 重排序缓冲向所有的模块发出一个取消信号,取消该指令后面的所有指令。修改控制寄存器,把系统态设置为核心态,保存例外原因、发生例外的程序计数器等到指定的控制寄存器中。然后把程序计数器的值置为0x80000180 这个例外处理入口地址

    ​ 处理器跳到0x80000180后执行操作系统代码,操作系统首先保存处理器现场,包括寄存器内容等。保存现场后,操作系统向CPU的控制寄存器例外原因,发现是外部中断例外,就向南桥的中断控制器读中断原因,读的同时清除南桥的中断位。读回来发现中断原因是有人敲了空格键。

    ​ 操作系统接下来查看空格键是给谁的:有没有进程处在阻塞态等待键盘输入。发现有一个名为PowerPoint的进程处在阻塞态且对空格键会有相应,于是唤醒PowerPoint。

    ​ PowerPoint发现传来空格键,表示用户的请求是翻页,于是准备好下一页要显示的内容,调用操作系统的显示驱动程序,把要显示的内容送到显存,由GPU通过访问显存刷新屏幕。

  • 计算机系统的结构层次

    • API(应用程序编程接口)是建立生态的起点,ISA(指令系统)是软件兼容的关键,是生态建设的终点。
    • APIISA之间还有一层ABI(应用程序二进制接口),ABI是应用程序访问计算机硬件及操作系统服务的接口。
  • 冯诺依曼结构
    • 控制器、运算器、存储器、输入设备、输出设备
    • 负责计算的部分是由运算器和控制器组成的,称为中央处理器。
    • 负责记忆的部分称为存储器。
    • 核心思想:数据和程序都存在存储器中。CPU从内存中取指令和数据进行运算,并且把结果也放在内存中。概括起来就是存储程序和指令驱动执行。

1.2 衡量计算机的指标

  • 完成一个任务需要的时间 = 指令数 × 每条指令需要的拍数 × 每拍需要的时间
    • 指令数与算法、编译器和指令功能有关
    • 每条指令需要的拍数与编译器、指令功能、微结构设计有关
    • 每拍需要的时间就是时钟周期,与结构、电路设计、工艺等因素有关
  • CPI:Cycles Per Instruction.
  • IPC:Instructions Per Cycle
  • 芯片功耗:主要由晶体管产生。对于一个由PMOS管和NMOS管组成的反相器,其功耗主要可以分为三类:开关功耗、短路功耗、漏电功耗

1.4 体系结构设计的基本原则

  • 平衡性
  • 局部性
  • 并行性
  • 虚拟化

第二章 指令系统结构

2.2 指令系统设计原则

  • 兼容性
  • 通用性
  • 高效性
  • 安全性

2.3 指令系统发展历程

  • 分类
    • 复杂指令集(CISC, Complex Instruction Set Computing)
    • 精简指令集(RISC, Reduced Instruction Set Computing )
    • 超长指令字(VLIW,Very Long Instruction Word)
      • 本质上是多条同时执行的指令的组合
  • CISC:早期的CPU处理速度慢,设计者不得不加入越来越多的复杂指令来提高运行速度。简化了软件和编译器的设计,显著提高了硬件的复杂性。CISC结构出现了一些问题,复杂指令很少使用,80%的指令只占指令总数的20%。
  • RISC:RISC指令功能简单,单个指令执行周期短;定长指令,译码简单;访存只能通过load-store来实现。简单化的设计有利于实现高效流水线、多发射等技术,从而提高主频和效率。
  • VLIW:VLIW结构的最初思想即最大程度利用指令级并行。
  • 存储管理的演变
    • 连续实地址:各程序所需的内存空间连续存放,并保证不与其他程序产生冲突。
      • 难以管理,大量内存碎片。
    • 段式存储:内存分为多个段和节,地址组织为相对于段地址的偏移。
      • 虚拟地址分为段号和段内偏移两部分。由段长度和基址得到对应段的起始物理地址,再加上段内偏移,得到最终的物理地址。段内地址需要连续,仍然存在内存碎片问题。
    • 页式虚拟存储管理:将各进程的虚拟内存空间划分为若干长度相同的页,将虚拟地址和物理地址的对应关系组织为页表,并通过硬件(TLB)来实现快速的地址转换。
      • 虚拟地址分为虚拟页号和页内偏移两部分。地址转换时根据虚拟页号检索页表,得到对应的物理页号,与页内偏移组成最终的物理地址。
    • 段页式管理:结合了段式和页式的特点。
      • 虚拟地址分为段号、虚拟页号和页内偏移三部分。地址转换时先根据段号查询段表得到对应段的起始物理地址,再根据虚拟页号查询页表得到物理页号,与页内偏移组合得到最终的物理地址。
  • 运行级别的演变:
    • 无管理 -> 增加保护模式 -> 增加调试模式 -> 增加虚拟化支持
    • 现代操作系统包含保护模式,将程序分为两个权限等级:用户态核心态

第三章 指令集结构

3.1 地址空间

  • 每条指令都是一个操作的描述,主要包括操作码操作数操作码规定指令功能,例如加减法;操作数指示

操作功能。

  • 处理器可访问的地址空间包括寄存器空间和系统内存空间。寄存器空间包括通用寄存器、特殊寄存器和控制寄存器。寄存器空间通过指令及编码于指令中的寄存器号进行访问;系统内存空间通过访存指令进行访问。
  • 现代MIPS处理器中包含32个整数通用处理器和32个浮点通用寄存器。
  • 控制寄存器用于控制指令执行的环境,比如核心态还是用户态
    • Cause寄存器:标记异常和中断发生的原因。
    • EPC:异常程序计数器,异常和中断处理结束后的重新执行地址。
    • Count&Compare:组成一个简单但有用的高精度内部计数器。
    • BadVaddr:存放导致地址相关异常的程序地址。
  • 根据指令使用数据的方式,可以分为堆栈型、累加器型、寄存器型
    • 堆栈型:操作数在栈顶,在运算指令的过程中不需要指定操作数,默认对栈顶数据进行运算并将结果压回栈顶。
    • 累加器型:包含一个隐含操作数——累加器,另一个操作数在指令中指定,结果写回到累加器中。
    • 寄存器-存储器型:每个操作数都由指令显式指定,操作数为寄存器或者内存地址。
    • 寄存器-寄存器型:每个操作数都由指令显式指定,但除了访存指令,其他指令的操作数只能为寄存器。
    • 早期计算机经常使用堆栈型和累加器型指令系统,主要目的是降低硬件实现的复杂度。当今的指令系统主要是寄存器型,并且是寄存器-寄存器型,优势在于访问速度快,便于编译器的调度优化,并且可以充分利用局部性原理。另一个优势是,寄存器之间的相关性容易判断,容易实现流水线、多发射和乱序执行等方法。

3.2 操作数

  • 在执行访存指令时,要考虑访存地址是否对齐和指令系统是否支持不对齐访问。所谓对齐访问是指对该数据的访问起始地址和结束地址都符合其数据长度。以X86为代表的CISC指令集通常支持不对齐访问,而ARM、MIPS等RISC处理器只支持对齐访问。
  • 尾端问题(Endian):最高有效字节的地址较小的是大尾端,最低有效字节的地址较小的是小尾端。(?)
  • 寻址方式:寄存器寻址、立即数寻址、偏移量寻址、寄存器间接寻址、变址寻址、绝对寻址、存储器间接寻址、自增量寻址、自减量寻址、比例变址寻址。

3.3 指令操作和编码

  • 从功能上来分,指令可分为四大类:
    • 运算指令
    • 访存指令
    • 转移指令,控制程序的流向
      • 转移条件和转移地址是转移指令的两个要素。
    • 特殊指令
  • 指令编码:CISC长度可变,编码自由。RISC长度固定。MIPS指令集的三种编码格式为:
    • R型 寄存器类指令 | OP | RS1 | RS2 | RD | SA | OPX |
    • I型 立即数类指令 | OP | RS1 | RS2 | Immediate |
    • J型 转移类指令 | OP | Target |
    • OP 操作码, OPX 辅助操作码, RS源操作数寄存器, RD目标操作数寄存器, Immediate 立即数, Target指令的目标地址, SA Special Area。
  • 延迟槽技术:条件转移指令的后一条指令为延迟槽指令。有些指令集规定延迟槽指令无论是否跳转都要执行。MIPS实现了延迟槽。但对于当今常用的动态流水线和多发射技术而言,延迟槽技术则没有使用的必要。
  • LWL/LWRLWL指令读取访存地址所在的字并将访存地址到该字中最低位字节拼接到目标寄存器的高位LWR指令读取访存地址所在的字并将访存地址到该字中最高位字节拼接到目标寄存器的低位

3.5 C语言的机器表示

  • 过程调用:
    • 调用者(S)将参数(实参)放入寄存器或栈中。
    • 使用JAL指令调用被调用者(R)
    • R在栈中分配自己所需要的局部变量空间
    • 执行R过程
    • R释放局部变量空间
    • R使用JR指令返回调用者S

第四章 异常与中断

计算机通常按照软件的执行流进行顺序执行和跳转,但有时会需要中断正常的执行流程去处理其他任务,可以触发这一过程的事件统称为异常

4.1 异常分类

  • 中断(外部事件):来自CPU核外部的事件,来自处理器内部其他模块或者处理器外部的真实物理连线,也成为中断
  • 执行指令中的错误:例如不存在的指令、除法除以0、地址不对齐、用户态调用核心态指令。
  • 数据完整性问题:例如存储器发生校验错误。
  • 地址转换异常:存储管理单元对一个内存页进行地址转换,而硬件转换表中不存在对应的转换项。
  • 系统调用和陷入:由专有指令产生,目的是产生操作系统能识别的异常,用于在保护模式下调用核心态的相关操作。
  • 需要软件修正的异常:常见的为浮点数导致的异常,对于某些操作和操作数的组合,硬件由于实现的原因不愿意处理,寻求软件的帮助。

4.2 异常处理

异常处理的流程通常是:异常处理准备、确定异常来源、保存执行状态、处理异常、恢复执行状态并返回。

  • 异常处理准备:
    • 精确异常:发生异常时,被异常打断的指令(EPTR)前的所有指令都要执行完,后面的指令都像没有执行一样。
  • 确定异常来源:
    • X86由硬件进行异常和中断号的查询,并根据编号查询预设好的中断描述符表(IDT)得到不同的异常处理地址。
    • MIPS将异常相关状态存于Cause寄存器,由异常处理程序进一步查询和区分处理。
  • 保存执行状态:通常至少需要将通用寄存器程序状态字寄存器的值保存到中。同时根据需要关闭或保留部分中断使能,防止异常处理过程中产生新的中断影响程序执行状态。
  • 处理异常
  • 恢复执行状态并返回

4.3 中断

  • 中断在外部事件想要获得CPU注意时产生。

  • 与X86类似,MIPS处理器包含两种类型的中断输入:可屏蔽中断(INT)不可屏蔽中断(NMI)。MIPS处理器中NMI的处理入口地址与重启一致,即触发NMI会导致系统重启。

  • 中断的优先级

    • 软件维护一个中断优先级(IPL),每个中断源都被赋予特定的优先级。
    • 正常状态下,CPU运行在最低优先级。
    • 当处于最高优先级,任何中断都被禁止。
    • 更高优先级的中断可以抢占低优先级的中断。
  • 中断的原子性:在MIPS中,原子性采用LL(Load Linked)SC(Store Conditional)指令。由硬件维护一个LL bit, 在LL指令访问某内存地址后,若该地址被改写则修改LL bit的状态,执行SC指令时检查LL bit来确认原子性。

    LL 指令的功能是从内存中读取一个字,以实现接下来的 RMW(Read-Modify-Write) 操作;SC 指令的功能是向内存中写入一个字,以完成前面的 RMW 操作。LL/SC 指令的独特之处在于,它们不是一个简单的内存读取/写入的函数,当使用 LL 指令从内存中读取一个字之后,比如 LL d, off(b),处理器会记住 LL 指令的这次操作(会在 CPU 的寄存器中设置一个不可见的 bit 位),同时 LL 指令读取的地址 off(b) 也会保存在处理器的寄存器中。接下来的 SC 指令,比如 SC t, off(b),会检查上次 LL 指令执行后的 RMW 操作是否是原子操作(即不存在其它对这个地址的操作),如果是原子操作,则 t 的值将会被更新至内存中,同时 t 的值也会变为1,表示操作成功;反之,如果 RMW 的操作不是原子操作(即存在其它对这个地址的访问冲突),则 t 的值不会被更新至内存中,且 t 的值也会变为0,表示操作失败。

  • 向量化中断:在传统的MIPS指令系统中,中断处理程序的入口地址是一个固定的位置,在后续的异常处理程序中再进行中断源的区分和处理。而在新的规范中,增加了向量化中断和EIC模式中断,可以减少中断处理过程中区分中断源的代价。打开向量化中断时,8个可屏蔽中断将有各自独立的入口地址。EIC模式将6个硬件中断输入改为6位中断编码。

  • 中断传递机制

    • 中断线:系统资源不多时,直接连接到处理器引脚即可,若中断源较多,可使用中断控制器汇总后再连接到处理器。此方法扩展性不强。其次,中断处理过程中,需要查询中断控制器和设备中的状态寄存器来判断中断原因,有较长延迟,效率不高。
    • 消息中断:以数据的形式在总线上传递。发中断就是往指定地址写一个指定的数。具有较高的扩展性和灵活性。

第五章 存储管理

5.1 存储管理的原理

  • 处理器的存储管理软件(MMU)支持虚实地址转换多进程空间等功能,是通用处理器体现“通用性”的重要单元,也是处理器和操作系统交互最紧密的部分。
  • 存储管理构建虚拟的内存地址。作用和意义有:
    • 隐藏和保护。用户态程序只能访问kuseg内存区域的数据,其他区域只能由核心态程序访问。
    • 为程序分配连续的内存空间:由分散的物理页构建连续的虚拟内存空间。
    • 扩展地址空间。
    • 节约物理内存:多个程序共享页面。
  • TLB:又称为转换后援缓冲器或快表,借由局部性原理,存储当前处理器中最经常访问页的页表,用于实现快速的虚实地址转换。
  • 处理器用地址空间标识符(Address Space Identifier, ASID)虚拟页号(Virtual Page Number, VPN)在TLB中进行查找匹配,若命中则读出其物理帧号(Physical Frame Number,PFN)和标志位。
    • 标志位用于判断该访问是否合法,一般包括是否可读、可写、可执行等。若非法则发出非法访问异常。
    • 若未在TLB中命中,则产生TLB缺失异常,由异常处理程序完成TLB重填。
  • 为了降低页表存储开销,操作系统通过多级页表管理来提高页表内存的使用效率。引入多级页表的原因是为了避免把全部页表一直保存在内存中。

5.2 TLB的结构和使用

  • MIPS存储管理的核心部件是TLB。MIPS的TLB采用全相联查找方式。考虑到TLB处于访存流水线的关键路径上,其容量不能太大,通常设计为32项或64项。
  • VPN2:虚拟页号。MIPS指令系统的一个特点是每项把两个连续的虚拟页映射为两个物理页。
  • ASID:标记该TLB表项属于哪个地址空间,用于区分不同进程的页表。只有CPU中当前的ASID号与该域相同才能命中。
  • G:全局域,为1时关闭ASID匹配,表示该TLB表项适用于所有的地址空间。
  • MASK:用于TLB查找时控制VPN2的低位是否参加地址比较
  • PFN:物理帧号
  • C:表示对应物理页的Cache算法
  • D:写控制位,为1时表示允许对该页写入
  • V:有效位,表示对应的物理页是否在内存中

  • MIPS指令系统TLB相关控制寄存器:

  • MIPS指令集规定了TLBR、TLBWI、TLBWR和TLBP这4条指令用于访问TLB。

    • TLBR指令用Index寄存器值作为索将引TLB表项的值读到Pagemask、EntryHi、EntryLo0和EntryLo1控制寄存器中。
    • TLBWI、TLBWR分别以Index寄存器和Random寄存器作为索引将上述寄存器的值写到对应的TLB表项中。
    • TLBP在TLB中查找和EntryHi寄存器中的VPN2和ASID域相匹配的TLB表项。
    • 上述指令和MFC0、MTC0等指令都只能在核心态下执行,在用户态将产生非法指令异常。
  • CPU使用TLB时,将EntryHi中的ASID域和访存地址与TLB中的每一项进行匹配,若命中则读出对应的PFN、C、D、V等内容,若不命中则发出TLB重填(TLB refill)异常;若TLB命中但V位为0,则发出TLB无效(TLB invalid)异常;若写TLB且TLB命中但读出的D位为0,则发出TLB修改(TLB modify)异常
  • EPC寄存器保存被TLB异常打断的指令PC。
  • BadVAddr寄存器保存发生TLB异常的虚拟内存地址。
  • Context寄存器用于加速TLB重填异常的处理过程。
  • PTEBase域保存页表起始地址。
  • BadVPN2域保存发生异常的虚拟页号。

5.3 TLB异常的处理

  • TLB异常有三种类型:

    • TLB重填异常:TLB中没有相应的表项
    • TLB无效异常:相应的物理页不在内存中。此时需要从外存取物理页到内存。
    • TLB修改异常:非法写了只读页。操作系统会杀掉要进行非法访问的进程。
  • 其中,TLB重填异常有专门的入口地址,因为发生地最频繁。其他两种异常使用通用异常入口地址。

  • TLB重填异常处理程序(?)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    .set noreorder
    .set noat
    TLBrefillR4K:
    mfc0 k1, C0_CONTEXT
    nop
    lw k0, 0(k1)
    lw k1, 4(k1)
    mtc0 k0, C0_ENTRYLO0
    mtc0 k1, C0_ENTRYLO1
    nop
    tlbwr
    eret
    .set at
    .set reorder
  • 发生异常时,硬件直接设置好EntryHi和Context寄存器的值。EntryHi的内容已经按照TLB的格式排好。Context寄存器中的PTEBase指向页表起始地址,由操作系统在进程切换时设置好,BadVPN2恰好作为页表的偏移地址。
  • 页表每项为8字节,已经按照EntryLo0和EntryLo1的格式排好,因此取到寄存器后可以直接写入TLB。
  • 异常处理程序的入口地址在TLB转换的kseg0段,且页表也放在kseg0段,因此异常处理程序可保证不会引起新的异常。
  • 发生异常时,硬件自动将CPU设置为核心态,完成异常处理后ERET指令自动将CPU设置为用户态
  • TLB异常处理的例子

    1
    2
    3
    array = (int *)malloc(0x1000);
    for(i = 0; i< 1024; i++)
    array[i] = 0;
    • 用户程序首先调用内存分配函数malloc来分配大小为0x1000字节的空间,返回一个虚拟地址0x450000。
    • 操作系统在进程的vma_struct链表里记录地址范围0x450000 - 0x451000为已分配地址空间,并且是可读、可写的。但此时只是分配了一个地址范围,还没有真实分配内存的物理空间,也没有在页表里建立页表项,TLB里更没有。如果进程不访问这个虚拟地址,就不用真的为其分配物理空间。
    • 接下来,for循环对数组array进行赋值,用户程序向地址0x450000写数据。store操作在完成地址运算后查找TLB,由于TLB里没有这一项,所以触发TLB refill异常。
    • TLB refill异常处理程序从相应的页表位置取页表内容填入TLB。但此时这个地址空间的页表还没有被初始化。
    • 异常处理程序返回到用户程序重新开始访问,TLB里有了对应的虚拟地址,但是没有物理地址。触发TLB invalid异常。
    • 处理TLB invalid异常时,操作系统需要查找vma_struct这个结构,如果判断出这个地址已经分配,处于可写状态,此时才真正分配物理页面,并分配物理页表,将物理地址填入页表,更新TLB相应的表项。
    • 异常处理程序返回到用户程序,store指令再次执行,这次就成功了。
    • 由于分配的一个页面的大小正好是4KB,这个int数组的总大小也是4KB,因此后续的地址访问都会在TLB中命中,不会再产生异常。

第六章 软硬件协同

6.1 函数调用规范

  • 程序在某个指令系统上执行时,必须遵循一些特定的规定,这就是ABI(Application Binary Interface,应用程序二进制接口)。ABI通常包括寄存器的命名和使用、函数调用、数据表示格式等约定。
  • MIPS堆栈布局
    • 叶子函数:不调用其他函数的函数称为叶子函数,叶子函数属于简单堆栈函数。
    • 非叶子函数:是包含其他函数调用的函数。这种函数在开始时需要设置sp寄存器,为自己函数分配空间并标明嵌套调用的参数结构基址。此外还需要保存s0-s8、ra等寄存器的值。sp只在开始时设置一次,堆栈的数据访问通过相对于sp的偏移量进行。
    • 复杂堆栈函数、sp、fp(?)

6.2 中断的生命周期

6.3 系统调用过程

  • 系统调用是操作系统内核为用户态程序实现的子程序。
  • 系统调用运行在核心态,具有很高的权限。
  • 在MIPS指令系统中,系统调用作为一种异常进行处理,由SYSCALL指令触发。在协处理器寄存器Cause的ExcCode域反映为特定的值。

6.4 同步与通信

  • 基于互斥的同步机制
    • 对数据进行原子操作的程序段叫做临界区。在临界区前后应该包含申请锁和释放锁的过程。申请锁失败的线程被阻塞,占有锁的进程在完成临界区操作后应该及时释放锁。
    • 当确认竞争者在另一个CPU上,而且临界区程序很短时,可以使用自旋锁。但当竞争者都在同一个CPU核上,在不可抢占的内核下进行自旋可能导致死锁。
    • 当自旋锁不可用,需要使用互斥锁。当一个线程获取锁失败时,会将自己阻塞并调用操作系统的调度去。在释放锁的时候还需要同时让其他等待锁的线程离开阻塞状态。
    • 测试锁和设置锁的代码依赖于原子的”测试并设置“指令,MIPS的实现方式是LL/SC指令。
  • 非阻塞的同步机制
    • 基于锁的资源保护和线程同步的缺点:
      • 若持有锁的线程死亡、阻塞或死循环,则其他等待锁的线程可能永远等待下去
      • 即使冲突的情况很少,锁机制也有获取锁和释放锁的代价
      • 锁导致的错误与时机有关,难以重现
      • 持有锁的线程因时间片中断或者页错误而被取消调度时,其他线程需要等待
    • 事务内存是一种非阻塞的同步机制,可以避免上述不足。 核心思想是尝试性地执行事务代码,在程序运行过程中动态检测事务间的冲突,并根据冲突检测结果进行提交或取消事务。

第七章 计算机组成原理和结构

7.1 冯·诺依曼结构

  • 主要特点:
    • 计算机由存储器运算器控制器输入设备输出设备五部分组成。其中运算器控制器合称为中央处理器(CPU)
    • 存储器是按地址访问的、线性编址的一维结构,每个单元的位数固定。
    • 采用存储程序方式,即指令和数据不加区别混合存储在同一个存储器中。
    • 控制器通过执行指令发出控制信号控制计算机的操作。指令在存储器中按其执行顺序存放,由指令计数器指明要执行的指令所在的单元地址。指令计数器一般按顺序递增,但执行顺序可按运算结果或当时的外界条件而改变。
    • 以运算器为中心。输入设备、输出设备与存储器之间的数据传送都经过运算器。
  • 改进:
    • 由以运算器为中心改进为以存储器为中心。
    • 由单一的集中控制改进为分散控制。运算器、存储器、输入输出设备的速度差异很大,需要采用异步方式分散控制。
    • 从基于串行算法改进为适应并行算法。
    • 出现为适应特殊需要的专用计算机。

7.2 计算机的组成部件

  • 运算器:是计算机中负责计算(包括算术计算和逻辑计算)的部件。
  • 控制器:是计算机中发出控制命令以控制机器各部件自动、协调地工作的装置。控制器需要实现的功能包括:从存储器中读取指令,解析指令(译码),根据译码内容执行相应的操作。
  • 存储器:是计算机中负责存储程序、原始数据和中间结果的部件。
    • 目前计算机系统的存储介质主要包括以下几类:
      • 磁性存储介质:如磁盘、磁带。存储密度高、成本低、非易失性。缺点是访问速度慢,磁盘的访问速度一般在毫秒级。
      • 闪存(Flash Memory):非易失性。访问速度快、成本高、容量下。一般用磁盘或闪存来构建大容量的永久存储器(例如硬盘)。
      • 动态随机访问存储器(DRAM):存储密度较高、数据具有易失性(需要周期性刷新)、访问速度较快。访问速度在几十纳秒级。一般用来构建程序的主存储器(也称为内存、主存)。
      • 静态随机访问存储器(SRAM):速度快、成本高,访问速度可以达到纳秒级,能够和处理器核工作在相同的时钟频率。一般用来构建片上的高速缓存(Cache)
    • 内存对计算机的整体性能影响重大。为了提升处理器的访存性能,现代处理器采用了大量的结构优化方法,例如在片内增加多级Cache,或将内存控制器与CPU集成在同一芯片内,以减少平均访存延迟。
    • 现代内存基本都采用同步动态随机存储器(SDRAM)实现。影响SDRAM芯片读写速度的因素有两个:
      • 行缓冲局部性。命中行缓冲会降低延迟;行冲突时要先将缓冲的数据写回对应的行,再将新地址的数据读入行缓冲,然后进行读写,延迟最长。
      • Bank级并行度。SDRAM芯片包含的多个Bank是相互独立的,它们可以同时执行不同的操作。利用这个特性可以在内存控制器上对并发访问进行调度。
  • 输入设备:是用来往计算机中输送程序、数据的装置。
  • 输出设备:是将计算机运算结果输送出来的装置。
  • 有些设备同时具有输入和输出两大功能,例如GPU、硬盘。
    • GPU:是与CPU联系最紧密的外设之一。CPU将需要显示的原始数据放在内存中,让GPU通过DMA方式读取数据,经过解析和运算,将结果写至显存中,再由显示控制器读取显存中的数据并输出显示。
      • 将GPU和CPU集成至同一个处理器芯片,能够大大减少芯片间的数据搬运,但同时因为显存和内存的合并,也会大大增加访存压力。
    • 硬盘:具有断电记忆功能,可以长时间保存数据。
      • 性能衡量标准是延迟和带宽。
    • 闪存(Flash Storage):一种半导体存储器,非易失性存储。
      • 访问延迟只有磁盘的千分之一到百分之一,尺寸小、功耗低、抗震性更好。SSD固态硬盘是用闪存构建的大容量存储设备,它模拟硬盘接口,可以直接通过硬盘的SATA总线和计算机相连。

7.3 计算机系统硬件结构发展

  • 计算机系统的硬件结构主要包括中央处理器、图形处理器、北桥及南桥等部分。
    • 中央处理器:主要包含控制器和运算器,在发展过程中不断与其他部分融合。
    • 图形处理器
    • 北桥:离CPU最近的芯片,主要负责控制显卡、内存与CPU之间的数据交换,向上连接处理器,向下连接南桥。
    • 南桥:主要负责硬盘、键盘及各种对带宽要求较低的IO接口与内存、CPU之间的数据交换。
  • CPU-GPU-北桥-南桥 四片结构
  • CPU-北桥-南桥 三片结构
  • CPU-弱北桥-南桥 三片结构
  • CPU-南桥 两片结构
  • SoC单片结构

​ 片上系统(System on Chip,SoC)是一种单片计算机系统解决方案。集成度高,功耗控制方法更灵活,有利于系统的小型化和低功耗设计。但扩展性不好。

7.4 处理器和IO设备间的通信

  • IO设备大都是具有特定功能的部件,不能当做简单的存储阵列来处理。IO设备的设备控制器会提供一组寄存器接口,寄存器的内容变化会引起设备控制器执行一系列复杂操作。设备控制器的接口寄存器也被称为IO寄存器。处理器通过读写IO寄存器来访问设备。
  • IO寄存器寻址:
    • 内存映射IO:把IO寄存器的地址放入内存地址空间中,寄存器和内存存储单元被统一编址。读写IO地址和读写内存地址使用相同的指令。
    • 特殊IO指令:专用的指令来执行IO操作。
  • 处理器和IO设备之间的同步
    • 查询:处理器向IO设备发出访问请求后,需要不断读取IO设备的状态寄存器。查询方式也被称为轮询。IO设备的速度一般都很慢,使用查询方式会浪费处理器的指令周期。
    • 中断:当设备完成某个操作后,自行产生一个中断信号来中断处理器的执行。处理器被中断后,再去读取设备的状态寄存器。中断方式提高了处理器的利用率。
  • 存储器和IO设备之间的数据传送
    • PIO(Programming Input/Output)模式:数据要经过处理器内部的通用寄存器进行中转。降低了数据传送的速率。
    • DMA(Direct Memory Access,直接存储器访问):在存储器和外设之间开辟直接的数据传送通道,数据传送由专门的硬件来控制。控制DMA数据传送的硬件被称为DMA控制器。
  • IO中断控制器
    • 中断的一般过程:
      • 中断源发出中断信号到中断控制器
      • 中断控制器产生中断请求给CPU
      • CPU发出中断响应,并读取中断类型码
      • CPU根据中断类型码执行对应的中断服务程序
      • CPU从中断服务程序返回,中断结束
    • 中断控制器是负责中断汇集、记录和转发的硬件逻辑。中断控制器一般具有可编程功能,因此被称为可编程中断控制器(PIC)。

第八章 计算机总线接口技术

8.1 总线概述

  • 总线的根本作用是完成数据交换。总线用于将两个或两个以上的部件连接起来,使得它们之间可以进行数据交换,或者说通信。

8.2 总线分类

  • 按照数据传递的方向:单向总线、双向总线。
  • 按照使用的信号类型:
    • 并行总线:包含多位传输线,在同一时刻可以传输多位数据。优点是同频率下带宽更大。
      • 例如PCI总线、DDR总线。
    • 串行总线:只有一位传输线,同一时刻只传输一位数据。传输频率大大提升。
      • 例如USB、SATA
  • 按照总线所处的物理位置:片上总线、内存总线、系统总线和IO总线。

8.3 片上总线

  • 片上总线是指芯片片内互连使用的总线。一个高性能通用处理器在设计时,常常会划分为处理器核、共享高速缓存、内存控制器等模块,这些模块之间的连接就需要通过片上互连总线。
  • 常见的片上互连总线有ARM公司的AMBA系列总线,包括AXI、AHB、ASB、APB等总线。
  • AXI总线
    • 是一种高性能、高带宽、低延迟的片上总线。
    • 地址/控制和数据总线是分离的,支持不对齐的数据传输。
    • 分为5个独立的通道,分别为写请求、写数据、写响应、读请求、读响应。每个通道采用握手协议独立传输。
    • AXI协议的特点:
      • 单向通道体系结构。信息流只以单方向传输,符合片内设计的要求。
      • 支持多项数据交换。
      • 独立的地址和数据通道。
    • AXI是一个主从协议。每套总线的主设备和从设备是固定好的。只有主设备才可以发起读写命令。
    • AXI支持多个并发访问同时进行,允许地址控制信息在数据传输之前发生,允许读写事务的乱序完成。
    • AXI采用双向握手协议,每次传输都需要主从双方给出确认信号。
    • AXI使用VALID和READY握手机制进行传输,地址和数据信息都只在VALID和READY信号同时为高的情况下进行传输。(看图:P91)
    • AXI支持读写事务乱序完成:每一个读写事务都有一个ID标签,该标签通过AXI信号的ID域进行传输。同ID的读事务或者同ID的写事务必须按照接收的顺序按序完成。不同ID的事务可以乱序完成。
  • AHB总线:读写操作共用命令和响应通道。
  • ASB总线:第一代AMBA总线
  • APB总线:本地二级总线,通过桥和AHB/ASB相连。主要是为了满足不需要高性能流水线接口或不需要高带宽接口的设备间的互连。

8.4 内存总线

  • 内存总线主要用于连接处理器和主存储器。
  • 内存条将自身的一些设计信息保存在一个EEPROM中,该EEPROM可以通过I2C总线访问,称为SPD(Serial Present Detect)。计算机系统可以通过I2C总线来读取内存条的信息,从而自动匹配合适的控制参数并获取正确的系统内存容量。
  • DRAM存储单元时按照Bank、行、列来组织的。对DRAM的寻址通过Bank地址、行地址和列地址来进行。
  • 对内存总线的控制是由内存控制器来实现的。内存控制器负责管理内存条的的初始化、读写、低功耗控制等操作。

8.5 系统总线

  • 系统总线常用于桥片连接,同时也作为多处理器间的连接以构成多路系统。
  • HyperTransport总线
    • 为了提升片间传输性能,系统总线渐渐由并行总线发展为串行总线。
    • HT总线用于连接微处理器与配套桥片,以及多个处理器之间的连接。
    • 与并行总线不同,串行总线通常采用点对点传输形式。体现在计算机系统结构上,就是一组串行总线只能连接两个芯片。
    • HT总线用于数据传输的信号并非双向信号,而是由两组方向相反的单向信号各自传输。发送和接收两个方向互不干扰,提升了总线效率。
    • HT总线采用流控机制替代了握手机制。提升了效率。
    • HT总线的读写请求是通过包的形式传输的。

8.6 IO总线

  • IO总线用于计算机系统中与设备接口的连接,也称为设备总线。
  • PCI是一种对计算机系统结构影响深远并广泛应用的设备总线。PCIE是升级版。
  • PCIE总线
    • 串行总线。点对点方式。一组PCIE总线只能连接一个设备。
    • 传输以包为单位。
    • 采用流控机制来替代握手机制。

第九章 计算机系统启动过程分析

  • 处理器的启动过程,实际就是一个特定程序的执行过程。这个程序被称为固件,又称为BIOS(Basic Input Output System,基本输入输出系统)。

  • 系统启动示意图

9.1 处理器核初始化

  • 所谓初始化,就是将处理器内部的各种寄存器状态从不确定设置为确定。将一些模块状态从无序强制为有序的过程。
9.1.1 处理器复位
  • 处理器的第一条指令,实际上是由复位信号控制的。复位后的第一条指令会从一个预先定义的特定地址读取。
  • 复位信号并没有对处理器内部的所有部分进行控制,例如TLB、Cache等复杂结构。因为对于MIPS来说,第一条指令地址0xBFC00000这个虚拟地址属于直接映射且不经Cache缓存的地址段,不需要使用TLB转换,也不需要使用Cache。所以硬件灭有对这两个结构初始化,而是在软件的启动过程中对其初始化。
9.1.2 调试接口初始化
  • 在启动过程中,优先初始化的是调试用的接口部分。

  • 对于龙芯处理器,最先初始化的是芯片内集成的串口控制器。

9.1.3 TLB初始化
  • 首先将TLB的每项逐一清空,以免程序中使用的地址被未初始化的TLB表项所错误映射。
  • 接着将BIOS希望使用的地址映射填入TLB表。
9.1.4 Cache初始化
  • Cache的组织结构中,主要包含标签(Tag)和数据(Data)两个部分,Tag用于保存Cache块的状态、Cache块地址等信息,Data则保存数据内容。大多数情况下对Cache的初始化就是对Tag的初始化,只要将其中的Cache块状态设置为无效,其他部分的随机数据就不会产生影响。

9.2 总线接口初始化

  • 内存和IO设备的具体组成在计算机系统中可以比较灵活地搭配,不同系统间的差异可能会比较大。
9.2.1 内存初始化
  • 内存的使用和设置与外接内存芯片的种类、配置相关,所以在启动过程中要先获取内存的配置信息,再根据这些信息对内存控制器进行配置。这些信息是程序通过I2C总线对外部内存条的SPD芯片进行读操作来达成的。
  • 对内存的初始化就是根据内存配置信息对内存控制器进行初始化。
  • 内存的初始化包括两个相对独立的部分:
    • 根据内存的行地址、列地址对内存地址映射进行配置。
    • 针对协议对内存信号调整的支持方式对内存读写信号相关的寄存器进行训练,以保证传输时的数据完整性。
9.2.2 IO总线初始化
  • 丢死龙芯3A2000处理器,对IO总线的初始化主要做了三件事:
    • 对IO总线的访问地址空间进行了配置,划分了设备的配置访问空间、IO访问空间和Memory访问空间。
    • 对IO设备的DMA访问空间进行了规定。
    • 对HT总线进行了升频。

9.3 设备的探测及驱动加载

  • 在PCI软件框架下,系统可以灵活地支持设备的自动识别和驱动的自动加载。
  • PCI协议下,IO的系统空间分为三个部分:配置空间、IO空间和Memory空间。
    • 配置空间存储设备的基本信息,主要用于设备的探测和发现
    • IO空间比较小,用于少量的设备寄存器访问
    • Memory空间可映射的区域较大,可以方便地映射设备所需要的大块物理地址空间
  • 配置空间的地址偏移由总线号、设备号、功能号和寄存器号的组合得到。

9.4 多核启动过程

  • 实现不同处理器核之间相互通信的一种手段是核间中断与信箱机制。
9.4.1 初始化时的多核协同
  • 主核除了对本处理器核进行初始化之外,还要负责对各种总线及外设进行初始化;从核只需要对本处理器核的私有部分进行初始化,之后在启动过程中就可以保持空闲状态,直至进入操作系统再由主核进行调度。
  • 为了加速整个启动过程,主核还可能给从核分配工作。
  • 主核在一些重要节点需要与从核进行通信。可以将信箱寄存器的不同位定义为不同含义,一旦主核完成了某些初始化阶段,就可以给信箱寄存器写入相应的值。
9.4.2 操作系统启动时的多核唤醒
  • 当从核完成了自身的初始化之后,如果没有其他工作需要进行,就会跳转到一段等待唤醒的程序。从核会定时检查自己的信箱寄存器。如果非0,表示主核开始唤醒从核,此时从核需要从其他几个信箱寄存器中得到唤醒程序的目标地址和执行时的参数。然后从核转到目标地址开始执行。

第十章 二进制与逻辑电路

10.1 计算机中数的表示

  • 小数点位置约定在固定位置的数称为定点数,小数点位置约定为可以浮动的数称为浮点数
  • 定点数的表示
    • 原码:采用”符号-数值“的表示方式。与人们日常记录正负数的习惯接近,但加减规则复杂,对于逻辑实现影响很大。
    • 补码:$[X]_{\text{补}} = (2^n + X) \,\,mod \,\,2^n, -2^{n - 1} \leq X < 2^{n-1}$ . 简单计算方法:原码最高位不变,其余位按位取反后末位加1.
    • 溢出:
      • n位的二进制有符号数,原码的表示范围是 $[-2^{n-1}+1, 2^{n-1}-1]$. 补码的表示范围是 $[-2^{n-1}, 2^{n-1} - 1]$.
      • 同符号数相加或者异符号数相减可能溢出。
      • 加减溢出的判断方法:如果A和B的最高位一样,但是A+B的结果的最高位与A和B的最高位不一样,表示溢出。
  • 浮点数的表示
    • 利用科学计数法表示二进制实数,一般的表示形式为:$(-1)^s \times f \times 2^e$. 包含三个域: $s$表示符号,$f$表示尾数域的值,$e$为指数域的值。
    • 计算机内部位宽是有限的,尾数和阶码之间存在着一个此消彼长的关系。增加尾数的位宽就减少了阶码的位宽,这会提高表示的精度,但是会减少表示的范围。
    • IEEE754 标准浮点数格式
      • 32位单精度格式:1位符号 | 8位阶码 | 23位尾数
      • 64位双精度格式:1位符号 | 11位阶码 | 52位尾数
      • IEEE 754 标准中,尾数用原码表示。
      • 规格化尾数的表示统一为1.xxxx的形式。尾数规格化后,第一位总为1,因而可以在尾数中缺省这一位,隐藏该位后尾数可以多表示一位,精度提高一位。
      • 阶码是用减偏置常量的移码表示,所用的偏置常量是$(2^{n-1} - 1)$。
    • 无穷大:阶码全为1,尾数全为0
    • 非数:阶码全1,尾数非0
    • 规格化非0数:阶码非全0非全1
    • 非规格化非0数:阶码全0,尾数非0
    • 零:阶码全0,尾数全0

10.2 MOS晶体管工作原理

  • 现代计算机采用晶体管实现二值系统。晶体管可以根据控制端电压或电流的变化来实现”开启“和”关闭“的功能,从而表达二进制。
  • 晶体管主要分为双极型晶体管(Bipolar Junction Transistor)和金属-氧化物半导体场效应晶体管(Metal Oxide Semiconductor Field Effect Transistor,MOS)。当前大多数CPU都采用MOS晶体管,其中又以CMOS(Complementary MOS)晶体管电路设计最为常见。
10.2.1 半导体
  • N(Negative)型材料:在纯净硅中掺杂少量5价原子(如磷),会多出一个游离的电子,在电场的作用下形成负电流。
  • P(Positive)型材料:在纯净硅中掺杂少量3价原子(如硼),会缺少一个电子,形成空穴,相当于空也在顺着电场的方向流动,形成正电流。
10.2.2 NMOS和PMOS晶体管
  • MOS晶体管是由多层摞放在一起的导电和绝缘材料构建起来的。每个晶体管的底部叫做衬底,是低浓度掺杂的半导体硅。晶体管上部三个信号端口,分别称为源极(Source)、漏极(Drain)和栅极(Gate)。源极和漏极采用跟衬底相反极性的高浓度掺杂。
  • NMOS:衬底是低浓度P型掺杂,有源区是高浓度N型掺杂的MOS晶体管叫做NMOS晶体管。
  • PMOS:衬底是低浓度N型掺杂,有源区是高浓度P型掺杂的MOS晶体管叫做PMOS晶体管。
  • 屏蔽掉物理细节,NMOS管的工作行为就是:在栅极上加上电就通,不加电就断。PMOS管与NMOS管相反,加上电就断,不加电就通。

10.3 CMOS逻辑电路

10.3.1 数字逻辑电路
  • 根据电路是否具有数据存储功能,可将数字逻辑电路分为组合逻辑电路和时序逻辑电路两类。
  • 组合逻辑:组合逻辑中没有数据存储单元,电路的输出完全由当前的输入决定。与非门(NAND)、或非门(NOR)、异或门(XOR)、同或门(与或非门)(XNOR)。
  • 时序逻辑:时序逻辑电路包含时钟信号和数据存储单元两个要素。其输出不仅与当前输入的逻辑值有关,而且与之前曾经输入过的逻辑值有关。
  • 时钟信号是时序逻辑电路的基础。它是具有固定周期的标准脉冲信号。
  • 数据存储单元多由锁存器构成。
    • RS锁存器:包含置位端S(Set)和复位端R(Reset)两个输入端口。S为1时输出为1,R为1时输出为0. 当R和S同时为1时,能保持输出值不变,从而实现数据的存储。
    • D锁存器:在RS锁存器前面连接两个与非门,再用时钟C控制D输入就构成了D锁存器。当C=0时,R和S都为1,RS锁存器处于保持状态。当C = 1时,输出Q与输入D值相同。
    • D触发器:两个D锁存器串接起来就构成了一个D触发器。当C= 0时,第一个D锁存器直通,第二个D锁存器保持。当C= 1时,第一个D锁存器保持,第二个D锁存器直通。C从0变成1时,D的值被锁存起来。
10.3.2 常见CMOS电路
  • P135

第十一章 简单运算器设计

11.1 顶点补码加法器

  • 一位全加器

    • 实现两位本地二进制数以及低位的进位位相加,求得本地和以及向高位的进位。
    • 可近似认为,每个一位全加器需要2或3级的门延迟(计算进位需要2级门延迟,计算本地和需要3级门延迟)。
  • 行波进位加法器

    • N位行波进位加法器就是将N个一位全加器逐个串接起来。延迟太高。
  • 先行进位加法器

    • 第$i$位的进位输出是 $c_{i+1} = g_i | p_i \& c_i$

    • 进位生成因子:$g_i = a_i \& b_i$ 被称作第$i$位进位生成因子。

    • 进位传递因子:$p_i = a_i | b_i$ 被称作第$i$位的进位传递因子。

    • 把每一位的进位公式展开后,可以知道每一位的进位输出$c_{i + 1}$可以仅由本地信号生成的$g$ 和 $p$(和 $c_0$)直接得到。

    • 块内并行、块间串行逻辑:实现更多位的加法器时通常采用分块的进位方法,将加法器分为若干个相同位数的块,块内通过先行进位的方法计算进位,块间通过行波进位的方法传递进位。

    • 块内并行、块间并行逻辑

      • 块间进位生成因子:$G = g_3 | p_3 \& g_2 | p_3 \& p_2 \& g_1 | p_3 \& p_2 \& p_1 \& g_0$ 被称作第$i$位进位生成因子。

      • 块间进位传递因子:$P = p_3 \& p_2 \& p_1 \& p_0$ 被称作第$i$位的进位传递因子。

      • 这种逻辑设计具有很好的层次扩展型,即以层次化的方式构建进位传递逻辑,把下一级的P和G输出作为上一级的$p_i$和$g_i$输入。

        计算步骤如下:

        1 )下层的4块4位先行进位逻辑根据各块对应的$p_i$和$g_i$生成各自的块间进位生成因子G和块间进位传递因子P。(2级门延迟)

        2 )上层的4位先行进位逻辑把下层的先行进位逻辑生成的P和G作为本层的$p_i$和$g_i$输入,生成块间的进位$c_4, c_8, c_{12}, c_{16}$。(2级门延迟)

        3 )下层的每块4位先行进位逻辑分别把$c_0$以及上层计算出的$c_4, c_8, c_{12}$作为各自块的进位输入$c_0$,再结合本地的$p_i$和$g_i$分别计算出本块内部所需要的每一位进位。(2级门延迟)

11.2 减法运算实现

  • $[A]_{补} - [B]_补 = [A - B]_补 = [A]_{补} + [-B]_补$
  • $[-B]_补$可以直接将 $[B]_补$按位取反,末位加1得到。
  • 所以,只需要将被减数直接接到加法器的A输入,减数按位取反后接到B输入,再把加法器的进位输入$C_{in}$置为1,就可以用加法器完成减法运算。

11.3 比较运算实现

11.4 移位器

第十二章 定点补码乘法器

12.1 补码乘法器

  • 迭代式硬件原码乘法器

​ 操作步骤:(以两个8位数的乘法为例)

​ 1)最初时,将乘法结果设置为0.

​ 2)在每个时钟周期,判断乘数的最低位,如果为1,就把被乘数加到乘法结果;如果为0,则不进行加法操作。此后乘数右移1位,被乘数左移1位。将参与运算的3个数锁存,进入下一个时钟周期。

​ 3)执行8次操作,得到正确的乘法结果。

  • 补码乘法原理:

    $[X \times Y]_补 = [X]_补 \times (-y_7 \times 2^7 + y_6 \times 2^6 +… + y_0 \times 2^0)$

  • -10010000 $\rightarrow$ 00101111 + 1

  • 需要特地挑出第N个部分积,并使用补码减法进行操作,这就需要一个额外的状态机来控制,增加了硬件复杂度。

12.2 Booth乘法器

  • Booth一位乘算法:

    $[X \times Y]_补 = [X]_补 \times (-y_7 \times 2^7 + y_6 \times 2^6 +… + y_0 \times 2^0) $

    $= [X]_补 \times \{(y_6 - y_7) \times 2^7 + (y_5 - y_6)\times 2^6 +…+ (y_0 - y_1)\times 2^1 + (y_{-1}-y_0)\times 2^0\}$

    • 只需要根据最末两位来确定如何将被乘数累加到结果中。
    • Booth一位乘运算规则:

    • | $y_i$ | $y_{i-1}$ | 操作 |
      | :—-: | :———-: | :—————————: |
      | 0 | 0 | +0 |
      | 0 | 1 | 补码加X(+$[X]_补$) |
      | 1 | 0 | 补码减X(-$[X]_补$) |
      | 1 | 1 | +0 |

    • 为了计算N位补码乘法 ,依然需要N-1次加法。而数据宽度较大的补码加法器面积大、电路延迟长。

  • Booth两位乘算法:

    • | $y_{i+1}$ | $y_i$ | $y_{i-1}$ | 操作 |
      | :———-: | :—-: | :———-: | :———————————-: |
      | 0 | 0 | 0 | +0 |
      | 0 | 0 | 1 | 补码加X(+$[X]_补$) |
      | 0 | 1 | 0 | 补码加X(+$[X]_补$) |
      | 0 | 1 | 1 | 补码加2X(+$[X]_补$左移) |
      | 1 | 0 | 0 | 补码减2X(-$[X]_补$左移) |
      | 1 | 0 | 1 | 补码减X(-$[X]_补$) |
      | 1 | 1 | 0 | 补码减X(-$[X]_补$) |
      | 1 | 1 | 1 | +0 |

    • 使用Booth两位乘算法,计算N位的补码乘法,只需要 N/2次加法。

12.3 华莱士树(?)

  • 华莱士树由全加器搭建而成。全加器可以将3个1位数A、B、C的加法转换为两个1位数S和C的错位加法:

    ​ A + B + C = S + (C << 1)

  • 全加器的S输出需要3级门延迟,C输出需要2级门延迟,不论参与加法的数据宽度是多少位,将4个数相加转换为两个数相加最多只需要6级门延迟,最后把这两个数加起来还需要一个加法器。因此用华莱士树进行多个数相加可以明显降低计算延迟。

  • 使用华莱士树进行M个N位数相加,可以大致降低延迟$\log N$倍,而每一层华莱士树包含的全加器个数为$\lfloor 2M’/3\rfloor$,$M’$是当前层次要加的数字个数。

  • 华莱士树的精髓在于:通过连线实现进位传递,从而避免了复杂的进位传递逻辑。

第十三章 指令流水线

13.1 单周期处理器

  • 简单CPU的数据通路:

    • 程序计数器:又称PC,指示当前指令的地址。
    • 指令存储器:按照指令地址存储指令码,接收PC,读出指令。
    • 译码部件:用于分析指令,判定指令类型。
    • 通用寄存器堆:用于承载寄存器的值,绝大多数指令都需要读取及修改寄存器。
    • 运算器:用于执行指令所指示的运算操作。
    • 数据存储器:按照地址存储数据,主要用于访存操作。
  • 带有时序控制逻辑的数据通路:

    1)复位信号将复位的PC装载到PC触发器内,之后的第一个时钟周期内,使用PC取指、译码、执行、读数据存储器、生成结果

    2)当第二个时钟周期上升沿到来时,将新的PC锁存,将上一个时钟周期的结果写入寄存器堆,执行可能的数据存储器写操作

    3)第二个时钟周期内,按以上步骤执行第二条指令。

  • 由于每条指令的执行基本在一拍内完成,这个模型被称为单周期处理器。

13.2 流水线处理器

  • 单周期处理器中,每个周期要完成取指、译码、读寄存器、执行、访存等很多组合逻辑的工作,所以时钟周期很长,导致CPU主频无法提高。使用流水线技术可以提高CPU主频。

  • 多周期处理器:在每段操作前后加上触发器,就能减少每个周期的工作量,提高处理器频率。采用分频时钟,将原始的时钟信号通过分频的方式产生5个时钟,就能分别控制5组触发器。

  • 流水线处理器:从多周期处理器演进到流水线处理器,核心在于控制逻辑和数据通路对应关系维护机制的变化。流水线处理器在每级流水的触发器旁边添加一批用于存储控制逻辑的触发器。指令的控制藉由这些触发器沿着流水线逐级传递下去。

  • 流水线处理器的时空图:

13.3 指令相关和流水线冲突

  • 指令相关是指,在流水线中,如果某指令的某个阶段必须等到它前面另一条指令的某个阶段后才能开始,则这两条指令存在相关。指令相关分为数据相关、控制相关和结构相关。
    • 数据相关:如果两条指令访问同一个寄存器或内存单元,而且这两条指令中至少有1条是写该寄存器或内存单元。根据读写次序可分为写后读(RAW)、写后写(WAW)、读后写(WAR)相关。在5级简单流水线中,只有RAW会引起流水线冲突,也被称为真相关。但是在乱序执行流水线中,WAR和WAW也有可能引起流水线冲突。
      • 指令在写回阶段才会修改目的寄存器。为了解决冲突,可以加入流水线阻塞。
      • 为了提高处理器性能,可以加入前递技术,将已完成运算但还没有写回的运算结果直接传递给后续的相关指令。
    • 控制相关:如果两条指令中有一条是转移指令且另一条指令是否被执行取决于该指令的执行结果,则存在控制相关。
    • 结构相关:如果两条指令使用同一份硬件资源。
  • 如何支持异常和中断:
    • 不可恢复异常:系统硬件出现了严重故障,此时立即终止当前的执行,记录软件所需的信息然后跳转到异常处理入口。
    • 可恢复异常:精确异常。

13.4 提高流水线效率的技术

  • 多发射数据通路:降低CPI最直观的方法,让处理器每级流水线都可以同时处理更多的指令。要在处理器中支持多发射,就要将处理器的各种资源翻倍。
  • 动态调度:把相关的解决尽量往后拖延,同时前面指令的等待不影响后面指令继续前进。
    • 将译码阶段拆分成”发射“和”读操作数“两个阶段。发射阶段进行指令译码并检查结构相关,随后在读操作数阶段一直等待直至操作数可以读取。
    • 保留站:处于等待状态的指令不能一直停留在译码级流水线上,所以利用一个被称作保留站(发射队列)的结构来保存这些等待的指令。除了存放指令,保留站还要负责控制其中的指令何时去执行。每个时钟周期,保留站会选择一条没有被阻塞的指令,送往执行逻辑,并退出保留站,这个动作被称为”发射“
    • WAW和WAR同RAW是有本质区别的它们并不是程序中真正的数据依赖产生的相关关系。通过寄存器重命名技术,可以消除WAR和WAW相关。
    • 重排序缓冲(ROB):用于解决精确异常。ROB维护着指令的有序结束,同时在流水线中增加一个”提交“阶段。指令对机器状态的修改只有在到达提交阶段时才能生效。ROB是一个先进先出的队列,所有指令在译码后按顺序进入队列尾部,执行完毕的指令从队列头部按序提交。提交时一旦发现指令有异常,则ROB中该指令及其后面的所有指令都被清空。
  • 转移预测:转移预测机制由两部分组成:预测和确认。
    • 第一部分是预测:当执行取指或译码时,预测这条转移指令的转移目标,不用等到这条指令执行,先去目标处取指。
    • 第二部分是确认:当这条转移指令执行完毕后,确认当初预测的结果和实际转移目标是否相同,如果不同,则取消这条转移指令后的所有指令,并从正确的目标重新取指。
    • 根据预测是在取指级还是译码级,可以分为基于PC的预测和基于指令的预测。
      • 基于PC的预测器,可以维护一个表,每一项包含PC和目标两个信息。当一条转移指令完成后,就将它的信息写入该表,后续的取指查询该表。
      • 基于指令的预测器,要根据转移指令的类型使用不同的预测机制。
        • 对于分支指令:只需要预测分支方向,通常使用PC低位索引一个表来实现。不需要在表中存放PC信息,只存放了是否跳转,单项内容少,可以包含很多项。
        • 跳转类指令:需要预测分支目标,要在表中存放PC和目标。
  • Cache:是一个硬件结构,存放内存的子集,容量较小,访问速度很快。
    • 当指令要访问的数据在Cache中时,直接从Cache中取得数据;当数据不在Cache中,称为Cache失效,处理器要阻塞这条指令的写回,并去内存中取回对应的数据,放置在Cache中。
    • 存在数据Cache和指令Cache。
    • 现代处理器实现了多级Cache,因此进行失效处理时,先去查询容量更大的二级Cache,如果仍然失效,再去访问下一级Cache或内存。
    • 写回与写穿透
      • 写回Cache:存数指令需要修改内存的值,如果修改后的值暂时放在Cache中,当Cache替换回内存时再写回,则称为写回Cache。
      • 写穿透Cache:每条存数指令都要立即更新内存值,则称为写穿透Cache。

第十四章 并行编程基础

14.1 程序的并行行为

  • 程序的并行行为主要包括指令级并行、数据级并行、任务级并行。
  • 指令级并行性(Instruction Level Parallelism, 简称ILP):现代处理器采用多种微结构设计技术挖掘指令级并行性。包括指令流水线、多发射、动态调度、寄存器重命名、转移猜测等技术。
  • 数据级并行性(Data Level Parallelism, 简称DLP):是指对集合或者数组中的元素同时执行相同的操作。这种并行性通常来源于程序中的循环语句。可以再计算机体系结构的多个层次来利用数据级并行性。例如,可以在处理器中设计向量功能部件,采用SIMD设计方法;设计专门的向量处理器;在多处理器中采用SPMD(Single Program Multi-Data)的编程方式,将数据分布到不同的处理器上执行同一个程序控制流。
  • 任务级并行性(Task Level Parallelism):将不同的任务分布到不同的处理单元上执行。

14.2 并行模型编程

  • 单任务数据并行编程模型
    • SIMD、SPMD。
    • 单线程。
    • 同构并行。数据并行程序的一条语句,同时作用在不同数组元素或者其他聚合数据结构。在数据并行程序的每条语句之后,均有一个隐式同步。
    • 全局命名空间。
    • 隐式相互作用。不需要显式的同步,通信可以由变量指派隐含地完成。
    • 隐式数据分配。
  • 多任务共享存储编程模型
    • 全局命名空间。
    • Pthread、OpenMP。
  • 多任务消息传递编程模型
    • 多进程。
    • 异步并行性。消息传递的各进程彼此异步执行。使用诸如栅障和阻塞通信等方式来同步各进程。
    • 独立的地址空间。
    • 显式相互作用。
    • 显式分配。
  • 共享存储与消息传递编程模型的编程复杂度
    • 都是运行在多处理器并行处理系统上的。
    • 共享存储系统中,所有处理器共享主存储器。消息传递系统中,每个处理器的存储器是单独编址的。

14.3 典型并行编程环境

  • SIMD(Single Instruction Multiple Data):单指令多数据流。
  • Pthreads(POSIX threads):早期的共享存储编程模型。
  • OpenMP标准:用于共享存储并行系统的编程标准。不是一种语言,而是对基本编程语言进行编译制导扩展。程序员可以通过在程序源代码中加入专用pragma制导语句来指明自己的意图。
    • OpenMP是一个基于线程的并行编程模型,一个OpenMP进程由多个线程组成,使用fork-join并行执行模型。
  • MPI:消息传递编程接口。为程序员提供了一个并行环境库,程序员用标准串行语言编写代码,并在其中调用MPI的库函数来实现消息通信,进行并行处理。
    • 通信域提供了MPI中独立的安全的消息传递。MPI通信域包含进程组通信上下文进程组是参加通信的一个有限并有序的进程集合。通信上下文提供一个相对独立的通信区域,消息总是在其被发送的上下文内被接收,不同上下文的消息互不干涉。
    • 点到点通信:发送和接收语句必须是匹配的。不同的语句采用了通信域Comm和标志位tag来实现成对语句的匹配。
      • 分为阻塞和非阻塞两种机制。阻塞方式保证了缓冲区等资源可再用。非阻塞允许了通信和计算的重叠,但并不保证资源的可再用性。

第十五章 多核处理结构

其他问题

动态功耗VS静态功耗

  • 处理器总功耗 = 总电流 X 总电压
  • 总电流 = 静态电流 + 动态电流
  • 静态电流用欧姆定律