精华内容
下载资源
问答
  • 1.线程级并行(Thread Level Parallelism) 并发(Concurrency)指的是在同一时间段内进行多个任务(但是一个时间点上只有一个任务在进行)。单处理器系统下,多线程实现的是并发而非并行。 并行(Parallelism)指的是在...

    1.线程级并行(Thread Level Parallelism)

    并发(Concurrency)指的是在同一时间段内进行多个任务(但是一个时间点上只有一个任务在进行)。单处理器系统下,多线程实现的是并发而非并行。

    并行(Parallelism)指的是在同一时间点时进行多个任务。多线程的并发需要在多处理器系统下才能实现,而多处理器实现一般依赖于以下两个技术:

    • 超线程技术(Hyper-Threading,简称HT)

            超线程技术实现了单个物理核心同时两个线程,也就是别人常说的虚拟内核数。比如单物理核心实现的双线程,它同时可以处理两个线程,它的物理核心数其实是是1个,通过Hyperthreading技术实现的线程级并行(Thread Lever Parallelism)。

    • 多核技术(Mult-Core Processor)

            处理器中包含多个内核,每一个内核均可以独立处理线程,也可以同时利用HT技术,一个核心处理多个线程。

    2.指令级并行(Instruction Level Parallelism)

    指令级并行,依赖于指令级流水技术,通过指令级的流水达到在同一时间点(指令周期,更准确的说)内,无数据依赖的指令同时执行。常见的依赖关系包括真依赖(Read After Write, RAW)和两个存储相关依赖,即反依赖(Write After Read, WAR)和写后写(Write After Write)。后两种依赖可以通过使用额外的存储来避免,前一种往往需要通过其他手段,如添加空周期、指令调度(在中间添加其他无依赖的指令增加两条指令中间间隔的周期)和数据旁路技术(在Write指令执行阶段就将结果送给Read指令)。

    RISC(Reduced Instruction Set Computers)架构相较于CISC(Complex Instruction Set Computers)架构,由于具有更小而简单的指令执行阶段,更加便于实现流水技术。但是,对CISC而言,复杂的指令是通过微程序实现的,而微程序又由小而简单的微指令构成,因此也可以受益于流水技术。

    3.数据级并行(Data Level Parallelism)

    主要运用了SIMD(Single -Instruction ,Multple -Data)单指令多数据流技术。通过一个指令,对多个相同类型的数据(也叫"数据向量”)进行同一的操作。SIMD指令集可以提供更快的图像,声音,视频数据等运行速度,常见的SIMD指令集有MMX,SSE4和AVX。

    展开全文
  • 计算机系统结构第4章指令级并行与限制第四章 指令级并行及限制;4.1 指令级并行的概念 ;4.1.1 指令级并行;3、循环级并行:使一个循环中的不同循环体并行执行。开发循环体中存在的并行性最常见、最基本是指令级并行...

    计算机系统结构第4章指令级并行与限制

    第四章 指令级并行及限制;4.1 指令级并行的概念 ;4.1.1 指令级并行;3、循环级并行:使一个循环中的不同循环体并行执行。开发循环体中存在的并行性最常见、最基本是指令级并行研究的重点之一例如,考虑下述语句: for (i=1; i<=500; i=i+1) a[i]=a[i]+s;每一次循环都可以与其他的循环重叠并行执行;在每一次循环的内部,却没有任何的并行性。 ;4、最基本的开发循环级并行的技术循环展开(loop unrolling)技术采用向量指令和向量数据表示;4.1.2 相关性对指令级并行的影响;例4-1 对于下面的源代码, for (i=1; i<=1000; i++) x[i] = x[i] + s;(Ⅰ)转换成DLX汇编语言,在不进行指令调度和进行指令调度两种情况下,分析代码一次循环的执行时间。

    (Ⅱ)编译过程进行分析,来仔细考察换名的过程。

    备注:本章使用的浮点流水线的延迟如上表所示;解: (Ⅰ) (1) 变量分配寄存器 整数寄存器R1:循环计数器,初值为向量 中最高端地址元素的地址。 浮点寄存器F2:保存常数S。 假定最低端元素的地址为8。 (2) DLX汇编语言后的程序 Loop:LDF0,0(R1) ADDDF4,F0,F2 SD0(R1),F4 SUBIR1,R1,#8 BNEZR1,Loop;(3) 程序执行的实际时钟;(4) 指令调度以后,程序的执行情况;(Ⅱ);(2) 编译器可以通过对相关链上存储器访问偏移量的直接调整,将前3条SUBI指令消除掉,从而得到下面一个14条指令构成的指令序列,如下所示:Loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 LD F0 , -8(R1) ADD.D F4 , F0 , F2 SD -8(R1) , F4 LD F0 , -16(R1) ADD.D F4 , F0 , F2 SD -16(R1) , F4 LD F0 , -24(R1) ADD.D F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop ;(3) 通过寄存器换名,消除名相关。得到下面的指令序列,如下所示:Loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 LD F6 , -8(R1) ADD.D F8 , F6 , F2 SD -8(R1) , F8 LD F10 , -16(R1) ADD.D F12 , F10 , F2 SD -16(R1) , F12 LD F14 , -24(R1) ADD.D F16 , F14 , F2 SD -24(R1) , F16 SUBI R1 , R1 , #32 BNEZ R1 , Loop;再来看一个控制相关的例子。 ;控制相关会带来两方面的限制:;再考察例4-1,假设循环展开时,循环控制分支指令没有去除,则指令序列如下所示: ;由于上述指令段中BEQZ R1 , Exit,BEQZ R1 , Exit,BEQZ R1 , Exit三条分支指令的存在,引起控制相关,导致其后的4条指令不能跨越分支指令进行调度,即不同循环遍次里的指令不能够跨越循环遍次进行调度。 ;4.1.3支持指令级并行的基本编译技术;1.检测并提高循环级并行; 在这个循环程序中,用到了两次x[i],它们之间即存在数据相关,但这是循环体内的相关而不是体间相关。在相邻的两次对i的引用上,存在体间相关,但这种相关包含规约变量,很容易识别和消除。;循环体间相关常常以重现的形式出现的:for (

    展开全文
  • 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十个、几千个、几万个等)通过网络连接以一定的方式有序地组织...

    第一章
    1、并行计算的定义和主要目的P11
    定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十个、几千个、几万个等)通过网络连接以一定的方式有序地组织起来(一定的连接方式涉及网络的互联拓扑、通信协议等,而有序的组织则涉及操作系统、中间件软件等)。
    并行计算的主要目的:
    一是为了提供比传统计算机快的计算速度;
    二是解决传统计算机无法解决的问题。
    2、并行计算研究的主要内容P12-17
    (1)并行计算机的设计
    (2)有效算法的设计
    (3)评价并行算法的方法
    (4)并行计算机语言
    (5)并行编程环境与工具
    (6)并行程序的可移植性
    (7)并行计算机的自动编程
    3、并行计算机体系结构要素P34-37
    结点、互联网络、内存
    4、什么是并行计算机、并行计算机的组成部分P26-27
    并行计算机是由一组处理单元组成的,这组处理单元通过相互之间的通信与协作,以更快的速度共同完成一项大规模的计算任务。
    并行计算机的组成部分:计算节点和节点间的通信与协作机制。

    5、进程的定义、状态和进程间的信息交流方式P39-40
    (1)进程的定义:进程(process)可表示成四元组(P, C, D, S)
    P是程序代码
    C是进程的控制状态
    D是进程的数据
    S是进程的执行状态
    (2)进程的状态:
    非存在状态:进程依赖的程序还没有投入运行
    就绪状态:进程由其父进程调入并准备运行
    运行状态:进程占有CPU和其它必须的计算资源,并执行指令
    挂起状态:由于CPU或其它必须的计算资源被其它进程占有,或必须等待某类事件的发生,进程转入挂起状态
    退出状态:进程正常结束或因异常退出而被废弃
    (3)进程间的信息交流方式:
    进程是操作系统资源调度的基本单位
    各进程不能直接访问其它进程的局部内存空间
    多个进程之间相互交流信息 的三种形式 :
    通信:进程间的数据传递称为进程间通信
    同步:同步是使位于相同或不同处理机中的多个进程之间相互等待的操作
    聚集:聚集将位于相同或不同处理机中的多个进程的局部结果综合起来

    6、并行计算机的分类Flynn(1966年)分类法P48

    Flynn(1966年)分类法是根据系统的指令流和数据流对计算机系统进行分类的一种方法。

    指令流:机器所执行的指令序列
    数据流:指令流调用的数据序列(包括输入数据和中间结果)

    1)SISD:传统的单处理机系统。由程序生成的一个单指令流,在任意时刻处理单独的数据项。
    2)SIMD:如:阵列处理机系统(Processor Arrays)。由一个控制器负责从存储器中取出指令并将这些指令发送给各个处理器,每个处理器同步执行相同的指令,但操作不同的数据。
    3)MISD:相当于在指令一级并行,而在被操作的数据级串行的情况,实际上这种模型是不能实现的。
    4)MIMD:当今绝大多数并行计算机都属于这一类。每个处理器拥有一个单独的程序,每个程序为每一个处理器生成一个指令流,每条指令对不同的数据进行操作。

    第二章
    1、并行处理技术的核心P1
    核心:增加同一时间间隔的操作数
    2、并行算法的定义P3
    并行算法:适合于并行操作的一类算法的总称。
    并行算法是指在各种并行计算机上求解问题和处理数据的算法,其本质是把多个任务映射到多个处理器中执行。并行算法的实现强烈依赖于计算机硬件环境和软件环境。
    3、并行算法的分类P4
    按运算对象分类
    数值算法、非数值算法;
    按进程间程序执行的顺序关系分类
    同步算法、异步算法;独立并行算法;
    (分布式算法)
    按处理机承担的计算任务粒度分类
    细粒度并行算法、中粒度并行算法、
    大粒度并行算法
    4、并行算法运行时的相关时间定义P5-7
    并行算法运行时间:并行算法在具体并行计算机上求解一个问题所需时间。一般用Tp表示。
    如果并行算法的不同任务进程不能同时开始或同时结束,并行算法运行的时间定义为:第一个任务进程开始执行的时间算起到最后一个任务进程执行完毕所需的时间。

    5、并行机的规模P9
    并行计算机的规模指某一具体并行计算机所具有的最大计算性能,包括处理机台数、单机性能、网络带宽、整体内存大小与输入输出能力等硬件指标;还涉及操作系统、并行程序设计环境等软件指标。
    6、问题的规模和分类P10
    问题规模:指问题求解的规模或问题求解的大小。问题规模是衡量并行计算机性能的一个重要参数。可以将问题规模大致分为:输入输出规模、计算规模、内存需求规模和通信(同步)规模。
    应用问题的分类:
    根据算法实现的难易程度、通信方式,将问题分为:同步问题(松散同步问题、非规则松散同步问题)、异步问题、独立并行问题。
    7、并行算法的度量指标P12-13
    除运行时间、并行机规模和问题规模,对于并行算法的度量指标还包括
    1)并行度:算法中可并行执行的单位操作数
    操作是计算的基本单位,一般指加减乘除等基本算术运算,也可以指某一任务级的作业。
    2)粒度:粒度是一个相对的概念,与算法固有的内在并行度和具体的并行机相关。大粒度以为着并行执行的是大任务。
    3)成本:运行时间与处理机个数的乘积
    4)加速比:在单处理机上的运行时间除以多处理机上运行的时间
    8、绝对加速比和相对加速比的定义P18-19
    绝对加速比:将最好的串行算法与并行算法相比较.
    定义一(与具体机器有关)将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。
    定义二(与具体机器无关)将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。
    在这里插入图片描述

    相对加速比:同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。
    这种定义侧重于描述算法和并行计算机本身的可扩展性。
    在这里插入图片描述

    9、可扩展性的直观定义、研究目的和度量方法P47-49
    直观定义:对任意数量(n)的处理机和任意规模(s)的问题,若所有算法的系统效率 E =1, 则系统是可扩展的。
    可扩展性的研究目的:
    1)确定某类问题的何种并行算法与何种并行系统的组合,可有效的利用系统大量处理机
    2)有算法在小规模并行机上的运行性能来预测起移植到大规模并行机上后的运行性能
    3)对一固定规模的问题,能确定起运行在某类并行系统上时,所需的最有处理机台数和获得的最大加速比
    4)指导并行算法和并行机体系结构的改进
    度量方法:
    等效率可扩展性度量方法:揭示问题规模与系统规模的关系(1987);
    等速度可扩展性度量方法:揭示并行算法-机器组合的关系(1996)
    等时间/通信开销比的可扩展性度量方法:等计算时间/通信开销比(1999)
    可扩展性度量方法的基本要求:
    1)能提供并行系统规模的变化如何影响起性能的信息;2)能描述并行算法与并行机组合的函数;3)可评估、可比较的定性性能度量方法。

    第三章
    1、并行计算模型的定义和作用P3-4

    定义: 并行计算模型:从并行算法的设计和分析出发,将各种并行计算机(至少是某一类)的基本特征抽象出来,形成一个抽象的并行计算模型。
    并行计算模型的作用
    1)是并行算法实现的基础
    2)给并行算法设计与分析提供了一个简单方便的框架
    3)使并行算法的设计具有一定的生命力

    2、PRAM模型定义、优缺点P7-9
    定义:PRAM(Parallel Random Access Machine)模型是单指令流多数据流(SIMD)并行机中的一种具有共享存储的模型。它假设有一个无限大容量的共享存储器,并且有多个功能相同的处理器,在任意时刻处理器可以访问共享存储单元。
    优缺点:
    优点
    适合并行算法表示和复杂性分析,易于使用,隐藏了并行机的通讯、同步等细节。
    缺点
    不适合MIMD并行机,忽略了SM的竞争、通讯延迟等因素
    不现实,首先容量无限大的存储器是不存在的,而且由于各方面的原因,全局访存通常要比预想的慢。其次,他忽略了通信带宽的影响。

    3、APRAM模型定义、优缺点P10、P14
    定义:
    又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序;无全局时钟,各处理器异步执行;处理器通过SM进行通讯;处理器间依赖关系,需在并行程序中显式地加入同步(路)障(Synchronization Barrier)。
    优缺点
    易编程和分析算法的复杂度,但与现实相差较远,其上并行算法非常有限,也不适合MIMD-DM模型。
    4、LogP模型的参数表示意义、优缺点P16-17
    参数表示意义:
    L(Latency):源处理机与目标处理机之间进行消息通信(一个或几个字)所需等待的延迟时间的上限。
    o(overhead):处理机用于发送或者接受每个消息的时间开销。
    g(gap):一台处理机连续进行消息发送或接收时的最小时间间隔。
    P(Processor):处理机或处理模块的数量
    LogP模型是异步的,假设所有消息都很短。
    优缺点:
    捕捉了MPC的通讯瓶颈,隐藏了并行机的网络拓扑、路由、协议,可以应用到共享存储、消息传递、数据并行的编程模型中;但难以进行算法描述、设计和分析。
    5、BSP模型中参数的意义P19
    BSP模型以三个参数描述分布式存储的多计算模型。三个参数:
    处理机(P)
    处理机之间的点对点通信的选路器(g)
    执行以时间间隔L为周期的路障同步器(L)
    6、LogP模型与BSP模型之间的关系P18-19
    BSP vs. LogP
    BSPLogP:BSP块同步BSP子集同步BSP进程对同步=LogP
    BSP可以常数因子模拟LogP,LogP可以对数因子模拟BSP
    BSP=LogP+Barriers-Overhead
    BSP提供了更方便的程设环境,LogP更好地利用了机器资源
    BSP似乎更简单、方便和符合结构化编程
    7、并行算法设计的常用手段P20
    设计算法经常采用以下三种手段:
    1)将现有的串行算法中固有的并行性直接并行化;
    2)从问题本身出发设计一个新的算法;
    3)修改已有的并行算法,使其可以求解相似问题
    8、并行算法常用的设计技术P48-49
    目前普遍使用的并行算法的设计技术:
    1).流水线技术
    将任务分割成许多子任务,每个处理器完成其中一个,且第一个处理器完成第一个子任务后,第二个处理器可以开始完成第二个子任务…
    2).分治策略
    将原问题分成若干个特征相同的子问题,分别处理。
    常见的分治策略:任务分割;数据分割
    3).平衡树方法
    将输入元素作为叶子节点构造二叉平衡树。
    4).倍增技术(指针跳跃技术)
    适合处理链表、有向图等数据结构;经常应用于通信系统中。
    5).加速级联策略
    将最优算法(计算速度慢)和最快算法(不是最优)级联起来。
    9、并行程序设计的主要方式P51
    并行程序的设计有多种方式,主要分为:
    共享变量方法;消息传递方法;数据并行程序设计;面向对象的并行程序设计;函数程序设计方法;逻辑程序设计方法。
    第四章
    1、三对角方程组的并行求解的常方法P31
    求解三对角线性方程组的并行算法有很多:追赶法、基于递推公式的并行算法、循环约化法、分裂法等。我们这里只考虑目前最有效的矩阵分裂法。

    2、稀疏矩阵的压缩存储P69
    矩阵的压缩存储:为多个值相同的元素只分配一个存储空间,对零元素不分配空间
    一般来说,稀疏矩阵非0元素的分布是无规律的。因此,在存储非0元素的同时,还要存储适当的辅助信息。
    稀疏矩阵常用的压缩存储方式:(1)三元组表(2)十字链表
    (1)三元组表:存储特点:
    对于矩阵中每个非0元素,用它的行号、列号、元素值,即(i, j, aij)表示。
    将表示稀疏矩阵的所有非0元素的三元组按行优先(列优先)顺序排列,则可得到一个其结点均是三元组的线性表,称为三元组表。
    要唯一确定一个稀疏矩阵,还必须存储该矩阵的行数和列数。
    (2)十字链表:十字链表是稀疏矩阵链接形式存储结构的一种(当然还有其它形式)。
    在该方法中每一个非0元素用一个结点表示,结点中除了表示非0元素的行、列和值的三元组外,还增加了两个链域:
    行指针域:用来指向本行中下一个非0元素;
    列指针域:用来指向本列中下一个非0元素。
    在每一个行链表和每一个列链表增加一个和表结点相同的表头结点,表头结点中的行、列域置为0,并且将所有的行、列链表和他们的头结点一起链成一个循环链表。

    实际实现时,两组头结点可以合用,即第i行链表和第i 列链表共享一个表头结点。因为表头结点中值域v无用,所以可以将它作为指针域,用来指向下一个表头结点的指针。

    3、矩阵与向量乘法的并行设计(一维划分)P12-16

    4、矩阵与矩阵乘法的并行设计(行列划分)P27-29

    5、Cannon 算法P41-45
    第五章
    1、矩阵的LU分解

    2、三对角方程组的并行求解

    3、Arnoldi算法P69

    4、FOM算法P74

    第九章
    1、消息传递模型的原理和优缺点P208
    原理:消息传递模型中,计算由一个或多个进程组成,进程间的通信通过调用库函数发送和接收消息来完成。
    优点:
    1)具有高度的可移植性。
    2)允许用户显式地控制控制并行并行程序的存储,特别可以控制每个进程所使用的内存。(需要编程人员对内存分配,需要考虑通信顺序等细节问题)
    缺点:消息传递接口的不同对程序性能将产生重要影响,主要因素有:实际消息传递的带宽、延迟和计算与通信的重叠。

    2、什么是MPI?P209-210
    MPI一个信息传递接口的标准,用来开发基于信息传递的并行程序,它的目的是为用户提供功能强、可移植和灵活的信息传递接口库。(注:MPI是一个库而不是一种语言)
    3、MPI中6个常用函数的基本功能P211
    MPI_INIT 初始化MPI
    MPI_FINALIZE 终止MPI
    MPI_COMM_SIZE 确定进程的数目
    MPI_COMM_RANK 确定进程的序号
    MPI_SEND 发送一条信息
    MPI_RECV 就收一条信息
    补充部分
    1、Matlab并行循环执行的前提条件Chap2(一)P1
    对于次数确定的循环(for循环),如果循环的‘计数模块’对于单次循环是独立的(计算结果与循环体的执行顺序无关),那么理论上可以将整个循环拆分成几个子循环,然后将子循环的结果合并。
    2、简约操作及其满足条件Chap2(一)P51-57
    只有当循环的操作题相互独立时才可以用parfor关键字进行并行。但是有一类特殊的循环操作不受这个条件限制,这类操作我们称为简约操作。
    简约操作所对应的循环体并不独立,但是执行结果与执行顺序无关。

    简约变量在parfor中应该满足一些要求
    1.简约变量只能出现在简约赋值操作的表达式中
    简约操作可以由上面给的各种操作符引导,也可以自己定义。
    2.在同一parfor中,对简约变量的操作必须一致。
    3.如果简约变量的操作是‘*’或者‘[]’,x在操作符前面或者后面都可以,但是位置必须恒定。
    4.简约变量赋值应满足结合律和交换律

    3、在parfor循环中,Matlab变量主要分类Chap2(二)P2
    循环变量(loop variable)
    分段变量(sliced variable)
    广播变量(broadcast variable)
    简约变量(reduction variable)
    临时变量(temporary variable)

    4、SPMD并行结构的优势Chap3P10
    SPMD并行结构给用户提供了更大的自由度,用户可以控制更多的并行计算的细节。

    5、SPMD结构中可以使用的三种数据对象
    数据集分割方式:
    1)通过数据文件的方式将大的数据集分割到各个计算节点;
    2)通过composite对象(Matlab特有结构);
    3)通过分布式数值阵列(Matlab特有结构)。
    6、一般并行程序的数据类型Chap5P3-7
    1)同体变量2)异体变量3)独有变量4)分布式变量
    7、常用两种通用并行程序设计的方式
    Matlab并行程序一般由三种方式实现:
    1)利用Matlab内置的并行结构;
    2)利用Matlab提高的通用并行程序设计;
    3)Matlab和其他语言混合编程

    展开全文
  • 文章目录第5章 指令级并行及其开发—硬件方法5.1 指令级并行的概念5.1.1 相关概念介绍5.2 相关与指令级并行5.2.1相关与流水线冲突5.2.2 程序顺序5.3 指令的动态调度5.3.1 动态调度的基本思想5段流水线的最大局限性...

    第5章 指令级并行及其开发—硬件方法

    5.1 指令级并行的概念

    指令级并行(Instruction-Level Parallelism,ILP):指指令之间存在的一种并行性,利用它,计算机可以并行执行两条或两条以上的指令。

    5.1.1 相关概念介绍

    开发ILP的两种途径:

    • 资源重复:重复设置多个处理部件,让它们同时执行相邻或相近的多条指令;
    • 采用流水线技术:使指令重叠并行执行。

    开发ILP的方法可以分为两大类:

    • 主要基于硬件的动态开发方法(本章内容)
    • 基于软件的静态开发方法

    流水线处理机的实际CPI

    • 理想流水线的CPI加上各类停顿的时钟周期数
      C P I 流水线 = C P I 理想 + 停顿 结构冲突 + 停顿 数据冲突 + 停顿 控制冲突 CPI_\text{流水线} = CPI_\text{理想} + \text{停顿}_\text{结构冲突} + \text{停顿}_\text{数据冲突} + \text{停顿}_\text{控制冲突} CPI流水线=CPI理想+停顿结构冲突+停顿数据冲突+停顿控制冲突

    • 理想CPI是衡量流水线最高性能的一个指标

    • IPC:Instructions Per Cycle:每个时钟周期完成的指令条数

    基本程序块

    • 基本程序块:一串连续的代码除了入口和出口以外,没有其他的分支指令和转入点
    • 实际上程序平均每4~7条指令就会有一个分支。

    循环级并行

    • 使一个循环中的不同循环体并行执行。
    • 开发循环的不同叠代之间存在的并行性 (最常见、最基本)
    • 是指令级并行研究的重点之一
    • 一种开发循环级并行性的重要方法是采用向量指令向量数据表示

    5.2 相关与指令级并行

    5.2.1相关与流水线冲突

    相关有三种类型:

    • 数据相关、名相关、控制相关
    • 流水线冲突是指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条指令不能在指定的时钟周期执行。
      • 流水线冲突有三种类型:结构冲突、数据冲突、控制冲突
    • 相关是程序固有的一种属性,它反映了程序中指令之间的相互依赖关系。
    • 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿,则是流水线的属性

    可以从两个方面来解决相关问题:

    • 指令调度 :保持相关,但避免发生冲突。
    • 通过代码变换,消除相关。

    5.2.2 程序顺序

    程序顺序:由原来程序确定的在完全串行方式下指令的执行顺序。

    • 只有在可能会导致错误的情况下,才保持程序顺序。

    程序顺序与属性

    控制相关:并不是一个必须严格保持的关键属性(不是提高性能的主要限制)。

    对于正确地执行程序来说,必须保持的最关键的两个属性是:数据流异常行为

    • 保持异常行为是指:无论怎么改变指令的执行顺序,都不能改变程序中异常的发生情况。
      • 即原来程序中是怎么发生的,改变执行顺序后还是怎么发生。
      • 弱化为:指令执行顺序的改变不能导致程序中发生新的异常
    • 数据流:指数据值从其产生者指令到其消费者指令的实际流动。
      • 分支指令使得数据流具有动态性,因为一条指令有可能数据相关于多条先前的指令。
      • 分支指令的执行结果决定了哪条指令真正是所需数据的产生者。

    有时,不遵守控制相关既不影响异常行为,也不改变数据流。

    • 可以大胆地进行指令调度,把失败分支中的指令调度到分支指令之前。

    例如:对于以下程序

              DADDU     	R1,R2,R3
              BEQZ	R12,Skipnext
              DSUBU	R4,R5,R6
              DADDU	R5,R4,R9
    Skipnext:OR	R7,R8,R9
    
    • 假设我们知道R4在Skipnext之后不再被使用,而且DSUBU不会产生异常,那么就可以把DSUBU移到分支指令之前。这是因为这个移动不会改变数据流。

    • 如果分支成功,尽管按原程序DSUBU指令是不该执行的,但现在执行了也没关系,因为它不会影响程序的执行结果。

    5.3 指令的动态调度

    静态调度与动态调度的对比

    静态调度动态调度
    调度发生时间在编译期间进行代码调度和优化在程序的执行过程中
    依靠依靠编译器对代码进行静态调度,以减少相关和冲突依靠专门硬件对代码进行调度
    调度方式通过把相关的指令拉开距离来减少可能产生的停顿减少数据相关导致的停顿

    动态调度的优缺点

    优点缺点
    能够处理一些在编译时情况不明的相关(比如涉及到存储器访问的相关),并简化了编译器硬件复杂性的显著增加为代价
    能够使本来是面向某一流水线优化编译的代码在其它的流水线(动态调度)上也能高效地执行

    静态与动态流水线的时空图

    静态和动态流水线的时空图

    5.3.1 动态调度的基本思想

    5段流水线的最大局限性

    到目前为止我们所使用流水线(5段流水线)的最大的局限性:

    • 指令是按序流出按序执行

    例:考虑下面一段代码:

    DIV		F4,F0,F2
    ADD		F10,F4,F6 
    SUB		F12,F6,F14
    
    • ADD指令与DIV指令关于F4相关,导致流水线停顿。
    • SUB指令与流水线中的任何指令都没有关系,但也因此受阻。
    • 这是按序流出和按序执行带来的局限性。如果可以不按程序顺序执行指令,就能进一步提高性能。

    在5段流水线中,结构冲突和数据冲突都是在译码(ID)段进行检测的。只有当既没有结构冲突也没有数据冲突时,指令才能够流出。为了使上述指令序列中的SUB指令能继续执行下去,必须把指令流出的工作拆分为两步

    1. 检测结构冲突;
    2. 等待数据冲突消失。

    只要检测到没有结构冲突,就可以让指令流出。并且流出后的指令一旦其操作数就绪就可以立即执行。

    ⚠️修改后的流水线是乱序执行

    • 即指令的执行顺序程序顺序不相同。

    • 同样,指令的完成也是乱序完成的,即指令的完成顺序程序顺序不相同。

    • 为了支持乱序执行,将前述5段流水线的译码(ID)段细分为两个段。

      1. 流出(Issue,IS):指令译码,并检查是否存在结构冲突。如果不存在结构冲突,就将指令流出。
      2. 读操作数(Read Operands,RO):等待数据冲突消失(如果有),然后读操作数。

      指令的流出仍然是按序流出(In-order Issue)的。

      但是,它们在读操作数段可能停顿和互相跨越,因而进入执行段时就可能已经是乱序的了。

    修改前后的时空图

    按序发射按序执行
    DIV F4,F0,F2IFIDEXMEMWB
    ADD F10, F4, F6stallstallstallIFIDEXMEMWB
    SUB F12, F6, F14IFIDEXMEMWB
    无序发射无序执行
    DIV F4,F0,F2IFIDEXMEMWB
    ADD F10, F4, F6stallstallstallIFIDEXMEMWB
    SUB F12, F6, F14IFIDEXMEMWB

    在前述5段流水线中,是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。

    考虑以下代码:

    DIV	  F10, F0, F2
    ADD	  F10, F4, F6
    SUB	  F6, F8, F14
    
    • DIV指令与ADD指令存在输出相关
    • ADD指令和SUB指令存在反相关
    • 可以通过使用寄存器重命名(换名)来消除。

    动态调度的流水线支持多条指令同时处于执行当中。

    • 要求:具有多个功能部件、或者功能部件流水化、或者兼而有之。
    • 我们假设具有多个功能部件

    指令乱序完成带来的最大问题:

    • 异常处理(中断)比较复杂
      • 分为:精确异常处理、不精确异常处理
      • 不精确异常:当执行指令i导致发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同。
      • 精确异常:当执行指令i导致发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场相同。要设置一定数量的后援寄存器,把流水线中所有指令的执行结果和现场保存下来。成本高,现在都这样实现。
    • 动态调度的处理机保持正确的异常行为的方式:
      • 对于一条会产生异常的指令来说,只有当处理机确切地知道该指令将被执行时,才允许它产生异常。
    • 即使保持了正确的异常行为,动态调度处理机仍可能发生不精确异常。
      • 发生不精确异常的原因:因为当发生异常(设为指令i)时:
        • 流水线可能已经执行完按程序顺序是位于指令i之后的指令;
        • 流水线可能还没完成按程序顺序是指令i之前的指令。
      • 不精确异常使得在异常处理后难以接着继续执行程序。

    精确断点法与不精确断点法

    • 精确断点法

      • 要设置一定数量的后援寄存器,把流水线中所有指令的执行结果和现场保存下来。
    • 不精确断点法:

      • 流水线可以不“断流”;
      • 所需要的硬件比较少,控制逻辑相对比较简单
      • 中断响应时间稍长,要增加一条流水线的时间长度
    • 采用不精确断点法可能会发生如下两个问题:

      • 程序执行的结果可能出错
      • 程序的调试困难

    5.3.2 记分牌动态调度算法

    CDC 6600计算机最早采用此功能

    记分牌算法的基本思想

    • 该机器用一个称为记分牌的硬件实现了对指令的动态调度。
    • 该硬件中维护着3张表,分别用于记录指令的执行状态功能部件状态寄存器状态以及数据相关关系等。
    • 它把前述5段流水线中的译码段ID分解成了两个段:流出段读操作数段,以避免当某条指令在ID段被停顿时挡住后面无关指令的流动。

    记分牌的目标

    • 在没有结构冲突时,尽可能早地执行没有数据冲突的指令,实现每个时钟周期执行一条指令。

    要发挥指令乱序执行的好处,必须有多条指令同时处于执行阶段。

    • CDC 6600具有16个独立的功能部件
      • 4个浮点部件
      • 5个访存部件
      • 7个整数操作部件

    为了讨论的简单,假设所考虑的处理器有2个乘法器、1个加法器、1个除法部件和1个整数部件。

    • 整数部件用来处理所有的存储器访问、分支处理和整数操作

    记分牌的MIPS处理器的基本结构

    记分牌算法的执行

    每条指令的执行过程(EX段)分为4段 (主要考虑浮点操作 )

    • 流出
      • 如果当前流出指令所需的功能部件空闲,并且所有其他正在执行的指令的目的寄存器与该指令的不同(其他指令不写该指令的目的寄存器),记分牌就向功能部件流出该指令,并修改记分牌内部的记录表。
      • 解决了WAW冲突
    • 读操作数
      • 记分牌监测源操作数的可用性,如果数据可用,它就通知功能部件从寄存器中读出源操作数并开始执行。
      • 动态地解决了RAW冲突,并导致指令可能乱序开始执行。
    • 执行
      • 取到操作数后,功能部件开始执行。当产生出结果后,就通知记分牌它已经完成执行。
      • 在浮点流水线中,这一段可能要占用多个时钟周期。
    • 写结果
      • 记分牌一旦知道执行部件完成了执行,就检测是否存在WAR冲突。如果不存在,或者原有的WAR冲突已消失,记分牌就通知功能部件把结果写入目的寄存器,并释放该指令使用的所有资源。

    检测到WAR冲突的情况以及解决

    • 如果检测到WAR冲突,就不允许该指令将结果写到目的寄存器。这发生在以下情况:
      • 前面的某条指令(按顺序流出)还没有读取操作数;而且:其中某个源操作数寄存器与本指令的目的寄存器相同。
      • 在这种情况下,记分牌必须等待,直到该冲突消失。

    记分牌的信息

    由三部分构成

    • 指令状态表:记录正在执行的各条指令已经进入到了哪一段。
    • 功能部件状态表:记录各个功能部件的状态。每个功能部件有一项,每一项由以下9个字段组成:
      • B u s y Busy Busy:忙标志,指出功能部件是否忙。初值为“no”;
      • O p Op Op:该功能部件正在执行或将要执行的操作;
      • F i F_{i} Fi:目的寄存器编号;
      • F j , F k F_{j},F_{k} FjFk:源寄存器编号;
      • Q j , Q k Q_{j},Q_{k} QjQk:指出向源寄存器 F j 、 F k F_{j}、F_{k} FjFk写数据的功能部件 ;
      • R i , R j R_{i},R_{j} RiRj:标志位,为“yes”表示 F j F_{j} Fj F k F_{k} Fk中的操作数就绪且还未被取走。否则就被置为“no”。
    • 结果寄存器状态表Result:每个寄存器在该表中有一项,用于指出哪个功能部件(编号)将把结果写入该寄存器
      • 如果当前正在运行的指令都不以它为目的寄存器,则其相应项置为“no”。
      • Result各项的初值为“no”(全0)。

    记分牌算法举例

    分析下列代码运行过程中记分牌保存的信息

    L.D	    	F6, 34(R2)
    L.D	    	F2, 45(R3)
    MULT.D      F0, F2, F4
    SUB.D	    F8, F6, F2
    DIV.D	    F10, F0, F6
    ADD.D	    F6, F8, F2
    

    情况一:第一条指令L.D执行完毕;第二条指令L.D执行完毕,但没有写入目的寄存器F2,记分牌状态表如下:

    MIPS记分牌中的信息1

    1. 在上图的指令状态表中:

      • 第一条L.D指令已经完全执行完,其结果已经写人了F6;
      • 第二条L.D指令也已经执行完,但是结果还没有写人目的寄存器F2;
      • 由于第二条L.D指令与MULT.DSUB.D指令之间存在关于寄存器F2的先写后读(RAW)相关,因此MULT.DSUB. D在流出段等待,不能进入流水线的读操作数段。
      • 同样,MULT.DDIV.D之间存在关于寄存器F0RAW相关,因此DIV.D也只能在流出段等待。
      • 指令ADD.D与指令SUB.D之间存在关于加法器的结构相关,因此后面的ADD.D连流出都不能做,必须等到前面SUB.D指令全部执行完毕、释放加法器后才能够流出。
    2. 在上图的**功能部件状态表**中:

      • 整数(Integer)部件

        • Busy字段为yes,表示部件正忙
        • 其Op表示它在执行L.D指令
        • 目的寄存器字段 F i F_{i} Fi中记录的是F2。相应地,在结果寄存器状态表的F2字段中记录的是Integer部件。
        • 对于存储器访问类指令来说,第一源操作数寄存器字段 F j F_{j} Fj中记录的是访存地址寄存器。在本例中就是R3。它的 R j R_{j} Rj字段为no,表示R3的数据已经被读取过了。
      • 在乘法1(Mult1)部件

        • Busy字段是yes,表示正忙
        • Op字段记录的是MULT.D指令
        • 其目的寄存器字段 F i F_{i} Fi的内容为F0。相应地,在结果寄存器状态表的F0字段中记录的是Mult1,表示F0将存放Mult1部件的运算结果。
        • 在第一源操作数寄存器字段 F j F_{j} Fj中记录的是F2,它的 Q j Q_{j} Qj字段为Integer,表示F2的数据将来自Integer部件的操作结果,它的 R j R_{j} Rj字段为no,表示F2的数据还没有就绪,这个过程可以用来判断并解决数据的写后读(RAW)相关
        • 第二源操作数寄存器字段 F k F_{k} Fk中记录的是F4, Q k Q_{k} Qk字段为空,表示F4不依赖于当前工作的任何部件, R k R_{k} Rk字段为yes,表示F4的数0据已经就绪。
      • 乘法2(Mult2)部件

        • Busy字段是no,表示该功能部件当前空闲。
      • 其余部件的分析类似

    3. 在上图的结果寄存器状态表中:

      • 表中的字段与每个寄存器一一对应,它记录了当前机器状态下将把结果写人该寄存器的功能部件的名称
      • 当前写F0的为Mult1部件,写F2的为Integer部件,写F8的为Add部件,写F10的为Divide部件。
      • 字段为空表示空闲,即对应的寄存器没有被任何当前正在工作的功能部件作为目的寄存器使用。

    为更进一步分析,假设复电流水线各部件的延迟如下:

    加法需2个时钟周期
    乘法需10个时钟周期
    除法需40个时钟周期

    情况二:给出MULT.DDIV.D准备写结果之前的记分牌状态。

    • 程序执行到MULT.D将要写结果时记分牌的状态

    MIPS记分牌中的信息2

    从上图中可以知道,在MULT. D准备写结果之前,由于DIV.D指令与MULT.D
    令之间存在关于寄存器F0的RAW相关,因此在MULT. D指令完成写结果之前,DIV.D
    指令被阻塞在流出段而无法进人读操作数段。

    同时由于ADD.D指令与DIV.D指令之间存在关于寄存器F6的WAR相关,因此在DIV.D指令从F6中读出操作数之前,ADD. D指令被阻塞在执行段,无法进入写结果段。

    • 程序段执行到DIV.D将要写结果时记分牌的状态

      MIPS记分牌中的信息3

    在上图中

    • 由于DIV.D指令执行需要40个时钟周期,其后的ADD.D指令只需要两个时钟周期
    • DIV.D准备写结果之前,这条指令前面的指令已经全部执行完毕
    • 而且DIV.DADD. D之间存在的WAR相关DIV.D读走源操作数后就已经消失了
    • 因此ADD.D有足够的时间完成所有操作,所以就只剩下DIV.D指令没有完成写结果操作。

    记分牌算法伪代码

    为了表述算法的方便,约定:

    • FU:表示当前指令所要用的功能部件;
    • D:目的寄存器的名称;
    • S1、S2:源操作数寄存器的名称;
    • Op:要进行的操作;
    • F j [ F U ] F_{j}[FU] Fj[FU]:功能部件FU F j F_{j} Fj字段(其他字段依此类推);
    • Result[D]:结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结果写入寄存器D的功能部件的名称。
    1. 指令流出

      //进入条件:
      not Busy[FU] & not Result[D]; // 功能部件空闲且没有写后写(WAW)冲突。
      
      //计分牌内容修改:
      Busy[FU] ← yes; // 把当前指令的相关信息填入功能部件状态表。
      Op[FU] ← Op;    // 记录操作码。
      Fi[FU] ← D;     // 记录目的寄存器编号。
      Fj[FU] ← S1;    // 记录第一个源寄存器编号。
      Fk[FU] ← S2;    // 记录第二个源寄存器编号。
      
      Qj[FU] ← Result[S1];	// 记录将产生第一个源操作数的部件。
      Qk[FU] ← Result[S2];	// 记录将产生第二个源操作数的部件。
      
      //如果Qj[FU]为“no”,就表示没有操作部件要写S1,数据可用。
      //置Rj[FU]为“yes”。否则置Rj[FU]为“no”。
      Rj[FU] ← not Qj[FU];	// 置第一个源操作数是否可用的标志。
      Rk[FU] ← not Qk[FU];	// 置第二个源操作数是否可用的标志。
      Result[D] ← FU;			// D是当前指令的目的寄存器。功能部件FU将把结果写入D。
      
    2. 指令流出

      //进入条件:
      Rj[FU] & Rk[FU];	// 两个源操作数都已就绪。
      
      //计分牌内容修改:
      Rj[FU] ← no;	// 已经读走了就绪的第一个源操作数。
      Rk[FU] ← no;	// 已经读走了就绪的第二个源操作数。
      Qj[FU]0;		// 不再等待其他FU的计算结果。
      Qk[FU]0; 
      
    3. 执行

      //结束条件
      //功能部件操作结束。
      
    4. 写结果

      //进入条件:不存在WAR冲突。f((Fj[f] ≠ Fi[FU] or Rj[f] = no)
      &  (Fk[f] ≠ Fi[FU] or Rk[f]=no))
      //计分牌内容修改:
      // 如果有指令在等待该结果(作为第一源操作数),则将其Rj置为“yes”,表示数据可用。f(if Qj[f] = FU then Rj[f] ← yes);
      // 如果有指令在等待该结果(作为第二源操作数),则将其Rk置为“yes”,表示数据可用。f(if Qk[f]=FU then Rk[f]←yes);	
      
      Result(Fi[FU])0;	// 释放目的寄存器Fi[FU]。
      Busy[FU] = no;		// 释放功能部件FU。
      

    记分牌的性能限制(四个方面)

    • 程序代码中可开发的并行性,即是否存在可以并行执行的不相关的指令。

    • 记分牌的容量

      • 记分牌的容量决定了流水线能在多大范围内寻找不相关指令。
      • 流水线中可以同时容纳的指令数量称为指令窗口
    • 功能部件的数目和种类

      • 功能部件的总数决定了结构冲突的严重程度。
    • 反相关和输出相关

      • 它们引起计分牌中WAR和WAW冲突 。
    • 问题(2)和(3)可通过增加记分牌的容量和功能部件的数量来解决,但这会导致处理器成本增加,并可能影响系统时钟周期时间。

    • 在采用动态调度的处理器中,WAW和WAR冲突会增多,因为乱序流出的指令在流水线中会引起更多的名相关。

    • 如果在动态调度中采用分支预测技术,就会出现循环的多个迭代同时执行,名相关将更加严重。

    5.3.3 Tomasulo算法

    IBM 360/91首先采用了Tomasulo算法。

    核心思想

    • 记录和检测指令相关,操作数一旦就绪就立即执行,把发生RAW冲突的可能性减少到最小(引入延迟);
    • 通过寄存器换名来消除WAR冲突WAW冲突

    IBM 360/91 采用Tomasulo算法的原因

    • IBM 360/91的设计目标是基于整个360系列的统一指令系统和编译器来实现高性能,而不是设计和利用专用的编译器来提高性能。与此同时, 需要更多地依赖于硬件。

    • IBM 360体系结构只有4个双精度浮点寄存器,限制了编译器调度的有效性

    • 360/91的访存时间和浮点计算时间都很长。

    基于Tomasulo算法的MIPS处理器浮点部件的基本结构

    基于Tomasulo算法的MIPS处理器浮点部件的基本结构

    其中各个功能部件介绍如下:

    1.保留站(reservation station)

    • 每个保留站中保存一条已经流出并等待到本功能部件执行的指令(相关信息)。

    • 存储内容包括:操作码、操作数以及用于检测和解决冲突的信息。

    • 对源操作数的处理

      • 在一条指令流出到保留站的时候,如果该指令源操作数已经在寄存器中就绪,则将之取到该保留站中。
      • 如果操作数还没有计算出来,则在该保留站中记录将产生这个操作数的保留站的标识
    • 每个保留站都有一个标识字段,唯一地标识了该保留站。

    • 保留站的类型

      • 浮点加法器有3个保留站:ADD1,ADD2,ADD3
      • 浮点乘法器有两个保留站:MULT1,MULT2

    2.公共数据总线CDB

    • 是该结构中的一条重要的数据通路
    • 所有功能部件的计算结果都是送到CDB上,由它把这些结果直接送到(播送到)各个需要该结果的地方。
    • 在具有多个执行部件且采用多流出(即每个时钟周期流出多条指令)的流水线中,需要采用多条CDB

    3.load缓冲器和store缓冲器

    • 存放读/写存储器的数据或地址

    • load缓冲器的作用有3个:

      • 存放用于计算有效地址的分量
      • 记录正在进行的load访存,等待存储器的响应;
      • 保存已经完成了的load的结果(即从存储器取来的数据),等待CDB传输。
    • store缓冲器的作用有3个:

      • 存放用于计算有效地址的分量
      • 保存正在进行的store访存的目标地址,该store正在等待存储数据的到达;
      • 保存该store的地址和数据,直到存储部件接收。

    4.浮点寄存器FP

    • 共有16个浮点寄存器:F0,F2,F4,…,F30。
    • 它们通过一对总线连接到功能部件,并通过CDB连接到store缓冲器。

    5.指令队列

    • 指令部件送来的指令放入指令队列
    • 指令队列中的指令按先进先出的顺序流出

    6.运算部件

    • 浮点加法器完成加法和减法操作
    • 浮点乘法器完成乘法和除法操作

    Tomasulo算法的寄存器换名

    实现:

    • 寄存器换名是通过保留站和流出逻辑来共同完成的。

    • 当指令流出时,如果其操作数还没有计算出来,则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识

    结论:

    • 指令流出到保留站后,其操作数寄存器号或者换成了数据本身(如果该数据已经就绪),或者换成了保留站的标识,不再与寄存器有关系

    Tomasulo算法的两个特点

    由于Tomasulo算法采用分布的保留站,因此具有以下特点:

    • 冲突检测和指令执行控制是分开的
      • 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。
    • 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件,而不用经过寄存器。

    Tomasulo算法指令执行的步骤

    使用Tomasulo算法的流水线需3段(均在EX段):

    1.流出:从指令队列的头部取一条指令。

    • 如果该指令的操作所要求的保留站有空闲的,就把该指令送到该保留站(设为r)。

    • 如果其操作数在寄存器中已经就绪,就将这些操作数送入保留站r

    • 如果其操作数还没有就绪,就把将产生该操作数的保留站的标识送入保留站r

    • 一旦被记录的保留站完成计算,它将直接把数据送给保留站r。

    消除WAR以及WAW冲突

    • 在这一阶段,通过对寄存器换名(换成保留站的标识)和对操作数进行缓冲(就绪的操作数直接存入保留站),消除了WAR冲突

    • 此外,这一阶段还完成了对目的寄存器的预约工作,将其设置为接收保留站r的结果,这实际上相当于完成了写操作(预约)。由于指令是按照顺序流出的,当出现多条指令写同一个结果寄存器时,最后留下的结果一定是最后一条指令的,即消除了WAW冲突

    如果没有空闲的保留站,指令就不能流出。

    • 发生了结构冲突

    2.执行

    • 当两个操作数都就绪后,本保留站就用相应的功能部件开始执行指令规定的操作。
    • load和store指令的执行需要两个步骤:
      • 计算有效地址(要等到基地址寄存器就绪)
      • 把有效地址放入load或store缓冲器

    消除RAW冲突

    • 此处要等到所有操作数都准备就绪才开始执行指令,即通过推迟执行的方式解决RAW冲突

    3.写结果

    • 功能部件计算完毕后,就将计算结果放到CDB上,所有等待该计算结果的寄存器和保留站(包括store缓冲器)都同时从CDB上获得所需要的数据。

    保留站的7个字段

    • O p Op Op:要对源操作数进行的操作

    • Q j , Q k Q_{j},Q_{k} QjQk:将产生源操作数的保留站号

      • 等于0表示操作数已经就绪且在 V j V_{j} Vj V k V_{k} Vk中,或者不需要操作数。
    • V j , V k V_{j},V_{k} VjVk:源操作数的值

      • 对于每一个操作数来说, V V V Q Q Q字段只有一个有效。
      • 对于load来说, V k V_{k} Vk字段用于保存偏移量。
    • B u s y Busy Busy:为“yes”表示本保留站或缓冲单元“忙”

    • A A A:仅loadstore缓冲器有该字段。开始是存放指令中的立即数字段,地址计算后存放有效地址。

    • Q j Q_{j} Qj:寄存器状态表

      • 每个寄存器在该表中有对应的一项,用于存放将把结果写入该寄存器的保留站的站号。
      • 为0表示当前没有正在执行的指令要写入该寄存器,也即该寄存器中的内容就绪。

    Tomasulo算法举例

    对下列指令序列给出当第一条指令完成并写入结果时,Tomasulo算法所用的各信息表中的内容

    L.D	F6,34(R2)
    L.D	F2,45(R3)
    MUL.D	F0,F2,F4
    SUB.D	F8,F2,F6
    DIV.D	F10,F0,F6
    ADD.D	F6,F8,F2 
    

    Tomasulo示例

    • 图中所有的指令均已流出,但只有第一条load指令执行完毕并将结果写到CDB上。

    • 第二条load指令已经完成有效地址计算,正在等待存储器的响应。

    • 用Regs[]表示寄存器组,用Mem[]表示存储器。

    • 这里,刚刚流出的ADD.D指令与前一条指令DIV.D有一个WAR冲突,但它可以先于DIV. D完成而不会导致错误。

    Tomasulo算法伪代码

    各符号的意义

    • r:分配给当前指令的保留站或者缓冲器单元编号;

    • rd:目标寄存器编号;

    • rs、rt:操作数寄存器编号;

    • imm:符号扩展后的立即数;

    • RS:保留站;

    • result:浮点部件或load缓冲器返回的结果;

    • Qi:寄存器状态表;

    • Regs[ ]:寄存器组;

    • 与rs对应的保留站字段:VjQj

    • 与rt对应的保留站字段:VkQk

    • Qi、Qj、Qk的内容或者为0,或者是一个大于0的整数。

      • Qi为0表示相应寄存器中的数据就绪。
      • Qj、Qk为0表示保留站或缓冲器单元中的VjVk字段中的数据就绪。
      • 当它们为正整数时,表示相应的寄存器、保留站或缓冲器单元正在等待结果。

    1. 指令流出

    • 浮点运算指令
    // 进入条件:有空闲保留站(设为r)
    // 操作和状态表内容修改:
    if (Qi[rs]0// 检测第一操作数是否就绪
    {
        //第一操作数没有就绪,进行寄存器换名,即把将产生该操作数的保留站的编号放入当前保留站的Qj。
        //该编号是一个大于0的整数。
        RS[r].Qj ← Qi[rs]; 
    }
    else
    {
        RS[r].Vj ← Regs[rs]; //第一操作数就绪。把寄存器rs中的操作数取到当前保留站的Vj。 
        RS[r].Qj ← 0		//置Qj为0,表示当前保留站的Vj中的操作数就绪 。
    }
    
    if (Qi[rt]0// 检测第二操作数是否就绪
    {
        //第二操作数没有就绪,进行寄存器换名,即把将产生该操作数的保留站的编号放入当前保留站的Qk。
        //该编号是一个大于0的整数。
        RS[r].Qk ← Qi[rt]; 
    }
    else
    {
        RS[r].Vk ← Regs[rt]; //第二操作数就绪。把寄存器rt中的操作数取到当前保留站的Vk。 
        RS[r].Qj ← 0;		//置Qk为0,表示当前保留站的Vk中的操作数就绪 。
    }
    
    RS[r].Busy ← yes;	//置当前保留站为“忙”
    RS[r].Op ← Op;  	//设置操作码
    Qi[rd] ← r;	// 把当前保留站的编号r放入rd所对应的寄存器状态表项,以便rd将来接收结果。 
    
    
    • load和store指令
    // 进入条件:缓冲器有空闲单元(设为r) 
    // 操作和状态表内容修改:
    if (Qi[rs]0// 检测第一操作数是否就绪
    {
        //第一操作数没有就绪,进行寄存器换名,即把将产生该操作数的保留站的编号存入当前缓冲器单元Qj。
        //该编号是一个大于0的整数。
        RS[r].Qj ← Qi[rs]; 
    }
    else
    {
        RS[r].Vj ← Regs[rs]; //第一操作数就绪。把寄存器rs中的操作数取到当前缓冲器单元的Vj。 
        RS[r].Qj ← 0		//置Qj为0,表示当前缓冲器单元的Vj中的操作数就绪 。
    }
    RS[r].Busy ← yes;	// 置当前缓冲器单元为“忙”
    RS[r].A ← Imm;		// 把符号位扩展后的偏移量放入当前缓冲器单元的A                               
    

    对于load指令

    // 把当前缓冲器单元的编号r放入load指令的目标寄存器rt所对应的寄存器状态表项,以便rt将来接收所取的数据。
    Qi[rt] ← r;	
    

    对于store指令

    if (Qi[rt]0)	// 检测要存储的数据是否就绪
    {
    	// 该数据尚未就绪,进行寄存器换名,即把将产生该数据的保留站的编号放入当前缓冲器单元的Qk。
    	RS[r].Qk ← Qi[rt];
    }else
    {
        RS[r].Vk ← Regs[rt]// 该数据就绪,把它从寄存器rt取到store缓冲器单元的Vk
        RS[r].Qk ← 0;			 // 置Qk为0,表示当前缓冲器单元的Vk中的数据就绪。
    }
    

    2.执行

    • 浮点操作指令
    // 进入条件:(RS[r].Qj = 0)且(RS[r].Qk = 0) // 两个源操作数就绪
    // 操作和状态表内容修改:进行计算,产生结果 。
    
    • load/store指令
    // 进入条件:(RS[r].Qj = 0)且r成为load/store缓冲队列的头部
    // 操作和状态表内容修改:  
    RS[r].A ← RS[r].Vj + RS[r].A;	//计算有效地址
    //对于load指令,在完成有效地址计算后,还要进行:
    从Mem[RS[r].A]读取数据;    //从存储器中读取数据
    

    3.写结果

    • 浮点运算指令和load指令
    // 进入条件:保留站r执行结束,且CDB就绪。
    // 操作和状态表内容修改:
    ∀x (if(Qi[x] = r)	// 对于任何一个正在等该结果的浮点寄存器x
    {
    	Regs[x] ← result;	// 向该寄存器写入结果
        Qi[x]0;	     	// 把该寄存器的状态置为数据就绪
    }      
            
    ∀x (if(RS[x].Qj = r)	// 对于任何一个正在等该结果第作为第一操作数的保留站x
    {
    	RS[x].Vj ← result;	// 向该保留站的Vj写入结果
        RS[x].Qj ← 0;	// 置Qj为0,表示该保留站的Vj中的操作数就绪
    }
    
    ∀x (if(RS[x].Qk = r)  	// 对于任何一个正在等该结果作为第二操作数的保留站x
    {
    	RS[x].Vk ← result;	// 向该保留站的Vk写入结果
        RS[x].Qk ← 0;		// 置Qk为0,表示该保留站的Vk中的操作数就绪。  
    }
    RS[r].Busy ← no;        // 释放当前保留站,将之置为空闲状态。
    
    • store指令
    // 进入条件:保留站r执行结束,且RS[r].Qk = 0	// 要存储的数据已经就绪     	
    // 操作和状态表内容修改: 
    Mem[RS[r].A] ← RS[r].Vk		// 数据写入存储器,地址由store缓冲器单元的A字段给出。
    RS[r].Busy ← no;    		// 释放当前缓冲器单元,将之置为空闲状态。
    

    Tomasulo算法两个主要的优点

    • 冲突检测逻辑是分布的
      • 通过保留站和CDB实现
      • 如果有多条指令已经获得了一个操作数,并同时在等待同一运算结果,那么这个结果一产生,就可以通过CDB同时播送给所有这些指令,使它们可以同时执行。
    • 消除了WAW冲突和WAR冲突导致的停顿
      • 使用保留站进行寄存器换名,并且在操作数一旦就绪就将之放入保留站。

    说明

    • 当浮点运算指令流出到一个保留站r时,把该指令的目的寄存器rd的状态表项设置为r,方便将来接收运算结果。
    • load和store指令的处理与浮点运算指令不同。只要load缓冲器有空闲单元,就可以流出。STORE指令在写结果段执行。
    • 指令执行的限制,流水线中还有分支指令没有执行,当前指令就不能进入执行段。
    展开全文
  • 体系结构复习-Part 2-Cache + 指令级并行体系结构复习-Part 2-Cache + 指令级并行1. Cache与存储1.1 CPU & Memory Gap1.2 Cache结构1.2.1 局部性(Locality)1.2.2 Cache需要解决的4个关键问题1.2.3 Cache缺失...
  • 文章目录第6章 指令级并行的开发——软件方法6.1 基本指令调度及循环展开6.1.1 指令调度的基本方法6.1.2 循环展开 第6章 指令级并行的开发——软件方法 6.1 基本指令调度及循环展开 6.1.1 指令调度的基本方法 指令...
  • 向量处理机向量流水处理机 时间重叠向量特点向量流水处理横向处理纵向处理分组纵向处理4种向量指令V冲突功能冲突解决阵列处理机 资源重复 SIMD(单指令流多数据流)阵列处理机的原理分布式存贮器并行处理机集中式共享...
  • 高等计算机系统结构指令级并行处理高等计算机系统结构指令级并行处理(第二讲)程 旭2013年3月25日北京大学微处理器研究开发中心 北京大学计算机系统结构研究所复习: 三种数据冒险对于执行如下类型的指令序列:r ...
  • Oracle数据库并行处理技术是数据库的一项核心技术,它使组织能够高效地管理和访问TB数据。如果不能提供高效的Oracle数据库并行处理技术,这些大型数据库(通常用于数据仓库但也越来越多地出现在业务系统中)将不会...
  • 而且源端和目标端的表结构不一致,这样传统的EXP/EXPDP无法满足数据初始化,于是我使用了外部表来初始化数据,在默认模式下,经过测试,外部表每秒可以卸载1G的数据,本文主要对比并行模式下,外部表的卸载效率。...
  • 混合并行:即backbone使用数据并行,分类层使用模型并行; 该方法具备两个优点: 1)缓解了 W 的存储压力。将W划分为k个子矩阵w; 2)将 W 梯度的通信转换成了所有GPU的特征 X 与 softmax 局部分
  • oracle hint 和 并行

    2021-05-08 18:44:45
    需注意操作后会导致对象的默认并行度变化 并行DML ALTER SESSION FORCE PARALLEL DML|ALTER SESSION ENABLE PARALLEL DML+HINT 仅修改并行度和加并行HINT时 不能并行DML 只有其中的SELECT能并行并行 并行数据加载...
  • 集群是一组独立的计算机(结点)的集合体,结点间通过高性能网络相连接,各结点除了作为一个单一的计算资源供用户使用外,还可以协同工作,并表示为一个单一的、集中的计算资源,供并行计算任务使用。集群是一种造价...
  • Oracle数据库并行处理技术是数据库的一项核心技术,它使组织能够高效地管理和访问TB数据。如果不能提供高效的Oracle数据库并行处理技术,这些大型数据库(通常用于数据仓库但也越来越多地出现在业务系统中)将不会...
  • end //将对称系数的输入数据相加,同时将对应的滤波器系数送入乘法器 //为了进一步提高运行速度,另外增加了一寄存器 reg signed [12:0] Add_Reg[7:0]; always @(posedge clk or posedge rst) if ...
  • 数据、管道和基于张量切片的并行性来个大杂烩。 提示:以下是本篇文章正文内容,下面案例可供参考 一、pandas是什么? 示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。 二、使用...
  • oracle数据库并行处理技术是数据库的一项核心技术,它使组织能够高效地管理和访问tb数据。如果不能提供高效的oracle数据库并行处理技术,这些大型数据库(通常用于数据仓库但也越来越多地出现在业务系统中)将不会...
  • MindSpore 自动并行提供了 5 维的并行方式:数据并行、算子模型并行、Pipeline 模型并行、优化器模型并行和重计算,并且在图编译阶段,有机融合了 5 个维度的并行。这 5 维并行方式组合起来构成了盘古的并行策略。...
  • 目录 ​​​​​​扩展阅读关于并行度 ...一个Operator由多个并行的Task(线程)来执行, 一个Operator的并行Task(线程)数目就被称为该Operator(任务)的并行度(Parallel) 详细讲解 并行度可以有如下几种指定方式...
  • 呜~ 就隔了一段时间没看并行计算,发现作业贼难顶,不得不写篇博客来记录一下复习(预习)的内容。 并行计算性能评测 并行机的一些基本性能指标 对并行计算机的性能关注点还是落在了CPU和存储器上,毕竟CPU和存储器...
  • Parallel Programing caiyi 2021/6/17 第一章 1.为什么要构建并行系统? 电路晶体管密度过大会使...基本思想是把任务分配给各个核,主要有两种方法:任务并行数据并行。 任务并行指的是把各个的任务分配给不同的核
  • 关于并行计算的相关总结1. 定义2. 特征及层次3. 应用举例3.1 基于CUDA 的K-Means 多级并行优化方法3.2 面向GPU的直方图统计图像增强并行算法3.3 基于FPGA的多核可扩展卷积加速器设计 1. 定义 并行计算或称平行计算是...
  • 线程级并行 - 多个线程并发执行(例如pthreads) 指令级并行 - 多个指令可以同时执行(例如,超标量处理器) 流水线并行 - 多个指令随时都在进行中,但执行指令的不同部分(例如任何具有流水线级的现代处理器)
  • MySQL8.0 InnoDB并行执行

    2021-01-19 21:15:27
    分区 并行扫描的一个核心步骤就是分区,将扫描的数据划分成多份,让多个线程并行扫描。InnoDB引擎是索引组织表,数据以B+tree的形式存储在磁盘上,节点的单位是页面(block/page),同时缓冲池中会对热点页面进行缓存...
  • JAVA并行程序基础

    2021-02-13 00:48:29
    JAVA并行程序基础一、有关线程你必须知道的事进程与线程在等待面向线程设计的计算机结构中,进程是线程的容器。我们都知道,程序是对于指令、数据及其组织形式的描述,而进程是程序的实体。线程是轻量的进程,是...
  • ES实现百亿级数据实时分析实战案例

    千次阅读 2021-01-13 00:00:00
    第三种方案,将数据按照实验+小时分索引后,可以将每个索引包含的数据量降到1000万以下,再借助ES在查询、聚合方面高效的能力,应该可以实现秒响应,并且用户体验也会非常好。 技术方案由此确定。 技术架构 1.用...
  • Oracle 锁和并行机制

    2021-05-06 01:44:37
    Sybase机制:数据更新会导致其他访问都挂起,没有并行可言,速度和正确不可兼得。Informix机制:实现行级封锁的同时,需要消耗大量的内存和时间,容易导致系统瘫痪。Oracle机制注意点:事务处理是数据库的全部工作,...
  • 在学习具体的CUDA编程之前,对一些文档中出现的概念性的词语不免有些疑惑,其中一个便是:Parallel Computing 并行计算。网上找了一些介绍的文章,发现美国Lawrence Livemore国家实验的官网上有一篇介绍并行计算的...
  • 高性能计算之并行编程技术MPI并行程序设计(完整版)高性能计算之并行编程技术—— MPI并行程序设计都志辉 编著李三立 审阅陈渝 刘鹏 校对I内容提要本书介绍目前最常见的并行程序— MPI并行程序的设计方法 它适合高校...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,061
精华内容 103,624
关键字:

数据级并行