CUDA: сортировка массива в соответствии с порядком, определенным другим массивом с использованием команды thrust. - PullRequest
Новая
       45

CUDA: сортировка массива в соответствии с порядком, определенным другим массивом с использованием команды thrust.

0 голосов
/ 27 августа 2018

У меня есть 10 массивов. Я хочу отсортировать их. Но поскольку их элементы имеют одинаковое поведение, я хочу сохранить вычисления и отсортировать только одно, а остальные будут отсортированы на основе отсортированного массива. Я использую тягу. Есть оптимальный, зачем это делать? Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 28 августа 2018

Из комментариев мое предложение было:

Используйте thrust::sort_by_key для первого набора данных (массива), передавая первый набор данных в качестве ключей и индексную последовательность (0, 1, 2, ...) в качестве значений. Затем используйте переупорядоченную индексную последовательность в операции сбора или рассеивания тяги, чтобы переставить остальные массивы.

В соответствии с запросом, вот рабочий пример: 

$ cat t282.cu
#include <thrust/sort.h>
#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <thrust/copy.h>
#include <thrust/sequence.h>
#include <iostream>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/zip_iterator.h>

const size_t ds = 5;
typedef float ft;

int main(){
  ft a1[ds] = {0.0f, -3.0f, 4.0f, 2.0f, 1.0f};
// data setup
  thrust::device_vector<ft> d_a1(a1, a1+ds);
  thrust::device_vector<ft> d_a2(ds);
  thrust::device_vector<ft> d_a3(ds);
  thrust::device_vector<ft> d_a2r(ds);
  thrust::device_vector<ft> d_a3r(ds);
  thrust::device_vector<size_t> d_i(ds);
  thrust::sequence(d_i.begin(), d_i.end());
  thrust::sequence(d_a2.begin(), d_a2.end());
  thrust::sequence(d_a3.begin(), d_a3.end());
// sort
  thrust::sort_by_key(d_a1.begin(), d_a1.end(), d_i.begin());
// copy, using sorted indices
  thrust::copy_n(thrust::make_permutation_iterator(thrust::make_zip_iterator(thrust::make_tuple(d_a2.begin(), d_a3.begin())), d_i.begin()), ds, thrust::make_zip_iterator(thrust::make_tuple(d_a2r.begin(), d_a3r.begin())));
// output results
  thrust::host_vector<ft> h_a1 = d_a1;
  thrust::host_vector<ft> h_a2 = d_a2r;
  thrust::host_vector<ft> h_a3 = d_a3r;
  std::cout << "a1: " ;
  thrust::copy_n(h_a1.begin(), ds, std::ostream_iterator<ft>(std::cout, ","));
  std::cout << std::endl << "a2: " ;
  thrust::copy_n(h_a2.begin(), ds, std::ostream_iterator<ft>(std::cout, ","));
  std::cout << std::endl << "a3: " ;
  thrust::copy_n(h_a3.begin(), ds, std::ostream_iterator<ft>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t282 t282.cu
$ cuda-memcheck ./t282
========= CUDA-MEMCHECK
a1: -3,0,1,2,4,
a2: 1,0,4,3,2,
a3: 1,0,4,3,2,
========= ERROR SUMMARY: 0 errors
$

Здесь, вместо операции thrust::gather или thrust::scatter, я просто делаю thrust::copy_n с thrust::permutation_iterator, чтобы выполнить переупорядочение. Я объединяю оставшиеся массивы, которые нужно переупорядочить, используя thrust::zip_iterator, но это не единственный способ сделать это.

Обратите внимание, что я делаю это не для 10 массивов, а для 3, однако это должно проиллюстрировать метод. Расширение до 10 массивов должно быть просто механическим. Однако обратите внимание, что метод должен быть несколько изменен для более чем 10-11 массивов, так как thrust::tuple ограничен 10 элементами. В качестве модификации вы можете просто вызвать thrust::copy_n в цикле, один раз для каждого переупорядочиваемого массива, вместо использования zip_iterator. Я не думаю, что это должно иметь большое значение в эффективности.

0 голосов
/ 27 августа 2018

Несколько способов сделать это (независимо от тяги):

  1. 1005 *

    1. Инициализировать массив индексов indices до 0, 1, 2, 3... и т. Д.
    2. Сортировка indices, с функцией сравнения, осуществляющей доступ к элементам в одном из массивов (тот, для которого сравнения являются самыми дешевыми), и сравнение их. Вызвать полученный массив
    3. Для каждого из 10 массивов arr примените операцию Gather, используя отсортированные indices и arr в качестве данных, из которых необходимо собрать данные. т.е. sorted_arr[i] = arr[indices[i]] для всех i.

  2. 1025 *

    1. Адаптируйте одну из реализаций сортировки так, чтобы она также выполняла "ведение журнала индекса", то есть всякий раз, когда вы меняете или размещаете данные в "реальном" массиве, также устанавливаете индекс в массиве индексов.
    2. Запустите эту сортировку с сохранением индекса на одном из 10 массивов (самый дешевый для сортировки).
    3. Применить Сбор от 1,3 к другим 9 массивам

  3. Пусть cheap будет самым дешевым массивом для сортировки (или сравнения элементов)

    1. Создание массива пар pairs[i] = { i, cheap[i] } соответствующего типа.
    2. У сравнения этих пар используйте только второй элемент пары.
    3. Сортировка pairs
    4. Проект pairs на свой первый элемент: indices[i] = pairs[i].first
    5. Проецируйте pairs на второй элемент: sorted_cheap[i] = pairs[i].second
    6. Применить Сбор от 1,3 к другим девяти массивам

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

...