Как уменьшить время доступа в векторе - PullRequest
Новая
       2

Как уменьшить время доступа в векторе

1 голос
/ 02 февраля 2012

Я пытаюсь увеличить скорость алгоритма, поэтому я запустил свое приложение с «Инструментами» для iOS, результаты, почти 75% времени используются для сохранения вычислений в векторе.

Кто-нибудь знает лучший способ сохранить данные, не потребляя так много процессора?Я полагаю, это связано с доступом к кеш-памяти или что-то в этом роде.Строка помечена комментарием, в этой строке сохраняется шорт в массиве шорт. 

short XY[32*32*2]
Mat _XY(bh, bw, CV_16SC2, XY), matA;
Mat dpart(dst, Rect(x, y, bw, bh));

for( y1 = 0; y1 < bh; y1++ )
{
    short* xy = XY + y1*bw*2;
    int X0    = M[0]*x + M[1]*(y + y1) + M[2];
    int Y0    = M[3]*x + M[4]*(y + y1) + M[5];
    float W0  = M[6]*x + M[7]*(y + y1) + M[8];

    M2[2] = X0;
    M2[3] = Y0;

    for(x1=0; x1<bw; x1++)
    {

        float W      = W0 + M[6]*x1;
        W            = 1./W;
        float x12[2] = {x1*W,W};


        matvec2_c(M2,x12,M3);
        short aux    = (M3[0]);
        int aux2     = x1*2;
        xy[aux2]     = aux;          // %60 CPU TIME
        xy[x1*2+1]   = (M3[1]);      // 11% CPU TIME
    }
    // ...
}

void matvec2_c(float m[4], float v[2], float d[2])
{
    d[0] = m[0]*v[0] + m[2]*v[1];
    d[1] = m[1]*v[0] + m[3]*v[1];
}

Ответы [ 3 ]

1 голос
/ 03 февраля 2012

Я предполагаю, что это проблема оптимизации компилятора: вычисление указателя для xy выполняется в for (x1 = -loop, а не в for (y1 = -loop), поэтому выполняется намного больше, чем необходимо.

Возможное решение: используйте assert() для принудительного создания экземпляра: 

#include <assert.h>

...
short* xy = XY + y1*bw*2;
assert (xy!=NULL);
...
0 голосов
/ 07 февраля 2012

Это было лучшее, что я мог сделать: 

short XY[32*32*2];
int XYI[32*32*2];
Mat _XY(bh, bw, CV_16SC2, XY), matA;
Mat _XYI(bh, bw, CV_32S, XYI);
Mat dpart(dst, Rect(x, y, bw, bh));

 for( y1 = 0; y1 < bh; y1++ )
 {
    int * xyi = XYI + y1*bw;
    short * xy = XY + y1*bw*2;

    int X0 = M[0]*x + M[1]*(y + y1) + M[2];
    int Y0 = M[3]*x + M[4]*(y + y1) + M[5];

    float W0 = M[6]*x + M[7]*(y + y1) + M[8];
    M2[2]=X0;
    M2[3]=Y0;

    for(x1=0;x1<bw;x1++){

    float W = W0 + M[6]*x1;
    W= 1./W;
    float x12[2]={x1*W,W};


    matvec2_c(M2,x12,M3);

    xyi[x1*2] = (M3[0]);//9% 
    xyi[x1*2+1]=(M3[1]);//6%



}
for(x1=0;x1<bw;x1++){

  xy[x1*2] = xyi[x1*2];//4%
  xy[x1*2+1]=xyi[x1*2+1];//3%
}

Я просто разделил часть, в которой код сохраняет уравнение, на две части, поэтому я предполагаю, что это связано с тем, как процессор обращается к кешу, или, возможно, с другими форматами. Время уменьшения алгоритма с 93 до 78 мс.

0 голосов
/ 03 февраля 2012

Я не уверен, что делает ваш код, он не очень дружелюбен к авторам.Но если вы обращаетесь к данным в этих массивах во всех направлениях (влево, вверх, вправо, вниз), то для вас может быть следующее:

Индексируйте свой массив, используя Morton Code / ZКривая порядка. .Это увеличивает локальность ссылок , что улучшает поведение при кэшировании, когда вы получаете доступ к элементам полностью вокруг элементов.

Подумайте об этом: при использовании классической двумерной индексации расстояние до верхних и нижних соседей представляет собой высоту или ширину.Если ваша ширина / высота очень высоки, то вы получаете доступ к очень отдаленным элементам вашего массива.Учитывая, что ЦП выполняет много спекулятивного кэширования, многие из этих спекуляций приводят к напрасным усилиям (так называемый cache-miss ).У вас есть несколько хороших показателей (левый и правый соседи), а некоторые очень и очень плохие (верхний и нижний соседи).

С индексированием Мортона у вас нет идеальных левых / правых соседей, но в равной степени у вас нет дальних верхних / нижних соседей.

Если в среднем вы делаете попадания в кэшированные данные, то доступ к этим данным действительно дешевый (данные могут быть уже в кеше, даже если вы даже не начали доступ к ним, благодаря [http://en.wikipedia.org/wiki/Speculative_execution](speculativeвыполнение) и предварительная выборка .

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

...