我应该如何改善这种代码的缓存友好？ （三维复杂阵列的2D矩阵的一维数组）

Question

我工作的一个Android应用程序与多声道音频处理交易。该STFT函数产生与尺寸nChannels一个三维复杂阵列由n帧由nFreq形式的复杂的频率 - 时间表示。

然而，在下一步骤中，我需要执行盲源分离移动每个频率仓的通道和帧划分为一个矩阵，其运行时的好处很大程度上从我。目前，阅读STFTin的条目时的代码是相当缓存不友好。有没有什么办法，使这个更多的缓存友好吗？

    Complex[][] temp = new Complex[nFrames][nChannels];
    Complex[][] tempConj = new Complex[nFrames][nChannels];

    X = new Array2DRowFieldMatrix[nFreqs];
    Xcopy = new Array2DRowFieldMatrix[nFreqs];
    Xconj = new Array2DRowFieldMatrix[nFreqs];
    Y = new Array2DRowFieldMatrix[nFreqs];
    for (int f = 0; f < nFreqs; f++) {
        for (int t = 0; t < this.nFrames; t++) {
            for (int c = 0; c < this.nChannels; c++) {
                temp[t][c] = STFTin[c][t][f];
                tempConj[t][c] = STFTin[c][t][f].conjugate();
                //STFTin is nChannels by nFrames by nFreq
        }
        X[f] = new Array2DRowFieldMatrix<>(temp);
        Xconj[f] = new Array2DRowFieldMatrix<>(tempConj);
        Xcopy[f] = (Array2DRowFieldMatrix<Complex>) X[f].copy();
        Y[f] = (Array2DRowFieldMatrix<Complex>) X[f].copy();
    }

Answer 1

正如我在评论中提到的，你可能会想，以适应现有的高速缓存友好的矩阵转置的算法来实现你的逻辑（因为这是大多数你doing-什么矩阵转置的）。别人已经充实了有关最佳块大小，循环有序的实施细则，以及如何占优势情况下（不规则形状例如矩阵），所以调整现有的代码将导致速度更快，bug更少的代码。

但是，如果你真的需要推出自己的解决方案，这就是我会尝试。首先，重新排序的循环，这样的频率和信道的循环是循环的框架内。您是从频率子阵列直接访问元素和它们储存在通道内的子阵，所以它的重要的是我们做的最这两种，而他们被加载到高速缓存;这就是为什么我们需要保持帧循环在外面。

接下来，你的块阵列按一定比例，以你的缓存大小的访问。这样，所有我们所操作的频率和信道子阵可以在的cache是​​同时存在的，我们不会通过一次读从频率阵列值太多，反之亦然抹杀道子阵列。有方法来计算规模，但说实话更可靠，更快地只要运行它时间它 - 当事情停止越来越快停止增加的块大小。

下面粗代码大纲：

Complex[][][] temp = new Complex[nFreqs][nFrames][nChannels];
Complex[][][] tempConj = new Complex[nFreqs][nFrames][nChannels];

int blockSizeF = 1 << 2;  // Increase these until you see no speedup
int blockSizeC = 1 << 3;

X = new Array2DRowFieldMatrix[nFreqs];
Xcopy = new Array2DRowFieldMatrix[nFreqs];
Xconj = new Array2DRowFieldMatrix[nFreqs];
Y = new Array2DRowFieldMatrix[nFreqs];
for (int t = 0; t < this.nFrames; t++) {
    for (int fBlock = 0; fBlock < nFreqs; fBlock += blockSizeF) {
        for (int cBlock = 0; cBlock < this.nChannels; cBlock += blockSizeC) {
            for (int f = fBlock; f < fBlock + blockSizeF; f++) {
                for (int c = cBlock; c < cBlock + blockSizeC; c++) {
                    temp[f][t][c] = STFTin[c][t][f];
                    tempConj[f][t][c] = STFTin[c][t][f].conjugate();
                    //STFTin is nChannels by nFrames by nFreq
                }
            }
        }
    }
}
for (int f = 0; f < nFreqs; f++) {
    X[f] = new Array2DRowFieldMatrix<>(temp[f]);
    Xconj[f] = new Array2DRowFieldMatrix<>(tempConj[f]);
    Xcopy[f] = (Array2DRowFieldMatrix<Complex>) X[f].copy();
    Y[f] = (Array2DRowFieldMatrix<Complex>) X[f].copy();
}

通常blockSizeF和blockSizeC将是相同的，但在这种情况下，每一个读入STFTin的频率子阵列，您执行两个写入temp和tempConj的独立通道的子阵列。这意味着你将要为渠道比频可能2的因素较大的块大小，也许的我sqrt(2)-不太确定的因素是诚实的。我想像这将是这两个虽之一，所以我只是尝试，找出最。无论哪种方式，你可能会想圆你的块大小断两帮与高速缓存行或页边界对齐（或至少一些大功率的两多）的最近的电源。

但是请注意，blockSizeF和blockSizeC绝对必须分别为nFreqs和nChannels的因素。周围有此规定的方式，但它的复杂，速度较慢，而且容易出错。它通常容易只是垫你的矩阵，去掉多余的改造后。