Потоковый фильтр в cuda

Question

У меня есть массив значений и связанный список индексов.Теперь я хочу сохранить только те значения из массива, которые соответствуют индексам в LL.Есть ли стандартный алгоритм для этого.Пожалуйста, приведите пример, если это возможно

Итак, предположим, у меня есть массив 1,2,5,6,7,9, и у меня есть связанный список 2-> 3

Итак, я хочусохранить значения в индексах 2 и 3. То есть сохранить 5 и 6. Таким образом, моя функция должна возвращать 5 и 6

Answer 1

В общем, связанный список по своей сути является последовательным.Наличие параллельной машины не ускорит обход вашего списка, поэтому число шагов вашей проблемы не может быть меньше O (n), где n - размер списка.

Однако, если у вас естькакой-то дополнительный способ получить доступ к списку, вы можете сделать что-то с ним.Например, все элементы списка могут храниться в массиве фиксированного размера (хотя и не обязательно последовательно).Член списка может быть представлен в массиве с использованием следующей структуры:

struct ListNode {
    bool isValid;
    T data;
    int next;
}

Значение isValid устанавливается, если данная ячейка в массиве занята допустимым членом списка или это просто пустая ячейка.

Теперь параллельный алгоритм будет считывать все ячейки одновременно, проверять, представляют ли они действительные данные, и если да, что-то с ними делать.

Вторая часть: каждый поток, имеющий действительныеИндекс idx вашего входного массива A должен был бы пометить A[idx], чтобы его нельзя было удалить.Как только мы узнаем, какие элементы A должны быть удалены, а какие нет - можно применить алгоритм параллельного сжатия.