Как мне улучшить дружественность кеша этого кода?(3D комплексный массив в 1D массив 2D матриц)

Question

Я работаю над приложением для Android, которое занимается обработкой многоканального звука.Функция STFT создает сложное частотно-временное представление в виде трехмерного комплексного массива с размерами nChannels от nFrames от 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

Как я уже упоминал в комментариях, вы, вероятно, захотите адаптировать существующий алгоритм транспонирования матрицы с учетом кэша для реализации вашей логики (поскольку это большая часть того, что вы делаете, - транспонирование матрицы).Другие уже уточнили детали реализации, касающиеся оптимальных размеров блоков, упорядочения циклов и того, как учитывать крайние случаи (например, матрицы неправильной формы), поэтому адаптация существующего кода приведет к более быстрому и менее ошибочному коду.

Однако, если вам действительно нужно накатить собственное решение, вот что я бы попробовал.Во-первых, переупорядочьте петли так, чтобы петли частоты и канала были внутри цикла for-frame.Вы получаете доступ к элементам непосредственно из частотного подмассива и храните их внутри подмассива канала, поэтому важно, чтобы мы максимально использовали оба из них, пока они загружены в кэш;вот почему нам нужно держать цикл кадров снаружи.

Далее, разбейте на части доступ к вашему массиву в соответствии с некоторой пропорцией к размеру вашего кэша.Таким образом, все частотные и канальные подмассивы, с которыми мы работаем, могут одновременно существовать в кэше - мы не уничтожим подмассивы каналов, считывая слишком много значений из частотных массивов за раз, или наоборот.Есть способы рассчитать этот размер, но, честно говоря, он более надежный и быстрый, чтобы просто запустить его и рассчитать время - когда дела пойдут быстрее, прекратите увеличивать размер блока.

Примерный пример кода ниже:

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 соответственно.Есть способы обойти это условие, но оно сложное, медленное и подверженное ошибкам.Обычно проще просто дополнить вашу матрицу и удалить лишнее после преобразования.