Существует такая проблема когда производительность приложения может заметно ухудшиться из-за особенностей вычисления на числах с плавающей точкой. Как правило CPU заточен под целочисленные операции, а сопроцессор FPU (floating point unit) в нем работает на порядке медленнее. Существую такие платформы где вообще отсутствует FPU и эмулирование операций с числами занимало бы много времени. Например, при наличии FPU, умножение чисел с плавающей точкой выполняется всего одной командой fmul, а при отсутствии FPU, умножение выполняется эмулирующей функцией __mulsf3. По сравнению с командой fmul, функция __mulsf3 эмулирует операции над числами с плавающей точкой, при этом вычисления производятся в целочисленном виде, что приводит к увеличению машинного кода и времени на его выполнение, в то время как команда fmul выполнит эту операцию быстро, с использованием аппаратных средств.
Данной проблеме существует решение, которое позволяет проводить вычисления с фиксированной точкой на целочисленном типе.
Принцип данного типа заключается в фиксированном сдвиге числа на N бит, в результате чего дробное число можно представить целым и оно будет иметь точность 2^N после точки. Пример преобразования числа с плавающей точкой в число с фиксированной точкой порядка 8 бит (2^8 = 1024).
Вот пример перевода числа с плавающей точкой в число с фиксированной точкой:
Fixed(12345,6789) = 1024 * 12345,6789 = 12641975,<s>1936</s>Данное число, после точки, имеет точность 2^8 после запятой.
Пример обратного перевода числа с фиксированной точкой в число с плавающей точкой.
Float(12641975) = 12641975 / 1024 = 12345,678<s>7109375</s>В данном случае число после обратного перевода имеет вид 12345,6787109375 и является точным в 3 знака после точки, максимальная точность на самом деле равна 2^8 = 1024.
Как происходят вычисления на типе с фиксированной точкой?
Операции суммы и разности эквивалентны обычным целочисленным операциям.
Fixed(x) + Fixed(y) и Fixed(x) - Fixed(y), с любым порядком(1024 * x) + (1024 * y) и (1024 * x) - (1024 * y)Умножение таких чисел производится в такой форме.
(Fixed(x) * Fixed(y)) / p, это эквивалентно, с порядком 8 бит((1024 * x) * (1024 * y)) / 1024Деление.
(Fixed(x) * p) / Fixed(y), также с порядком 8 бит, это(1024 * 1024 * x)*(1024 * y)Переполнение
При выполнении операций умножения и деления возможен случай переполнения, что приведет к неверному результату. Это произойдет в том случае, если, например, будет использоваться 32 битный целочисленный тип и при вычислениях произойдет переполнение данного типа и в результате этого переполнения число потеряет старшие биты. Существует два способа устранения переполнения:
- Выполнить вычисления в 64-битном целочисленном типе.
- Выполнить вычисления в «разобранном» виде, например при умножении, (xi+xf)*(yi+yf) = xi*yi+xf*yf+xi*yf+yi*xf, приставки i и f означают целую часть и часть после точки.
Класс для работы с fixed-point на C++
#define DIGITS 1024 // экспонента
#define EPS 20 // константа устанавливающая границы приближенности вычисления корня
using namespace std;
typedef signed int __int32_t;
class Fixed {
signed int x;
Fixed(signed int a){
x = a;
}
public:
Fixed(){
x = 0;
}
static Fixed fromInt(signed int val){
return Fixed(val*DIGITS);
}
static Fixed fromFloat(float val){
return Fixed((signed int)(val*DIGITS));
}
float fixed2float(){
return ((float)x)/DIGITS;
}
Fixed sum(Fixed a,Fixed b){
return Fixed(a.x+b.x);
}
Fixed diff(Fixed a,Fixed b){
return Fixed(a.x-b.x);
}
Fixed mul(Fixed a,Fixed b){
signed int c=a.x*b.x;
if(c/b.x != a.x){
// Overflow!
signed int i1 = a.x/DIGITS;
signed int i2 = b.x/DIGITS;
signed int f1 = (a.x&(DIGITS-1));
signed int f2 = (b.x&(DIGITS-1));
return Fixed((i1*i2)*DIGITS+(f1*f2)/DIGITS+i1*f2+i2*f1);
}else{
return Fixed(c/DIGITS);
}
}
Fixed div(Fixed a,Fixed b){
if(a.x>(1<<21)){
// Overflow!
signed int i = a.x/DIGITS;
signed int f = (a.x&(DIGITS-1));
return Fixed(((i*DIGITS)/b.x)*DIGITS+(f*DIGITS)/b.x);
}else{
return Fixed((a.x*DIGITS)/b.x);
}
}
Fixed sqrt(Fixed k){
Fixed tmp(0);
tmp.x = k.x/2;
signed int min = 0;
signed int max = k.x;
Fixed quick(0);
do{
tmp.x = (min+max)/2;
quick = Fixed::mul(tmp,tmp);
if(abs(quick.x-k.x)<EPS) return Fixed(tmp);
if(quick.x>k.x){
max = tmp.x;
}else{
min = tmp.x;
}
}while(true);
}
};
Комментарии (18)
NeoCode
15.05.2019 13:39+1Странно что fixed point не поддерживается на уровне языка c/c++. Я когда-то писал программу для микроконтроллера в которого не было FPU. Конечно написать можно и так, но для каждой переменной и для каждой операции приходилось писать комментарий — сколько тут знаков до запятой и после:)
Mirn
15.05.2019 15:12Да даже если есть в контроллере FPU, то часто бывает супер скалярность и SIMD инструкции когда сразу вычисляется умножение нескольких 16 битных пар X и W с накоплением в аккумулятор 32 битный. Я поступал так: просто завёл два типа 16 и 32 бита int внутри и сделал так чтоб они между собой были не совместимы с ошибками компиляции. И набор функций конвертации — просто сдвиги с явным привидением типа.
Бонусом то что FPU всегда требует дополнительной конвертации int в флоат и обратно и это не параллелится. Но для fixed SIMD обычная загрузка позволяет загружать до 4 значений X или W сразу и она паралеллится с самой вычисляющей SIMD FMA инструкций — итого по две инструкции за ОДИН такт, и обе из них векторные которые обрабатывают несколько пар.
Итог:
на FPU нейросеть на 1000 классов — не более одной FPS ровно,
на фиксед с SIMD — несколько FPS.
И это притом что помимо нейросетки необходимо захватывать сырой raw с камеры, дебаеринг, денойз делать, а потом результаты выводить в графический интерфейс с тачами и жестами, окнами и оверлеями в реалтайме. И это всё на одном ядре контроллера. Хотя скоро двуядерные кортекс М7 появятся.
lgorSL
16.05.2019 00:48+1для каждой переменной и для каждой операции приходилось писать комментарий — сколько тут знаков до запятой и после:)
В с++ же есть шаблоны и их параметризация целыми числами. Почему бы информацию о положении точки не сделать частью типа? Тогда после компиляции эта информация пропадёт и на производительность не повлияет, но зато во время компиляции будет возможность поймать часть ошибок.
Keroro
16.05.2019 06:38Я пришёл к такой системе:
struct { uint16_t Value; uint8_t FixedPoint; }fPointVal; fPointVal Temperature; Temperature.Value=366; Temperature.Point=1; LCD_print_fixed(0, 0, Temperature.Value, Temperature.Point); //36.6
Dima_Sharihin
16.05.2019 13:05Добавьте бит знака, сделайте Value 24-битным, FixedPoint — 7-битным и показывающим положение двоичной точки и вы получите IEEE-754 Single-Precision Floating Point
unC0Rr
15.05.2019 16:30+1Интуитивно кажется, что лучше операцию умножения всегда выполнять по ветке с защитой от переполнения, чем при каждом умножении делать дополнительное деление с возможным пересчётом результата.
unC0Rr
15.05.2019 16:45Ещё дополню: операцию возведения в квадрат можно сделать быстрее, чем умножение числа на само себя (три умножения вместо четырёх), а операцию деления можно сделать точнее за счёт более точного вычисления выражения (i*DIGITS)/b.x (по указанной в статье формуле 1 / 3 будет вычислено равным нулю).
FGV
16.05.2019 09:12При выполнении операций умножения и деления возможен случай переполнения…
Все гараздо страшнее — переполнение может возникнуть и при сложении/вычитании.
А вот умножение и деление кстати можно организовать так что переполнения не будет — через отбрасывание мл. части для умножения и через сдвиг делимого в старшую часть. Для деления правда будут ограничения — делимое должно быть меньше делителя.
picul
Проблема производительности FP уже не актульна лет 20, сейчас FP-вычисления могут быть даже быстрее целочисленных (это на x86, не знаю как в других). А вот в плане проблем с унификацией результата вычислений это может помочь (если обычный FP может давать разные результаты на разных платформах, то проэмулированый даст один и тот же).
MichaelBorisov
Проблема мега актуальна для микроконтроллеров, DSP и FPGA, где FPU нет, либо оно медленное, либо затратное по аппаратным ресурсам. Кроме того, еще лет 10 назад операции с плавающей точкой даже на x86 были медленнее, чем целочисленные. Читал в руководстве от Intel по оптимизации с применением MMX, SSE и т.д. Там предлагается в первую очередь отказаться от чисел с плавающей точкой, если это возможно.
picul
Медленнее максимум в несколько раз, и по-этому бороться с ними эмулятором не получится — разве что полным отказом от FP, как Вы и сказали.
berez
И сейчас предлагается. Только причина не в том, что floating point медленный, а в том, что расширения MMX и SSE используют регистры математического сопроцессора. То есть если программа использует и то, и другое, придется постоянно сохранять и восстанавливать регистры сопроцессора, а это много (больше 100 байт, если я правильно помню) и долго.