Extending Completion Optimization to RTL Designs Through Contextual Partially Defined Boolean Functions

I. Introduction

Logic synthesis traditionally transforms a Boolean specification into an efficient gate-level implementation. Recent work on Completion Optimization demonstrated that significant improvements in logic area and depth can be achieved by optimizing an incompletely specified Boolean function before logic synthesis.

First Optimize the Boolean Function. Then Optimize the Circuit.

Despite these promising results, conventional RTL designs are generally regarded as completely specified Boolean functions, whereas Completion Optimization operates on partially defined Boolean functions. Consequently, the applicability of Completion Optimization to ordinary RTL designs is not immediately apparent.

The central observation is that an internal RTL block is completely specified only when viewed in isolation. Within the complete design, many local input terms are unreachable because surrounding circuitry prevents them from occurring. Those terms cannot influence externally observable behavior.

This paper demonstrates the feasibility of extending Completion Optimization to ordinary RTL designs through contextual PDBF extraction. Rather than presenting a universal extraction algorithm, the objective is to establish a new research direction.

Principal contributions

• Identification of hidden contextual don't-care conditions in ordinary RTL designs.
• Definition of a Contextual PDBF based on reachable local input terms.
• A prototype PDBF extraction procedure.
• Classification of independent and correlated reachability.
• Integration with Completion Optimization and the PDBF Passport Library.
• Experimental evidence of substantial gate and logic-depth reductions.

II. Background

A. Partially Defined Boolean Functions

A PDBF specifies required output values only for a subset of its input terms. The remaining terms are unspecified, and each legal assignment produces a Fully Defined Boolean Function called a Legal Completion.

B. Completion Optimization

Completion Optimization searches the Opportunity Space of a PDBF and selects a Legal Completion according to an implementation objective. Conventional synthesis then optimizes the selected function's implementation.

C. PDBF Passport Library

A PDBF Passport records the identity and structure of a PDBF together with optimized implementations and measured characteristics such as gate count, logic levels, wire count, and fan-out. The library enables recognized PDBFs to reuse previously optimized implementations.

III. Hidden Don't-Care Conditions in RTL Designs

RTL blocks appear completely specified when considered in isolation. In a complete design, however, the local inputs of an internal block are generated by preceding logic, which may prevent many combinations from ever occurring.

Only a subset of the complete local input space is reachable. The remaining local input terms are never exercised and cannot affect primary outputs or architectural state under the considered operating context.

These unreachable local input terms are hidden contextual don't-care conditions.

IV. Contextual Partially Defined Boolean Functions

The resulting Contextual PDBF remains behaviorally equivalent to the original RTL block within the context of the complete design. It preserves every reachable local input/output relation while exposing optimization opportunities on unreachable terms.

V. PDBF Extraction Procedure

The Contextual PDBF may be obtained by observing the complete RTL design and recording the local input terms that occur during operation.

1. Select an RTL block for optimization.
2. Enumerate assignments of the primary inputs of the complete RTL design.
3. Evaluate the complete RTL design for each assignment.
4. Record all reachable local input terms of the selected block.
5. Remove duplicate local input terms.
6. Preserve unique reachable terms and treat all remaining local terms as unspecified.

The procedure states what must be determined without prescribing a universal implementation. Larger designs may use symbolic simulation, SAT, BDDs, formal reachability analysis, or other methods.

VI. Vedic Multiplier Case Study

The methodology was evaluated using a Vedic multiplier composed of four multiplier blocks, M0–M3, and three adder blocks, A0–A2. The multiplier blocks generate partial products, and the adders combine them to produce the final product.

Each adder was analyzed independently. For every primary-input assignment, the complete design was evaluated and the selected adder's local input term was recorded. Duplicate terms were removed to obtain the reachable local input set.

VII. Independent Reachability

Block A0 receives local inputs from multiplier blocks M2 and M3, which depend on disjoint subsets of the primary inputs. Their reachable output values can therefore vary independently.

|R(A0)| = |R(M2)| × |R(M3)| = 7 × 7 = 49.

The 49 reachable terms form the specified portion of A0's Contextual PDBF. All other local combinations are unreachable and become hidden contextual don't-care conditions.

VIII. Correlated Reachability

Block A1 receives inputs from A0 and M0. Although values at the A0 and M0 outputs may each be individually reachable, they cannot necessarily occur together because they share dependencies on the primary inputs.

The reachable terms must therefore be determined directly from the behavior of the complete RTL design. The same principle applies to A2, where additional computation stages further constrain the reachable local input space.

IX. Integration with Completion Optimization

After extraction, the Contextual PDBF is processed by the existing Completion Optimization framework. Completion Optimization assigns values to contextual don't-care terms and selects a Legal Completion according to the desired implementation objective.

The selected completion is synthesized or retrieved from the PDBF Passport Library. Conventional optimization may subsequently be applied.

First Discover the Contextual PDBF. Then Optimize the PDBF. Then Optimize the Circuit.

X. Experimental Results

The extracted Contextual PDBFs were optimized using Completion Optimization and implemented through the PDBF Passport Library. The resulting implementations were compared with area-oriented and faster ripple adders.

The principal source of improvement is not a new implementation-level optimization algorithm, but the discovery of contextual optimization opportunities hidden in conventional RTL representations.

XI. Discussion

The Contextual PDBF captures the effective Boolean behavior of an internal block without altering reachable behavior. Independent and Correlated Reachability provide an initial classification of contextual relationships.

The prototype extraction procedure demonstrates feasibility rather than a universal algorithm. More scalable realizations may use symbolic simulation, SAT solving, BDDs, formal verification, compositional reachability, abstraction, or hybrid analysis.

The PDBF Passport Library provides a path for reuse. Once a Contextual PDBF has been identified and optimized, its implementations and measured properties can be stored and reused.

A. Future Research Directions

• Symbolic and SAT-based extraction for large RTL designs.
• BDD and formal-reachability methods.
• Automatic identification of promising internal blocks.
• Hierarchical and compositional Contextual PDBFs.
• Approximate conservative reachability analysis.
• Automatic PDBF Passport matching and library growth.
• Integration into native and commercial EDA flows.
• Evaluation on industrial arithmetic, control, and datapath designs.
• Optimization objectives including area, delay, power, fan-out, and wiring.

XII. Conclusion

This paper introduced Contextual Partially Defined Boolean Functions for ordinary RTL designs. An internal RTL block may be completely specified in isolation while only a subset of its local input terms is reachable in the complete design.

The unreachable terms form hidden contextual don't-care conditions. A prototype extraction procedure applied to a Vedic multiplier introduced Independent and Correlated Reachability and showed how reachable local terms define the specified portion of a Contextual PDBF.

Measured arithmetic results demonstrated substantial gate-count and logic-depth reductions relative to two ripple-adder baselines.

First Discover the Contextual PDBF. Then Optimize the PDBF. Then Optimize the Circuit.

References

1. G. Toms, “Completion Optimization of Partially Defined Boolean Functions,” manuscript in preparation / submitted version.
2. R. K. Brayton and A. Mishchenko, “ABC: An Academic Industrial-Strength Verification Tool,” in Proc. CAV, 2010.
3. Reference on Vedic multiplier architectures to be added.
4. Reference on reachability and Boolean don't-care computation to be added.
5. Reference on SAT/BDD-based symbolic analysis to be added.