Как современные процессоры X86 на самом деле вычисляют умножения?
Я смотрел лекцию об алгоритмах, и профессор использовал умножение как пример того, как можно улучшить наивные алгоритмы...
Это заставило меня понять, что умножение не так очевидно, хотя, когда я кодирую, я просто считаю, что это простая атомарная операция, умножение требует запуска алгоритма, он не работает как суммирование чисел.
Поэтому мне интересно, какой алгоритм на самом деле используют современные настольные процессоры? Я предполагаю, что они не полагаются на логарифмические таблицы и не делают циклы с тысячами сумм...
1 ответ
Митч Алсуп (который работал над Motorola 88K, Ross SPARC, AMD x86 и т. Д.) Заявил в группе новостей comp.arch:
Все современные разработчики умножителей используют метод Дадды для построения дерева.
(Идентификатор сообщения:
и (относительно наличия последних ссылок на то, какие механизмы умножения используются AMD/Intel/NVIDIA):
Только в патентном бюро.
(Идентификатор сообщения:
См. Википедию для получения информации о множителях дерева Дадды.
Существует множество процедур умножения, которые можно использовать в ЦП. Например, множитель Бута для двоичных чисел с дополнением до 2, преподаваемый в большинстве курсов по архитектуре и организации компьютеров. Умножение в двоичном формате проще, чем умножение в десятичном представлении. Рассчитать частичные продукты просто. Множаемое M(если бит умножителя равен 1) или 0(если бит умножителя равен 0). Сравните это с десятичным числом, где это может быть любое значение от (0*M до 9*M). Всякий раз, когда кто-то проектирует собственный ЦП (например, программное ядро на ПЛИС), разработчик может выбрать соответствующие процедуры умножения. Наиболее часто используются множители CORDIC, Radix-2,Radix-4,Radix-8... множители будки. Весь этот алгоритм умножения генерирует частичный продукт (как ручное умножение). Все частичные продукты добавляются в конечный продукт.Есть несколько способов сделать это в современных процессорах, например, используя множитель Дадда, дерево Уоллеса.
Проще говоря, каждый разработчик процессора может использовать любой алгоритм умножения для создания частичных продуктов и добавлять частичные продукты для получения окончательных результатов. В зависимости от двоичного представления, используемого внутри регистров процессора, размера регистра в битах, наиболее оптимальный алгоритм будет варьироваться.
Современные процессоры имеют встроенные математические сопроцессоры. Я считаю, что они содержат LUT (таблицы поиска) для умножения.