Busca Exaustiva com Thrust

A paralelização com Thrust seguiu a mesma lógica implementada do algoritmo da Busca Exaustivo original, porém adaptado para a estrutura da biblioteca Thrust. Então para isso, primeiro é feito a leitura de todos os dados em host_vectors (leitura mais rápida) que depois são copiados para device_vectors para serem realizadas as operações do Thrust. Com isso é inicializado um device_vector com tamanho (1 << n) e preenchido em sequência, ou seja, representa todas as permutações possíveis com o número de filmes que recebeu. Com isso feito, esse device_vector irá passar por um transform_reduce com a função customizada exhaustive_search que irá verificar se a permutação atual é válida e retornar o número de filmes que ela possui. Por fim, esse transform_reduce irá retornar o maior número de filmes que uma permutação possui, que é o resultado final. A lógica usada na função customizada exhaustive_search é a mesma do algoritmo original, porém adaptada para o uso de device_vectors e device_ptrs.

Implementação

#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <thrust/remove.h>
#include <thrust/extrema.h>
#include <thrust/sequence.h>
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/transform_reduce.h>
using namespace std;
struct exhaustive_search {
int n;
int c;
int* start;
int* end;
int* categories;
int* category_limit;
exhaustive_search(int n, int c, int* start, int* end, int* categories, int* category_limit)
: n(n), c(c), start(start), end(end), categories(categories), category_limit(category_limit) {};
__device__
int operator()(const int& possibility) {
int total_movies = 0;
int available_times[24];
for (int i = 0; i < 24; i++) {
available_times[i] = 1;
}
int possibility_category_limit[20];
for (int i = 0; i < c; i++) {
possibility_category_limit[i] = category_limit[i];
}
for (int i = 0; i < n; i++) {
if (possibility & (1 << i)) {
if (start[i] < end[i]) {
for (int j = start[i]; j < end[i]; j++) {
if (available_times[j] == 0) {
return 0;
}
}
if (possibility_category_limit[categories[i] - 1] > 0) {
possibility_category_limit[categories[i] - 1] -= 1;
for (int k = start[i]; k < end[i]; k++) {
available_times[k] = 0;
}
total_movies += 1;
} else {
return 0;
}
} else {
return 0;
}
}
}
return total_movies;
}
};
int main() {
int n, c;
cin >> n >> c;
thrust::host_vector<int> category_limit_cpu(c);
for (int i = 0; i < c; i++) {
cin >> category_limit_cpu[i];
}
thrust::host_vector<int> start_cpu(n);
thrust::host_vector<int> end_cpu(n);
thrust::host_vector<int> categories_cpu(n);
for (int i = 0; i < n; i++) {
cin >> start_cpu[i] >> end_cpu[i] >> categories_cpu[i];
}
thrust::device_vector<int> start_gpu(start_cpu);
thrust::device_vector<int> end_gpu(end_cpu);
thrust::device_vector<int> categories_gpu(categories_cpu);
thrust::device_vector<int> category_limit_gpu(category_limit_cpu);
thrust::device_vector<int> all_possibilities_gpu((1 << n));
int* start_gpu_ptr = thrust::raw_pointer_cast(start_gpu.data());
int* end_gpu_ptr = thrust::raw_pointer_cast(end_gpu.data());
int* categories_gpu_ptr = thrust::raw_pointer_cast(categories_gpu.data());
int* category_limit_gpu_ptr = thrust::raw_pointer_cast(category_limit_gpu.data());
auto start = std::chrono::high_resolution_clock::now();
thrust::sequence(all_possibilities_gpu.begin(), all_possibilities_gpu.end());
int max_films = thrust::transform_reduce(all_possibilities_gpu.begin(), all_possibilities_gpu.end(), exhaustive_search(n, c, start_gpu_ptr, end_gpu_ptr, categories_gpu_ptr, category_limit_gpu_ptr), 0.0, thrust::maximum<int>());
auto finish = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = finish - start;
cout << 2 << ' ' << n << ' ' << c << ' ' << max_films << ' ' << elapsed.count() << endl;
return 0;
}