Стоит ли SIMD?Есть ли лучший вариант? - PullRequest
Новая
       2

Стоит ли SIMD?Есть ли лучший вариант?

6 голосов
/ 18 июля 2010

У меня есть некоторый код, который работает довольно хорошо, но я бы хотел, чтобы он работал лучше.Основная проблема, с которой я столкнулся, заключается в том, что он должен иметь вложенный цикл for.Внешний предназначен для итераций (которые должны выполняться последовательно), а внутренний - для каждой рассматриваемой точечной частицы.Я знаю, что я мало что могу сделать с внешним, но мне интересно, есть ли способ оптимизировать что-то вроде: 

    void collide(particle particles[], box boxes[], 
        double boxShiftX, double boxShiftY) {/*{{{*/
            int i;
            double nX; 
            double nY; 
            int boxnum;
            for(i=0;i<PART_COUNT;i++) {
                    boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+
                        BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
                        //copied and pasted the macro which is why it's kinda odd looking

                    particles[i].vX -= boxes[boxnum].mX;
                    particles[i].vY -= boxes[boxnum].mY;
                    if(boxes[boxnum].rotDir == 1) {
                            nX = particles[i].vX*Wxx+particles[i].vY*Wxy;
                            nY = particles[i].vX*Wyx+particles[i].vY*Wyy;
                    } else { //to make it randomly pick a rot. direction
                            nX = particles[i].vX*Wxx-particles[i].vY*Wxy;
                            nY = -particles[i].vX*Wyx+particles[i].vY*Wyy;
                    }   
                    particles[i].vX = nX + boxes[boxnum].mX;
                    particles[i].vY = nY + boxes[boxnum].mY;
            }   
    }/*}}}*/

Я посмотрел на SIMD, хотя не могу найтимного об этом, и я не совсем уверен, что обработка, необходимая для правильного извлечения и упаковки данных, будет стоить выигрыша, выполняя вдвое меньше инструкций, так как очевидно, что одновременно можно использовать только два двойных числа.1005 * Я попытался разбить его на несколько потоков с помощью shm и pthread_barrier (чтобы синхронизировать различные этапы, из которых приведенный выше код является одним), но это только замедлило его.

Мой текущий код работает довольно быстро;он составляет порядка одной секунды на итерации 10M частиц *, и, насколько я могу судить по gprof, 30% моего времени тратится только на эту функцию (5000 вызовов; PART_COUNT = 8192 частиц заняло 1,8 секунды).Я не беспокоюсь о мелочах с постоянным временем, просто 512K частиц * 50K итераций * 1000 экспериментов заняли больше недели в прошлый раз.эти длинные векторы, которые более эффективны, чем просто проходить через них.Я чувствую, что должно быть, но я не могу его найти.

Ответы [ 5 ]

6 голосов
/ 19 июля 2010

Я не уверен, сколько SIMD выиграет;Внутренний цикл довольно маленький и простой, поэтому я думаю (просто глядя), что вы, вероятно, больше связаны с памятью, чем все остальное.Имея это в виду, я бы попробовал переписать основную часть цикла, чтобы не касаться массива частиц больше, чем нужно: 

const double temp_vX = particles[i].vX - boxes[boxnum].mX;
const double temp_vY = particles[i].vY - boxes[boxnum].mY;

if(boxes[boxnum].rotDir == 1)
{
    nX = temp_vX*Wxx+temp_vY*Wxy;
    nY = temp_vX*Wyx+temp_vY*Wyy;
}
else
{
    //to make it randomly pick a rot. direction
    nX =  temp_vX*Wxx-temp_vY*Wxy;
    nY = -temp_vX*Wyx+temp_vY*Wyy;
}   
particles[i].vX = nX;
particles[i].vY = nY;

Это имеет небольшой потенциальный побочный эффект - не делать дополнительного сложения вend.

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

Поскольку вы обращаетесь к частицам по порядку, вы можете попробовать предварительную выборку (например, __builtin_prefetch в GCC) на несколько частиц вперед, чтобы уменьшить потери в кэше.Предварительная выборка на полях немного сложнее, поскольку вы получаете к ним доступ в непредсказуемом порядке;Вы можете попробовать что-то вроде 

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc...
// prefetch boxes[nextBoxnum]

Последнее, что я только что заметил - если box :: rotDir всегда +/- 1.0, тогда вы можете исключить сравнение и переход во внутреннем цикле, какэто: 

const double rot = boxes[boxnum].rotDir; // always +/- 1.0
nX =     particles[i].vX*Wxx + rot*particles[i].vY*Wxy;
nY = rot*particles[i].vX*Wyx +     particles[i].vY*Wyy;

Естественно, обычные предостережения о профилировании до и после применения.Но я думаю, что все это может помочь, и может быть сделано независимо от того, переключаетесь ли вы на SIMD.

3 голосов
/ 19 июля 2010

Только для записи, есть также libSIMDx86!

http://simdx86.sourceforge.net/Modules.html

(При компиляции вы также можете попробовать: gcc -O3 -msse2 или аналогичный).

2 голосов
/ 18 июля 2010 
((int)(particles[i].sX+boxShiftX))/BOX_SIZE

Это дорого, если sX - int (не могу сказать).Обрезать boxShiftX / Y до целого перед входом в цикл.

1 голос
/ 27 мая 2013

В вашем алгоритме слишком много памяти, целочисленных и ветвящихся инструкций, чтобы иметь достаточно независимых флопов для получения прибыли от SIMD Трубопровод будет постоянно останавливаться.

Поиск более эффективного способа рандомизации был бы первым в списке. Затем попробуйте работать либо в float, либо в int, но не в обоих случаях. Пересмотрите условные выражения как арифметические или, по крайней мере, как операцию выбора. Только тогда SIMD станет реалистичным предложением

1 голос
/ 18 июля 2010

Достаточно ли у вас профилирования, чтобы сказать вам, где время тратится в этой функции?

Например, вы уверены, что это не ваши дивы и моды в подсчете boxnum, где тратится время?Иногда компиляторы не могут определить возможные альтернативы shift / AND, даже если человек (или, по крайней мере, тот, кто знал BOX_SIZE и BWIDTH / BHEIGHT, чего я не знаю) мог бы.

Это было быжалко тратить много времени на SIM-карту. Неправильный бит кода ...

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

...