I am trying to code the following problem in cuda/thrust. I am given a list of key and three values associated with each keys. I have managed to sort them in lexicographic order. The input now needs to be reduced if inputs with same key have each value-wise relation. In example below, V1(a)<=V1(c) and V2(a)<=V2(c) and V3(a)<=V3(c), implies that Input a < Input c, and hence, Input c is removed from output.
Example Input:
Key V1 V2 V3
a. 1 2 5 3
b. 1 2 6 2
c. 1 2 7 4
d. 1 3 6 5
e. 2 8 8 8
f. 3 1 2 4
Example Output:
Key V1 V2 V3
a. 1 2 5 3
b. 1 2 6 2
e. 2 8 8 8
f. 3 1 2 4
- Input a < Input c ==> c removed
- Input a < Input d ==> d removed
I’ve been able to solve the above problem using for-loops, and if-statements. I am currently trying to solve this using gpu based cuda/thrust. Could this be done on the gpu (preferably thrust) or an individual kernel has to be written in cuda ?
I have not been to formulate this problem using unique as discussed in Thrust: Removing duplicates in key-value arrays
Edited to include program "stl/c++" program to generate above scenario: section "Reducing myMap" is my implementation using for-loops and if-statements.
#include <iostream>
#include <tr1/array>
#include <vector>
#include <algorithm>
struct mapItem {
mapItem(int k, int v1, int v2, int v3){
key=k;
std::tr1::array<int,3> v = {v1, v2, v3};
values=v;
};
int key;
std::tr1::array<int,3> values;
};
struct sortLexiObj{
bool operator()(const mapItem& lhs, const mapItem& rhs){
return lhs.values < rhs.values;
}
};
struct sortKey{
bool operator()(const mapItem& lhs, const mapItem& rhs){
return lhs.key < rhs.key;
}
};
int main(int argc, char** argv){
std::vector<mapItem> myMap;
// Set up initial matrix:
myMap.push_back(mapItem(3, 1, 2, 4));
myMap.push_back(mapItem(1, 2, 6, 2));
myMap.push_back(mapItem(1, 2, 5, 3));
myMap.push_back(mapItem(1, 3, 6, 5));
myMap.push_back(mapItem(2, 8, 8, 8));
myMap.push_back(mapItem(1, 2, 7, 4));
std::sort(myMap.begin(), myMap.end(), sortLexiObj());
std::stable_sort(myMap.begin(), myMap.end(), sortKey());
std::cout << "\r\nOriginal sorted Map" << std::endl;
for(std::vector<mapItem>::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){
std::cout << mt->key << "\t";
for(std::tr1::array<int,3>::iterator it=(mt->values).begin(); it!=(mt->values).end(); ++it){
std::cout << *it << " ";
}
std::cout << std::endl;
}
/////////////////////////
// Reducing myMap
for(std::vector<mapItem>::iterator it=myMap.begin(); it!=myMap.end(); ++it){
std::vector<mapItem>::iterator jt=it; ++jt;
for (; jt != myMap.end();) {
if ( (it->key == jt->key)){
if ( it->values.at(0) <= jt->values.at(0) &&
it->values.at(1) <= jt->values.at(1) &&
it->values.at(2) <= jt->values.at(2) ) {
jt = myMap.erase(jt);
}
else ++jt;
}
else break;
}
}
std::cout << "\r\nReduced Map" << std::endl;
for(std::vector<mapItem>::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){
std::cout << mt->key << "\t";
for(std::tr1::array<int,3>::iterator it=(mt->values).begin(); it!=(mt->values).end(); ++it){
std::cout << *it << " ";
}
std::cout << std::endl;
}
return 0;
}
