精华内容
下载资源
问答
  • 体系结构复习 CH5 指令级并行5.1 指令级并行概念5.1.1 指令级并行指令级并行(ILP)指通过通过流水线等技术实现多条指令同时并行执行的并行技术实现ILP主要的方法有: 依靠硬件动态发现和开发并行 依靠软件在编译时...

    体系结构复习 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是该流水段执行完毕后需要记录的信息:

    Status Wait Until Book Keeping
    Issue !FU.busy && result[D] == null FU.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)
    Read Rj && Rk Rj = true; Rk = true;
    Execute FU complete record 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是该流水段执行完毕后需要记录的信息:

    Status Wait Until Book Keeping
    Issue !FU.busy && result[D] == null FU.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)
    Read Rj && Rk Rj = true; Rk = true;
    Execute FU complete record 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

    展开全文
  • 计算机指令级并行

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

      并行计算从其并行的粒度来看,分为指令级、循环级、过程级、子程序级、作业级;而从并行计算机的体系结构而言,存在着核内并行、晶核级并行、PCB板级核间并行、机箱级并行、机架级并行、机群(异构)级并行,等多种并行等级。不同的并行粒度与不同的并行等级之间,是有着对应关系的。
      其指令级并行,与CPU内部结构有着紧密的关联,指令级并行包括核内多条指令的并行与多个核之间指令的并行。从计算机体系结构而言,就是核内并行与晶核级并行。如何提高这两种并行度,对于CPU结构有着不同的要求;对于并行程序的编制也有不同的要求。
      本文根据本人近期所阅读的书籍,以及从网络上获取的资料,通过分析目前较新的并行芯片结构,找到提高并行度的关键点。并从软、硬件方向预测为了进一步提升效率,未来并行芯片结构的发展方向,以及编制并行软件的改变。

    一:核内并行
    1:指令的流水线操作
      事实上从8086开始,就存在有核内并行。
      在8086以前的微处理器,对指令的操作都是串行的,即对每一条指令而言,都是先取指令,再分析、执行。具体可表示为:

    取指令——【读操作数】——执行——【写操作数】——取(下一条)指令一……

    方括号内的操作是操作数在内存中时所要进行的,当操作数是CPU内部的某个寄存器时,则不需要这一步。显然,在指令执行期间,总线(BUS)是空闲的,这一重要的系统资源没有得到充分利用。
      而8086是由它由两大部分组成:执行部件(Eu:Execute Unit)和总线接口部件(BIU :BUS Interface Unit)。前者负责指令的译码和执行,后者负责所有涉及外部总线的操作。二者既独立工作,又相互配合。
      而8086在执行部件执行指令期间,总线接口部件可利空闲,用总线预取后续指令或进行存储器操作数的读或写。这种不同指令在同一时间内处于不同执行状态的指令并行操作,或者说指令的重叠执行,通常被称为指令流水线操作。
      BIU使用了指令预取队列机制来实现指令流水线操作。该队列的容量为6个字节,即允许预取6个字节的指令代码。每当指令队列有两个或两个以上的字节空间,且执行部件未向BIU申请读/写存储器操作数时,BIU顺序地预取后续指令的代码,并填入指令队列。
      指令队列的工作方式是先进先出(First-in,First-out,FIFO),或者说是管道方式,先预取的指令即排在前面的指令先被取走执行,后面的依次向前推进,腾出的空间再放新预取的指令。
      而当执行部件执行指令时发现是一条转移指令,则总线接口部件清除队列,从新的地址取指令,并立即送给执行部件去执行,然后,从后续的指令序列中预取指令填满队列。可见,一遇到转移指令,就要重新预取指令队列中的下一条及下下一条指令。显然,这会明显影响机器的运行速度。 
      核内并行,可以极大的减少平均指令执行周期(CPI),如使普通的CISC架构处理器的CPI值从5-8降低到略大于1。

      从上述说明可以看出,要提高核内并行度,有做以下几个方面的提高。

    (a)处理转移指令。
      8086乃至80386、80486,在遇到转移指令时,会放弃所有的指令预取队列,从而影响效率。直到Pentium出现,引入了分支指令预测技术,才得以克服。
      在Pentium微处理器中包含2个预取指令队列,指令的分支预测是由一个叫做分支预测逻辑和分支目标缓冲器(BTB)的功能部件完成的。2个预取指令队列不是同时工作,在同一时刻只有一个预取指令队列处在有效状态。指令预取器从指令Cache中取出指令以后,将它们顺序存放在那个有效的预取指令队列中,当预测分支指令将会发生转移时,预取器将跳转到分支指令的转移目标地址顺序取指,并将当时空闲的第二条指令队列激活,把取出的指令顺序存放在第二条指令队列中。
      同样可以看出,不能使用密集的转移指令,这仍将使分支预取实效。随着分支预取的进一步扩展(如Athlon64可以在16字节的范围内记录3条分支),这一限制正在不断缩小,但仍旧是可能影响效率的一个方面。

    (b)对寻址方式的限制。
      对流水线进行分析,操作数如果是寄存器,自然不需要访问内存;如果是立即数,也已经进入预取队列,并进行了译码。但如果操作数不是寄存器或立即数,就必须重新从内存中读写数据。直接寻址还可以在译码后先期取得;而间址、变址,只能在执行到指令时才进行访问。
    虽说L1、L2乃至L3的高速缓存越来越大,而且从片外移到了片内,提供了较高的命中率,但其速度仍旧无法同寄存器相比。对数据段内存的过多访问,会降低系统的运行效率。通过增加寄存器数量,减少内存访问来提高效率,促使了在上世纪90年代RISC技术的极大发展。
      RISC的load/restore指令只有在访问内存时才使用,所有其它的指令都是在寄存器内对数据进行运算。一条存取数指令从内存将数据取出放到寄存器中,在那里可以对数据进行快速处理,并把它暂存在寄存器里,以便将来还要使用。在适当的时候,一条存数指令可将这个数据送回到它在内存中的地址中去。RISC的设计技术与CISC的设计技术相比,有大量寄存器。由于允许数据在寄存器中保留较长的时间,这样就减少了存/取指令对内存访问的需要。
      RISC中所有指令采用固定长度,寻址方式不超过三种,简化了逻辑和缩短译码时间。确保单周期执行指令,由于指令的固定格式保证指令译码和取操作能同时进行,从而有利于流水线操作的执行。
      精简的指令更容易被流水线所操作。但由于软件的兼容性,以x86系列为代表的CISC仍占据着主要的市场。

    (c)RISC与CISC的结合。
      RISC与CISC各自的优缺点,使其有相互结合的必要。
      从使用IA-32结构的Pentium PRO开始,其微体系结构就采用了RISC的设计思想,它将x86指令转换成多个易执行的微操作(mops),该操作为3操作数格式,对程序员透明,而与x86指令兼容。
      这样,即利用了RISC技术适宜流水线操作的优点,又兼顾了软件的兼容性。

    2:指令的超标量技术
      从Pentium开始,在一个内核中出现了多条流水线。如Pentium就包含两条整型流水线U、V,和一条浮点流水线。这使得CPI首次在理论上可能小于1。
      需要说明的是,这并不是现在意义上的多核芯片,这是因为

    (a)各条流水线使用了同样的指令cache、同一条指令预取队列、同样的寄存器组,根据指令配对法则,将满足一定条件的两条指令同时执行。每条流水线并不能成为完整的内核。
    (b)U、V两条流水线并不相同。U流水线可以执行所有的x86指令,而V流水线只能执行部分的“简单”指令。而能够同时执行的两条指令,也必须都是“简单”指令,并且没有寄存器数据相关。所谓的“简单”指令是指由硬件逻辑、而非微码实现的单周期指令。

      而Pentium PRO中,各条流水线的功能已经相对独立。在实际操作时,各流水线使用独立的寄存器,并由分发 / 执行部件(DEU)将操作数无关的mops“乱序”执行。而在执行结束以后,通过退离部件(RU)按原指令流的顺序取走已执行完的mops,把物理寄存器还原成逻辑寄存器,把无序的执行按原始指令流输出结果。
      使用RISC设计思想而出现的mops、多物理寄存器结构,都被硬件所屏蔽,对用户透明;用户看到的只是一个可以部分并行的x86结构。

    3:提高核内并行度的方法
      要提高核内并行度,其主要的方法有:

    (a)内存大小匹配:当不同的指令操作相同的数据时,要避免内存大小失配。当一条指令读写了一个数据,随后另一条指令又读写这个数据,则要保证数据是对齐的,即保证两次都以相同的大小读写这一内存数据;
    (b)适当的内存拷贝程序:内存的复制是在程序中经常使用,而且占据相当时间周期的操作,要充分利用其内存带宽,使用专用的读写指令,如读:PREFETCH、写:PREFETCHW等;
    (c)分支指令的对齐:指令的预取是按块进行的,如16B。不要将分支指令与这样的块边界交叉,跨边界的指令不能进行分支预取。会影响执行的效率;
    (d)分支指令的密度:指令分支预取的分支数量是有限的,如果有集中的多条分支出现,就会出现没有预取的分支;
    (e)使用读取—执行的指令:不要使用分别的指令来进行读取和执行,而使用直接读取操作数并执行的方式。以提高cache的命中率;
    (f)避免代码段与数据段的重叠:避免代码的自修改,避免代码段被放到数据段,这些都会引起L1 cache的效率降低;
    (g)使用正确的数据类型:对于浮点指令避免使用整型操作数,SSE、SSE2指令等使用相对应的数据类型;

      上面的方法都可以提高流水线的效率,为整个程序的执行提高也许不到1%的速度。当然要提高指令并行度(ILP),成倍提高运行速度,最关键的是:减少相邻指令的关联度。这样多条指令才能乱序执行,做到真正的指令级并行。

      从计算机体系结构的概念——“程序员所看到的计算机”——而言,让每一个程序员都去了解核内的流水线结构是不现实的。较可行的方法是由优化编译程序来完成。
      上述提高流水线效率的几点,都可以很方便的由编译程序来完成。减少用户程序的指令关联度可能较难;但是可以对所有的库函数进行优化,重新编写出相邻无关的指令序列,从而提高整体的执行效率。

      这里提到了并行计算的最细粒度——指令级并行。由上所述,要提高核内指令级并行,需要的是提高核内的超流水线、超标量技术,并由目标程序充分利用这些技术;最重要的是利用编译程序减少相邻指令的关联度,乱序执行指令。

    二:晶核(DIE)级并行
    1:从单核到多核

      为了提高CPU的性能,通常做法是提高CPU的时钟频率和增加缓存容量。不过目前CPU的频率越来越快,如果再通过提升CPU频率和增加缓存的方法来提高性能,往往会受到制造工艺上的限制以及成本过高的制约。 
      提高计算机的性能已经从单纯的提高速度,转变为由单核向多核发展,通过提高芯片内的并行处理能力,来提高整体的性能。
      大型并行计算机主要有SIMD,PVP,SMP,MPP,DSM,COW六种。多核芯片的模式也将会有类SMP、类MPP、类DSM、类COW等多种形式(SIMD、PVP的结构不利于扩展,发展前途不如其他几种形式)。

    (1)类SMP:随着大规模集成电路技术的发展以及半导体制造工艺的提高,人们已经将大规模并行处理器中的SMP(对称多处理器)集成到同一芯片内,从而实现单芯片多处理器(CMP),各个处理器并行执行不同的进程。SMP技术已经相当成熟,因此此类的多核处理器芯片,结构设计起来相对容易。
      在高端服务器领域,IBM Power5芯片最多可以包含8个处理器;而AMD K8、Intel Pentium D 9xx等桌面级芯片也是实际意义上双核心处理器,目前正向四核发展。
      与传统的SMP相比,CMP尺寸更小、功耗更低、速度更快。
      目前的多核处理器在内核中只放置了较小数量的高速缓存,而没有统一编址的内存(内存与高速缓存的关系见下文)。如果高速缓存的数量极大增加,并且可以统一编址供各个内核对等使用。那么单单一块芯片就能够完成以往一台SMP并行计算机的工作。
      与SMP并行计算机一样,类SMP多核芯片在内核数量增加时,会出现存储总线的访问瓶颈,不利于系统的扩展。

    (2)类MPP:芯片的发展一方面是向多核发展,而另一个方向是向SOC(System on Chip)发展,不仅在芯片中包含控制器、运算器,还包含内存及输入、输出部件。类MPP实际就是这两个发展方向的结合。在一块芯片上集成多个核心,以及内存等其他部件。按照片内内存与内核连接方式的不同,就产生出类MPP与类DSM两种不同结构。
      如果所有的内核对所有的片内内存,可以进行对等存取,那么这仍旧是不利于扩展的SMP结构。类MPP与类DSM都会拥有各自独立的核内内存。
      MPP与DSM的区别在于是否存在内存的统一编址。而对于MSOC而言,芯片是由一个厂商统一规划、设计、生产的。应当较容易实现片内内存的统一编制。
      如果内核不需要访问到其他的核间内存,不进行统一编制,那就是类MPP;而如果核间通讯量大,需要访问核间内存,进行了统一编制,那就是类DSM。

    (3)类DSM:此类芯片中包含有多个内核,每个内核中仍可能有多条流水线,甚至于每个内核仍是一台SMP。如2007年5月新推出的Power6芯片,每个微处理器(MPU)内核都作为2路CMP设计来实现,而在一块芯片上集成2或4块MPU。当然Power6从本文定义的结构上来说,还是类SMP,但在内核结构上已经有了类DSM的影子。
      每个内核都拥有自己独立的核内内存,或是由CMP内核共享的核内内存。该内存的存取速度应当接近于目前L1缓存。每个内核通过特殊的存取指令,可以访问到其他内核的核内内存。虽然内存已经统一编制,但是我仍然建议对于核间内存的访问使用与核内内存不同的指令,程序员应当了解到这两种内存的不同。
      核内内存应当存放被频繁访问的数据。如可以将程序中函数定义的局部变量放到核内内存中。这种方法可以被编译程序所使用,但是程序员无法直接控制。
      另在C语言中有register关键字。在目前条件下,由于寄存器数量较少,人工干预寄存器的分配反而会影响整体的效率。而如果将register关键字对应的变量放入核内内存,则能够极大的提高效率。这就相当于在使用高速缓存的芯片中,一个变量被固定在L1中,还不需要考虑回写。

    (4)类COW:COW与其他结构的并行计算机相比,最大的不同是使用了通用的网络结构来进行连接。而如果将整个COW结构封装到一块芯片中,芯片内各个内核之间的连接必定是专用的。所以在这里的类COW只是套用了这一概念,实际是指多块多核芯片之间的互联。相对与芯片内的连接,PCB板上芯片间的连接网络更加“通用”。
      目前的类SMP结构芯片,已经存在有芯片间的互联。如IBM p5系列小型机,最多可以有64个内核(p5的并发多线程能力(SMT)使得从软件运行角度看,会有128个内核),也就是说会多达有8块Power5芯片互联。
      这里谈谈我对类DSM结构多核芯片互联的一些预测。
      对于每个内核而言,有着核内内存,片内核间内存,片间内存三个层次。这些存在于内核中的内存从整台计算机的角度被统一编制,但是这三个层次内存的访问速度逐级降低。目前意义上的主存,依旧存在,但是从其功能和用途看,更接近于当前意义上的外存储器。
      在当前的计算机中,程序和数据使存放在外设,如硬盘上。需要通过输入输出指令将其读入内存才能进行操作,并在需要的时候回写。而对未来可能的多片类DSM芯片组成的计算机而言,存在有易失性内存与非易失性内存(如FLASH)。非易失性内存取代硬盘作为外设存在;易失性内存临时数据、临时文件的存贮(如数据库的TEMP表空间)。

      类MPP、类DSM、类COW都只是本人的一点预测,从目前的文献以及网络资源上都还没有发现类似的讲法。

    2:超标量、超线程与多核
      虽然CMP相对简单,但对于注重价格因素的桌面系统而言仍是一项复杂的工作。为此业界提出了一个折中的方案——多线程处理器(SMT)。多线程处理器对线程的调度与传统意义上由操作系统负责的线程调度是有区别的,它完全由处理器硬件负责线程间的切换。由于采用了大量的硬件支持,所以线程的切换效率更高。线程高效调度的目的就是要尽可能减少处理器处于闲置状态,通过有效的线程切换来获取处理器在相同工作时间内更高的工作效率。而SMT最具吸引力的是它只需小规模改变处理器核心的设计,几乎不用增加额外的成本就可以获得显著的效能提升。此类技术的代表就是超线程(HT/Hyper –Threading)。

      超线程技术是在一颗CPU同时执行多个程序而共同分享一颗CPU内的资源,理论上要像两颗CPU一样在同一时间执行两个线程,P4处理器需要多加入一个Logical CPU Pointer(逻辑处理单元),用以资源的分配。因此新一代的P4 HT的晶核(DIE)的面积比以往的P4增大了5%。而其余部分如ALU(整数运算单元)、FPU(浮点运算单元)、L2 Cache(二级缓存)则保持不变,这些部分是被分享的。 
      虽然采用超线程技术能同时执行两个线程,但它并不象两个真正的CPU那样,每个CPU都具有独立的资源。当两个线程都同时需要某一个资源时,其中一个要暂时停止,并让出资源,直到这些资源闲置后才能继续。因此超线程的性能并不等于两颗CPU的性能。
      HT技术造就了PENTIUM 4的一个辉煌时代的武器,尽管它被评为失败的技术,但是却对P4起一定推广作用。其实引用《现代计算机》杂志所比喻的HT技术好比是一个能用双手同时炒菜的厨师,并且一次一次把一碟菜端上桌;而真正的双核心处理器好比2个厨师炒两个菜,并同时把两个菜端上桌。很显然双核心处理器性能要更优越。按照技术角度PENTIUM D 8xx系列不是实际意义上的双核心处理器,只是两个处理器集成,但是PENTIUM D 9xx就是实际意义上双核心处理器,而K8从一开始就是实际意义上双核心处理器。 
      需要注意的是,含有超线程技术的CPU需要芯片组、BIOS、操作系统和应用软件支持,才能比较理想的发挥该项技术的优势。
      目前支持超线程技术的芯片组包括如: Intel 845E以后的芯片组,如845PE/GE/GV、865/875和915/925系列芯片组;VIA的P4X400、P4X533、PT800、PT880、PM800和PM880芯片组;SIS的SIS655、SIS648FX、SIS661FX、SIS655FX、SIS655TX、SIS649和SIS656芯片组;ULI的M1683和M1685芯片组。
      操作系统如:Microsoft Windows XP、Microsoft Windows 2003,Linux kernel 2.4.x以后的版本也支持超线程技术。
      一般来说,只要能够支持多处理器的软件均可支持超线程技术,但是实际上这样的软件并不多,而且偏向于图形、视频处理等专业软件方面。应用软件有Office 2000、Office XP等。但事实上如果有用户并发的操作,就能享用到一定的性能提升。

      双芯虽然比超线程更复杂,但事实上双核芯片早以有之。 “双核”的概念最早是由IBM、HP、Sun等支持RISC架构的高端服务器厂商提出的,不过由于RISC架构的服务器价格高、应用面窄,没有引起广泛的注意。比如拥有128MB L3缓存的双核心IBM Power4处理器的尺寸为115x115mm,生产成本相当高。
      而Intel和AMD公司的桌面产品正从单核多流水线、伪双核(超线程)向着真正的双核、多核进展。把多核并行从高端带到了平民阶层。而这两家公司的“真”双核产品还存在着很多结构上的不同。
      AMD Opteron 处理器从一开始设计时就考虑到了添加第二个内核,两个CPU内核使用相同的系统请求接口SRI、HyperTransport技术和内存控制器,兼容90纳米单内核处理器所使用的940引脚接口。是将两个内核做在一个晶核上,通过直连架构连接起来,集成度更高。从用户端的角度来看,AMD的方案能够使双核CPU的管脚、功耗等指标跟单核CPU保持一致,从单核升级到双核,不需要更换电源、芯片组、散热系统和主板,只需要刷新BIOS软件即可。
      而Intel则是将放在不同晶核上的两个完整的CPU内核封装在一起,连接到同一个前端总线上。可以说,AMD的解决方案是真正的“双核”,而英特尔的解决方案则是“双芯”。可以设想,这样的两个核心必然会产生总线争抢,影响性能。不仅如此,还对于未来更多核心的集成埋下了隐患,因为会加剧处理器争用前端总线带宽,成为提升系统性能的瓶颈,而这是由架构决定的。
      因此可以说,AMD的技术架构为实现双核和多核奠定了坚实的基础。AMD直连架构(也就是通过超传输技术让CPU内核直接跟外部I/O相连,不通过前端总线)和集成内存控制器技术,使得每个内核都自己的高速缓存可资遣用,都有自己的专用车道直通I/O,没有资源争抢的问题,实现双核和多核更容易。而Intel是多个核心共享二级缓存、共同使用前端总线的,当内核增多,核心的处理能力增强时,肯定要遇到堵塞的问题。

    3:现有的高并行度多核芯片
      目前已经存在的高并行度多核芯片,不是哪家厂商生产的CPU,而是被称为GPU的显示处理芯片。
      单就浮点性能而言,现在的处理器已经远不如显示处理芯片,比如Intel Pentium 4 3.0 GHz约为6Gflops(每秒十亿次浮点操作),四路双核心Itanium 2也不过45Gflops,而最新的AMD R600可达到475Gflops。
      当今最强大的超级计算机是IBM的蓝色基因/L,拥有65536个双核心处理器,也就是131072个处理核心,峰值运算性能367TFlops。如果换算成R600,理论上只需不到800个图形处理器就能达到蓝色基因/L的性能水平。
      ATI早先发布的催化剂7.4驱动已经能够支持斯坦福大学的蛋白质折叠分布式计算,只要拥有一块X1000系列显卡,接入互联网,并且安装了斯坦福大学GUP分布式计算应用程序。那么就可以在显卡空闲时(非3D模式)为科学计算做一份贡献。由于所有的计算都是由显卡来完成,因此它不会占用您的CPU和内存资源,在上网和文字处理时不会受到任何影响,仅仅是占用少量的网络带宽,另外要消耗一部分电能。
      一家软件公司Peakstream声称,他们已经开发出一套新的软件平台,结合普通处理器的处理能力和显卡的资源即可打造出超级计算机。只需在已有计算机内简单地增加显卡,Peakstream就能将原有系统的能力提高20倍之多。根据Peakstream提供的数据,该平台性能与传统的处理器系统相比,在Monte Carlo Simulation测试中成绩可提高16倍,在Kirchhoff Migration中可提高21倍。GPU已经超越CPU成为当今桌面电脑系统里最强大的部件。

      GPU的主要部件包括顶点着色单元、象素着色单元、纹理单元、光栅化引擎。而随着DirectX10的发布,nVidia最新的G80(06年11月推出)与AMD(ATI)的R600(07年5月推出)都采用了统一渲染结构,使用较为通用的处理内核来进行顶点运算和象素运算。G80使用了128个并行的流处理器;R600使用了64个流处理器单元,而每个单元中有5个ALU,其中一个还能进行诸如Sin、Cos的复杂运算。

      除了内核数量的增多,显示处理芯片所能够达到的高性能还有以下一些原因。
    (a)流水线程度高:CPU中就使用了流水线来提高核内并行度,如Pentium 4就有20级的流水线。但是流水线级数越多,一条指令从开始进入流水线到最后被执行完毕这之间的延迟间隔会相当大。而CPU的设计目标是不仅要有很高的吞吐量,还要求很小的延迟,这是CPU并不采用过多流水线级数的原因之一。另外流水线只有在满载时,才能发挥出最佳效率来。由于CPU执行的代码中有很多分支语句,因此长流水线需要用有效的技术来预测分支,尽量保持流水线在满负荷状态。但是一旦预测分支失败,就会清除流水线中滞留的大量无用指令,如果流水线阶段过多的话,再次充满整个流水线就需要很长的时间,速度反而下降了。所以权衡利弊,CPU不会使用深度流水线。
      但是GPU却采用了几百级的流水线,比如GeForce 3的流水线有800个阶段。这是因为1:显示可以有相当的延迟,只需要满足人眼的视觉暂留即可;即便是为了增强互动程度而提高帧速到100,也不过需要在10ms中完成,这对于只有几ns的时钟周期来说,根本就是天文数字,完全可以延迟。2:在GPU中执行的Shader程序中,分支语句用的很少(在早期的GPU中,甚至不提供动态的分支语句),流水线可以长时间的保持满负荷状态。因此,GPU的流水线深度变大后,利大于弊,大大提升了整体性能。
    (b)并行线程的切换:GPU的执行速度很快,但是当运行到慢速指令,如从内存中获取纹理数据这样的指令时(由于内存访问是瓶颈,而且纹理越练越大,此操作比较缓慢),整个流水线便出现长时间停顿。在GPU内部Cache命中率不高,只用Cache解决不了这个问题。所以,为了保持流水线保持忙碌,GPU中使用了多线程机制。由硬件完成对这一线程的切换,对另一个像素进行处理。等到慢速指令完成时,可再切换到原先线程。
    (c)并行数据的无关性: 无论是CPU送给GPU的顶点数据,还是GPU光栅生成器产生的像素数据都是互不相关的,可以并行地独立处理。而且顶点数据(xyzw),像素数据(RGBA)一般都用四元数表示,适合于并行计算。在GPU中专门设置了SIMD指令来处理向量,一次可同时处理四路数据。GPU中的各个执行部件,可以各自独立的获取数据,并进行计算,从而提高总体的运行效率。
    (d)内存访问的限制:纹理片要么只能读取,要么只能写入,不允许可读可写,从而解决了存贮器访问的读写冲突。GPU这种对内存使用的约束也进一步保证了并行处理的顺利完成。

    4:GPU的并行结构适合于并行科学计算
      以R600为例,其64个流处理器单元,每个单元中有5条流水线,从本文涉及的并行计算角度来讲,这就比G80多了一级核内并行。这5个ALU既可以一同执行一条5维向量运算,也可以同时执行5条标量运算,甚至是2+2+1、4+1等多种组合形式。而这一分配正是由分支执行单元(Branch Execution Unit)进行乱序分配而实现的,符合本文所述的核内指令级并行情况。
      而G80的128个流处理器被分为8组并行的阵列,每组16个流处理器;这16个处理器共享L1缓存(这一阵列的核内内存),每个处理器中只有一条流水线。这一个阵列就类似于一台CMT。而8组CMT合并成为一台类DSM。而线程的是通过线程处理器(Thread Processor)来进行分配。

      随着高速缓存的逐步扩大,cache块表所占据的容量也将增加,会使缓存实际容量的减少,造成浪费。个人认为当L1缓存从k级别大小上升到M级别时,就会拥有自己的地址,允许程序员自行将所需要的数据、变量放入其中。这主要是针对数据cache,当容量足够大时,由程序员自行定义会比硬件自动预取高效;而对于指令cache,由于指令的顺序执行特性,由硬件完成自动预取同样可以有很高的命中率。这可能会成为哈佛结构cache的一种发展方向。
    其实这种拥有地址的高速内存,与RISC结构中数量成百上千的寄存器起到了同样的作用。将缓存改为内存,其实就是增加了程序员对缓存的直接干预;并由于取消了缓存与主存的映射,避免的回写问题。
      如果高速内存进一步扩大,大到能够放下整个进程运行所需要的代码段和数据段。那就达到了晶核级并行的理想状态。只有进程间的通讯才需要访问到核外的内存,每个线程在独立的内核中运行,由多流水线乱序执行指令,来实现核内并行;内核中的多路CMP共享核内内存,执行一个进程中各自的线程,执行晶核级并行;各个进程使用各自的CMP,执行核间并行。
    这一层次的并行被称为晶核级并行,是因为与内核与核内内存之间的访问,必须有极其快的速度,从工艺上将,只有将内核与核内内存放置在同一晶核上才能实现,所以将这一层次的并行称为晶核级的并行。
      GPU正是使用类似的方式来实现极高的并行度,达到大大超越CPU的运算能力。从上述对两款最新GPU的表述中,可以发现AMD的芯片结构,其核内并行、核间并行层次清晰,更有利于科学并行计算。

      由此,可以看出,要提高晶核级核间指令级并行,需要编写多线程程序,利用芯片的超线程、同一晶核内的多核,能够同时运行多个线程的能力,并行执行多个线程。
      这就需要改变并行程序的编写习惯。在细粒度上编写多线程程序。如将每一个CMT内核所运行的进程,按照输入、合法性判断、计算、输出等不同功能,分别编制线程;这些线程形成实际上的流水线,将各自生成的结果交由队列管理,并由下一线程处理。不同的线程使用共同的核内内存,可以高效的并行执行。

    三:芯片与并行操作系统的定制
      GPU之所以能够提供如此强大的并行计算能力,与其所使用的“并行操作系统”——DirectX有着密不可分的关系。

    1:硬件设备无关性
      微软不仅开发了DirectX标准平台,并且根据硬件制造厂商和游戏厂商合作共同更新升级DirectX的标准。硬件制造商按照此标准研发制造更好的产品,游戏开发者根据这套标准开发游戏。也就是说,无论硬件是否支持某种特效,只要DirectX标准中有,游戏开发者就可以把它写到游戏中,当这个游戏在硬件上运行,如果此硬件根据DirectX标准把这个效果做到了此硬件驱动程序中,驱动程序驾驭其硬件算出结果,用户就可以欣赏到此效果。这就是“硬件设备无关性”,是DirectX真正意义所在。
      这句话换一下几个名词,就成了。应当提供并行硬件抽象层(PHAL/Parallel Hardware Abstraction Layer),硬件制造商按照此标准研发制造更好的并行芯片、并行计算机,并行软件开发者根据这套标准开发并行程序。也就是说,无论硬件是否支持功能,只要PHAL标准中有,程序开发者就可以把它写到程序中,当这个并行程序在硬件上运行,如果此硬件根据PHAL标准把这个功能做到了此硬件驱动程序中,驱动程序驾驭其硬件实行并行计算,用户就可以享受到并行的优势。这就是“硬件设备无关性”,是PHAL真正意义所在。

      当并行计算还是大型计算机的专属时,开发这样的PHAL属于得不偿失,但是当并行计算已经进入桌面,可以为几乎所有的应用程序提供服务的时候。把并行处理交给PHAL,就可以解放并行程序的开发人员,使其将精力集中到应用程序本身的算法,而不是如何并行上。
    当图形加速卡刚出现时,是需要应用程序直接操纵硬件来取得加速性能的。而诸如DirectX、OpenGL等图形API接口,也是到了一个开发瓶颈阶段才出现,并逐渐被游戏开发人员所采用。
    到DirectX7.0为止,DirectX的工作主要是逐步实现图形卡已有的功能,并提供API以简化开发。而从8.0开始,DirectX已经领先于图形卡的设计,每一个版本的DirectX都对应了新的一代显示核心,标准的定义已经超前于实现。
      目前正是并行计算刚刚进入桌面系统的时代,目前的并行能力都需要应用程序来实现。而PHAL将逐步简化这一过程,并最终成为引领并行计算机结构发展的源动力。

    2:并行操作系统、并行编译系统的结合
      DirectX内含的Shader Model提供了对GPU中流处理器的编程控制。在编程中,需要为每一个顶点(Vertex)或象素(Pixel)编制对应的Shader,该Shader负责对这一对象的显示。在最新的DirectX10所定义的Shader Model 4.0中最大指令数从512条增加到了64k条;临时暂存器数量也从原先的32个增加到惊人的4096个;允许同时对128个纹理(Texture)进行操作,对于纹理的尺寸Shader Model4.0也有惊人的提升,8192x8192的最高纹理分辩率比原先最高2048x2048的分辩率要高出4倍。
      从计算机结构的角度讲,上述内容的含义就是:每一个对象有其所对应的线程负责显示,每个活动线程所使用的代码cache为64k;数据cache为64k(每个寄存器存放4维向量,每维32bit);L2 cache由于受到纹理压缩比的影响,不容易计算。这些数以万计的这些线程,在运行时,在GPU内部被硬件调度,实现高度的并行。
      这些参数,既是DirectX技术标准的定义,也是各种支持DirectX10图形处理器的实际配置。
      所以说DirectX决不仅仅是一组API,还提供了并行程序编写语言及其编译器,并同硬件一同实现并行操作系统。

      综上所述,如果能够实现PHAL,那么PHAL也必定是并行编译系统与并行操作系统的结合。只有这样才能编写出“细粒度”的线程,以满足晶核级并行的要求。

    四:结束语
      整篇文章主要写了为了提高指令级并行,在未来软硬件所可能的发展方向。
      本来是想把后面的循环级、过程级、子程序级、作业级写个遍的,但是时间有限。
      以一己之力来推断未来并行技术(主要指桌面级计算机的并行技术)的发展,自然谬误不断。但从逻辑上,本文所述的各种技术都合理可行。但是否能够真正实施,需要时间和实践的检验。本人所准备编写的“推箱子的并行算法”正是对这些推断的一点小小证明。
      现在看本文,也许嗤之以鼻;十年后看本文,也许一笑了之。
      下面再写一些本人的武断,要把这些东西全部说清,或许还要十倍的篇幅。

    结论:
    1:CPU的结构向着类DSM发展
    2:核内缓存的数量增加——cache块表过大——成为核内内存——其区别在于,可以由人工直接填写数据,而没有映射。
    3:并行科学计算的编程,成为细粒度的多线程编程。PHAL的出现,使线程的分配变的简单。
    4:CPU的制造,可以定制,根据不同需求,可以配备不同的特定部件。
    5:一个过程从宏观上看,就是一条超长的指令。所以过程级并行是宏观的指令级并行。其主要由刀片机内多PCB板间并行来实现。
    6:类DSM结构的CPU组成的机群,是并行计算机发展的方向。
    7:并行程序的设计语言必须有全新的关键字来进行定义。对不同内存的读写,有不同的指令。
    8:不同级别的并行度,是由不同手段的并行解决方法。

    展开全文
  • 一、循环并行性 在主要的程序结构中,循环结构一般是比较耗时的部分。如果可以并行执行循环,那么可以很大程度上提高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
    指令级并行流水线提高的是指令带宽(吞吐率),而不是单条指令的执行速度相关限制了流水线性能的发挥 结构相关:需要更多的硬件资源 数据相关:需要定向,编译器调度 控制相关:尽早检测条件,计算目标地址,延迟...
  • 3. 循环级并行 4. 循环展开 5. 数据流 把握要点: 6. 流水线处理的实际CPI和基本程序宽度该奶奶 7. 循环级并行和基本的开发技术 8. 相关与流水线冲突以及解决方法、程序顺序 9. 数据流和异常行为,这里需注意使用...
  • 由于指令可以并行执行,所以指令之间可能实现的这种重叠称为指令级并行(ILP)。 ILP大体有两种不同开发方法 1) 依靠硬件来帮助动态发现和开发并行 2) 依靠软件技术在编译时静态发现并行 基本块:一段顺序执行代码...
  • 开发计算机并行性的方法【理论】

    千次阅读 2016-08-30 15:48:21
    并行性主要是指同时性或并发性,并行处理是指对一种相对于串行处理的处理方式,它着重开发计算过程中存在的并发事件。 并行处理(Parallel Processing)是计算机系统中能同时执行两个或更多个处理的一种计算方法。...
  • 什么是指令级并行(ILP),以及开发ILP的两种途径 ILP:当指令中不存在相关时,它们在流水线上是可以重叠执行的,我们重叠执行指令以提高性能。而这种指令序列存在的潜在并行性称为指令级并行。 ...
  • convoy - 护航指令组,一组可以一直执行的向量指令,不包含任何结构冒险 条带挖掘(strip mining) 一种生成代码的技术,使每个向量运算都是针对小于或等于MVL的大小来完成的。即将向量分段,第一段长度为n%MVL,...
  • 关于并行

    千次阅读 2015-07-05 17:13:33
    所谓并行性(parallelism)是指计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠,就存在并行性。它包括同时性与并发性。 同时性(simultaneity):两个或以上的事件在同一时刻发生。 ...
  • Matlab并行运算

    千次阅读 2014-06-06 17:14:31
    今天搞了一下matlab的并行计算,效果好的出乎我的意料。 本来CPU就是双核,不过以前一直注重算法,没注意并行计算的问题。今天为了在8核的dell服务器上跑程序才专门看了一下。本身写的程序就很容易实现并行化,因为...
  • 今日头条当前后端服务超过80%的流量是跑在 Go 构建的服务上。微服务数量超过100个,高峰 QPS 超过700万,日处理请求量超过3000亿,是业内最大规模的 Go ...Python 的解释语言特性以及其落后的多进程服务模型受到了...
  • 并发编程系列之线程并行学习笔记

    千次阅读 2018-12-15 23:36:54
    一、线程并行相关概念 同步(Synchronous)和异步(Asynchronous) 同步和异步的本质区别是是否需要等待,比如一个方法在执行,必须等前面一个方法程执行完成,才可以执行,这就是同步。如果不需要等上一个方法执行...
  • 本文介绍了图计算中的核心概念与算法,了解这些基本知识可以帮助我们更好更快的探索一个图,找到相应的解决方案,同时也是更深层次研究的基础。
  • 模型并行( **model parallelism** ):分布式系统中的不同机器(GPU/CPU等)负责网络模型的不同部分 —— 例如,神经网络模型的不同网络层被分配到不同的机器,或者同一层内部的不同参数被分配到不同机器;...
  • 并行计算及并行算法

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

    千次阅读 多人点赞 2015-07-28 00:14:58
    汇编语言应该是我们现在学的最“低级”的语言了,因为现在不会再有人去学机器语言了。而汇编语言还在一些硬件或者嵌入式...字长word是指微处理器内部一次可以并行处理二进制代码的位数,它与微处理器内部寄存器以及CP
  • 什么是并行计算?

    千次阅读 2020-01-15 14:26:19
    最近项目需要实现程序的并行化,刚好借着翻译这篇帖子的机会,了解和熟悉并行计算的基本概念和程序设计。帖子的原文见这里。 这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的...
  • [并行计算] 1. 并行计算简介

    万次阅读 多人点赞 2017-07-20 15:30:07
    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。
  • 程序正确证明与并行程序设计

    千次阅读 2011-11-12 21:18:58
    程序正确证明与并行程序设计 (2011-08-20 20:27:59) 标签: 校园 分类: 工作篇 理论计算机科学   关于计算和计算机械的数学理论,也称为计算理论或计算机科学的数学基础。理论...
  • 并行计算期末复习

    2020-08-31 16:55:24
    文章目录推动并行计算的因素并行计算的应用超算机并行计算软件技术面临的挑战并行程序设计的复杂数据移动(通信)代价很高能耗挑战伸缩挑战软件生态环境几乎停滞Cache相关工作原理及概念冯诺伊曼结构Cache 高速...
  • 目录 动态分支预测技术 概念 分支预测的有效取决于 动态分支预测技术的目的 分支预测表 BHT 1个预测位 ...指令调度与循环展开 ...概念 ...循环展开 ...概念 ...循环展开和指令调度的注意事项 ...指令级并行总...
  • 并行计算简介

    千次阅读 2013-07-13 09:07:20
    英文原文地址:https://computing.llnl.gov/tutorials/parallel_comp/ 译文地址:... 目录 1 ...什么是并行计算 ...为什么使用并行计算 ...概念和术语 3.1 冯诺依曼体系结构
  • 并行计算模型

    千次阅读 2019-06-21 17:09:42
    并行计算指的在同一时刻存在多于一个计算任务被执行。由于CPU主频提高的上限,使用多核心处理器进行并行计算早已成为主流。GPU也是一个多核心的处理器,但它的并行计算模型与多核的CPU有很大区別。我们有必要了解GPU...
  • 文章目录2.7 常见的并行模式2.7.1 基于循环的模式循环的迭代依赖是指循环的一次迭代依赖于之前的一次或多次先前迭代的结果。基于循环的迭代是实现并行化的模式中最容易的一个。对问题的分解 依据可用的逻辑处理单元...
  • 深度学习和并行化实现

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

    千次阅读 2018-02-08 21:25:50
    深度学习及并行化实现概述摘要: 深度学习可以完成需要高度抽象特征的人工智能任务,如语音识别、图像识别和检索、自然语言理解等。深层模型是包含多个隐藏层的人工神经网络,多层非线性结构使其具备强大的特征表达...
  • 并行计算框架

    万次阅读 2018-03-25 11:59:41
    概念 框架与引擎 批处理框架 流处理框架 混合处理框架 MapReduce Hadoop 基本处理过程 优势和局限 Spark Spark的批处理模式 Spark的流处理模式 优势和局限 总结 MPI MPI的优点 MPI的缺点 OpenMP CUDA Cpu与...
  • 强化学习的并行加速

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,395
精华内容 17,358
热门标签
关键字:

循环级并行性概念