Быстрый способ умножения двух одномерных массивов

У меня есть следующие данные:

A = [a0 a1 a2 a3 a4 a5 .... a24]
B = [b0 b1 b2 b3 b4 b5 .... b24]

который я затем хочу умножить следующим образом:

C = A * B' = [a0b0 a1b1 a2b2 ... a24b24]

Это явно включает 25 умножений.

Однако в моем сценарии только 5 новых значений сдвигаются в A за «итерацию цикла» (и 5 старых значений сдвигаются из A). Есть ли какой-нибудь быстрый способ использовать тот факт, что данные перемещаются через A, а не являются совершенно новыми? В идеале я хочу свести к минимуму количество операций умножения (за счет, возможно, большего количества сложений/вычитаний/накоплений). Сначала я думал, что систолический массив может помочь, но это не так (я думаю!?)

Обновление 1: Примечание B фиксируется на длительное время, но его можно перепрограммировать.

Обновление 2: смещение A выглядит следующим образом: a[24] ‹= a[19], a[23] ‹= a[18]... a[1] ‹= new01, a[0] ‹= новый00. И так далее каждый такт

Большое спасибо!


fpga verilog hardware vhdl asic
person trican    schedule 11.04.2013    source источник
comment
Остается ли B неизменным на протяжении всего процесса перехода?   -  person Sergey Kalinichenko    schedule 11.04.2013
comment
Как насчет создания 5 множителей для параллельной работы или 1 множителя с тактовой частотой 5x?   -  person Alexey Frunze    schedule 11.04.2013
comment
Каково Б? например если бы это был алгоритм DSP с фиксированной длиной фильтра, B мог бы состоять из небольших коэффициентов со средним значением менее 2 установленных битов.   -  person Aki Suihkonen    schedule 11.04.2013
comment
Что с тегами? Это C-код, или vhdl, или сборка, или что-то совсем другое? Что ты пытаешься сделать? Спроектировать ЦП или написать программу для выполнения на нем?   -  person jalf    schedule 11.04.2013
comment
@jalf :-) это специальное оборудование, я просто пытаюсь увеличить количество глазных яблок, которые видят этот вопрос - не так много подписчиков на теги vhdl или verilog   -  person trican    schedule 11.04.2013
comment
@dasblinkenlight B остается прежним ... большую часть времени, но его можно перепрограммировать.   -  person trican    schedule 11.04.2013
comment
@AkiSuihkonen Значения B в настоящее время составляют около 16 бит - возможно, их можно оптимизировать.   -  person trican    schedule 11.04.2013
comment
В этом случае я бы рассмотрел распределенную арифметику с деревом CSA.   -  person Aki Suihkonen    schedule 11.04.2013
comment
@AlexeyFrunze Мне нужны здесь только одни часы. 5 множителей параллельно? Я не уверен, как это будет работать? Мне нужно 25 результатов за такт, и 5 новых значений смещаются за такт.   -  person trican    schedule 11.04.2013
comment
под смещением вы имеете в виду, что элемент по этому индексу заменяется новым? например a[0] с новым элементом или a[0] с a[1] и a[1] с a[2] и так далее? Вы играете с DMA для прямого хранения?   -  person Koushik Shetty    schedule 11.04.2013
comment
@Koushik новые значения a[25] ‹= a[20], a[24] ‹= a[19]... a[1] ‹= new01, a[0] ‹= new00. Я надеюсь, что это проясняет ситуацию   -  person trican    schedule 11.04.2013
comment
в соответствии с вашим кодом должно быть 26 ритуалов умножения?   -  person Koushik Shetty    schedule 11.04.2013
comment
Извините, ошибка описания нулевого индекса! Его 25 умножений, записи от 0 до 24 - я обновлю вопрос   -  person trican    schedule 11.04.2013
comment
@trican: пытаетесь увеличить количество глазных яблок... вставляя вводящие в заблуждение теги? Вот, проголосуй. В следующий раз попробуйте использовать соответствующие теги.   -  person jalf    schedule 11.04.2013
comment
@jalf - я категорически не согласен, я считаю, что это подходящие теги - это алгоритмический вопрос относительно эффективной реализации (хотя и на аппаратном уровне) - если есть возможная оптимизация, люди, разбирающиеся в low c или ассемблере, скорее всего, смогут внести полезный вклад предложения (см. ответ andand ниже) как люди, ориентированные на аппаратное обеспечение. В качестве альтернативы, какие теги вы могли бы предложить?   -  person trican    schedule 11.04.2013

Ответы (3)


arrow_upward
2
arrow_downward

Есть ли какой-нибудь быстрый способ использовать тот факт, что данные перемещаются через A, а не являются совершенно новыми?

Хотя все, что вы делаете, — это смещение и добавление новых элементов к A, продукты в C, как правило, все будут другими, поскольку один из операндов обычно будет меняться после каждой итерации. Если у вас есть дополнительная информация о том, как структурированы элементы A или B, вы потенциально можете использовать эту структуру, чтобы уменьшить количество умножений. За исключением любых подобных структурных соображений, вам придется вычислять все 25 продуктов в каждом цикле.

В идеале я хочу свести к минимуму количество операций умножения (за счет, возможно, большего количества сложений/вычитаний/накоплений).

Теоретически вы можете уменьшить количество умножений до 0, сдвигая и добавляя элементы массива для имитации умножения. На практике это будет медленнее, чем аппаратное умножение, поэтому вам лучше просто использовать любое доступное аппаратное умножение, если нет какого-либо дополнительного, соответствующего ограничения, о котором вы не упомянули.

person andand    schedule 11.04.2013

arrow_upward
1
arrow_downward

в самых первых 5 наборах данных вы можете сохранить до 50 умножений. но после этого его плоская дорога умножения. так как для каждого набора после первых 5 наборов вам нужно умножить на новый набор данных.

я предполагаю, что все массивы инициализированы нулем. Я не думаю, что эти 50 сохраненных имеют какую-либо пользу, учитывая количество умножения в целом.

Но все же я дам вам подсказку, как сохранить эти 50, может быть, вы могли бы найти расширение для него?

Прибыл 1-й набор данных: умножьте первый набор данных в a на каждый набор данных в b. сохранить все в a, скопировать только a[0] в a[4] в c. Здесь 25 умножений.

Прибыл 2-й набор данных: умножьте только a[0] на a[4] (имея новые данные) с b[0] на b[4] соответственно. сохранить в a[0] в a[4], скопировать в a[0->9] в c. 5 умножений здесь

Пришел 3-й набор данных: умножьте a[0] на a[9] на b[0] на b[9] на этот раз и скопируйте в соответствующие a[0->14] на c.Здесь 10 умножений

4-й набор данных: умножьте a[0] на a[14] с соответствующим b скопируйте соответствующие a[0->19] на c. Здесь 15 умножений.

5-й набор данных: умножьте a[0] на a[19] с соответствующей копией b, соответствующей a[0->24] на c. Здесь 20 умножений.

общее количество сохраненных умножений: 50 умножений.

6-й набор данных: обычные умножения данных. 25 каждый. это связано с тем, что для каждого набора в массиве a доступен новый набор данных, поэтому умножение неизбежно.

person Koushik Shetty    schedule 11.04.2013

arrow_upward
0
arrow_downward

Можете ли вы добавить еще один массив D, чтобы пометить измененное/неизмененное значение в A. Каждый раз, когда вы проверяете этот массив, чтобы решить, делать ли новые умножения или нет.

person Tianyun Ling    schedule 11.04.2013