Сжатие потока (или упаковка в массив) с префиксным сканированием с использованием Openmp

Question

Я использую openmp для распараллеливания моего кода. У меня есть оригинальный массив:

A=[3,5,2,5,7,9,-4,6,7,-3,1,7,6,8,-1,2]

и массив меток:

M=[1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1]

используя массив M, я могу сжать мой оригинальный массив в этот упакованный массив:

A=[3,2,-4,-3,1,-1,2]

Я хотел бы решить эту проблему, используя многопоточный подход. Библиотека Thrust для C++ решает эту проблему, но я не могу найти аналогичные инструменты для Fortran. Существует ли библиотека, подобная 'thrust' для C++, которую я могу использовать для выполнения сжатия потока? Кроме того, есть ли алгоритм, который я могу написать сам, используя Fortran и OpenMP, чтобы решить эту проблему?

Answer 1

Существует ли библиотека, подобная 'thrust' для C++, которую я могу использовать для выполнения сжатия потока?

Не должно быть так сложно вызывать подпрограмму тяги из Фортрана (если вы готовы написать немного кода на C++). Кроме того, тяга может быть нацелена на бэкэнд OMP вместо бэкэнда GPU.

Кроме того, есть ли алгоритм, который я могу написать сам, используя Fortran и OpenMP, чтобы решить эту проблему?

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

1. Выполните параллельную сумму префикса (включительно сканирование) на M массив:

    M=[1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1]
   sM=[1,1,2,2,2,2,3,3,3,4,5,5,5,5,6,7]
   

2. Затем каждый поток проверяет свой элемент в M массив, и если этот элемент не равен нулю, он скопирует соответствующий элемент в A массив в выходной массив (назовем его O):

    M=[1,0,1,0,0,0, 1,0,0, 1,1,0,0,0, 1,1]
   sM=[1,1,2,2,2,2, 3,3,3, 4,5,5,5,5, 6,7]
    A=[3,5,2,5,7,9,-4,6,7,-3,1,7,6,8,-1,2]
    O=[3,  2,      -4,    -3,1,      -1,2]
   

Если вы делали это в OMP, вам потребуется барьер OMP между шагами 1 и 2. Работа на шаге 2 относительно проста и полностью независима, поэтому вы можете использовать параллельный цикл do OMP и разбить работу любым способом. ты хочешь. Шаг 1 будет сложным, и я предлагаю следовать плану, приведенному в главе, которую мы с вами связали. Код OMP там потребует различных барьеров на этом пути, но он распараллелен.

Как уже упоминалось в комментариях, если это единственная часть работы, которую вы хотите распараллелить, я бы не рекомендовал GPU, потому что стоимость передачи данных в / из GPU, вероятно, перевесила бы любые преимущества параллельного выполнения, которые вы могли бы нарастают. Но, как я уже упоминал, тяга может быть нацелена на реализацию OMP, а не на реализацию GPU. Возможно, стоит попробовать.

Что касается тяги от Фортрана, большая часть того, что вам нужно, здесь. Это по общему признанию CUDA fortran, но единственными отличиями должно быть не использование атрибута устройства, а использование thrust::host_vector вместо thrust::device_vector (по крайней мере, для начала).