Как убрать нулевые значения из массива параллельно
Как я могу эффективно удалить нулевые значения из массива параллельно с помощью CUDA.
Информация о количестве нулевых значений доступна заранее,
что должно упростить эту задачу.
Важно, чтобы числа оставались упорядоченными как в исходном массиве,
при копировании в результирующий массив.
Пример:
Массив будет, например, содержат следующие значения:
[0, 0, 19, 7, 0, 3, 5, 0, 0, 1]
с дополнительной информацией, что 5 значений являются нулями.
Тогда желаемым конечным результатом будет другой массив, содержащий:
[19, 7, 3, 5, 1]
Решение
Для исключения некоторых элементов из массива вы можете использовать Уплотнительные операции библиотеки Thrust. Учитывая предикат is_not_zero, который возвращает false для нулевых значений и true для других, вы можете написать операцию, как это
thrust::copy_if(in_array, in_array + size, out_array, is_not_zero);
выходной массив будет содержать только те значения, которые не равны нулю, поскольку предикат указывает на это.
Вы также можете использовать функцию «remove_if» с обратным предикатом, который возвращает true для нулей и false для других..
thrust::remove_if(in_array, in_array + size, is_zero);
Я предлагаю вам взглянуть на примеры уплотнения библиотеки Thrust или общей концепции уплотнения.
http://code.google.com/p/thrust/source/browse/examples/stream_compaction.cu
Другие решения
Если вы не хотите использовать Thrust и предпочитаете использовать CUDA, возможно, лучше всего запустить Sum Scan, подробно описанную здесь.
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter36.html
Как насчет вариации нечетно-четной сортировки слиянием или фактически любого алгоритма сортировки, где порядок определяется a < b === (a != 0 && b == 0)?