Параллельный выбор с сохранением порядка из массива с использованием tbb

У меня есть диапазон-изображение, и я хочу преобразовать его в облако точек libpointmatcher. Облако представляет собой Eigen::Matrix с 4 строками (x, y, z, 1) и несколькими столбцами для каждой точки. Изображение диапазона - это unsigned short*array, включающий значения диапазона (z) и unsigned char*array, включая информацию о видимости пикселей.

Последовательно мой код выглядит так:

//container to hold the data
std::vector<Eigen::Vector4d> vec;
vec.reserve(this->Height*this->Width);

//contains information about pixel visibility
unsigned char* mask_data = (unsigned char*)range_image.mask.ToPointer();
//contains the actual pixel data 
unsigned short* pixel_data = (unsigned short*)range_image.pixel.ToPointer();

for (int y =0;y < range_image.Height; y++)
{ 
    for (int x = 0; x < range_image.Width; x++)
    {   
        int index  =x+y*range_image.Width;
        if(*(mask_data+index) != 0)
        {               
            vec.push_back(Eigen::Vector4d(x,y,(double)*(data+index),1));
        }               
    }
}
// libpointmatcher point cloud with size of visible pixel
PM::Matrix features(4,vec.size());
PM::DataPoints::Labels featureLabels;
featureLabels.resize(4);
featureLabels[0] =  PM::DataPoints::Label::Label("x");
featureLabels[1] =  PM::DataPoints::Label::Label("y");
featureLabels[2] =  PM::DataPoints::Label::Label("z");
featureLabels[3] =  PM::DataPoints::Label::Label("pad");

//fill with data
for(int i = 0; i<vec.size(); i++)
{
    features.col(i) = vec[i];
}   

Из-за больших изображений этот цикл занимает 500 мс для 840000 точек, и это слишком медленно. Теперь моя идея заключалась в том, чтобы объединить приведенный выше код в одну параллельную функцию. Проблема в том, что Eigen::Matrix не предоставляет функциональных возможностей push_back, я не знаю заранее количество видимых точек и мне нужны точки в правильном порядке для обработки облака точек.

Поэтому мне нужен параллельный алгоритм для извлечения видимых 3D-точек из моего изображения диапазона и вставки их в Eigen :: Matrix в правильном порядке. Я работаю с Microsoft Visual Studio 2012 и могу использовать либо OpenMP 2.0, либо TBB. Я ценю любую помощь :)

ОБНОВЛЕНИЕ

Как подсказал Арч Д. Робисон, я попробовал tbb::parallel_scan. Я передал массив масок и двойной массив для хранения трехмерных координат. Выходной массив в четыре раза превышает размер входного массива для хранения однородных трехмерных данных (x, y, z, 1). Затем я отображаю массив otput в Eigen :: Matrix. Количество строк фиксировано, а столбцы появляются из результата parallel_scan.

size_t vec_size = width*height;
double* out = new double[vec_size * 4];
size_t m1 = Compress(mask, pixel, out, height, width,
 [](unsigned char x)  {return x != 0; });
Map<MatrixXd> features(out, 4, m1);

. Вот код из operator():

void operator()(const tbb::blocked_range2d<size_t, size_t>& r, Tag) {
    // Use local variables instead of member fields inside the loop,
    // to improve odds that values will be kept in registers.
    size_t j = sum;
    const unsigned char* m = in;
    const unsigned short* p = in2;
    T* values = out;
    size_t yend = r.rows().end();
    for (size_t y = r.rows().begin(); y != yend; ++y)
    {
        size_t xend = r.cols().end();
        for (size_t x = r.cols().begin(); x != xend; ++x)
        {
            size_t index = x + y*width;
            if (pred(m[index]))
            {
                if (Tag::is_final_scan())
                {
                    size_t idx = j*4;
                    values[idx] = (double)x;
                    values[idx + 1] = (double)y;
                    values[idx + 2] = p[index];
                    values[idx + 3] = 1.0;
                }
                ++j;
            }
        }
    }
    sum = j;
}

Я сейчас в 4 раза быстрее серийной версии. Что вы думаете об этом подходе? Я что-то пропустил и есть ли улучшения? Спасибо


person PSchn    schedule 16.08.2016    source источник
comment
Если вам нужен логический эквивалент std :: copy_if, рассмотрите возможность использования tbb :: parallel_scan (software.intel.com/sites/default/files/bc/2b/parallel_scan.pdf). На финальной фазе сканирования можно вычислить конечный индекс назначения (как сумму индексов успешного выполнения и выполнить условное присвоение).   -  person Arch D. Robison    schedule 18.08.2016
comment
@ ArchD.Robison, можете ли вы дать мне пример кода требований parallel_scan (Body, reverse_join_assign)? Я понятия не имею, как это сделать: / Какая структура лучше всего подходит для хранения индексов и как мне объединить их при окончательном сканировании? пожалуйста, помогите мне :)   -  person PSchn    schedule 18.08.2016


Ответы (2)


Вот пример того, как сделать что-то вроде std::copy_if using tbb::parallel_scan. Ключевым методом является operator(), который обычно вызывается дважды для каждого поддиапазона, один раз для предварительного сканирования и один раз для окончательного сканирования. (Но имейте в виду, что TBB пропускает предварительное сканирование, когда в нем нет необходимости.) Здесь предварительное сканирование просто выполняет подсчет, а окончательное сканирование выполняет окончательную работу (которая включает повторное воспроизведение подсчета). См. https://software.intel.com/sites/default/files/bc/2b/parallel_scan.pdf для получения более подробной информации о методах. Еще одна полезная ссылка - https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf, где показано множество возможностей параллельного сканирования (также известного как сумма префиксов).

```

#include "tbb/parallel_scan.h"
#include "tbb/blocked_range.h"
#include <cstddef>

template<typename T, typename Pred>
class Body {
    const T* const in;
    T* const out;
    Pred pred;
    size_t sum;
public:
    Body( T* in_, T* out_, Pred pred_) :
        in(in_), out(out_), pred(pred_), sum(0)
    {}
    size_t getSum() const {return sum;}
    template<typename Tag>
    void operator()( const tbb::blocked_range<size_t>& r, Tag ) {
        // Use local variables instead of member fields inside the loop,
        // to improve odds that values will be kept in registers.
        size_t j = sum;
        const T* x = in;
        T* y = out;
        for( size_t i=r.begin(); i<r.end(); ++i ) {
            if( pred(x[i]) ) {
                if( Tag::is_final_scan() )
                    y[j] = x[i];
                ++j;
            }
        }
        sum = j;
    }
    // Splitting constructor used for parallel fork.
    // Note that it's sum(0), not sum(b.sum), because this
    // constructor will be used to compute a partial sum.
    // Method reverse_join will put together the two sub-sums.
    Body( Body& b, tbb::split ) :
        in(b.in), out(b.out), pred(b.pred), sum(0)
    {}
    // Join partial solutions computed by two Body objects.
    // Arguments "this" and "a" correspond to the splitting
    // constructor arguments "b" and "this".  That's why
    // it's called a reverse join.
    void reverse_join( Body& a ) {
        sum += a.sum;
    }
    void assign( Body& b ) {sum=b.sum;}
};

// Copy to out each element of in that satisfies pred.
// Return number of elements copied.
template<typename T, typename Pred>
size_t Compress( T* in, T* out, size_t n, Pred pred ) {
    Body<T,Pred> b(in,out,pred);
    tbb::parallel_scan(tbb::blocked_range<size_t>(0,n), b);
    return b.getSum();
}

#include <cmath>
#include <algorithm>
#include <cassert>

int main() {
    const size_t n = 10000000;
    float* a = new float[n];
    float* b = new float[n];
    float* c = new float[n];
    for( size_t i=0; i<n; ++i )
        a[i] = std::cos(float(i));
    size_t m1 = Compress(a, b, n, [](float x) {return x<0;});
    size_t m2 = std::copy_if(a, a+n, c, [](float x) {return x<0;})-c;
    assert(m1==m2);
    for( size_t i=0; i<n; ++i )
        assert(b[i]==c[i]);
}

```

person Arch D. Robison    schedule 19.08.2016
comment
Спасибо за Ваш ответ. Я попробую как можно скорее. Вы только что выбрали размер 10 000 000. Можете ли вы сказать что-нибудь о производительности при меньших значениях? вроде 1 миллион или всего 100 тысяч? - person PSchn; 19.08.2016
comment
Все зависит от того, насколько тяжелая операция pred для вашего случая. Если это всего лишь несколько циклов (например, ‹на целых числах), сканирование, вероятно, будет проигрышным предложением для Xeon с большим ядром, потому что накладные расходы на передачу памяти затопят вычисления. На Рыцарской Гавани может быть некоторая надежда на ускорение. Если ваш предшественник тяжеловес, вам повезет больше. - person Arch D. Robison; 23.08.2016

Почему бы вам не проверить условие *(m_maskData+index)==0 перед m_features(0,index) = x;?

person ntfs.hard    schedule 16.08.2016
comment
Да, я сделаю это. Проблема в том, что я не знаю количество видимых пикселей, а parallel_for не выполняется в определенном порядке. Но мне нужен только видимый пиксель в том же порядке, что и на изображении. - person PSchn; 16.08.2016