Арифметика насыщенности - Saturation arithmetic

Арифметика с насыщением - это версия арифметики, в которой все операции, такие как сложение и умножение, ограничены фиксированным диапазоном между минимальным и максимальным значением.

Если результат операции больше максимального, он устанавливается (« фиксируется ») на максимум; если он ниже минимума, он ограничивается минимумом. Название происходит от того, как значение становится «насыщенным», когда достигает крайних значений; дальнейшее прибавление к максимуму или вычитание из минимума не повлияет на результат.

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

  • 60 + 30 → 90.
  • 60 + 43 → 100 ( не ожидалось 103.)
  • (60 + 43) - (75 + 75) → 0. ( не ожидаемый −47.) (100-100 → 0.)
  • 10 × 11 → 100 ( не ожидаемые 110).
  • 99 × 99 → 100 ( не ожидаемый 9801.)
  • 30 × (5-1) → 100. ( не ожидаемые 120.) (30 × 4 → 100.)
  • (30 × 5) - (30 × 1) → 70. ( не ожидаемые 120. не предыдущие 100.) (100 - 30 → 70.)

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

Современное использование

Обычно микропроцессоры общего назначения не реализуют целочисленные арифметические операции с использованием арифметики насыщения; вместо этого, они используют проще в реализации модульной арифметики , в которой значение , превышающее значение максимального « обернуть вокруг » до минимального значения, как часы на часы , проходящих от 12 до 1. В аппаратных средств, модульная арифметике с минимумом ноль и максимум r n - 1, где r - основание системы счисления, могут быть реализованы простым отбрасыванием всех цифр, кроме младших n . Для двоичного оборудования, которым является подавляющее большинство современного оборудования, основание системы счисления равно 2, а цифры - биты.

Однако, хотя арифметика с насыщением более сложна в реализации, она имеет множество практических преимуществ. Результат максимально приближен к истинному ответу; для 8-битной двоичной арифметики со знаком, когда правильный ответ равен 130, гораздо менее удивительно получить ответ 127 из арифметики с насыщением, чем получить ответ -126 из модульной арифметики. Точно так же для 8-битной двоичной арифметики без знака, когда правильный ответ равен 258, менее удивительно получить ответ 255 от насыщающей арифметики, чем получить ответ 2 от модульной арифметики.

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

Кроме того, арифметика насыщения позволяет использовать эффективные алгоритмы для решения многих задач, особенно при цифровой обработке сигналов . Например, регулировка уровня громкости звукового сигнала может привести к переполнению, а насыщенность вызывает значительно меньшие искажения звука, чем циклический переход. По словам исследователей Г.А. Константинидеса и соавт .:

При сложении двух чисел с использованием представления в виде дополнения до двух переполнение приводит к явлению «циклического перехода». Результатом может быть катастрофическая потеря отношения сигнал / шум в системе DSP. Поэтому сигналы в схемах DSP обычно либо масштабируются соответствующим образом, чтобы избежать переполнения для всех входных векторов, кроме самых крайних, либо генерируются с использованием арифметических компонентов насыщения.

Реализации

Арифметические операции с насыщением доступны на многих современных платформах, и, в частности, было одним из расширений, сделанных платформой Intel MMX специально для таких приложений обработки сигналов. Эта функциональность также доступна в более широких версиях целочисленных команд SSE2 и AVX2 .

Арифметика насыщения для целых чисел также была реализована в программном обеспечении для ряда языков программирования, включая C , C ++ , таких как GNU Compiler Collection , LLVM IR и Eiffel . Это помогает программистам лучше предвидеть и понимать последствия переполнения, а в случае компиляторов обычно выбирают оптимальное решение.

Насыщение сложно реализовать эффективно в программном обеспечении на машине, использующей только модульные арифметические операции, поскольку для простых реализаций требуются ветви, которые создают огромные задержки в конвейере. Однако можно реализовать сложение и вычитание с насыщением в программном обеспечении без ветвей , используя только модульные арифметические и побитовые логические операции, которые доступны на всех современных процессорах и их предшественниках, включая все процессоры x86 (назад к исходному Intel 8086 ) и некоторые популярные 8-битные процессоры (некоторые из которых, например Zilog Z80 , все еще находятся в производстве). С другой стороны, на простых 8-битных и 16-битных процессорах алгоритм ветвления может быть быстрее, если он запрограммирован на сборке, поскольку нет конвейеров, которые можно было бы остановить, и каждая инструкция всегда занимает несколько тактовых циклов. На x86, который предоставляет флаги переполнения и условные перемещения , возможен очень простой код без ветвлений.

Хотя арифметика насыщения менее популярна для целочисленной арифметики на оборудовании, стандарт с плавающей запятой IEEE , наиболее популярная абстракция для работы с приблизительными действительными числами , использует форму насыщения, при которой переполнение преобразуется в «бесконечность» или «отрицательную бесконечность», и любая другая операция над этим результатом продолжает давать то же значение. Это имеет преимущество перед простым насыщением в том, что последующие операции по уменьшению значения не приведут к ошибочно «разумному» результату, например, при вычислении . В качестве альтернативы могут быть особые состояния, такие как «переполнение экспоненты» (и «истощение экспоненты»), которые аналогичным образом сохранятся в последующих операциях, или вызовут немедленное завершение, или будут проверяться как в FORTRAN для IBM704 (октябрь 1956 г.). IF ACCUMULATOR OVERFLOW ...

Смотрите также

Заметки

Внешние ссылки