Выбрасывает целое число со знаком в двоичное число с плавающей запятой дешевле, чем обратная операция?

Question

Я знаю из таких статей, как «Why you should never cast floats to ints», и многим другим нравится, что литье поплавка в подписанное int дорого. Я также знаю, что некоторые инструкции преобразования или векторные инструкции SIMD на некоторых архитектурах могут ускорить процесс. Мне любопытно, что преобразование целого числа в плавающую точку также дорого, так как весь материал, который я нашел по этому вопросу, говорит только о том, как дорого конвертировать из плавающей точки в целое.

Прежде, чем кто-нибудь скажет: «Почему бы вам просто не проверить его?» Я не говорю о производительности на определенной архитектуре, меня интересует алгоритмическое поведение преобразования на нескольких платформах, придерживающихся стандарта IEEE 754-2008. Есть ли что-то, что присуще алгоритму преобразования, который влияет на производительность в целом?

Наглядно, я думаю, что преобразование из целого числа с плавающей точкой будет легче в целом по следующим причинам:

• Округления необходимо только тогда, когда точность целого превышает точность двоичных плавающего номер точки, например 32-битовое целочисленное и 32-битное float может потребовать округления, но 32-разрядное целочисленное и 64-битное float не будет, и ни одно из 32-разрядных целых чисел, использующих только 24 бита, не будет.

• Там нет необходимости проверять NAN или +/- INF или +/- 0.

• Там нет опасности переполнения или сгущенного.

Каковы причины того, что переход от междунар плавать может привести к снижению производительности кросс-платформенной, если (кроме платформы эмуляции чисел с плавающей запятой в программном обеспечении)? Преобразование из int в float обычно дешевле, чем float to int?

Answer 1

Intel указывает в своем «Справочном руководстве по оптимизации архитектуры», что CVTSI2SD имеет задержку в 3-4 цикла (и 1 цикл) на базовой линии для настольных компьютеров и серверов с Core2. Это можно считать хорошим примером.

С точки зрения аппаратного обеспечения такое преобразование требует некоторой помощи, которая делает его пригодным для разумного количества циклов, в противном случае оно становится слишком дорогостоящим. Ниже следует наивное, но довольно хорошее объяснение. Во всяком случае, я предполагаю, что одного тактового цикла процессора достаточно для такой операции, как целочисленное целочисленное добавление (но не радикально длиннее!), И все результаты предыдущего цикла применяются на границе цикла.

Первый тактовый цикл с соответствующей аппаратной поддержкой (priority encoder) дает Count Leading Zeros (CLZ), среди которых обнаруживаются два особых случая: 0 и INT_MIN (набор MSB и все остальные бит очищены). 0 и INT_MIN лучше обрабатывать отдельно (загрузка константы в регистр назначения и завершение). В противном случае, если целое число ввода было отрицательным, оно должно быть отменено; для этого обычно требуется еще один цикл (потому что отрицание представляет собой комбинацию инверсии и добавления бит переноса). Таким образом, проводятся 1-2 цикла.

В то же время он может рассчитывать смещенное предсказание экспоненты на основе результата CLZ. Обратите внимание, что нам не нужно заботиться о денормализованных значениях или бесконечности. (Можно ли предсказать CLZ (-x) на основе CLZ (x), если x < 0? Если мы сможем, это сэкономит нам 1 цикл.)

Затем применяется сдвиг (1 цикл снова, с barrel shifter) до поместите целочисленное значение, чтобы его наивысшее значение 1 находилось в фиксированном положении (например, со стандартными 3 битами расширения и 24-битной мантиссой, это бит № 26).Это использование баррель-переключателя должно сочетать все младшие бит с липким битом (может потребоваться отдельный пользовательский экземпляр shrelter ствола, но это waaaay дешевле, чем кеш-мегабайт или OoO dispatcher). Теперь, до 3 циклов.

Затем применяется округление. Округление анализирует в нашем случае 4 наименьших бита текущего значения (mantissa LSB, guard, round и sticky) и OTOH, текущий режим округления и целевой знак (извлеченный в цикле 1). Округление до нуля (RZ) приводит к игнорированию защитных/круглых/липких бит. Округление до -∞ (RMI) для положительного значения и + ∞ (RPI) для отрицательного значения равно нулю. Округление до ∞ противоположного знака приводит к добавлению 1 к основной мантиссе. Наконец, округление до ближайшего к узлу (RNE): x000 ... x011 -> discard; x101 ... x111 -> добавить 1; 0100 -> отказаться; 1100 -> добавить 1. Если аппаратное обеспечение достаточно быстро, чтобы добавить этот результат в тот же цикл (я думаю, это вероятно), у нас есть до 4 циклов.

Это добавление на предыдущем этапе может привести к переносу (например, 1111 -> 10000), поэтому экспоненту может увеличиться. Заключительный цикл состоит в том, чтобы упаковать знак (из цикла 1), мантисса (до знака) и смещенный показатель (рассчитанный по циклу 2 из результата CLZ и, возможно, отрегулированный с переносом из цикла 4). Итак, 5 циклов.

Является ли преобразование из int в плавание, как правило, более дешевым, чем float to int?

Мы можем оценить одно и то же преобразование, например. от binary32 до int32 (подписано). Предположим, что преобразование NaN, INF или слишком большого значения приводит к фиксированному значению, скажем, INT_MIN (-2147483648). В этом случае:

Разделить и проанализировать входное значение: знак S; BE - предвзятый показатель; M - мантисса (значение); также примените режим округления. Сигнал «преобразование невозможно» (переполнение или недействительный) генерируется, если: BE> = 158 (сюда входят NaN и INF). Сигнал «нуля» генерируется, если BE < 127 (abs (x) < 1) и {RZ, или (x> 0 и RMI), или (x < 0 и RPI)}; или, если BE < 126 (abs (x) < 0,5) с RNE; или, BE = 126, значение = 0 (без скрытого бита) и RNE. В противном случае сигналы для окончательных +1 или -1 могут быть сгенерированы для случаев: BE < 127 и: x < 0 и RMI; x> 0 и RPI; BE = 126 и RNE. Все эти сигналы могут быть рассчитаны в течение одного цикла с использованием логической логической схемы и привести к завершению результата в первом цикле. Параллельно и независимо вычислять 157-BE с использованием отдельного сумматора для использования в цикле 2.

Если еще не финализировано, мы имеем abs (x)> = 1, поэтому BE> = 127, но BE < = 157 (поэтому abs (x) < 2 ** 31). Получите 157-BE из цикла 1, это необходимое количество сдвига. Примените сдвиг вправо на эту величину, используя тот же самый баррек, что и в алгоритме int -> float, к значению с (еще раз) 3 дополнительными битами и сбором липкого бита. Здесь проводятся 2 цикла.

Применить округление (см. Выше). Проводится 3 цикла, а перенос может производиться. Здесь мы можем снова обнаружить целочисленное переполнение и получить соответствующее значение результата. Забудьте дополнительные биты, теперь оценивается только 31 бит.

Наконец, отрицайте полученное значение, если x было отрицательным (знак = 1). Проводится до 4 циклов.

Я не опытный разработчик бинарной логики, поэтому может упустить шанс скомпрометировать эту последовательность, но она довольно близка к значениям Intel. Таким образом, сами конверсии довольно дешевы, при условии наличия аппаратной поддержки (говоря еще раз, это приводит не более чем к нескольким тысячам ворот, так что крошечный для современного производства чипов).

Вы также можете взглянуть на Berkeley Softfloat library - он реализует практически тот же подход с незначительными модификациями. Начните с исходного файла ui32_to_f32.c.Они используют больше дополнительных бит для промежуточных значений, но это не принципиально.

Answer 2

См. Отличный ответ Net Net на алгоритм, но это не только алгоритм. FPU работает асинхронно, поэтому операция int-> FP может запускаться, и CPU может затем выполнить следующую команду. Но при хранении FP до целого числа должен быть FWAIT (Intel).