CUDA Thrust — как я могу написать функцию, используя несколько векторов устройств с разными размерами?

Я пытался понять, как выполнить простой расчет энтропии, используя четыре вектора тяги.

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

Это выглядит примерно так:

Пара векторов устройств 1

КейВал 6 8 9

Считает 1 3 2

Пара векторов устройств 2

KeyVal 6 8 8 9 9

БинВал 1 1 2 1 1

Вектор результатов (содержит рассчитанные результаты энтропии)

KeyVal 8

Энтропия 0,602

Что я планирую сделать, так это использовать первую пару векторов, чтобы проверить, появляется ли ключ достаточное количество раз для вычисления энтропии. Если количество достаточно велико, вторая пара векторов будет использоваться для вычисления энтропии со значениями интервала для этого ключа. Мне нужно будет использовать все значения корзины для этого конкретного ключа. Например, если бы я хотел посчитать энтропию для ключей, появившихся не менее 3 раз, я бы нашел в первой паре векторов, что KeyVal 8 готов. Затем я искал во второй паре все экземпляры KeyVal 8 и вычислял энтропию, используя их соответствующие BinVals. Расчет энтропии прост, он просто включает сложение BinVal*Log(BinVal) для каждого соответствующего значения. В моем примере это будет энтропия = 1*log(1) + 2*log(2).

Однако я понятия не имею, как заставить эту часть работать. Я пытался использовать тягу:: for_each, чтобы найти все ключи, которые появляются достаточное количество раз для проверки, но я не думаю, что возможно искать ключи во второй паре векторов и выполнять вычисления в функции for_each.

Есть ли у кого-нибудь предложения о других способах достижения этого?

Спасибо за помощь.


person user2471905    schedule 02.07.2015    source источник
comment
можешь закончить описание? предоставить полную последовательность векторов, включая желаемый результирующий вектор для вашего примера. В частности, вы говорите: «Тогда я бы искал во второй паре все экземпляры KeyVal 8 и вычислял энтропию, используя соответствующие BinVal. Что это значит? Какую именно арифметику вы хотите выполнить с BinVals, которые соответствуют KeyVal 8 (т.е. BinVals 1 и 2, в вашем примере)?   -  person Robert Crovella    schedule 02.07.2015
comment
Извините, я должен был включить это. Расчет прост, он просто складывает BinVal*Log(BinVal) для каждого соответствующего значения. В моем примере это будет энтропия = 1*log(1) + 2*log(2).   -  person user2471905    schedule 02.07.2015
comment
Отсортированы ли векторы KeyVal? Если нет, случайно не сгруппированы ли вместе ключи? И могу ли я ожидать, что ключи будут появляться в одном и том же порядке в каждом векторе? Если конкретный KeyVal появляется в первом векторе KeyVal, есть ли вероятность, что для него не будет никаких записей во втором векторе KeyVal?   -  person Robert Crovella    schedule 02.07.2015
comment
Векторы KeyVal отсортированы, а одинаковые ключи сгруппированы вместе.   -  person user2471905    schedule 02.07.2015
comment
Если конкретный KeyVal появляется в первом векторе KeyVal, есть ли вероятность, что для него не будет записей во втором векторе KeyVal?   -  person Robert Crovella    schedule 02.07.2015
comment
Нет, если KeyVal появляется в первом, он гарантированно появится и во втором векторе KeyVal.   -  person user2471905    schedule 02.07.2015
comment
Извините за все вопросы. Если KeyVal появляется во втором векторе KeyVal, есть ли вероятность, что для него нет записей в первом векторе KeyVal?   -  person Robert Crovella    schedule 02.07.2015
comment
Без проблем. Если KeyVal появляется в одном векторе, то он должен появиться и в другом.   -  person user2471905    schedule 02.07.2015
comment
разве это не должно быть Counts 1 2 2 ? Или эти подсчеты не учитывают, как часто ключ встречается во втором векторе KeyVal?   -  person m.s.    schedule 02.07.2015
comment
Подсчеты подсчитывают общее количество BinVals для этого KeyVal.   -  person user2471905    schedule 02.07.2015


Ответы (1)


Две идеи, которые я рассматривал, были:

Идея А:

  1. Вычислите все энтропии
  2. Выберите те, которые соответствуют критериям

Идея Б:

  1. Выберите входящие данные, которые соответствуют критериям
  2. Вычислите энтропии.

Идея А, кажется, выполняет ненужную работу — вычисляет энтропию, которая не нужна или может быть не нужна. Однако по мере того, как я работал над идеей B, я добавил так много шагов (например, вычисление сумм префиксов) для завершения шага 1 идеи B, что казалось, что это не будет лучше. Итак, я сейчас представлю Идею А. Может быть, м.с. или кто-то еще придет и опубликует что-то лучше.

Шаг 1 идеи A обрабатывается thrust::reduce_by_key вместе с соответствующим функтором для вычисления конкретной функции энтропии.

Шаг 2 идеи A обрабатывается thrust::copy_if

$ cat t827.cu
#include <iostream>
#include <thrust/device_vector.h>
#include <thrust/copy.h>
#include <thrust/reduce.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <math.h>

// THRESH determines the minimum Counts value required for a KeyVal Entropy calculation to occur
#define THRESH 2

using namespace thrust::placeholders;


struct my_entropy : public thrust::unary_function<float, float>
{
  __host__ __device__
  float operator()(float val){
    return val*log10f(val);}  // if you want napierian log, change this to logf
};

int main(){

  int KeyVal1[]={6, 8, 9};
  int Counts[] ={1, 3, 2};
  int KeyVal2[]={6, 8, 8, 9, 9};
  float BinVal[] ={1, 1, 2, 1, 1};

  int dsize1 = sizeof(KeyVal1)/sizeof(int);
  int dsize2 = sizeof(KeyVal2)/sizeof(int);

  thrust::device_vector<int> d_KeyVal1(KeyVal1, KeyVal1+dsize1);
  thrust::device_vector<int> d_Counts(Counts, Counts+dsize1);
  thrust::device_vector<int> d_KeyVal2(KeyVal2, KeyVal2+dsize2);
  thrust::device_vector<float> d_BinVal(BinVal, BinVal+dsize2);


  // method 1 - just compute all entropies, then select the desired ones
  thrust::device_vector<float> entropies(dsize2);
  thrust::reduce_by_key(d_KeyVal2.begin(), d_KeyVal2.end(), thrust::make_transform_iterator(d_BinVal.begin(), my_entropy()), thrust::make_discard_iterator(), entropies.begin());
  thrust::device_vector<int> res_keys(dsize1);
  thrust::device_vector<float>res_ent(dsize1);
  int res_size = thrust::copy_if(thrust::make_zip_iterator(thrust::make_tuple(d_KeyVal1.begin(), entropies.begin())), thrust::make_zip_iterator(thrust::make_tuple(d_KeyVal1.end(), entropies.end())), d_Counts.begin(), thrust::make_zip_iterator(thrust::make_tuple(res_keys.begin(), res_ent.begin())), _1 >= THRESH) - thrust::make_zip_iterator(thrust::make_tuple(res_keys.begin(), res_ent.begin()));
  std::cout << "Counts threshold: " << THRESH << std::endl <<  "selected keys: " << std::endl;
  thrust::copy_n(res_keys.begin(), res_size, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl << "calculated entropies: " << std::endl;
  thrust::copy_n(res_ent.begin(), res_size, std::ostream_iterator<float>(std::cout, ","));
  std::cout << std::endl;

  return 0;
}
[bob@cluster1 misc]$ nvcc -o t827 t827.cu
$ ./t827
Counts threshold: 2
selected keys:
8,9,
calculated entropies:
0.60206,0,
$
person Robert Crovella    schedule 02.07.2015
comment
Спасибо! Я протестировал Идею А со своим кодом и убедился, что она дает правильную энтропию для моих данных. - person user2471905; 02.07.2015