结合行波进位加法器与可路由传播/生成信号在FPGA上构建动态块大小进位跳跃加法器

摘要

本发明涉及一种加法器，该加法器在现场可编程门阵列(FPGA)中实现。加法器具有第一行波进位加法器块，用于加法器的最低有效位。加法器具有块大小不同的多个进位跳跃加法器块。每个块大小与输入到块的位宽有关。块大小不同的进位跳跃加法器块用于加法器的多个位。加法器具有第二行波进位加法器块，用于加法器的最高有效位。

说明书

相关申请的交叉引用

本申请要求于2021年2月2日提交的申请号为63144875、标题为“通过结合行波进位加法器与可路由传播/生成信号在FPGA上构建动态块大小进位跳跃加法器(DYNAMICBLOCK SIZE CARRY-SKIP ADDER CONSTRUCTION ON FPGAS BY COMBINING RIPPLE CARRYADDERS WITH ROUTABLE PROPAGATE/GENERATE SIGNALS)”的美国临时专利申请的优先权的权益，该临时专利申请通过引用并入本文。

背景技术

加法在数字设计中很常见，因此现代FPGA具有专门用于实现这一功能的电路。与使用纯粹的查找表(LUT)来实现加法不同，FPGA通常增加有专门用于有效实现加法器的电路。通常，全加器(例如，每个具有输入A、B和进位输入，输出进位及总和)以两种方式之一连接，以实现更宽的加法器。

实现更宽的加法器的一种简单方法是直接添加从全加器的进位输出到另一全加器的进位输入的专用路由，这可用于实现快速行波进位加法器(RCA)。通过行波进位加法器的关键路径由行波进位路径主导，它随着加法器的宽度线性增长，加法器的宽度与加法器输入的位宽和加法器输出的位宽有关。这种类型的加法器在设计用于添加低位宽时通常是相当快的，但由于通过冗长的行波进位路径会产生较长延迟，因此对于高位宽可能会变得相当慢。

在FPGA中用于实现更宽的加法器的另一种选择是在逻辑块群中添加具有固定的块大小(K)的专用超前进位加法器(CLA)电路。块大小与块的宽度或位宽有关，更具体地，与块的输入和/或输出的位宽有关。该进位超前加法器电路用于预先计算一组大小为K的全加器是否会忽略传入的进位输入、传播传入的进位输入或生成进位输出，而不管进位输入的值。该CLA电路加速了行波路径，它的关键路径与位的数量/K成线性关系。K的选择是FPGA架构师必须预先做出的权衡。较大的K值将为宽加法器提供更好的性能，但会导致更高的固定面积损失。

其他工作表明，FPGA上的LUT和加法器可用于实现复杂的并行前缀加法器，这对于非常高的位宽来说可以更快。然而，由于缺少对这些结构的架构支持，因此在典型的FPGA中执行此操作会产生很大的面积开销。

发明内容

本文描述的实施例使用被修改为使传播和生成信号可路由的现有的RCA加法器电路与软逻辑的组合实现一类快速进位跳跃加法器。本文描述的技术允许以最小的架构修改来创建具有可变块大小的快速进位跳跃加法器。在一个实施例中，架构修改并不决定块大小，所以形成加法器的块大小是作为面积和速度之间的权衡在编译时决定的。较大的块大小导致较高的面积开销，而较小的块大小则导致较低的面积开销。对于低位宽的加法器，可以实现标准的RCA，以避免任何软逻辑面积开销。

本文公开的一个实施例是一种在现场可编程门阵列(FPGA)中实现的加法器。该加法器具有第一行波进位加法器块，用于加法器的最低有效位。该加法器具有多个进位跳跃加法器块，该多个进位跳跃加法器块具有不同的块大小。每个块大小与输入到块的位宽有关。多个进位跳跃加法器块用于加法器的多个位。该加法器具有第二行波进位加法器块，用于加法器的最高有效位。

本文公开的一个实施例是一种计算机辅助设计(CAD)方法，该方法由CAD系统实施。该方法包括接收在现场可编程门阵列(FPGA)中实现加法器的指令，以及以用于对FPGA进行编程的格式生成加法器。加法器包括第一行波进位加法器块，用于加法器的最低有效位。加法器包括具有不同的块大小的多个进位跳跃加法器块，用于加法器的多个位。每个块大小与输入到块的位宽有关。加法器包括第二行波进位加法器块，用于加法器的最高有效位。

本文公开的一个实施例是一种其上具有指令的有形的、非暂时性的计算机可读介质。当指令由处理器执行时，会导致处理器执行方法。该方法包括接收在现场可编程门阵列(FPGA)中实现加法器的指令以，以及对FPGA进行编程以实现加法器。加法器包括第一行波进位加法器块，用于加法器的最低有效位。加法器包括具有多个进位跳跃加法器块，该多个进位跳跃加法器块具有不同的块大小。每个块大小与输入到块的位宽有关。多个进位跳跃加法器块用于加法器的多个位。加法器包括第二行波进位加法器块，用于加法器的最高有效位。

在一个实施例中，面积/速度的权衡可以按以下方式决定：

1)由用户使用全局选项，以改进并可能优化整个设计的面积或速度；

2)使用参数化的加法器IP内核，用户可以将其配置为更偏向于面积或速度；

3)使用物理综合技术从面积优化的加法器开始，然后将块大小修改为仅针对关键路径上的加法器的目标速度。

与使用硬超前进位加法器相比，本文公开的加法器实施例具有以下优点中的一个或多个：

·与简单的RCA相比，面积开销减少并且可能为最小，因此与实现超前进位加法器电路相比，FPGA管芯尺寸更小。

·关键路径延迟呈次线性变化，因为块大小可以随着进位链长度的增加而增加。

·可变块大小可用于在广泛的位宽范围内提供优越的性能优势。

·不需要集群的FPGA架构。

附图说明

通过下面给出的详细描述和本发明的各个实施例的附图，本文所描述的实施例将得到更充分的理解，然而，这些附图不应被视为将本发明限制于特定的实施例，而是仅用于解释和理解。

图1示出了使用4-LUT和附加的2:1进位行波多路复用器实现的标准全加器。

图2示出了K＝2进位跳跃加法器块的一个实施例。

图3示出了K＝4进位跳跃加法器块的一个实施例。

图4示出了K＝16进位跳跃加法器块的一个实施例。

图5示出了更快的K＝16进位跳跃加法器块的一个实施例。

图6示出了使用块大小的组合以隐藏一般的路由延迟来构建进位跳跃加法器。

图7示出了选择可变块大小以优化整体的加法器延迟。

图8示出了实现根据本公开的加法器的各种实施例的计算机辅助设计(CAD)系统的一个实施例。

具体实施方式

以下描述中，阐述了许多细节以提供对本实施例的更彻底的解释。然而，对于本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下实践本发明。在其他情况下，以框图形式而不是详细地说明公知的结构和设备，以避免模糊本实施例。

本文描述了用于在FPGA上创建一类快速进位跳跃加法器结构的技术，与使用标准硬RCA的修改版本、利用传播和生成信号驱动路由结构的普通行波进位加法器(RCA)相比，该结构具有较低的面积开销。

图1示出4-LUT(四级查找表)104被分解以实现传播110、生成108和总和106功能的一个实施例。在各种实施例中，查找表是FPGA中的块，其具有布置在多个级中的多路复用器。一般的查找表的一些实施例以及具体的4-LUT的一些实施例，作为块内的块，都具有半加器，例如每个具有输入A和B以及输出进位和总和的半加器。参照图1，4-LUT的下半部分用于创建传播110及生成108信号，它们都使用输入A和B。总和106是使用4-LUT 104的上半部分的3-LUT实现的，并且具有输入118、120、122A/B/Cin。附加的2:1多路复用器116(即，多路复用器)用于生成进位输出信号。如果传播110信号(可选地，传播进位)被断言，则多路复用器116选择进位输入(Cin)112信号，用于进位输出(Cout)114。否则，多路复用器116选择生成108信号(可选地，生成进位)，用于进位输出(Cout)114。

在一些实施例中，使用图1中的4-LUT 104实现的全加器以以下方式操作。作为加法器的输入的操作数A和B被加载到SRAM(静态随机存取存储器)102中。由输入A 118控制的4-LUT 104的第一级多路复用器从SRAM 102选择“A”的值，以传播到4-LUT 104的第二级多路复用器。由输入B 120控制的4-LUT 104的第二级多路复用器从由第一级多路复用器传播的值中选择，并产生生成108(或者称为生成进位)、传播110(或者称为传播进位)和传播到第三级多路复用器以生成总和106的值。在4-LUT 104的第三级多路复用器中，多路复用器中的一个由进位输入(Cin)122控制，并从由第二级多路复用器传播的值中选择，从而生成总和106。传播110控制多路复用器116，根据传播110的值选择进位122或生成108，以进行进位输出114。在本示例中，4-LUT 114的第四级中的多路复用器未被使用。

图2示出了使用所提出的架构实现的具有块大小202K＝2的进位跳跃块的一个实施例。为了与块大小202保持一致，输入“a”(例如，a1，a0)和“b”(例如，b1，b0)和输出(例如，sum1，sum0)中的每一个的位宽为2。参照图2，总和(例如，sum1，sum0)是从左侧的全加器216和218正常生成的。传播(Prop)210是使用单个4-LUT(例如参见图1)生成的，因为它是输入a0、a1、b0、b1的函数。块生成(Block_Generate)208是来自2位进位行波的进位输出，来自通过块214和两个全加器216、218传播的进位输入路由(Cin_routing)204。需要注意的是，如果传播(Prop)210是错误的，则块生成(Block_Generate)208不依赖于直接进位输入(Cin_direct)206，这是使用块生成(Block_Generate)208的唯一情况，例如，由多路复用器222针对进位输出212进行选择，然后将其作为直接进位输出(Cout_direct)和进位输出路由(Cout_routing)从该块传出。因此，进位输入(Cin)以阻止生成是错误的路径。然后，使用通用路由将块生成(Block_Generate)208和传播(Prop)210路由到另一个全加器块(未示出，但容易设想)。该另一个全加器块实现块行波进位。进位跳跃块为组预先计算进位传播和进位生成信号，这样进位就不必波及进位跳跃块内的所有全加器块。

图3示出了利用所提出的K＝4的架构实现的具有块大小302的进位跳跃块的一个实施例。这与图2中的实施例类似，除了输入和输出总和是四位宽以与块大小302保持一致，存在四个一位宽的全加器316、318、320、322，并且通过AND块324将来自左侧的加法器316、318、320、322的每个单独全加器的传播信号进行AND运算生成传播306。这种使用宽AND门逻辑生成传播306的方法对于K>2来说节省了面积。通过块314和全加器传播以产生块生成308的进位输入路由304、直接进位输入310、由多路复用器326生成以进行直接进位输出和进位输出路由的进位输出312也类似于图2中的实施例。

图4示出了以所提出的K＝16的架构实现的具有块大小402的进位跳跃块的一个实施例。需要注意的是，与图3相比，存在额外级的4-LUT，其布置为连接到AND块420的AND块418以将来自左侧的十六个一位宽全加器416的传播信号进行AND运算。这种使用宽AND门逻辑生成传播408的方法对于K＝16来说节省了面积。通过块414和全加器传播以产生块生成406的进位输入路由404、直接进位输入410、通过多路复用器422生成以进行直接进位输出和进位输出路由的进位输出412也类似于图2和图3中的实施例。

图5示出了通过使用行波进位加法器516实现宽AND功能来生成块生成508信号。通过修改行波路径中LUT的LUTMASK(查找表掩码)，可以将功能从加法器更改为按位(bitwise)AND。图5示出了具有K＝16的块大小502的进位跳跃块的一个实施例，与图4所示的实施例相比，其具有更快的进位跳跃块架构。块生成508由行波进位加法器516的宽AND函数产生。块传播(Block_Prop)506由块518产生。直接进位输入510、由多路复用器520生成以进行直接进位输出和进位输出路由的进位输出512也类似于图2、图3和图4中的实施例。

参照图2-5中的进位跳跃加法器实施例，可以将任意数量的带有半加器的查找表连接在一起，以生成用于块的组进位传播，其处理任意数量的位，实际上当然受设备大小的限制。图2-5示出了如何创建块进位生成和块进位传播。块进位生成决定是否生成进位输出，而不管进位输入值如何。并且，块进位传播决定是否将组进位输入传播到进位输出。这被称为软逻辑，并且为了在加法器实施例中实现这种逻辑，通过常规路由访问进位传播，这在本实施例之外的FPGA架构中可能通常不是这样的。在一些实施例中，进位传播信号来自半加器的内部电路，并且被暴露于外部路由(即，在半加器外部的路由)，例如作为查找表或逻辑块的输出端口。在进位跳跃加法器实施例中，每个大小为K的进位跳跃加法器块的进位传播信号进入用作组进位链的进位链的一个位。而且，进位生成信号来自半加器的内部电路并被暴露于外部路由，并进入进位链的同一个位(参见图1-5中的多路复用器生成进位输出)。由于这种架构，关键路径是从进位输入到进位输出，这可以非常快，特别是对于进位链的那一位的硬逻辑。硬逻辑在这里是指一种专用的、快速的电路，而不是由其他可编程、可配置元件组成的电路。相比之下，软逻辑在这里是指可编程的、可配置可用于构建逻辑电路以通过对FPGA进行编程来实现特定功能的逻辑。从块内部暴露进位传播信号和进位生成信号可以构建进位跳跃加法器。在各种实施例中使用例如用于硬逻辑的专用的、特定尺寸的多路复用器，尽管在进一步的实施例中可以使用专用的、特定尺寸的组合逻辑。在进位的关键路径中使用例如特定多路复用器的硬逻辑允许组进位行波通过硬逻辑，与软逻辑相比，速度非常快。

图6示出了通过使用普通RCA开始和结束进位跳跃加法器来隐藏创建的块生成/传播信号的延迟。这意味着可变块大小的进位跳跃加法器的一个实施例的延迟永远不会比普通RCA慢。图6示出了以下的实施例：由用于输入和输出的最低有效位的行波进位加法器604(这里示出为具有两个或多个一位宽加法器)组成的加法器、由对于输入和输出的中间位的每个块大小为K＝4的两个进位跳跃加法器608、610组成的进位跳跃加法器、以及用于输入和输出的最高有效位的行波进位加法器604(这里示出为具有两个或多个一位宽加法器)。在图6所示的示例中，即使一个块中有5个LUT，由于第一个LUT仅用于将进位输入从通用逻辑路由到通向加法器的专用进位路径，因此它也是一个K＝4的块。也就是说，最顶层的LUT没有实现全加器。用于加法器进位的关键路径602通过行波进位加法器604、进位跳跃加法器608、610和行波进位加法器606传播。但是，因为进位跳跃加法器中的进位逻辑相对较快，所以关键路径602比在相同的技术，例如在FPGA中实现的类似大小的行波进位加法器的进位的关键路径更块。换句话说，在其他因素相同的情况下(例如技术、给定元件的电路延迟、位宽)，如图6所示的可变块大小的进位跳跃加法器的架构以及用于最低有效位和最高有效位的行波进位加法器在关键路径602上产生比行波进位加法器更快的进位。这些特征在具有各种宽度的行波进位加法器以及进位跳跃加法器块的各种宽度和相应块大小的加法器的进一步实施例中得到了概括。

图7示出了动态进位跳跃加法器的最佳的块大小，以减少并可能最小化关键路径延迟。需要注意的是，在一个实施例中，选择进位跳跃加法器块702的块大小来计算加法器位的最大数量，该最大数量可以在加法器的给定级或块中计算，而无需在进位跳跃加法器块702的传播/生成逻辑中创建关键路径，该创建将减慢加法器进位的关键路径704中的进位传播。

在图7所示的实施例中，进位跳跃加法器块702的块大小从位于进位跳跃加法器块702的较低有效位端的K＝2向加法器的中间位增加到K＝6，并且从加法器的中间位向进位跳跃加法器块702的更高有效位端减少到K＝2。该特征在具有各种块大小值以及通过实现的加法器的块大小的各种增量和减量的加法器的进一步实施例中得到了概括。

在一个实施例中，在块大小选择方面，用户可以通过以下方式来选择加法器结构：利用用户可以使用物理综合技术从面积优化的加法器开始在他们的设计中实例化(例如，用户可以指定控制加法器结构的参数)、然后修改块大小以仅针对关键路径上的加法器的目标速度的参数化的加法器模块，通过指定CAD工具是否应该更多地关注面积或性能(这是影响整个设计的全局选项)，来选择加法器结构。

因此，如上所述，使用硬资源和软逻辑/路由的混合，在FPGA上有效地实现进位跳跃加法器结构。在实施例的范围内，至少包括以下特征，以及CAD系统生成具有这些特征的各种组合的加法器实施方式的能力。

·一种加法器结构，其使用路由传播并从加法器逻辑生成信号以创建进位跳跃加法器结构。

·一种加法器结构，其具有可变进位跳跃块大小，以隐藏与生成组传播和生成信号相关联的路由延迟。

·一种加法器结构，其在加法器结构中具有定制的块大小，以权衡加法器面积的性能。

·一种加法器结构，其包括用于快速块传播生成的生成宽AND门逻辑的行波进位结构。

加法器结构具有两个或多个前述特征。

各种实施例在各种组合中具有的进一步特征如下。

·与用于可在FPGA中实现的具有与加法器相同的整体输入位宽的行波进位加法器的关键路径延迟相比，用于加法器的进位的关键路径延迟更低。

·与可在FPGA中实现、由具有固定的块大小的进位跳跃加法器块组成的进位跳跃加法器的面积相比，FPGA中加法器的面积更低，该固定的块大小等于不同的块大小中的最大者。

图8示出了实现根据本公开的加法器的各种实施例的计算机辅助设计(CAD)系统802的一个实施例。在处理器806上执行的CAD工具804接收用于加法器808的指令，例如来自用户的用于CAD工具804的适当格式(例如，RTL中的文件，即，寄存器传输语言、Verilog或VHDL编码等)。CAD工具804使用例如以适当的格式输出以用于对FPGA进行编程的参数化的加法器模块810来生成加法器实施方式812。然后，CAD系统802或其他系统可以对FPGA进行编程，从而产生具有加法器实施方式812的编程的FPGA 814。在各种实施例中，上述实施例的各个方面和特征由CAD工具804或由用户选择配合CAD工具804自动完成。在进一步的实施例中，上述实施例的各个方面和特征进一步以各种组合应用于其他类型的集成电路，以及用于其他类型的集成电路的CAD工具和CAD系统，例如全定制、ASIC(专用集成电路)、PLD(可编程逻辑器件)等。

在各种实施例中，在具有块内块的分层结构中，综合将整个加法器创建为一个块。例如，如果被指示实现32位加法器，则CAD工具804创建用于创建加法器的进位跳跃版本的所有块大小。在一些实施例中，CAD工具804探索权衡，例如块大小越大，创建组、生成和传播信号所花费的时间就越长。回到32位加法器的示例，CAD工具804可以将设计分成四个八组或八个四组，并分析关键路径，然后选择两种可能性中的哪一种对于进位时序是最佳的。CAD工具804可以确定四位行波加法器的时序，并比较用于四位进位跳跃加法器的时序。这种比较可以针对加法器的各个阶段，以不同的块大小组合进行。

已经发现，随着加法器的大小和宽度增加，计算进位所需的时间以次线性方式变化。并且，比较行波进位加法器的关键路径，计算进位所需的时间与加法器的宽度呈线性关系。因此，已经发现，低于某个位宽，行波进位加法器是最快的。这样的位宽可以在CAD工具804中用作阈值。被指示实现位宽低于或等于阈值的加法器，CAD工具804可以实现行波进位加法器。大于该位宽，CAD工具804可以实现以行波进位加法器开始和结束，即一个行波进位加法器用于低位，另一个行波进位加法器用于高位，并且具有用于中间位的进位跳跃加法器或块大小不同的多个进位跳跃加法器块。

在开始时，CAD工具804可以从较小的块大小开始，例如块大小为2。然后存在额外的阈值，从分析上讲，在该阈值处，增加下一个块的块大小并且仍然低于延迟以跟上通过进位的关键路径的行波是有意义。这就是在各种实施例中隐藏一般路由延迟的含义。将用于给定的进位跳跃加法器模块的进位生成和进位传播信号的延迟与用于组装的加法器的进位的关键路径上的延迟进行比较，然后根据该比较确定进位跳跃加法器模块的可接受的块大小(以及块进位生成和块进位传播信号的次关键延迟)。

在某些时候，例如大约在加法器的中途，添加大的块可能会创建新的关键路径以生成和位。添加较小的块，生成加法器的后期或最后和位所需的延迟较少，避免了这条新的关键路径。CAD工具804可以沿这个方向进行，朝加法器的更有效位生成更小的块大小。然后，可以使用另一个行波进位加法器来实现加法器的最终位，这将比另一个进位跳跃加法器块更快。经过加法器的中间，CAD工具804可以创建更小的块大小并不断减小块大小，因为在行波结束时可以掩盖的延迟更少。

CAD工具804的一些实施例通过进位链中的行波和块进位生成和块进位传播信号中的延迟来平衡延迟，优化利用可变块大小实现的加法器的块大小。使用更大的块大小意味着进位的关键路径中的行波阶段更少，这会加快进位传播，但会使总和生成速度变慢。

CAD工具804的一个实施例查看加法器的每个位，并确定如何计算下一组位的总和，例如，这将是一次一位、一次两位、三位还是一次四位等等。有两个因素决定，一个是有足够的延迟来生成比迄今为止在进位的关键路径中累积的延迟更早的组生成信号。另一个因素是考虑到通过通用路由的链路的行波的情况下的总和位的生成。使一些信号变慢是可以接受的，因为它们不在关键路径中，这决定了块大小可以是多大。存在外向约束和输入约束。在加法器的更有效位端，总和位可能会被减慢并成为关键路径。从算法的角度来看，一个判断是它是否通过生成块来创建新的关键路径，如果是，那么尝试更小的块。

以上详细描述的一些部分是就对计算机存储器内数据位的操作的算法和符号表示的方面来呈现的。这些算法描述和表示是数据处理领域的技术人员用来将他们的工作内容最有效地传达给本领域其他技术人员的手段。这里通常认为算法是导致期望结果的自洽的步骤序列。这些步骤要求物理地操控物理量。通常，尽管不是必须的，这些物理量采用能够被存储、传输、组合、比较以及以其他方式操控的电信号或磁信号的形式。已经证明，主要出于通用的原因，将这些信号称为位、值、元素、符号、字符、术语以及数字等有时是方便的。

然而，应该牢记的是，所有这些和类似术语都将与适当的物理量有关并且仅仅是应用于这些量的方便标签。除非从下面的讨论中明显地另行说明，否则理解的是，在整个说明书中，利用诸如“处理”或“用计算机计算”或“计算”或“确定”或“显示”等术语的讨论是指计算机系统或者类似的电子计算装置的动作和处理，其将表示为计算机系统的寄存器和存储器内的物理(电子)量的数据操纵并且转换为类似地表示为计算机系统存储器或者寄存器或者其它这种信息存储、传输或者显示装置内的物理量的其它数据。

本发明还涉及用于执行本文操作的设备。该设备可以为所需目的而专门建造，或者其可以包括由存储在计算机中的计算机程序选择性地激活或重新配置的通用计算机。这样的计算机程序可以存储在计算机可读存储介质中，例如但不限于：包括软盘、光盘、CD-ROM和磁光盘的盘的任意类型，只读存储器(ROM)，随机存取存储器(RAM)，EPROM，EEPROM，磁卡或光卡，或适用于存储电子指令的任何类型的介质，并且每个介质都与计算机系统的总线连接。

本文提出的算法和显示并非固有地与任何特定计算机或其他装置相关。各种通用系统可以根据本文的教导与程序一起使用，或者可以证明构造更专用的设备以执行所需的方法步骤是方便的。各种这些系统所需的结构将从下面的描述中看出。另外，本发明没有参考任何特定的编程语言来描述。应当理解的是，可以使用各种编程语言来实现如本文所述的本发明的教导。

机器可读介质包括用于以机器(例如计算机)可读的形式存储或传输信息的任何机制。例如，机器可读介质包括只读存储器(“ROM”)；随机存取存储器(“RAM”)；磁盘存储介质；光学存储介质；闪速存储器装置；电、光、声或其他形式的传播信号(例如，载波、红外信号、数字信号等)；等等。

尽管在阅读了前述描述之后，本发明的许多改变和修改对于本领域普通技术人员来说无疑将变得显而易见，但是应该理解的是，通过说明的方式示出和描述的任何特定实施例绝不意图被视为限制性的。因此，对各种实施例的细节的参考并不旨在限制权利要求的范围，权利要求本身仅叙述被认为是对本发明必不可少的那些特征。