精华内容
下载资源
问答
  • 循环优化的三种重要技术包括
    千次阅读
    2014-01-13 11:53:27

    C语言常规优化策略


    3 循环优化


    提高程序效率的核心是对影响代码执行速度的关键程序段进行优化。在任何程序中,最影响代码速度的

    往往是循环语句,特别是多层嵌套的循环语句。因此,掌握循环优化的各种实用技术是提高程序效率的

    利器,也是一个高水平程序必须具备的基本功。
    本节有关各种循环优化技术的讨论基本上以下面的一个程序段为对象,程序的涵义为:对于两个给定的

    数组a、b,计算a[8]b[8]+a[12]b[12]+...+a[84]b[84]的值。原始的代码为:
    // 版本0
    prod=0;
    i=1;
    while (i<=20)
    {
     x=*(a+4*i+4);
     y=*(b+4*i+4);
     z=x*y;
     prod+=z;
     i++;
    }
    常用的循环优化技术包括代码外提、删除冗余运算、强度削弱、变换循环控制条件、合并已知量以及删

    除无用赋值等。下面我们围绕这一例子来介绍这些内容。

    3.1 代码外提


    代码外提是指将循环体中与循环变量无关的运算提出,并将其放到循环之外,以避免每次循环过程中的

    重复操作。
    在原始代码中,计算x、y的值时,重复使用到a+4, b+4操作,由于它们与循环变量i无关,可以放到循环

    之外一次执行完成:
    // 版本1
    prod=0;
    i=1;
    a1=a+4;
    b1=b+4;
    while (i<=20)
    {
     x=*(a1+4*i);
     y=*(b1+4*i);
     z=x*y;
     prod+=z;
     i++;
    }

    3.2 删除冗余运算


    在版本1中,循环体内执行了两次4*i的操作,通过引入中间变量保留这一结果,可以删除冗余计算。
    // 版本2
    prod=0;
    i=1;
    a1=a+4;
    b1=b+4;
    while (i<=20)
    {
     j=4*i;
     x=*(a1+j);
     y=*(b1+j);
     z=x*y;
     prod+=z;
     i++;
    }


    3.3 强度削弱与合并已知量

    版本2还有进一步优化的必要,其中4*i这一乘法操作可根据问题的特点改换成加法操作。因为在两次相

    邻的循环执行过程中,i的值相差4,为一个常数,因此可将j=4*i改换成j+=4,j的初值在循环外设置成

    j=4*(i-1)。这一步称为强度削弱。在本例子中,由于i的初值为1,数j的初值为0,这一步称为合并已知

    量。
    // 版本3
    prod=0;
    i=1;
    j=0;
    a1=a+4;
    b1=b+4;
    while (i<=20)
    {
     j+=4;
     x=*(a1+j);
     y=*(b1+j);
     z=x*y;
     prod+=z;
     i++;
    }

    3.4 变换循环控制条件

    从版本3可以看到,循环变量i在循环体中除自身引用外,已不起任何作用,因此,可以将i从循环中删去

    ,其控制作用交给变量j来完成,由于在每次进入循环时,i、j之间总是保持关系j=4(i-1),从而可将循

    环条件所改成j<=76。
    // 版本4
    prod=0;
    j=0;
    a1=a+4;
    b1=b+4;
    while (j<=76)
    {
     j+=4;
     x=*(a1+j);
     y=*(b1+j);
     z=x*y;
     prod+=z;
    }
    在这一最后的版本中,除了变换循环控制条件外,还将有关i的无用赋值从循环内外全部驱除出去了。下

    表列出了原始版本和最终版本在循环体内一些基本操作的差异:
      加法次数 乘法次数 赋值次数
    原始版本 6  3  3
    最终版本 4  1  3
    其中,”+=“及”++”均算作一次加法。由此可见最终版本的效率约为原始版本的2倍。

    3.5 循环优化的其它措施

    循环优化是一个非常古老的话题,从第一个计算机程序诞生至今,一代一代的程序员已经积类起很多循

    环优化的知识。例如,有一种称之为循环展开的方法在50,60年代非常流行,至今虽然一般程序员已不常

    采用,但在一些特别追求效率的领域,如游戏程序编制,计算机动画等,还能找到这一方法的一丝踪迹

    。循环展开的思想非常简单,如我们要计算一个数组前20项之和,通常的程序为:
    s=0;
    for (i=0; i<20;i++)
     s+=a[i];
    采用最极端的循环展开法,上述程序可以写成:
    s=a[0]+a[1]+...+a[19]
    当然在程序中是不允许出现省略号的,这里我们只是一种示意性说明。很显然,根端的循环展开法在大

    部分情况下是不可取的,例如,要计算数组前100项的和,我们决不会愚蠢到在程序中写出100数相加的

    复杂表达式,即使你有时间和耐心去完成这项乏味的工作,大部分的编译程序都会对此提出警告,或者

    在执行优化的过程中建议对表达式进行简化。一种变通的方式为: 仅在循环中展开几步,但仍保留循环

    结构:
    s=0;
    for (i=0; i<20;)
    {
     s+=a[i++];
     s+=a[i++];
     s+=a[i++];
     s+=a[i++];
    }
    据说,将循环展开2~7步可以提高程序效率达10%~20%。即便如此,除非无路可走,我是决不会采纳这

    种措施的。
    在循环优化的诸多措施中,最有效的措施要数强度削弱了,只有强度削弱才是改善循环效率的关键,作

    为一个例子,大家可以对前面给出的中点线算法进行优化,将循环内的乘法全改为加法来完成。对于本

    节给出的例子和中点线算法,循环中的乘法都是与循环变量线性相关的,对于非线性相关的情况,也能

    够经过多次强度削弱,从而将乘法改变成加法。下面的例子是要计算前n个整数的平方和,我们来看看循

    环变量的平方是怎样由加法来完成的。
    S=0;
    for (i=1; i<=n; i++)
     S+=i*i;
    首先,两次连续的循环中i相差1,从而(i+)*(i+1)与i*i相差2*i+1,因此,上面的程序可以改进为:
    S=0;
    j=0;
    for (i=1; i<=n; i++)
    {
     j=2*i+1;
     S+=j;
    }
    线性乘法又可以进一步改进为加法:
    S=0;
    j=0;
    k=-1;
    for (i=1; i<=n; i++)
    {
     k+=2;
     j+=k;
     S+=j;
    }
    当然还可以对上面的循环变量进行交换以进一步提高效率。
    有关循环优化的最后一个课题是关于多重循环的组织问题。多重循环是需要加以有效地组织的,这可能

    与我们通常的理解相反,比知说,我们要旋转一幅图象,一个典型的二重循环可以完成这一任务:
    // ImageSre,lmageDst分别为原图象与目标图象
    // cosV,sinV分别旋转角的余、正弦值
    for (x=0; x<W; x++)  // W,H分别为原图象宽度和高度
     for (y=0; y<H; y++)
     {
      GetPixel(ImageSrc, x, y, color); // 取原图象一象素
      x’=x*cosV-y*sinV+x0;
      y’=x*sinV+y*cosV+y0;
      PutPixel(ImageDst, x’, y’, color);  // 置图象目标一象素
     }
    这一程序可进行多方面的优化,但无论怎样改造,上面的程序总存在一个先天的不足:数据的处理次序

    与存贮次序不一致,一幅图象,或者直观地说一个二维数组,在内存中总是逐行存放的,而在上面的处

    理中却是逐列进行的,这会有什么问题呢?首先,两者之间的不一致会导致程序在许多方面优化不下去,

    例如,我们可设计一个指针指向原图象的某一象素,要取下一象素时,只需将指针加1即可,而且,从第

    一个象素至最后一个象素都能按这一方式统一处理,而如果逐列处理,当前处理的象素与下一象素位置

    上相差太远,有时还需要跳来跳去,象素指针的这种统一位移关系就会被破坏,造成处理的低效;其次

    还有一个更严重、更隐蔽的问题。如果要处理的图象太大,在内存中不能一次放入,这就需要在内存与

    文件之间往复交换数据,当处理次序与存放次序不一致时,数据将会频繁地在内外存之间倒换,从而产

    生抖动现象,即系统忙于为程序的正常运行准备内存空间而不停顿地交换内外存数据,反而使得程序无

    法正常运行下去。如果我们在Windows上设计出一个产生抖动的程序,就会看到硬盘指示灯不断闪烁。如

    果出现这种情况,就要对你的程序仔细检查,看是否有抖动的情况存在。
     

    更多相关内容
  • 编译优化之 - 通用循环优化

    千次阅读 2020-09-11 21:58:13
    循环的优化分为源码上的修改和编译器的优化,编译器能自动执行许多循环优化技术,但对源代码的修改可辅助编译器就行优化处理。 1. 源码上的优化 1. 多重循环的“外小内大”   在多重循环中,采用迭代次数较小的...

    前言

      循环是程序中最常见结构,针对循环已有众多的优化技术。循环的优化分为源码上的修改和编译器的优化,编译器能自动执行许多循环优化技术,但对源代码的修改可辅助编译器就行优化处理。

    1. 源码上的优化

    1. 多重循环的“外小内大”

      在多重循环中,采用迭代次数较小的循环驱动内层迭代次数较大的循环能减少内存的消耗,如下示例:

    for (int i = 0; i < 10000; i++) {
        for (int j = 0; j < 200; j++) {
    
        }
    }
    改为:
    for (int i = 0; i <200 ; i++) {
        for (int j = 0; j < 10000; j++) {
    
        }
    }
    
    2. 循环变量实例化放在循环外

    如下示例:

    int i,j;
    for (i = 0; i <200 ; i++) {
        for (j = 0; j < 10000; j++) {
    
        }
    }
    
    3. 循环无关的表达式放到循环外

    如下示例:

    int i,j;
    for (i = 0; i <200 ; i++) {
        for (j = 0; j < 10000; j++) {
              j = i*j*x/(y-1);
        }
    }
    改为:
    int i,j,tmp;
    tmp = x/(y-1);
    for (i = 0; i <200 ; i++) {
        for (j = 0; j < 10000; j++) {
              j = i*j*tmp;
        }
    }
    
    4. 消除循环终止时的方法调用

    如下示例:

    for (int i = 0; i < vec.size(); i++) {
    
    }
    改为:
    int size = vec.size();
    for (int i = 0; i < size; i++) {
    
    }
    
    5. 循环外部捕获异常

      在循环外部捕获异常能有效减少内层消耗。一般而言,foreach 循环优先于传统的 for 循环。

    6. 循环的 i++ 改为 ++i

      效率上来说++i 比 i++来的更有效率(后置操作符必须先保存操作数原来的值),但现代编译器上这个影响会很小。


    2. 编译器角度的优化

    1. 循环展开(loop Unrolling)

      重组循环,以便每次迭代多次使用加载的值,让一拍流水线上尽可能满。在流水线中,会因为指令顺序安排不合理而导致CPU等待空转,影响流水线效率。循环展开为编译器进行指令调度带来了更大的空间。
    如下示例:

    do j = 1,2*n
        do i = 1,m
            A(j) = A(j) + B(i)
        enddo
    enddo
    
    Unrolling之后:
    do j = 1,2*n by 2
        do i = 1,m
            A(j) = A(j) + B(i)
            A(j+1) = A(j+1) + B(i)
        enddo
    enddo
    
    2. 循环分块(loop tiling)

      由于内存空间有限,代码访问的数据量过大时,无法一次性将所需要的数据加载到设备内存,循环分块能有效提高处理器 cache 上的访存效率,改善数据局部性。(分块应用于外部循环,它会增加计算的空间和时间局部性;分块应与缓存块一起使用,因为这样可以提高最内部软件流水线的效率)。示意如图:
    loop1

    如下示例:

    do j = 1,2*n
        do i = 1,m
            A(j)= A(j) + B(i)
        enddo
    enddo
    
    Tiling之后:
    do jj = 1,2*n by 2
        do i = 1,m
            do j = jj, jj+2-1
                A(j)= A(j)+B(i)
            enddo
        enddo
    enddo
    
    Unroll and Jam之后:
    do jj = 1,2*n by 2
        do i = 1,m
            A(j)= A(j)+B(i)
            A(j+1)= A(j+1)+B(i)
        enddo
    enddo
    

    更多关于 loop tiling 的优化方法可参见论文:《Augmenting Loop Tiling with data Alignment for Improved Cache Performance》《Automatic Tiling of Iterative Stencil Loops》《面向局部性和并行优化的循环分块技术》

    3. 循环交换(loop interchange)

      内外层循环交换,改善空间局部性,并最大限度地利用引入缓存的数据。对循环进行重新排序,以最大程度地减少跨步并将访问模式与内存中的数据存储模式对齐。
    如下示例:

    do i=1,n
        do j=1,n
            A(i,j)=B(i,j)*C(i,j)
        enddo
    enddo
    
    interchange之后:
    do j=1,n
        do i=1,n
            A(i,j)=B(i,j)*C(i,j)
        enddo
    enddo
    
    4. 循环融合(loop fusion)

      将相邻或紧密间隔的循环融合在一起,减少的循环开销和增加的计算密度可改善软件流水线,数据结构的缓存局部性增加,编译器在某些情况下未执行融合,需要手动完成。
    如下示例:

    for(i = 0; i < size; ++i){
        A(i) = a(i) + b(i);
        c(i) = 2*a(i);
    }
    for(i = 1; i < size-1; ++i){
        D(i) = c(i) + a(i);
    }
    
    fusion之后:
    A(0) = a(0) + b(0);
    c(0) = 2*a(0);
    A(size-1) = a(size-1) + b(size-1);
    c(size-1) = 2*a(size-1);
    for(i = 1; i < size-1; ++i){
        A(i) = a(i) + b(i);
        c(i) = 2*a(i);
        D(i) = c(i) + a(i);
    }
    
    5. 循环分裂(loop fission)

      将循环分成多个循环,可以在有条件的循环中使用,分为无条件循环和含条件循环。
    如下示例:

    for(i = 0; i < size; ++i){
        A(i) = a(i) + b(i);
        c(i) = 2*a(i);
        if(temp[i] > data)
            d(i) = a(i);
    }
    
    fission之后:
    for(i = 0; i < size; ++i){
        A(i) = a(i) + b(i);
        c(i) = 2*a(i);
    }
    for(i = 0; i < size; ++i){
        if(temp[i] > data)
            d(i) = a(i);
    }
    
    6. 循环剥离(loop peeling)

      剥离 k 次迭代意味着从循环主体中删除这些迭代并将其放置在循环主体之前或之后。
    如下示例:

    do i=1,n
        Y(i,n) = (1.0 - x(i,1))*y(1,n) + x(i,1)*y(n,n)
    enddo
    
    peeling之后:
    t2 = y(n,n)
    t1 = y(1,n)
    y(1,n) = (1.0 - x(1,1))*t1 + x(1,1)*t2
    do i=2,n-1
        Y(i,n) = (1.0 - x(i,1))*t1 + x(i,1)*t2
    enddo
    y(n,n) = (1.0 - x(n,1))*t1 + x(n,1)*t2
    
    7. 循环强度减弱(Strength reduction in loops)

      使用简单的表达式来替换复杂的表达式。
    例如,除法替换,如下示例:

    z(i) = x(i)/y(i)
    w(i) = u(i)/v(i)
    
    Strength reduction之后:
    tmp = 1.0/(y(i)*v(i))
    z(i) = x(i)*v(i)*tmp
    w(i) = u(i)*y(i)*tmp
    

    References:

    • https://blog.csdn.net/qq_37436998/article/details/100055770
    • https://www.cs.colostate.edu/~mstrout/CS553Fall07/Slides/lecture27-tiling.pdf
    • http://users.cecs.anu.edu.au/~Alistair.Rendell/sc02/module2b.pdf
    展开全文
  • TI C6000 优化进阶:循环重要

    千次阅读 2017-02-03 10:22:04
    本文集中介绍 TI C6000 DSP架构下的循环优化,文中涉及的C6000基础概念可参考TI官方手册及本公众号以往技术文章。


    软件流水循环

    1. C6000流水线(Pipeline)

    一个指令的处理过程并不是一步完成,它被分为三个阶段:取指(Fetch)、译码(Decode)、执行(Excute)。将每一个阶段放入独立的流程车间处理,形成流水线式的处理过程,可以大大加快指令的处理速度。


    如图1所示,流水编排后的3个指令只需5个cycle,相比顺序执行的9个cycle大大减少,当指令数增多,流水线的优势将更加明显。


    图1 简单的流水线编排示意


    实际上,C6000架构把每一个阶段进一步划分为多个子阶段,每个子阶段消耗1个CPU cycle。

    取指(4个子阶段):

    • PG: Program address generate (update program counter register)

    • PS: Program address send (to memory)

    • PW: Program (memory) access ready wait

    • PR: Program fetch packet receive (fetch packet = eight 32-bit instructions)

    译码(2个子阶段):

    • DP: Instruction dispatch (or assign, to the functional units)

    • DC: Instruction decode

    执行(1-10个子阶段,指令间有区别):

    • E1 – E10, where E1 is the first sub stage in the execute stage



    图2 高性能的C6000流水线


    2. 流水线阻塞

    下列两种情况出现时,流水线将被阻塞:

    • 当前为load、complex multiply等具有多个延时时隙(delay slot)的指令时,下一指令需多个cycle,等其返回结果后才能往下继续执行

    • 跳转指令出现时,CPU无法预知下一步执行哪个分支指令,因此跳转目标指令需等到跳转指令执行到E1阶段才能进入流水线


    为了充分利用流水线的资源,避免delay slots造成的阻塞,C6000架构在软件和硬件上分别新增了一个处理机制

    • 软件上:提供软件流水(software pipelining)指令编排

    • 硬件上:提供SPLOOP buffer(software pipelining loop buffer)


    3. 软件流水

    软件流水≠流水线!

    软件流水技术指编译器通过重新调整指令的位置,使得原本将发生阻塞的流水线得以充分利用,其重点在“软件”两字。


    例如处理下面循环:

    for(i=0; i<15; i++)

    {

    sum += tab[i];

    }

    传统指令流程(Solution1)和软件流水编排后的指令流程(Solution2)如图3所示:


    图3 传统编排 Vs 软件流水编排


    从图中看到,经过软件重新编排过的指令将不再发生流水线阻塞,提升运行效率的同时也不影响代码功能的实现


    解释下有关软件流水的三个名词:

    • 流水核(Kernel):流水线被充分利用的一段代码

    • 流水填充(Prolog):流水核之前的一段填充过程代码

    • 流水排空(Epilog):流水核之后的一段排空过程代码


    4. SPLOOP Buffer

    软件流水将会带来两个主要的缺点:汇编文件代码尺寸的增加并影响代码的中断属性。


    SPLOOP Buffer的出现就是为了就解决以上问题。SPLOOP Buffer是C6000内部的一个存储区域,用来装载SPLOOP指令。当一个SPLOOP 第一次被执行时,循环的相关指令被拷贝到SPLOOP Buffer中,整个循环运行过程将从这里取指执行,直到循环结束。


    C6000还为SPLOOP Buffer的使用提供了专门的寄存器和操作指令,如果编程者使用汇编/线性汇编编程,需要熟悉这些指令和寄存器,并了解SPLOOP Buffer特有的执行机制(参考文献[1]),如果使用C/C++编程则由编译器自动生成相应指令。


    以存储块拷贝函数为例,示意使用SPLOOP Buffer前后的编码效果:


    图4 memery copy 使用SPLOOP buffer前



    图5 memery copy 使用SPLOOP buffer后


    *注意:SPLOOP Buffer最多只能存放14个执行包(每个执行包可含8条指令,顺序/并行),因此如果循环体较复杂将不能使用SPLOOP Buffer。


    5. 导致软件流水编排失败的因素

    在CCS开发环境中,开启-O2/-O3优化选项,编译器将自动为合适的代码进行软件流水编排,因此编程者需要注意的是使设计的循环体符合软件流水编排的条件。


    下列一些因素将可能引起软件流水编排失败:

    • 汇编语句嵌入到C/C++代码中

    • 出现复杂的流控制语句如goto、break等

    • 循环中包含一个调用(内嵌函数除外)

    • 需进行软件流水编排的指令太多

    • 没有初始化循环计数器

    • 循环变量在循环过程中被修改

    • 软件流水被关闭:没有使用-O2或-O3选项;使用了-ms2或-ms3选项;使用-mu关闭了软件流水



    理解编译器反馈信息

    1. 编译器优化循环的几个步骤

    循环的运算性能主要取决于编译器能否编排出恰当的软件流水,编译器优化一个循环的过程大致分为三个步骤:


    获取循环次数信息。这些信息能帮助编译器判断是否要对循环做自动展开等操作。有时编译器无法从代码中获得完整的这些信息,编译器将会对循环采取保守的优化策略。因此,若要获得最佳的优化性能,编程者应尽可能地提供这些信息给编译器,可通过 MUST_ITERATE 、UNROLL 等 pragma语句。

    几个关键参数如下:

    • 最小可能循环次数(Minimum Trip Count)

    • 最大可能循环次数(Maximum Trip Count)

    • 循环倍数系数(Max Trip Count Factor)


    收集循环资源和相关图信息。CPU完成一次循环迭代所需的cycle数称为迭代间隔(iteration interval,ii),编译器的优化目标就是最小化ii。

    几个关键参数如下:

    • 循环执行相关限(Loop Carried Dependency Bound),指循环体中最大的一条依赖路径的距离,而所谓依赖是指当前指令的开始依赖于前面指令的结束。

    以下面一段代码为例:

    void simple_sum(short *sum, short *in1, unsigned int N)

    {

    int i;

    for (i = 0; i < N; i++)

    {

    sum[i] = in1[i] + 1;

    }

    }

    其中最大的依赖路径如下图所示,图中显示,下一次数据的加载需等待上一次数据存储完成。


    图6 循环依赖路径


    很多时候,循环执行相关限是由于编译器对某些指针变量的信息缺乏了解造成,当指针的确切值无法得知时,编译器必须假定任何两个指针都可能指向相同的位置。因此,从一个指针进行加载暗含了其与另一个指针执行存储操作的相关,反之亦然。类似这种相关通常是不必要的,编程者可通过添加“restrict”关键词来消除这种相关。


    • 未分配资源限(Unpartitioned Resource Bound):编译器将每条指令分配到A、B运算单元之前,使ii达到最小情况下的资源限。

    • 已分配资源限(Partitioned Resource Bound):编译器将每条指令分配到A、B运算单元之后,使ii达到最小情况下的资源限。


    寻找软件流水编排策略。编译器首先将ii设为Loop Carried Dependency Bound和Partitioned Resource Bound两个指标中的大值,然后以它为目标寻找编排策略。如果失败,则将ii+1,继续寻找……期间编译器将会反馈出编排失败的原因和一些相关信息。


    2. 编译反馈输出相关选项

    编程者可以选择查看上述编译器反馈的一些编译信息,来了解代码的优化程度,进而相应调整代码结构。如果要获得反馈输出,需打开-k和-mw选项。

    • -k:保留编译输出的汇编文件

    • -mw:生成详细的软件流水报告


    一个反馈信息的例子如下所示:


    图7 编译器反馈信息示例


    3. 依据反馈信息制定优化策略

    Loop Carried Dependency Bound is Much Larger Than Unpartitioned Resource Bound

    现象描述:循环执行相关限远大于未分配资源限。

    分析:相关路径过长,可能存在潜在的存储器别名混淆问题。

    解决方案:

    • 运用-pm程序及优化减少存储器指针别名

    • 对传入函数且没有存储重叠的指针参数加“restrict”

    • 运用-mt选项假定没有存储器别名问题

    • 使用.mdep和.no_mdep汇编优化指令

    • 如果循环控制复杂,尝试用-mh选项


    Uneven Resources

    现象描述:对某一运算单元的使用次数为奇数。

    分析:如一次循环过程调用了3次乘法,那么分配到A、B两侧后,执行这个循环至少需要2个迭代间隔。如果能将该循环展开一倍,则循环一次需6次乘法,分配到A、B两侧后得到一个3周期的ii,从而改善循环性能。

    解决方案:展开循环从而得到偶数个资源。


    Larger Outer Loop Overhead in Nested Loop

    现象描述:存在循环嵌套时,外循环所用时间占整个循环时间的比重很大。

    分析:内循环计数值较小,而编译器将只重点优化内循环。

    解决方案:展开内层循环,使嵌套结构变为一个大循环。


    T Address Paths Are Resource Bound

    现象描述:T地址通道数定义为每次循环迭代从地址总线发出的存储器访问次数,该资源的访问对循环进行有限制。

    分析:应减少对T地址通道的访问次数。

    解决方案:用宽字节存取指令访问存储器。



    冗余循环

    1. 什么是冗余循环?

    为了填充流水线,软件流水循环结构需要循环迭代至少执行某个次数(循环次数要达到最小循环计数值)。当编译器无法确定循环计数时,默认会产生两个循环:一是不经流水编排的代码,二是循环流水编排的。运行时,若循环计数大于等于最小循环计数值,执行第2个循环,否则执行第1个。因此,总有一个循环不被执行,这个循环就是冗余循环。


    冗余循环的出现将引起代码尺寸的增加。


    2. 如何避免生成冗余循环

    • 设置-ms选项的任一级别都将关闭冗余循环的生成

    • 使用MUST_ITERATE pragma伪指令告诉编译器循环次数的具体信息



    中断对循环的影响

    1. 单分配和多分配

    C6000中的寄存器分配被分为单分配和多分配。单分配代码是可中断的,多分配代码是不可中断的。


    多分配是指某一特殊寄存器被分配多于一个值。如下为一段多分配的代码。

    cycle

    1    SUB .S1 A4,A5,A1 ; writes to A1 in single cycle

    2    LDW .D1 *A0,A1 ; writes to A1 after 4 delay slots

    3    NOP

    4    ADD .L1 A1,A2,A3 ; uses old A1 (result of SUB)

    5−6  NOP 2

    7    MPY .M1 A1,A4,A5 ; uses new A1 (result of LDW)

    在第4周期,ADD指令开始时,寄存器被分配两个不同值。一个值是SUB指令在第1周期所写,已经在寄存器中存在。第二个值叫做in-flight值,在第2周期由LDW指令分配。因为LDW指令在第6周期之前没有实际值写入寄存器A1,所以考虑分配为in-flight。


    in-flight操作因其不可预见性所以其代码不可中断。


    2. 循环不可被中断的情形

    所有小于6个cycle的循环都是不可中断的。


    即使代码使用单分配,但循环也可能不能使用中断。因为硬件中断保护所有分值操作的延迟间隙,所以只要CPU有悬挂分支,所有中断就保持悬挂。而又因为分支跳转指令有5个延迟时隙,小于6个cycle的循环总有悬挂分支。


    3. 如何设置循环体的中断属性?

    循环的中断属性可设置为三个级别:


    级别0,不可中断

    该级别下编译器不能使中断无效,因此需确保中断不会发生,其优势是允许编译器用多分配代码以及产生最小周期间隔的软件流水循环。

    • -mi选项将某一模块设置为该属性

    • 可用pragma伪指令对某个特殊函数func进行如下设置:

    #pragma FUNC_INTERRUPT_THRESHOLD(func, uint_max);


    级别1,任何时刻可中断

    该级别编译器处处用单分配,绝不产生小于6个cycle的循环。

    • -mi1选项将某一模块设置为该属性

    • 可用pragma伪指令对某个特殊函数func进行如下设置:

    #pragma FUNC_INTERRUPT_THRESHOLD(func, 1);


    级别2,在阈值周期内不可中断

    用户设置一个周期阈值threshold,若循环的cycle数未超过阈值,编译器将在循环周围关中断,并允许寄存器多分配。反之,则产生单分配的代码,循环可中断。如果编译器无法判断循环周期,则假定达到阈值,产生一个可中断循环。

    • -mi(阈值)选项将某一模块设置为该属性

    • 可用pragma伪指令对某个特殊函数func进行如下设置:

    #pragma FUNC_INTERRUPT_THRESHOLD(func, threshold);



    参考文献

    【1】Introduction to TMS320C6000 DSP Optimization--SPRABF2,2011.

    【2】TMS320C6000 Programmer's Guide--SPRU198K,2011.

    【3】田黎育,何佩琨,朱梦宇. TMS320C6000系列DSP编程工具与指南[M].北京:清华大学出版社 2006.




    ·END·


    想进一步跟踪本博客动态,欢迎关注我的个人微信订阅号:信号君


    郑重·专业·有料



    展开全文
  • 软件流水线化也是一种重要的指令调度技术,就像硬件流水线的指令一样,它通过并行执行来自不同循环体的指令来加快循环程序的执行速度, 在前一个循环体未结束前启动下一个新的循环体,来达成循环体时间上的并行性。...

    浙江大学《编译原理》课程报告

    我的GIS/CS学习笔记:https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes
    <一个浙江大学本科生的计算机、地理信息科学知识库 >

    上一篇:
    编译过程中的并行性优化(二):基本块与全局代码调度算法

    软件流水线化

    软件流水线化也是一种重要的指令调度技术,就像硬件流水线的指令一样,它通过并行执行来自不同循环体的指令来加快循环程序的执行速度, 在前一个循环体未结束前启动下一个新的循环体,来达成循环体时间上的并行性。相比于简单的展开循环(在提高性能的同时会导致代码的膨胀),软件流水线提供了一个方便的优化方法,能够在优化资源使用的同时保持代码的简洁。

    对于循环之间没有数据依赖的 do-all 循环,我们可以用一个简单的对比来说明软件流水线同简单循环展开的不同,下图为简单的循环展开:

    在这里插入图片描述

    软件流水线化通过将循环展开调度后中重复的部分进行循环,完成流水线。下图为软件流水线化的结果:

    在这里插入图片描述

    在开始阶段(1-6行)用来填充流水线的指令序列被称为序言;在稳定循环的部分(7-8行)被称为稳定状态;用来排空流水线的指令序列(9-14行)称为尾声

    在软件流水中,相邻循环体的启动时间间隔称为启动间距。在软件流水中再次应用循环展开,使同一时刻可以运行多个循环,可以使软件流水实现分数值的启动间距,同时基于展开的优化技术可以降低程序的资源需求和关键路径的长度。但是,循环展开也会引起代码量增长和寄存器需求增大,代码量的增长会导致缓存的性能变差,寄存器需求的增大则有可能使软件流水失败。因此,软件流水的核心问题之一就是展开因子的确定。

    对于各个迭代之间的存在数据依赖关系的循环,也称 do-access 循环,软件流水线化也可以起到一定的效果:

    在这里插入图片描述

    SIMD

    SIMD 扩展指令允许将原来需要多次装载的内存中地址连续的数据一次性装载到向量寄存器中,通过一条 SIMD 扩展指令实现对 SIMD 向量寄存器中所有数据元素的并行处理;这种执行方式非常适合于处理计算密集、数据相关性少的音视频解码等多媒体程序。

    为了高效利用SIMD扩展部件的特性,需要让编译器分析串行程序中控制流和数据流的特征,识别程序中可以向量执行的部分,将标量语句自动转换为相应的SIMD 向量语句。SIMD 自动向量化编译流程大致可分为3部分,分别是发掘、优化和代码生成:

    • 发掘:识别生成出 SIMD 指令,同时解决控制依赖对发掘的影响。SIMD 扩展部件可在不同的粒度进行识别向量化,包括面向基本块内向量化、面向最内层循环或者循环嵌套的向量化以及面向函数级别的向量化。
    • 优化:首先减小辅助指令的开销,同时考虑数据局部性、寄存器重用等工作。由于部分体系结构的 SIMD 指令只能从内存中存取连续对齐的数据,因此当程序中存在不对齐或不连续内存引用时需要通过移位或者重组等辅助指令才能组成向量。减少辅助指令的数量和提高辅助指令的效率,是增加程序 SIMD 向量化收益的关键问题。
    • 代码生成:考虑平台支持哪些数据类型和向量运算。直接面向特定平台的 SIMD 向量化代码生成存在许多不足,通常分阶段并行编译优化和虚拟向量是解决面向多平台向量化的两个方法。

    我的GIS/CS学习笔记:https://github.com/yunwei37/myClassNotes
    <一个浙大GIS/CS小白的课程学习笔记 >


    展开全文
  • 百钱百鸡问题的多种解法,包含三重循环、二重循环和一重循环,主要侧重于讲解优化重要性。 我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题,该问题叙述如下:鸡翁一,值钱五;鸡母一,...
  • 最近几年,我开始专注于数据库的查询优化,2016年末的一次培训成为契机,我决定出一本书,于是我一边培训,一边梳理书中可写的内容,对要写哪些内容,写到什么深度做了一些定位,当时想的是如果有出版社出版就出版,...
  • 方法:while循环4.内存复制编译器优化取舍分析经验总结: 前言 公司大佬,经常会在群里发送一些认为比较有价值的技术文章, 之前比较忙没空学习整理, 现在准备学习这些文章,一方面提高自己的见识面, 一方便做个...
  • 三种近距离通信技术(WIFI、蓝牙、NFC)
  • 通过有限元分析软件ANSYS中的优化设,计模块,使用ANSYS参数化设计语言建立了在保证电磁力及体积限制条件下,以总损耗最小为目标函数,的维参数化分析模型,多次循环迭代求解后得到了较为优化的系统参数。仿真及实验...
  • 原文地址:《一文看懂循环神经网络-RNN(独特价值+优化算法+实际应用)》 卷积神经网络 - CNN 已经很强大的,为什么还需要RNN? 本文会用通俗易懂的方式来解释 RNN 的独特价值——处理序列数据。同时还会说明 RNN ...
  • 图像算法的工程优化技术

    千次阅读 2016-02-29 21:35:52
    图像算法的工程优化技术当一个很酷的图像算法实现之后,我们希望集成到软件中去,这时将会遇到最大的拦路虎:性能。 可以想像一下,如果美图秀秀做一个美颜效果要转圈圈转个30秒,还会有多少人用呢。 学术界喜欢...
  • 因为在放入新的位置时,HashMap会将Entry对象不断的插入链表的头部。插入头部也主要是为了防止尾部遍历,否则这对key的...如果条件竞争发送了,可能会出现环形链表,之后当我们get(key)操作时,就有可能发生死循环
  • SQL查询优化技巧

    千次阅读 2022-04-23 10:05:16
    查询优化的本质是让数据库优化器为SQL语句选择最佳的执行计划。一般来说,对于在线交易处理(OLTP)系统的数据库,减少...索引是优化查询性能的重要方法,因此我们首先需要了解哪些字段适合创建索引: 基于经常出现在
  • 网站性能优化的10方法

    千次阅读 2021-07-29 17:59:45
    对于拥有较大浏览量的首页来说,有一种技术可以平衡内置代码带来的HTTP请求减少与通过使用外部文件进行缓存带来的好处。其中一个就是在首页中内置 JavaScript和CSS,但是在页面下载完成后动态下载外部文件,在子...
  • C++ 性能优化《测量性能》

    千次阅读 2020-11-28 21:20:02
    本章将介绍两测量性能的工具软件:分析 器和计时器软件。我将讨论如何设计性能测量实验,使得测量结果更有指导意义,而不是 误导我们。 最基本和最频繁地执行的软件性能测量会告诉我们“需要多长时间”。执行函数...
  • 现在的Web前端应用已经不是简单的层结构就能轻松解决,而是已经形成了编译流程化、生产环境基础优化结构运行的模式。HTML结构层必须要知道的DOCTYPEHTML4.01是基于SGML(Standard Generalized Markup language,...
  • 史上最强Tomcat8性能优化

    万次阅读 多人点赞 2019-10-25 15:33:32
    文章目录授人以鱼不如授人以渔目的服务器资源Tomcat配置优化Linux环境安装运行Tomcat8AJP连接执行器(线程池)3运行模式部署测试用的web项目查看服务器信息部署web应用使用Apache JMeter进行性能测试下载安装修改...
  • Android性能优化之页面优化

    千次阅读 2022-03-03 14:03:32
    通过原理,实战的角度,带读者了解如何进行安卓的界面性能优化
  • UE4 优化

    千次阅读 2022-01-06 22:16:25
    UE4 优化
  • wiki没有找到专门介绍sectioning的页面,在上面的循环优化的wiki( http://en.wikipedia.org/wiki/Loop_optimization )中提到了此项优化技术如下: loop-sectioning (also known as strip-mining) is a loop-...
  • 智能优化算法

    千次阅读 2021-11-16 22:29:50
    一、常用的无约束优化方法 1. 最速下降法:负梯度方向使目标函数下降最快 2.牛顿法 二、分类 1. 兔子理论:为了找出地球上最高的山,一群兔子开始想办法。 局部搜索:兔子朝着比现在高的地方跳去。他们找到了...
  • 本论文技术性地介绍了三种最常见的神经网络:前馈神经网络、卷积神经网络和循环神经网络。且该文详细介绍了每一种网络的基本构建块,其包括了基本架构、传播方式、连接方式、激活函数、反向传播的应用和各种优化算法...
  • 文章目录早期(编译期)优化概述Javac编译器Javac的源码与调试解析与填充符号表注解处理器语义分析与字节码生成Java 语法糖的味道泛型与类型擦除自动装箱、拆箱与遍历循环条件编译实战:插入式注解处理器晚期(运行...
  • Oracle数据库SQL优化详解

    千次阅读 多人点赞 2022-01-07 16:53:15
    Oracle数据库SQL优化1. Oracle SQL优化概述2. Oracle SQL优化详解2.1 Oracle 查询阻塞2.2 Oracle 查询耗时 SQL2.3.Oracle 查看执行计划2.4.Oracle 查看收集统计信息2.5.Oracle 查询优化器 -- 改写查询语句2.6.Oracle...
  • 基因测序技术发展历史及一、二、三代测序技术原理和应用 红皇后学术 公众号:红皇后学术(ID: zzlphs2516) 已关注 125 人赞同了该文章 基因测序技术 基因测序技术也称作DNA测序技术,即获得目的DNA片段碱基...
  • 计算机级数据库技术复习资料总结

    万次阅读 多人点赞 2020-10-25 18:38:00
    master:最重要的数据库,记录所有系统级信息,主要的信息都是存放在这。 msdb:保存报警、作业、操作员等信息。(考的不多) model:所有创建数据库的模板。 tempdb:临时数据库,每次启动SQL都会重新创建,因此不...
  • 全国计算机级数据库技术

    千次阅读 多人点赞 2020-02-22 15:42:31
    全国计算机等级考试级(数据库技术) 一:考试内容及要求 1.掌握数据库技术的基本概念、原理、方法和技术 2.能够使用SQL语言实现数据库操作 3.具备数据库系统安装、配置及数据库管理和维护的基本 4.掌握数据库管理...
  • 避免在循环体中创建对象

    千次阅读 2021-03-08 14:25:08
    1. 尽量在合适的场合使用单例使用单例可以减轻加载的负担,缩短加载的时间,提高加载的效率,但并不是所有地方都适用于单例,简单来说,单例主要适用于以下个方面:第一,控制资源的使用,通过线程同步来控制资源...
  • 以基本块为单位,进行运算上的推导优化。堪称妙!原来编译器这么强大!
  • 基因测序技术 基因测序技术也称作DNA测序技术,即获得目的DNA片段碱基排列顺序的技术,获得目的DNA片段的序列是进一步进行分子生物学研究和基因改造的基础。 基因测序技术的发展历史 1977年,Walter Gilbert和...

空空如也

空空如也

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

循环优化的三种重要技术包括