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

Я использую 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, чтобы решить эту проблему?


openmp fortran thrust stream-compaction prefix-sum
person Pierpym    schedule 05.11.2014    source источник
comment
Я думаю, вам будет сложно написать программу OpenMP, чтобы превзойти A = pack(A,M==1). Я думаю, что накладные расходы на запись нескольких потоков в A убьют любое ускорение от распределения работы packing. Но я с нетерпением жду, чтобы оказаться неправым. Как Thrust решает проблему?   -  person High Performance Mark    schedule 05.11.2014
comment
Я мог бы и, возможно, должен был добавить к моему предыдущему комментарию, что я не знаю ни одной библиотеки для реализации распараллеленной версии встроенного pack в Fortran. Я полагаю, вам будет достаточно легко вызывать подпрограммы C++ из Thrust.   -  person High Performance Mark    schedule 05.11.2014
comment
Если ваш вектор очень-очень длинный, вы можете попробовать разделить его на несколько фрагментов в цикле OMP do и использовать pack для каждого подмножества. Вам нужно будет сохранить полученные подмножества независимо и объединить их в конце.   -  person damienfrancois    schedule 05.11.2014
comment
Во-первых, спасибо за ваш ответ. Я не знаю, как Thrust решает проблему, но я читал, что в этой библиотеке есть много API, которые выполняют такого рода операции (сокращения, префикс-суммы, переупорядочение и т. д.) в многопоточности для приложений GPU. Здесь (http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html) кажется, что нужно параллельное сканирование префикса, а затем скаттер, но я не понимаю, как это можно написать на фортране с помощью openmp. Встроенная функция Pack является последовательной, поэтому я не знаю, смогу ли я добиться лучшей производительности с большими массивами и большим количеством потоков (MIC или GPU).   -  person Pierpym    schedule 05.11.2014
comment
По моему убеждению, не подкрепленному доказательствами, время, необходимое вашему компьютеру для перемещения очень больших массивов между оперативной памятью хоста и оперативной памятью сопроцессора, перевешивает любую выгоду, которую вы могли бы получить от распараллеливания этой операции packing. Мне будет интересно увидеть ваши результаты, если вы пойдете по этому пути. Я думаю, что большая часть материала в URL-адресе, на который вы нам указываете, показывает преимущества использования параллельных алгоритмов, когда вы получили данные в ОЗУ графического процессора, но довольно скромно говорит о времени, необходимом для их перемещения туда и обратно.   -  person High Performance Mark    schedule 05.11.2014

Ответы (1)


arrow_upward
1
arrow_downward

Есть ли библиотека, такая как «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 относительно проста и полностью независима, поэтому вы можете использовать параллельный цикл выполнения OMP и разбивать работу любым способом. ты хочешь. Шаг 1 будет сложным, и я предлагаю следовать плану, представленному в главе, на которую вы и я ссылались. Код OMP потребует различных барьеров на пути, но его можно распараллелить.

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

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

person Robert Crovella    schedule 08.11.2014