测试准备:操作顺序

    测试中测试函数将对一定范围内的内存进行反复的操作。根据硬件设计的一般原理,操作顺序将会对执行的速度有很大的影响。所以必须讨论采取何种操作顺序进行测试。

    首先来说,顺序操作是必须要测试的。因为很多理论分析是基于顺序操作得出的,Intel的优化指南也经常要求数据是顺序组织的。但仅有顺序操作不能反映实际情况。为此,我们在测试中引入块跳跃方式的操作。下面以16个内存单元(不一定是1字节。不同情况下其大小也不同:对ALU为4字节,MMX为8字节,SSE为16字节)为例,说明顺序操作和块跳跃操作的具体过程:

PreBench_Pattern_01.gif (4707 bytes)    PreBench_Pattern_02.gif (7977 bytes)

上面左图是顺序操作对内存单元的访问顺序,右图是4单元大小的块跳跃操作对内存的访问顺序。仔细分析右图的情况,可以发现其操作模式可以认为是4路并行顺序操作。这也可以对应于多媒体应用中的一般内存操作模式(当然会有一些差异)。另外,顺序操作其实可以看作是块跳跃操作的特殊形式(块大小为1个内存单元)。所以在测试程序中可以用同样的程序生成地址序列,只要提供不同的参数就可以了。实际测试程序中是采用的这种处理方式。这里要特别说明一下复制操作。复制操作有2个操作区域:读出区和写入区。在测试中,复制操作也采用上面这种访问顺序:在读出区按指定的顺序读出数据,再向写入区按相同的顺序写入。

    确定了内存操作顺序以后,就是如何在测试中生成这个地址序列的问题。以前已经讨论过指令和寻址模式的选择,这里将结合这些信息详细讨论最终所使用的测试指令序列。

    下表是以前讨论过的所要采用的寻址方式。由于MMX和SSE只是指令操作码不同,就没有必要单独列出了。

 
(1) (A) mov  eax,  [esi] mov  [esi],        eax
(B) mov  eax,  [esi+xx] mov  [esi+xx],  eax
(2) (A) mov  eax,  [esi+edx] mov  [esi+edx],       eax
(B) mov  eax,  [esi+edx+xx] mov  [esi+edx+xx], eax
(3) (A) mov  eax,  [esi+edx*y] mov  [esi+edx*y],       eax
(B) mov  eax,  [esi+edx*y+xx] mov  [esi+edx*y+xx], eax

首先看较简单的间接寻址方式:类型(1)。其中又以指令(A)的格式最简单。但指令(A)有一个缺点,就是它只能寻址一个内存单元。要访问别的内存单元,必须修正地址寄存器ESI。这样,循环的核心指令将如下:

复制
mov  eax,  [esi]

add  esi,  BlockSize

mov  [esi],  eax

add  esi,  BlockSize

mov  eax,  [esi]

add  esi,  BlockSize

mov  [edi],  eax

add  edi,  BlockSize

其中复制操作由于有2个操作区,将使用2个地址寄存器。

    可以看出,读和写的核心指令是2条,这意味着有效操作的指令密度只有50%。这对Intel的CPU应该没有什么问题,因为它们都只有一个读端口和一个写端口,每周期只能处理一个操作,而CPU每周期可以处理3条指令,所以只要有效操作的指令密度达到33.3%就可以满足要求。但AMD的CPU有2个读端口和2个写端口,其CPU同样每周期处理3条指令,则有效操作的指令密度必须达到66.7%才能“喂饱”读写端口。当然这只是理论分析的结果。不过我们总是希望有效操作的指令密度能够高一些,可以让读写端口有充分发挥的余地。所以我们采取结合(A)和(B)指令的方法来实现更高有效操作的的指令密度。最一般的情况如下:

复制
mov  eax,  [esi]

mov  eax,  [esi+BlockSize]

mov  eax,  [esi+BlockSize*2]

......

mov  eax,  [esi+BlockSize*(n-1)]

add  esi,  BlockSize*n

mov  [esi],  eax

mov  [esi+BlockSize],  eax

mov  [esi+BlockSize*2],  eax

......

mov  [esi+BlockSize*(n-1)],  eax

add  esi,  BlockSize*n

mov  eax,  [esi]

mov  [edi],  eax

mov  eax,  [esi+BlockSize]

mov  [edi+BlockSize],  eax

mov  eax,  [esi+BlockSize*2]

mov  [edi+BlockSize*2],  eax

......

add  esi,  BlockSize*n

add  edi,  BlockSize*n

上面是改进了的核心语句,其中BlockSize是块跳跃操作中块的字节大小,是一个常数,n是指令序列中有效操作的个数,将在下面讨论其值。可见其有效操作的指令密度会有很大的提高,特别是上面的n比较大的时候尤其如此。不过,由于复制是用的2条指令,其有效操作的的指令密度必然小于50%。这是无法解决的问题。即使使用串操作指令(movsd)也无法解决。由于串操作指令是复杂指令,在AMD的指令译码器中每周期最多处理1条。如果使用REP前缀(REP MOVSD),按AMD的文档,其延迟为15+ECX*4/3,极限情况下平均每周期仅0.75个操作,而上面的2指令序列在极限情况下每周期将有1.5个操作(仅AMD),虽比理想值2小了不少,但已经是最好情况了。对Intel的CPU而言,写操作2个uOP,读操作1个uOP,加起来正好3个uOP,是CPU每周期可以处理的最大uOP数,也就是在极限情况下每周期1个操作,应该刚好能够满足读写端口的需要。综合来看,上面的指令序列是能得到的最好情况了。

    下面讨论n的选取。从上面的分析可以知道,选大一些的n可以提高有效操作的指令密度。但n的选取还要受其它一些因素的影响。首先是内存块大小的影响。例如,上面的例子使用了16个单元的内存,如果块大小取为4个内存单元,则共有16÷4=4块,那么为了实现上的简单n不能取大于4的值。另外,在指令序列中最大的常数偏移OffMax=BlockSize*(n-1)。在X86指令集中,寻址的常数偏移可以有8位和32位2种格式。8位偏移仅可以编码-128~+127,而32位偏移可以寻址整个4GB内存地址。似乎32位偏移是最佳的候选。但是还有一个要考虑的问题是指令长度。8位偏移时指令长度为3字节,32位偏移时为6字节。而Intel和AMD的指令预取缓冲区大小是16字节,要达到最佳的指令译码速度,必须在这16字节中装入3条指令。用32位偏移的指令,3条指令共3×6=18>16,并不是一个好的现象。当然,据Intel的文档,P4是没有这个要求的。不过我们总是希望我们的程序不仅可以准确地测试P4的参数,也可以测试其它CPU的参数。所以我们在测试中将只使用8位偏移的格式。

    8位偏移可以编码-128~+127,如果按上面的指令写法,将要求:

    BlockSize*(n-1)<=127   ===>    n<=(127/BlockSize)+1

这其实没有充分利用8位偏移的值域范围。我们可以适当调整指令让其可以利用整个值域范围。具体调整步骤为:

(1)在进入循环前把ESI加上128

(2)每条指令的常数偏移减去128

调整后的核心指令序列如下:

复制
mov  eax,  [esi-128]

mov  eax,  [esi+BlockSize-128]

mov  eax,  [esi+BlockSize*2-128]

......

mov  eax,  [esi+BlockSize*(n-1)-128]

add  esi,  BlockSize*n

mov  [esi-128],  eax

mov  [esi+BlockSize-128],  eax

mov  [esi+BlockSize*2-128],  eax

......

mov  [esi+BlockSize*(n-1)-128],  eax

add  esi,  BlockSize*n

mov  eax,  [esi-128]

mov  [edi-128],  eax

mov  eax,  [esi+BlockSize-128]

mov  [edi+BlockSize-128],  eax

mov  eax,  [esi+BlockSize*2-128]

mov  [edi+BlockSize*2-128],  eax

......

add  esi,  BlockSize*n

add  edi,  BlockSize*n

这样,n必须满足的关系为:

    BlockSize*(n-1)-128<=127   ===>    n<=(255/BlockSize)+1

可见n的范围扩大了一倍。

    还有一个不起眼的优化可以使用。我们知道,在循环的末尾总是这样的指令:

                sub   ecx,  1 ;Intel建议使用sub而不使用dec

                jnz   loop_entry

这是2条相关指令。如果放到一起,将要执行2个周期才能完成。但我们可以在2指令之间插入不改变标志寄存器的指令(如上面的读写指令),就可以让这2条指令和其它指令并行执行。上面的指令序列的最后一条指令是add,要修改标志寄存器,不能作为这种用途。所以我们要对其指令顺序进行调整:

复制
add  esi,  BlockSize*n

; sub ecx, 1

mov  eax,  [esi-128]

mov  eax,  [esi+BlockSize-128]

mov  eax,  [esi+BlockSize*2-128]

......

mov  eax,  [esi+BlockSize*(n-1)-128]

add  esi,  BlockSize*n

; sub ecx, 1

mov  [esi-128],  eax

mov  [esi+BlockSize-128],  eax

mov  [esi+BlockSize*2-128],  eax

......

mov  [esi+BlockSize*(n-1)-128],  eax

add  esi,  BlockSize*n

add  edi,  BlockSize*n

; sub ecx, 1

mov  eax,  [esi-128]

mov  [edi-128],  eax

mov  eax,  [esi+BlockSize-128]

mov  [edi+BlockSize-128],  eax

mov  eax,  [esi+BlockSize*2-128]

mov  [edi+BlockSize*2-128],  eax

......

当然在进入循环前要对地址寄存器(ESI和EDI)进行适当的修正。这样我们就可以在上面标明的地方插入修改循环计数的指令。当然,这个优化对于稍大一些的循环不会有可测量的影响。不过既然有这样一个优化,我们还是在程序中采用之。

    最后,n的选取还要和循环展开因子(见以前的文章)有关。比如,循环展开因子UnrollArg=1时,要求核心循环有2个有效操作。此时,n不能大于2。一般来说,应有n=(1<<UnrollArg)。但n还要满足上面所列出的限制,当UnrollArg很大时,我们必须要把上面的核心指令序列复制多份才能组成一个循环体。当然修改循环计数的指令只在最后一块的开头处插入。

    上面讨论的是间接寻址方式下的地址处理。对于SIB寻址来说,其实非常简单:我们只要把变址寄存器清零,则上面所有的讨论都适用。在测试中我们用EDX作为变址寄存器,并在进入循环前清零。在测试中我们共测试2种SIB寻址方式:比例因子为1和比例因子为4。这是因为Intel的文档说P4的地址要在ALU中运算,而比例因子不为1时将使用延迟为4周期的移位部件(简直难以理解:即使用加法部件,也最多3次加法就可以完成,延迟为1.5个周期!!!)。我们希望这里的测试可以反映出P4的这些特性。

    下表是不同地址模式的比较(PIII-M650@500):

PreBench_Pattern_Tb01.gif (8277 bytes)

其中IND表示间接寻址,SIB表示比例因子为1的SIB寻址,SIB4表示比例因子为4的SIB寻址。RD是读,WR是写。所有操作都是32位的。最左面一列是循环展开因子(UnrollArg)。测试数据单位是Byte/Cycle。可以看到,对读操作来说,寻址方式对速度没有显著的影响,不同寻址方式之间的差异可以忽略。但对于写操作,简直是天壤之别!在UnrollArg=11时,间接寻址的最好成绩(3.6053)比2种SIB的最好成绩(2.6566)快了36%。这是一个不能忽略的比例,也是在以后的参数测试中采用间接寻址的原因。

    另外,表中数据还反映出SIB寻址的写操作在UnrollArg=1时达到性能最佳的反常现象,这在以前讨论循环展开的文章中已经有描述,当时的结论是还有性能更好的实现。回来以后寝食难安,直到实现了这个性能更好而且不再异常的写操作以后才放心。这应该都是拜Intel那个诡异的Store Address单元所赐,但具体这个该死的单元如何影响写操作,只有Intel知道了。

    还有一点不能不说,就是上表中写操作的最好成绩与理论最大值(4)还有一段距离(约11%)。经过多方实验,发现当仅对1个内存单元进行写操作时,将可以接近理论最大值到满意的程度。这在我们的测试中是不适用的,所以就不在这里进行比较了。如有兴趣可以自己写来看看。

    由于修改了测试函数的核心语句,所有前面进行的测试的结果都发生了变化。但我们仔细分析以后发现,以前的文章的讨论仍然适用,新数据并不影响其正确性。由于不同的CPU的测试结果将有很大不同,这里就不再列出新的测试结果了。等测试程序发布以后,你可以在自己的机器上去测试。这比我在这里列出的结果要有说服力得多。


Leading Cloud Surveillance, Recording and Storage service; IP camera live viewing

Leading Enterprise Cloud IT Service; cloud file server, FTP Hosting, Online Storage, Backup and Sharing

Powered by FirstCloudIT.com, a division of DriveHQ, the leading Cloud IT and Cloud Surveillance Service provider since 2003.