векторные инструкции ("vcl" и "ume") для подсчета сортировки - PullRequest
Новая
       38

векторные инструкции ("vcl" и "ume") для подсчета сортировки

0 голосов
/ 08 июня 2019

Я пробую векторную инструкцию, используя библиотеки "vcl" и "ume" для своего рода сортировки, которая возвращает только позицию 

// icpc sort.cpp -xCORE_AVX2 -o c
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "vcl/vectorclass.h"
#include "umesimd/UMESimd.h"
using namespace UME::SIMD;

int main(void) {
    //scalar version as example __________________________________________
    int s0[4], k0 = 0, x0[4] = { 9,
                                 1,
                                 2,
                                 1};
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++)
            if (x0[j] == i) {
                s0[k0] = j;
                k0++; }
    for (int j = 0; j < 4; j++) printf("%i\n", s0[j]); printf("\n");

    int a[32] = {9, 1,  5,  2,  1,  6,  3,  5,
                1,  4,  0,  3,  4,  7,  1,  1,
                2,  2,  1,  4,  4,  7,  2,  5,
                1,  4,  0,  1,  6,  4,  6,  5};
    //vcl version _____________________________________________________________________
    Vec8i s1[4] = 0, k1 = 0, x1[4]; Vec8ib msk1;
    x1[0].load(a);  x1[1].load(a + 8);  x1[2].load(a + 16); x1[3].load(a + 24);
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", x1[i].extract(j)); printf("\n"); } printf("\n");
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++) {
            msk1 = (x1[j] == i);
            //s1[k1] = select(msk1, j, s1);
            k1 = select(msk1, k1 + 1, k1); }
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", s1[i].extract(j)); printf("\n"); } printf("\n");

    //ume version ______________________________________________________________________
    SIMD8_32i s2[4] = 0, k2 = 0, x2[4]; SIMDMask8 msk2;
    x2[0].load(a); x2[1].load(a + 8); x2[2].load(a + 16); x2[3].load(a + 24);
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", x2[i].extract(j)); printf("\n"); } printf("\n");
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++) {
            msk2 = x2[j].cmpeq(i);
            //s2[k2].assign(msk2, j);
            k2.assign(msk2, k2 + 1); }
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", s2[i].extract(j)); printf("\n"); } printf("\n");

    return 0;
}

к сожалению, я не могу найти решение ни для одной избиблиотеки и мне нужна помощь, чтобы решить ее (закомментированные строки)

1 Ответ

0 голосов
/ 08 июня 2019

Сложной частью Counting Sort является проблема гистограммы.

Гистограммы сложны для SIMD, потому что вам требуется собирать нагрузки и разбросать хранилища, а также обнаруживать конфликты (где ваш вектор входных элементов имеет дубликаты, поэтому вам нужно увеличивать один и тот же интервал несколько раз). х86 имеет только это с AVX512.

Без сбора / разброса / обнаружения конфликтов есть скалярные трюки, которые полезны для небольшого количества сегментов. например повторение массива счетчиков 4 раза для устранения узких мест при пересылке данных в хранилище / перезагрузке, если появляется один и тот же входной номер, который некоторое время составляет большую часть входных данных. (При неисполнении заказа он не должен быть на 100% непрерывным, чтобы вызвать проблему.)

Вы можете использовать SIMD для суммирования массивов сегментов в конце, например, _mm256_add_epi32 для 32-битных счетчиков. Существует некоторая область для ручной SIMD-оптимизации части memset / std::fill производства отсортированного вывода, но обычно это не медленная часть.

Дальнейшее чтение:

...