Действительно ли SIMD стоит Того? Существует ли более оптимальный вариант?
У меня есть некоторый код, который работает довольно хорошо, но я хотел бы заставить его работать лучше. Основная проблема, которую я имею с ним, состоит в том, что это должно иметь вложенный для цикла. Внешний - для повторений (который должен произойти последовательно), и внутренний - для каждой частицы точки на рассмотрении. Я знаю, что нет очень, я могу сделать о внешнем, но я задаюсь вопросом, существует ли способ оптимизировать что-то как:
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, хотя я не могу найти много об этом, и я не совсем уверен, что обработка, необходимая, чтобы правильно извлечь и упаковать данные, стоила бы усиления выполнения вдвое меньше инструкций, так как по-видимому только два удваиваются, может использоваться за один раз.
Я пытался разбить его в несколько потоков с отметкой курса корабля и pthread_barrier (для синхронизации различных этапов, из которых вышеупомянутый код - один), но это просто сделало его медленнее.
Мой текущий код действительно идет довольно быстро; это находится на порядке одной секунды на 10M particle*iterations, и от того, что я могу сказать от gprof, 30% моего времени потрачены в одной только той функции (5 000 вызовов; частицы PART_COUNT=8192 заняли 1,8 секунды). Я не волнуюсь по поводу маленьких, постоянных вещей времени, это просто, что 512K частицы * 50K повторения * 1 000 экспериментов заняли больше чем неделю в прошлый раз.
Я предполагаю, что мой вопрос состоит в том, если существует какой-либо способ иметь дело с этими длинными векторами, который более эффективен, чем просто цикличное выполнение через них. Я чувствую, что должно быть, но я не могу найти его.
4 ответа
Я не уверен, насколько 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;
Это имеет небольшой потенциальный побочный эффект, заключающийся в том, что в конце не выполняется дополнительное добавление.
Еще одно возможное ускорение - использование __ 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 или нет.
Для записи, есть еще libSIMDx86!
http://simdx86.sourceforge.net/Modules.html
(При компиляции вы также можете попробовать: gcc -O3 -msse2 или аналогичный).
((int)(particles[i].sX+boxShiftX))/BOX_SIZE
Это дорого, если sX - это int (не могу сказать). Перед входом в цикл усечь boxShiftX / Y до целого числа.
Есть ли у вас достаточный профайлинг, чтобы сказать, где тратится время в этой функции?
Например, вы уверены, что время тратится не на ваши div'ы и mod'ы в вычислении boxnum? Иногда компиляторы не замечают возможных альтернатив shift/AND даже там, где человек (или, по крайней мере, тот, кто знает BOX_SIZE и BWIDTH/BHEIGHT, чего я не знаю) мог бы это сделать.
Было бы жаль тратить много времени на SIMDификацию неправильной части кода...
Другая вещь, на которую стоит обратить внимание, - можно ли заставить эту работу работать с библиотекой типа IPP, которая будет принимать обоснованные решения о том, как лучше использовать процессор.