Arhn - архитектура программирования

Быстрый способ получить близкое число степени двойки (с плавающей запятой)

В численных вычислениях часто необходимо масштабировать числа, чтобы они находились в безопасном диапазоне.

Например, вычисление евклидова расстояния: sqrt(a^2+b^2). Здесь, если величина a или b слишком мала/велика, может произойти недополнение/переполнение.

Обычный подход к решению этой проблемы состоит в том, чтобы разделить числа на наибольшее число. Однако это решение:

  • медленный (деление идет медленно)
  • вызывает небольшую дополнительную неточность

Поэтому я подумал, что вместо того, чтобы делить на наибольшее число величины, давайте умножим его на близкое обратное число степени двойки. Это кажется лучшим решением, так как:

  • умножение намного быстрее деления
  • лучшая точность, так как умножение на число степени 2 является точным

Итак, я хотел бы создать небольшую служебную функцию с такой логикой (под ^ я имею в виду возведение в степень):

void getScaler(double value, double &scaler, double &scalerReciprocal) {
    int e = <exponent of value>;
    if (e<-1022) { scaler=2^-1022; scalerReciprocal = 2^1022; }
    } else if (e>1022) { scaler=2^1022; scalerReciprocal = 2^-1022; }
    } else { scaler=2^e; scalerReciprocal = 2^(2046-e); }
}

Эта функция должна возвращать нормализованные числа scaler и scalerReciprocal, оба являются числами степени 2, где scaler близко к value, а scalerReciprocal является обратным scaler.

Максимально допустимые показатели степени для scaler/scaleReciprocal равны -1022..1022 (я не хочу работать с субнормальными scaler, так как субнормальные числа могут быть медленными).

Как это сделать быстро? Можно ли это сделать с помощью операций с плавающей запятой? Или я должен извлечь экспоненту из value и использовать простые if для выполнения логики? Есть ли какой-то трюк, чтобы сделать сравнение с (-) 1022 быстрым (поскольку диапазон симметричен)?

Примечание. scaler не обязательно должно быть ближайшей степенью двойки. Если в этом нуждается какая-то логика, scaler может быть небольшой степенью двойки от ближайшего значения.


  • Я не думаю, что это ответит на ваш вопрос, но если вы ищете повышение производительности, самый быстрый способ умножения и деления на 2 - это сдвиг битов. При обработке сигнала вы вычитаете смещение сигнала и, как вы сказали, масштабируете его так, чтобы диапазон был [0,1], и вы проектируете фильтр с максимальной величиной 1. Плюс я не понимаю: вы масштабируете только если показатель степени меньше -1022 или больше 1022: почему? какой диапазон должен быть? 22.01.2019
  • @FrancescoBoi: Нет, масштабирование всегда будет происходить. Но scaler должен иметь показатели степени только между -1022..1022 (это почти весь диапазон. Устраняются только проблемные граничные значения). 22.01.2019
  • Вас интересует портативный чистый C, который будет эффективно компилироваться для x86, или вас также интересует C со встроенными функциями для SIMD-инструкций, таких как AVX512 _mm512_getexp_pd (извлечение показателя степени как double) и _mm512_scalef_pd что делает dst[63:0] := tmp_src1[63:0] * POW(2, FLOOR(tmp_src2[63:0])) (т.е. добавляет целую часть числа double к полю экспоненты другого.) 22.01.2019
  • @PeterCordes: меня больше всего интересует чистый C или, может быть, расширения, которые широко доступны. AVX все еще не так широко распространен. Но спасибо за упоминание, я не знал о _mm512_getexp_pd/_mm512_scalef_pd. Они кажутся похожими на старые FXTRACT/FSCALE. 22.01.2019
  • В чистом C, если вы в конечном итоге что-то зажимаете, напишите это так, чтобы оно могло эффективно компилироваться в minsd/maxsd (или автоматически векторизоваться с их SIMD-версиями). Это SSE2 и, следовательно, базовый уровень для x86-64, и я думаю, что большинство наборов инструкций SIMD содержат минимальные/максимальные инструкции. См. Какая инструкция дает минимальное и максимальное значение FP без ветвления на x86?. например a < b ? a : b. Можно просто отдельно зажимать скейлер и его ответную часть. Конечно, если вы работаете с целочисленной экспонентой, вам может понадобиться зафиксировать целочисленный диапазон, прежде чем вставлять его в double. 22.01.2019
  • @PeterCordes: да, спасибо за информацию. У меня есть зажим, а затем мне нужно создать двойное значение на основе зажима. Я ожидаю, что здесь может быть какой-то трюк. Если зажим не изменяет значение, мне нужна простая операция and (просто очистить мантиссу). Если зажим модифицируется, то происходит немного больше. Может быть, есть какой-то чрезвычайно умный способ сжать эти if во что-то умное. 22.01.2019
  • Можете ли вы предположить, что C++ double представлен IEEE 754 64-битной двоичной плавающей запятой? 22.01.2019
  • @PatriciaShanahan: есть стандартный предопределенный макрос, который сообщает вам, так это или нет. 22.01.2019
  • @PatriciaShanahan: да. 22.01.2019
  • @PeterCordes Что касается тернарного оператора и minsd, minpd, maxsd, maxpd, то clang почему-то работает лучше, чем gcc. ссылка на Godbolt 22.01.2019
  • Мне приходит в голову другое решение — использовать экстремальную версию расщепления Вельткампа-Деккера: double get_scale(double x) { double d = x * (0x1p52 + 1); double t = d - x; return d - t; }. Это всего лишь три обычные арифметические инструкции, но они не обрабатывают значения вблизи верхней границы конечного диапазона. 26.01.2019
  • @EricPostpischil: это хороший трюк, чтобы получить близкое значение степени двойки. На платформах, где манипулирование числами с плавающей запятой как целыми происходит медленно, этот трюк может быть частью решения. Мне нужны фиксированные показатели степени (можно легко сделать с помощью сравнения), а также обратное значение (я не вижу быстрого способа получить это без манипулирования значением как целым числом). 26.01.2019

Ответы:


1

Основываясь на ответе wim, вот еще одно решение, которое может быть быстрее, так как в нем на одну инструкцию меньше. Выход немного отличается, но все же соответствует требованиям.

Идея состоит в том, чтобы использовать битовые операции для исправления граничных случаев: поместить 01 в младший бит экспоненты, независимо от ее значения. Итак, показатель:

  • 0 становится 1 (-1023 становится -1022)
  • 2046 становится 2045 (1023 становится 1022)
  • другие показатели степени также изменились, но незначительно: число может стать в два раза больше по сравнению с решением Вима (когда младший бит степени изменяется с 00 на 01), или уменьшиться вдвое (когда 10->01) или 1/4 (когда 11-> 01)

Итак, эта модифицированная процедура работает (и я думаю, что это довольно круто, что проблема может быть решена всего с помощью двух быстрых ассемблерных инструкций ):

#include<stdio.h>
#include<stdint.h>
#include<immintrin.h>
/* gcc -Wall -m64 -O3 -march=sandybridge dbl_scale.c */

union dbl_int64{
    double d;
    uint64_t i;
};

double get_scale(double t){
    union dbl_int64 x;
    uint64_t and_i;
    uint64_t or_i;
         /* 0xFEDCBA9876543210 */
    and_i = 0x7FD0000000000000ull;
    or_i =  0x0010000000000000ull;
    x.d = t;
    x.i = (x.i & and_i)|or_i;                     /* Set fraction bits to zero, take absolute value */
    return x.d;
}

double get_scale_x86(double t){
    __m128d x = _mm_set_sd(t);
    __m128d x_and = _mm_castsi128_pd(_mm_set1_epi64x(0x7FD0000000000000ull));
    __m128d x_or  = _mm_castsi128_pd(_mm_set1_epi64x(0x0010000000000000ull));
            x     = _mm_and_pd(x, x_and);
            x     = _mm_or_pd(x, x_or);
    return _mm_cvtsd_f64(x);
}

/* Compute the inverse 1/t of a double t with all zero fraction bits     */
/* and exponent between the limits of function get_scale                 */
/* A single integer subtraction is much less expensive than a            */
/* floating point division.                                               */
double inv_of_scale(double t){
    union dbl_int64 x;
                     /* 0xFEDCBA9876543210 */
    uint64_t inv_mask = 0x7FE0000000000000ull;
    x.d = t;
    x.i = inv_mask - x.i;
    return x.d;
}

double inv_of_scale_x86(double t){
    __m128i inv_mask = _mm_set1_epi64x(0x7FE0000000000000ull);
    __m128d x        = _mm_set_sd(t);
    __m128i x_i      = _mm_sub_epi64(inv_mask, _mm_castpd_si128(x));
    return _mm_cvtsd_f64(_mm_castsi128_pd(x_i));
}


int main(){
    int n = 14;
    int i;
    /* Several example values, 4.94e-324 is the smallest subnormal */
    double y[14] = { 4.94e-324, 1.1e-320,  1.1e-300,  1.1e-5,  0.7,  1.7,  123.1, 1.1e300,  
                     1.79e308, -1.1e-320,    -0.7, -1.7, -123.1,  -1.1e307};
    double z, s, u;

    printf("Portable code:\n");
    printf("             x       pow_of_2        inverse       pow2*inv      x*inverse \n");
    for (i = 0; i < n; i++){  
        z = y[i];
        s = get_scale(z);
        u = inv_of_scale(s);
        printf("%14e %14e %14e %14e %14e\n", z, s, u, s*u, z*u);
    }

    printf("\nx86 specific SSE code:\n");
    printf("             x       pow_of_2        inverse       pow2*inv      x*inverse \n");
    for (i = 0; i < n; i++){  
        z = y[i];
        s = get_scale_x86(z);
        u = inv_of_scale_x86(s);
        printf("%14e %14e %14e %14e %14e\n", z, s, u, s*u, z*u);
    }

    return 0;
}
22.01.2019
  • Какие 3 инструкции вы считаете? Ваш уменьшает его до 2, просто ANDPS/ORPS вместо ANDPS/MINPD/MAXPD. Или, если вы считаете, что фактически масштабируете 2 значения в соответствии с максимальной величиной, вам потребуется И + И + (выберите самый высокий показатель с помощью MAXPD или AVX512 VPMAXUQ) + ИЛИ + PSUBQ, а затем примените его к обоим входам с 2x MULPD или VFMADD... если вы или компилятор можете сократить первый шаг после нормализации до FMA. 22.01.2019
  • И кстати, избегайте встроенных функций для скаляра; они отстой, потому что нет способа сказать компилятору, что вам нужен вектор с неопределенным верхним элементом, т. е. без скалярного->128 эквивалента __m256 _mm256_castps128_ps256 (__m128 a). К сожалению, за исключением clang, большинство компиляторов действительно тратят впустую инструкцию, расширяющую ноль для _mm_set_sd(t). Как объединить скаляр в вектор без того, чтобы компилятор тратил впустую инструкцию, обнуляющую верхние элементы? Ограничение дизайна во встроенных функциях Intel?. Просто используйте версию с каламбуром типа union, я думаю, что все основные компиляторы x86 su 22.01.2019
  • О, я только что посмотрел на вашу ссылку Godbolt. Странно, что скалярные компиляторы не могут использовать ANDPS / ORPS даже в цикле и фактически извлекают в GP regs с movq. В x86-64 System V нет регистров XMM с сохранением вызовов, поэтому они не могли поднять константы, но использование их из памяти все равно было бы выигрышем. Будем надеяться, что компиляторы будут автоматически векторизовать чистую версию C. 22.01.2019
  • @PeterCordes: да, на самом деле их всего два :) Я был счастлив, что смог вырезать одну инструкцию из версии wim, я не удосужился проверить, что на самом деле первая инструкция действительно не нужна. Спасибо за ссылку, проверю! 22.01.2019
  • Возможно, вы захотите добавить версию своей функции, которая принимает 2 входа и возвращает масштабный коэффициент для использования для обоих, потому что, как я уже сказал, вы можете комбинировать это определение максимальной величины с обнулением мантиссы. 22.01.2019
  • Хорошее решение. Я думаю, что ваша функция get_scale немного более шаткая, чем моя, тем не менее, она может хорошо работать для вашего приложения. 23.01.2019
  • @wim: Помните, что вариант использования OP заключается в том, чтобы просто масштабировать значения до величины, при которой их возведение в квадрат не приведет к переполнению до бесконечности или уменьшению значения до денормализованного / нуля, для таких вещей, как sqrt(a^2+b^2) и тому подобное. Оставить большее значение в диапазоне [1..2) вместо [0.5 .. 1) вполне нормально. Использование OR для применения минимума — действительно хорошая идея для этого варианта использования. 23.01.2019
  • @PeterCordes: С идеей И/ИЛИ нормальные значения масштабируются до диапазона [0,5...8,0), что действительно идеально подходит для надежного вычисления гипотенузы. 23.01.2019

  • 2

    Ты можешь использовать

    double frexp (double x, int* exp); 
    

    Возвращаемое значение — это дробная часть x, а exp — показатель степени (минус смещение).

    В качестве альтернативы следующий код получает экспоненциальную часть числа double.

    int get_exp(double *d) {
      long long *l = (long long *) d;
      return ((*l & (0x7ffLL << 52) )>> 52)-1023 ;
    }
    
    21.01.2019
  • frexp делает здесь больше, чем нужно. И делает меньше, так как мне нужно зажимать эксп, а потом нужно конвертировать обратно, чтобы получить double. Я не думаю, что frexp действительно применим в моем случае, так как мне нужна скорость. Я бы предпочел извлечь экспоненту вручную, если это так (это просто memcpy, сдвиг и маска). 22.01.2019
  • @geza: frexp - это просто смена и маска, стандартизированные и задокументированные, чтобы сделать их переносимыми. Если вы хотите настроить экспоненту, соедините ее с ldexp (обратите внимание, что ldexp добавляет к экспоненте, а не заменяет ее) 22.01.2019
  • @BenVoigt: к сожалению, нет. Проверьте исходный код. Он обрабатывает nan/inf и субнормальные числа. И это делает некоторую логику, которая может быть частью моей if (exp<-1022) .. логики. Так что с frexp у меня будет избыточный код. Я не говорю, что это очень медленно. Но все же лучше (для меня) извлекать экспоненту вручную, если это так. 22.01.2019

  • 3
  • Спасибо за ответ! Основываясь на вашем решении, я нашел (возможно) более быстрое решение. 22.01.2019
  • Re: каламбур типа union: GNU C++ явно поддерживает его как расширение ISO C++. См. gcc.gnu.org/onlinedocs/gcc/Optimize-Options. .html#Тип-каламбур и gcc.gnu.org/onlinedocs/gcc/. Я думаю, что MSVC также поддерживает это, но IDK, если это задокументировано. Тем не менее, нет недостатка в использовании memcpy для хороших компиляторов, если это полная ширина типа. 23.01.2019
  • @PeterCordes: насколько я знаю, MSVC не использует оптимизацию, основанную на строгих правилах псевдонимов. Например, этот код перезагружает *a дважды без необходимости. 24.01.2019
  • @geza: строгие псевдонимы связаны, но отделены от каламбура союза. *(int*)&my_float по-прежнему является UB в GNU C, хотя на практике он может часто работать для таких простых случаев, как этот, когда нет смешанных операций FP. 24.01.2019
  • @PeterCordes: конечно :) Я имел в виду, что с MSVC работают все виды каламбуров, а не только объединение, как с gcc/clang. Я никогда нигде не видел документального подтверждения этого, это просто основано на моем опыте. 24.01.2019
  • @geza: понятно. Да, я думаю, это правда, что MSVC намеренно поддерживает приведение указателей и для каламбура типов (поскольку это используется во многих устаревших непереносимых кодах). В общем, мы должны внимательно смотреть на пропущенную оптимизацию/случайно работать и делать вывод, что она официально поддерживается, но я думаю, что в этом случае мы можем. (Основываясь на широко распространенном использовании идиомы и на том, что если MSVC когда-либо собирался что-то сломать, он, вероятно, сломает это.) 24.01.2019
  • @PeterCordes: Re: каламбур союзного типа: спасибо за ссылки. Я провел несколько экспериментов с union и memcpy. С clang, MSVC и gcc я не смог найти никакой разницы между сборкой, сгенерированной для этих двух случаев. С icc была небольшая разница 24.01.2019
  • Новые материалы

    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..

    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..

    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..

    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..

    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..

    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..

    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..