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 evaluation across contextual control, arithmetic, and decoding PDBFs with ABC/GT comparisons.

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 proposed methodology was evaluated on six Contextual PDBFs representing three distinct RTL contexts: a scalable one-hot arbiter-to-encoder family (8, 16, 32, and 64 requests), a BCD-adder correction block, and an instruction-decoder-to-ALU-control block. These examples complement the Vedic multiplier case study by demonstrating contextual partiality in control, arithmetic, and decoding structures.

Each PLA contains only the local input combinations reachable from the surrounding RTL context. The same PDBFs were synthesized with GT and, where available, two evaluated ABC flows (synt and transtoch). Multiple gate/level pairs are retained when different runs provide distinct area/depth tradeoffs.

Table I shows lower GT gate counts and logic depths than the available ABC results for all six evaluated Contextual PDBFs. The arbiter/encoder family provides a controlled scaling experiment: PI grows from 8 to 64 while the reachable care set grows only from 9 to 65 one-hot-or-zero combinations.

For Table II, gate reduction compares the minimum reported GT gate count with the minimum reported ABC gate count for the same PDBF; level reduction analogously compares the minimum reported logic depth. These minima may come from different synthesis variants and therefore summarize the best observed value for each metric rather than a single paired operating point. GT gate-count reductions range from 34.5% to 54.2%, while logic-depth reductions range from 40.0% to 66.7%.

The arbiter/encoder family makes the contextual restriction especially explicit: the nominal local input space grows as 2^n, while only n+1 combinations are reachable. The BCD correction and ALU-control examples provide additional arithmetic and decoding contexts with structurally restricted reachable domains.

The observed improvements are associated with optimization opportunities exposed by the extracted Contextual PDBFs. By preserving only reachable local input terms and treating all other terms as contextual don't-care conditions, Completion Optimization can select legal completions unavailable when the internal block is treated as fully specified over its entire nominal local input space.

These experiments are intended as evidence of feasibility rather than a universal performance claim. They show that contextual partiality can be constructed from ordinary RTL relationships and exploited across several structurally different examples using the same PDBF-oriented synthesis methodology.

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.

The extracted Contextual PDBFs were synthesized with GT and evaluated ABC flows on six examples spanning one-hot control, BCD arithmetic correction, and instruction decoding. In this dataset, GT reduced the best observed gate count by 34.5% to 54.2% and the best observed logic depth by 40.0% to 66.7% relative to the corresponding best available ABC metric.

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.