Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Categories:

Exact arithmetics: Integers and Reals (and “48 bits should be enough” ☺)

Вот почитаешь «Software disenchantment» Тонского, и сразу хочется вернуться к дизайну компьютерных архитектур времён суперкомпьютеров CDC 3000 Сеймура Крэя или Лебедевскомого БЭСМ-6, где в самом деле считали сколько чего нужно, а не разбрасывались ресурсами попусту.

Вот например для кодирования указателей, целых чисел и чисел с плавающей запятой стандартной точности там использовалось по 48 бит, очень приятная длина машинного слова. Было понятно, что 32 бита — это слишком мало, а 64 бита — избыточно для большинства применений.

Я вообще большой поклонник машинной арифметика с fallback'ами, без overflow/underflow. То есть, если результат какого-то вычисления не влезает в машинное слово, в то место, куда надо положить результат, вписывается 0b10...0 (со значением “не влезло на полях, смотрите в сносках”), а настоящее вычисление производится при помощи библиотеки арифметики произвольной точности (“bignum”) и записывается в специальную “таблицу сносок” в отдельном месте памяти, в виде записи “по адресу 0x348973794893 не влезло число, вот оно: 12164510 0408832000”. Ну и соответственно, всё это работает прозрачно: если запустилась какая-то машинная арифметическая операция, а операнд оказался 0b10...0, то вместо машинной операции запускается fallback из bignum-библиотеки, и так далее. При таком подходе понятно как оценивать, какая нужна длина машинного слова: нужно, чтобы на практике необходимость вызывать fallback'и была очень, очень редка, потому что они работают в тысячи и тысячи раз медленнее, чем встроенные операции. Но с другой стороны, каждый лишний бит в машинном слове означает, что встроенная арифметика будет медленнее, транспорт из памяти будет медленнее и в кеши (каждого уровня) будет влезать меньше полезного, чем могло бы. Исходя из этих соображений 48 — очень хороший компромисс.

Кроме того, это хороший компромисс и для чисел с плавающей запятой. 24, 48 и 96 битов для чисел с правой запятой — это гораздо более адекватные стандарты для low-precision real, standard-precision real и high-precision real, чем 16, 32 и 64.

Кстати, в этой области есть интересные недавние подвижки. На смену стандартным IEEE-754 floats предложили новую систему Posit, которая
(а) отказывается от всех этих +0, -1, бесконечностей и NaNов в пользу единственного зарезирвированного значения (на побитовом уровне, кстати, кодируемого тем же самым 0b10...0), которое сигнализирует, что результат операции не является вещественным числом, а чем он конкретно является нужно трактовать по контексту; а в случае когда происходит операция с непонятным результатом, предлагается чтобы случался трап (recoverable exception) и программист сам решал, чего там делать.
(b) использует побитовое кодирование, которое позволяет сравнивать вещественные числа при помощи обычных целочисленных операций сравнения
(c) более разумно распределяет представимые числа по вещественному лучу (плотнее вокруг 1 и 0 и без аномалии с subnormals), что приводит к немножко меньшей потере точности на типовых арифметических операциях и очень хорошей дискретизации сигмоидных функций,
(d) система очень дружественна к операции FUSED ACCUMULATE-MULTIPLY — это такая операция с использованием промежуточного “регистра” большого размера, позволяющая вычислять точное (т.е. без промежуточных округлений) произведение матриц. Это операция является краеугольным камнем всех вычислений высокой точности на числах с плавающей запятой.

Автор системы Джон Густафсон прежде экспериментировал с очень неортодоксальными системами представления чисел с плавающей запятой, но потом внял суровой критике Вэлвла Кагана (основного разработчика IEEE-754, 85-летнего корифея и мастадонта в этой области), и придумал достаточно скромно отклоняющуюся от IEEE-754 систему Posit. Отсутствие всяких NaN'ов с бесконечностями имеет недостатки для SIMD-вычислений, где “ignore and calculate as if it works” (т.е. графика в компьютерных играх), но если требуется предсказуемость вычислений (все остальные случаи), то подход Posit лучше — либо пусть программист заранее проставит флаги, что делать если случилось какое-нибудь деление на ноль или корень из отрицательного, либо пусть ловит эксепшн и решает проблему по-существу.

В интервальной арифметике на позитах “особое значение” в качестве левой границы интерпретируется как -∞, а правой — как +∞. Поэтому в интервальной арифметики восстанавливаются все ценные фичи IEEE-754 (в т.ч. algebraic integrity) и даже больше. IEEE-754«+∞» = (MAX_POS_VALUE, 0b10...0), IEEE-754«-∞» = (0b10...0, MIN_NEG_VALUE), IEEE-754«+0» = (0, MIN_POS_VALUE), IEEE-754«-0» = (MAX_NEG_VALUE, 0).

Надеюсь, когда-нибудь мы доживём и до того, что компьютеры будут на уровне железа поддерживать хорошую интервальную арифметику, чтобы можно было прогнать числомолотилку и получить “обоснованную догадку” (именно это, кстати, и значит слово «posit»), а жесткую вилку, в пределах которой обязан быть результат. Густафсон в общем именно этим сейчас и занимается, насколько я понимаю. Он известен тем, что предложил подход к интервальной арифметике, базирующийся не на замкнутых конечных интервалах, а на связных подмножествах проективной вещественной прямой ℝ̂, получилось очень элегантно — даже корифей и мастадонт интервальной арифметики Ульрих Кулиш (по забавному стечению обстоятельств тоже 85-летний) был крайне впечатлён и отметил, что стандарт интервальной арифметики IEEE-1788, который Кулиш несколько лет разрабатывал с ещё несколькими десятками специалистов, благодаря работам Густафсона устарел ещё до принятия.

В ближайшие годы несомненно будут доделаны языки программирования, поддерживающие точную вещественную арифметику (я к этому имею прямое отношение) в том смысле, что на них можно будет задавать манипуляции над вещественными числами произвольной сложности таким образом, что сколь угодно малая погрешность на выходе будет теоретически достижима, если обеспечить достаточно малую погрешность на входе (что для вычислений ab inito выполнено автоматически) и достаточное количество вычислительных ресурсов (а вот с этим будет проблема). Несомненно также и то, что применительно к инженерным задачам (от моделирования балки до симуляции плазмы) вычресурсов для применения точной арифметики не будет хватать на порядки, и смысл записи решения в терминах вещественной арифметики тут будет не в том, чтобы “запустить и оно посчитало само”, но в том, чтобы иметь работающий потенциально эталон (и слишком тяжеловесный для регулярного практического использования), на который неточным вычислительным алгоритмам можно равняться. Равняться можно в том смысле, что “один разок можно по-честному прогнать на суперкомпьютере за 2-3 месяца” и посмотреть, насколько точный результат отличается от приблизительного, который вычисляется за 2-3 секунды. Но гораздо более важна возможность равняться в смысле возможности писать математические доказательства того, что приблизительные алгоритмы сходятся, стабильны, гарантируют с такой-то вероятностью погрешность в таких-то пределах, и т.д. И для этого нам нужно кроме точных вычислений иметь формальную модель вычислений приближенных, соответствующую фактической модели, реализованной в процессоре. И в качестве таковой интервальные вычисления, капсулирующие проблематику промежуточных округлений, подходят гораздо больше, чем просто вычисления с плавающей запятой по IEEE-754, где эффект округлений хоть и сбалансирован, но абсолютно непредсказуем. Для интервальных вычислений про некоторые алгоритмы можно доказать строгие гарантии — точный результат отличается от приближенного, не более чем на столько-то. Про IEEE-754 такого шанса нет вообще, там любые гарантии могут быть только статистическими.
Subscribe

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 21 comments

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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