Mam n
(8 bitów) ciągi znaków wszystkich z nich tej samej długości (np. m
) i innego ciągu s
o tej samej długości. Muszę obliczyć odległości Hamminga od s
do każdego z pozostałych ciągów. W czystym C, coś jak:Obliczanie odległości Hamminga na kilka ciągów za pomocą SSE
unsigned char strings[n][m];
unsigned char s[m];
int distances[n];
for(i=0; i<n; i++) {
int distances[i] = 0;
for(j=0; j<m; j++) {
if(strings[i][j] != s[j])
distances[i]++;
}
}
Chciałbym użyć instrukcji SIMD z gcc, aby bardziej efektywnie wykonać takie obliczenia. Przeczytałem, że PcmpIstrI
w SSE 4.2 może być przydatny, a mój komputer docelowy obsługuje ten zestaw instrukcji, więc wolałbym rozwiązanie z wykorzystaniem SSE 4.2.
EDIT:
napisałem następujących funkcji, aby obliczyć odległość Hamminga między dwa ciągi:
static inline int popcnt128(__m128i n) {
const __m128i n_hi = _mm_unpackhi_epi64(n, n);
return _mm_popcnt_u64(_mm_cvtsi128_si64(n)) + _mm_popcnt_u64(_mm_cvtsi128_si64(n_hi));
}
int HammingDist(const unsigned char *p1, unsigned const char *p2, const int len) {
#define MODE (_SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_EACH | _SIDD_BIT_MASK | _SIDD_NEGATIVE_POLARITY)
__m128i smm1 = _mm_loadu_si128 ((__m128i*) p1);
__m128i smm2 = _mm_loadu_si128 ((__m128i*) p2);
__m128i ResultMask;
int iters = len/16;
int diffs = 0;
int i;
for(i=0; i<iters; i++) {
ResultMask = _mm_cmpestrm (smm1,16,smm2,16,MODE);
diffs += popcnt128(ResultMask);
p1 = p1+16;
p2 = p2+16;
smm1 = _mm_loadu_si128 ((__m128i*)p1);
smm2 =_mm_loadu_si128 ((__m128i*)p2);
}
int mod = len % 16;
if(mod>0) {
ResultMask = _mm_cmpestrm (smm1,mod,smm2,mod,MODE);
diffs += popcnt128(ResultMask);
}
return diffs;
}
Więc mogę rozwiązać mój problem za pomocą:
for(i=0; i<n; i++) {
int distances[i] = HammingDist(s, strings[i], m);
}
Czy to co mogę zrobić, czy mogę skorzystać z tego, że jeden z porównywanych łańcuchów jest zawsze taki sam? Ponadto, czy powinienem wykonać pewne wyrównanie na moich tablicach, aby poprawić wydajność?
kolejna próba
Po rekomendacji Harolda, napisałem poniższy kod:
void _SSE_hammingDistances(const ByteP str, const ByteP strings, int *ds, const int n, const int m) {
int iters = m/16;
__m128i *smm1, *smm2, diffs;
for(int j=0; j<n; j++) {
smm1 = (__m128i*) str;
smm2 = (__m128i*) &strings[j*(m+1)]; // m+1, as strings are '\0' terminated
diffs = _mm_setzero_si128();
for (int i = 0; i < iters; i++) {
diffs = _mm_add_epi8(diffs, _mm_cmpeq_epi8(*smm1, *smm2));
smm1 += 1;
smm2 += 1;
}
int s = m;
signed char *ptr = (signed char *) &diffs;
for(int p=0; p<16; p++) {
s += *ptr;
ptr++;
}
*ds = s;
ds++;
}
}
ale nie jestem w stanie zrobić ostateczny dodatek bajtów w __m128i
za pomocą psadbw
. Czy ktoś może mi w tym pomóc?
Czym dokładnie jest Twoje pytanie? – andy256
W rzeczywistości 'pcmpistri' nie jest w ogóle użyteczny, w tej sytuacji wszystko czego potrzebujesz to zwykły stary' pcmpeqb'. I nie potrzebujesz żadnego z tych popcnt-stuff, po prostu odejmij wynik porównania od zliczenia (ponieważ wynikiem jest -1, gdzie są różne) i "psadbw" je na końcu (lub jeśli twoje struny są 4K długie lub dłuższe, 'psadbw' tuż przed przetworzeniem 4K bajtów) – harold
Dzięki Harold, opublikowałem moją próbę chociaż nie byłem w stanie używać psadbw. – pepeStck