CPU指令并行化(读书笔记)

December 4th, 2013 by JasonLe's Tech Leave a reply »

SIMD俗称单指令流,多数据流,就是同一条指令被多个数据流的多处理器执行。SIMD通过将相同的操作以并行的方式应用在数据的各个项来实现数据级的并行。我们在选购处理器的时候,经常会关注指令集。我们以SSE为例,SSE俗称Streaming SIMD Extensions 的缩写,思想就是每个16字节的XMM寄存器可以存放多个值。可以存放4个int和float 或者两个double  。SSE指令可以使用这些xmm寄存器执行向量操作。

比如指令 mulps  (%rcs),%xmm0  就会从存储器中读出4个值,并行的执行4个乘法,其中 %rcs包含4个单精度浮点数地址, %xmm0包含4个单精度浮点数。

下面来说一些CPU指令的限制因素,首先我们要明白一些架构术语:IA32  IA64  AMD64

IA32是指英特尔32位CPU架构,他是X86的子集。

IA64是指英特尔64位CPU架构,它与IA32彻底决裂,不兼容IA32指令集。32位的程序跑在上面需要进行硬件虚拟化,并且运行效率不高。它面向高性能计算,企业服务等。

AMD64是基于x86推出的64位技术也就是我们俗称的X86_64。具有64位寻址能力,又兼容32位的程序。

我们都知道AMD64比起X86拓展了寄存器个数和每个寄存器的指令长度,使得拥有了更好地性能。前面我们也说过使用不同的组合会产生的并行,都会有不同的CPE。但是这个并行度也不是可以无线拓展的,比如我们的并行度超过一定量,性能会急剧下降。因为从内存中读写到寄存器会抵消多值并行的好处。所以对于x86拓展到x86_64增加八个寄存器。也就是话说x86_64可以同时累计12个值,然后不产生溢出。

另外CPU为了加速指令执行,还会使用分支预测,分支预测正确则直接将指令结果存储在寄存器中,失败则会直接导致严重的预测错误惩罚,大概在45个指令周期。所以我们要编写易于CPU分支预测的程序代码。

 

void merge(int src1[],int src2[],int dest[],int n)
{
     int i1 = 0;int i2 = 0;int id = 0;
     while(i1<n&&i2<n)
     {
         if(src1[i1]<src[i2])
              dest[id++] = src1[i1++];
         else
              dest[id++] = src2[i2++];
     }
     while(i1<n)
         dest[id++] = src[i1++];
     while(i2<n)
         dest[id++] = src[i2++];
}
******************************************************
//其中while里面的if非常难预测,所以我们这段代码的CPE值大概在17.50左右,如果我们改成下面的CPE将会变为14.0左右
while(i1<n&&i2<n)
{
     int v1 = src[i1];
     int v2 = src[i2];
     int value = v1< v2;
     dest[id++] = value ? v1:v2;
     i1 +=value;
     i2 +=(1-value);
}

除了优化代码结构,实现循环展开,读写相关也是制约CPE降低的主要原因。读写相关就是存储读的结果依赖于一个最近最近的存储器写。
看个例子

void psum1(float a[],float p[],long int n)
{
    long int i;
    p[0] = a[0];
    for(i = 1;i<n;i++)
    {
       p[i] = p[i-1] + a[i];
    }
}//我们看到p[i]依赖于上次的p[i-1],这样就使得关键路径是串行的,不是并行的!
//如果我们将两者使用临时变量保存,CPE就会有大幅度降低
void psum2(float a[],float p[],long int n)
{
    long int i;
    float temp1,temp2;
    temp1 = p[0] = a[0];
    for(i = 1;i<n;i++)
    {
        temp2 = temp1 + a[i];
        p[i]  = temp2;
        temp1 = temp2
    }
}//这样就使得前后的读写不相关,降低CPE
//上面改进的例子没有加入K次循环展开,如果改写为3次的展开,CPE将降为3.0!
void psum3(float a[],float p[],long int n)
{
	long int i;
	p[0] = a[0];
	float val1,val2,val3=p[0];
	for (i=1;i<n-2;i+=3)
	{
		val1 = val3 + a[i];
		val2 = val1 + a[i+1];
		val3 = val2 + a[i+2];
		p[i]=val1;
		p[i+1]=val2;
		p[i+2] = val3;
	}
	for(;i<n;i++)
		p[i]=p[i-1]+a[i];
}

最后,我学习到了一个Amdahl定律。
也就是系统中某部件由于采用某种方式使系统性能改进后,整个系统性能的提高与该方式的使用频率或占总的执行时间的比例有关。

公式就是:S = 1/((1-a)+a/k) 其中a是部分在整个系统所占比例,k是提高的倍数。
这对我们优化系统的某个部分有帮助!