Внедряване на бърз брояч в код с паралелни битове

Търся оптимизирана реализация на брояч, вероятно подобен на сивия код, който ще ми позволи бързо да преминавам през числа в нарязан на битове масив.

Ако приемем, че имам масива:

_m256 header[640];

Трябва да продължа да променям брояч в битове 608 - 639. Всеки от 256-те бита представлява отделен, паралелен брояч.

Операция „увеличаване“ отнема до 31 операции: И за изчисляване на пренасяне, XOR за изчисляване на стойност, повтарящи се за всяка позиция.

Сивият код трябва да се нуждае само от xor, но не знам за ефективен начин за изчисляване на индекса - изглежда, че изисква до 31 операции за определяне на битова позиция.

В идеалния случай бих искал брояч, който изисква малък брой ALU операции, за да определи кой бит да се промени. Някой знае ли нещо, което би било полезно?


optimization algorithm simd assembly
person Xavier    schedule 27.05.2011    source източник
comment
Не ми е много ясно какво се опитваш да направиш. Казвате, че всеки от 256-те бита представлява отделен, паралелен брояч. 1-битов брояч просто осцилира между 0, 1, 0, 1, ... И пренасянето е само обърнатата стойност. За да изчислите пренасянето, преди да „увеличите“, трябва просто да вземете текущата стойност на всеки брояч. За да изчислите новата стойност, просто „не“ брояча. Това може да се направи с множество броячи едновременно чрез кастинг към голям тип данни (напр. int) и вземане на побитово допълнение (~стойност).   -  person Ponkadoodle    schedule 27.05.2011
comment
Има 256 паралелни брояча, всеки 32 бита. Counter0 използва бит 0 от заглавка[608]..header[639], counter255 използва бит 255 от заглавка[608]..[639].   -  person Xavier    schedule 28.05.2011

Отговори (3)


arrow_upward
1
arrow_downward

LRS може да генерира последователност, съдържаща всички ненулеви числа 1..2^n-1, използвайки малък брой XOR, но измествайки всички останали битове на всеки етап. Има малко информация на http://www.ee.unb.ca/cgi-bin/tervo/sequence.pl?binary=11111. Броят на XOR зависи от броя на докосванията. Има списък с LRS конфигурации за 32 бита с няколко докосвания на http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/32stages.txt. Разбира се, генерираната последователност не е в ред - очевидно е произволна.

person mcdowella    schedule 28.05.2011

arrow_upward
0
arrow_downward

Мисля, че това е грешно. Както знам, връзката в TCP се дефинира от четворка {host1, port1; хост2, порт2}. Ако отворите слушащ сокет, не е назначен локален порт за обработка на свързващ клиент. Но ако отворите изходяща връзка към отдалечен сървър, наистина се присвоява локален порт за обработка на новооткрита връзка. И така, те отвориха 64 000 връзки от всяка машина, за да не излизат от броя на наличните локални портове, които поддържат връзка от страна на клиента
person Jim Mischel    schedule 27.05.2011
comment
Изчисляването на точния индекс може да бъде по-бавно и с санкциите за разклоняване. Не е необходимо да покривам целия диапазон, така че брояч с по-малко състояния би бил добър. - person Xavier; 28.05.2011

arrow_upward
0
arrow_downward

Можете да внедрите 256 паралелни Регистър за обратна връзка с линейно изместване по този начин (с base==608)

calculate x := header[base+0] XOR header[base+1] XOR header[base+21] XOR header[base+31]
move all elements header[base]...header[base+30] to header[base+1]...header[base+31]
set header[base] := x

Това ще има 2^32-1 различни състояния. Ако 2^31-1 е достатъчно, използвайте кранове 27 и 30 вместо 0,1,21,31. Магическите числа са от http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf.

person Gunther Piez    schedule 29.05.2011