PaperlayerView exact revision on arXiv

Source-linked AI summary

A Compression Tree Generation Method for High Performance VLSI Datapaths

Christophe Giacomotto

arXiv:2610.02228v1cs.AR

TL;DR

Compression trees have typically been treated as parts of standalone multipliers, while growing fused arithmetic datapaths create a broader many-addition problem. This paper generates trees from weighted bit heaps using delay-aware CSA3:2 reduction and a Dadda-style topology. On evaluated Radix-4 Booth multipliers, the approach reports lower delay and reduced estimated logic volume than other strategies.

  • Problem

    Compression trees are traditionally presented as standalone multiplier components, although growing MAC density brings fused sums of products into datapaths.

    Source: §I · p. 1

  • Method

    The generator represents bits by significance and relative arrival time, then reorders them through delay-aware CSA3:2 reduction with Dadda-style maximum bandwidth.

    Source: §I · p. 1

  • Results

    Approximately 8%–25% estimated logic-volume reduction was reported, and evaluated Radix-4 Booth trees consistently had lower delay than other strategies.

    Source: §IV · p. 4, §VIII · p. 7

  • Takeaways & Limitations

    Weighted bit-heap generation provides a simple, versatile basis for comparing candidate trees and guiding production datapath generation.

    Source: §VIII · p. 7

    The model is a logical-pressure metric, not a replacement for detailed physical implementation analysis.

    Source: §VIII · p. 7

Abstract

from arXiv · show

Compression trees have been historically a key component of several arithmetic units, most notably multipliers. The latter have been for the most part standalone units and in common situations synthesis tools can generate very close to optimal solutions. With large matrix multiply structures taking more of a central role in the compute industry, the need for a better understanding of these compression trees is apparent. Furthermore, the boundary of its usage needs to be redefined: dot products, polynomial fitting of non-linear operators, are all sums of products. And since products are sums of partial products, in the end, we are just adding many things together as bit heaps; i.e. the fundamental role of a compression tree. Therefore, we must see them as more than just a component of a multiplier. This paper presents a delay-aware compression-tree methodology based on a weighted bit heap. Each bit is described by its significance and relative arrival time, and the generator uses technology-independent normalized delay units to estimate Boolean logical pressure. By exploiting the commutativity of addition within each column, the method reorders bits across reduction stages and uses a Dadda-style maximum-bandwidth topology with flexible CSA3:2 operators. For Radix-4 Booth multipliers from 11 to 64 bits, the resulting trees show lower modeled delay and estimated logic volume than the evaluated Wallace-style maximum-compression trees. Fused four-way integer dot products further demonstrate how the same representation can evaluate the cost of microarchitectural constraints, such as preserving individual product redundant formats. These results show that weighted bit-heap generation provides a practical technology-independent basis for exploring compression trees beyond standalone multiplication.

I. INTRODUCTION

Compression trees are increasingly relevant beyond standalone multipliers as datapaths combine many products and additions. This paper introduces a delay-aware generator based on weighted bit heaps and evaluates it on multipliers and fused dot products.

I. INTRODUCTION

  • Fused datapaths can combine partial products, shared redundant formats, and differently timed inputs, making isolated-multiplier trees unsuitable for some complete datapaths.Microarchitectural requirements may also require individual products or intermediate redundant formats to remain available.Source: §I · p. 1
  • A weighted bit heap represents each bit by its significance and relative arrival time, independently of its originating arithmetic operation.This supports compression-tree generation for fused arithmetic structures, not only standalone multipliers.Source: §I · p. 1
  • The generator reorders commutative bits using a delay-aware CSA3:2 methodology and a Dadda-style maximum-bandwidth topology.The evaluation compares modeled delay and estimated logic volume on Radix-4 Booth multipliers and examines costs of preserving intermediate redundant formats.Source: §I · p. 1
  • The technology-independent model is intended for early design-space exploration, not as a replacement for technology-specific characterization and physical implementation.The paper positions it as a compact way to compare candidate structures before synthesis, placement, and routing.Source: §I · p. 1

II. LOGICAL EFFORT

The paper estimates logical delay through normalized Boolean pressure rather than technology-specific cell timing. It applies this model to CSA3:2 paths while tracking carry-path timing.

II. LOGICAL EFFORT

  • The delay model uses normalized Boolean logical pressure because technology-dependent Logical Effort estimation would be counterproductive for this work.The paper assumes the Boolean expressions in equations (1) and (2) typically yield similar delays in dense, low-fanout datapaths.Source: §II · p. 2
  • A “delay unit” is Boolean logical term pressure normalized to equations (1) or (2), which are assumed equivalent for normalization.The unit is not standard-cell delay characterization or a physical stage breakdown.Source: §II · p. 2
  • CSA3:2 grouping must track the C input because its path to Carry affects logical depth relative to the Sum path.The passage notes that the C-to-Carry path has a floating timing relation to Sum when the three-way XOR is specified as two stages.Source: §II · p. 2

III. TREE TOPOLOGIES

The section contrasts Wallace and Dadda reduction strategies through how much bit-heap bandwidth they retain between stages. It motivates flexible CSA3:2 reduction while noting conditions that can favor narrower stage bandwidth.

III. TREE TOPOLOGIES

  • Tree stage count depends on the 3:2 counter’s reduction capability, tree height, and bit-heap shape; narrow heaps may not support the final iteration.Carries offset into adjacent columns and can prevent that iteration.Source: §III · p. 2
  • A Wallace tree reduces the maximum number of bits in parallel at each stage, whereas a Dadda tree reduces only the minimum required amount.The resulting extremes minimize and retain stage-to-stage bandwidth, respectively.Source: §III · p. 2
  • Using only flexible CSA3:2 counters with Dadda-style maximum bandwidth is reported as best under the proposed delay model.The passage contrasts this approach with hybrid trees using CSA2:2 and CSA4:2 operators.Source: §III · p. 3
  • Reducing bandwidth can be preferable when pipelining for tight frequency or excessive glitching, because pipeline-register bit counts can raise area and power costs.The passage says most compression trees nowadays fit in one cycle, even for 64-bit multipliers.Source: §III · p. 3

IV. GENERATOR METHODOLOGY

The generator represents additions as weighted bit heaps and uses delay-aware CSA3:2 reductions that preserve bandwidth between stages. Across evaluated Radix-4 Booth multipliers, its trees are systematically faster than Wallace trees, with estimated logic-volume reductions also reported.

IV. GENERATOR METHODOLOGY

  • A standalone tree generator is intended to accommodate datapaths with shared operations, multiple arrival times, and microarchitectural constraints.Such constraints can require individual products or intermediate redundant formats to remain available.Source: §IV · p. 3
  • The bit-heap input records each bit’s position and relative arrival time, allowing the generator to form a tree without knowing the originating operation.In the example, all bits arrive at the earliest time and are labeled 0.Source: §IV · p. 3
  • Preserving maximum bandwidth lets early-arriving bits from shorter columns feed later CSA3:2 inputs, reducing logical pressure on critical paths.In the example, maximum compression yields 6 delay units, while bandwidth retention produces a faster result.Source: Figure 3 · p. 3, §IV · p. 3
  • Without the 7th partial product, bandwidth-retaining trees still have faster or less critical paths than Wallace trees, although both have a 5-unit worst delay.The Dadda tree limits the delay cost of the extra bit even when it must enter the tallest section.Source: Figure 4 · p. 4, §IV · p. 4
  • Across Radix-4 Booth multipliers from 11b to 64b, Dadda trees are systematically better than Wallace trees in modeled delay.The delay profile remains consistent across tree topologies and multiplier sizes.Source: Figure 5 · p. 4, §IV · p. 4
  • Estimated logic-volume reduction ranges from approximately 8% to 25% over the plotted multiplier sizes.Production EDA flows typically show far fewer benefits than this estimate.Source: Figure 6 · p. 4, §IV · p. 4

V. BEYOND THE LONE MULTIPLICATION

The section extends compression-tree analysis to fused dot products and microarchitectural constraints such as preserving individual product redundant formats. It compares fully fused and preserved-product implementations across delay and area.

V. BEYOND THE LONE MULTIPLICATION

  • The authors use a typical integer dot-product operator, with A and B vectors of D elements, to illustrate compression-tree complexity, noting that compression trees and CPAs are functionally decoupled in practice.They also vary Radix-4 Booth multipliers from 8b to 16b and examine dot-product depth of 8 ways.Source: §V · pp. 4–5
  • The compared Fig. 7 strategies are fully fused product summation or preserving each product’s RDF for sharing with less timing-critical datapaths.Straightforward RTL may cause synthesis to insert intermediate CPAs before the final sum, depending on the tool, library, and coding style.Source: §V · pp. 4–5
  • Fully fusing all partial products prevents practical extraction of individual products, while preserving RDFs lets a dependent tree use their input delay profiles.The preserved products must include sign-propagation logical 1s, causing moderate delay overhead on upper RDF bits.Source: §V · p. 5
  • The delay of the lower half of the tree is unaffected by extracting individual multiplier RDFs, regardless of multiplier size or dot-product depth.This result applies to the preserved-product constraint.Source: §V · p. 5, Figure 9 · p. 5
  • The Fig. 8 overhead for {D;N}={4;8} remains proportional and consistent across the tried D and N dimensions.The comparison concerns two dot-product summation microarchitectures.Source: §V · p. 5, Figure 8 · p. 5
  • Increasing dot-product depth from D=4 to 8 compounds area overhead linearly, producing a proportional area-reduction offset across multiplier sizes.As multiplier width grows, the tree widens and area-reduction returns diminish.Source: §V · p. 6, Figure 10 · p. 6

VI. THE LATE ACCUMULATE CASE

The section examines how a compression tree handles an accumulator that arrives after multiplier partial products. It finds that absorption is limited, and that late inputs can slow the tree’s critical path.

VI. THE LATE ACCUMULATE CASE

  • An accumulator arriving no later than Booth partial products should enter the tree at time 0; if it arrives after the multiplier RDF profile, the accumulator is critical.In that latter case, compression-tree timing is irrelevant.Source: §VI · p. 6
  • An intermediate late arrival can force a vector into a reduction stage, making the next-stage sums and carries slower and propagating the slowest path at 2x rate.Parallel trees can absorb some delay before adding the vector at the end becomes preferable.Source: §VI · p. 6
  • For a 16x16 multiplier with a 32b accumulator, the absorption limit is 2 delay units compared with adding the accumulator after a CSA3:2 row.Here, TNS is the cumulative arrival-time difference and WNS the largest difference, not their traditional clock-referenced meanings.Source: §VI · p. 6, Figure 11 · p. 6
  • Across multiplier sizes, late-accumulator absorption maxes out at 3 delay units for the critical path, and smaller multipliers accommodate less.A slow input can quickly have a very negative impact on overall tree performance.Source: §VI · p. 6, Figure 12 · p. 6

VII. NEXT STEP

The next step is to include switching activity alongside delay when weighting a bit heap. The section outlines ways to trade timing against activity and energy.

VII. NEXT STEP

  • Switching activity can be tracked as a second weight dimension alongside delay in a bit heap.Using delay alone to weight the heap can still be sub-optimal.Source: §VII · p. 6
  • Activity can be a secondary grouping criterion by reordering activity nodes within delay-equivalent groups at no timing cost.This leaves the delay-aware grouping already selected by the heuristic intact.Source: §VII · p. 7
  • Increasing logical depth on some paths can trade delay for energy, but higher depth typically increases energy through higher logical effort.This design-space problem involves technology-node and physical-design awareness.Source: §VII · p. 7

VIII. CONCLUSION

Compression trees can serve as general-purpose bit-heap reduction structures for datapaths combining products, accumulations, and redundant representations. The weighted-bit-heap method supports exploring these organizations while its technology-independent delay model remains a logical-pressure metric, not a substitute for physical analysis.

VIII. CONCLUSION

  • The method consistently produced lower delay and reduced estimated logic volume than other strategies for the evaluated Radix-4 Booth multipliers.Its Dadda-style organization also absorbed additional bits or uneven arrival times with less penalty on the critical path.Source: §VIII · p. 7
  • The generator describes relevant bits by position and relative arrival time, allowing compression trees to be evaluated independently of the surrounding arithmetic operation.It can evaluate fused dot products and shared redundant representations, and quantify costs such as keeping individual intermediate products available.Source: §VIII · p. 7
  • The technology-independent delay model is a logical-pressure metric, not a replacement for detailed physical implementation analysis.Future work will add switching activity for energy-aware optimization while retaining delay as the primary criterion.Source: §VIII · p. 7
Loading 2610.02228v1…