关键字 |
| Kogge-Stone加法器，达达乘法器，Brent-Kung加法器，Han-Carlson加法器 |
介绍 |
| 高速乘法是许多高性能数字系统的基本要求。为了这个目的，已经开发了并行乘法方案。并行乘法器有两类，即数组乘法器和树乘法器。树乘法器，也称为列压缩乘法器，以其较高的速度而闻名，这使得它们在高速计算中非常有用。它们的传播延迟与操作数字长对数成正比，而数组乘法器的延迟与操作数字长[1]成正比。列压缩乘法器比阵列乘法器速度快，但结构不规则，因此设计困难。随着超大规模集成电路(VLSI)设计技术和工艺技术的进步，以前不可行或难以通过人工布局实现的设计现在可以通过自动合成来实现。 |
| 两个最著名的列压缩乘法器已经由Wallace[3]和Dadda[4]提出。这两种结构是相似的，不同之处在于部分积的约简过程和最终加法器的大小。在华莱士吗?S方案下，尽快减少部分产物。另一方面，爸爸?s方法在每一层都做了最小的必要缩减，需要与华莱士乘法器[5]相同的层数。本文介绍了一个生成指定大小的达达乘法器Verilog文件的C语言程序。最后，对不同大小的哒哒乘法器与并行前缀加法器后期综合和后期布局结果进行了比较。第二和第三部分解释了爸爸?s算法及其在C语言中的实现来创建一个自动Verilog文件生成器。 Section IV gives the post synthesis and also post layout results for the multiplier of varying sizes. |
哒哒乘数架构 |
| 哒哒乘数体系结构可分为三个阶段。第一阶段是利用Baugh-Wooley[2]提出的二补并行数组乘法算法生成部分积。在他们的算法中，所有部分积位的符号都是正的。它与传统的二补乘法不同，传统的二补乘法产生的部分积位带有正负符号。还原后得到的最终产品也是在二?S补形式。图1为Baugh-Wooley法生成4x4乘法器的部分乘积。图2(a)显示了8x8乘数的部分乘积的排列。圆点代表部分积。 |
| 在第二阶段，使用哒哒开发的列压缩程序将部分乘积矩阵简化为2的高度。这样做的迭代过程如下: |
| 1.设h1 = 2，重复hj + 1=地板(1.5*h .j)，以增加j的值。继续这样做，直到j达到最大，此时在现阶段矩阵中至少有一列的点比hj多。用这个方程，我们得到h1h = 2,2h = 3,3.h = 4,4= 6 h5=9，以此类推。例如，在图2(a)所示的8x8达达乘法的第一阶段，列的最大高度为8，因此，hj的值为6意味着列的高度降低到最大6。第二阶段同理，如图2(b)所示，列高度的最大值为6,hj的值为4，列高度的最大值为4。 |
| 2.所有高大于hj的列都被降为hj使用半加法器或全加法器。如果列高必须减少1，使用半加法器，否则使用全加法器，继续这一步，直到列高减少到hj． |
| 3.如果矩阵高度为2，则停止约简，然后将其馈入最终加法器。 |
| 图2 (b)、(c)、(d)和(e)显示了8x8达达乘法器的减小阶段。 |
| 一旦矩阵的高度降低到2，使用2N-2位加法器来生成最终产品。本文描述了在最后加法器阶段使用不同的并行前缀加法器，稍后将在第III-D节中描述。 |
Verilog代码生成 |
| 编写C程序的主要目的是根据用户输入n为NxN达达乘数输出一个verilog文件。我们实现了达达算法，并使用C语言将verilog代码写入一个文件来实现这一目标。 |
A.初始化Verilog模块 |
| 最初，程序提示用户输入乘数的大小。在接受大小后，程序创建一个空的Verilog文件，并在其中打印半加法器和全加法器模块。接下来，它会打印门级别”和?部分积生成的原语。在此之后，使用上面生成的子模块打印顶层乘数模块。 |
| 顶部模块包含两个n位输入?数据类型，一个2N位的输出?乘数位、乘数位和积位的数据类型。该程序还设置了N2“导线?用于存储部分产品的数据类型。在Verilog文件中设置了上述所有模块和数据类型后，程序将打印所需数量的半加法器和全加法器，以降低列的高度，如前面第ii节所述。列约简利用C语言中的点阵数组，如下所述。 |
B.点阵数组创建 |
| 为了实现列压缩根据哒哒?S算法，该程序在内部创建了一个等价的点阵数组。数组的列由队列(先进先出数据结构)表示。因此，程序创建2N-1队列，其中每个队列都实现为链表。 |
| 所有队列的第一个和最后一个元素的大小和指针都被存储。这允许更快的入队和出队操作。队列中的每个元素都存储一串字符，特别是携带部分产品的连接的名称。 |
| 最初，队列中装载了持有部分产品的连接的名称。 |
C.阵列约简 |
| 一旦数组，使用队列，已经在C中创建，它需要根据达达?年代的算法。 |
| 第二节中描述的递归过程是用C语言使用while循环实现的。队列的大小(列的高度)通过使用全加法器和半加法器来减小。当所有队列的长度(所有列的高度)小于等于2时，循环停止执行。 |
| 在每次迭代的开始，说迭代no。i，检查所有2N-1队列的大小，它们的最大值存储在L[i]中。hj值的计算也如第ii节中定义的迭代过程的第一部分所示。hj的值存储在H[i]中。 |
| 计算H[i]后，开始还原阶段。从队列1开始，依次检查所有队列的大小。如果队列的大小小于或等于H[i]，则不对队列进行任何更改。如果队列的大小大于H[i]，则需要使用半加法器和全加法器将队列减小到H[i]。 |
| 这两种加法器的使用取决于队列长度和H[i]之间的差值。如果差值为1，则使用半加法器。前两个元素被退出队列，并用作半加法器的输入。从半加法器得到的和被排队到同一个队列中，执行被按顺序排队到下一个队列中。每使用一半加法器，队列的大小就减少1。 |
| 如果队列长度与H[i]之间的差值大于或等于2，则使用全加法器来减少队列。当使用完整加法器时，队列的前三个元素将从队列中退出，并作为完整加法器的输入提供。完整加法器的和被放入同一队列，而执行被依次放入下一个队列。对于每使用一个完整的加法器，队列的大小减少2。递归地执行上述过程，直到队列的大小等于H[i]。当一个队列被缩减后，按顺序使用下一个队列进行缩减。在检查队列长度以减少时，会考虑之前队列的进位。迭代继续进行，直到每个队列中最多保留两个元素。一旦达到这种状态，“while?”环路退出，还原阶段完成。 |
| 通过一个示例解释了使用队列的数组缩减。以一个4x4哒哒乘法为例。还原开始前队列的状态如图3(a)所示。减少4x4乘数的队列解释如下: |
| 1)迭代一:在检查所有队列的大小时，观察到本次迭代的最大长度(L[1])为4，可以计算出H[1]为3。因此，所有大小大于3的队列都需要缩小。队列1-3的大小小于或等于3。由于队列4的长度比所需的长度大1，因此队列的前两个元素将从队列中退出。通过在Verilog文件中打印半加法器，这些脱离队列的元素在半加法器中求和(“ha0?”)。半加法器的和位被分配给“ha0s?”同一半加法器的进位被赋给导线“ha0c?”根据算法，“ha0s?”是排队到队列4和“ha0c?进入Queue 5。 Fig. 3(b) shows the elements to be enqueued to Queues 4 and 5. The elements above the arrow in the queue are the ones which are enqueued in this iteration. The addition of one more element to Queue 5 increased the length of the queue to 5. Hence, a full adder („fa0?) is used to reduce its length to 3. The addition of the full adder leads to dequeuing of the first three elements of Queue 5 and enqueuing of the sum of the full adder„fa0s? to Queue 5 and the carry out of the full adder „fa0c? to Queue 6. This iteration is now complete because the length of all queues is less than or equal to three. The state of the queues at the end of stage one is shown in Fig. 3(c). |
| 2)迭代二:在检查所有队列的大小时，观察到第二次迭代的最大长度(L[2])为3，可以计算出H[2]为2。因此，所有大小大于2的队列都需要缩小。程序开始按顺序检查队列的大小。队列3是长度大于2的第一个队列。因为长度只超出了1，所以使用半加法器(“ha1?”)将长度减少到2。前两个元素(由正方形包围)作为半加法器和“ha1s?”以“ha1c?”正在进入队列4。这将队列4的长度增加到4，比允许的大小多2个。因此，使用全加法器(“fa1?”)将其长度减少到2。 The addition of the full adder leads to dequeuing of the first three elements of Queue 4 and enqueuing of the sum of the full adder„fa1s? to Queue 4 and the carry out of the full adder „fa1c? to Queue 5. This increases the size of Queue 5 to four. It undergoes the same procedure as Queue 4. Queue 6 also faces the same situation and undergoes the same procedure outlined above. Fig. 3(d) shows the elements dequeued and enqueued to Queues 3, 4, 5 and 6. The final state of the queues at the end of stage two is shown in Fig. 3(e). |
D.最后阶段加法器 |
| 一旦所有队列的大小减少到两个或更少，队列中的元素就可以使用加法器进行求和了。所有队列的第一个元素构成加法器的第一个输入，第二个元素构成加法器的第二个输入。对于NxN乘法器，加法器的大小必须是2N-2位。使用不同的并行前缀加法器，如Kogge- Stone加法器，Brent-Kung加法器和Han-Carlson加法器。下面描述了这些加法器的实现。 |
| 1) Kogge-Stone加法器:Kogge-Stone加法器在O(log n) time[6]内产生进位信号。大小为2N-2的基数-2 Kogge-Stone加法器被用作NxN乘法器的最终加法器。图4显示了不带进位的8位Kogge- Stone加法器的示例。方框中的第一个位是传播位，而第二个位是生成位。最初(阶段零)在一个n位Kogge-Stone加法器中，传播位和生成位根据(1)生成。 |
 |
| 其中an和bn是两个输入的第n位。 |
| 在ith(i≥1)阶段在第n块(P我,n和G我,n)按(2)计算。 |
 |
| 其中m由(3)给出 |
 |
| 最后，根据式(4)计算进位和和位。 |
 |
| 在年代n和Cn分别是和和和进位的第n位。Gf, n是最后阶段第n个块的生成位。 |
| 加法器中的阶段数取决于它的大小。在大小为N的Kogge-Stone加法器中，有ceil(log2N)+1级。由于NxN乘法器的最后一级需要一个2N-2位加法器，加法器的级数为ceil[log2(2N-2)]+1。Kogge-Stone加法器的对数延迟是保持乘法器整体对数延迟的关键。 |
| 2) Brent-Kung加法器:Kogge-Stone加法器性能较高，但占地面积较大。Brent-Kung加法器的布放面积比Kogge-Stone加法器小，线路拥塞少，但时间性能较差[7]。在大小为N的Brent-Kung加法器中，有Ceil[2*log2(N)]级。在n位Brent- Kung加法器的初始阶段(阶段零)，传播位和生成位根据(5)生成。 |
 |
| 一个n和bn是两个输入的第n位吗 |
| 在第i(1≤i≤log2(N))阶段，在第N个块(P我,n和G我,n)按(6)计算。 |
 |
| 其中m由(7)给出 |
 |
| 计算第i级(log .)的生成和传播位2(N)+1≤i <2*log2(N))，我们定义了三个变量count, x和y。count =k，其中对于i= log, 2k是最小整数≥N且x∈Z+， x≥2且x=22(N)+1，并为后续的每一阶段和递增1 |
 |
| 现在在第i阶段，传播和生成第n个块(P我,n和G我,n)按…计算 |
 |
 |
| 其中m和l分别由(10)和(11)给出 |
 |
 |
| 最后，根据式(12)计算进位和和位。 |
 |
| 在年代n和Cn分别是和和和进位的第n位。Gf, n是最后阶段第n个块的生成位。 |
| 图5显示了8位布兰特-孔加法器的示例。由于NxN乘法器的最后一级需要2N-2位加法器，加法器的级数为ceil[2*log]2(2 - 2)。 |
| 3) Han-Carlson加法器:Brent-Kung加法器减少面积和功率，但不产生最小深度的并行前缀电路。它们的延迟时间也很高(2*log2Kogge-Stone加法器具有较小的延迟(log2N)，但具有较高的面积和功率。通过结合B-K和K-S图，Han和Carlson得到了一种新的混合前缀图，它实现了面积和时间的中间值[8]。图6是一个8位汉-卡尔森加法器的例子。加法器中的阶段数取决于它的大小。在大小为N的汉-卡尔森加法器中，有Ceil[log2(N) + 2)阶段。 |
| 最初(阶段零)在一个n位汉卡尔森加法器，传播和生成位是根据(13 |
 |
| 一个n和bn是两个输入的第n位吗 |
| 在第i(1≤i≤log2我n和G我,n)按(14)计算 |
 |
| 让S = {n ?2张+2 ≤ n ≤ N, n is even} |
 |
| 哪里m =n - 2张 |
| 在最后一个阶段(i=log . log .2(N)+1)在第N块(P我,n和G我,n)根据(16 .)计算 |
 |
| 让R = {n ?3.≤ n ≤ N, n is odd} |
 |
| 最后，根据式(17)计算进位和和位。 |
 |
| 在年代n和Cn分别是和和和进位的第n位。Gf, n是最后阶段第n个块的生成位。 |
| 由于NxN乘法器的最后一级需要一个2N-2位加法器，加法器的级数由ceil[log2(2N-2)+2]给出。 |
结果与讨论 |
| 所有的乘数设计都使用Verilog作为HDL。比较了上一节讨论的所有并行前缀加法器与哒哒乘法器的综合和后布局结果。本节为上述所有架构提供以毫秒为单位的延迟、以平方微米为单位的面积和以毫瓦为单位的功率。在典型(tt)条件下，在Cadence RTL编译器中使用90 nm UMC技术库进行合成。合成的网络列表与设计约束.sdc文件、技术库文件和.lef文件一起使用SOC Encounter工具生成布局。对不同尺寸的哒哒乘数进行了布局，并将其后期布局结果制成表格。后期布局结果与后期综合结果具有相同的趋势。 |
| 后置布局区域为芯线区域，包括标准单元区域和互连线区域。图7显示，在最后阶段使用Kogge-Stone加法器的乘法器比使用其他加法器的乘法器要快得多。如图8所示，它的功耗是所有功耗中最高的。图9比较了功率延迟产品 |
| 可以观察到，使用Kogge-Stone加法器和Han-Carlson加法器的达达乘法器在最后阶段比使用Brent-Kung加法器的达达乘法器具有更低的功率延迟乘积。与Kogge-Stone和Han-Carlson加法器相比，Brent-Kung加法器的达达乘法器的功率和面积较低，但由于延迟较高，其功率延迟积也较高。 |
结论 |
| 本文介绍了一种简单有效的生成用户指定大小的达达乘法器可合成Verilog代码的方法。最后阶段采用并行前缀加法器，大大提高了哒哒乘法器的运算速度，并得到了较低的功率延迟乘积。并行前缀加法器的对数延迟补充了压缩树的对数延迟，从而提供了一个整体的对数延迟。 |
表格一览 |
|
|
|
数字一览 |
 |
 |
 |
 |
 |
| 图1 |
图2 |
图3 |
图4 |
图5 |
 |
 |
 |
 |
| 图6 |
图7 |
图8 |
图9 |
|
|
参考文献 |
- P. R. Cappello和K . Steiglitz，“管道衬里的达达乘法器的VLSI布局”，ACM计算机系统汇刊1,2(1983年5月)，第157-17页
- 查尔斯·鲍;伍利，文学士，“A二的互补并行数组乘法算法”，计算机，IEEE汇刊，卷c - 22, no. 2。12，第1045页，1047页，1973年12月
- Wallace, C. S.，“一个快速乘法器的建议”，电子计算机，IEEE汇刊，vol.EC-13, no. 1。1、1964年2月，第14、17页
- L.达达，“并行乘法器的若干方案”，《频率分析》，第34卷，第349-356页，1965年
- Townsend, W. Swartzlander, E. Abraham, J.，“Dadda和Wallace乘数延迟的比较”。高级信号处理算法，体系结构和实现
- 彼得·M.科格;石，哈罗德S.，“有效解一类一般递归方程的并行算法”，计算机，IEEE汇刊，vol.C-22, no. 1。第8卷，第786,793页，1973年8月
- 理查德·布兰特;龚海涛，“并行加法器的规则布局”，计算机与电子工程学报，vol.C-31, no. 1。第3页，第260、264页，1982年3月
- 汉族,Tackdon;卡尔森，D.A，“快速高效的VLSI加法器”，计算机算术(ARITH)， 1987年第8届IEEE研讨会上，卷，no. 2。， 1987年5月18日至21日第49、56页
|
菜单
