Как уменьшить непоследовательные сегменты чисел в массиве с помощью Thrust - PullRequest
Новая
       90

Как уменьшить непоследовательные сегменты чисел в массиве с помощью Thrust

0 голосов
/ 28 апреля 2019

У меня есть 1D массив "A", который состоит из множества массивов "a", например: An example of an array

Я реализую код для суммирования непоследовательных сегментов (Суммируйте числа в сегментах одного цвета каждого массива «a» в «A» следующим образом:

An example for one array

Любые идеи, чтобы сделать этоэффективно с тягой?

Большое спасибо

Примечание: на рисунках представлен только один массив "a". Большой массив "A" содержит много массивов "a"

1 Ответ

2 голосов
/ 28 апреля 2019

В общем случае, когда порядок данных и группировка по сегментам заранее неизвестны, общее предложение состоит в том, чтобы использовать thrust::sort_by_key для группировки похожих сегментов, а затем использовать thrust::reduce_by_key для суммирования сегментов.Примеры приведены здесь .

Однако, если сегменты входных данных следуют известному повторяющемуся шаблону, такому как здесь предлагается, мы можем исключить этап сортировки, используя thrust::permutation_iterator to "соберите «похожие сегменты» вместе, как входные данные для thrust::reduce_by_key.

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

0  1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...

Эта последовательность будет затем «отображать» или переупорядочивать входной массив, так что все подобные сегменты будут сгруппированы вместе.Я уверен, что есть разные способы создания такой последовательности, но я выбрал следующий подход.Мы начнем со стандартной последовательности итераторов подсчета, а затем применим к ней функтор преобразования (используя make_transform_iterator), чтобы создать вышеописанную последовательность.Я решил сделать это, используя следующий метод, упорядоченный в пошаговой последовательности, показывающий компоненты, которые добавляются вместе: 

counting iterator: (_1)                         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
---------------------------------------------------------------------------------------------------
((_1/seg_len)%seg_types)*(seg_len*seg_types):   0  0  0  9  9  9 18 18 18  0  0  0  9  9  9 18 18 18 ...
 _1%seg_len:                                    0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 ...
_1/(seg_len*seg_types)*seg_len:                 0  0  0  0  0  0  0  0  0  3  3  3  3  3  3  3  3  3 ...
 Sum:                                           0  1  2  9 10 11 18 19 20  3  4  5 12 13 14 21 22 23 ...

Вот полностью обработанный пример: 

$ cat t457.cu
#include <thrust/reduce.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <thrust/device_vector.h>
#include <thrust/copy.h>
#include <iostream>

typedef int dtype;
const int seg_len = 3;
const int seg_types = 3;

using namespace thrust::placeholders;

int main(){

  dtype data[] = {10,16,14,2,4,4,1,2,1,8,2,10,3,1,6,8,0,2,9,1,0,3,5,2,3,2,1};
  //                0   1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...
  //              ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len

  int ads = sizeof(data)/sizeof(data[0]);
  int num_groups = ads/(seg_len*seg_types); // ads is expected to be whole-number divisible by seg_len*seg_types
  int ds = num_groups*(seg_len*seg_types);  // handle the case when it is not
  thrust::device_vector<dtype> d_data(data, data+ds);
  thrust::device_vector<dtype> d_result(seg_types);
  thrust::reduce_by_key(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1/(ds/seg_types)), thrust::make_transform_iterator(thrust::counting_iterator<int>(ds), _1/(ds/seg_types)), thrust::make_permutation_iterator(d_data.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len))), thrust::make_discard_iterator(), d_result.begin());
  thrust::copy(d_result.begin(), d_result.end(), std::ostream_iterator<dtype>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t457 t457.cu
$ ./t457
70,30,20,
$
...