Параллелизированная малая сеть

Question

Я работал над сетью (для массивов меньше 8) и заметил, что все алгоритмы сосредоточены на его способности разрешать параллельные операции. Вот один такой набор для массива размером 5.

 #define SWAP(x,y) if (data[y] < data[x]) { int tmp = data[x]; data[x] = data[y]; data[y] = tmp; }

    //Parallelizable
    SWAP(1, 2);
    SWAP(4, 5);

    //Parallelizable
    SWAP(0, 2);
    SWAP(3, 5);

    //Parallelizable
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(2, 5);

    //Parallelizable
    SWAP(0, 3);
    SWAP(1, 4);

    //Parallelizable
    SWAP(2, 4);
    SWAP(1, 3);

    //Parallelizable
    SWAP(2, 3);

Я работал с long int массивы (таким образом, каждый элемент имеет размер 8 байт). Так есть ли простой способ распараллелить эти операции в C? Есть ли какие-либо аппаратные команды, которые я могу использовать для достижения этой цели (SIMD, ASM(x86) и т. Д.)

Answer 1

Как объясняется в этом ответе на вопрос о сортировке небольших коллекций, вы можете сделать свой код подкачки более производительным, изменив его определение на следующее:

#define SWAP(x, y) {                        \
    int dx = data[x];                       \
    data[x] = dx < data[y] ? dx : data[y];  \
    data[y] ^= dx ^ data[x];                \
}

Согласно исследованию " Применение сортировочных сетей для синтеза оптимизированных библиотек сортировки", эта версия SWAP не имеет ответвлений и сводится к простым 5 инструкциям по GCC или Clang с достойным уровнем оптимизации. Статья также намекает на тот факт, что небольшое количество инструкций может фактически принести выгоду коду от параллелизма на уровне инструкций.

Если xor не работает для сортировки типов, вы можете использовать альтернативную версию SWAP который использует два условия вместо одного, что должно быть почти так же быстро, как xor версия. На самом деле, я использую этот трюк в моей библиотеке сортировки, и сортировка небольшой коллекции целых чисел фиксированного размера с сетками сортировки перешла от "не совсем лучше, чем сортировка по вставке" к "в несколько раз быстрее, чем сортировка по вставке", когда я представил эту хитрость. Сортировка набора из 8 целых чисел происходит в ~5 раз быстрее при сортировке сетей, чем при сортировке вставками на моем компьютере.