Я пытаюсь ускорить функцию popcount. Вот код:
extern ll LUT16[];
typedef long long ll;
typedef unsigned char* pUChar;
ll LUT16Word32Monobit(pUChar buf, int size) {
assert(buf != NULL);
assert(size > 0);
assert(size % sizeof(unsigned) == 0);
int n = size / sizeof(unsigned);
unsigned* p = (unsigned*)buf;
ll numberOfOneBits = 0;
for(int i = 0; i < n; i++) {
unsigned int val1 = p[i];
numberOfOneBits += LUT16[val1 >> 16] + LUT16[val1 & 0xFFFF];
}
return numberOfOneBits;
}
Вот несколько деталей:
Я пытался использовать openMP для ускорения, но это не работает. Я должен добавить, что я использую MS Visual Studio 2010 и что я включил директивы openMP. Я считаю, что одна из причин, по которой openMP не ускоряет процесс, связана с временем доступа к памяти. Можно ли как-нибудь использовать DMA (прямой доступ к памяти)?
Кроме того, я должен предупредить вас, что мои навыки openMP отсутствуют; здесь говорится о части openMP (вроде того же кода, что и выше):
#pragma omp for schedule(dynamic,CHUNKSIZE)
for(int i = 0; i < n; i++) {
unsigned int val1 = p[i];
numberOfOneBits += LUT16[val1 >> 16] + LUT16[val1 & 0xFFFF];
}
CHUNKSIZE установлен на 64. Если я установлю его ниже, результаты будут хуже, чем в последовательной версии, если я установлю его выше, это не принесет пользы.
Кроме того, я не хочу использовать инструкции popcount, которые предоставляют процессоры, ни инструкции SSE.
Ваш LUT16
массив 512 КБ (при условии long long
является 64-разрядным), что полностью разрушит производительность кэша L1 / L2 для произвольных / случайных данных (L1 обычно составляет 32 КБ, L2 обычно составляет 256 КБ).
Во-первых, вам не нужно long long
за это. Во-вторых, попробуйте LUT8
вместо. В-третьих, просто используйте встроенный __popcnt
внутренняя.
Других решений пока нет …