Каким образом инструкции по обнаружению конфликтов облегчают векторизация циклов?

Question

Семейства команд AVX512CD: VPCONFLICT, VPLZCNT и VPBROADCASTM.

The Wikipedia section about these instruction говорит:

Инструкция по обнаружению AVX-512 конфликтов (AVX-512CD) являются разработана, чтобы помочь эффективно рассчитать бесконфликтных подмножества элементов в виде петель, которые обычно не могут быть безопасно векторизованными.

Каковы некоторые примеры, показывающие, что эта инструкция полезна в векторизации циклов? Было бы полезно, если бы ответы включали скалярные циклы и их векторизованные копии.

Спасибо!

Answer 1

Одним из примеров, где могут быть полезны инструкции CD, является гистограммирование. Для скалярного кода гистограммирование только простой цикл, как это:

load bin index 
load bin count at index 
increment bin count 
store updated bin count at index 

Обычно вы не можете векторизации гистограммирования потому что вы можете иметь один и тот же индекс бен больше, чем один раз в векторе - Вы могли бы наивным попробовать что-то вроде этого:

load vector of N bin indices 
perform gathered load using N bin indices to get N bin counts 
increment N bin counts 
store N updated bin counts using scattered store 

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

Так, CD инструкция к спасению:

load vector of N bin indices 
use CD instruction to test for duplicate indices 
set mask for all unique indices 
while mask not empty 
    perform masked gathered load using <N bin indices to get <N bin counts 
    increment <N bin counts 
    store <N updated bin counts using masked scattered store 
    remove non-masked indices and update mask 
end 

На практике этот пример не является малоэффективным и не лучше, чем скалярный код, но есть и другие более вычислительны ёмкие примеры, когда с помощью инструкции CD, кажется, стоит. Обычно это будут симуляции, в которых элементы данных будут обновляться недетерминированным образом. Один пример (из LAMMPS Molecular Dynamics Simulator) упоминается в KNL book by Jeffers et al.