
CMUCS97134
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS97134
*PBHD: An Efficient Graph Representation for
Floating Point Circuit Verification
YirngAn Chen, Randal E. Bryant
May 1997
CMUCS97134.ps
Keywords: Binary moment diagram, *BMD, hybrid decision diagram,
HDD, K*BMD, multiplicative power binary hybrid diagram, *PBHD, arithmetic
circuit, IEEE Floating Point Standard, formal verification
*BMDs, HDDs, and K*BMDs provide compact representations for
functions which map Boolean vectors into integer values, but not
floating point values. In this paper, we propose a new data structure,
called Multiplicative Power Binary Hybrid Diagrams (*PBHDs), to provide
a compact representation for functions that map Boolean vectors into
integer or floating point values. The size of the graph to represent the
IEEE floating point encoding is linear with the word size. The
complexity of floating point multiplication grows linearly with the word
size. The complexity of floating point aaddition grows exponentially
with the size of the exponent part, but linearly with the size of the
mantissa part. We applied *PBHDs to verify integer multipliers and
floating point multipliers before the rounding stage, based on a
hierarchical verification approach. For integer multipliers, our results
are at least 6 times faster than *BMD's. Previous attempts at verifying
floating point multipliers required manual intervention. We verified
floating point multipliers before the rounding stage automatically.
22 pages
