Арифметика насыщения

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

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

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

60 + 30 → 90.
60 + 43 → 100. ( не ожидаемое 103.)
(60 + 43) − (75 + 25) → 0. ( не ожидаемое 3.) (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.)

Вот еще один пример насыщенного вычитания , когда вместо этого допустимый диапазон от 0 до 100:

30–60 → 0. ( не ожидаемое -30.)

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

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

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

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

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

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

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

Реализации

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

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

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

Хотя арифметика насыщения менее популярна для целочисленной арифметики в аппаратном обеспечении, стандарт IEEE с плавающей запятой , самая популярная абстракция для работы с приблизительными действительными числами , использует форму насыщения, при которой переполнение преобразуется в «бесконечность» или «отрицательную бесконечность». и любая другая операция с этим результатом продолжает давать то же значение. Это имеет преимущество перед простым насыщением, заключающееся в том, что последующие операции, уменьшающие значение, не приведут к получению обманчиво «разумного» результата, например, при вычислении ${\textstyle {\sqrt {x^{2}-y^{2}}}}$ . В качестве альтернативы могут существовать специальные состояния, такие как «переполнение экспоненты» (и «недополнение экспоненты»), которые аналогичным образом будут сохраняться в последующих операциях или вызывать немедленное завершение или проверяться, как в IF ACCUMULATOR OVERFLOW ... как в FORTRAN для IBM 704 (октябрь 1956 г.).

См. также

Цензура (статистика)

Примечания

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

Ссылки

^ Г. А. Константинидес, ПИК Чунг и В. Лук. Синтез арифметических архитектур насыщения .
^ «Внутреннее устройство коллекции компиляторов GNU (GCC): арифметика» . Документация GCC . Встроенные языковые функции
^ «Насыщающая арифметика без ветвей» . locklessinc.com . Архивировано из оригинала 13 февраля 2019 г.

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

SARITH: Safe ARITHmetic – Отчет о ходе работы : Отчет о компоненте арифметики насыщения для Eiffel .
saturation — библиотека C++, предназначенная только для заголовков, для насыщения арифметических операций с точки зрения встроенных функций GCC Overflow.

[1] Фактически, сбоев арифметика ненасыщения также может страдать от ассоциативности и дистрибутивности в средах с ограниченной точностью, но такие сбои, как правило, менее очевидны.

[2] Г. А. Константинидес, ПИК Чунг и В. Лук. Синтез арифметических архитектур насыщения .

[3] «Внутреннее устройство коллекции компиляторов GNU (GCC): арифметика» . Документация GCC . Встроенные языковые функции

[4] «Насыщающая арифметика без ветвей» . locklessinc.com . Архивировано из оригинала 13 февраля 2019 г.

[а]

[1]

[2]

[3]