Misplaced Pages

Unum (number format): Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 12:56, 10 July 2018 editMatthiaspaul (talk | contribs)Autopatrolled, Extended confirmed users, Page movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors137,492 edits →Implementations: removed stray text← Previous edit Revision as of 12:56, 10 July 2018 edit undoMatthiaspaul (talk | contribs)Autopatrolled, Extended confirmed users, Page movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors137,492 edits →Quire: formatting per MOSNext edit →
Line 77: Line 77:
=== Quire === === Quire ===


Quire is one of the most useful feature of posits. It is a special data type that will give posits "near-infinity" number of bits to accumulate dot products. It is based on the work of Kulisch and Miranker<ref name="kulish_1986"/>. Quire is one of the most useful feature of posits. It is a special data type that will give posits "near-infinity" number of bits to accumulate dot products. It is based on the work of Kulisch and Miranker.<ref name="kulish_1986"/>


=== Implementations === === Implementations ===

Revision as of 12:56, 10 July 2018

The unum (universal number) format is a format similar to floating point, proposed by John Gustafson as an alternative to the now ubiquitous IEEE 754 arithmetic. The proposal and justification are explained in his book The End of Error. That version of unum is now officially known as Type I unum. Gustafson had since invented two additional types of unum, Type II and Type III in late 2016. Type III unum is also known as posits and valids. It is the type that can serve as a replacement for IEEE 754 floats, for programs that are not based on IEEE 754 features. Valids are the interval arithmetic version of posits. Details of valids have yet to be officially articulated by Gustafson.

Type I and Type II Unum

The two defining features of the type I unum format (while type II unum is different) are:

  • a variable-width storage format for both the significand and exponent, and
  • a u-bit, which determines whether the unum corresponds to an exact number (u=0), or an interval between consecutive exact unums (u=1). In this way, the unums cover the entire extended real number line .

For performing computation with the format, Gustafson proposes using interval arithmetic with a pair of unums, what he calls a ubound, providing the guarantee that the resulting interval contains the exact solution.

Unum implementations have been explored in Julia. including type II unum (or at least a modified version of his new proposal). Unum had been explored in MATLAB. Also, Roger Stokes has a learning lab for type II unum in J language.

William Kahan and John Gustafson discussed unums at the Arith23 conference.

Type III Unum - Posit

In February 2017, Gustafson officially introduced unum type III, posits and valids. Posit is a hardware-friendly version of unum where difficulties faced in the original type I unum due to its variable size are resolved. Similar size posits when compared to floats offer a bigger dynamic range and more fraction bits for accuracy. In an independent study, Lindstrom, Lloyd and Hittinger from Lawrence Livermore National Laboratory confirmed that posits out-perform floats in accuracy. Posits have particularly superior accuracy in the range near one, where most computations occur. This makes it very attractive to the current trend in deep learning to minimise the number of bits used. It potentially helps any applications to achieve a speedup by enabling the use of fewer bits (since it has more fraction bits for accuracy) thus reducing network and memory bandwidth, and power requirements, and bring us one step closer to exascale.

Posits have a different format than IEEE 754 floats. It consists of four parts, sign, regime, exponential and fraction (also known as significand/mantissa). For a n-bit posit, regime can be of length 2 to (n−1). The format of regime is such that it is a repetition of a same-sign bit and terminated by a different-sign bit.

Example 1:

Example 1 Example 2
000000000000001 1110


Example 1 shows a regime with 14 same-sign bit (bit 0), terminated by a different-sign bit (bit 1). As there are 14 same-sign bits, the runlength of the regime is 14.

Example 2 shows a regime with 3 same-sign bit (bit 1), terminated by a different-sign bit (bit 0). As there are 3 same-sign bits, the runlength of the regime is 3.

Sign, exponential and fraction bits are very similar to IEEE 754. In the case of posits, it is possible to have no exponential and fraction bits, i.e. the entire posit consists of only sign and regime bits. Example 3 shows the longest possible regime runlength for a 16-bit posit, where the regime terminating bit, exponential bit and fraction bits are beyond the length of the size of the posit. Example 4 illustrates the shortest possible runlength of 1 for a 16-bit posit with one exponential bit (bit value = 1) and 12 fraction bits (bit value = 100000000001).


Example 3: Regime runlength = 15 Example 4: Regime runlength = 1
0111111111111111 0101100000000001


The recommended posit sizes and corresponding exponential bits and quire sizes:

Posit size (bits) Number of exponential bits Quire size (bits)
8 0 32
16 1 128
32 2 512
64 3 2048

Note: 32-bit posit is expected to be sufficient to solve almost all classes of applications.

Quire

Quire is one of the most useful feature of posits. It is a special data type that will give posits "near-infinity" number of bits to accumulate dot products. It is based on the work of Kulisch and Miranker.

Implementations

There are several software and hardware implementations of posits from the community. The earliest software implementation in Julia came from Yonemoto. A C++ version with support for any posit sizes combined with any number of exponential bits is also provided. A fast implementation in C, SoftPosit, provided by the NGA research team based on Berkeley SoftFloat is the latest addition to the available software implementations.

SoftPosit

SoftPosit is a software implementation of posits that is based on Berkeley SoftFloat. This allows software comparison between posits and floats. It currently supports

  • Add
  • Subtract
  • Multiply
  • Divide
  • Fused-multiply-add
  • Fused-dot-product (with quire)
  • Square root
  • Convert posit to signed and unsigned integer
  • Convert signed and unsigned integer to posit
  • Convert posit to another posit size
  • Less than, equal, less than equal comparison
  • Round to nearest integer

Helper functions

  • convert double to posit
  • convert posit to double
  • cast unsigned integer to posit

for 16-bit posits with one exponential bit and 8-bit posit with zero exponential bit. Support for 32-bit posits is pending correctness verification. Currently it supports x86_64 systems. It has been tested on GNU gcc (SUSE Linux) 4.8.5 Apple LLVM version 9.1.0 (clang-902.0.39.2).

Examples

Add with posit8_t 

#include "softposit.h"
int main (int argc, char *argv){
    posit8_t pA, pB, pZ;
    pA = castP8(0xF2);
    pB = castP8(0x23);
    pZ = p8_add(pA, pB);
    //To check answer by converting it to double
    double dZ = convertP8ToDouble(pZ);
    printf("dZ: %.15f\n", dZ);
    //To print result in binary (warning: non-portable code)
    uint8_t uiZ = castUI8(pZ);
    printBinary((uint64_t*)&uiZ, 8);
    return 0;
}

Fused dot product with quire16_t 

//Convert double to posit
posit16_t pA = convertDoubleToP16(1.02783203125 );
posit16_t pB = convertDoubleToP16(0.987060546875);
posit16_t pC = convertDoubleToP16(0.4998779296875);
posit16_t pD = convertDoubleToP16(0.8797607421875);
quire16_t qZ;
//Set quire to 0
qZ = q16_clr(qZ);
//accumulate products without roundings
qZ = q16_fdp_add(qZ, pA, pB);
qZ = q16_fdp_add(qZ, pC, pD);
//Convert back to posit
posit16_t pZ = q16_to_p16(qZ);
//To check answer
double dZ = convertP16ToDouble(pZ);

Critique

William Kahan, the principal architect of IEEE 754-1985 criticizes type I unums on the following grounds (some are addressed in type II and type III standards):

  • The description of unums sidesteps using calculus for solving physics problems.
  • Unums can be expensive in terms of time and power consumption.
  • Each computation in unum space is likely to change the bit length of the structure. This requires either unpacking them into a fixed-size space, or data allocation, deallocation, and garbage collection during unum operations, similar to the issues for dealing with variable-length records in mass storage.
  • Unums provide only two kinds of numerical exception, quiet and signaling NaN (Not-a-Number).
  • Unum computation may deliver overly loose bounds from the selection of an algebraically correct but numerically unstable algorithm.
  • The costs and benefits of unum over short precision floating point for problems requiring low precision are not obvious.
  • Solving differential equations and evaluating integrals with unums guarantee correct answers but may not be as fast as methods that usually work.

See also

References

  1. Tichy, Walter F. (April 2016). "The End of (Numeric) Error: An interview with John L. Gustafson". Ubiquity - Information everywhere. 2016 (April). Association for Computing Machinery (ACM): 1–14. doi:10.1145/2913029. Archived from the original on 2016-07-10. Retrieved 2016-07-10. JG: The word "unum" is short for "universal number," the same way the word "bit" is short for "binary digit." {{cite journal}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  2. Gustafson, John L. (2016-02-04) . The End of Error: Unum Computing. Chapman & Hall / CRC Computational Science. Vol. 24 (2nd corrected printing, 1st ed.). CRC Press. ISBN 978-1-4822-3986-7. Retrieved 2016-05-30.
  3. ^ Gustafson, John L.; Yonemoto, Isaac (2017). "Beating Floating Point at its Own Game: Posit Arithmetic". Supercomputing Frontiers and Innovations. 4 (2). Publishing Center of South Ural State University, Chelyabinsk, Russia. doi:10.14529/jsfi170206. Archived from the original on 2017-11-04. Retrieved 2017-11-04. {{cite journal}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  4. ^ J. Gustafson and I. Yonemoto. (2017, Feb) Beyond Floating Point: Next Generation Computer Arithmetic. . Available: https://www.youtube.com/watch?v=aP0Y1uAA-2Y
  5. ^ Gustafson, John L. (2017-10-10). "Posit Arithmetic" (PDF). Archived from the original (PDF) on 2017-11-04. Retrieved 2017-11-04. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch; 2017-11-05 suggested (help); Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  6. Tichy, Walter (September 2016). "Unums 2.0: An Interview with John L. Gustafson". Ubiquity.ACM.org. Retrieved 2017-01-30. I started out calling them "unums 2.0," which seemed to be as good a name for the concept as any, but it is really not a "latest release" so much as it is an alternative.
  7. Byrne, Simon (2016-03-29). "Implementing Unums in Julia". Retrieved 2016-05-30.
  8. "Unum arithmetic in Julia: Unums.jl". Retrieved 2016-05-30.
  9. "Julia Implementation of Unums: README". Retrieved 2016-05-30.
  10. "Unum (Universal Number) types and operations: Unums". Retrieved 2016-05-30.
  11. "jwmerrill/Pnums.jl". Github.com. Retrieved 2017-01-30.
  12. Ingole, Deepak; Kvasnica, Michal; De Silva, Himeshi; Gustafson, John L. "Reducing Memory Footprints in Explicit Model Predictive Control using Universal Numbers. Submitted to the IFAC World Congress 2017". Retrieved 2016-11-15. {{cite web}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  13. Ingole, Deepak; Kvasnica, Michal; De Silva, Himeshi; Gustafson, John L. "MATLAB Prototype of unum (munum)". Retrieved 2016-11-15. {{cite web}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  14. "Program: Special Session: The Great Debate: John Gustafson and William Kahan". Arith23: 23rd IEEE Symposium on Computer Arithmetic. Silicon Valley, USA. 2016-07-12. Archived from the original on 2016-05-30. Retrieved 2016-05-30. {{cite web}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  15. Gustafson, John L.; Kahan, William M. (2016-07-12). The Great Debate @ARITH23: John Gustafson and William Kahan (1:34:41) (video). Retrieved 2016-07-20.
  16. ^ Kahan, William M. (2016-07-16) . "A Critique of John L. Gustafson's THE END of ERROR — Unum Computation and his A Radical Approach to Computation with Real Numbers" (PDF). Santa Clara, CA, USA: IEEE Symposium on Computer Arithmetic, ARITH 23. Archived from the original (PDF) on 2016-07-25. Retrieved 2016-07-25. {{cite web}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)
  17. Gustafson, John L. (2016-07-12). ""The Great Debate": Unum arithmetic position paper" (PDF). Santa Clara, CA, USA: IEEE Symposium on Computer Arithmetic, ARITH 23. Retrieved 2016-07-20.
  18. ^ P. Lindstrom, S. Lloyd, and J. Hittinger, “Universal Coding of the Reals: Alternatives to IEEE Floating Point,” in Conference for Next Generation Arithmetic. ACM, 2018.
  19. U. Kulisch and W. Miranker, “The Arithmetic of the Digital Computer: A New Approach,” SIAM Rev., vol. 28, no. 1, pp. 1–40, Mar. 1986. . Available: https://dx.doi.org/10.1137/1028001
  20. S. Chung, “Provably Correct Posit Arithmetic with Fixed-Point Big Integer.” ACM, 2018.
  21. J. Chen, Z. Al-Ars, and H. Hofstee, “A Matrix-Multiply Unit for Posits in Reconfigurable Logic Using (Open)CAPI.” ACM, 2018.
  22. Z. Lehoczky, A. Szabo, and B. Farkas, “High-level .NET Software Implementations of Unum Type I and Posit with Simultaneous FPGA Implementation Using Hastlayer.” ACM, 2018.
  23. S. Langroudi, T. Pandit, and D. Kudithipudi, “Deep Learning Inference on Embedded Devices: Fixed-Point vs Posit,” in Energy Efficiency Machine Learning and Cognitive Computing for Embedded Applications (EMC), 2018. . Available: https://sites.google.com/view/asplos-emc2/program
  24. https://github.com/ityonemo/Unum2
  25. https://github.com/stillwater-sc/universal
  26. ^ https://gitlab.com/cerlane/SoftPosit
  27. http://www.jhauser.us/arithmetic/SoftFloat.html
  28. Kahan, William M. (2016-07-15). "Prof. W. Kahan's Commentary on "THE END of ERROR — Unum Computing" by John L. Gustafson, (2015) CRC Press" (PDF). Archived from the original (PDF) on 2016-08-01. Retrieved 2016-08-01. {{cite web}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)

Further reading

External links

Category: