Существует несколько допустимых вариантов использования связанных списков на графическом процессоре.Подумайте об использовании списка пропусков в качестве альтернативы, поскольку они обеспечивают более быстрые операции.Существуют примеры очень параллельных алгоритмов списка пропусков, доступных через поиски Google.
Проверьте эту ссылку http://www.cse.iitk.ac.in/users/mainakc/lockfree.html/ для кода CUDA в формате PDF и PPT для ряда структур данных CUDA без блокировок.
Списки ссылок могут создаваться параллельно с использованием алгоритма сокращения.Это предполагает, что ВСЕ члены известны во время строительства.Каждый поток начинается с подключения 2 узлов.Затем половина потоков соединяет 2 сегмента узла вместе и так далее, сокращая число потоков на 2 на каждую итерацию.Это создаст список в log2 N.
Ограничение памяти - ограничение.Предварительно выделите все узлы в массиве на хосте.Тогда вы можете использовать индексы массива вместо указателей.Это имеет то преимущество, что обход списка действителен на GPU и хосте.
Для параллелизма вам нужно использовать атомарные операции CUDA.Атомарное добавление / приращение для подсчета узлов, используемых из массива узлов, и сравнение и замена для установки связей между узлами.
Снова внимательно рассмотрите вариант использования и шаблоны доступа.Использование одного большого связанного списка очень последовательное.Использование 100 - 100-х из небольшого связанного списка более параллельно.Я ожидаю, что доступ к памяти будет незакрытым, если только не будут предприняты меры для выделения подключенных узлов в смежных местах памяти.