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

В вычислениях , особенно в цифровой обработке сигналов , операция умножения-накопления ( MAC ) или умножения-сложения ( MAD ) является распространенным шагом, который вычисляет произведение двух чисел и добавляет это произведение в аккумулятор . Аппаратный блок, выполняющий операцию, известен как умножитель-аккумулятор ( модуль MAC ); саму операцию также часто называют операцией MAC или MAD. Операция MAC изменяет аккумулятор a : $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 \times c$ , округляет его до N значащих битов, добавляет результат к a и округляет обратно до N значимых битов, объединенное умножение-сложение вычисляет все выражение $a + (b \times c)$ до полной точности перед округлением окончательного результата до N значащих битов.

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

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

Обычно можно полагаться на объединенное умножение-сложение для получения более точных результатов. Однако Уильям Кахан отметил, что это может создать проблемы, если использовать его необдуманно. ^[8] Если $х 2 - и 2$ оценивается как $((x \times x) - y \times y)$ (в соответствии с предложенными Каханом обозначениями, в которых избыточные круглые скобки заставляют компилятор сначала округлять $термин (x \times 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 .

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

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

Операция объединенного умножения-сложения была представлена как «слитое умножение-сложение» в процессоре 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 г.) Набор инструкций

См. также

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

Ссылки

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

[1] «Возможность создания аналитической машины Ладгейта» . Архивировано из оригинала 7 августа 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] "безумный - пс" . 20 ноября 2019 г. Проверено 14 августа 2021 г.

[6] Уайтхед, Натан; Фит-Флоря, Алекс (2011). «Точность и производительность: числа с плавающей запятой и соответствие стандарту IEEE 754 для графических процессоров NVIDIA» (PDF) . нвидиа . Проверено 31 августа 2013 г.

[7] "fmadd инструкции" . ИБМ .

[8] Кахан, Уильям (31 мая 1996 г.). «Стандарт IEEE 754 для двоичной арифметики с плавающей запятой» .

[9] Куиннелл, Эрик (май 2007 г.). Архитектуры смешанного умножения-сложения с плавающей запятой (PDF) (кандидатская диссертация) . Проверено 28 марта 2011 г.

[goldschmidt_algo-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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]