Распараллеливание последовательного цикла for для GPU
У меня есть цикл for, где текущий индекс вектора зависит от предыдущих индексов, которые я пытаюсь распараллелить для GPU в MATLAB.
- A является известным вектором nx1
- B - выходной вектор nx1, который инициализируется нулями.
Код выглядит следующим образом:
for n = 1:size(A)
B(n+1) = B(n) + A(n)*B(n) + A(n)^k + B(n)^2
end
Я посмотрел на этот похожий вопрос и попытался найти простую замкнутую форму для рекуррентного отношения, но не смог ее найти.
Я мог бы сделать префиксную сумму, как упомянуто в первой ссылке над термином A(n)^k, но я надеялся, что будет другой способ ускорить цикл.
Любой совет приветствуется!
PS В моем реальном коде используются трехмерные массивы, которые индексируют и суммируют вдоль 2D-срезов, но любая помощь в одномерном случае должна перейти на 3D-масштабирование.
1 ответ
Слово "распараллеливание" звучит волшебно, но применяются правила планирования:
Ваша проблема не в том, чтобы тратить усилия на то, чтобы превратить чистый SEQ -процесс в это PAR -представление, но при покрытии расходов на это, если вы действительно настаиваете на PAR любой ценой.
m = size(A); %{
+---+---+---+---+---+---+---+---+---+---+---+---+---+ .. +---+
const A[] := | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | | M |
+---+---+---+---+---+---+---+---+---+---+---+---+---+ .. +---+
:
\
\
\
\
\
\
\
\
\
\
\
+---+---+---+---+---+ .. + .. +---+---+---+---+---+ .. +---+
var B[] := | 0 | 0 | 0 | 0 | 0 | : | 0 | 0 | 0 | 0 | 0 | | 0 |
+---+---+---+---+---+ .. : .. +---+---+---+---+---+ .. +---+ }%
%% : ^ :
%% : | :
for n = 1:m %% : | :
B(n+1) =( %% ====:===+ : .STO NEXT n+1
%% : :
%% v :
B(n)^2 %% : { FMA B, B, .GET LAST n ( in SEQ :: OK, local data, ALWAYS )
+ B(n) %% v B } ( in PAR :: non-local data. CSP + bcast + many distributed-caches invalidates )
+ B(n) * A(n) %% { FMA B, A,
+ A(n)^k %% ApK}
);
end
Однажды SEQ -процесс-зависимость от данных является периодической (необходимость повторного использования LAST B(n-1) за назначение СЛЕДУЮЩЕГО B(n) Любая попытка сделать такое SEQ расчетная работа в PAR придется ввести общесистемную связь известных значений, прежде чем "новые" значения могут быть вычислены только после соответствующего "предыдущего" B(n-1) был оценен и назначен - через чистый серийный номер SEQ цепочка повторяющихся вычислений, таким образом, не до того, как все предыдущие ячейки будут обработаны последовательно - поскольку фрагмент LAST всегда необходим для шага NEXT, ref. "перекресток" в for() -loop итератор зависимость-карта (имея это, все остальные должны ждать в "очереди", чтобы иметь возможность сделать их два примитива .FMA -s + .STO результат для следующего в рекуррентной внушаемой "очереди").
Да, можно "принудительно" применить формулу к выполнению PAR, но сами затраты на такие значения LAST передаются "через" PAR - структура исполнения (по направлению к NEXT), как правило, чрезмерно дорогая (с точки зрения ресурсов и накопленных задержек) - либо повреждает маскирование задержки планировщика, оптимизированное для SIMT, либо блокирует все потоки до тех пор, пока не будет получено значение LAST, присвоенное "соседу", что они полагаются на это и не могут действовать, не получив его первыми, что фактически разрушает любую потенциальную выгоду от всех усилий, вложенных в PAR).
Даже просто пара FMA -s недостаточно кода, чтобы оправдать затраты на надстройки - действительно, очень малый объем работы - для всех PAR усилия.
Если не будет какой-то очень математически "плотной" обработки, все дополнительные затраты не будут легко скорректированы, и такая попытка ввести PAR Режим вычислений демонстрирует только отрицательный (отрицательный) эффект вместо любого желаемого ускорения. Во всех профессиональных случаях следует выразить все дополнительные расходы на этапе проверки концепции (PoC), прежде чем принимать решение о целесообразности какой-либо реализации. PAR -подход возможен вообще, и как добиться ускорения >> 1,0 х
Полагаться на только что объявленные теоретические GFLOPS и TFLOPS - нонсенс. Ваше настоящее GPU-ядро никогда не сможет повторить показатели производительности объявленных тестов (если вы не используете точно такой же оптимизированный макет и код, который вам не нужен, не так ли?). Как правило, нужно вычислить собственную специфическую алгоритмизацию, связанную с проблемной областью, не желая искусственно выравнивать все элементы задачи-игрушки, чтобы графическому процессору не приходилось ждать реальных данных и иметь возможность настраивать кэш / основанные на регистре ILP-артефакты, практически не достижимые в большинстве реальных проблемных решений). Если есть один шаг, чтобы порекомендовать - всегда оценивайте PoC, оправдывающий накладные расходы, прежде чем посмотреть, есть ли такая возможность для ускорения, прежде чем тратить ресурсы и тратить время и деньги на создание прототипа детального проектирования и тестирования.
Периодическая и слабая обработка полезных нагрузок ядра GPU почти в каждом случае будет изо всех сил, чтобы отрегулировать, по крайней мере, их дополнительные издержки (двунаправленная передача данных ( H2D + D2H) + нагрузки, связанные с кодом ядра).