Балансируя между точностью и производительностью

Есть несколько важных аспектов, которые нужно обязательно учитывать при создании приложения, производящего какие-либо вычисления, а точнее — операции с числами с плавающей точкой. Что мы ждём и планируем получить от таких приложений (в большинстве случаев, научных)? В первую очередь, нас интересует точность вычислений – полученный результат должен быть наиболее близок к «правильному». Другая сторона медали – стабильность результатов и портируемость приложения. Нам важно иметь возможность получать одинаковый, неизменно повторяющийся от запуска к запуску результат, причём на разных машинах/архитектурах. Ну и последний, но не менее значимый пункт – производительность. Насколько быстро при всём этом будет выполняться наше приложение, и когда мы получим результаты наших вычислений?

В компиляторе компании Intel есть набор опций, отвечающих за контроль оптимизаций вычислений над числами с плавающей точкой. Рассмотрим преинтереснейший ключик –fp-model, который, судя по описанию в документации, управляет семантикой вычислений над числами с плавающей точкой. Кстати, стоит отметить, что похожие ключи есть и в других компиляторах, не только Интеловском, об этом мы тоже поговорим. По сути, с помощью данного ключика мы и сможем контролировать баланс между производительностью и точностью вычислений. Возможные значения, которые могут быть указаны в опции –fp-model: precise, fast[=1|2], strict, source, [no-]except (Linux*) or except[-] (Windows*). Давайте разберёмся, что они дают при компиляции нашего кода.

Все эти ключи позволяют, в конечном счёте, контролировать следующие правила компилятора и отвечают на соответствующие вопросы:

Безопасность значений (value safety)
Может ли компилятор производить трансформации, способные изменить результат?
Например, в безопасном режиме компилятор не будет оптимизировать выражение х/х в 1.0, потому что во время выполнения приложения значение может быть 0 или NaN. Так же, изменение последовательности вычислений (в частности, закон ассоциативности или дистрибутивности) может быть запрещено.

Точность при вычислении выражений (floating-point expression evaluation)
Как компилятор должен округлять промежуточные результаты (какую точность выбирать)?

Доступ к окружению (floating-point environment access)
Может ли приложение изменять параметры окружения (например, правила округления) во время выполнения? В целом, FP окружением является набор регистров, который управляет работой FPU (Floating-point unit, сопроцессор для работы с числами с плавающей точкой). В него входят управление режимом округления, исключениями, работы с ненормализованными числами (сбрасывание в 0), маски исключений и другие функции. При дефолтных ключах предполагается, что в приложении нет доступа к FPU окружению.

Операция умножения-сложения (contractions)
Должен ли компилятор генерировать операции умножения-сложения (Fused multiply-add, FMA), позволяющие совмещать умножение и сложение в одной инструкции (не требуется промежуточного округления до N бит после умножения перед сложением, в отличие от пары отдельных инструкций)? Сложение выполняется над более точным внутренним представлением, и только после него происходит округление. Это позволяет увеличить точность.

Исключения для операций с плавающей точкой (precise floating-point exceptions)
Учитывает ли компилятор возможность исключений при работе с операциями над числами с плавающей точкой?
При определённых условиях (например, деление на ноль), FPU может сгенерировать исключение. По умолчанию, семантика исключений отключена. Стоит отметить, что разрешение исключений и подключение семантики исключений – это не одно и то же. В последнем случае компилятор принимает во внимание то, что операции с «плавающими» числами могут сгенерировать исключение. Кстати, ввиду того, что FPU является отдельной частью процессора, исключение будет генерироваться не сразу, а только при достижении CPU (он проверяет наличие FPU исключений) следующей инструкции над числами с плавающей точкой.

Итак, эти 5 основных вопроса могут контролироваться опциями компилятора следующим образом:

опция	безопасность	точность	FMA	окружение	исключения
precise source	варьируется	код код	да	нет	нет
strict	варьируется	код	нет	да	да
fast=1 (по умолчанию)	небезопасно	неизвестно	да	нет	нет
fast=2	небезопасно	неизвестно	да	нет	нет
except except-	не меняет	код код	не меняет	не меняет	да нет

Допустим, мы разобрались с тем, что контролируют данные опции. Давайте на примерах попробуем понять, как их использовать и для чего.

Например, возьмём алгоритм суммирования Кахана, позволяющий получать более аккуратные результаты при суммировании чисел с плавающей точкой.

float KahanSum(const float A[], int n ) {    float sum=0, Y, T;    float C=0; //A running compensation for lost low-order bits.    for (int i=0; i<n; i++)    {       Y = A[i] - C;     //So far, so good: C is zero.       T = sum + Y;      //Alas, sum is big, Y small, so low-order digits of Y are lost.       C = T - sum - Y;  //(T - sum) recovers the high-order part of Y;                          //subtracting y recovers -(low part of y)       sum = T;    //Next time around, the lost low part will be added to y in a fresh attempt.    }    return sum; } 

Данный алгоритм будет весьма чувствителен к возможным оптимизациям со стороны компилятора. Если применить алгебраические преобразования, которые компилятор вполне может выполнить при заданной модели fast, получим следующее:

Ввиду того, что С вне цикла и является константой, равной 0, то

Y = A[i] - C ==> Y = A[i]  T = sum + Y ==> T = sum + A[i] sum = T ==> sum = sum + A[i] 

В итоге после оптимизации получим обычное суммирование в цикле, а это далеко не то, на что мы рассчитывали. Поэтому важно запретить компилятору проводить подобные перестановки и оптимизации, установив, например, флажок fp-model precise.

Кстати, интересны различные комбинации этих опций, потому что возникает ощущение, что precise и source делают одно и то же. Все модели делятся на 3 группы:

• A: precise, fast, strict
• B: source
• C: except

Соответственно, их можно «миксовать», но с учётом определённых оговорок:
• Нельзя использовать fast и except вместе, причём из-за того, что fast является дефолтной моделью, нельзя добавить except без других опций из групп A и B.
• Можно указывать только одну модель из группы А и одну из группы В. Если всё же указать более одной, будет использована последняя в строке компиляции (та, которая правее).
• Если except указана более одного раза, будет так же использоваться последняя опция

Поэтому в общем случае, precise и source будут задавать одну и ту же модель работы с числами с плавающей точкой. Но если задать fast и source вместе, то source задаст точность, с которой нужно округлять промежуточные результаты (соответственно названию, будет использоваться та точность, которая используется в коде).

А что у других компиляторов? Там всё похоже и смысл остается тот же – с помощью ключиков контролируются те же 5 основных правила компилятора при работе с числами с плавающей точкой, вот только ключи по умолчанию отличаются. Например, если взять компилятор Microsoft, то даже названия опций и моделей там такие же, как у Интеловского компилятора. Скажем, флажок fp:precise, который является дефолтным. Кстати, упор там (по умолчанию) делается всё же на безопасность вычислений, в то время как у Интела — на производительность (ключик fast=1).
Но есть различия в поведении компилятора – при опции precise у компилятора Microsoft будет использоваться максимальная точность (расширенная), то есть код

float a, b, c, d; double x; ... x = a*b + c*d; 

будет трактоваться компилятором примерно так:

float a, b, c, d; double x; ... register tmp1 = a*b; register tmp2 = c*d; register tmp3 = tmp1+tmp2; x = (double) tmp3; 

Нюансы, конечно, существенные, но при понимании того, что контролировать и как, можно без труда переходить на другой компилятор, главное, чтобы он давал разработчику эту возможность контроля.

Кстати, по этой теме в MSDN есть отличная статья, в которой в подробностях описано поведение компилятора Microsoft, и рассмотрено много примеров.

Мы же вернёмся к ещё одному примерчику, на этот раз на Фортране (я же упомянул научную тему в начале):

REAL T0, T1, T2; ... T0 = 4.0E + 0.1E + T1 + T2 

Вопрос в том, как это выражение будет считаться при ключике –fp-model fast? На основании таблички, представленной выше, можно предположить, что сложение может быть выполнено в произвольном порядке, будет использована точность single (одинарная), double (двойная), или extended double (расширенная) при вычислении промежуточных результатов, при этом константное значение может быть вычислено заранее.

Например, компилятор может интерпретировать наш код следующим образом:

REAL T0, T1, T2;  ... T0 = (T1 + T2) + 4.1E; 

Или

REAL T0, T1, T2; ... T0 = (T1 + 4.1E) + T2; 

При установке опции -fp-model source (или -fp-model precise, в случае отдельного использования они эквиваленты), сложение будет выполняться строго в заданном в коде порядке, будет использована одинарная точность (как в коде), константа может быть вычислена заранее, используя округление, заданное по умолчанию:

REAL T0, T1, T2; ... T0 = ((4.1E + T1) + T2); 

Ну и самый «жесткий» уровень контроля над точностью -fp-model strict.
В данном случае мы получим что-то подобное:

REAL T0, T1, T2; ... T0 = REAL ((((REAL)4.0E + (REAL)0.1E) + (REAL)T1) + (REAL)T2); 

Как и во всех моделях, отличных от fast, используется точность, заданная в коде (одинарная в данном случае). Константа не вычисляется заранее, потому что мы не знаем, какой режим округления будет выставлен во время выполнения приложения.

Собственно, это всё, о чём я хотел рассказать в рамках этого поста. Тема работы с числами с плавающей точкой очень обширна, и рассказать ещё есть о чём… скажем, кроме рассмотренных опций, есть так же флаги prec-div, prec-sqrt, -ftz, -assume:protect_parens, стандарт IEEE 754-2008, который поддерживается во многих компиляторах и в котором есть много чего любопытного… так что при должном интересе, мы ещё продолжим этот разговор.