CODEWITHSUNDEEP
c++cudagpgputhrust
aiwyn
aiwyn

Reputation: 278

Thrust: reduce_by_key passing zip_iterator(tuple) into custom functor to retrieve average by key

What I'm trying to do is get an average of values by key via thrust::reduce_by_key. I first sort_by_key and that works just fine to group by consecutive keys for reduce_by_key. I used this to help get me this far. However, I am getting lots of errors that I cannot understand (this is also my first time using reduce_by_key) and I can't think of a better way to do this without using lots of temporary allocations to (1) get the sum of the values by key then the count by key and (2) divide the two for the average.

input keys:   1,   1,   1,  2,   3,   5,  5,  2
input values: 120, 477, 42, 106, 143, 53, 83, 24

expected output values: 213, 65, 143, 68

I have the following custom functor:

struct GetAverage
{
    template<typename Tuple>
    __host__ __device__
    int operator()(const Tuple& t)
    {
        //SumByKey / CountByKey
        return thrust::get<0>(t) / thrust::get<1>(t);
    }
};

The functor is called from the below code, located in main()

thrust::device_vector<unsigned int> tempKey(8);
thrust::device_vector<unsigned int> tempValue(8);

tempKey[0] = 1;
tempKey[1] = 1;
tempKey[2] = 1;
tempKey[3] = 2;
tempKey[4] = 3;
tempKey[5] = 5;
tempKey[6] = 5;
tempKey[7] = 2;

tempValue[0] = 120;
tempValue[1] = 477;
tempValue[2] = 42;
tempValue[3] = 106;
tempValue[4] = 143;
tempValue[5] = 53;
tempValue[6] = 83;
tempValue[7] = 24;

thrust::sort_by_key(tempKey.begin(), tempKey.end(), tempValue.begin());

thrust::equal_to<int> binary_pred;
thrust::reduce_by_key(
    tempKey.begin(),
    tempKey.end(),
    thrust::make_zip_iterator(
        thrust::make_tuple(
            tempValue.begin(),
            thrust::make_constant_iterator(1)
        )
    ), //values_first; Should go into GetAverage() custom functor as a zipped tuple <tempValue, 1>
    tempKey.begin(), //keys_output; Should be returning the unique keys
    tempValue.begin(), //values_output; Should be returning the average by key 
    binary_pred,
    GetAverage()
);

Example errors:
-no instance of function template "GetAverage::operator()" matches the argument list
-no operator "=" matches these operands
-no suitable conversion function from "InputValueType" to "TemporaryType" exists
-no suitable conversion function from "thrust::detail::tuple_of_iterator_references<thrust::device_reference<int>, int, thrust::null_type, thrust::null_type, thrust::null_type, thrust::null_type, thrust::null_type, thrust::null_type, thrust::null_type, thrust::null_type>" to "TemporaryType" exists

Does anyone have any ideas on how to fix this? Or links? I read the documentation on everything in use here and was as careful in trying to understand it as possible, but with no resolution. Thanks!

UPDATE
See Eric's answer. In conjunction with what he said, this is the new source code. Created an op to handle plus for Tuples. The only thing this code doesn't do is after the reduce_by_key call, a thrust::transform should be used on the results to get the average by dividing the sum by the count.

// --- Defining key tuple type
typedef thrust::tuple<int, int> Tuple;

/* PLUS OPERATOR BETWEEN TUPLES */
struct TuplePlus
{
    __host__ __device__
    Tuple operator ()(const Tuple& lhs, const Tuple& rhs)
    {
        return thrust::make_tuple(
            thrust::get<0>(lhs) + thrust::get<0>(rhs),
            thrust::get<1>(lhs) + thrust::get<1>(rhs)
        );
    }
};

Inside main() I have the following now.

thrust::equal_to<int> binary_pred;
thrust::reduce_by_key(
    tempKey.begin(),
    tempKey.end(),
    thrust::make_zip_iterator(
        thrust::make_tuple(
            tempValue.begin(),
            thrust::make_constant_iterator(1)
        )
    ), //values_first; goes in as a zipped up tuple <value, 1>
    tempKey.begin(), //keys_output
    thrust::make_zip_iterator(
        thrust::make_tuple(
            tempValue.begin(),
            tempCount.begin()
        )
    ), //values_output; ZipIterator<Sum, Count> by key
    binary_pred,
    TuplePlus()
);

Upvotes: 0

Views: 1354

Answers (1)

kangshiyin
kangshiyin

Reputation: 9771

There are two issues.

The result of a tuple sequence reduction should be a tuple but not int. According to the document

https://thrust.github.io/doc/group__reductions.html#ga633d78d4cb2650624ec354c9abd0c97f

The last parameter binary_op should be of the type

BinaryFunction is a model of Binary Function and BinaryFunction's result_type is convertible to OutputIterator2's value_type.

It means your reduction operation should be something like 

struct GetSum
{
  template<typename Tuple>
  __host__ __device__
  Tuple operator()(const Tuple& a, construction Tuple& b)
  {
    ...
  }
}

On the other hand, at the reduction stage, you can only calculate the sum but not the average efficiently. It means your values_output should also be a zip iterator with the same type as values_first.

OutputIterator2 is a model of Output Iterator and InputIterator2's value_type is convertible to OutputIterator2's value_type.

So you need two result arrays, one for the sum by key and one for the count by key. They should be zipped together and used as values_output .

Then you need another thrust::transform to calculate the final result - average by key.

You could also try the approach proposed by @RobertCrovella, which uses a single thrust::reduce_by_key to calculate the average.

Output from reduce_by_key() as a function of two reduced vectors

Upvotes: 1

Related Questions