В 1993 году компания Intel выпустила мощный процессор Pentium, положив начало долгоживущей серии высокопроизводительных чипов.^{1 примеч.} Pentium содержит блок вычислений с плавающей точкой (FPU), который способен быстро вычислять такие функции, как синус, косинус, логарифм и экспоненциальную функцию. Но как именно Pentium выполняет эти вычисления?

Ранние процессоры Intel использовали алгоритмы класса CORDIC (итерационные алгоритмы на сдвиге и сложении), однако в Pentium компания перешла к полиномиальной аппроксимации этих трансцендентных функций, что позволило выполнять вычисления значительно быстрее. Коэффициенты полиномов были тщательно оптимизированы и сохранены в специальной постоянной памяти (ROM), встроенной в FPU. Несмотря на то, что Pentium — сложный микрочип, содержащий 3,1 миллиона транзисторов, рассмотреть эти транзисторы под микроскопом и прочитать хранящиеся там константы вполне возможно.

Первая часть статьи описывает, как реализована постоянная память с константами FPU на уровне аппаратуры. Вторая часть объясняет, как Pentium использует эти константы для вычисления функций sin, log и других.

На фотографии ниже показан кремниевый кристалл процессора Pentium, размером примерно с ноготь, под микроскопом. Основные функциональные блоки подписаны: блок вычислений с плавающей точкой находится в нижнем правом углу. Постоянная память с константами (выделена) расположена в нижней части этого блока. Выше находится ROM с микрокодом — микропрограммными инструкциями, задающими пошаговое выполнение сложных операций. При выполнении, например, инструкции вычисления синуса микрокод направляет FPU через десятки шагов, используя константы из ROM для вычисления аппроксимационного полинома.

Нахождение числа π в постоянной памяти

В двоичной системе π записывается как 11.00100100001111110… Что это значит? Число 11 слева от двоичной точки — это просто 3 в двоичном представлении. (Двоичная точка — то же самое, что десятичная, только для системы счисления по основанию 2.) Цифры справа от точки имеют значения 1/2, 1/4, 1/8 и так далее. Таким образом, двоичное значение 11.001001000011… соответствует 3 + 1/8 + 1/64 + 1/4096 + 1/8192 + …, что совпадает с десятичным значением числа π.

Так как π — иррациональное число, его битовая последовательность бесконечна и не повторяется; значение в ROM обрезано до 67 бит мантиссы и сохранено в виде числа с плавающей точкой.

Число с плавающей точкой представляется двумя частями: экспонентой и значащей частью (мантиссой). Числа с плавающей точкой включают как очень большие величины вроде 6.02×10²³, так и очень малые вроде 1.055×10⁻³⁴. В десятичной записи у 6.02×10²³ значащая часть (мантисса) равна 6.02, а экспонента — 23 (10²³). В двоичной системе число с плавающей точкой представляется аналогично — со значащей частью и экспонентой, — только значащая часть умножается на степень 2, а не 10. Например, π в формате с плавающей точкой записывается как 1.1001001…×2¹.

На диаграмме ниже показано, как π закодировано в чипе Pentium. При увеличении становится видна постоянная память с константами (constant ROM). Ещё большее увеличение небольшого участка ROM показывает строки транзисторов, в которых хранятся константы. Стрелки указывают на транзисторы, представляющие битовую последовательность 11001001, где бит 0 кодируется наличием транзистора (вертикальная белая линия), а бит 1 — его отсутствием (сплошной тёмный кремний). Каждый увеличенный чёрный прямоугольник внизу содержит два потенциальных транзистора и, соответственно, хранит два бита. Ключевая идея в том, что по рисунку «полосок» можно восстановить расположение транзисторов и, следовательно, значение каждой константы — в данном случае π.

Биты «разнесены» из-за того, что каждая ROM строка содержит восемь перемежающихся констант — это упрощает компоновку. Над битами ROM расположена схема мультиплексоров, которая выбирает нужную константу из восьми в активной строке. Иными словами, выбор строки и затем одной из восьми констант в этой строке даёт доступ к одной из 304 констант в ROM. В ROM хранится гораздо больше разрядов числа π, чем показано здесь; на диаграмме показаны 8 из 67 бит значащей части.

Реализация постоянной памяти с константами

ROM построена на транзисторах МОП — именно такие транзисторы используются во всех современных компьютерах. На схеме ниже показана структура МОП-транзистора. Интегральная схема создаётся на кремниевой подложке. Области кремния легируются примесями, формируя «диффузионные» области с требуемыми электрическими свойствами. Транзистор можно рассматривать как переключатель, который позволяет току течь между двумя диффузионными областями — истоком и стоком. Управление транзистором осуществляется затвором, выполненным из особого вида кремния — поликремния. Подача напряжения на затвор открывает канал между истоком и стоком; без напряжения ток перекрыт. В большинстве компьютеров применяются два типа МОП-транзисторов: n-канальные (NMOS) и p-канальные (PMOS). Оба типа имеют схожую конструкцию, но противоположное легирование: NMOS использует n-тип диффузионных областей, как показано ниже, тогда как PMOS — p-тип. Поскольку эти типы являются комплементарными, схемы, построенные на их сочетании, называются КМОП (CMOS).

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

На схеме ниже показано восемь бит хранения. Каждый из четырёх розовых кремниевых прямоугольников содержит два потенциальных транзистора. Если поликремниевый затвор пересекает кремний, формируется транзистор; если нет — транзистора нет. Когда активируется линия выбора (горизонтальный поликремний), она включает все транзисторы в этой строке. Если транзистор присутствует, соответствующий бит ROM равен 0, потому что транзистор притягивает выходную линию к «земле». Если транзистора нет, бит ROM равен 1. Таким образом, именно рисунок расположения транзисторов определяет данные, хранящиеся в ROM. Объём ROM — 26144 бита (304 слова по 86 бит), поэтому возможных транзисторов тоже 26144.

На фотографии ниже показан нижний слой металлизации (M1): вертикальные металлические проводники, формирующие выходы ROM и подводящие «землю» к ROM. (На схеме выше эти проводники изображены серыми линиями.) Поликремниевые транзисторы (или зазоры на их месте) едва заметны между металлическими линиями. Большинство маленьких кружков — это вольфрамовые контакты к кремнию или поликремнию; сравните с предыдущим фото. Другие кружки — это вольфрамовые переходы (виа) на верхний слой металлизации (M2), где проложены горизонтальные соединения, удалённые мной для этого снимка. Небольшие металлические «язычки» работают как перемычки между горизонтальными линиями выбора в M2 и поликремниевыми линиями выбора. Верхний слой металлизации (M3, не виден) несёт более толстые вертикальные шины основных магистралей питания и «земли» кристалла. Таким образом, три слоя металлизации чередуются по направлению — горизонтальная и вертикальная разводка — с переходами между слоями.

ROM реализована в виде двух решёток ячеек (ниже): одна хранит экспоненты, другая — значащие части (мантиссы), как показано ниже. Решётка экспонент (слева) содержит 38 строк и 144 столбца транзисторов, а решётка значащих частей (справа) — 38 строк и 544 столбца. Для более удобной компоновки каждая строка хранит восемь разных констант; биты перемежаются: сначала записан первый бит восьми констант, затем второй бит восьми констант и так далее. Таким образом, при 38 строках ROM содержит 304 константы; у каждой константы 18 бит в части экспоненты и 68 бит в части мантиссы.

Часть экспоненты у каждой константы состоит из 18 бит: 17 бит экспоненты и одного бита знака мантиссы, а значит и самой константы. Отдельного знакового бита для экспоненты нет, потому что экспонента хранится со смещением на 65535 (0x0ffff), что исключает отрицательные значения. Запись значащей части длиной 68 бит в ROM включает «загадочный» флаговый бит^{2 примеч.}, за которым следует 67-битная значащая часть; первый бит значащей — целая часть, остальные — дробная.^{3 примеч.} Полное содержимое ROM приведено в приложении в конце статьи.

Чтобы выбрать конкретную константу, «схема выбора строки» между двумя секциями активирует одну из 38 строк. Эта строка выдаёт 144+544 бита на схему выборки над ROM. В этой схеме 86 мультиплексоров; каждый мультиплексор выбирает один бит из группы из восьми, тем самым выбирая нужную константу. Биты значащей части поступают в тракт данных блока вычислений с плавающей точкой, расположенный выше ROM. А вот схема обработки экспонент находится в левом верхнем углу FPU, на заметном расстоянии от ROM, поэтому биты экспонент передаются по шине в соответствующую схему.

Схема выбора строки состоит из логики для декодирования номера строки и мощных драйверов тока, которые активируют выбранную строку ROM. На фотографии ниже — крупный план двух драйверов строк рядом с ячейками ROM. Слева транзисторы PMOS и NMOS образуют вентиль выбора строки. Далее, более крупные NMOS и PMOS входят в состав драйвера. Крупные квадратные структуры — это биполярные транзисторы NPN; Pentium необычен тем, что сочетает биполярные транзисторы и КМОП, то есть использует технику BiCMOS.^{4 примеч.} Каждый драйвер занимает по высоте четыре строки ROM, поэтому драйверы расположены горизонтально по четыре; на фото виден только один.

Структура блока вычислений с плавающей точкой

Блок вычислений с плавающей точкой организован так, что данные текут вертикально через горизонтально расположенные функциональные узлы, как показано ниже. Функциональные узлы — сумматоры, схемы сдвига, регистры и компараторы — выстроены рядами. Эта совокупность функциональных узлов, через которые проходит поток данных, называется трактом данных (datapath).^{5 примеч.}

Каждый функциональный узел собран из ячеек — по одной на каждый бит, где слева расположен старший бит, а справа — младший. Все ячейки имеют одинаковую ширину — 38,5 мкм, — поэтому функциональные узлы можно соединять словно кирпичики Lego, минимизируя объёмы разводки. Высота функционального узла варьируется по необходимости, в зависимости от сложности схемы. Типичная разрядность узлов — 69 бит, но некоторые шире, из-за чего по краям тракта данных получается неровный контур.

Именно такая ячеечная конструкция объясняет, почему в каждой строке ROM хранится по восемь констант. Один бит в ROM требует всего одного транзистора, который намного уже, чем, скажем, сумматор. Поэтому размещение одного бита в каждой ячейке шириной 38,5 мкм растратило бы пространство. Сжатие бит ROM в узкую полосу тоже неэффективно: для подключения каждого бита ROM к соответствующему биту тракта данных потребовалась бы диагональная проводка. Если же в каждую ячейку поместить по восемь бит для восьми разных констант, ширина ячейки ROM совпадает с остальной частью тракта данных, и выравнивание бит сохраняется. В итоге компоновка ROM на кристалле получается плотной, эффективной и соответствующей ширине всего FPU.

Полиномиальная аппроксимация: не используйте ряд Тейлора

Далее перейдём от «железа» к константам. Если заглянуть в таблицу констант ROM в приложении, можно заметить, что многие значения близки к обратным величинам или обратным факториалам, но всё же не совпадают. Например, одна константа равна 0.1111111089 — это близко к 1/9, но заметно отличается. Другая почти равна 1/13! (факториал), но с погрешностью около 0,1 %. В чём дело?

Pentium использует полиномы для аппроксимации трансцендентных функций (синус, косинус, тангенс, арктангенс, а также показательную функцию 2^x (по основанию 2) и логарифмы). Ранние блоки FPU Intel — от 8087 до 486 — применяли алгоритм CORDIC, который формировал результат по одному биту за раз. Однако в Pentium, благодаря быстрому умножителю и более объёмной ROM используются полиномы — вычисления получаются в два–три раза быстрее, чем в 486 (алгоритм CORDIC).

Из курса математического анализа вы можете помнить, что полином ряда Тейлора аппроксимирует функцию в окрестности некоторой точки (обычно 0). Например, уравнение ниже задаёт ряд Тейлора для синуса.

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

Проблема в том, что ряд Тейлора очень точен возле 0, но погрешность резко возрастает на границах диапазона аргумента, как видно на левом графике ниже. При реализации функции нам нужна точность по всему диапазону, а не только около 0, поэтому ряд Тейлора сам по себе не подходит.

Одно из улучшений называется «редукция диапазона» (range reduction): «сжимаем» аргумент к меньшему диапазону, попадая в «плоскую», точную часть.^{6 примеч.} Правый график показывает погрешность (абсолютную ошибку) для ряда Тейлора на более узком интервале [−1/32, 1/32]. Погрешность падает драматически — примерно на 22 порядка (обратите внимание на шкалу). Однако на границах диапазона погрешность всё равно «взлетает» тем же образом. Как бы сильно мы ни сжимали диапазон, в середине ошибка почти отсутствует, а на краях остаётся значительной.^{7 примеч.}

Как избавиться от ошибки на границах диапазона? Хитрость в том, чтобы «подкрутить» коэффициенты ряда Тейлора особым образом: немного увеличить ошибку в середине, но куда сильнее уменьшить её на краях. Поскольку мы хотим минимизировать максимальную ошибку на всём интервале (критерий минимакса), такой компромисс выгоден. Конкретно, коэффициенты можно оптимизировать с помощью процесса, называемого алгоритмом Ремеза.^{8 примеч.} Как видно ниже, изменение коэффициентов менее чем на 1% радикально повышает точность. Оптимизированная функция (синяя) даёт значительно меньшую ошибку на всём диапазоне и потому гораздо лучше подходит для аппроксимации, чем ряд Тейлора (оранжевая).

Подытожим: ряд Тейлора полезен в математическом анализе, но его не стоит использовать для приближённого вычисления функции. Намного лучшая аппроксимация получается при очень небольшом изменении коэффициентов по алгоритму Ремеза. Это объясняет, почему коэффициенты в ROM «почти, но не совсем» совпадают с рядом Тейлора.

Arctan

Теперь посмотрим на константы Pentium для разных трансцендентных функций. В постоянной памяти содержатся коэффициенты для двух полиномов arctan: один для одинарной точности, другой — для двойной. Эти полиномы почти совпадают с рядом Тейлора, но были изменены ради повышения точности. Кроме того, в ROM хранятся значения arctan(1/32) … arctan(32/32); процесс редукции диапазона использует эти константы вместе с тригонометрическим тождеством, чтобы сузить диапазон аргумента до [−1/64, 1/64].^{9 примеч.}

На графике ниже показана ошибка полинома arctan из Pentium (синий) по сравнению с рядом Тейлора той же длины (оранжевый). Полином Pentium выигрывает благодаря оптимизации по Ремезу. Хотя полином Тейлора заметно более ровный в центре, его ошибка резко растёт у границ. Полином Pentium колеблется сильнее, но удерживает низкую ошибку на всём диапазоне. Вне этого диапазона ошибка у полинома Pentium взлетает, но это не имеет значения.

Тригонометрические функции

У синуса и косинуса есть по две полиномиальные реализации: одна с 4 членами в ROM и одна с 6 членами в ROM. (Заметьте, коэффициенты, равные 1, в ROM не хранятся.) В таблице констант также есть 16 значений вроде sin(36/64) и cos(18/64), которые используются для редукции диапазона аргумента.^{¹⁰ примеч.} Тангенс Pentium вычисляет делением синуса на косинус. График я не привожу, поскольку ошибка у реализации Pentium получилась хуже, чем у ряда Тейлора, так что либо у меня ошибка в коэффициенте, либо я делаю что-то не так.

Экспонента

В Pentium есть инструкция для вычисления функции 2ˣ.^{¹¹ примеч.} В ROM лежат два набора полиномиальных коэффициентов для экспоненты: один с 6 членами и один с 11 членами. Любопытно, что полиномы в ROM вычисляют eˣ, а не 2ˣ. Следовательно, Pentium должен масштабировать аргумент через ln(2) — соответствующая константа есть в ROM. На графике ниже показано преимущество полинома Pentium по сравнению с полиномом ряда Тейлора.

Полином обслуживает узкий диапазон аргумента [−1/128, 1/128]. Обратите внимание: при вычислении функции 2ˣ в двоичной системе целая часть аргумента обрабатывается тривиально: она становится экспонентой результата. Поэтому функции нужно обрабатывать лишь диапазон [1, 2]. Для редукции диапазона в ROM хранится 64 значения вида 2^n/128-1. Чтобы сузить диапазон с [1, 2] до [−1/128, 1/128], из аргумента вычитается ближайшее n/128, а затем результат умножается на соответствующую константу из ROM. Константы распределены неравномерно, по-видимому, ради точности: местами шаг 4/128, а местами 2/128.

Логарифм

Pentium умеет вычислять логарифмы по основанию 2.^{12 примеч.} Коэффициенты задают полиномы для гиперболического арктангенса, который тесно связан с логарифмом. Подробности см. в примечаниях. В ROM также есть 64 константы для редукции диапазона: log₂(1 + n/64) для нечётных n от 1 до 63. Необычная особенность этих констант — разбиение каждой на две части для увеличения точности: верхняя часть имеет точность 40 бит, нижняя — 67 бит, в сумме давая 107-битную константу. Дополнительные биты нужны, потому что логарифмы сложно вычислять с высокой точностью.

Прочие константы

Набор инструкций x87 предоставляет прямой доступ к нескольким константам — 0, 1, π, log₂(10), log₂(e), log₁₀(2) и logₑ(2), — поэтому эти константы хранятся в ROM. (Эти логарифмы полезны для смены основания при вычислении логарифмов и экспоненциальных функций.) В ROM также есть другие константы для внутреннего использования блоком вычислений с плавающей точкой, такие как −1, 2, 7/8, 9/8, π/2, π/4 и 2·log₂(e). Кроме того, ROM содержит битовые маски для извлечения части машинного слова, например для доступа к 4-битовым BCD-цифрам внутри слова. Хотя большинство значений мне удалось интерпретировать, остаются и загадки — например, маска с загадочным значением 0x3e8287c. В конце ROM есть 34 неиспользованные записи; в них лежат слова, содержащие выразительное шестнадцатеричное значение 0xbad или, возможно, 0xbadfc — «плохая константа с плавающей точкой».

Как я исследовал ROM

Чтобы проанализировать Pentium, я удалил металлические и оксидные слои с помощью различных химикатов (серная кислота, фосфорная кислота, Whink). (Позже я обнаружил, что простая шлифовка кристалла тоже работает на удивление хорошо.) Затем я сделал множество микрофотографий ROM. Техпроцесс этого Pentium — 800 нм, то есть лишь чуть больше верхней границы видимого диапазона (≈700 нм). Поэтому кристалл можно изучать под оптическим микроскопом, хотя это уже близко к пределам. Чтобы восстановить содержимое ROM, я кропотливо просматривал снимки ROM, анализируя каждый из 26 144 бит и отмечая каждый транзистор. Разобравшись с форматом ROM, я написал программы, которые комбинируют простые функции во множестве сочетаний, чтобы вывести математические выражения вроде arctan(19/32) или log₂(10). Поскольку коэффициенты полиномов оптимизированы, а в считанных данных ROM есть битовые ошибки, программе потребовались проверки неточных совпадений — как численных, так и побитовых. Наконец, нужно было определить, как именно эти константы используются в алгоритмах.

Выводы

Изучая под микроскопом постоянную память с константами блока вычислений с плавающей точкой Pentium, можно извлечь все 304 хранящиеся там константы. Мне удалось определить смысл большинства из них и реконструировать некоторые алгоритмы вычислений с плавающей точкой, используемые в Pentium. Эти константы наглядно показывают, как полиномы могут эффективно вычислять трансцендентные функции. Хотя полиномы ряда Тейлора хорошо известны, их точность оказывается удивительно низкой, поэтому их следует избегать. Небольшие изменения коэффициентов по алгоритму Ремеза, напротив, дают значительно более качественные полиномы.

На уровне архитектуры это тот же класс решений: выбор инвариантов точности и латентности, разбиение на слои (редукция диапазона, таблицы, полином), контракт интерфейсов. На курсе Software Architect разбираются подобные инженерные компромиссы и шаблоны проектирования вычислительных подсистем.

Раньше я разбирал константы с плавающей точкой, хранящиеся в сопроцессоре 8087. В Pentium таких констант 304, тогда как в 8087 — всего 42, что позволяет поддерживать более эффективные алгоритмы. Кроме того, 8087 был внешним блоком вычислений с плавающей точкой, тогда как FPU Pentium встроен в сам процессор. Различия между 8087 (1980 год, 65 000 транзисторов) и Pentium (1993 год, 3,1 млн транзисторов) обусловлены экспоненциальным ростом числа транзисторов, описанным законом Мура.

Приложение: постоянная память с константами

В таблице ниже перечислены 304 константы из постоянной памяти (ROM) блока FPU Pentium. В первых четырёх столбцах показаны значения, хранящиеся в ROM: экспонента, бит знака, флаговый бит и значащая часть (мантисса). Чтобы избежать отрицательных экспонент, они записаны со смещением, равным 0x0ffff. Например, значение 0x0fffe соответствует экспоненте −1, а 0x10000 — экспоненте 1. Приблизительное десятичное значение константы приведено в столбце «value».

Специальные значения выделены цветом. В частности, «обычные» числа — чёрным. Константы с экспонентой, целиком состоящей из нулей, — синим; с экспонентой, целиком из единиц, — красным; с необычно большой или малой экспонентой — зелёным; по-видимому, это битовые маски, а не числа. Неиспользуемые записи — серым. Неточные константы (из-за оптимизации по Ремезу) помечены символом приближения «≈».

Примечания (осторожно, много текста)

1. В этой статье я разбираю версию «P5» оригинального процессора Pentium. Легко запутаться во всех «Pentium», потому что «Pentium» стал брендом с множеством микроархитектур, линеек и продуктов. Оригинальный Pentium (1993) сменили Pentium Pro (1995), Pentium II (1997) и так далее.

Оригинальный Pentium использовал микроархитектуру P5 — суперскалярную микроархитектуру, которая была передовой, но всё ещё исполняла инструкции в порядке поступления, как традиционные микропроцессоры. Оригинальный Pentium пережил несколько существенных ревизий. Первым продуктом был 80501 (кодовое имя P5) с 3,1 млн транзисторов. Энергопотребление этих чипов оказалось разочаровывающим, поэтому Intel улучшила кристалл и выпустила 80502 с кодовым именем P54C. По топологии на кристалле P5 и P54C выглядят почти одинаково, но в P54C добавили схемы для многопроцессорности, что увеличило число транзисторов до 3,3 млн. Крупнейшим изменением в оригинальном Pentium стал Pentium MMX с номером 80503 и кодовым именем P55C. Pentium MMX добавил 57 векторных инструкций и содержал 4,5 млн транзисторов. Блок с плавающей запятой (FPU) был переработан в MMX, но константы, вероятно, остались теми же. 

2. Я не знаю, что означает флаговый бит в ПЗУ; я условно называю его «флагом». Моя смелая догадка — он помечает те записи ПЗУ, которые нужно исключить из контрольной суммы при проверке ПЗУ. 

3. Внутренне мантисса имеет один целочисленный (старший) бит, а остальное — дробная часть, поэтому двоичная точка (аналог десятичной точки) стоит после первого бита. Однако это не единственный способ представления мантиссы. Формат x87 с расширенной двойной точностью (80 бит) использует тот же подход. А вот 32-битный (одинарной точности) и 64-битный (двойной точности) форматы опускают первый бит и используют «имплицитную единицу». Это даёт «бесплатно» ещё один бит мантиссы, поскольку в нормальных случаях первый бит мантиссы равен 1. 

4. Необычная особенность Pentium — использование биполярных транзисторов NPN вместе с КМОП-схемами; такую технологию называют BiCMOS. Добавив несколько дополнительных этапов к стандартному КМОП-процессу, можно сформировать биполярные транзисторы. В Pentium схемы BiCMOS применялись широко, поскольку они уменьшали задержки сигналов до 35%. Intel также использовала BiCMOS в процессорах Pentium Pro, Pentium II, Pentium III и Xeon (но не в Pentium MMX). Однако по мере снижения рабочих напряжений выгода от биполярных транзисторов уменьшалась, и от BiCMOS в итоге отказались.

В ПЗУ с константами схемы BiCMOS улучшают работу цепей выбора строк. Каждая линия выбора строки очень длинная и подключена к сотням транзисторов, поэтому ёмкостная нагрузка велика. Благодаря быстрому и «мощному» NPN-транзистору драйвер BiCMOS обеспечивает меньшую задержку при высокой нагрузке по сравнению с обычным КМОП-драйвером.

Такую BiCMOS-логику также называют BiNMOS или BinMOS, потому что в выходном каскаде используются биполярный транзистор и NMOS-транзистор. Подробнее о схемах BiCMOS в Pentium — в моей статье «Стандартные ячейки: взгляд на отдельные логические элементы процессора Pentium».

5. Целочисленный вычислительный блок Pentium построен аналогично: горизонтально «сложенные» функциональные узлы образуют тракт данных. Каждая ячейка в целочисленном блоке значительно шире, чем плавающая (64 мкм против 38,5 мкм). Однако целочисленный блок всего 32-разрядный, тогда как блок с плавающей запятой имеет ширину порядка 69 бит, поэтому по общей ширине FPU получается больше. 

6. Мне не нравится говорить о «диапазоне аргумента», поскольку «range» — это обычно область значений функции (выход), а вход — «domain». Но термин «range reduction» («приведение диапазона») — общепринятый, так что оставлю его. 

7. Есть причина, почему кривая ошибки выглядит похожей, даже если сузить диапазон. Погрешность от усечённого ряда Тейлора примерно равна следующему члену ряда; в нашем случае ошибка примерно равна −x^11/11! или O(x¹¹⁾. Отсюда видно, почему приведение диапазона так эффективно: если уменьшить диапазон в 2 раза, ошибка уменьшится на огромный множитель 2¹¹. Но это также объясняет, почему форма кривой ошибки сохраняется: кривая всё ещё ~x¹¹, только шкалы по осям меняются. 

8. Коэффициенты для Pentium, вероятно, получены с помощью алгоритма Ремеза; см. «Проверка вычислений с плавающей запятой». Преимущества полинома Ремеза по сравнению с рядом Тейлора обсуждаются в «Лучшие аппроксимации функций: Тейлор против Ремеза». Описание алгоритма Ремеза дано в книге «Элементарные функции: алгоритмы и реализация», где есть и другая релевантная информация о полиномиальных аппроксимациях и приведении диапазона. Подробнее о полиномиальных аппроксимациях см. «Численное вычисление экспоненты с помощью полиномиальных аппроксимаций» и «Восемь полезных полиномиальных аппроксимаций для sinf(3)».

Полином Ремеза на графике синуса — не тот полином, который использует Pentium; он сгенерирован для иллюстрации с помощью lolremez, полезного инструмента. Конкретный полином таков:

9.9997938808335731e-1 ⋅ x − 1.6662438518867169e-1 ⋅ x³ + 8.3089850302282266e-3 ⋅ x⁵ − 1.9264997445395096e-4 ⋅ x⁷ + 2.1478735041839789e-6 ⋅ x⁹

Ниже показана ошибка для этого полинома. Обратите внимание, что ошибка колеблется между верхней и нижней границами. Это типичный вид полинома Ремеза. Для сравнения: у ряда Тейлора ошибка почти нулевая посередине и резко возрастает на краях. Этот полином Ремеза оптимизирован для диапазона [-π, π]; вне этого диапазона ошибка «взрывается». Ключевой момент в том, что полином Ремеза распределяет ошибку внутри диапазона. Это минимизирует максимальную ошибку (минимакс).

9. Я полагаю, что аргумент arctan приводится к диапазону [-1/64, 1/64]. Это можно сделать с помощью тригонометрической тождественности arctan(x) = arctan((x−c)/(1+xc)) + arctan(c). Идея в том, чтобы выбрать c как значение вида n/32, ближайшее к x. В результате x−c окажется в требуемом диапазоне, и первый arctan можно вычислить полиномом. Другой член, arctan(c), берётся из таблицы значений в ПЗУ. Инструкция FPATAN («частичный арктангенс») принимает два аргумента, x и y, и возвращает atan(y/x); это упрощает работу с плоскими координатами. В этом случае тождество принимает вид arctan(y/x) = arctan((y−tx)/(x+ty)) + arctan c. Операция деления в некоторых случаях может приводить к срабатыванию ошибки FDIV; см. «Вычислительные аспекты истории с Pentium».

10. У Pentium есть несколько тригонометрических инструкций: FSIN, FCOS и FSINCOS возвращают синус, косинус или оба сразу (что почти так же быстро, как вычислить любую из них по отдельности). FPTAN возвращает «частичный тангенс», состоящий из двух чисел, которые нужно разделить, чтобы получить tan. (Это связано с ограничениями исходного сопроцессора 8087.) Pentium возвращает тангенс первым числом и константу 1 — вторым, сохраняя семантику FPTAN, но делая использование удобнее.

Приведение диапазона, вероятно, основано на тождестве sin(a+b) = sin(a)cos(b) + cos(a)sin(b). Чтобы вычислить sin(x), выбирают b как ближайшую константу из таблицы, n/64, затем получают a = x − b. Значение a будет приведено по диапазону, так что sin(a) можно вычислить по полиному. Величины sin(b) и cos(b) доступны из таблицы. Искомое значение sin(x) затем вычисляется умножениями и сложением по указанному тождеству. Косинус можно получить аналогично. Заметим, что cos(a+b) = cos(a)cos(b) − sin(a)sin(b); правые части совпадают с формулой для sin(a+b), только комбинируются иначе. Следовательно, вычислив правые части, можно собрать синус, косинус или сразу оба. Тангенс Pentium получает делением синуса на косинус. Это может вызвать ошибку деления FDIV; см. «Вычислительные аспекты истории с Pentium».

См. также «Тайминги инструкций Агнера Фога»; длительности различных операций дают подсказки о том, как они реализованы. Например, FPTAN выполняется дольше, чем FSINCOS, потому что тангенс получается делением синуса на косинус. 

11. Для экспонент существует инструкция F2XM1, вычисляющая 2^x − 1; вычитание 1 повышает точность. Конкретно, 2^x близко к 1 в типичном случае, когда x близок к 0, поэтому если вычитать 1 отдельно после вычисления 2^x, возникает сильная потеря значащих битов из-за вычитания близких величин. С другой стороны, если вам нужно именно 2^x, явное прибавление 1 не ухудшает точность. Это пример того, как инструкции с плавающей запятой аккуратно спроектированы для сохранения точности. Подробности — в книге «Руководство по 8087» от архитекторов процессора 8086 и сопроцессора 8087. 

12. У Pentium есть инструкции логарифма по основанию 2: FYL2X и FYL2XP1. Инструкция FYL2X вычисляет y · log2(x), а FYL2XP1 — y · log2(x+1). Инструкции включают умножение, потому что при большинстве операций с логарифмами требуется умножение для смены основания; выполнение умножения с внутренней точностью повышает точность результата. Вариант «плюс один» улучшает точность для аргументов, близких к 1, например в расчётах процентов.

Моя гипотеза по приведению диапазона такова: входной аргумент масштабируется в интервал от 1 до 2. (Взять логарифм от показательной части аргумента тривиально, поскольку логарифм по основанию 2 от степени двойки — это просто показатель степени.) Далее аргумент делится на наибольшую константу вида 1 + n/64, меньшую аргумента. Это сведёт аргумент к диапазону [1, 1+1/32]. Полином логарифма можно вычислять на приведённом аргументе. Наконец, добавляется константа из ПЗУ для log2(1 + n/64), чтобы компенсировать деление. Константа разбивается на две части для большей точности.

Мне потребовалось много времени, чтобы понять константы логарифма, потому что они были разделены. Константы «верхней части» казались бессмысленно неточными, так как нижние 27 бит обнулены. Константы «нижней части» выглядели как крошечные полуслучайные числа порядка ±10^-13. В конце концов я понял, что фокус в их сложении.

Читать другие статьи серии:

1. Исследование кремниевых кристаллов процессора Intel 386

2. Невидимая оборона 386: как защищены входы и выходы процессора

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

• 17 ноября: «Архитектурные решения в Backend-разработке». Записаться

• 17 ноября: «Основные шаблоны проектирования в системном дизайне». Записаться

• 24 ноября: «Вход в ядро: системные вызовы и граница между user space и kernel space». Записаться