具有n输入算术运算符的并行流水线移位加法常数乘法的理论下限

与常数相乘是数字信号处理系统中的常规操作。在硬件中，乘法在面积和功耗方面要求很高。然而，单常数乘法和多重常数乘法运算可以仅通过移位、加法和减法来实现，最后两者通常以一般形式称为加法。

PSCM案例：每当定理（定理 1 到 8）中提到常数 c 时，我们认为该常数的 MNSD 是 S，它的基因数数是Ω。定理 1 提供了非零位数的上限，这些数字可以由具有给定深度级别数的任何图形生成，无论其 R 操作数如何。由此，我们可以知道图形必须具有的最小深度级别数才能实现具有给定 S 的常量。

定理 2 和 3 证明了完全乘法图的性质，即以尽可能少的 R 运算数生成定理 1 中提到的非零位的上限。从他们那里，我们可以得到完全乘法图是一个具有 R 运算数下限的解决方案。

然而，众所周知，这个图有关节点，每个关节点代表两个级联子图之间的并集，即两个较小常数的乘积。因此，定理 4 使用Ω来确定哪些常数可以用完全乘法图实现。

定理 5 确定了具有给定深度级别的任何非乘法图中所需的最小 R 运算数，定理 6 证明非乘法图可以生成定理 1 中提到的非零位的上限及其最小 R 运算数。然后，定理 7 建立了实现素数常数所需的 R 运算次数的下限。

最后，定理 8 完成了定理 4 和 7 的信息，即实现非素数常数所需的 R 运算下界，这些常数的因子数少于完全乘法图中使用的子图数。

具有 p 深度水平的完全乘法图具有 p 个 A 运算，每个 A 运算形成一个子图。根据[38]，两个子图之间的流水线只需要一个寄存器，因为流水线发生在关节点上。这导致每个 A 操作后都有一个寄存器。由于 A 操作后跟寄存器被视为 R 操作，因此总共只有 p 个 R 操作。

考虑一个具有 p 深度水平的图，该图由两个完全乘法图组成，每个图的（p − 1）级，从图的输入并行连接，并在第 p 级放置一个 A 运算，用于汇总上述图的输出。其中一个图的输出连接到最后一个 A 运算的 n − 1 个输入，另一个图的输出连接到最后一个 A 运算的剩余输入。这是一个非乘法图，因为它不是由级联子图形成的，它是由 （2p − 1） A 运算组成的。

根据定理2，我们可以得到n p − 1来自完全乘法图的非零数字，根据定理 3，这些图可以在不需要额外寄存器的情况下进行流水线化。

证明：由于 Ω = 1 成立，因此必须使用非乘法图来实现该常数。根据定理 6，我们有一个常数，其中≤ S ≤ n p非零数字可以用至少 p 深度级别和至少 2 p − 1 R 运算来实现。这是 R 运算数量的下限，因为根据定理 5，我们可以得到具有 p 水平的非乘法图至少需要 2p − 1 个 R 运算。

证明：由于 Ω = 1 成立，因此必须使用非乘法图来实现该常数。根据定理 6，我们有一个常数，其中≤ S ≤ n p非零数字可以用至少 p 深度级别和至少 2 p − 1 R 运算来实现。这是 R 运算数量的下限，因为根据定理 5，我们可以得到具有 p 水平的非乘法图至少需要 2p − 1 个 R 运算。

PMCM案例：定理针对 N 个常数 c 进行陈述 1， c 2， ...， c N ，其各自的 MNSD 为 S 1， S 2， ...， S N ，并且它们各自的基因数数Ω13 V2, ..., Ω N ，使得 S 1≤ S 2≤ ...≤ S N。

定理 9 表示形成 MCM 块所需的 n 次输入 A 运算次数的下限。如果添加流水线，则可能需要比上述下限更多的 R 运算，因为素因数较少的常量可能使用非乘法图，这需要额外的 R 运算。

此外，PMCM模块的所有输出必须具有相同数量的深度级别，以平衡输入-输出延迟，这也可能需要额外的R操作。基于这些观察结果，定理 10 通过确定至少需要多少额外的 R 运算来扩展定理 9 中提供的下限。从这些定理中，我们获得了形成PMCM块所需的R操作次数的下限。

最后，定理 9 表示形成 MCM 块所需的 n 次输入 A 运算次数的下限。如果添加流水线，则可能需要比上述下限更多的 R 运算，因为素因数较少的常量可能使用非乘法图，这需要额外的 R 运算。

此外，PMCM模块的所有输出必须具有相同数量的深度级别，以平衡输入-输出延迟，这也可能需要额外的R操作。基于这些观察结果，定理 10 通过确定至少需要多少额外的 R 运算来扩展定理 9 中提供的下限。从这些定理中，我们获得了形成PMCM块所需的R操作次数的下限。