Операция умножения-накопления

Операция, распространенная в числовой обработке сигналов

В вычислениях , особенно в цифровой обработке сигналов , операция умножения-накопления ( MAC ) или умножения-сложения ( MAD ) является распространенным шагом, который вычисляет произведение двух чисел и добавляет это произведение в аккумулятор . Аппаратный блок, выполняющий операцию, известен как умножитель-аккумулятор ( модуль MAC ); саму операцию также часто называют операцией MAC или MAD. Операция MAC изменяет аккумулятор a :

$${\displaystyle a\gets a+(b\times c)}$$

При работе с числами с плавающей запятой это может выполняться с двумя округлениями (типично для многих DSP ) или с одним округлением. Когда оно выполняется с одним округлением, оно называется объединенным умножением-сложением ( FMA ) или объединенным умножением-накоплением ( FMAC ).

Современные компьютеры могут содержать специальный MAC, состоящий из умножителя, реализованного в комбинационной логике , за которым следуют сумматор и регистр-накопитель, в котором сохраняется результат. Выходной сигнал регистра подается обратно на один вход сумматора, так что в каждом такте выходной сигнал умножителя добавляется в регистр. Комбинационные умножители требуют большого объема логики, но могут вычислять произведение гораздо быстрее, чем метод сдвига и сложения, типичный для более ранних компьютеров. Перси Ладгейт был первым, кто придумал MAC в своей «Аналитической машине» 1909 года ^[1] и первым, кто использовал MAC для деления (используя умножение, полученное обратным числом, через сходящийся ряд (1+ x ) ^-1 ). Первыми современными процессорами, оснащенными блоками MAC, были процессоры цифровых сигналов , но сейчас эта технология также распространена в процессорах общего назначения. ^{[2] [3] [4] [5]}

В арифметике с плавающей запятой

При работе с целыми числами операция обычно является точной (вычисляется по модулю некоторой степени двойки ). Однако числа с плавающей запятой обладают лишь определенной математической точностью . То есть цифровая арифметика с плавающей запятой обычно не является ассоциативной или дистрибутивной . (См. § Арифметика с плавающей запятой § Проблемы с точностью .) Таким образом, на результат имеет значение, выполняется ли умножение-сложение с двумя округлениями или за одну операцию с одним округлением (слитное умножение-сложение). IEEE 754-2008 указывает, что оно должно выполняться с одним округлением, что дает более точный результат. ^[6]

Слитое умножение-сложение

Слитое умножение -сложение ( FMA или fmadd ) ^[7] — это операция умножения-сложения с плавающей запятой, выполняемая за один шаг ( слитая операция ) с одним округлением. То есть, если неслитное умножение-сложение вычисляет произведение b × c , округляет его до N значащих битов, добавляет результат к a и округляет обратно до N значащих битов, объединенное умножение-сложение вычисляет все выражение a + ( b × c ) до полной точности перед округлением окончательного результата до N значащих битов.

Быстрый FMA может ускорить и повысить точность многих вычислений, связанных с накоплением продуктов:

• Скалярное произведение
• Умножение матрицы
• Полиномиальная оценка (например, по правилу Горнера )
• Метод Ньютона вычисления функций (по обратной функции)
• Свертки и искусственные нейронные сети
• Умножение в арифметике дабл-дабл

Обычно можно полагаться на объединенное умножение-сложение для получения более точных результатов. Однако Уильям Кахан отметил, что это может создать проблемы, если использовать его необдуманно. ^[8] Если x ² − y ² вычисляется как (( x × x ) − y × y ) (следуя предложенной Каханом записи, в которой избыточные круглые скобки предписывают компилятору сначала округлить член ( x × x ) ), используя слитое умножение – сложите, то результат может быть отрицательным, даже если x = y из-за того, что первое умножение отбрасывает биты низкой значимости. Это может привести к ошибке, если, например, затем будет вычислен квадратный корень результата.

При реализации внутри микропроцессора FMA может выполняться быстрее, чем операция умножения, за которой следует сложение. Однако стандартные промышленные реализации, основанные на исходной конструкции IBM RS/6000, требуют 2 N -битного сумматора для правильного вычисления суммы. ^[9]

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

Инструкция скалярного произведения

Некоторые машины объединяют несколько операций слитого умножения и сложения в один шаг, например, выполняют скалярное произведение четырех элементов на двух 128-битных SIMD- регистрах a0×b0 + a1×b1 + a2×b2 + a3×b3с пропускной способностью за один цикл.

Поддерживать

Операция FMA включена в IEEE 754-2008 .

Инструкция VAX компании Digital Equipment Corporation (DEC) используется для оценки полиномов по правилу Хорнера с использованием последовательности шагов умножения и сложения. В описаниях инструкций не указано, выполняются ли умножение и сложение за один шаг FMA. ^[11] Эта инструкция была частью набора инструкций VAX с момента ее первоначальной реализации 11/780 в 1977 году.POLY

Стандарт языка программирования C 1999 года поддерживает операцию FMA через функцию стандартной математической библиотеки и автоматическое преобразование умножения с последующим сложением (сокращением выражений с плавающей запятой), которое можно явно включить или отключить с помощью стандартных прагм ( ). . Компиляторы GCC и Clang C по умолчанию выполняют такие преобразования для процессорных архитектур, поддерживающих инструкции FMA. В GCC, который не поддерживает вышеупомянутую прагму, ^[12] этим можно глобально управлять с помощью параметра командной строки. ^[13]fma()#pragma STDC FP_CONTRACT-ffp-contract

Операция объединенного умножения-сложения была представлена ​​как «слитое умножение-сложение» в процессоре IBM POWER1 (1990), ^[14] , но с тех пор была добавлена ​​​​во многие другие процессоры:

• HP PA-8000 (1996 г.) и выше
• Хитачи СуперХ SH-4 (1998)
• SCE - Toshiba Emotion Engine (1999)
• Интел Итаниум (2001 г.)
• Ячейка ИППП (2006)
• Fujitsu SPARC64 VI (2007 г.) и новее
• ( MIPS -совместимый) Loongson -2F (2008) ^[15]
• Эльбрус-8СВ (2018)
• Процессоры x86 с набором инструкций FMA3 и/или FMA4
  • AMD Bulldozer (2011 г., только FMA4)
  • AMD Piledriver (2012, FMA3 и FMA4) ^[16]
  • Паровой каток AMD (2014)
  • AMD Экскаватор (2015)
  • AMD Zen (2017 г., только FMA3)
  • Intel Haswell (2013 г., только FMA3) ^[17]
  • Intel Skylake (2015 г., только FMA3)
• Процессоры ARM с VFPv4 и/или NEONv2:
  • АРМ Кортекс-М4Ф (2010 г.)
  • STM32 Cortex-M33 (работа VFMA) ^[18]
  • АРМ Кортекс-А5 (2012 г.)
  • АРМ Кортекс-А7 (2013 г.)
  • АРМ Кортекс-А15 (2012 г.)
  • Квалкомм Крайт (2012 г.)
  • Яблоко А6 (2012 г.)
  • Все процессоры ARMv8
    • Fujitsu A64FX имеет «FMA с четырьмя операндами и префиксной инструкцией».
• IBM z/Architecture (с 1998 г.)
• Графические процессоры и платы GPGPU:
  • Графические процессоры AMD (2009 г.) и новее
    • TeraScale 2 «Evergreen» на базе серии
    • Графическое ядро ​​Next на базе
  • Графические процессоры Nvidia (2010 г.) и новее
    • на основе Ферми (2010)
    • на основе Кеплера (2012)
    • Максвелл - на основе (2014)
    • на основе Паскаля (2016)
    • На базе Вольты (2017)
  • Графические процессоры Intel со времен Sandy Bridge
  • Интел МИК (2012 г.)
  • Серия ARM Mali T600 (2012 г.) и новее
• Векторные процессоры:
  • NEC SX-Аврора ЦУБАСА
• Набор инструкций RISC-V (2010 г.)

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

• Составной оператор

Рекомендации

1. «Возможность создания аналитической машины Ладгейта». Архивировано из оригинала 07 августа 2019 г. Проверено 30 августа 2020 г.
2. Ляхов, Павел; Валуева, Мария; Валуев Георгий; Нагорнов, Николай (январь 2020 г.). «Метод повышения производительности цифрового фильтра на основе усеченных многократно-накопительных единиц». Прикладные науки . 10 (24): 9052. дои : 10.3390/app10249052 .
3. Тунг Тхань Хоанг; Сьяландер, М.; Ларссон-Эдефорс, П. (май 2009 г.). «Умножение-накопление двойной пропускной способности для усовершенствований процессора FlexCore». 2009 Международный симпозиум IEEE по параллельной и распределенной обработке . стр. 1–7. дои : 10.1109/IPDPS.2009.5161212. ISBN 978-1-4244-3751-1. S2CID  14535090.
4. Кан, Чонсон; Ким, Тэван (01 марта 2020 г.). «PV-MAC: единичная структура умножения и накопления, использующая изменчивость точности в сверточных нейронных сетях на устройстве». Интеграция . 71 : 76–85. дои :10.1016/j.vlsi.2019.11.003. ISSN  0167-9260. S2CID  211264132.
5. "безумный - PS" . Проверено 14 августа 2021 г.
6. Уайтхед, Натан; Фит-Флоря, Алекс (2011). «Точность и производительность: числа с плавающей запятой и соответствие стандарту IEEE 754 для графических процессоров NVIDIA» (PDF) . нвидиа . Проверено 31 августа 2013 г.
7. "fmadd instrs" . ИБМ .
8. Кахан, Уильям (31 мая 1996 г.). «Стандарт IEEE 754 для двоичной арифметики с плавающей запятой».
9. Куиннелл, Эрик (май 2007 г.). Архитектуры смешанного умножения-сложения с плавающей запятой (PDF) (кандидатская диссертация) . Проверено 28 марта 2011 г.
10. Маркштейн, Питер (ноябрь 2004 г.). Деление программного обеспечения и квадратный корень с использованием алгоритмов Гольдшмидта (PDF) . 6-я конференция «Действительные числа и компьютеры». CiteSeerX 10.1.1.85.9648 . 
11. "Инструкция недели VAX: POLY" . Архивировано из оригинала 13 февраля 2020 г.
12. «Ошибка 20785 — Pragma STDC * (C99 FP) не реализована» . gcc.gnu.org . Проверено 2 февраля 2022 г.
13. «Параметры оптимизации (с использованием коллекции компиляторов GNU (GCC))» . gcc.gnu.org . Проверено 2 февраля 2022 г.
14. Монтой, РК; Хокенек, Э.; Руньон, СЛ (январь 1990 г.). «Проектирование исполнительного блока IBM RISC System/6000 с плавающей запятой». Журнал исследований и разработок IBM . 34 (1): 59–70. дои : 10.1147/rd.341.0059.
15. «Godson-3 эмулирует x86: новый китайский процессор, совместимый с MIPS, имеет расширения для перевода x86» .
16. Холлингсворт, Брент (октябрь 2012 г.). «Новые инструкции для «Бульдозера» и «Сваебойщика». Центр разработчиков AMD.
17. «Intel добавляет 22-нм восьмиядерный процессор Haswell в план разработки процессоров» . Регистр . Архивировано из оригинала 17 февраля 2012 г. Проверено 19 августа 2008 г.
18. «Руководство по программированию микроконтроллеров STM32 Cortex-M33» (PDF) . СТ . Проверено 6 мая 2024 г.