两个一维数组相乘的快速方法

cet 发布于 2019-03-09 asic 最后更新 2019-03-09 14:31 9 浏览

我有以下数据:

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 ] <= new00。每个时钟周期都是如此 非常感谢!
已邀请:

podio

赞同来自:

Is there any fast way to exploit the fact that data is shifting through A rather than being completely new?
即使你所做的只是转移并向A添加新元素,C中的产品通常都会有所不同,因为其中一个操作数通常会在每次迭代后发生变化。如果您有关于A或B元素结构的方式的其他信息,您可以使用该结构来减少乘法的数量。除非考虑到任何此类结构因素,否则您必须计算每个循环的所有25个产品。
Ideally I want to minimize the number of multiplication operations (at a cost of perhaps more additions/subtractions/accumulations).
理论上,通过移位和添加数组元素来模拟乘法,可以将乘法次数减少到0。实际上,这将比硬件乘法慢,所以你最好只使用任何可用的基于硬件的乘法,除非你没有提到一些额外的相关约束。

icum

赞同来自:

你可以添加另一个数组D来标记A中已更改/未更改的值。每次检查此数组以决定是否进行新的乘法运算。

phic

赞同来自:

在最初的5个数据集中,您可以节省多达50次乘法。但在那之后它是一条平坦的乘法之路。因为对于前5个集合之后的每个集合,您需要乘以新的数据集。 我假设所有数组都初始化为零。 考虑到整体上的乘法量,我不认为那些保存的50个是有用的。 但是我仍然会给你一个关于如何保存那些50的提示,也许你可以找到它的延伸? 第一个数据集到达:将a中的第一个数据集与b中设置的每个数据相乘。全部保存在a中,仅将a[0]复制到a[4]c。这里有25次乘法。 第二个数据集到达:仅将a[0]a[4](具有新数据)与b[0]相乘,再加上b[4]。保存在a[0]a[4],复制到a[0->9]c。这里有5次乘法 第3个数据集到达:此次将a[0]b[0]相乘b[9]到PLACEHOLDER_FOR_CODE_17并复制到相应的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中的每个集合都有一个新的数据集可用,因此乘法是不可避免的。