Как оптимизировать статистику гистограммы с помощью неоновых присадок?

Question

Я хочу оптимизировать статистический код гистограммы с помощью неоновых встроенных функций. Но мне это не удалось. Вот код c:

#define NUM (7*1024*1024)
uint8 src_data[NUM];
uint32 histogram_result[256] = {0};
for (int i = 0; i < NUM; i++)
{
    histogram_result[src_data[i]]++;
}

Статистика по гисторам больше похожа на последовательную обработку. С неоновыми внутренностями сложно оптимизировать. Кто-нибудь знает, как оптимизировать? Заранее спасибо.

Answer 1

Вы не можете векторизовать хранилища напрямую, но вы можете конвейеризовать их, и вы можете векторизовать вычисление адресов на 32-битных платформах (и в меньшей степени на 64-битных платформах).

Первое, что вы захотите сделать, для чего на самом деле не требуется NEON, это развернуть массив гистограмм, чтобы вы могли иметь больше данных в полете одновременно:

#define NUM (7*1024*1024)
uint8 src_data[NUM];
uint32 histogram_result[256][4] = {{0}};
for (int i = 0; i < NUM; i += 4)
{
    uint32_t *p0 = &histogram_result[src_data[i + 0]][0];
    uint32_t *p1 = &histogram_result[src_data[i + 1]][1];
    uint32_t *p2 = &histogram_result[src_data[i + 2]][2];
    uint32_t *p3 = &histogram_result[src_data[i + 3]][3];
    uint32_t c0 = *p0;
    uint32_t c1 = *p1;
    uint32_t c2 = *p2;
    uint32_t c3 = *p3;
    *p0 = c0 + 1;
    *p1 = c1 + 1;
    *p2 = c2 + 1;
    *p3 = c3 + 1;
}

for (int i = 0; i < 256; i++)
{
    packed_result[i] = histogram_result[i][0]
                     + histogram_result[i][1]
                     + histogram_result[i][2]
                     + histogram_result[i][3];
}

Обратите внимание, что p0 в p3 никогда не может указывать на один и тот же адрес, поэтому изменение порядка их чтения и записи просто отлично.

Из этого вы можете векторизовать расчет p0 в p3 с внутренними, и вы можете векторизовать цикл завершения.

Проверьте это как есть (потому что я этого не сделал!). Затем вы можете поэкспериментировать с структурированием массива как result[4][256] вместо result[256][4]или используя меньший или больший коэффициент развертывания.

Применяя некоторые NEON-свойства к этому:

uint32 histogram_result[256 * 4] = {0};
static const uint16_t offsets[] = { 0x000, 0x001, 0x002, 0x003,
                                    0x000, 0x001, 0x002, 0x003 };
uint16x8_t voffs = vld1q_u16(offsets);
for (int i = 0; i < NUM; i += 8) {
    uint8x8_t p = vld1_u8(&src_data[i]);
    uint16x8_t p16 = vshll_n_u8(p, 16);
    p16 = vaddq_u16(p16, voffs);
    uint32_t c0 = histogram_result[vget_lane_u16(p16, 0)];
    uint32_t c1 = histogram_result[vget_lane_u16(p16, 1)];
    uint32_t c2 = histogram_result[vget_lane_u16(p16, 2)];
    uint32_t c3 = histogram_result[vget_lane_u16(p16, 3)];
    histogram_result[vget_lane_u16(p16, 0)] = c0 + 1;
    c0 = histogram_result[vget_lane_u16(p16, 4)];
    histogram_result[vget_lane_u16(p16, 1)] = c1 + 1;
    c1 = histogram_result[vget_lane_u16(p16, 5)];
    histogram_result[vget_lane_u16(p16, 2)] = c2 + 1;
    c2 = histogram_result[vget_lane_u16(p16, 6)];
    histogram_result[vget_lane_u16(p16, 3)] = c3 + 1;
    c3 = histogram_result[vget_lane_u16(p16, 7)];
    histogram_result[vget_lane_u16(p16, 4)] = c0 + 1;
    histogram_result[vget_lane_u16(p16, 5)] = c1 + 1;
    histogram_result[vget_lane_u16(p16, 6)] = c2 + 1;
    histogram_result[vget_lane_u16(p16, 7)] = c3 + 1;
}

Если развернуть массив гистограмм x8, а не x4, вы можете использовать восемь скалярных аккумуляторов вместо четырех, но вы должны помнить, что это подразумевает восемь регистров подсчета и восемь регистров адресов, что больше регистров, чем у 32-битного ARM (поскольку вы не могу использовать SP и ПК).

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