1D Convolution без операторов if-else (не-FFT)?

Question

1D Convolution без операторов if-else (не-FFT)?

Я написал простую последовательную 1D функцию свертки (ниже). Я также экспериментирую с реализациями свертки графических процессоров. Это в основном для моего собственного любопытства; Я пытаюсь изучить компромиссы производительности между различными стратегиями реализации не-FFT.

Избегание ветвления будет важно для моих экспериментов по свертке графических процессоров, так как ветвление стоит дорого на графических процессорах Nvidia. Один из моих друзей упомянул, что есть способ реализовать приведенный ниже код без if/else заявления, но он не мог вспомнить, как это работает.

Как я могу сделать правильную реализацию 1D свертки без использования каких-либо if/else заявления?

Вот мой основной 1D последовательный код на C ++:

vector<int> myConv1d(vector<int> vec, vector<int> kernel)
{
int paddedLength = vec.size() + kernel.size() - 1;
vector<int> convolved(paddedLength); //zeros
reverse(kernel.begin(), kernel.end()); //flip the kernel (if we don't flip it, then we have correlation instead of convolution)
for(int outputIdx=0; outputIdx<paddedLength; outputIdx++) //index into 'convolved' vector
{
int vecIdx = outputIdx - kernel.size() + 1; //aligns with leftmost element of kernel
for(int kernelIdx=0; kernelIdx<kernel.size(); kernelIdx++)
{
if( (vecIdx+kernelIdx) >= 0  &&  (vecIdx+kernelIdx) < vec.size() ) //TODO: FIND A WAY TO REMOVE THIS
{
convolved[outputIdx] += kernel[kernelIdx]*vec[vecIdx+kernelIdx];
}
}
}
return convolved;
}

Пару быстрых заметок:

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

2

c++convolution image-processing optimization

Решение

Другие решения

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

Пусть L = 5 и K = 3, вы должны в конечном итоге с дополненным вектором

p p v v v v v v q q

где vs — векторные элементы, ps и qs — отступы. Имейте в виду, что наборы инструментов графического процессора должны позволять зажимать элементы вне исходного вектора либо до 0, либо до значения границы, что фактически делает бесполезным заполнение, описанное выше.

1

Источник

Accepted Answer

Почему бы тебе не сделать что-то подобное?

int lowerBound = std::max( 0, -vecIdx );
int upperBound = std::min( kernel.size(), vec.size() - vecIdx );
for( int kernelIdx = lowerBound; kernelIdx < upperBound; kernelIdx++ )

Извините, если я не понял вопроса.

3