На этом шаге мы рассмотрим алгоритмы.

В библиотеке Thrust реализованы следующие алгоритмы:

Трансформация (Transformations);
Редукция (Reductions);
Нахождение префикс-сумм массива (Prefix-Sums);
Алгоритмы изменения порядка (Reordering);
Алгоритмы сортировки (Sorting).

Приведем примеры, демонстрирующие возможности алгоритмов библиотеки Thrust.

Пример 1. Трансформация

#include <thrust/device_vector.h>
#include <thrust/transform.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/fill.h>
#include <thrust/replace.h>
#include <thrust/functional.h>
#include <iostream>

int main(void){
 //Создаем 3 вектора в памяти видеокарты
 thrust::device_vector<int> X(10);
 thrust::device_vector<int> Y(10);
 thrust::device_vector<int> Z(10);

 //Заполняем вектор числами 0, 1, 2, и т.д.
 thrust::sequence(X.begin(), X.end());

 //Помещаем в вектор Y элементы вектора X, умноженные на -1 
 thrust::transform(X.begin(), X.end(), Y.begin(), thrust::negate<int>());

 //Заполняем вектор Z значением равным 2
 thrust::fill(Z.begin(), Z.end(), 2);

 //Умножаем каждый элемент вектора X на соответсвующий ему элемент вектора Z 
 //и результат помещаем в вектор Y
 thrust::transform(X.begin(),X.end(),Z.begin(),Y.begin(),thrust::modulus<int>());

 //Изменяем все элементы вектора Y, равные 1, на значение 10
 thrust::replace(Y.begin(), Y.end(), 1, 10);
 
 //Выводим содержимое вектора Y на экран, 
 //используя функцию копирования и потоковый итератор
 thrust::copy(Y.begin(),Y.end(),std::ostream_iterator<int>( std::cout,"\n"));

 return 0;
}

/*
Результат выполнения программы:
0
10
0
10
0
10
0
10
0
10
*/

Полный текст приложения можно взять здесь.

Опишем каждую из функций.

sequence - функция заполнения элементов вектора, рассположенных между 1-м и 2-м параметрами, значениями, равными порядковому номеру;
transform - функция применяет операцию (последний параметр) для каждого элемента, расположенного между 1-м и 2-м параметром, и результат помещается в 3-й параметр (если задана унарная операция, например операция умножения на число). Если задана бинарная операция (например, операция взятия остатка (modulus)), то в качестве третьего параметра задается начало 2-го операнда операции, а результат помещается в 4-й параметр;
fill - функция заполнения данных, расположенных между итераторами begin() и end(), значением третьего параметра;
replace - функция замены всех элементов равных 3-му параметру на значение 4-го параметра, которые расположены между 1-м и 2-м параметрами;
copy - функция копирования данных, расположенных между итераторами begin() и end(), в 3-й параметр.

Пример 2. Редуцирование

#include <thrust/device_vector.h>
#include <thrust/reduce.h>
#include <thrust/functional.h>
#include <cstdio>
using namespace std;

const int N = 512 * 512 * 512;

int main(){
 //Создаем вектор из N элементов и инициализируем его единицами
 thrust::device_vector<float> X(N, 1);

 //Посчитаем паралельно сумму всех элементов, используя функцию reduce
 float result = thrust::reduce(X.begin(), X.end());	

 //Выведем на экран результат
 printf("%.10f", result);
 return 0;
}

/*
Результат выполнения программы:
134217728.0000000000
*/

Полный текст приложения можно взять здесь.

Параллельная редукция является одной из часто встречающихся операций над массивами. В общем случае данная операция формулируется следующим образом:

Пусть заданы массив a₀, a₁, a₂, ... , a_n-1 и некоторая бинарная ассоциативная операция. В качестве такой операции мы рассматрели операцию сложения, однако данная операция может быть умножением, минимумом или максимум из двух чисел и т.п.

Тогда редукцией массива a₀, a₁, a₂, ... , a_n-1 относительно операции сложения будет следующая величина (фактически это просто сумма всех элементов массива): A = ((...(a₀ + a₁) + ... + a_n-2) + a_n-1.

Данная фунция reduce принимает 2 параметра (на самом деле она может иметь больше параметров, смотри документацию):

начало участка редуцирования;
конец участка редуцирования.

По умолчанию используется операция суммирования, но можно в качестве операции (3-й параметр) указать, например, операцию взятия максимума.

Пример 3. Нахождение префикс-суммы массивов.

#include <thrust/scan.h>
#include <cstdio>
  
int main(){
 //Создадим два массива	
 int data1[6] = {1, 0, 2, 2, 1, 3};
 int data2[6] = {1, 0, 2, 2, 1, 3};

 //Посчитаем префикс - сумму данных массивов
 thrust::inclusive_scan(data1, data1 + 6, data1);
 thrust::exclusive_scan(data2, data2 + 6, data2);

 //Выведем на экран содержимое первого массива
 for (int i = 0; i < 6; ++i){
  printf("%d ", data1[i]);   
 } 
 printf("\n");

 //Выведем на экран содержимое второго массива
 for (int i = 0; i < 6; ++i){
  printf("%d ", data2[i]);   
 } 
 printf("\n");
 
 return 0;
}

/*
Результат выполнения программы:
1 1 3 5 6 9 
0 1 1 3 5 6 
*/

Полный текст приложения можно взять здесь.

Различие между функциями inclusive_scan и exclusive_scan заключается только в том, что в первом случае результат будет размещаться с 0-го элемента, а во втором случае - с 1-го, при этом в 0-й элемент будет записано число 0.

Пример 4. Алгоритмы сортировки

#include <thrust/sort.h>
#include <cstdio>

const int N = 6;

//Создадим массив из N элементов
int a[N] = {1, 4, 2, 8, 5, 7};

//Функция вывода массива на экран
void PRINT( ){
 for(int i = 0; i < N; ++i){
  printf("%d ", a[i]); 
 } 
 printf("\n");
}

int main(){
 //Отсортируем массив и выведем его содержимое на экран
 thrust::sort(a, a + N);
 printf("sort a: ");
 PRINT();
 
 //Отсортируем элементы массива в обратном порядке и выведем его содержимое на экран
 thrust::stable_sort(a, a + N, thrust::greater<int>());
 printf("\nstable_sort a: ");
 PRINT(); 
	

 int keys[N] = {1, 4, 2, 8, 5, 7};
 char values[N] = {'a', 'b', 'c', 'd', 'e', 'f'};

 //Отсортируем массив values, используя ключи - элементы массива keys
 //т.е. на первом месте в массиве values будет стоять элемент с наименьшим ключем, 
 //на последнем месте - с наибольшим
 thrust::sort_by_key(keys, keys + N, values);

 //Выведем содержимое массива values на экран
 printf("\nsort_by_key values: ");
 for(int i = 0; i < N; ++i){
  printf("%c ", values[i]);
 }
 printf("\n");

 return 0;
}

/*
Результат выполнения программы:
sort a: 1 2 4 5 7 8 

stable_sort a: 8 7 5 4 2 1 

sort_by_key values: a c b e f d 
*/

Полный текст приложения можно взять здесь.

На следующем шаге мы рассмотрим итераторы.

Предыдущий шаг Содержание Следующий шаг