Browse Prior Art Database

Carry Lookahead Load Balancing

IP.com Disclosure Number: IPCOM000125184D
Original Publication Date: 2005-May-23
Included in the Prior Art Database: 2005-May-23
Document File: 5 page(s) / 32K

Publishing Venue

IBM

Abstract

The congestion and heavy loading requirements of the lesser significant carry bits in a Carry-Lookahead Adder to form the more significant carry bits present a timing and routing challenge in the formation of a dense and fast design. Off-loading these lesser significant carry bits onto other carry bit positions to be utilized to form the more significant carry bits is discussed as a means to improve the speed and reduce the area needed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 40% of the total text.

Page 1 of 5

Carry Lookahead Load Balancing

A carry bit generation tree is formed in three levels of logic. The first level occurs by forming a carry out of every nibble. A 64 bit adder implementation wouldhave 16 nibble carry outs. The second level utilizes the previous levels' nibble carry outs to form 16 bit wide carry outs. There are 15 16 bit wide carry groupings for a 64 bit adder. These groupings overlap a given nibble such that there is a carry out of every fourth bit position. The final level forms a carry bit for every 4th bit position by combining the outputs of the first and second level carries while the load of any given first or second level output does not exceed four loads. This is a balanced loading scheme claimed to be unique and novel by this invention. This loading scheme can be compared with a traditional Carry Lookahead Adder which tends to have heavier loading on the lesser significant carry terms. What follows is a detailed logical description of the boolean equations for these levels of carry-generation as well as the final sum formation output from a 64 bit adder utilizing this carry-generation scheme:

64-bit ling adder implementation:

First level (prior art):

Gi = Ai * Bi

Pi = Ai + Bi, where i= bit position

Second Level (prior art):

P02_05 = P02*P03*P04*P05

P06_09 = P06*P07*P08*P09
P10_13 = P10*P11*P12*P13
P14_17 = P14*P15*P16*P17
P18_21 = P18*P19*P20*P21
P22_25 = P22*P23*P24*P25
P26_29 = P26*P27*P28*P29
P30_33 = P30*P31*P32*P33
P34_37 = P34*P35*P36*P37
P38_41 = P38*P39*P40*P41
P42_45 = P42*P43*P44*P45
P46_49 = P46*P47*P48*P49
P50_53 = P50*P51*P52*P53
P54_57 = P54*P55*P56*P57
P58_61 = P58*P59*P60*P61

X01_04 = G01 + G02 + P02*G03 + P02*P03*G04

X05_08 = G05 + G06 + P06*G07 + P06*P07*G08 X09_12 = G09 + G10 + P10*G11 + P10*P11*G12 X13_16 = G13 + G14 + P14*G15 + P14*P15*G16 X17_20 = G17 + G18 + P18*G19 + P18*P19*G20

1

Page 2 of 5

X21_24 = G21 + G22 + P22*G23 + P22*P23*G24

X25_28 = G25 + G26 + P26*G27 + P26*P27*G28 X29_32 = G29 + G30 + P30*G31 + P30*P31*G32 X33_36 = G33 + G34 + P34*G35 + P34*P35*G36 X37_40 = G37 + G38 + P38*G39 + P38*P39*G40 X41_44 = G41 + G42 + P42*G43 + P42*P43*G44 X45_48 = G45 + G46 + P46*G47 + P46*P47*G48 X49_54 = G49 + G50 + P50*G51 + P50*P51*G52 X53_56 = G53 + G54 + P54*G55 + P54*P55*G56 X57_60 = G57 + G58 + P58*G59 + P58*P59*G60 X61_Ci = G61 + G62 + P62*G63 + P62*P63*Cin

Third Level (prior art):

P02_17 = P02_05*P06_09*P10_13*P14_17

P06_21 = P06_09*P10_13*P14_17*P18_21 P10_25 = P10_13*P14_17*P18_21*P22_25 P14_29 = P14_17*P18_21*P22_25*P26_29 P18_33 = P18_21*P22_25*P26_29*P30_33 P22_37 = P22_25*P26_29*P30_33*P34_37 P26_41 = P26_29*P30_33*P34_37*P38_41 P30_45 = P30_33*P34_37*P38_41*P42_45 P34_49 = P34_37*P38_41*P42_45*P46_49 P38_53 = P38_41*P42_45*P46_49*P50_53 P42_57 = P42_45*P46_49*P50_53*P54_57 P46_61 = P46_49*P50_53*P54_57*P58_61

X01_16 = X01_04 + P02_05*X05_08 + P02_05*P06_09*X09_12 + P02_05*P06_09*P10_13*X13_16
X05_16 = X05_08 + P06_09*X09_12 + P06_09*P10_13*X13_16 X09_16 = X09_12 + P10_13*X13_16
X17_32 = X17_...