Умножение с накоплением¶

Умножение с накоплением (англ. multiply–accumulate, MAC) — это арифметическая операция, выполняющая перемножение двух чисел и сложение полученного произведения с текущим значением аккумулятора (накопительного регистра). В общем виде операция описывается формулой: \( a \leftarrow a + (b \times c) \), где \( a \) — накапливаемое значение, \( b \) и \( c \) — множители. Умножение с накоплением является базовой операцией в цифровой обработке сигналов, машинном обучении, численных методах и криптографии, а также аппаратно реализуется в специализированных вычислительных блоках (MAC-блоках) процессоров и цифровых сигнальных процессоров (DSP).

¶История

Концепция умножения с накоплением возникла с развитием цифровых вычислительных машин в середине XX века. В ранних компьютерах, таких как ENIAC (1945), умножение и сложение выполнялись как отдельные команды, что требовало нескольких тактов для последовательного выполнения операций. С появлением арифметико-логических устройств (АЛУ) и регистров-аккумуляторов в 1950-х годах (например, в компьютере IBM 704) операция MAC стала выполняться за один цикл, что значительно ускорило обработку данных.

В 1970-х годах с развитием цифровой обработки сигналов (ЦОС) и появлением первых DSP-микросхем (например, Texas Instruments TMS32010, 1983) умножение с накоплением было реализовано аппаратно в виде специализированного блока, выполняющего команду MAC за один такт. Это позволило эффективно реализовывать алгоритмы фильтрации, преобразования Фурье и корреляции. В 1990-х годах MAC-блоки стали стандартными компонентами в микропроцессорах общего назначения (например, в архитектуре x86 с расширениями MMX и SSE), а также в графических процессорах (GPU) и нейронных процессорах (NPU) для ускорения операций машинного обучения.

¶Математическое описание

Умножение с накоплением является частным случаем операции свёртки. Для последовательности входных данных \( x[n] \) и коэффициентов \( h[n] \) результат свёртки \( y[n] \) вычисляется как:

\[ y[n] = \sum_{k=0}^{N-1} h[k] \cdot x[n-k] \]

Каждый шаг вычисления \( y[n] \) включает умножение \( h[k] \times x[n-k] \) и накопление результата в аккумуляторе. В цифровой обработке сигналов эта операция повторяется для каждого отсчёта, что делает MAC-блоки критически важными для производительности.

В машинном обучении операция MAC используется в нейронных сетях при вычислении взвешенной суммы входов нейрона:

\[ z = \sum_{i=1}^{n} w_i \cdot x_i + b \]

где \( w_i \) — веса, \( x_i \) — входные значения, \( b \) — смещение. Каждое умножение \( w_i \times x_i \) и последующее сложение с аккумулятором является MAC-операцией.

¶Аппаратная реализация

¶Архитектура MAC-блока

Типичный MAC-блок состоит из следующих компонентов:

• Умножитель — цифровое устройство, выполняющее умножение двух чисел (обычно с фиксированной или плавающей запятой). В современных процессорах используются умножители на основе архитектуры Уоллеса (Wallace tree) или Дэдда (Dadda tree), обеспечивающие высокую скорость.
• Аккумулятор — регистр, хранящий текущую сумму. Разрядность аккумулятора обычно превышает разрядность входных данных, чтобы избежать переполнения при накоплении большого числа произведений.
• Сумматор — арифметическое устройство, выполняющее сложение произведения с содержимым аккумулятора.
• Управляющая логика — обеспечивает синхронизацию и загрузку данных.

¶Типы реализации

1. Аппаратные MAC-блоки в DSP: Специализированные процессоры, такие как серии TMS320 (Texas Instruments) или ADSP (Analog Devices), содержат один или несколько MAC-блоков, выполняющих команду MAC за один такт. Например, TMS320C64x выполняет до 8 MAC-операций за такт.

1. Векторные расширения процессоров: В архитектурах x86 (SSE, AVX), ARM (NEON) и RISC-V (V-расширение) реализованы векторные инструкции, выполняющие несколько MAC-операций параллельно. Например, инструкция VFMADD (fused multiply-add) в AVX-512 выполняет умножение и сложение для 16 пар чисел с плавающей запятой за один такт.

1. GPU и тензорные блоки: Графические процессоры (NVIDIA CUDA, AMD ROCm) и специализированные тензорные блоки (NVIDIA Tensor Core, Google TPU) выполняют матричные умножения, сводящиеся к множеству MAC-операций. Например, Tensor Core в NVIDIA Volta выполняет 64 MAC-операции за такт для матриц 4×4.

1. FPGA и ASIC: В программируемых логических интегральных схемах (FPGA) и заказных микросхемах (ASIC) MAC-блоки реализуются в виде встроенных блоков DSP (например, Xilinx DSP48E) или пользовательской логики. Это позволяет достичь высокой производительности при низком энергопотреблении.

¶Проблемы точности

При выполнении большого числа MAC-операций с плавающей запятой может накапливаться ошибка округления. Для уменьшения ошибок используются методы:

• Слияние умножения и сложения (FMA): Выполнение операции \( a \leftarrow a + (b \times c) \) с одним округлением, что повышает точность по сравнению с последовательным умножением и сложением.
• Использование аккумулятора повышенной разрядности: Например, в процессорах Intel AVX-512 аккумулятор имеет разрядность 80 бит для чисел с плавающей запятой двойной точности.
• Алгоритмы компенсации ошибок: Метод Кахана (Kahan summation) и другие алгоритмы, корректирующие накопление ошибок.

¶Применение

¶Цифровая обработка сигналов

Умножение с накоплением является основой для реализации:

• КИХ-фильтров (конечная импульсная характеристика): каждый выходной отсчёт вычисляется как сумма произведений входных отсчётов и коэффициентов фильтра.
• БИХ-фильтров (бесконечная импульсная характеристика): используются рекурсивные MAC-операции.
• Быстрого преобразования Фурье (БПФ): алгоритм Кули-Тьюки сводится к серии MAC-операций для вычисления поворотных коэффициентов.
• Корреляции и свёртки: в радиолокации, сонарах и обработке изображений.

¶Машинное обучение и нейронные сети

В обучении и инференсе нейронных сетей MAC-операции составляют до 90% всех вычислений. Конкретные применения:

• Полносвязные слои: вычисление \( y = Wx + b \), где \( W \) — матрица весов.
• Свёрточные слои: выполнение свёртки входного тензора с ядром фильтра.
• Рекуррентные нейронные сети: вычисление скрытых состояний с использованием MAC-операций.

Для ускорения используются тензорные блоки (NVIDIA Tensor Core, Google TPU) и специализированные нейронные процессоры (NPU), такие как Huawei Ascend или Intel Movidius.

¶Криптография

В криптографических алгоритмах с открытым ключом (RSA, ECC) умножение с накоплением используется в модульной арифметике. Например, в алгоритме Монтгомери (Montgomery multiplication) для быстрого возведения в степень по модулю выполняется серия MAC-операций с модульным сокращением.

¶Научные вычисления

В численных методах (решение систем линейных уравнений, метод конечных элементов, моделирование физических процессов) MAC-операции применяются при умножении матриц, вычислении скалярных произведений и интегралов.

¶Производительность

Производительность MAC-операций измеряется в количестве операций в секунду (MAC/s). Для современных процессоров:

• CPU: до 100–500 ГMAC/s (Intel Xeon Platinum, AMD EPYC) при использовании векторных инструкций.
• GPU: до 10–100 ТMAC/s (NVIDIA A100 — 312 ТMAC/s для разрежённых матриц).
• NPU: до 1–10 ПMAC/s (Google TPU v4 — 275 ПMAC/s при 16-битной точности).
• FPGA: до 1–10 ТMAC/s (Xilinx Virtex UltraScale+).

¶Ограничения и критика

Несмотря на высокую эффективность, использование умножения с накоплением имеет ряд ограничений:

• Энергопотребление: MAC-блоки потребляют значительную часть энергии процессора (до 30–50% в DSP и GPU). Для мобильных устройств и дата-центров это критично.
• Тепловыделение: Высокая плотность MAC-операций требует эффективного охлаждения.
• Точность: При работе с плавающей запятой накопление ошибок может приводить к неверным результатам, особенно в длинных итеративных алгоритмах (например, в обучении нейронных сетей).
• Сложность программирования: Для эффективного использования MAC-блоков требуется оптимизация кода (векторизация, распараллеливание), что не всегда доступно прикладным программистам.

¶Интересные факты

• Первый коммерческий DSP-микропроцессор TMS32010 (1983) содержал один MAC-блок, выполнявший 5 миллионов операций в секунду.
• В 2020-х годах компания NVIDIA представила тензорные блоки с поддержкой разрежённых матриц, что позволяет выполнять MAC-операции только для ненулевых элементов, ускоряя обучение нейронных сетей в 2–4 раза.
• В архитектуре x86 инструкция FMA (fused multiply-add) была введена в 2011 году с набором AVX2, что позволило выполнять одну MAC-операцию за такт без потери точности.

¶Источники

• Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach. 6th ed. Morgan Kaufmann.
• Proakis, J. G., & Manolakis, D. G. (2007). Digital Signal Processing: Principles, Algorithms, and Applications. 4th ed. Pearson.
• Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press.
• Intel Corporation. (2021). Intel® 64 and IA-32 Architectures Software Developer’s Manual.
• NVIDIA Corporation. (2020). NVIDIA A100 Tensor Core GPU Architecture.