On the systematic creation of faithfully rounded truncated multipliers and arrays
File(s)TC-2012-07-0520.R2_Drane-main.pdf (408.66 KB)
Accepted version
Author(s)
Drane, Theo A
Rose, Thomas M
Constantinides, George A
Type
Journal Article
Abstract
Often, when performing fixed-point multiplication, it is sufficient to return a faithfully rounded result, i.e., the machine representable number either immediately above or below the arbitrary precision result, if the latter is not exactly representable. Compared to correctly rounded multipliers, i.e., those returning the nearest machine representable number, faithfully rounded multipliers use considerably less silicon area, typically by implementing a truncation scheme within the partial product array. A number of such heuristically inspired schemes exist in the literature, however their use in industrial practice is hampered by the absence of verification, and exhaustive simulation is typically infeasible, e.g., a 32 bit multiplier requires 2 64 simulations. We present three truncated multiplier schemes which subsume the majority of existing schemes and derive both closed form necessary and sufficient conditions for faithful rounding. For two of the schemes we provide closed form expressions for the bit vectors giving rise to the worst-case error and the probability of encountering these inputs during Monte-Carlo simulation. From these expressions, we show how HDL code can be created that performs correct-by-construction faithfully rounded multiplication. We also present a method for truncating an arbitrary array while maintaining faithful rounding, creating two novel truncated multiplier schemes in the process.
Date Issued
2014-10-01
Date Acceptance
2013-06-05
Citation
IEEE Transactions on Computers, 2014, 63 (10), pp.2513-2525
ISSN
0018-9340
Publisher
Institute of Electrical and Electronics Engineers
Start Page
2513
End Page
2525
Journal / Book Title
IEEE Transactions on Computers
Volume
63
Issue
10
Copyright Statement
© 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000343886800011&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Engineering, Electrical & Electronic
Computer Science
Engineering
Data-path design
parallel circuits
high-speed arithmetic
worst-case analysis
COMPENSATION
REDUCTION
Publication Status
Published