精华内容
下载资源
问答
  • 2015-06-20 22:38:43

    体系结构复习 CH5 指令级并行


    5.1 指令级并行概念

    5.1.1 指令级并行

    指令级并行(ILP)指通过通过流水线等技术实现多条指令同时并行执行的并行技术

    实现ILP主要的方法有:

    • 依靠硬件动态发现和开发并行
    • 依靠软件在编译时静态发现并行

    5.1.2 指令间相关性

    指令间的相关性限制了指令级的并行度,相关性主要分为(真)数据相关、名称相关和控制相关

    (1)数据相关

    指令i位于指令j的前面,下面两种情况下称指令j数据相关于指令i:

    • 指令i生成的结果可能会被指令j用到
    • 指令j数据相关于指令k,而指令k数据相关于指令j

    数据相关在一定程度上限制了ILP,最常用客服相关性的方法是在不改变相关性的条件下通过指令调度消除数据冒险

    (2)名称相关

    当两条指令使用相同寄存器和存储器位置(称为名称),但与该名称相关的指令之间并没有数据流动,此时存在名称相关

    主要分为以下两种情况(指令i位于指令j的前面):

    • 反相关:指令j对指令i读取的寄存器和存储器位置进行写操作时,发生反相关
    • 输出相关:指令i和指令j对相同寄存器和存储器位置进行写操作时,发生输出相关

    名称相关并不是真正的数据相关,通过寄存器重命名技术来消除名称相关

    (3)数据冒险

    数据冒险是指指令间存在相关性并且这两条指令相聚非常接近,足以使执行期间的重叠改变相关操作数的访问顺序,数据冒险分成三类:

    • RAW写后读:j在i还没写入时就读取同一位置,会读取旧值
    • WAW写后写:j在i还没写入时就写入同一位置,会被i写入覆盖(存在于i指令执行时间较长,如浮点运算或乘法指令)
    • WAR读后写:j在i还没读入时就写入同一位置,i错误读取新值(一般先读后写的指令集不会出现,可能情况是j提前写而i在流水线后期才读的情况)

    (4)控制相关

    控制相关是指分支指令限定了指令i相对于其的执行顺序,和分支条件相关的指令必须先于分支指令执行,受控于分支指令的指令必须在分支指令后执行,不受控于分支指令的指令必须在分支指令前执行


    5.2 软件方法的指令级并行——基本块内的指令级并行

    基本块是指一段顺序执行的代码,除了入口处没有其他转入分支,除了出口处没有其他转出分支

    考虑一下C语言代码:

    for (i = 1; i <= 1000; i++) {
        x[i] = x[i] + s;
    }

    基本块对应的汇编程序为:

    Loop:   LD      F0,0(R1)
            ADDD    F4,F0,F2
            SD      0(R1),F4
            DADDI   R1,R1,#-8
            BNEZ    R1,Loop

    遵循以下指令延迟规定:

    这里写图片描述

    那么可以直接分析基本块汇编程序的指令周期延迟(共9个周期):

    1Loop:  LD      F0,0(R1)
    2       <stall>
    3       ADDD    F4,F0,F2
    4       <stall>
    5       <stall>
    6       SD      0(R1),F4
    7       DADDI   R1,R1,#-8
    8       <stall>
    9       BNEZ    R1,Loop

    5.2.1 静态调度

    静态调度是指通过改变指令顺序而不改变指令间数据相关来改善指令延迟,把上述R1的递减改到前面并利用延迟槽技术(设置延迟槽为1)可以让上述基本快代码压缩到6个周期完成:

    1Loop:  LD      F0,0(R1)
    2       DADDI   R1,R1,#-8
    3       ADDD    F4,F0,F2
    4       <stall>
    5       BNEZ    R1,Loop
    6       SD      8(R1),F4

    说明:

    • DADDI让R1递减提前,那么SD中存储位置是R1+8而不是R1
    • 延迟槽是无论分支是否成功都要执行的指令

    5.2.2 循环展开

    静态调度能够大幅提升基本快执行效率(50%),但是还有一个周期的停顿不能消除,那么由此引入另一种块内消除延迟方法——循环展开

    循环展开是将循环中多个基本块展开成一个基本块从而填充stall间隙的方法

    将上段基本块做4段展开,并做调度:

    1Loop:  LD      F0,0(R1)
    2       LD      F6,-8(R1)
    3       LD      F10,-16(R1)
    4       LD      F14,-24(R1)
    5       ADDD    F4,F0,F2
    6       ADDD    F8,F6,F2
    7       ADDD    F12,F10,F2
    8       ADDD    F16,F14,F2
    9       SD      0(R1),F4
    10      SD      -8(R1),F8
    11      DADDI   R1,R1,#-32
    12      SD      16(R1),F12
    13      BNEZ    R1,Loop
    14      SD      8(R1),F16

    平均每个次循环仅需要14/4=3.5个cycle,性能大幅增加!

    5.2.3 编译器角度来看代码调度

    上述最优循环展开代码调度是我们手工完成的,能够完成高效的调度是因为我们知道R1代表枚举变量,并知道R1-32前的-16(R1)和16(R1)指向的同一内存区域,但编译器确定对存储器引用却不是那么容易,如其无法确定:

    • 同一次循环中,100(R4)和20(R6)是否相等
    • 不同次循环中,100(R4)和100(R4)是否相等

    5.2.4 循环间相关

    上面举例不同次循环间是不相关的,但如果出现下述情况:

    for (i = 1; i <= 100; i++) {
        A[i] = A[i] + B[i];         //S1
        B[i+1] = C[i] + D[i];       //S2
    }

    S1和S2没有相关,但是S1依赖于前一次循环的B[i],这种循环常不能直接并行执行,需要修改代码:

    A[1] = A[1] + B[1]; 
    for (i = 1; i <= 99; i++) {
        B[i+1] = C[i] + D[i];           //S2
        A[i+1] = A[i+1] + B[i+1];       //S1
    }
    B[101] = C[100] + D[100];

    5.3 硬件方法的指令级并行

    之前所了解的静态调度技术存在困难,并且一旦出现无法消除的数据相关,那么流水线就会停顿,直到清除相关流水线才会继续流动

    动态调度提出动态发射的思想,若流水线即将发生停顿,硬件会动态选择后续不会违反相关性的指令发射,这也就是常说的顺序发射、乱序执行、乱序完成

    动态调度有许多优点:

    • 对一种流水线编译的代码可以在不同流水线上高效执行,而不需要针对不同微体系结构重新编译
    • 动态调度能克服编译器静态调度不能确定的相关性(上述难题)
    • 允许处理器容忍一些不确定/动态的延迟,如缓存缺失带来的延迟,静态调度是无论如何也不能做到这一点的

    5.3.1 记分牌动态调度

    记分牌算法把ID段分成两个步骤:

    • 发射:译码,并检测结构相关
    • 读操作数:等到没有数据相关时读入操作数

    其主要思想为,在没有结构冲突时尽可能的发射指令,若某条指令停顿则选取后续指令中与流水线正在执行和停顿的指令发射

    (1)记分牌四阶段

    阶段内容
    Issue发射如果当前指令所使用的功能部件空闲,并且没有其他活动的指令(执行和停顿)使用相同的目的寄存器(避免WAW),记分牌发射该指令到功能部件,并更新记分牌内部数据。如果有结构相关或WAW相关,则该指令的发射暂停,并且也不发射后继指令,直到相关解除。
    Read读操作数如果先前已发射的正在运行的指令不对当前指令的源操作数寄存器进行写操作,或者一个正在工作的功能部件已经完成了对该寄存器的写操作,则该操作数有效。操作数有效时记分牌控制功能部件读操作数,准备执行。(避免RAW)
    Execute执行接收到操作数后功能部件开始执行。当计算出结果后,它通知记分牌该条指令的执行结束,记分牌记录
    Write写结果一旦记分牌得到功能部件执行完毕的信息后,记分牌检测WAR相关。如果没有WAR相关就写结果,否则暂停该条指令。

    (2)记分牌硬件部件

    1.Instruction status记录正在活动的指令处于四阶段中的哪一步

    2.Function unit status记录功能部件(完成运算的单元)的状态,其中每个FU有9个记录参量:

    • Busy:该功能部件是否正在使用
    • Op:该功能部件当前完成的操作
    • Fi:目的寄存器编号
    • Fj,Fk:两个源寄存器编号
    • Qj,Qk:产生源操作数Fj,Fk的功能部件
    • Rj,Rk:标识Fj,Fk是否就绪的标志位

    3.Register result status记录哪个FU对某个寄存器是否进行写操作(还未写入),若没有该域为空

    (3)动态调度算法

    有了上述三个部件,就可以完成四阶段中一些查看操作,如FU是否空闲、操作数是否就绪(能否执行)、是否存在WAW等

    之所以该算法称为记分牌算法,是因为这三个部件就像公示的记分牌一样,流水线中各操作都需要去查看记分牌的状态并根据执行情况在记分牌中写入相应参数信息

    将四阶段和记分牌控制用伪代码的形式给出,wait util是某指令向下阶段流水的必要条件,Book keeping是该流水段执行完毕后需要记录的信息:

    StatusWait UntilBook Keeping
    Issue!FU.busy && result[D] == nullFU.busy = true; FU.op = op; FU.Fi = ‘D’; FU.Fj = ‘S1’; FU.Fk = ‘S2’; Qj = result[S1]; Qk = result[S2]; Rj = (Qj == null ? true : false); Rk = (Qk == null ? true : false); Result[D] == ‘FU’(若是源操作数是立即数或R整数寄存器,对应Rjk直接是yes)
    ReadRj && RkRj = true; Rk = true;
    ExecuteFU completerecord complete cycle
    Write任意其他FU的Fj和Fk不是FU.Fi(WAR)或者他们已经ready“通知”所有Fj和Fk是FU.Fi的其他FU该操作数ready,修改Rj/k为true; Result[FU.Fi] = null; FU.busy = false;

    5.3.2 Tomasulo动态调度

    另一种动态调度算法是Tomasulo动态调度算法,它和记分牌的区别主要有:

    • 控制和缓存在记分牌中是集中的,Tomasulo是分布在各部件中
    • Tomasulo的FU称做Reservation Station保留站(RS),RS中表示寄存器要么是寄存器值,要么是指向RS或Load Buffer(也可以看做特殊的RS)的指针;RS可以完成寄存器重命名,避免WAR、WAW,RS可以多于寄存器,实现更多编译器无法完成的优化
    • Register result status中记录的结果都是RS的名字,而不是寄存器
    • FU计算完毕后通过Common Data Bus(CDB)广播给所有其他RS,并修改Register result status中记录
    • Tomasulo可以跨越分支!不仅仅局限于基本快内部FP操作的乱序执行

    Tomasulo受限于CDB的性能,一般采用高速CDB

    (1)寄存器重命名

    为什么寄存器重命名能够避免WAR和WAW?事例如下:

    DIVD    F0,F2,F4
    ADDD    F6,F0,F8
    SD      F6,0(R1)
    SUBD    F8,F10,F14
    MULD    F6,F10,F8

    存在下列三个名称相关:

    • SUBD的目的操作数是F8,ADDD源操作数是F8,存在WAR冒险
    • MULD的目的操作数是F6,SD源的操作数是F6,存在WAR冒险
    • MULD的目的操作数是F6,ADDD目的操作数是F6,存在WAW冒险

    用T、S重命名寄存器,有:

    DIVD    F0,F2,F4
    ADDD    S,F0,F8
    SD      S,0(R1)
    SUBD    T,F10,F14
    MULD    F6,F10,T

    且后续F8都用T代替,那么有:

    • SUBD写入T可以先于ADDD读F8,WAR冒险消除
    • MULD写入F6可以在SD读入S之前,WAR冒险消除
    • MULD写入F6可以在ADDD写入S之前,WAW冒险消除

    (2)部件结构

    1.RS的结构和记分牌算法的FU相似,因为有了寄存器重命名,它省去了F和R两个标志位:

    • Busy:该RS是否正在使用
    • Op:该RS当前完成的操作
    • A:存放存储器地址,开始存立即数,计算出有效地址后存有效地址
    • Vj,Vk:源操作数的值
    • Qj,Qk:产生源操作数的RS

    2.Register result status中存对某一寄存器写操作的RS名字

    (3)三阶段

    阶段内容
    Issue发射如果对应RS空闲(无结构相关),则发射指令和操作数(RS重命名避免WAR和WAW)
    Execute执行两操作数就绪后RS开始执行,若没准备好随时监听CDB以获取所需的操作数(避免RAW)
    Write写结果CDB传送所有结果,并修改Register result status

    (4)Tomasulo流水控制

    Tomasulo动态调度算法的伪代码表示如下:

    1.发射阶段:

    // rs、rt为源操作数
    // rd为目的操作数
    
    void issue() {
        if op == FP operation {
            wait until: RS[r].busy == false; // r是和FP Operation对应的RS编号
    
            if RegisterStatus[rs].Qi != null {
                RS[r].Vj = null;
                RS[r].Qj = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vj = Register[rs];
                RS[r].Qj = null;
            }
    
            if RegisterStatus[rs].Qk != null {
                RS[r].Vk = null;
                RS[r].Qk = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vk = Register[rs];
                RS[r].Qk = null;
            }
    
            RS[r].busy == true;
            RegisterStatus[rd].Qi = r; 
        }
    
        if op == Load or Store {
            wait until: RS[r].busy == false; // Load Buffer和RS相同数据结构
    
            if RegisterStatus[rs].Qi != null {
                RS[r].Vj = null;
                RS[r].Qj = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vj = Register[rs];
                RS[r].Qj = null;
            }
    
            RS[r].A = imm;
            RS[r].busy = true;
    
            if op == Load { // Load only
                RegisterStatus[rt].Qi = r;
            } else {        // Store only
                if (RegisterStatus[rd].Qi != null) {// 避免WAW
                    RS[r].Vk = null;
                    RS[r].Qk = RegisterStatus[rt].Qi;
                } else {
                    RS[r].Vk = Register[rt];
                    RS[r].Qk = null;
                }
            }
        }
    }
    

    2.执行阶段:

    void execute() {
        if op == FP Operation {
            wait until: RS[r].Qj == null && RS[r].Qk == null
    
            compute result with Operand in Vj and Vk;
        }
    
        if op == Load or Store {
            wait until: RS[r].Qj = 0 && r is head of load-store queue(每次处理队头元素)
    
            RS[r].A = RS[r].Vj + RS[r].A;
    
            if op == Load {
                wait until: RS[r].A写入完成
    
                Read from Mem[RS[r].A]
            }
        }
    }

    3.写结果阶段:

    void write() {
        if op == FP Operation {
            wait until: Execution of r is complete & CDB available
    
            for all x in RegisterStatus_Index_Set par-do { 
                // 硬件并行执行,模拟直接for循环串行模拟即可
                if RegisterStatus[x].Qi == r {
                    Register[x] = result;
                    RegisterStatus[x].Qi = null;
                }
            }
    
            for all x in RS_Index_Set par-do {
                if RS[x].Qj == r {
                    RS[x].Vj = result;
                    RS[x].Qj = null;
                }
    
                if RS[x].Qk == r {
                    RS[x].Vk = result;
                    RS[x].Qk = null;
                }
            }
    
            RS[r].busy = false;
        }
    
        if op == Store {
            wait until: Execution of r is complete & RS[r].Qk == null
    
            Mem[RS[r].A] = RS[r].Vk;
            RS[r].busy = false;
        }
    }

    5.3.3 Tomasulo处理循环

    Tomasulo算法能够循环覆盖执行,关键点在于:

    • 寄存器重命名:不同循环中处理不同的物理存储位置,寄存器重命名将寄存器表示为动态的指针,增加了寄存器的个数
    • 整数部件先行:以便能够发射多个循环中操作
    更多相关内容
  • 计算机体系结构-第五章-指令级并行

    千次阅读 2018-09-27 23:18:33
    5.1 指令级并行概念 5.1.1 指令级并行 指令级并行(ILP)指通过通过流水线等技术实现多条指令同时并行执行的并行技术 实现ILP主要的方法有: 依靠硬件动态发现和开发并行 依靠软件在编译时静态发现并行 5.1.2 ...

    ILP instruction-level parallelism

    5.1 指令级并行概念

    5.1.1 指令级并行

    指令级并行(ILP)指通过通过流水线等技术实现多条指令同时并行执行的并行技术

    实现ILP主要的方法有:

    • 依靠硬件动态发现和开发并行
    • 依靠软件在编译时静态发现并行

    5.1.2 指令间相关性

    指令间的相关性限制了指令级的并行度,相关性主要分为(真)数据相关、名称相关和控制相关

    (1)数据相关

    指令i位于指令j的前面,下面两种情况下称指令j数据相关于指令i:

    • 指令i生成的结果可能会被指令j用到
    • 指令j数据相关于指令k,而指令k数据相关于指令j

    数据相关在一定程度上限制了ILP,最常用客服相关性的方法是在不改变相关性的条件下通过指令调度消除数据冒险

    (2)名称相关

    当两条指令使用相同寄存器和存储器位置(称为名称),但与该名称相关的指令之间并没有数据流动,此时存在名称相关

    主要分为以下两种情况(指令i位于指令j的前面):

    • 反相关:指令j对指令i读取的寄存器和存储器位置进行写操作时,发生反相关(由此可能引发RAW冲突)
    • 输出相关:指令i和指令j对相同寄存器和存储器位置进行写操作时,发生输出相关(由此可能引发WAW冲突)

    名称相关并不是真正的数据相关,通过寄存器重命名技术来消除名称相关

    (3)数据冒险

    数据冒险是指指令间存在相关性并且这两条指令相聚非常接近,足以使执行期间的重叠改变相关操作数的访问顺序,数据冒险分成三类:

    • RAW写后读:j在i还没写入时就读取同一位置,会读取旧值
    • WAW写后写:j在i还没写入时就写入同一位置,会被i写入覆盖(存在于i指令执行时间较长,如浮点运算或乘法指令)
    • WAR读后写:j在i还没读入时就写入同一位置,i错误读取新值(一般先读后写的指令集不会出现,可能情况是j提前写而i在流水线后期才读的情况)

    (4)控制相关

    控制相关是指分支指令限定了指令i相对于其的执行顺序,和分支条件相关的指令必须先于分支指令执行,受控于分支指令的指令必须在分支指令后执行,不受控于分支指令的指令必须在分支指令前执行

    相关冲突的区别和联系:

    相关包括数据相关,名称相关控制相关

    冲突包括结构冲突,数据冲突,控制冲突

    其中: 

    结构冲突是由硬件资源冲突造成的

    数据冲突是由数据相关名称相关造成的

    控制冲突是由控制相关造成的

     

    相关是程序的固有属性,它反映了程序汇中指令之间的相互依赖关系

    冲突是流水线的属性,存在相关不一定会引起冲突

     

    因此,开发指令级并行可以从两方面考虑:

    1. 保持相关但避免冲突的发生(如指令调度)
    2. 进行代码变换直接消除相关性

     


    5.2 软件方法的指令级并行——基本块内的指令级并行

    基本块是指一段顺序执行的代码,除了入口处没有其他转入分支,除了出口处没有其他转出分支

    考虑一下C语言代码:

    for (i = 1; i <= 1000; i++) {
        x[i] = x[i] + s;
    }

    基本块对应的汇编程序为: 

    #简化起见,假设最低地址是8
    Loop:   LD      F0,0(R1) # R1处给F0赋值  <-
            ADDD    F4,F0,F2 # F0+F2->F4
            SD      0(R1),F4 #存储结果到F4   ->
            DADDI   R1,R1,#-8 R1作为地址下标
            BNEZ    R1,Loop # R1 != 0 
    

    遵循以下指令延迟规定:

    这里写图片描述

    那么可以直接分析基本块汇编程序的指令周期延迟(共9个周期):

    1Loop:  LD      F0,0(R1)
    2       <stall>
    3       ADDD    F4,F0,F2
    4       <stall>          #由上表可知加操作需要两个停顿周期
    5       <stall>
    6       SD      0(R1),F4
    7       DADDI   R1,R1,#-8
    8       <stall>
    9       BNEZ    R1,Loop

    5.2.1 静态调度

    静态调度是指通过改变指令顺序而不改变指令间数据相关来改善指令延迟,把上述R1的递减改到前面并利用延迟槽技术(设置延迟槽为1)可以让上述基本快代码压缩到6个周期完成:

    1Loop:  LD      F0,0(R1)
    2       DADDI   R1,R1,#-8
    3       ADDD    F4,F0,F2
    4       <stall>
    5       BNEZ    R1,Loop
    6       SD      8(R1),F4

    说明:

    • DADDI让R1递减提前,那么SD中存储位置是R1+8而不是R1
    • 延迟槽是无论分支是否成功都要执行的指令

    5.2.2 循环展开

    静态调度能够大幅提升基本快执行效率(50%),但是还有一个周期的停顿不能消除,那么由此引入另一种块内消除延迟方法——循环展开

    循环展开是将循环中多个基本块展开成一个基本块从而填充stall间隙的方法

    将上段基本块做4段展开,并做调度:

    1Loop:  LD      F0,0(R1)
    2       LD      F6,-8(R1)
    3       LD      F10,-16(R1)
    4       LD      F14,-24(R1)
    5       ADDD    F4,F0,F2
    6       ADDD    F8,F6,F2
    7       ADDD    F12,F10,F2
    8       ADDD    F16,F14,F2
    9       SD      0(R1),F4
    10      SD      -8(R1),F8
    11      DADDI   R1,R1,#-32
    12      SD      16(R1),F12
    13      BNEZ    R1,Loop
    14      SD      8(R1),F16

    平均每个次循环仅需要14/4=3.5个cycle,性能大幅增加!

    5.2.3 编译器角度来看代码调度

    上述最优循环展开代码调度是我们手工完成的,能够完成高效的调度是因为我们知道R1代表枚举变量,并知道R1-32前的-16(R1)和16(R1)指向的同一内存区域,但编译器确定对存储器引用却不是那么容易,如其无法确定:

    • 同一次循环中,100(R4)和20(R6)是否相等
    • 不同次循环中,100(R4)和100(R4)是否相等

    5.2.4 循环间相关

    上面举例不同次循环间是不相关的,但如果出现下述情况:

    for (i = 1; i <= 100; i++) {
        A[i] = A[i] + B[i];         //S1
        B[i+1] = C[i] + D[i];       //S2
    }

    S1和S2没有相关,但是S1依赖于前一次循环的B[i],这种循环常不能直接并行执行,需要修改代码:

    A[1] = A[1] + B[1]; 
    for (i = 1; i <= 99; i++) {
        B[i+1] = C[i] + D[i];           //S2
        A[i+1] = A[i+1] + B[i+1];       //S1
    }
    B[101] = C[100] + D[100];

    5.2.5 循环展开和调度小结

    由上例可知,通过循环展开,寄存器重命名,指令调度可以有效地开发出指令级并行,但是循环展开和指令调度需要注意以下几个问题:

    1. 正确性(展开后代码要正确,如循环控制和操作数偏移量的修改)
    2. 有效性(能否进行展开,不同循环体之间需要有无关性)
    3. 重命名(使用不同的寄存器避免名称冲突)
    4. 删除冗余指令(删除多于的测试指令和分支指令并对循环结束代码和新的循环体代码进行相应修正)
    5. 特别保证载入和存储指令的不相关(load和store在不同循环体中访问的地址不相同)

    循环展开的不足之处:

    1. code size 增大,这可能会造成cache缺失率增大
    2. reg pressure 增大,寄存器的数量可能不足导致寄存器紧缺,影响重命名

    5.3 硬件方法的指令级并行

    5.3.0动态分支预测

    分支预测(Branch Prediction)是现代处理器用来提高CPU执行速度的一种手段, 其对程序的分支流程进行预测, 然后预先读取其中一个分支的指令并解码来减少等待译码器的时间.维基百科上对此的解释是"a strategy in computer architecture design for mitigating the costs usually associated with conditional branches, particularly branches to short sections of code."

    分支预测的方法有 静态预测 和 动态预测 两类:静态预测方法行为比较简单,如预测永远不转移、预测永远转移(jmp)、预测后向转移等等,它并不根据执行时的条件和历史信息来进行预测,因此预测的准确性不会很高;动态预测方法则根据同一条转移指令过去的转移情况来预测未来的转移情况。

    由于程序中的条件分支是根据程序指令在流水线处理后的结果来执行的,所以当CPU等待指令结果时,流水线的前级电路也处于等待分支指令的空闲状态,这样必然出现时钟周期的浪费。如果CPU能在前条指令结果出来之前就预测到分支是否转移,那么就可以提前解码并执行相应的指令,这样就避免了流水线的空闲等待,也就相应提高了CPU的整体执行速度。但另一方面,一旦前条指令结果出来后证明分支预测是错误的, 也就是产生了错误的分支预测,那么就必须将已经装入流水线执行的指令和结果全部清除,然后再装入正确的指令重新处理,这样就比不进行分支预测而是等待结果再执行新指令有额外的周期消耗。

    因此,分支预测的错误并不会导致结果的错误,而只是导致流水线的停顿,如果能够保持较高的预测准确率,分支预测就能提高流水线的性能, 换言之, 如果在软件开发过程中, 能够考虑这一特性, 减少甚至移除条件分支(值得一提的是, 条件转移不需要预测, 因此条件转移也远没有产生错误分支的性能代价大), 就能一定程度上提供程序的整体效率.
     

    看体系结构,看了流水线,知道流水线流起来之后,就会产生hazard,然后就会对hazard进行分类,找出解决hazard的方法;然后大伙蜂拥而上,发现hazard中,对于branch hazard这部分带来的性能影响很大,根据量化书中写的,branch带来的性能影响是10%~30%,并且流水级数越长,性能影响越大,这个其实很好理解的。所以大伙就集中精力解决这个问题了。然后出现了各种方法了啊,根据书上写的,以及我的理解,对于分支指令的处理就两大类:静态的和动态的。

    所谓的静态分支处理方法,就是不依靠程序执行期间的信息进行处理,静态的方法一般也就如下了哦:
    1)出现branch,就冻结流水线——这是傻瓜也能想出的方法;
    2)认为branch一定会token;
    3)认为branch一定不会token;
    4)由于branch的执行,第一步是IF取指令,然后第二部是译码,即ID,在第二阶段ID才能判断出当前指令是否是branch指令,为此可以在ID阶段继续取一条指令,作为分支指令的delay slot,这条指令不管branch是否token,都会执行。

    所谓的动态分支处理方法,是指利用程序执行期间的信息,进行处理,所以这儿很明显带来的是硬件开销,因为程序执行期间是不可能由软件协助的,否则性能影响也就太大了吧。相对的,静态分支处理,其实是利用编译器实现的。

    现在一般的处理器中,对于动态分支预测算法,支持的基本功能是BTB和BHT两个基本逻辑。
    BTB——Branch Target Buffer——分支目标缓冲,记录分支的“目标”即跳转地址的缓冲
    BHT——Branch Histroy Table——分支历史表,记录分支指令是否token

    那么,我们应该在什么阶段进行分支预测呢?当然是越快越好!
    考虑教学用5级流水线结构,第一级是取指令,这个时候,我们是不知道这条指令是否是分支指令的;第二级是译码,这个时候才能知道某条指令是否是分支指令的。为此,针对分支预测,则最快也才能在第二级才能进行分支预测,而进行预测也需要一个时钟周期的,因此,也就说,在第三级才能得到分支的结论:是否需要跳转。假设分支预测都是准确的,这个时候最少也会在流水线中插入两级stall,而不是一级stall。

    为此带来的流水性能损失是不可接受的。大家也就继续想办法:能否再取指令的同时,进行部分译码呢?因为RISC的指令集都比较规整,分支指令的编码方式也比较规整,进行部分译码需要的逻辑不算多,不会过都影响流水线的时钟周期提升。

    这个时候可以把上面的BHT以及BTB用上了,不过BTB和BHT是分别用在两个地方的:

    BHT——Branch History Table,顾名思义,这是记录分支历史信息的表格,用于判定一条分支指令是否token;这儿记录的是跳转信息,简单点的,可以用1bit位记录,例如1表示跳转,0表示不跳转,而这个表格的索引是指令PC值;考虑在32位系统中,如果要记录完整32位的branch history,则需要4Gbit的存储器,这超出了系统提供的硬件支持能力;所以一般就用指令的后12位作为BHT表格的索引,这样用4Kbit的一个表格,就可以记录branch history了。当然,通过大伙的不懈努力和分析,发现在BHT中用1bit位记录分支是否跳转还不够准确,用2bit位记录就非常好了,而用3bit或者更多位记录,效果与2bit类似。所以在BHT中,一般就用2bit位记录分支是否跳转:例如11和10表示这条分支会跳转;01和00表示分支不会跳转。这个2bit计数器大伙叫做饱和计数器。

    BTB——用于记录一条分支指令的跳转地址,由于这儿存储的是指令地址,例如32位地址,因此,这个表格就不能做到存储BHT那样多的内容了,如果也支持4K条指令,则需要128Kbit的存储空间,这几乎可以赶上一个L1Cache的容量了,所以BTB一般很小,就32项或者64项。由于这个BTB容量小,并且其用于是记录分支指令的跳转地址,因此,如果这条指令不跳转,即其下一条指令就是PC+4,则不会在BTB中记录的。

    基于BTB和BHT的分支预测就很简单了:
    1)在取指阶段利用PC寻址BTB,如果命中,则说明这是一条跳转指令,利用从BTB中获取到的地址去取icache;
    2)由于BTB中保存的内容不够多,因此BHT的准确率更高,这个时候索引BHT表格,如果发现BHT也跳转,则说明这条指令预测是跳转的;如果BHT不跳转,则说明不跳转,这个时候就取消BTB中的指令地址,重新PC+4去取icache;

    --------------------- 

    常见的分支预测器: https://blog.csdn.net/edonlii/article/details/8754724

    https://www.zhihu.com/question/23973128

     

    5.3.1动态调度

    之前所了解的静态调度技术存在困难,并且一旦出现无法消除的数据相关,那么流水线就会停顿,直到清除相关流水线才会继续流动

    动态调度提出动态发射的思想,若流水线即将发生停顿,硬件会动态选择后续不会违反相关性的指令发射,这也就是常说的顺序发射、乱序执行、乱序完成

    动态调度有许多优点:

    • 对一种流水线编译的代码可以在不同流水线上高效执行,而不需要针对不同微体系结构重新编译
    • 动态调度能克服编译器静态调度不能确定的相关性(上述难题)
    • 允许处理器容忍一些不确定/动态的延迟,如缓存缺失带来的延迟,静态调度是无论如何也不能做到这一点的

    5.3.1 记分牌动态调度

    记分牌算法把ID段分成两个步骤:

    • 发射:译码,并检测结构相关
    • 读操作数:等到没有数据相关时读入操作数

    其主要思想为,在没有结构冲突时尽可能的发射指令,若某条指令停顿则选取后续指令中与流水线正在执行和停顿的指令发射

    (1)记分牌四阶段

    阶段内容
    Issue发射如果当前指令所使用的功能部件空闲,并且没有其他活动的指令(执行和停顿)使用相同的目的寄存器(避免WAW),记分牌发射该指令到功能部件,并更新记分牌内部数据。如果有结构相关或WAW相关,则该指令的发射暂停,并且也不发射后继指令,直到相关解除。
    Read读操作数如果先前已发射的正在运行的指令不对当前指令的源操作数寄存器进行写操作,或者一个正在工作的功能部件已经完成了对该寄存器的写操作,则该操作数有效。操作数有效时记分牌控制功能部件读操作数,准备执行。(避免RAW)
    Execute执行接收到操作数后功能部件开始执行。当计算出结果后,它通知记分牌该条指令的执行结束,记分牌记录
    Write写结果一旦记分牌得到功能部件执行完毕的信息后,记分牌检测WAR相关。如果没有WAR相关就写结果,否则暂停该条指令。

    (2)记分牌硬件部件

    1.Instruction status记录正在活动的指令处于四阶段中的哪一步

    2.Function unit status记录功能部件(完成运算的单元)的状态,其中每个FU有9个记录参量:

    • Busy:该功能部件是否正在使用
    • Op:该功能部件当前完成的操作
    • Fi:目的寄存器编号
    • Fj,Fk:两个源寄存器编号
    • Qj,Qk:产生源操作数Fj,Fk的功能部件
    • Rj,Rk:标识Fj,Fk是否就绪的标志位

    3.Register result status记录哪个FU对某个寄存器是否进行写操作(还未写入),若没有该域为空

    (3)动态调度算法

    有了上述三个部件,就可以完成四阶段中一些查看操作,如FU是否空闲、操作数是否就绪(能否执行)、是否存在WAW等

    之所以该算法称为记分牌算法,是因为这三个部件就像公示的记分牌一样,流水线中各操作都需要去查看记分牌的状态并根据执行情况在记分牌中写入相应参数信息

    将四阶段和记分牌控制用伪代码的形式给出,wait util是某指令向下阶段流水的必要条件,Book keeping是该流水段执行完毕后需要记录的信息:

    StatusWait UntilBook Keeping
    Issue!FU.busy && result[D] == nullFU.busy = true; FU.op = op; FU.Fi = ‘D’; FU.Fj = ‘S1’; FU.Fk = ‘S2’; Qj = result[S1]; Qk = result[S2]; Rj = (Qj == null ? true : false); Rk = (Qk == null ? true : false); Result[D] == ‘FU’(若是源操作数是立即数或R整数寄存器,对应Rjk直接是yes)
    ReadRj && RkRj = true; Rk = true;
    ExecuteFU completerecord complete cycle
    Write任意其他FU的Fj和Fk不是FU.Fi(WAR)或者他们已经ready“通知”所有Fj和Fk是FU.Fi的其他FU该操作数ready,修改Rj/k为true; Result[FU.Fi] = null; FU.busy = false;

    5.3.2 Tomasulo动态调度

    另一种动态调度算法是Tomasulo动态调度算法,它和记分牌的区别主要有:

    • 控制和缓存在记分牌中是集中的,Tomasulo是分布在各部件中
    • Tomasulo的FU称做Reservation Station保留站(RS),RS中表示寄存器要么是寄存器值,要么是指向RS或Load Buffer(也可以看做特殊的RS)的指针;RS可以完成寄存器重命名,避免WAR、WAW,RS可以多于寄存器,实现更多编译器无法完成的优化
    • Register result status中记录的结果都是RS的名字,而不是寄存器
    • FU计算完毕后通过Common Data Bus(CDB)广播给所有其他RS,并修改Register result status中记录
    • Tomasulo可以跨越分支!不仅仅局限于基本快内部FP操作的乱序执行

    Tomasulo受限于CDB的性能,一般采用高速CDB

    (1)寄存器重命名

    为什么寄存器重命名能够避免WAR和WAW?事例如下:

    DIVD    F0,F2,F4
    ADDD    F6,F0,F8
    SD      F6,0(R1)
    SUBD    F8,F10,F14
    MULD    F6,F10,F8

    存在下列三个名称相关:

    • SUBD的目的操作数是F8,ADDD源操作数是F8,存在WAR冒险
    • MULD的目的操作数是F6,SD源的操作数是F6,存在WAR冒险
    • MULD的目的操作数是F6,ADDD目的操作数是F6,存在WAW冒险

    用T、S重命名寄存器,有:

    DIVD    F0,F2,F4
    ADDD    S,F0,F8
    SD      S,0(R1)
    SUBD    T,F10,F14
    MULD    F6,F10,T

    且后续F8都用T代替,那么有:

    • SUBD写入T可以先于ADDD读F8,WAR冒险消除
    • MULD写入F6可以在SD读入S之前,WAR冒险消除
    • MULD写入F6可以在ADDD写入S之前,WAW冒险消除

    (2)部件结构

    1.RS的结构和记分牌算法的FU相似,因为有了寄存器重命名,它省去了F和R两个标志位:

    • Busy:该RS是否正在使用
    • Op:该RS当前完成的操作
    • A:存放存储器地址,开始存立即数,计算出有效地址后存有效地址
    • Vj,Vk:源操作数的值
    • Qj,Qk:产生源操作数的RS

    2.Register result status中存对某一寄存器写操作的RS名字

    (3)三阶段

    阶段内容
    Issue发射如果对应RS空闲(无结构相关),则发射指令和操作数(RS重命名避免WAR和WAW)
    Execute执行两操作数就绪后RS开始执行,若没准备好随时监听CDB以获取所需的操作数(避免RAW)
    Write写结果CDB传送所有结果,并修改Register result status

    (4)Tomasulo流水控制

    Tomasulo动态调度算法的伪代码表示如下:

    1.发射阶段:

    // rs、rt为源操作数
    // rd为目的操作数
    
    void issue() {
        if op == FP operation {
            wait until: RS[r].busy == false; // r是和FP Operation对应的RS编号
    
            if RegisterStatus[rs].Qi != null {
                RS[r].Vj = null;
                RS[r].Qj = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vj = Register[rs];
                RS[r].Qj = null;
            }
    
            if RegisterStatus[rs].Qk != null {
                RS[r].Vk = null;
                RS[r].Qk = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vk = Register[rs];
                RS[r].Qk = null;
            }
    
            RS[r].busy == true;
            RegisterStatus[rd].Qi = r; 
        }
    
        if op == Load or Store {
            wait until: RS[r].busy == false; // Load Buffer和RS相同数据结构
    
            if RegisterStatus[rs].Qi != null {
                RS[r].Vj = null;
                RS[r].Qj = RegisterStatus[rs].Qi;
            } else {
                RS[r].Vj = Register[rs];
                RS[r].Qj = null;
            }
    
            RS[r].A = imm;
            RS[r].busy = true;
    
            if op == Load { // Load only
                RegisterStatus[rt].Qi = r;
            } else {        // Store only
                if (RegisterStatus[rd].Qi != null) {// 避免WAW
                    RS[r].Vk = null;
                    RS[r].Qk = RegisterStatus[rt].Qi;
                } else {
                    RS[r].Vk = Register[rt];
                    RS[r].Qk = null;
                }
            }
        }
    }
    

    2.执行阶段:

    void execute() {
        if op == FP Operation {
            wait until: RS[r].Qj == null && RS[r].Qk == null
    
            compute result with Operand in Vj and Vk;
        }
    
        if op == Load or Store {
            wait until: RS[r].Qj = 0 && r is head of load-store queue(每次处理队头元素)
    
            RS[r].A = RS[r].Vj + RS[r].A;
    
            if op == Load {
                wait until: RS[r].A写入完成
    
                Read from Mem[RS[r].A]
            }
        }
    }

    3.写结果阶段:

    void write() {
        if op == FP Operation {
            wait until: Execution of r is complete & CDB available
    
            for all x in RegisterStatus_Index_Set par-do { 
                // 硬件并行执行,模拟直接for循环串行模拟即可
                if RegisterStatus[x].Qi == r {
                    Register[x] = result;
                    RegisterStatus[x].Qi = null;
                }
            }
    
            for all x in RS_Index_Set par-do {
                if RS[x].Qj == r {
                    RS[x].Vj = result;
                    RS[x].Qj = null;
                }
    
                if RS[x].Qk == r {
                    RS[x].Vk = result;
                    RS[x].Qk = null;
                }
            }
    
            RS[r].busy = false;
        }
    
        if op == Store {
            wait until: Execution of r is complete & RS[r].Qk == null
    
            Mem[RS[r].A] = RS[r].Vk;
            RS[r].busy = false;
        }
    }

    5.3.3 Tomasulo处理循环

    Tomasulo算法能够循环覆盖执行,关键点在于:

    • 寄存器重命名:不同循环中处理不同的物理存储位置,寄存器重命名将寄存器表示为动态的指针,增加了寄存器的个数
    • 整数部件先行:以便能够发射多个循环中操作

    参考链接: https://blog.csdn.net/load2006/article/details/12774103

    参考链接: https://blog.csdn.net/liudongdong19/article/details/80761637

    参考链接: https://www.zhihu.com/question/21823699/answer/111606716

    参考链接: https://blog.csdn.net/u014030117/article/details/46576043

    展开全文
  • 并行算法】并行循环

    千次阅读 2020-06-16 18:17:52
    一、循环并行性 在主要的程序结构中,循环结构一般是比较耗时的部分。如果可以并行执行循环,那么可以很大程度上提高Matlab程序的执行效率 对于次数确定的循环(for循环),如果循环的‘计数模块’对于单次循环...

    一、循环的并行性

    在主要的程序结构中,循环结构一般是比较耗时的部分。如果可以并行执行循环,那么可以很大程度上提高Matlab程序的执行效率

    对于次数确定的循环(for循环),如果循环的‘计数模块’对于单次循环是独立的(计算结果与循环体的执行顺序无关),那么理论上可以将整个循环拆分成几个子循环,然后将子循环的结果合并。

    编写Matlab并行程序时,有两种模式。利用Matlab提供的并行计算模块;利用Matlab提供的通用并行程序设计方法。

    Matlab提供的并行计算模块,除了parfor和spmd外,还提供了for-drange、pmode、dfeval和dfevalasync等标准并行结构。

    二、parfor循环的基本原理

    由for关键字表示的循环可以通过parfor关键字进行并行。Matlab遇到parfor关键字时表示循环采用并行方式执行。

    parfor关键字并行执行for循环时,会将for循环划分为若果部分,每部分交由不同的worker执行。循环次数能够被worker数量整除时,循环被平均划分;否则某些worker会执行较多的循环次数。

    worker是一个逻辑上的概念,指能并行运行代码的Matlab端。对于微机,单个处理器可以运行一个或多个worker。

    注意:

    1).parfor应用的前提是循环能够分解成互不相关的分段;

    2).parfor并行时会占用计算机资源进行必要的数据通信(循环的效率与循环的长度、需要传输的数据量有关)

    默认情况下,Matlab只启动一个进程。Matlab执行parfor之前,需要打开并行计算池。

    Matlab并行计算池管理若干worker,每个worker都可以被分配执行并行任务。对于一个CPU,可以运行一个或多个worker,一般情况下,可以只运行一个woeker。

    三、parfor循环示例

    1)串行循环与并行循环的运行结果比较

    %串行循环与并行循环的结果比较
    mypool=parpool
    n=8;
    a1=zeros(n,1);
    for i=1:8
        a1(i)=i;
    end
    a2=zeros(n,1);
    parfor i=1:8
        a2(i)=i;
    end
    [a1 a2]
    delete(mypool)

    运行结果

    第一列为串行循环,第二列为并行循环

    可以看出结果是一样的,也就是说串行循环与并行循环的结果是一致的。

    2)串行循环与并行循环的执行顺序比较

    %串行循环与并行循环的执行过程比较
    mypool=parpool
    n=8;
    display('for:')
    for i=1:n
        display(num2str(i));
    end
    display('parfor:');
    parfor i=1:n
        display(num2str(i));
    end
    delete(mypool)

    运行结果

    上方为串行,下方为并行

    可以看出,串行循环的执行顺序为1到8。

    并行循环,我的处理器是二核的,8除以2是能够整除的,平均分配第一个处理器是6547,第二个处理器是3218(并行时,不同的计算机,不同的次数,都有可能导致结果的不同,且不受人为干预)

    3)串行循环与并行循环的执行时间比较

    %串行循环与并行循环的执行时间比较
    mypool=parpool
    n=600;
    tic
    for i=1:n
        a1(i)=det(randn(n));
    end
    t1=toc;
    display(strcat('for:',num2str(t1),'s'));
    
    tic
    parfor i=1:n
        a2(i)=det(randn(n));
    end
    t2=toc;
    display(strcat('parfor:',num2str(t2),'s'));
    delete(mypool)

    运行结果

    for为串行循环的输出,parfor为并行循环的输出。

    结论

    1)串行循环与并行循环的运行结果一致

    2)串行循环与并行循环的执行顺序不同

    3)串行循环比并行循环的执行时间更长

     

    展开全文
  • 指令级并行

    万次阅读 2018-07-02 16:49:08
    指令级并行流水线提高的是指令带宽(吞吐率),而不是单条指令的执行速度相关限制了流水线性能的发挥 结构相关:需要更多的硬件资源 数据相关:需要定向,编译器调度 控制相关:尽早检测条件,计算目标地址,延迟...

    指令级并行

    流水线提高的是指令带宽(吞吐率),而不是单条指令的执行速度
    相关限制了流水线性能的发挥
        结构相关:需要更多的硬件资源
        数据相关:需要定向,编译器调度
        控制相关:尽早检测条件,计算目标地址,延迟转移,预测
    增加流水线的级数会增加相关产生的可能性
    异常,浮点运算使得流水线控制更加复杂
    编译器可降低数据相关和控制相关的开销
        Load 延迟槽
        Branch 延迟槽

        Branch预测

    指令级并行性又称细粒度并行, 主要是相对粗粒度并行而言的。
    粗粒度并行存在于程序间,主要是进程或线程间的并行性。

     指令级并行是指存在于指令一级即指令间的并行性, 主要是指机器语言一级, 如存储器访问指令、整型指令、浮点指令之间的并行性等。主要特点是并行性由处理器硬件和编译程序自动识别和利用, 不需要程序员对顺序程序作任何修改。正是由于这一优点, 使得它的发展与处理器的发展紧密相连。

    基于硬件的动态方法

     基于软件的静

    硬件+软件技术

     CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 
                     + 停顿控制冲突
    理想CPI是衡量流水线最高性能的一个指标。减少等式右端的各项就减少了总的的CPI,从而提高IPC.
    IPC:Instructions Per Cycle
       (每个时钟周期完成的指令条数)

    开发循环级并行的技术
        循环展开(loop unrolling)技术

       采用向量指令和向量数据表示

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

    :数据流和异常行为。

    保持异常行为是指:无论怎么改变指令的执行顺序,都不能改变程序中异常的发生情况。

    数据流:指数据值在产生结果的指令到使用结果的指令的实际流动。 
    分支指令使得数据流具有动态性,因为它让给定指令的数据可以有多个来源。

    仅仅保持数据相关性是不够的,只有再加上保持控制顺序,才能够保持程序顺序。(因为一条指令可能数据相关于多条先前的指令)


    静态调度

    依靠 编译器对 代码进行静态调度,以减少相关和冲突。
    它不是在程序执行的过程中、而是在 编译期间进行代码调度和优化 ,对相关的处理方法在程序执行过程中始终不变。
    通过把相关的指令拉开距离来减少可能产生的停顿。

    动态调度

    在程序的执行过程中,依靠 专门硬件对代码进行调度 ,减少数据相关导致的停顿。

    动态调度的基本思想

    流水线的最大的局限性:
    指令必须按序流出和按序执行

    乱序执行基本思想:通过指令窗口按序保存多条指令,采用数据流技术控制操作数就绪的指令优先执行(乱序执行)。异常处理比较复杂

    动态调度要保持正确的异常行为:对于一条会产生异常的指令来说,只有当处理机确切地知道该指令将被执行后,才允许它产生异常。
    即使保持了正确的异常行为,动态调度处理机仍可能发生不精确异常。 
    不精确异常:当执行指令i导致发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同。
    发生不精确异常的原因:
          因为当发生异常(设为指令i)时:
    流水线可能已经执行完按程序顺序是位于指令i之后的指令;流水线可能还没完成按程序顺序是指令i之前的指令。 

    精确异常:如果发生异常时,处理机的现场跟严格按程序顺序执行时指令i的现场相同。

     Tomasulo算法 

    核心思想
       
     记录和检测指令相关,操作数一旦就绪就立即执行,把发生RAW冲突的可能性减少到最小;
        通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站和流出逻辑来共同完成的。



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

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

    优点

    冲突检测逻辑是分布的
         (通过保留站和CDB实现)

    消除了WAW冲突和WAR冲突导致的停顿

    流出---执行 ---写结果




    动态分支预测技术:在程序运行时,根据分支指令过去的表现来预测其将来的行为。

    分支预测的有效性取决于:
        预测的
    准确性
        预测正确和不正确两种情况下的分支开销
        决定分支开销的因素:
            流水线的结构
            预测的方法
            预测错误时的恢复策略等

    采用动态分支预测技术的目的
          预测分支是否成功
         尽快找到分支目标地址(或指令)
        (避免控制相关造成流水线停顿) 
    需要解决的关键问题
         如何记录分支的历史信息;
         如何根据这些分支的历史信息来预测分支的去向(甚至取到指令)。

    (1)仅仅记录最近一次或最近几次的分支历史;
      (2)记录分支成功的目标地址;
      (3)记录分支历史和分支目标地址,相当于前
                面两种方式的结合;
      (4)记录分支目标地址的一条或若干条指令。     

    采用分支历史表 BHT  或分支预测缓冲器

    预测错误两次,才会改变预测结果


    两个步骤:
    分支预测。
    当分支指令到达译码段(ID)时,根据从BHT读出的信息进行分支预测 。
    若预测正确,就继续处理后续的指令,流水线没有断流。否则,就要作废已经预取和分析的指令,恢复现场,并从另一条分支路径重新取指令。 
    状态修改。 
    BHT方法只在以下情况下才有用:
        判定分支是否成功所需的时间大于确定分支目标地址所需的时间。 



      如果预测错误或在BTB中没有匹配的项,要有至少2个时钟周期的开销。
       因为:
       ①需要更新BTB中的项,要花费一个时钟周期;
       ②在更新BTB 中的项时,要停止取指令,那么取新的   指令又要花费一个时钟周期。

    更快地获得分支目标处的指令;
    可以一次提供分支目标处的多条指令,这对于多流出处理器是很有必要的;

    使我们可以进行称为分支折叠(branch folding)的优化。

    基于硬件的前瞻执行


       允许指令乱序执行,但必须按程序顺序确认。


    ROB中的每一项由以下4个字段组成:
    指令类型
        指出该指令是分支指令、store指令或寄存器操作指令。
    目标地址
           给出指令执行结果应写入的目标寄存器号(如果是
        load和ALU指令)或存储器单元的地址(如果是store指
        令)。
    数据值字段
       用来保存指令前瞻执行的结果,直到指令得到确认。
    就绪字段
        指出指令是否已经完成执行并且数据已就绪。
    控制字段
        设置ROB的某一项是否被占用



    9

    展开全文
  • 指令级并行--计算机体系结构

    千次阅读 2020-08-31 16:47:03
    由于指令可以并行执行,所以指令之间可能实现的这种重叠称为指令级并行(ILP)。 ILP大体有两种不同开发方法 1) 依靠硬件来帮助动态发现和开发并行 2) 依靠软件技术在编译时静态发现并行 基本块:一段顺序执行代码...
  • 系统结构期末复习(四)指令级并行

    千次阅读 多人点赞 2020-07-22 01:14:51
    3. 循环级并行 4. 循环展开 5. 数据流 把握要点: 6. 流水线处理的实际CPI和基本程序宽度该奶奶 7. 循环级并行和基本的开发技术 8. 相关与流水线冲突以及解决方法、程序顺序 9. 数据流和异常行为,这里需注意使用...
  • 数据级并行--计算机体系结构

    千次阅读 2020-09-17 09:42:18
    由于数据操作是并行的,所以程序员可以采用顺序思维方式但却能获得并行加速比 SIMD的三种变体 向量体系结构 多媒体SIMD指令集扩展 图形处理单元(GPU) 二、 向量体系结构 本质:以流水线形式来执行多数据操
  • 开发计算机并行性的方法【理论】

    千次阅读 2016-08-30 15:48:21
    并行性主要是指同时性或并发性,并行处理是指对一种相对于串行处理的处理方式,它着重开发计算过程中存在的并发事件。 并行处理(Parallel Processing)是计算机系统中能同时执行两个或更多个处理的一种计算方法。...
  • 什么是指令级并行(ILP),以及开发ILP的两种途径 ILP:当指令中不存在相关时,它们在流水线上是可以重叠执行的,我们重叠执行指令以提高性能。而这种指令序列存在的潜在并行性称为指令级并行。 ...
  • 体系结构习题 数据级并行

    千次阅读 2019-11-29 01:00:24
    convoy - 护航指令组,一组可以一直执行的向量指令,不包含任何结构冒险 条带挖掘(strip mining) 一种生成代码的技术,使每个向量运算都是针对小于或等于MVL的大小来完成的。即将向量分段,第一段长度为n%MVL,...
  • 计算机指令级并行

    千次阅读 2012-12-17 22:17:46
    提高桌面级计算机指令级并行度的方法 http://ce.sysu.edu.cn/hope2008/Education/ShowArticle.asp?ArticleID=13367 作者:未知 厚朴教育来源:转载 点击数:525 更新时间:2011-7-24  并行计算...
  • 什么是并行计算?

    万次阅读 多人点赞 2020-01-15 14:26:19
    最近项目需要实现程序的并行化,刚好借着翻译这篇帖子的机会,了解和熟悉并行计算的基本概念和程序设计。帖子的原文见这里。 这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的...
  • 1、并行计算的定义和主要目的 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十个、几千个、几万个等)通过...
  • 本文介绍了图计算中的核心概念与算法,了解这些基本知识可以帮助我们更好更快的探索一个图,找到相应的解决方案,同时也是更深层次研究的基础。
  • 要理解并行编程,首先要从并行的理解开始。 (1)从Wiki中并行编程的解释说起 Wiki是个好东西,包含了很多专业术语的解释,关键的是,除了解释,wiki还是一个好文档。 Paralle Programming(并行编程/并行...
  • 最大搜索子树 morris遍历 最小生成树 拓扑排序 最短路 简单迷宫问题 深搜DFS\广搜BFS 皇后问题 一般思路: 优化1: 优化2: 二叉搜索树实现 Abstract Self-Balancing Binary Search Tree 二叉搜索树 概念引入 ...
  • 并行:2 使用GPU理解并行计算

    千次阅读 2019-11-10 13:07:37
    文章目录2.7 常见的并行模式2.7.1 基于循环的模式循环的迭代依赖是指循环的一次迭代依赖于之前的一次或多次先前迭代的结果。基于循环的迭代是实现并行化的模式中最容易的一个。对问题的分解 依据可用的逻辑处理单元...
  • 目录 动态分支预测技术 概念 分支预测的有效取决于 动态分支预测技术的目的 分支预测表 BHT 1个预测位 ...指令调度与循环展开 ...概念 ...循环展开 ...概念 ...循环展开和指令调度的注意事项 ...指令级并行总...
  • Matlab并行运算

    万次阅读 2014-06-06 17:14:31
    今天搞了一下matlab的并行计算,效果好的出乎我的意料。 本来CPU就是双核,不过以前一直注重算法,没注意并行计算的问题。今天为了在8核的dell服务器上跑程序才专门看了一下。本身写的程序就很容易实现并行化,因为...
  • 并行计算的一些思考与总结

    千次阅读 2020-02-17 14:36:15
    分条/分块分解法要求程序员把问题分成若干个小块,即分条/分块,绝大多数并行处理方法都可以以不同形式来使用条/块模型,可以很直观的展示并发概念。 在二维空间里可以很容易想象一个问题-数据的一个平面组织...
  • 1、并行计算的定义和主要目的P11 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十个、几千个、几万个等)...
  • 强化学习的并行加速

    千次阅读 多人点赞 2021-02-12 19:53:52
    2017年McGill University和Microsoft的论文《Deep Reinforcement Learning that Matters》中研究了强化学习的可复现,指出像随机种子、环境因素、超参以及使用的codebase带来的不确定都会导致结果难以重现。...
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...
  • 并行计算

    千次阅读 2019-12-20 09:54:44
    科普:并行计算、分布式计算、集群计算和云计算 一、产生的背景 曾经,几乎所有的处理器都是以冯诺依曼计算机架构为基础的。该系统架构简单来说就是处理器从存储器中不断取指,解码,执行。 但如今这种系统架构...
  • 深度学习及并行化实现概述

    千次阅读 2018-02-08 21:25:50
    深度学习及并行化实现概述摘要: 深度学习可以完成需要高度抽象特征的人工智能任务,如语音识别、图像识别和检索、自然语言理解等。深层模型是包含多个隐藏层的人工神经网络,多层非线性结构使其具备强大的特征表达...
  • 今日头条当前后端服务超过80%的流量是跑在 Go 构建的服务上。微服务数量超过100个,高峰 QPS 超过700万,日处理请求量超过3000亿,是业内最大规模的 Go ...Python 的解释语言特性以及其落后的多进程服务模型受到了...
  • 并行计算期末复习

    千次阅读 多人点赞 2020-08-31 16:55:24
    文章目录推动并行计算的因素并行计算的应用超算机并行计算软件技术面临的挑战并行程序设计的复杂数据移动(通信)代价很高能耗挑战伸缩挑战软件生态环境几乎停滞Cache相关工作原理及概念冯诺伊曼结构Cache 高速...
  • 深度学习和并行化实现

    千次阅读 2018-02-07 14:54:29
    开始打造Google Brain项目,用包含16000个CPU核的并行计算平台训练超过10亿个神经元的深度神经网络,在语音识别和图像识别等领域取得了突破的进展[4]。该系统通过分析YouTube上选取的视频,采用无监督的方式训练...
  • 超硬核!操作系统学霸笔记,考试复习面试全靠它

    万次阅读 多人点赞 2021-03-22 18:43:49
    进程可以具有并行性(在多处理器的系统中),但是程序没有 进程是竞争系统资源的基本单位 进程与程序的关系: 一个程序对应多个进程,一个进程又可以为多个程序服务。 进程控制 1.基本知识 进程控制是进程管理中最...
  • JavaScript之异步 - 基本概念

    千次阅读 2017-05-12 20:28:08
    JavaScript之异步 - 基本概念 1.分块的程序 var data = $.ajax({ url: '/Http/GetAction', data: { username: "Rod Chen" }, type: 'GET',

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,598
精华内容 19,839
关键字:

循环级并行性概念

友情链接: CKEBCIO.rar