32-битное умножение на 24-битном ALU

Question

32-битное умножение на 24-битном ALU

Я хочу портировать 32 на 32-битное беззнаковое умножение на 24-битный dsp (это линейный конгруэнтный генератор, поэтому мне не разрешено усекать, также я не хочу пока заменять текущий LCG на 24-битный). Доступные типы данных: 24 и 48 бит.

Требуются только последние 32 LSB. Знаете ли вы какие-нибудь хаки, чтобы реализовать это в меньшем количестве умножений, масок и смен, чем обычным способом?

Линия выглядит так:

//val is an int(32 bit)
val = (1664525 * val) + 1013904223;

1

signal-processing multiplication 32-bit 24bit

Источник

user3115923 07 авг '14 в 19:14

2 ответа

Схема будет (в моем текущем стиле компилятора):
static uint48_t val = SEED; ... val = 0xFFFFFFFFUL & ((1664525UL * val) + 1013904223UL);
и, надеюсь, компилятор распознает:
он может использовать команду умножения и накопления
ему нужен только сокращенный алгоритм умножения из-за того, что "старшее слово" константы равно нулю
AND может быть осуществлено путем сброса старших битов или умножения константы и восстановления
... другие вещи зависят от вашей цели {mystery dsp}
Обратите внимание, что если вы увеличите коэффициенты на 2^16, вы можете получить усечение бесплатно, но из-за недостатка информации вам придется изучить / решить, будет ли оно лучше в целом.

0

Источник Поделиться

user2125225 09 авг '14 в 07:11 2014-08-09 07:11

2014-08-09 07:11

Другие вопросы по тегам signal-processing multiplication 32-bit 24bit

user3789665 01 янв '18 в 16:40 2018-01-01 16:40 · Answer 1 · 2018-01-01 16:40

(Это более сложная причина, почему два умножения 24×24 →n, 31 Вопрос раскрывает удивительно мало о возможностях создания метода
32×21→32 in fewer [24×24] multiplies, masks and shifts than the usual way на:
24 and 48 bit ints & DSP (Я читаю высокую пропускную способность, не высокая задержка 24×24→48).
Поскольку действительно существует умножение 24×24→48 (или даже 24 × 24 + 56 → 56 MAC) и один фактор меньше 24 бит, вопрос не имеет смысла, а второе умножение является убедительным решением.

Обычный состав 24 умноженный на 24×24→48, использует три из последних; компилятор должен знать так же хорошо, как и кодер, что "четвертое умножение" даст биты со значением / положением, превышающим суммарную длину нижних частей факторов.
Итак, возможно ли создать "длинный продукт", используя всего лишь секунду 24×24→48?
Пусть (в байтах) множителей будут w_xyz и W_XYZ соответственно; подчеркивания, указывающие на то, что " W s" являются битами с более низким значением в словах / целочисленных значениях более высокого значения, если их интерпретировать как 24-битные. Первые 24×24→48 дают сумму
Zx
у XzY
xX yYzZ
x YyZ
XZ, что нужно (жир)
W Z +
Z W.
Это может быть вычислено с использованием одного комбинированного умножения
((w << 16) | (z & 0xff)) × ((W << 16) | (Z & 0xff)). (Не берите в голову 17-й бит wZ+zW, "бегущего" в wW.)
(В первой редакции этого ответа я по глупости произвел wZ и zW по отдельности - в любом случае, в конце концов, требуется их сумма.)
(Удивительно, но это почти все, что вы можете сделать для 24×24→24 в качестве базовой операции - помимо этого "умножения с комбинированием", вам нужно четыре вместо одного.)

Еще один аспект для изучения - выбор другого PRNG. Это может быть> 24 бит (скажи!).
На 24-битной машине, XorShift * (или даже XorShift+) 48/32, кажется, стоит посмотреть.

user2125225 09 авг '14 в 07:11 2014-08-09 07:11 · Answer 2 · 2014-08-09 07:11

Схема будет (в моем текущем стиле компилятора):

static uint48_t val = SEED;
...
val = 0xFFFFFFFFUL & ((1664525UL * val) + 1013904223UL);

и, надеюсь, компилятор распознает:

он может использовать команду умножения и накопления
ему нужен только сокращенный алгоритм умножения из-за того, что "старшее слово" константы равно нулю
AND может быть осуществлено путем сброса старших битов или умножения константы и восстановления
... другие вещи зависят от вашей цели {mystery dsp}

Обратите внимание, что если вы увеличите коэффициенты на 2^16, вы можете получить усечение бесплатно, но из-за недостатка информации вам придется изучить / решить, будет ли оно лучше в целом.