Pull to refresh

Comments 60

хм, забыл про абс
mask = v >> sizeof(int) * CHAR_BIT — 1;
r = (v + mask) ^ mask;
вот это -(x < y) — можете прояснить?
посмотрите на ссылку, которую я выше написал, там объяснено
ссылка интересная, мне ее уже подсказали
А вот эта операция не содержит ли условного перехода внутри: -(x < y)?
Нет, но считается, что true == 1, а false == 0
Перехода нет. Есть лишь вычисление выражения (x<y) что есть sub x, y результат которого уходит дальше.
В современных процессорах есть команда SETL, которая записывает в регистр результат «меньше?» последнего сравнения (в виде 0 или 1). Без такой команды обойтись без переходов было бы очень сложно.
Можно, например: ((x — y) >> 31) & 1.
Нельзя. Если x=2e9, y=-2e9, то результат будет неправильным. В этом-то и основная проблема.
А потом этот код разбирать какому-нибудь программисту. Не завидую ему.
Если снабдить минимальными комментариями — разберется. Да и сам факт разбора кода декодера означает преодоление некоторого входного порога, «какой-нибудь» программист туда просто не полезет
Главное — добавить в начало строчку // return sign(a*b) * min(abs(a), abs(b))
Как раз именно та ситуация, когда нужны комментарии. При наличии их и тестов нет никаких проблем.
>Не завидую ему.

Ссылку на эту статью в комменты — и я наоборот ему завидую.
UFO just landed and posted this here
Спасибо, интересно и несложно. Хотя у atrydg действительно компактнее вышло.
Никак не мог распарсить
(unsigned)-1
Решил спросить что это такое и дошло.
Про пару опечаток в личку отписал.
Да, согласен, что можно не использовать вспомогательные массивы и в целом более компактно. Но согласитесь, что использование конструкции -(x < y) — это требует очень высокой стадии просветления
Здесь условных переходов точно нет. Сравнений тоже (предполагается, что ни a, ни b не равны -2^31)

int sa=a>>31, sb=b>>31; 
int sres=sa^sb;
a=(a^sa)-sa; b=(b^sb)-sb;
int d=a-b;
d&=(d>>31);
return ((b+d)^sres)-sres;
А потом кто-то запустит это на 64 битной машине.
Если компилятор мощный, то может наблюдаться прирост производительности в разы.
По идее, все будет хорошо, потому что int на 64х битной машине точно также равен четырем байтам.
Совсем нет.

По стандарту не задается размер int, есть только рекомендация делать его равным машинному слову. на 64 битах машинное слово будет равно 64 битам, и размер int, скорее всего будет зависеть от настроек компилятора. Компиляторов много разных, поэтому с каким нибудь может получиться, что int имеет размер 64 бита. Попробовал добиться этого от GCC, но там для x86 и x86_64 размер int всегда равен 32 битам.
int вообще-то в языке, а не на машине.
А уж что там за компилятор и как он его переделает — другое дело.
Если просто запустит — ничего не произойдет.
Если именно пересобрать под 64х битную платформу — то зависит от компилятора. В случае MSVS тоже ничего не произойдет.
Попробовал собрать и повторить.
И ускорение не в 10 раз, и… тупо не сходятся результаты расчетов.

C:\Temp\hey>1
0.954874 sec, x=-1132049649
0.381489 sec, x=-1903287257
0.452164 sec, x=971761649

gist.github.com/anonymous/5601991

Что я делаю не так??
Вы уверены, что в целях оптимизации компилятор не объединил три цикла в один? У меня сейчас нет возможности запустить ваш пример, как появится — проверю и отпишусь.
Лучше на ты. Да, уверен. В дебажном билде результаты расчетов такие же, в дизасме наглядно видать 3 цикла и честные вызовы функций.

Ну и эта, пример не мой ;) практически чистый cut/paste плюс пачка незначащих правок типа замены tprintf на printf. И одна значащая, вынос rand() за цикл с целью мерить именно оптимизируемую функцию, а не воздух.
Результат вычислений (x), естественно должен быть одинаков во всех трех случаях вне зависимости от debug/release. Спасибо, что обратил внимание, в LLR_2() и в LLR_3() вкрались опечатки. в LLR_2() это отсутствующая скобка (((unsigned)a^b)>>31), в LLR_3() не хватает скобок при операторе ^ и a вместо b там, где рассчитывается модуль а.

Насчет увеличения времени… В твоем примере (с вынесенном рандом) у меня функция с условными переходами работает быстрее чем остальные. По-видимому оба массива полностью поместились в стеке и и предсказание переходов дало свои плоды. Я увеличил размер массива до 1Мб, после чего LLR опять стала самой медленной. Но разница во времени выполнения — 3.5 раза а не 10.
Скопировал из статьи заново, результаты начали сходиться. С любым размером блока ускорение есть, однако ни разу не 10 раз. Вот например с блоком 16 мб выходит около 2.1 раз.

gist.github.com/anonymous/5604401
Я сделал дополнение к посту. Вероятно, все упирается в конкретную последовательность инструкций, а вызов rand() сильно «сбивает» конвеер.
int a,b,min;
...
min = a - (a-b) * ( ((a-b) >> 31) + 1 );
Либо даже вот так:
min = b + (b-a)*((a-b) >> 31);

На одно сложение меньше.
min = b - ((b-a) & ((a-b) >> 31));

А так от умножения избавились. Извините за столько комментариев — на ходу сочинял.
Работает только когда нет переполнения при вычитании. Например, при a,b>=0.
a,b — модули, так что тут все корректно
С отрицательными числами работает.
Только вот надо сказать, что декодер, работающий по такой приближенной формуле, довольно сильно проигрывает по вероятности ошибки «настоящей» формуле. Настоящая формула выглядит так:

x = 2 * atanh(tanh(a/2) * tanh(b/2)),


где a и b — настоящие LLR (т.е., не квантованные в int). К сожалению, в таком виде формула очень медленная и численно неустойчивая. Поэтому умные люди придумали эквивалентную ей формулу:

x = max(a + b, 0) + log(1 + exp(-abs(a + b)))
  - max(a, b) - log(1 + exp(-abs(a - b)))


Как видно, здесь все упирается в вычисление функции log(1 + exp(-abs(t))) для разных значений t. Для нее приходится делать lookup table. Работает это дело относительно медленно — уже не так важно, как вы там вычисляете максимум.

Интереснее, как оптимизировать другую половину алгоритма (на variable nodes). Там приходится «обрезать» получающиеся суммы, чтобы они не выходили за пределы некоторого интервала [-N, N], т.е. примерно так: x = max(min(a, N), -N). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.

Полностью согласен, я несколько упростил специально для того, чтобы акцентировать внимание на условных переходах. естественно далее там есть табулированный логарифм экспоненты.
Если N — степень двойки то на ARM например есть инструкция ssat, предполагаю на x86 что-нибудь похожее должно быть. А еще есть инструкции для saturating арифметики (qadd/qsub на ARM + аналоги для NEON). В SSE наверное тоже есть, не приходилось под x86 писать. Saturating-арифметика довольно часто используется в DSP и использование специальных инструкций дает прирост скорости в разы, по сравнению с условными переходами.
Каким компилятором собирали? VC++?
Для дальнейшего исследования можно попробовать посмотреть с vTune'е что происходит и где тормоза.
Странно, что до нынешнего времени компиляторы не научились распознавать и оптимизировать канонические реализации max и sign
Начиная с Пентиум Про есть команда условного перемещения — cmov.
если компилятор тупит и не хочет её генерировать для конструкций вида
a=a<b?a:b;
то можно ему
подсказать:
static inline int f4(int a, int b)
    {
    int _a=-a;
    _a=_a<0?a:_a;
    int _b=-b;
    _b=_b<0?b:_b;
    _a=_a<_b?_a:_b;
    int _c=-_a;
    _c=(a^b)<0?_c:_a;
    return _c;
    }

Сгенерируется красивый код без ветвлений:
примерно такой
//eax==a, edx==b
mov ebx, eax
neg ebx
cmovs ebx, eax
mov ecx, edx
neg ecx
cmovs ecx, edx
cmp ebx, edx
cmovg ebx, edx
mov edx, ebx
neg edx
xor eax, ebx
cmovs ebx, edx
//ebx <- ответ

Но он не сильно быстрее вашего варианта (cmov довольно медленно выполняется).

А вот этот заметно быстрее
static inline int f5(int a, int b)
    {
    int s,_a,_b,n[2];
    _a=(a>>31)&0xFFFFFFFE;
    _b=(b>>31)&0xFFFFFFFE;
    s=(_a^_b)+1;
    a*=(_a)+1;
    b*=(_b)+1;
    n[0]=b;
    n[1]=a;
    return s*n[a<b];
    }
А, получается вот как можно добиться cmov от компилятора. Мы пробовали использовать асмовую вставку с ним, действительно не особенно выигрывает по сравнению с условным переходом.
Удивительно, единственная выкладка на ассемблере в посте про низкоуровневую оптимизацию. И то, не в посте а в комментарии.
Я мог бы выложить соответствующие ассемблерные листинги, но намеренно не стал загромождать пост, т.к. в приведенных примерах трансляция в общем-то однозначная. Мне казалось, что небольших комментариев (про imul, rol и т.п.) будет достаточно.
Пока нет, но не очень понятно, что вы хотите ей сказать?
там отлично разжевано про предсказание ветвлений и про возможность отказа от условных переходов
в общем, очень по теме поста ссылка
А собственно какой из алгоритмов LDPC декодера был реализован?
Ответ комментом ниже, промахнулся
Реализация взята отсюда (с некоторыми оптимизациями, в т.ч. описанной в топике), длины блоков 16200 или 64800 бит
Ну вы не с того краю заходите ИМХО. Belief propagation (BP) алгоритм самый медленный. Все равно что сортировку пузырьком оптимизировать.
А что можете посоветовать?
Все зависит от постановки задачи, а об этом вы ни-ни. Откуда у вас вообще LDPС вылезло, что вы делаете?
Ну и конечно самый общий ответ на ваш вопрос тут ieeexplore.ieee.org
Sign up to leave a comment.

Articles