精华内容
下载资源
问答
  • c语言循环优化

    千次阅读 2014-01-13 11:53:27
    C语言常规优化策略 3 循环优化 提高程序效率的核心是对影响代码执行速度的关键程序段...本节有关各种循环优化技术的讨论基本上以下面的一个程序段为对象,程序的涵义为:对于两个给定的 数组a、b,计算a[8]b

    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上设计出一个产生抖动的程序,就会看到硬盘指示灯不断闪烁。如

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

    展开全文
  • 也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构...

    循环优化概述.

    什么叫做循环?循环就是程序中那些可能反复执行的代码序列。也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构程序设计思想,程序员在编程时应使用高级语言所提供的结构性的循环语句来编写循环。而由高级语言的循环语句所形成的循环,是不难找出的。对于循环中的代码,可以实行代码外提、强度削弱和删除归纳变量等优化操作。一个中间代码序列的程序流图如下所示:
    在这里插入图片描述
    我们不难看出,其中B 2 _2 2和B 3 _3 3分别构成一个循环,{B 2 _2 2,B 3 _3 3,B 4 _4 4,B 5 _5 5}构成一个范围更大的循环。而我们要进行循环优化,首先需要知道循环在哪里,接下来,我们就一步步给出,整个循环优化的过程。

    计算必经节点集.

    【定义】:若从首结点出发到达结点N j _j j的每一条通路都必须经过结点N i _i i,那么我们称N i _i i是N j _j j的必经节点,记为N i _i i dom N j _j j,其中dom是dominate的简写。那么N j _j j所有必经节点的集合,就是N j _j j的必经节点集,记为D(N j _j j).

    计算程序流图中必经节点集的算法也是一个不动点算法,通过每一次的迭代来计算一个结点的必经节点集。当程序流图中所有结点的迭代计算结果都不发生改变时,说明已经获得了最终的结果,算法宣布结束。下面我们给出计算必经节点集的算法:
    在这里插入图片描述
    这里我们也给出一个例题,作为计算必经节点集算法的收尾:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    需要注意的是,该算法并不像图中那样,一次迭代计算就可以确定结果,而是需要再一次迭代确认了所有的结点都没有发生变化,才能确定最终结果的。

    循环查找算法.

    1.查找回边.

    【定义】如果一个程序流图中存在有向边<N i _i i→N j _j j>,并且N j _j j∈D(N i _i i),那么我们称有向边<N i _i i→N j _j j>是一条回边。

    依旧是我们前一部分给出的实例,考察其中的回边:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    2.查找循环.

    求出了程序流图中的回边之后,我们就可以基于回边来查找循环。具体的方法是,若<N i _i i→N j _j j>是一条回边,那么该回边构成的循环中的结点包括:N i _i i和N j _j j以及所有不经过N i _i i能够到达N j _j j的结点。我们以上图中求出的三条回边为例,6→6确定的循环中只包括结点6;7→4确定的循环中包括结点有{4,7,5,6};4→2确定的循环中包括的结点有{2,4,3,5,6,7}。

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    代码外提.

    至此我们已经完成了查找循环包含结点的工作,接下来就是要对循环体中的中间代码进行优化了。循环中的某些代码虽然随着循环反复地执行,但其中某些运算的结果并没有发生改变,例如循环中有形如A:=B op C的代码,并且如果B和C都是常数,或者到达它们的定值点都在循环外,那么不管循环多少次,每次计算出来得到的B op C的结果都是不变的,对于这样的不变运算,我们完全可以将其外提到循环以外,避免其随着循环多次计算。如此一来,程序的结果没有发生变化,但程序的运行速率却得到了一定程度的提高,这就是代码外提。

    【定义】所谓变量A在程序中某一点d的定值到达了另一点u,或者说变量A的定值点d达到另一点u,指的是程序流图中从d有一条通路到达u,并且通路上没有A的其它定值点。

    实行代码外提时,我们在循环的入口结点之前建立一个新结点(基本块),称为循环的前置结点,该前置结点以循环的入口结点为其唯一后继。并且原来流图中从循环外引到循环入口结点的有向边,都改为引到该前置结点。如下图所示:
    在这里插入图片描述
    我们考虑的循环结构,其入口结点都是唯一的,从而其前置结点也是唯一的,我们后续进行代码外提时所有外提的代码都将提到前置结点中。下面一段Pascal源程序,是我们叙述代码外提的第一个例子:

    for I:=1 to 10 do
    	A[I,2*J]:=A[I,2*J]+1
    

    它对应的中间代码序列如下:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    1. 考察序号为3和7的语句,因为循环中并没有J的定值点,所以其中J所有引用的定值点都在循环外,从而3和7都是循环不变运算;
    2. 考察序号为6和10的语句,分配给数组A的首地址addr(A)的值并不会随着循环的一次次执行而改变,所以6和10也都是循环不变运算。

    所以我们可以做出这样的判断:3与7、6与10都可以外提到该循环的前置节点中,进行了代码外提之后的中间代码序列如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    那么问题又来了,是不是在任何情况下,都可以将循环不变运算进行外提呢?我们看第二个例子:
    在这里插入图片描述
    从程序流图中我们不难看出,{B 2 _2 2,B 3 _3 3,B 4 _4 4}构成了一个循环,并且B 2 _2 2是入口结点,B 4 _4 4是出口结点。

    【定义】出口结点是指循环中具有如下性质的结点:从该结点有一条有向边引到循环外的某结点。

    图中我们也不难看出,基本块B 3 _3 3中的I:=2语句是循环不变语句,那么我们是否可以直接将这一语句外提到循环以外的前置结点B 2 ′ _2' 2呢?我们暂且认为可以这样做,外提之后的程序流图如下所示:
    在这里插入图片描述
    我们看外提了I:=2这一语句的程序流图,执行到基本块B 5 _5 5时,变量I的值总会是2,从而J的值也会是2.但我们需要注意的是,在原始的、没有进行I:=2外提的程序流图中,B 3 _3 3并不是B 4 _4 4的必经结点。我们在原始流图中考虑X=30、Y=25的情况,这样的情况下B 3 _3 3是不会被执行的,所以执行到B 5 _5 5时变量I的值应该是1,从而J的值也应该是1而非2.那么很显然,我们进行了I:=2外提的程序已经改变了程序运行的结果,这必然是不允许的。问题到底出在什么地方呢?其实前面已经点出,B 3 _3 3并不是循环出口结点B 4 _4 4的必经节点,再直白一点说,B 3 _3 3中的代码并不一定会对B 4 _4 4中的代码起到作用,但如果我们将其外提到循环的前置结点,那么该外提的语句必然是会对B 4 _4 4产生影响的,这就导致了程序运行结果被改变的风险,我们并不允许这样的风险存在。
    所以从这个例子中我们可以看到,当一个循环不变运算要外提到循环的前置结点时,要求该循环不变运算的语句所在的结点是循环的所有出口结点的必经结点
    另外,我们注意到,如果循环中变量I的所有引用点都是B 3 _3 3I的定值点所能到达的,I在循环中不再有其它的定值点,并且出循环之后也不会再引用变量I的值(即在循环外的循环后继结点入口,变量I不是活跃的),那么即使B 3 _3 3不是B 4 _4 4的必经结点,还是可以将I:=2外提到循环的前置结点,因为这样做并不会改变程序的结果。
    再一个例子,如果我们将上述程序流图中的基本块B 2 _2 2改为:

    I:=3
    if X<Y goto B3
    

    考虑B 2 _2 2I:=3外提的问题。
    通过计算必经结点集可以发现,B 2 _2 2确实是循环出口结点B 4 _4 4的必经结点,那么我们是否可以将I:=3进行代码外提呢?同样的论述过程,我们姑且认为可以,那么如果程序的执行过程是2-3-4-2-4-5,则执行B 5 _5 5时的变量I值为2,从而J的值也是2;而如果不进行外提操作,那么同样的执行过程下,I和J的值都应该是3,而非2.这一错误的原因在于,循环中除了B 2 _2 2以外,B 3 _3 3也对同一个变量进行了定值。
    所以从这个例子中我们可以看到,当我们将循环不变运算A:=B op C外提时,要求循环中的其它地方不再有A的定值点
    第三个例子,也是最后一个例子,我们看下面一个程序流图:
    在这里插入图片描述
    考察基本块B 4 _4 4中循环不变运算I:=2这一语句的外提操作。首先,B 4 _4 4结点就是整个循环的出口结点,并且B 4 _4 4结点也是其本身的必经结点;其次整个循环{B 2 _2 2,B 3 _3 3,B 4 _4 4}中也没有第二个对于变量I定值的语句。那么我们是否可以将这一语句外提呢?同样的方法,我们还是暂且认为这一语句可以外提,再比较对于同一个执行过程,外提前后的执行结果。我们考虑X=0、Y=2的情况,循环的执行流程是2-3-4-2-4-5,代码外提前,程序的执行结果为J=2;而代码外提后,程序的执行结果为J=3.
    通过这个例子,我们看到,当将循环不变语句A:=B op C进行代码外提时,要求循环中所有对于A的引用点都是并且仅仅是这一定值语句所能到达的。上述的例子中,能够到达A:=I+1这一对于I的引用的定值语句,不仅有B 4 _4 4中的I:=2,还有B 1 _1 1中的I:=1.
    最后我们给出查找循环L中不变运算的算法:
    在这里插入图片描述
    以及代码外提算法:
    在这里插入图片描述

    强度削弱.

    我们要介绍的第二种循环优化技术叫做强度削弱。强度削弱是将程序中执行时间较长的运算替换为执行时间较短的运算。例如,最常见的就是将循环中的乘法运算用递归的加法运算来代替。我们考察前面经过了代码外提的示例流图:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    不难看出{B 2 _2 2,B 5 _5 5}是一个循环,并且B 2 _2 2是循环的入口结点。我们注意序号为13的语句,这里的变量I是一个递归赋值的变量,每循环一次,它增加一个常量1。另外,序号为4和8的语句在计算T 2 _2 2和T 6 _6 6时,都会使用I的值,并且T 2 _2 2和T 6 _6 6都是I的线性函数,每循环一次,它们都增加一个常量10.因此,如果把4和8外提到循环的前置结点中,并且在13号语句之后添加上为T 2 _2 2和T 6 _6 6增加常量10的语句,程序的运行结果依然不变。

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    经过上述变换,循环中原来的乘法运算4和8被替换为了在前置结点中进行一次初始化的乘法运算(计算初值)以及在循环中递归赋值的加法运算(4’)和(8’).不仅加法运算一般来说比乘法运算快,而且这种在循环前计算初值,再于循环末尾进行常量递增的运算,可以利用变址器提高运算速度,从而使运算的强度得到削弱。所以我们称这种优化技术为强度削弱。
    强度削弱不仅对于乘法可以实行,对于加法也可以实行。例如上图中序号为5和9的语句,T 3 _3 3与T 7 _7 7的计算中引用到了T 2 _2 2和T 6 _6 6,并且T 2 _2 2和T 6 _6 6也是递归赋值的变量,每循环一次,它们的值就增加一个常量10.而T 3 _3 3与T 7 _7 7的另一个运算对象都是循环不变量,所以每循环一次,T 3 _3 3与T 7 _7 7的值就增加一个常量10.很自然地,我们会想到对它们进行强度削弱,即外提一个初始化语句,在循环的末尾添加常量递增语句,得到的优化结果如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    从上面的例子中我们可以看到:

    1. 如果循环中有A的递归赋值A:=A±b 1 _1 1,并且循环中另一个变量B的赋值运算可以写为B:=k*A±b 2 _2 2的形式,那么对于B的赋值运算,我们可以进行强度削弱;
    2. 进行强度削弱之后,循环中可能会出现一些新的无用赋值,例如上图中的(4’)和(8’),因为循环中不再使用T 2 _2 2和T 6 _6 6,那么如果循环出口之后它们也不是活跃变量,是完全可以删除的;
    3. 循环中下标变量的地址计算是相当耗费时间的,这里介绍的方法对削弱下标变量地址计算的强度是非常有效的。前面的例子中,数组是二维的,如果我们考察一个更高维度的数组,将会进一步看到强度削弱的作用。对于下标变量地址计算来说,强度削弱实际上就是实现下标变量地址的递归计算。

    删除归纳变量.

    我们要介绍的最后一种循环赋值技术叫做删除归纳变量。讲述具体的流程之前,首先给出基本归纳变量以及归纳变量的定义:

    【定义】基本归纳变量:循环中对于变量A的赋值只有唯一的、形如A:=A±b 1 _1 1的赋值,那么称A为循环中的基本归纳变量;
    【定义】归纳变量:如果A是一个基本归纳变量,循环中对于B的赋值总是可以化归为A的同一个线性函数,即B:=k*A±b 2 _2 2,那么我们称B是一个归纳变量。

    考察进行了代码外提之后的示例程序流图:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    不难发现变量I是循环{B 2 _2 2,B 3 _3 3}的基本归纳变量,T 2 _2 2和T 6 _6 6是循环中与I同族的归纳变量,再继续发掘,T 3 _3 3和T 7 _7 7也是与I同族的归纳变量。
    一个基本归纳变量除了用于自身的递归赋值以外,往往只在循环中用于计算其他的归纳变量和控制循环的进行。经过了强度削弱之后的示例程序流图如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    关注基本块B 3 _3 3可以发现变量I除了用于自身的递归赋值以外,只用于控制循环的进行。这时,我们可以使用与I同族的某一个归纳变量来代替I控制循环的进行,从而删除变量I.例如,我们选取T 3 _3 3(T 7 _7 7与T 3 _3 3都在循环中被引用,所以是一样的,而T 2 _2 2和T 6 _6 6在循环中没有被引用)来代替I, 由于T 3 _3 3可以写为10*I+T1,并且循环的控制条件为I>10,所以用T 3 _3 3代替了I之后,控制条件变为了T3>100+T1.为了不在每一次进行判断时都计算100+T 1 _1 1的值,我们引入新的临时变量R:=100+T 1 _1 1,所以序号为2的if语句改写为:

    R:=100+T1
    if T3>R goto (15)
    

    然后我们就可以删去变量I了,这一优化技术称为删除归纳变量,也叫变换循环控制条件。如果我们假定T 2 _2 2和T 6 _6 6在循环出口之后也不是活跃的,那么我们完全可以删去这两个临时变量(因为它们在循环中也没有被使用)。但如果我们在选择代替I的变量时选择了T 2 _2 2或T 6 _6 6,那么(4’)或(8’)就不能删除了,最后完成删除归纳变量的中间代码如下:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    删除归纳变量是在强度削弱之后进行的。我们在下面统一给出强度削弱和删除归纳变量的算法:
    在这里插入图片描述

    展开全文
  • 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·


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


    郑重·专业·有料



    展开全文
  • wiki没有找到专门介绍sectioning的页面,在上面的循环优化的wiki( http://en.wikipedia.org/wiki/Loop_optimization )中提到了此项优化技术如下: loop-sectioning (also known as strip-mining) is a loop-...
    参考手册:
    

    http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011Update/compiler_c/index.htm


    说明:本系列文章为个人笔记,如有不正确之处,请参考官方相关文档,如果错误发现,我会尽量更新修改。另外,以下内容不保证对于所有版本的编译器都正确,编译器的实现也可能有一些变化之处,具体参考官方文档。


    更多说明请参考http://blog.csdn.net/gengshenghong/article/details/7034748中补充说明部分。


    说明:这里主要讨论和循环相关的基本优化技术的“术语”以及对其的理解。(不断更新)

    循环是程序中一个很重要的部分,因为在优化理论中,有很多对循环进行优化的研究。


    参考:

    Loop optimization (wiki):

    http://en.wikipedia.org/wiki/Loop_optimization


    1. Loop unwinding/loop unrolling/loop unroll循环展开

    http://en.wikipedia.org/wiki/Loop_unrolling

    Loop unwinding, also known as loop unrolling, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size (space-time tradeoff). The transformation can be undertaken manually by the programmer or by an optimizing compiler.

    简单来说,循环展开,是一种增加了二进制文件大小来优化程序执行速度的循环转换技术,可以人工或者通过编译器完成。循环展开的目的是通过减少或者消除控制循环的指令来增加程序速度。

    当然,循环展开有很多情况分类,参考wiki理解其中的细节。对于最简单的循环展开的情况,就是静态的循环的展开,如下:

    int x;
    for (x = 0; x < 100; x++)
    {
         delete(x);
    }
    一种可能的展开是:

    int x; 
    for (x = 0; x < 100; x+=5)
    {
         delete(x);
         delete(x+1);
         delete(x+2);
         delete(x+3);
         delete(x+4);
    }
    上面的代码很容易理解,循环的迭代次数从100次减少为20次,显然,这样会较少循环控制的判断(对x的判断)的指令执行次数,从而提高性能。当然,实际上,仅仅依靠上述循环展开往往不能很大程度的提高性能,而且上面的静态的循环迭代次数只是最简单的情况,还有很多情况需要动态进行循环展开等,另外,循环展开是对循环进行优化的一项基础技术,往往需要和其他优化进行合作。向量化的过程,往往就是从循环展开开始的。


    2. sectioning/loop-sectioning/strip-mining/strip mining

    循环切分?

    wiki没有找到专门介绍sectioning的页面,在上面的循环优化的wiki(http://en.wikipedia.org/wiki/Loop_optimization)中提到了此项优化技术如下:

    loop-sectioning (also known as strip-mining) is a loop-transformation technique for enabling SIMD-encodings of loops and improving memory performance. This technique involves each vector operation being done for a size less than or equal to the maximum vector length on a given vector machine.

    其后面给出了和此项技术有关的链接:

    Strip Mining to Optimize Memory Use on 32-Bit Intel® Architecture

    Strip-Mining(http://docs.oracle.com/cd/E19205-01/819-5262/aeugr/index.html)

    简单来说,sectioning(不确定中文翻译如何表述),是一项加强SIMD对循环的编码和提高内存性能的循环转换技术,使得每一个向量操作以小于或者等于给定的向量机最大的向量长度的大小来完成。

    参考上面的链接能很容易的理解此项技术对内存优化的过程,当然,上面的链接没有包括SIMD相关的优化的例子。


    3. Loop interchange循环交换

    http://en.wikipedia.org/wiki/Loop_interchange

    In compiler theory, loop interchange is the process of exchanging the order of two iteration variables.

    简单来说,循环交换就是交换内外层循环的迭代变量的过程。需要注意的是,不是所有情况都能直接进行循环交换,需要判断数据依赖关系。

    下面的例子可以很容易理解循环交换的过程:

    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            a[i][j]=i+j;
    
    for(int j=0;j<N;j++)
        for(int i=0;j<M;i++)
            a[i][j]=i+j;
    显然,上面两个循环是等价的,但是性能不一样。哪一个更好?大多数情况,相信是第一个循环更好,因为二维数组是连续排列的,第二个循环很有可能导致了更多刷新cache的次数。

    和循环交换相关的博文:

    http://www.cnblogs.com/bingsuixing/archive/2009/04/20/1440057.html

    http://www.cdblp.cn/paper/%E5%BE%AA%E7%8E%AF%E4%BA%A4%E6%8D%A2%E4%B8%8E%E9%80%92%E5%BD%92%E6%B6%88%E9%99%A4/6951.html


    4. Loop blocking

    loop blocking是intel编译器提供的一种优化技术,是strip mining和loop interchange的结合。

    参考http://software.intel.com/en-us/articles/performance-tools-for-software-developers-loop-blocking/理解其细节。

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

    千次阅读 2016-02-29 21:35:52
    图像算法的工程优化技术当一个很酷的图像算法实现之后,我们希望集成到软件中去,这时将会遇到最大的拦路虎:性能。 可以想像一下,如果美图秀秀做一个美颜效果要转圈圈转个30秒,还会有多少人用呢。 学术界喜欢...
  • 3D游戏技术 - 大型3D地图优化渲染技术

    万次阅读 多人点赞 2013-11-30 08:22:53
    技术简介: 如果需要渲染一个大型3D地图,由于数据量,需要渲染的东西非常多,所以尤其一些慢一点的机器就会变得非常卡。 如下面这些会造成帧率(FPS)下降的图: ...每一种技术都需要挺长篇幅介绍的,本文就分
  • 软件优化技术

    千次阅读 2007-06-07 11:53:00
    软件优化技术真经-框架篇 软件优化是一项系统工程。总体而言,整个优化框架可以分为两个部分:设计优化和代码优化。1,设计优化 设计优化包括了软件体系结构的优化,数据结构的优化,算法的优化...
  • 本论文技术性地介绍了三种最常见的神经网络:前馈神经网络、卷积神经网络和循环神经网络。且该文详细介绍了每一种网络的基本构建块,其包括了基本架构、传播方式、连接方式、激活函数、反向传播的应用和各种优化算法...
  • 因为在放入新的位置时,HashMap会将Entry对象不断的插入链表的头部。插入头部也主要是为了防止尾部遍历,否则这对key的...如果条件竞争发送了,可能会出现环形链表,之后当我们get(key)操作时,就有可能发生死循环
  • [转]C++性能优化技术导论

    千次阅读 2011-12-20 16:14:19
    本文完整的描述了C++语言的性能优化方法,从编译器、算法、语言特性、硬件、Linux等多个角度去考虑问题,文章技术含量很高,值得一看。 来源:http://www.whysearch.org/a/zh_CN/date/20110824 作者:冲出宇宙...
  • C++性能优化技术导论

    千次阅读 2012-06-05 16:31:19
    本文完整的描述了C++语言的性能优化方法,从编译器、算法、语言特性、硬件、Linux等多个角度去考虑问题,文章技术含量很高,值得一看。 来源:http://www.whysearch.org/a/zh_CN/date/20110824 作者:冲
  • 现在的Web前端应用已经不是简单的层结构就能轻松解决,而是已经形成了编译流程化、生产环境基础优化结构运行的模式。HTML结构层必须要知道的DOCTYPEHTML4.01是基于SGML(Standard Generalized Markup language,...
  • gcc的优化到底优化了哪些

    千次阅读 2016-11-13 23:28:51
    不同的优化级别使用的优化技术也可以单独的应用于代码。 可以使用-f命令行选项引用每个 单独的优化技术。 第一级:代码调整  代码调整是一局部的思维方式;基本上不触及算法层级;它面向的是代码,而不是问
  • 下面讨论的编译期优化指的是javac编译器将java文件转化为字节码的过程,而运行期间优化指的是JIT编译器所做的优化。 编译期优化 虚拟机设计团队把对性能的优化集中到了后端的即时编译器
  • java语言的“编译期”是一...下面讨论的编译期优化指的是javac编译器将java文件转化为字节码的过程,而运行期间优化指的是JIT编译器所做的优化。 编译期优化 虚拟机设计团队把对性能的优化集中到了后端的即时编译器
  • 本论文技术性地介绍了三种最常见的神经网络:前馈神经网络、卷积神经网络和循环神经网络。且该文详细介绍了每一种网络的基本构建块,其包括了基本架构、传播方式、连接方式、激活函数、反向传播的应用和各种优化算法...
  • 在此介绍TI C6000的软件开发流程,重点讨论C6000系列的C/C++程序优化技术包括优化流程,C/C++代码优化方法,编写线形汇编代码优化方法等。为DSP的C/C++软件开发提供了全面的程序优化技术和方法,对实际系统的...
  • 最近几年,我开始专注于数据库的查询优化,2016年末的一次培训成为契机,我决定出一本书,于是我一边培训,一边梳理书中可写的内容,对要写哪些内容,写到什么深度做了一些定位,当时想的是如果有出版社出版就出版,...
  • 史上最强Tomcat8性能优化

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

    千次阅读 2018-04-04 20:42:46
    蚂蚁在运动过程中,会留下一称为信息素的东西,并且会随着移动的距离,播散的信息素越来越少,所以往往在家或者食物的周围,信息素的浓度是最强的,而蚂蚁自身会根据信息素去选择方向,当然信息素越浓,被选择的...
  • 软件优化技术真经-框架篇

    千次阅读 2005-10-10 20:28:00
    1,设计优化 设计优化包括了软件体系结构的优化,数据结构的优化,算法的优化。1.1 软件体系结构的优化软件优化首先要对整个软件体系结构有个清晰的了解。在认识了整个软件的目标功能后,围绕这个目标,软件的模块...
  • Java程序员有一个共识,以编译方式执行本地代码比解释方式更快,之所以有这样的共识,除去虚拟机解释执行字节码时额外消耗时间的原因外,还有一个很重要的原因就是虚拟机设计团队几乎把对代码的所有优化措施都集中在...
  • 程序优化个级别

    千次阅读 2015-11-02 11:36:14
    程序优化个级别   HouSisong@GMail.com 2004.11.07整理 tag:代码优化,程序优化,综级优化,代码调整,新的视角,表驱动状态机 文章来源于abp论坛中的一篇帖子:...
  • 引擎V8及优化技术

    千次阅读 2015-04-17 12:03:06
    不过按照Lars Bak的说法, 所有这些优化技术都是不他们创造的。这些技术都只是在前人的基础上做的改进。以下列一下V8的相关优化技术. 2.1 隐藏类(hidden class) 为了减少 JavaScript 中访问属性所花...
  • 第16章 Unity中的渲染优化技术

    千次阅读 2018-01-23 16:36:57
    程序优化的第一条准则: 不要优化。程序优化的第二条准则(仅针对专家! 〉: 不要优化。 一一Michael A. Jackson 在进行程序优化的时候,人们经常会引用英国的计算机科学家Michael A. Jackson 在1988 年的优化准则...
  • C语言常规优化策略--赋值语句优化

    千次阅读 2007-11-16 08:28:00
    C语言常规优化策略从理论上讲,程序的优化一般分为局部优化、循环优化和全局优化...循环优化和全局优化往往能大幅提升程序效率,因此有关的技术对于高质量的程序设计是至关重要的。本文讨论C语言程序常规优化策略,其重
  • 开发中或者是正在运行的系统性能显著恶化的场合,需要进行性能优化。当听到性能优化时,有些人可能会感觉到非常困难,如果使用OB的话,通过使用索引或者内存等可以非常简单的进行性能优化。这篇文章将要介绍怎样使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 123,991
精华内容 49,596
关键字:

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