W1 4-2

15出勤 10作业 15大作业 60期末考试

计算机技术的发展永远不能满足增长应用对计算的需求

CISC问题：二八定律，20的复杂指令占据了80的处理时间

处理器频率陷入停滞，开始进入多核并行处理的时代，功耗成问题

指令内部并行、指令级并行、线程级并行——功耗问题；进一步开发数据级和指令并行性很难；储存器访问速度很慢

两方面的技术——计算机制造技术and系统结构

现代计算机系统结构的6个伟大思想：层次架构；摩尔定律；局部性原理（层次存储器）；并行；性能测量&提升；可信性via冗余

1.1 基本概念

微程序-传统机器语言-OS-汇编-高级语言-应用语言

翻译 程序整个转换为等效程序，然后再运行。常用于上三层

解释 每一条都对应过去并执行，然后再取下一条。更灵活，不利于优化，更低效

微程序

每条机器指令编写成若干微指令，对应微操作来解释执行。硬件电路简单，指令规整，可维护更灵活；执行慢

虚拟机：OS及以上都属于部分由软件实现的机器

Firmware固件，固化软件或者软件功能的硬件，把程序写入EEPROM只读。比如驱动，通过修改固件软件代码可以改变功能，比硬连更灵活。但速度更慢

计算机系统结构广义定义指令级结构+计算机组织+计算机实现

经典定义 传统机器程序员看到的计算机属性，概念性结构和功能特性。

实质 确定界面，以上是软件功能，以下是硬件和固件功能

Flynn弗林分类法

指令流和数据流的多倍（在系统最受限的部件上同时处于同执行阶段的指令or数据的最大数目）性质

SISD SIMD MISD MIMD

并行趋势：指令级-线程级-数据级

并行vs同时 同时刻or同时间间隔

隐藏指令问题 不存在于手册里但是对硬件有操作or手册里的功能并没有写出来，危险也不允许

在层次架构中最好有一一映射，保证层次之间的安全鲁棒。很多加速器就是突破层次的直连

计算机系统设计的定量原理

• 经常性事件原则，以经常性事件为重点Common Case，优化占比最大的指令
• Amdahl 评估方案优化效果，加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比
  • 可改进比例Fe
  • 部件加速比Se 一般大于1
  • 仅仅对计算任务中的一部分做性能改进，改进越多总体性能提升约受限？？加速比有上界
• 运行时间 = ICCPI时钟周期长度
• 有时候两种CPU执行的指令并不一样，比如分支+比较和没有比较指令。可能影响CPU运行时间的计算。
• 自顶向下现在更流行rather than自下而上（软硬件脱节，软件太被动）这两种软硬件都脱节
• 或者middle out 先确定软硬件分配

性能评测指标

M FLO P S 百万次浮点操作

TOPS 每秒钟万亿次操作

唯一可靠的性能标准就是真实程序的执行时间。

用户关心单个程序时间；数据处理中心管理员关心吞吐率（在单位时间内完成的更多的任务）

区分CPU时间和操作系统开销（系统CPU时间），CPU时间专指用户程序耗费的CPU时间

W2 4-2

W3 4-2

xx编址 按x访问

字节编址按字访问：浪费地址空间但是有利于符号处理，浪费储存空间，读写复杂，endian

定位方式：

直接（装入前）、静态（装入中）、动态定位（执行中）

控制器的微指令，把事实指令再拆解成微指令..

定制化processor大多是cisc 更通用就是risc

微架构：对软件不可见、Cache不可见但是os有对其控制的趋势；分支预测；指令周期；流水线

标量和向量流水线：对数据对象分类

非线性流水线的调度

非线性流水线必须使用连接图和预约表（预约表理解成时空图）共同表示。预约表只是流水线的一种工作方式，线性流水线一定是唯一的。

向量流水线和SIMD的区别在哪？

基本概念

三阶段指令：3n 2n+1 n+2

时空图，时间-阶段指令

连接图每个stage，流水划分尽量平均，最长阶段为瓶颈

设计连续的同类任务

分类

单多功能：各段可以通过不同的连接组合实现不同功能

静态动态：同一时间各段按照固定连接or不同方式连接，在时空图看两种任务时间是否相交

线性or非线性：串行or有反馈回路

线性用时空图唯一表示，非线性用连接图和预约表（时间-流水段打×）一起。比如1323 12323分别为前馈和反馈。前馈就是跳到后面，反馈跳前面

顺序乱序：流入留出相同，顺序流动 or 可以不同，后进可以先出 区别于乱序执行：允许多条指令不按顺序发给电路单元

标量向量流水：向量类似SIMD

流水线的性能指标

吞吐率，单位时间能够完成的任务数量。最大吞吐即无穷任务。总时间：一条指令完全执行+n-1条的流动单元

细分|重复设置（并行）瓶颈段。中间结果也算结果？

加速比：顺序时间比流水后时间。段数多任务需要多

效率：设备利用率，时空图上n任务占用时空区与功能段总时空区的比

静态流水：同时间只能固定连接，所以所有加减都出去才能开始计算乘法。

非线性流水调度

启动循环算法

1. 禁止集合：各功能段的禁止启动组合一起，无序
2. 冲突向量：哪一位禁止就是1，其他是0
3. 流水线状态图：冲突向量为初始状态，右移m次。如果移出1不管，移0则按位或初始向量形成新状态，构造转移图。每个状态都有m+1以上的移位，自然都回到初始状态。
4. 找可用启动距离和平均启动距离：从初始出发，找所有简单循环（无重复路径）先从一步回；多步回；不回循环；单循环；绝对安全循环等。找到平均最小的循环
5. 找出平均启动距离最小的启动循环or恒定循环（循环节为长度1）
   最小平均启动距离：大于等于任意行中最多的X（瓶颈段），任何一个简单循环都是上限，上限是冲突向量中1的个数加1.

预留算法 以最优调度，插入非计算delay段。如果理论最优为2，则通过插入Delay把每个x后面2的位置都预留出来。当瓶颈段一直忙碌，就实现了最优调度

动态调度

启动循环推出的启动间隔集合Gc，即所有可能的间隔。为C中的间隔任意连续相加。

多功能非线性流水线调度

多个冲突向量，对应下一个任务功能是AorB。多个初始节点对应第一个任务类型。双功能有四类冲突向量AA AB BB BA

重叠预约矩阵求初始MatrixA和B，转移边有任务类型和右移次数。

相关与冲突

一般约定写操作在前半周期，读在后半周期

相关

真数据相关RAW

名相关

寄存器or存储器单元名称相关，但没有数据流动。如WAR，WAW。——编译器or硬件来换名

控制相关

由if 等引出的指令顺序相关

流水线冲突

WAR和WAW冲突只有乱序发生，建议换名

定向技术：旁路、短路

编译器重调度解决

尽早判断和计算目标地址，假设到ID段完成

延迟分支 即插入延迟槽，无论是否成功都执行指令，掩盖暂停周期。编译器可以从前面、目标和失败的地方调度延迟槽

实现

性价比：最大吞吐/价格，单位任务时间为寄存器延迟+任务/段数，价格为整个流水价格+寄存器*段数，有最佳段数求导

问题

P66为什么挤上时空图？

预约表中同时刻占两个阶段如何理解？

W4 4-2

相关：数据（真）相关 名相关 控制相关

名相关：寄存器重命名

Load延迟槽，调度解决

编译器延迟分支：分支指令后面n个延迟槽，无论分支与否，一定被执行。从前调度、从目标调度，从失败处调度

W5 4-2

向量数据表示

等间距向量表示：向量从0开始计算，向量间距就是其中每个单元的位置，比如64*64bit就是8B的间距，向量长度是64（即维数）

带位移量的向量：从位移量开始，有效长度减去位移量。带位移后实现可变增量，能表示稀疏向量。向量长度L 位移f 有效长度L-f，甚至负数变正

稀疏向量表示：记录非0值，以及bitmap

向量处理方式

按行写一排同样形式的算式，然后按行（按算式结果）or按列（按阶段）

横向，一行行加工。每个分量都写读相关，频繁的流水线切换。向量机不适合

纵向：同种运算这一列同时全部执行，然后下一列

纵横：分组，分级按列处理。向量长度超过向量寄存器长度、

向量机结构

多个独立存储模块并发访问（纵向） or 多寄存器-寄存器（分组）结构复杂，寄存器多，对存储访问要求低

储存器-储存器：

每拍读两个写一个

存储器源源不断提供操作数并不断接受结果，要求存储器带宽和通信带宽

n个储存模块并不正比提升n倍：转移指令and数据随机性（比如跳跃访问，一半冲突）

冲突解决：存储体质数>=向量长度，则位移量与n互质，冲突不存在。如向量16取寄存器17 多次运算后分布改变，仍存在访问冲突

二维数组的行列对角线无冲突：顺序列冲突

顺移错位对角线冲突

一、错开法设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m＝2^2p＋1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1＝2P，d2＝1即同行相邻，同列错开2^p

存储体5 17 65等

2^p*i + j + k mod m 体中第i号

有浪费，实现简单

二、紧凑找到n = 2^2p的p，即可用n个并行存储体无冲突

体号地址：2(iL xor jH)＋(iH xor iL xor jL)

体内地址：j

无浪费，并行读写需要比较复杂的对准网络

上图引入A的2周期输入缓冲和 C的输出4周期缓冲，这样冲突的AB同时到流水线。且写入也可以不耽误流水线的连续运行（下一轮数据读出进入）

寄存器-寄存器

分组向量，缓冲为向量寄存器，操作数从寄存器读取并写入。向量寄存器：保存一堆标量并顺序访问，降低存储流量

0608-0615 Final Review

D.S. Wang

“尽可能量大一点，简单一点”

填空 判断对错 单选 计算题

都是量化的计算

题目很多很简单，两个实验都考

每章都要有，性能评价

L1 层级架构 Flynn分类法

amdahl定律 cpu性能公式 访存占xxx时，xx加速后最后加速比xxx

benchmark 执行时间吞吐率

L2数据表示

寻址方式（立即数 变址）编址 定位… huffman编码

L3 分类 静态动态 线性非线性 加速比（效率、资源利用率）

单功能非线性流水线调度，解决冲突且性能高，相关：指令固有的属性，由于相关会造成冲突

目标是相关指令不造成流水线冲突，多功能调度不要求

L4 向量处理机？ 数据集并行，三种向量处理方式，两种架构

多个技术：链接、编队、循环开采 性能评价方法

L5 掌握动态Tomasulo+ROB实现精确中断，预测失败的正确返回 记分牌不要求

动态分支预测技术

come from总线 vs goto总线

L6 只要求循环展开知道基本概念 EPIC不考

L7 存储 考试重点，基本概念为主

局部性原理 四个问题（策略）：放置（全 直接 组）、查找、替换、写策略（through back）

cache缺失原因：强制（冷启动缺失） 容量 冲突 一致性（不重要）

性能：miss少 miss代价小 hit更快

L9 互联函数 参数（规模 度 直径） 静态、动态的互连网络

L10 线程并行？多核处理器，必然，单核频率 UMA & NUMA下的一致性问题

多线程要细粒度才有意义

15 + 10 + 15 + 60

L1 基础 6.8

计算机技术的发展永远满足不了不断增长应用对计算的需求

CISC的二八定律：20%的指令占了80%的时间，剩下80只占20%时间

单核频率停滞，功耗成为大问题，存储器访问速度的提高pang慢；有效开发数据和指令并行难

计算机制造技术&系统结构

层次结构

应用+算法 编程语言 OS ISA 微架构 RTL 电路 设备 物理

应用 高级语言 汇编 操作系统级 【虚拟】|【物理】 机器语言 微程序

微程序一条机器指令包含若干微指令，硬件解释执行微操作

微程序：硬件简单 规整 灵活 可维护 慢

不使用：快 指令简单 复杂指令的逻辑电路复杂

经典定义：传统机器程序员看到的计算机属性，按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同的属性

广义定义： 指令集结构（Instruction Set Architecture） ＋ 计 算 机 组 织（Organization） ＋计 算 机 实 现（Implementation）

Flynn分类法

SISD 单核单数据

SIMD 经常数据并行，向量机

MISD 没什么，脉动阵列TPU

MIMD

经常性事件原则：多优化经常事件，阿姆达尔

加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比。可改进比例Fe 部件加速比Se

不可改进比例+可改进的变化

cpu时间 = InstrCount * CPI * 时钟周期长度

设计方法

自顶向下 先确定最高应用级特征，也容易脱节

自底向上 软件完全被动，硬件软件脱节，很少采用

中间开始 软硬件交界面开始分配软硬功能

性能评测

MIPS 每秒百万条指令

MFLOPS 每秒百万次浮点操作

TOPS 每秒T次操作

执行时间：全部时间orcpu时间（用户cpu时间和系统cpu时间）

benchmark测试 是否允许修改？

用户执行时间

服务器吞吐率

加权调和平均执行时间，上面是权重和

标准化执行时间，先归一化到某个机器上，然后计算平均（算数或者几何）Am Gm 几何平均值的比等于比的几何平均值

几何平均值的加权是乘方

系统结构发展

模拟，一般“解释”实现

仿真，宿主机的微程序实现目标机的指令级，更快但差别不能大

并行发展

同时：两个及以上时间同时刻发生

并发：两个及以上事件同时间间隔发生

字并》位并》字串位串

时间重叠，高性能单处理机，部件专用化；资源重复，多搞一些；资源共享

阵列处理机：SIMD？

指令内部并行；指令级；线程级；过程级；作业程序级

紧密耦合共享主存，松散耦合共享外存

L2 指令系统 6.8

软硬交界面

新型指令系统，比如mac指令乘加AxB+C = D

结构分类

cpu中存储单元: 堆栈结构 累加器结构 通用寄存器结构

堆栈：简单；指令短；隐式给操作数

累加器（专门数逻运算）：减少状态；指令短；隐式操作数

通用reg：增加内部寄存器数，降低存储器通信开销；更少的地址寻址减小目标代码；编译器更有效的使用寄存器

但均需显示命名给出，指令长

• 寄存器-存储器 ：ALU来源一个reg一个mem
• 寄存器-寄存器：两个reg
  x操作数指令

RR结构也是loadstore结构，只有LS访存。

指令字长固定，简洁简单；各种指令周期数相仿；

指令条多，不够紧凑，程序占用空间大

寻址方式

主存宽度8B

• 任意存

• 不能跨主存行，速度快但空间浪费。
  指令格式，对于操作数来说

• 直接方式，操作数在指令中

• 间接，操作码+地址码
  寻址方式，由操作码决定适合简单LSor专门指出寻址方式的字段适合多种访存多种寻址

• 立即数 给出操作数

• 直接 给出操作数地址

• 寄存器 给出寄存器符号

• 寄存器间接 给出寄存器-地址-数据

• 寄存器相对（偏移） 寄存器-地址-偏移-数据

• 基址变址 寄存器-寄存器-地址-数据

• 相对基址变址寻址 寄存器-寄存器-地址-偏移-数据

指令系统设计优化

转移地址一般：pc相对立即数寻址

指令操作码优化 Huffman编码

理论平均最短编码长度 -plogp求和

把叶节点从左到右在底下一行，然后左1右0

平均位数小但变长编码不利于处理

扩展码 有限码长 比如2-4扩展3+4=7个

等长扩展码，比如15/15/15法即4位一扩展，等长15个

8/64/512法，四位扩展但头一致。保证头是若干1一个0

定长码也不错，便于处理

编码格式

可变长编码：复杂效果好，各条字长和时间都差很大

固定长度编码：RISC 译码简单

混合编码：若干固定字长

指令系统发展演进——CISC

cisc——RISC软件复杂性指数上涨

• 面向目标程序，高频指令组合
• 面向高级语言优化，缩小语义差距
• 面向操作系统优化
  RISC cisc二八，不利于流水

操作数类型大小

类型

• 操作数类型由操作码指定如ADDDU

• 数据赋硬件解释标记，带标识符的数据表示；指令系统简单硬件检测；简化编译器；动态开销大
  操作

• 数据传送

• 数逻

• 控制转移

L3 流水线技术

基本概念

控制复杂 利用率高

时间并行：分时使用一个部件的不同部分

空间并行：多个不同部件共同完成

时空图 横坐标时间，纵坐标阶段

通过时间，第一个任务进入到流出

排空时间，最后一个任务…

连接图 单指令从输入到输出，中间latch流水寄存

连续同类任务，流水段尽可能时间相等

部件级（某种运算操作）；（指令）处理器级；（任务）系统级

单功能、多功能（静态、动态，各段不同连接，同一时间内各段连接方式分为静态动态。同时间只一种功能为静态，即虽然能变但是需要前一种任务排空才进下一种任务）

顺序乱序：流入流出顺序相同？

标量向量

线性or非线性（反馈回路）

非线性需要连接图+预约表，前馈为forward

性能指标

吞吐率，单位时间的任务量（指令数），实际吞吐和最大吞吐（指令数n趋于无穷）

瓶颈段影响吞吐？细分瓶颈段，冗余设置并行瓶颈段（允许多条指令同时位于此段）

加速比 约为m 段数多需要任务更多

算时间一般算一条指令完整通过+ n-1 * 瓶颈节拍

效率 占用时空区/总时空区，在时空图上看面积/矩形

画时空图求解问题！看静态动态！

非线性流水线调度

禁止启动距离：引起流水线冲突的启动距离，

不发生冲突的启动序列启动循环（1,7）也有恒定循环（5）

• 禁止集合 每行的任何两个x距离如2 4 6 行内多个√就都算

• 冲突向量 禁止项为1，如101010

• 状态图不断逻辑右移，和初始向量或

  • 移1不管 所以只有1 3 5 7*或者7+
  • 移0 按位或

• 找到可用启动距离即回到初始的循环

• 找到最小平均启动距离
  定理：理想下限是任意行内x的最多个数

上限是冲突向量的1个数再加1

状态图简单循环的平均启动都是上限

如何达成理想最小的恒定循环 x的个数？

预留算法 插入非计算延迟段，每一行与x距离为2的倍数都留下来

动态调度 启动间隔集合 从启动循环推导出各个任务可能的启动间隔，先在原循环按1相连2相连…？？

相关与冲突

真相关|数据相关 真对角线方向，RAW 且可传递

名相关 名字一样但没有数据流动

• 反相关WAR 先读后写
• 输出相关WAW 两次写
• 换名技术，寄存器换名可以编译or硬件。把所有后面的同名寄存器换成S
  控制相关 if

流水线hazard

• 结构冲突：硬件不够
  • 流水or更多硬件资源
  • 如IF和MEM都读指令——分开I和D的mem；插气泡
• 数据冲突：需要用到前面结果还没出来
  • WAR和WAW只有乱序才发生 换名
  • RAW
    • 专用路径（前馈、旁路、定向技术） stall，解决ALU
    • MEM？stall or 编译器重新组织
• 控制冲突：分支指令or改PC指令
  • stall3个周期直到pc在mem改变再IF
  • 尽早分支——在ID分支只有1周期延迟
  • 静态预测（软件）
    • 预测失败，正常IF i+1 i+2
    • 预测成功，没什么好处，由于在ID才能算出target所以还是要延迟一周期
  • 延迟分支（软件）：分支+延迟槽，分支成功与否都要执行slot指令，掩盖暂停周期——多由编译器完成
    • 从前调度，找一个必执行的放slot里
    • 从target调度：保证失败时这条slot instr不会产生错误。有可能需要复制指令？？==预测成功
    • 从失败处调度：保证xxx ==预测失败
    • 如果延迟预测错误就把该slot指令除了IF全idle（设为空指令）

流水线实现

尽可能各段相等，段数多（深度）性能高

成本？

L4 向量处理机

SIMD

三种并行

• 指令级并行，多个指令同时执行：流水线；超标量；VLIW；乱序
• 向量数据并行SIMD：MMX SSE TPUGOOGLE 脉动阵列 GPU
  • ADDV
  • Cray1
• 线程级并行，多指令流MIMD？？
  • 多处理机多核
  • 多线程

向量表示和处理方式

一般向量机是大型机，有辅助的高性能标量处理器

微机+向量协处理器

向量平衡点 向量标量利用率相等，向量代码比例（我跑一秒你也一秒）

把问题转换为向量

• 等间距向量表示，从头，多少个多长的元素
  起始A

长度L 表示有多少个单元（元素）

间距f 表示元素间距

A+nf, n<L

• 带位移量的向量表示
  起始A 长度L 位移量f 有效长度L-f 起始地址A+f

即从A开始，下标从f到L的这么多元素

默认间距为32即字长

再加上个控制Vector表示真正执行操作的字

• 稀疏向量表示法
  表示向量为val向量+01位向量

可以展开计算，也可以压缩着计算

向量处理方式 循环展开语义下 假设向量为列向量

• 横向处理
  按循环体中横向处理，都有RAW相关效率低，不适合

频繁切换流水线

• 纵向处理
  展开循环之后算出所有中间结果，然后算最终结果

适合向量机，不同运算只切换1次

• 纵横处理 分组处理
  组内纵向，组间横向。比如向量长度100大于向量寄存器字长4？分组N = k*n + r

每组两条指令，功能切换2次，相关1次

向量机结构

一般相比于向量计算，忽略取指开销？

存储器存储器

纵向采用，多个独立存储器并行工作，结构简单；对存储的延迟、带宽要求很高

高带宽要求？多体交叉并行存储器 or 缓冲技术

15/2.167约等于7 * 32*6 =1344

无冲突访存存储器 bank conflict问题

存储体选质数且>=向量长度，一维数组不可能冲突 多次运算后分布改变，无法克服

操作数和写结果的可变缓冲器目标是Ai Bi同时到，可以更加规整的读写？？

n*n在行列对角线访问都不冲突？？

设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m＝2^2p＋1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1＝2^p，d2＝1 浪费但简单

找到满足n = 2^2p的p则n个就可以无冲突访问

体号地址：2(iL Å jH)＋(iH Å iL Å jL)

体内地址：j

寄存器寄存器

分组采用；高带宽的告诉寄存器，需要大量寄存器；对存储系统要求低

T存储器类似cache但需要手动管理

• 向量冲突（使用相同的Vi，RAR也不行因为向量长度不一定一样。即指令commit之前占用R和W的reg）
• 功能部件冲突，连续两个乘法

常用技术

• 多个功能部件并行工作
• 链接技术 针对RAW&&没有src冲突和功能冲突，连起来刘水处理。即前一步作为中间结果
  • 计算公式一般为 第一条指令完整通过时间+向量长度-1
  • 第一条（访存指令）是不要 V到部件的1拍时间的，但store指令需要前后各一拍
• 分段开采
  • 超过机器向量长度的需要分段开采，算迭代次数和余数处理等。
  • • 条件执行
  • 屏蔽向量，为0的不操作..
• 多处理机

性能评价

单条长度为n的向量指令处理时间T_vp

部件建立setup+通过时间exec+n-1时钟周期c

启动时间start 开始执行到还差一个周期就流出的周期数，意义是start+n = 时间，即把-1分配过去了

编队 一个周期内开始执行的几条向量指令，一定不存在功能和数据冲突，总时间为编队执行时间之和

循环开采计算 大循环，整个指令的循环，每次加T_loop即可

200 / 64， start和loop每次循环都要有 无链接的编队start计算是各个编队时间相加-1，如12+12+12+6-1 = 41

例4.5 和 4.6自相矛盾

链接之后的启动时间？直接相加即可，虽然不对！12+7

最大性能 峰值R无穷 频率*浮点次数/周期数

如200M * 2n / 3n+…

半性能长度 n1/2 最大性能一半时所需的向量长度，向上取整

长度临界值 优于串行的速度，

L5 指令级并行开发，硬件

对程序员透明

数据流动不变 | 异常行为不变

IR阶段划分为IR，I译码并发射，R读regfile

显式动态寄存器重命名？？

把后面所有寄存器全都换掉名字！

硬件维护映射表，结构寄存器Ri分配物理寄存器Pi，查找映射表最近一次写寄存器

缺点：要求物理比结构寄存器多，

Tomasulo 隐式寄存器重命名消除WAR和WAW

功能部件保留站：保留已经发射等待执行的指令，操作码 操作数等信息

操作Op 保留站号QjQk 操作数VjVk 有效位busy

load store中需要A，立即数或者有效地址

load缓冲

• 计算地址分量

• 记录正在load的地址，等待结果

• 暂存结果
  store缓冲

• 计算地址分量

• 记录正在store的地址，等待数据到达

• 保存数据和地址知道memory ok
  指令队列

• 先进先出的顺序发射
  寄存器状态表

• 寄存器就绪状态，发射rd指令则标记非就绪并记录此指令 Qi寄存器状态表
  运行规则

• 如果保留站空则可以发射——结构冲突

  • 隐式换名发射时如果没结果则换名成保留站部件标识，产生后可能换成了数据本身，反正不再和寄存器号有关了。WAR
  • 预约rd，消除WAW
  • 记得标记R【F2】或者M【A1|80】
  • 浮点：设置busy，记录op，处理rsrt和rd

• 保留站操作数就绪后开始执行，结束后发射cdb

  • Load只能exec头部指令，即即使多保留站也要按顺序执行
  • Store就绪
  • 写rd需要cdb来写等待的寄存器和保留站，并释放busy

• 写入延迟

  • 某个操作完成后需要下一个周期才写成结果，不管是regfile的结果还是cdb等待的结果。
  • 如果数据准备好则同时开始运行计数，5就绪7完成exec comp 8清除并且各个地方收到数据
  • 顺序发射 乱序执行和完成
  • 因保留站满而不发射时，保留站需要滞空一周期，考虑边缘写入规则？

• 假设循环控制时SUBI和BNEZ不发射，一周期完成？？
  总线CDB comefrom 总线，发射广播，正常goto是dest+data，这里是data+src

不支持精确中断！引入ROB重排序缓存保证顺序提交！

• CDB连接ROB而非regfile，指令从ROB读数据是个FIFO队列？？发射入队，提交出队
• 编号取代保留站编号，记录整个指令instr
• 运行情况分为issue发射周期，啥也不干 - exec1234执行计数周期，write已经writeback等待commit，awake所有等待的保留站但不提交寄存器。commit（nobusy）
• dest 目的寄存器
• value最终结果
• 发射到ROB和保留站里

分支预测缓冲器BHT 历史表

局部指令

2bit第一次在中立态？？

需要判定分支成功时间》确定分支地址时间，五段经典流水线这里啷个过程都在ID段，不会有好处

m n预测器前m此其他条件转移指令，选择2^m个nbit预测器？？

BTB分支目标缓冲 即Branch Target Buffer （cache）存上目标地址。找得到就branch否则顺序执行

或者结合BHT，把2bitBHT放在BTB里

结合ROB和tomasuloROB的分支指令提交？

• 提交为预测正确时，正常提交正常执行
• 提交为预测错误时，清除后续所有ROB和相关的保留站等。寄存器状态回退为上一个ROB依赖。

多指令发射

超标量 n发射

编译器静态，也可以tomasulo动态调度

对程序员透明

可以发射一条整数+1浮点。load和分支延迟

超长指令字VLIW

发射固定条数，构成超长指令，并行，指令调度静态

指令字中很多个操作slot，独立控制功能部件。靠编译器

L6 指令级并行开发，软件静态方法

1 指令调度循环展开

避免空转的编译器静态调度

循环展开后调度 循环展开+改变次序减少空转+寄存器换名，把名相关的换大的

2 跨基本块的静态调度（全局调度）

多发射下：缩短关键路径长度；单发射减少指令数

全局调度非常复杂

踪迹调度

踪迹多个基本块组成的一组序列，可以分支但一定没有循环。

优化高频踪迹，减少开销，非常适合多发射处理器，需加补偿代码

超块调度

超块只能有一个入口，多个出口 “尾复制技术”

3 静态多指令发射VLIW

需要很智能的编译器

多发射适应场景》向量处理器，不规则也能挖掘并行。对存储没要求，cache便宜

6.4-6.6 自学不考

L7 存储系统

性能评价：延迟、带宽

1 basics

速度 容量 价格

访问效率理论最快时间/实际时间

额外开销：请求M2并把M2的数据写入高级存储M1的时间

放置、查找、替换、写策略

2 Cache basics

以 块 为单位调入调出cache

区分块地址——已经抛掉比block更低位的地址了

直接映射

唯一位置，简单，速度快；空间低效，冲突多

tag index block_offset

全相连

任一块，利用好，冲突少；复杂，代价高，慢

tag block_offset

n-way组相连 CAM内容寻址存储器

tag index offset

指令cache 直接映射

数据cache 组相连

FIFO 装入替换时其他+1，换最大的

LRU 装入替换时其他+1 命中时候比他小的+1，他回0

写策略

• hit
  • 写直达 直接写回主存，可靠，慢（写停顿）
  • 写回 惰性，脏的时候替换的时候才写回主存。读操作也会产生写指令
• MISS
  • 写不分配 直接写入主存，不管cache。配合直达
  • 写分配 写入主存和cache，结合写回

3 cache miss rate

乱序处理器cache要求低，可以串行访问cache，低功耗高频率

• 强制性——增加块大小，预取
• 容量缺失——增加容量，成本高，命中慢
• 冲突缺失——某个组太多、直接映像。两路组相连一般容量和正常容量的直接相连差不多
  块大小和缺失率，是对钩函数，块大：强制缺失少，但块少冲突缺失多，不灵活。cache大，最优块也大

相连度大命中慢

伪相连 两路的话用一位bit预测在哪，只需比较一个tag。命中时间不一致，适合离cpu更远的cache

编译器预取：循环是预取的主要对象，缺失开销越大展开越多；执行指令和读数据同时执行；开销不要超过

编译器优化局部性：数组合并；循环交换、融合；分块

牺牲cache Victimcache，减少冲突缺失不影响时钟频率

cache和底层设置全相连小cache，用于存放被替换出去的牺牲者块。小容量的直接映射很有用。

4 cache miss cost

多级cache

局部缺失、全局缺失：到这的请求还是全部请求

平均停顿时间是相对于最快hit时间来说的

低级cache用更高的相连度，多为强制、冲突缺失；更大的块大小；

读缺失优先写缺失

写缓冲器带来的复杂，读缺失想读的内容还没被写进去？

推迟读缺失处理or检查写缓冲器。

写回法中先读缓冲器，之后再考虑写

写缓冲合并

匹配写缓冲器如果有则合并，之后写入

请求字

只立即需要一个word 从请求字读起，提早发送给cpu等

非阻塞cache

miss时还能让cpu正常hit其他地址

5 cache hit cost

硬件简单、小；物理地址PIPT cache 虚拟地址VIVT cache

还有什么狗几把VIPT等

访问流水化

L1 cache流水组织

踪迹cache

存放cpu执行的动态指令序列，包含分支预测指令。

6 parallel main memory

单体多字存储器 每个周期m个cpuword 简单，效率低

多体交叉存储区 多个单字存储，如何编址？

高位交叉编址？按高位区分存储体，适合行优先的按列读出，即存储矩阵列优先

低位交叉？低位区分存储体，行优先

避免冲突c存储体素数，循环交换，扩展数组大小为非2幂

L9 互联网络

循环表示法( 1 2 3 4)输出左移一位

互联函数

2交换|方体 Cubex或者Ex都是x位地址取反

3均匀洗牌σ 循环左移1，子函数下标取右边，超函数上标取左边

混洗交换：cube0+均匀洗牌 左右能换大范围也能换

4蝶式函数β 高低互换

5反位序函数ρ 整个颠倒

6移数函数α +-k mod N 错开连接

7PM2I函数 +-2^i mod N

求连接，正反求两次，自己作为x和y

网络结构参数、性能指标

网络直径D，任意两个节点距离最大值

等分宽度b，N个节点等分切开沿切口边数的最小值

等分带宽：沿着切边的带宽

通信延时：软件开销+通道时延+选路+竞争

网络延时：通道+选路

端口带宽

聚集带宽：一半到另一半的最大信息传输带宽，对称除二

静态互连网络

运行中不能改变，固定连接通路

1 线性阵列 vs总线：总线独占而线性阵列可以复用

2 环、带弦环：

全连接

3 循环移数：2的整数幂加一条边 16的话度为7 直径2

一般直径为log/2 度为2n-1

4 树、星

5 胖树

6 二维网格 网络直径为对角线，等分宽度为边长

k维？ 2k内部度 直径k(n-1)

illiac 二维网列相连，行尾连下一行头 直径n-1

环网 列、行都是封闭自相连 直径2*fl(n/2)

7 超立方体 n-立方体由2^n节点构成，4立方体共24+8

8 带环立方体3ccc 每个节点变成3元环

9 k元n立方体

动态互联网络

交换开关，可以动态变化

2 交叉开关网络，类似可编程逻辑一堆交叉点，全置换

3 多级互联网络

• staran网络 级（交换）和部分级（移数）控制
  • x组y元交换，交换都是全部倒过来
• 简介二进制n方体 单元控制
• Omega logN级 每个N/2个开关

消息传递机制

消息-包-片

• 线路交换，先建立线路时间开销打。适合动态突发大规模并行数据传输。先发一个L1/B模拟传输速度，先传输

• 存储转发 分组交换 L(D+1)/B

• 虚拟直通 包头到了就决定转发不用接全包，

• 虫蚀方式，切片流水，缓冲器小，延迟小，共享好；片会阻塞在节点占用资源
  

利用虚拟通道减少死锁

流控制策略？

• 包冲突：暂存缓冲区；阻塞；丢弃；绕道
• 确定or自适应寻经
• xy寻径，先横后纵
• n方体寻径，先低位后高维
• 单、选播 广播 会议

L10 多处理机

只考基本概念

SMP UMA 单存储器单IO 总线连接

分布式存储器 ，延迟小带宽要求小；缺点通信复杂，跨域延迟大

NUMA DSM分布式共享地址空间，

消息传递的硬件简单，通信显式|共享存储器易于编程，编译器简单

并行性能常依赖app的高层特性

2 对称式共享存储器

cache一致性问题

• 目录协议
• 监听协议
  • 写作废 作废其他副本 针对块
  • 谢更新 其他人都update 针对word | byte

3 分布式共享

目录记录block状态以及哪些cache持有副本

由于M= K×N， K是每个处理机中存储块的数量，所以如果K保持不变，则目录中的信息量（M×N =K×N2）就与N2成正比。

没缓冲|share|独占

本地；宿主；远程（拥有副本）

全映像目录每个目录都N位|有限映像m*logN即m个机器地址|链式目录

5 同步性能

细粒度线程：每个周期都切换；荫蔽吞吐损失；减慢单个线程，可以优先来缓解

粗粒度：短停顿还是会停顿

同时多线程SMT 多发射动态调度，只有细粒度有意义 8threads

6

• PVP并行向量 高带宽交叉网络 不cache
• 对称式共享存储器多处理机和分布式共享存储器多处理机
• 大规模并行处理机 非共享存储器；专门地址空间；消息传递 可扩放性
• 机群计算机 每个节点都完整