Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

A Family of Variable-Precision Interval Arithmetic Processors

Published: 01 May 2000 Publication History

Abstract

Traditional computer systems often suffer from roundoff error and catastrophic cancellation in floating point computations. These systems produce apparently high precision results with little or no indication of the accuracy. This paper presents hardware designs, arithmetic algorithms, and software support for a family of variable-precision, interval arithmetic processors. These processors give the programmer the ability to detect and, if desired, to correct implicit errors in finite precision numerical computations. They also provide the ability to solve problems that cannot be solved efficiently using traditional floating point computations. Execution time estimates indicate that these processors are two to three orders of magnitude faster than software packages that provide similar functionality.

References

[1]
A. Yu, “The Future of Microprocessors,” IEEE Micro, vol. 16, no. 6, pp. 46-53, Dec. 1996.
[2]
M. Tremblay and J.M. O'Connor, “UltraSparc I: A Four-Issue Processor Supporting Multimedia,” IEEE Micro, vol. 16, no. 2, pp. 42-50, Apr. 1996.
[3]
A. Peleg and U. Weiser, “MMX Technology Extension to the Intel Architecture,” IEEE Micro, vol. 16, no. 4, pp. 42-50, Aug. 1996.
[4]
G. Bohlender, “What Do We Need Beyond IEEE Arithmetic?” Computer Arithmetic and Self-Validating Numerical Methods, C. Ullrich, ed., pp. 1-32, Boston: Academic Press, 1990.
[5]
D. Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic,” Computing Surveys, vol. 23, no. 1, pp. 5-48, 1991.
[6]
R.E. Moore, Interval Analysis. Englewood Cliffs, N.J.: Prentice Hall, 1966.
[7]
G. Alefeld and J. Herzberger, Introduction to Interval Computations. New York: Academic Press, 1983.
[8]
W. Kramer, “A Priori Worst Case Error Bounds for Floating-Point Computations,” IEEE Trans. Computers, vol. 47, no. 7, pp. 750-756, July 1997.
[9]
G.F. Corliss, “Industrial Applications of Interval Techniques,” Computer Arithmetic and Self-Validating Numerical Methods, C. Ullrich, ed., pp. 91-113, Boston: Academic Press, 1990.
[10]
R. Hammer M. Hocks U. Kulisch and D. Ratz, C++ Toolbox for Verified Computing. Berlin: Springer-Verlag, 1995.
[11]
R.E. Moore, “Computing to Arbitrary Accuracy,” Computational and Applied Mathematics, I: Algorithms and Theory, C. Brezinski and U. Kulisch, eds., pp. 327-336, Amsterdam: North-Holland, 1992.
[12]
R.B. Kearfott and V. Kreinovich, “Applications of Interval Computations: An Introduction,” Applications of Interval Computations, R.B. Kearfott and V. Kreinovich, eds., pp. 1-22, Boston: Kluwer Academic, 1996.
[13]
M.J. Schulte and E.E. Swartzlander Jr., “Software and Hardware Techniques for Accurate, Self-Validating Arithmetic,” Applications of Interval Computations, R.B. Kearfott and V. Kreinovich, eds., pp. 381-404, Boston: Kluwer Academic, 1996.
[14]
J.S. Ely, “The VPI Software Package for Variable Precision Interval Arithmetic,” Interval Computations, vol. 2, no. 2, pp. 135-153, 1993.
[15]
O. Knuppel, “PROFIL/BIAS—A Fast Interval Library,” Computing, vol. 53, nos. 3-4, pp. 277-288, 1994.
[16]
M.J. Schulte A. Akkas V. Zelov and J.C. Burley, “The Interval-Enhanced GNU Fortran Compiler,” Reliable Computing, vol. 5, no. 3, pp. 311-322, Aug. 1999.
[17]
R. Klatte U. Kulisch M. Neaga D. Ratz and C. Ullrich, PASCAL-XSC: Language Reference with Examples. Berlin: Springer-Verlag, 1991.
[18]
O. Aberth, “Precise Scientific Computation with a Microprocessor,” IEEE Trans. Computers, vol. 33, no. 8, pp. 685-690, Aug. 1984.
[19]
E. Kinoshita and L. Ki-Ja, “A Residue Arithmetic Extension for Reliable Scientific Computing,” IEEE Trans. Computers, vol. 46, no. 2, pp. 129-138, Feb. 1997.
[20]
A. Knofel, “Fast Hardware Units for the Computation of Accurate Dot Products,” Proc. 10th Symp. Computer Arithmetic, pp. 70-75, 1991.
[21]
C. Baumhof, “A New VLSI Vector Arithmetic Coprocessor for the PC,” Proc. 12th Symp. Computer Arithmetic, pp. 210-215, 1991.
[22]
P. Korenerup and D.W. Matula, “Finite Precision Rational Arithmetic: An Arithmetic Unit,” IEEE Trans. Computers, vol. 32, no. 7, pp. 378-388, July 1983.
[23]
T.M. Carter, “Cascade: Hardware for High/Variable Precision Arithmetic,” Proc. Ninth Symp. Computer Arithmetic, pp. 184-191, 1989.
[24]
M.S. Cohen T.E. Hull and V.C. Hamacher, “CADAC: A Controlled-Precision Decimal Arithmetic Unit,” IEEE Trans. Computers, vol. 32, no. 4, pp. 370-377, Apr. 1983.
[25]
J.E Stine and M.J. Schulte, “A Combined Interval and Floating-Point Divider,” Conf. Record 32nd Asilomar Conf. Signals, Systems, and Computers, pp. 218-222, 1998.
[26]
J.E Stine and M.J Schulte, “A Combined Interval and Floating-Point Multiplier,” Proc. Eighth Great Lakes Symp. VLSI, pp. 208-215, 1998.
[27]
M.J. Schulte and E.E. Swartzlander Jr., “A Software Interface and Hardware Design for Variable-Precision Interval Arithmetic,” Reliable Computing, vol. 1, no. 3, pp. 325-342, 1995.
[28]
M.J. Schulte and E.E. Swartzlander Jr., “A Hardware Design and Arithmetic Algorithms for a Variable-Precision, Interval Arithmetic Coprocessor,” Proc. 12th Symp. Computer Arithmetic, pp. 163-171, 1995.
[29]
M.J. Schulte, “A Variable-Precision, Interval Arithmetic Processor,” doctoral dissertation, Dept. of Electrical and Computer Eng., Univ. of Texas at Austin, 1996.
[30]
IEEE Standard 754 for Binary Floating Point Arithmetic, Am. Nat'l Standards Inst., IEEE, 1995.
[31]
LSI Logic 1. 0 Micron Cell-Based Products Databook, LSI Logic Corporation, Milpitas, Calif., 1991.
[32]
K.C. Bickerstaff M.J. Schulte and E.E. Swartzlander Jr., “Reduced Area Multipliers,” Proc. 1993 Int'l Conf. Application Specific Array Processors, pp. 478-489, 1993.
[33]
K.C. Bickerstaff M.J. Schulte and E.E. Swartzlander Jr., “Parallel Reduced Area Multipliers,” J. VLSI Signal Processing, vol. 9, no. 3, pp. 181-192, Apr. 1995.
[34]
D.W. Matula, “Design of a Highly Parallel IEEE Standard Floating Point Unit: The Cyrix 83D87 Coprocessor,” Proc. Second IEEE Symp. Parallel and Distributed Processing, p. 334, 1990.
[35]
E. Hansen, Global Optimization Using Interval Analysis. New York: Marcel Dekker, 1992.

Cited By

View all

Index Terms

  1. A Family of Variable-Precision Interval Arithmetic Processors

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image IEEE Transactions on Computers
    IEEE Transactions on Computers  Volume 49, Issue 5
    May 2000
    141 pages
    ISSN:0018-9340
    Issue’s Table of Contents

    Publisher

    IEEE Computer Society

    United States

    Publication History

    Published: 01 May 2000

    Author Tags

    1. Processors
    2. accuracy.
    3. computer arithmetic
    4. hardware designs
    5. interval arithmetic
    6. roundoff error
    7. variable-precision arithmetic

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Xvpfloat: RISC-V ISA Extension for Variable Extended Precision Floating Point ComputationIEEE Transactions on Computers10.1109/TC.2024.338396473:7(1683-1697)Online publication date: 2-Apr-2024
    • (2019)SMURFProceedings of the Conference for Next Generation Arithmetic 201910.1145/3316279.3316280(1-8)Online publication date: 13-Mar-2019
    • (2018)Real-Time Query Enabled by Variable Precision in AstronomyBig Scientific Data Management10.1007/978-3-030-28061-1_9(78-85)Online publication date: 30-Nov-2018
    • (2017)Mathematical model and implementation of rational processingJournal of Computational and Applied Mathematics10.1016/j.cam.2016.05.001309:C(575-586)Online publication date: 1-Jan-2017
    • (2015)MCALIBACM Transactions on Programming Languages and Systems10.1145/266507337:2(1-25)Online publication date: 16-Apr-2015
    • (2014)Recycled error bitsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC.2014.15(117-127)Online publication date: 16-Nov-2014
    • (2013)FPGA implementation of an exact dot product and its application in variable-precision floating-point arithmeticThe Journal of Supercomputing10.1007/s11227-012-0860-064:2(580-605)Online publication date: 1-May-2013
    • (2011)FPGA implementation of variable-precision floating-point arithmeticProceedings of the 9th international conference on Advanced parallel processing technologies10.5555/2042522.2042532(127-141)Online publication date: 26-Sep-2011
    • (2011)The Krawczyk algorithmProceedings of the 7th international conference on Reconfigurable computing: architectures, tools and applications10.5555/1987535.1987574(287-295)Online publication date: 23-Mar-2011
    • (2011)A monte-carlo floating-point unit for self-validating arithmeticProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950453(199-208)Online publication date: 27-Feb-2011
    • Show More Cited By

    View Options

    View options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media