这段代码的瓶颈在哪里？

Question

我有以下紧密循环组成我的代码的串行瓶颈.理想情况下,我会并行化调用此函数的函数,但这是不可能的.

//n is about 60
for (int k = 0;k < n;k++) 
{
    double fone = z[k*n+i+1];
    double fzer = z[k*n+i];
    z[k*n+i+1]= s*fzer+c*fone;
    z[k*n+i] = c*fzer-s*fone;
}

是否有任何可以进行的优化,例如矢量化或一些可以帮助此代码的邪恶内联？

我正在研究寻找三对角矩阵的特征解.http://www.cimat.mx/~posada/OptDoglegGraph/DocLogisticDogleg/projects/adjustedrecipes/tqli.cpp.html

Answer 1

简答:将矩阵的内存布局从行主顺序更改为列主顺序.

答案很长:看来你正在访问以行主顺序存储的矩阵的第(i)和第(i + 1)列 - 可能是一个整体不适合CPU缓存的大矩阵.基本上,在每次循环迭代时,CPU必须等待RAM(大约100个周期).经过几次迭代后,从理论上讲,地址预测应该启动,CPU应该在循环访问之前推测性地加载数据项.这应该有助于RAM延迟.但是仍然存在代码无效地使用内存总线的问题:CPU和内存从不交换单个字节,只交换缓存行(当前处理器上为64字节).在加载和存储的每64字节高速缓存行中,您的代码仅接触16个字节(或四分之一).

转置矩阵并以原生主要顺序访问它将使内存总线利用率提高四倍.由于这可能是代码的瓶颈,因此您可以期望大约相同的订单加速.

是否值得,取决于你的算法的其余部分.其他部分当然可能因内存布局的改变而受到影响.