缓存一致性
介绍现代计算机体系结构中往往使用多级缓存加快访存速度,往往使用多级缓存,其中1,2级缓存为每个核独享,而3级缓存往往是所有核共享。如果不同核同时对同一地址进行写,那么针对同一地址便有了不同的值,这种问题称为缓存一致性问题。
监听协议监听协议的特点为:
实现了一种广播机制来通知更改,通常使用总线
当CPU涉及全局操作时,需要在获取总线控制权之后,才可以进行更改。例如写入内存
所有处理器一直监听总线,并检测总线上的地址是否在本地中存在,如果有,则进行操作
写操作的串行化: 写操作必须在获得总线后才可进行
一个简单的监听协议中每个数据块有三种状态:
无效: 总线中的缓存在本地中不存在
共享: 当前缓存可能在其他处理器中有副本。只要发出读请求,就会进入共享状态,无论其他处理器中是否存在
独占: 当前缓存只在该处理器中存在
当接收到来自处理器的请求时,会发生如下转换:
当读写命中时:
当读写未命中时:
当总线中的请求命中时:
总的来说,当写入一块缓存时,这片缓存将会切换到独占状态,并且清除其他处理器中的缓存。当读取一块缓存时,将从其他处理器和内存中取得,并且将状态修改为共享
...
乱序处理器
基础本文乱序处理器基于tomasulo算法。指令集为mips,参考书籍为《超标量处理器设计》
乱序处理器处理的主要是tomasulo算法中提到的相关,大致可以分为重命名,发射,执行,写回,退休五个阶段。除了这五个阶段外,前端还有取指和译码两个大的阶段。
译码译码主要解析出这条指令的rs, rt, rd, src1, src2和aluop。rs和rt是两个源操作数,rd为目的操作数, src1和src2是两个操作数的值,aluop是代表这条指令进行的操作。
需要特别注意的一点是mult和div的处理。因为mult和div是存在hilo寄存器中的,并且它写回时需要写回两个操作数,因此可以将它划分成两条指令。两条指令的rd分别为hi和lo。
重命名基于rob的重命名首先我们有一个rat(寄存器重命名表),他表示虚拟寄存器(r0-r31)和物理寄存器(真实的物理寄存器堆和rob)的映射关系。
寄存器重命名的过程为:
根据解析出来的rs和rt编号查rat表,与此同时查物理寄存器堆
如果当前值位于物理寄存器中,则直接取出,并且将当前src置为从寄存器中取出来的值,输出的寄存器编号置为0。否则重 ...
Tomasulo算法
冲突
结构冲突: 由于硬件资源争夺导致的冲突,例如同时两条指令产生访问请求,或者ICache和DCache同时对L2 Cache产生访问请求。
数据冲突: 数据冲突分为写后读冲突(RAW),写后写冲突(WAW),读后写冲突(WAR)。写后读可以认为写在读之后
控制冲突: 主要是分支指令导致的冲突
其中结构冲突和控制冲突无法避免,我们需要想办法消除数据冲突
WARADD F2, F0, F1SUB F3, F2, F4其中F2存在读后写相关RAWADD F2, F0, F1SUB F1, F3, F4其中F1存在写后读相关WAWADD F2, F0, F1SUB F2, F3, F4其中F2存在写后写相关
其中写后读相关是无法避免的,在乱序执行中必须要等待写完成才可以读,在顺序处理器中使用前推解决。而写后读相关和写后写相关在顺序处理器中是不存在的,但是在乱序处理器中可能存在问题。
例如写后写相关,本来存储器中最终保存的是SUB的数据,但是现在保存的是ADD的数据。而读后写相关调换位置就变成了写后读相关。
Tomasulo算法
大致步骤:
流水线前端的指令信息保存在指令队列中
根据指令 ...
PDede: Partitioned, Deduplicated, Delta Branch Target Buffer
摘要: 本篇文章设计了一个新的BTB组织形式,将地址划分为Region,Page,Offset三部分,然后三部分使用不同的表进行存储,从而减小分支目标重复存储的几率。最终ipc提升14.4%,BTB缺失的概率减少54.7%(这性能…)
现象
BTB中存在一些重复的目标,浪费了空间
跳转的分支占所有分支的超过一半,甚至有些超过三分之二
Region,Page,Offset三部分有不同的空间和时间局部性,并且有许多分支目标使用同样的Region和Page
超过60%的target在同一个Page内方法如图为该论文设计的结构,大致分为BTBM,Region BTB, Page BTB三部分
当搜索分支目标时,将首先搜索BTBM,然后使用Page-BTB Pointer和Region-BTB Pointer来搜索其他两个BTB,最后将Region, Page, Offset三部分拼接得到最终结果。
根据前面的发现60%的分支目标在同一个page内,因此BTBM中有一个Delta-Bit位,如果Delta-Bit为1,则分支目标在同一个Page内,直接使用Offset和当前PC拼接便可得到分支 ...
三维观察
三维观察是将一个三维物体投影到二维平面上的过程。一般需要经过建模变换、观察变换、投影变换、规范化变换和裁剪、视口变换
观察变换
观察坐标就是人眼观察事物的坐标,我们可以使用n作为z轴正向向量,v作为眼睛上方向量也就是y,u是视线的右方也就是x。
观察变换的目的就是把物体从世界坐标系转换到观察坐标系
可以进行如下两个步骤实现转换
将世界坐标的参考原点由世界坐标系原点平移到相机坐标系原点
进行旋转,使nuv分别对应zyx轴
第一步可以使用矩阵:
M_1 = \begin{bmatrix}
1 & 0 & 0 & -x_0\\
0 & 1 & 0 & -y_0\\
0 & 0 & 1 & -z_0\\
0 & 0 & 0 &1
\end{bmatrix}第二步可以使用矩阵:
M_2 = \begin{bmatrix}
x_u & y_u & z_u & 0\\
x_v & y_v & z_v & 0\\
x_n & y_n & v_n & 0\\
0 & 0 & 0 &1
\end{bmatrix}其中的分量都是nuv向量在xyz轴上的分量
综合可以得到最终的变换 ...
向量处理器和gpu
向量处理器传统的处理器每一条指令只能针对一个数据执行加减乘除等操作,而向量指令可以在一条指令中实现对多个数据进行操作。
RV64V的主要构成为:
向量寄存器:供32项,每一项包含32个64位元素。向量寄存器至少有16个读端口和8个写端口。为了实现大带宽,通常做法为使用多个存储体来组成寄存器堆
向量功能单元: 包括加减乘除,逻辑运算,浮点运算等单元,所有单元都是完全流水化的
向量存储/载入单元: 可以复用标量存储单元,然后每个周期取1-2个数据
例如给出下面一段代码,并使用向量指令实现
for(int i=0; i<32; i++) y[i] = a * x[i] + y[i];
使用RV64V实现为vsetdcfg 4*FP64 # 启用4个双精度浮点向量寄存器fld f0.a # 载入标量avld v0.x5 # 载入向量Xvmul v1.v0.f0 # 向量-标量乘vld v2.x6 # 载入向量Yvadd v3.v1.v2 # 向量-向量加vst v3.x6 ...
A Scalable Front-End Architecture for Fast Instruction Delivery
简介一个非常经典且现在都在使用的流水线前端架构。它的特点是将分支预测放在流水线的最前端,和取指进行了结构。将ICache移出了关键路径。
结构
部件介绍:
FTQ: 用来缓存分支预测器提供的预测地址,分支预测器会不停的预测并提交地址给FTQ,然后Icache从FTQ中获得取指地址并进行取指
FTB(fetch target buffer): 包括分支预测器,btb等
FTBFTB是该设计的核心部件,他可以保存分支跳转指令的跳转地址,并对条件分支进行预测。它的结构如下图所示。
它的主体是一个表,使用pc进行查表,查表方式和cache类似。每个表项表示一个fetch blcok,每个fetch block的起始地址为分支跳转到目的地址,中止地址(fall through)为经常发生跳转(biased taken or unbiased)的分支。查表时是通过起始地址进行查表的。
FTB每次生成下一个fetch block的起始地址和中止地址,以及用于下次预测的pc。
每个表项包含如下内容:
tag: 地址的高位,参照cache的tag项
carry, partial fall thr ...
决策树算法
基本结构决策树是一个类似流程图的树形结构:其中,每个节点表示在一个属性上的测试。每个分支表示一个输出,每个树叶节点代表类或类的分布。
上面这个例子中play和don’t play是结果,表示玩还是不玩。然后不是叶结点的节点都有一个问号,例如第一个outlook询问的是天气,后面还有湿度和是否刮风。通过这些条件得到了叶节点,叶结点都是只包含一种情况,要么是play要么是don’t play。
我们可以把OUTLOOK,HUMIDITY等称为属性,把其中的每一个选项称为类
现在问题的关键是如何确定进行划分的属性
决策树归纳算法(ID3)决策树适合小规模,类别比较少的数据集。
确定属性的基础就是信息熵,这可以用来表示我们可以获得信息的多少,信息增益多我们就可以认为它对我们有帮助。
我们以此图为例来讲解求解过程。首先最后一行是我们想要知道的答案
首先期望获得的信息可以由以下公式给出
\begin{aligned}
I(s_1 ,s_2 ,s_3 ..., s_m ) = -\sum_i p_i \log_2 (p_i )
\end{aligned}上述公式中$s_m$是结果中的第几 ...
sparql和cpyher
sparql原文链接
SELECT [DISTINCT] <variable1> [<variable2> ...][FROM ...]WHERE{ triple pattern 1. [triple pattern 2.] ... [附加条件...]}[OFFSET 数字][LIMIT 数字][ORDER BY | GROUP BY ...]例如SELECT ?xWHERE { dbr:James_Cameron dbo:directs ?x . }
符号:
variable: 变量,使用?变量名来表示变量,例如?x1
: 注释
*和+: 正则表达式,*表示0次或多次,+表示一次或多次
^: 用来反转主语和宾语之间的关系,例如s p o和o ^p s等价
/: 表示拼接谓语。例如?s c:cites/c:cites/c:cites :paperA表示s经过引用距离为3的所有论文
关键字:
WHERE: 用来表示查询条件,它由主谓宾三部分组成,其中主语和宾语可以为变量
FROM: 用来 ...
Branch Runahead: An Alternative to Branch Prediction for Impossible to Predict Branches
介绍论文原文
tage-sc-l分支预测器在大多数问题上都有很高的准确率,但是对于数据依赖型的分支却无能为力。例如判断一个数组中的某个数据是否为0,它依赖于数组的值,现有分支预测器都是基于过去分支的历史进行的,二者没有相关性,因此无法预测。
本文提出了一种提前执行分支指令的方法,通过一个小的处理器提前计算出分支结果,来处理分支预测器无法预测数据依赖型分支的问题
依赖链的计算守护分支和影响分支想要提前计算出分支指令,首先需要知道哪些指令和这个分支指令相关。这里首先需要给出两个定义
守护分支(Guard branch): 守护分支会决定另外的分支是否执行。例如两层的if,如果外层的if不执行,那么内层的if也不会执行,这时外层的if就是守护分支
影响分支(affector branch): 影响分支是可以影响其他分支源数据的分支。
要获得守护分支和影响分支首先需要知道分支正确路径和错误路径的合并点。由于现代乱序多发射的结构导致一次预测错误会多取上百条错误指令,因此可以使用正确路径的指令和错误路径的指令来找到两条路径的合并点。
守护分支的确定很简单,任何出现在合并点之前的分支都可以认为是 ...