# Coding的痕迹

0%

## 动机

Number systems and computer arithmetics are essential for designing efficient hardware and software architecture. In particular, real-valued computation constitutes a crucial component in almost all forms of today’s computing systems from mobile devices to servers. IEEE 754 is a prominent standard established in 1985 for representing real-valued numbers in a floating-point format. Despite all its benefits, this number system suffers from a number of weaknesses.

• 对小的数字占用了太大空间。 IEEE754 标准分别使用 32和64个二进制位表示单精度和双精度两种数值，它在特定和有限的数字范围下的计算可能效率非常低。比如说，使用 IEEE754 表示，计算位于 [-1, 1] 范围内值的点乘只需要占用有限的几位就可以表示所有的可能，但大多数位都被浪费了。

Large size for small numbers. The IEEE 754 standard defines two specific formats for single- and double-precision value representation using 32 and 64 bits, respectively. Numerical computation within a limited range of values in these formats may be largely inefficient. For example, computing dot-products of values within [-1, 1] requires only a tiny fraction of all possible numbers represented in either format.

• 精度有限。 IEEE754 规定了固定的指数和尾数长度。这可能导致在表示实数时存在舍入错误，一些浮点数的精度会下降。

Limited precision. IEEE 754 has predefined fixed-size partitions for an exponent and a fraction. This may lead to a rounding error when representing real numbers; therefore, some floating-point numbers are not precise.

• 存在表示异常的位。 IEEE754 保留了一些位去表示 NaN（Not Available Number）、非规格化数、正负零和无穷这样的值。除了浪费了一些可能的位模式（bit patterns）外，也使得浮点处理器中不得不对这些值做单独的处理，增加了计算的复杂度。

Exceptional bit representations. IEEE 754 reserves several bits to represent NaNs, denormals, positive/negative zero and infinity. In addition to wasting some of the possible bit patterns, considering all the reserved patterns for computation adds further complexity to the floating-point processors.

• 不符合运算规则。 浮点格式可能在计算中不符合运算法则。如，一个浮点加法不总是符合加法结合律。浮点数值 x = 1e30y = -1e30z = 1 时表达式 (x+y) + z 结果是 1，而使用同样的值 x + (y + z) 的值确是 0

Breaking algebraic rules. The floating-point formats may break algebraic rules during computation. For instance, a floating-point addition is not always associative. The expression (x+y)+z results in 1, where the floating-point values are x = 1e30, y = -1e30 and z = 1 is 1. Using the same values, x+(y+z) results in 0.

• 产生了不一致的结果。 设两个向量：Q = (3.2E7, 1, -1, 9.0E7)W = (4.0E7, 1, -1, -1.6E7)，在单精度（如C语言中的 float 类型）下计算 Q·W 结果是 0，但是正确的答案是 2。而在双精度浮点表示中，需要使用 80 个中间位才能得到正确结果。

Producing inconsistent results. Consider two vectors Q = (3.2e7, 1, –1, 8.0e7) and W = (4.0e7, 1, –1, –1.6e7). The dot product Q.W is equal to 0 in single-precision (i.e., the float type in C); while, the right answer is 2. Using the floating-point representation, 80 intermediate bits are necessary to produce the correct answer in the double-precision format.

• 设计和验证太复杂。 由于必须要处理好取整、异常、NaN 和非规格化数，尾数对齐等等问题，设计一个浮点变量通常很麻烦。除此之外，在验证浮点数的设计时还有一个重要的任务是验证边界情况。

Complex design and verification. Designing an efficient floating-point unit could be time-consuming due to the necessary components for handling rounding, exception, NaNs, denormals, mantissa alignment, etc. Moreover, verifying the floating-point design is a significant task because of dealing with numerous corner cases.

To overcome these challenges, various number systems and data representation techniques have been proposed to enhance or replace the floating-point numbers. A few examples of such techniques are Interval arithmetic, universal number systems TypeI, and TypeII. The most recent floating-point number system invented by John L. Gustafson in 2017 is called posit that addresses many of the above-mentioned problems.

## Posit 格式

A generic posit format consists of a mandatory sign, one or multiple regime bits, multiple optional exponent bits, and multiple optional fraction bits (Fig. 1). The sign bit is 0 for positive numbers and 1 for negative ones. The number of regime bits is dynamic following a special encoding. After the sign bit, the regime includes a run of 0 or 1, which is terminated by an opposite bit (r̄) or at the end of the number format. Similarly, the number of bits for the exponent and fraction is dynamic. A posit number includes the exponent and fraction only if necessary.

Fig.1: General posit format for finite, nonzero values-color codes.

To understand how the regime bits represent numbers, consider the binary numbers in Fig. 2.

Fig. 2: Decimal values of regime bits (“x” means don’t care).

m 是控制位中琥珀色位表示的数量，当第一位是 0 时，零的数量（m）表示负值（-m），否则1的数量再减1表示一个正值（m-1）。控制位决定了 $ussed^k$ 中的幂，其中 $useed = 2^{2^{es}}$

Let m be the number of identical bits in the regime bits (amber color). If the first bit is zero, the number of zeros (m) represents a negative value (-m). Otherwise, the number of ones minus one (m-1) represents a positive value (m-1). The regime bits realize a scale factor of $useed^k$, where $useed = 2^{2^{es}}$.

Exponent e (blue bits) is regarded as an unsigned integer to realize another scale 2e. Unlike IEEE 754, posit does not use bias for the exponent. Each exponent may be up to a predefined number of bits (es). The remaining bits after the regime and the exponent are used for the fraction (f). Similar to IEEE 754, the fraction includes a hidden bit, which is always 1 as posit does not have any denormal number. Overall, an n-bit posit number § can represent the following numbers.

For instance, Fig.3 represents 477/134217728 ≈ 3.55393 × 10-6 with es=3.

Fig. 3: Example of a posit number and its decimal value

## Posit 数的构造

Fig. 4 shows values for a 3-bit posit format with n = 3 and es = 1. There are only two reserve representations: 0 (all 0 bits) and ±∞ (1 followed by all 0 bits). A total of 8 values may be represented using 3 bits.

Fig. 4: Values for a 3-bit posit

Similar to the floating-point numbers, appending 0 to a number does not change its value, whereas appending a 1 results in a new value between two existing numbers on the ring (Fig. 5, and 6). The new posit value may be (1) between the maxvalue (useed) and ±∞, the new value is maxvalue × useed, (2) between the existing values x = 2m and y = 2n , where |m-n|> 1, the new value is xy (add a new exponent bit), or (3) between the existing x and y values next to it, which is (x + y)/2( add a new fraction bit).

Fig. 5: Values for a 4-bit posit

Fig. 6: Values of a 5-bit posit

## Posit 与 IEEE754 标准 之间的对比

• 值的表示唯一。 在 Posit 格式里，如果 f 是一个函数，当 a = bf(a) = f(b) 恒成立，但在 IEEE754 却不然。按 IEEE754，由于正零应该等于负零，正负零的倒数分别对应于正无穷和负无穷，正无穷和负无穷却相等，这明显不对；在浮点数的比较中，当 ab 中有一个值为 NaN 时，浮点比较 a == b 的结果始终为 false，甚至 ab 有相同的位模式时也会这样。而在 Posit 表示中，如果 ab 的位模式一致，它们始终相等，否则，它们并不相等。Posit 还保证在不同硬件系统的同一个算术操作的结果保证相等；在开头 Q·W 的例子中，Posit 只需要 24 个二进制位便能得到正确结果。

Unique Value Representation. In the posit format, f(a) is always equal to f(b) if a and b are equal, where f is a function. In the IEEE 754, the reciprocals of positive and negative zeros are +∞, −∞, respectively. Moreover, the negative zero equals positive zero. This implies +∞ = -∞ which is not true. In a floating-point comparison (a == b), the result is always false if either a or b is NaN. This even holds if a and b has the same bit representation. In posits, however, a and b are equal if they use the same bit patterns; otherwise, they are not equal. Moreover, the result of an arithmetic operation would be the same over different hardware systems. For instance, in the case of the Q.W example at the beginning, posit needs only 24 bits to generate the correct result.

• 没有平缓下溢。 当计算结果非零，但小于最小规格化的数时，IEEE754 会面临下溢的问题。这个问题可以通过舍入值去缓解，但可能会导致产生一个非规格化数。因此，为了保存更小的数字，一些小数位被转换成指数，也就是我们说的平缓下溢（gradual underflow）。处理平缓下溢很复杂，而且应该在IEEE兼容的微处理器中由软件支持。由于使用了锥形精度（tapered precision），Posit 数字系统在处理小指数数字和大指数时有着更高的精度，避免了这个问题。

No Gradual Underflow. IEEE 754 faces an underflow problem when the exact result of an operation is nonzero but smaller than the smallest normalized number. This problem is alleviated by rounding values. However, this may result in a denormal number. As a result, some fraction digits are transferred to the exponent for representing smaller numbers. This is known as gradual underflow. Handling gradual underflow is complicated and is supported in software by some IEEE compliant microprocessors. The posit number system does not encounter this problem due to supporting a tapered precision, where numbers with small exponents are represented more accurately than the numbers with large magnitude exponents.

• 支持跨格式的算术规则。 与 IEEE754 不同，Posit 能正确处理加法运算的结合。涉及到多个不同大小的 Posit 值的计算能保证产生同样的结果

Holding Algebraic Rules Across Formats. Unlike IEEE 754, posit holds the associativity of addition. Moreover, computing values across multiple posit formats with different sizes is guaranteed to produce the same value.

• 异常处理。 在 IEEE754 中有 14 种 NaN 的表示方式，但 Posit 中仅有简单的 0 和无穷的表示，这也使得 Posit 数的计算比 IEEE754 更简单。当遇到异常（如除零异常），中断处理句柄需要向应用程序报告错误和原因。

Exception Handling. While there are 14 representations of Nans in IEEE 754, there is no “NaN” in posits. Moreover, posit has single representations for 0 and ∞. Overall, it makes the computation with the posit numbers simpler than IEEE 754. In the case of exceptions (e.g., division by zero), the interrupt handler is expected to report the error and its cause to the application.

• Posit 系统的不足。 尽管 Posit 数具有所有种种这些优点，但浮点数格式却有一个相对于 Posit 的优势：具有固定的指数和尾数长度。固定长度对于分离指数和尾数可以进行并行解码。由于 Posit 字段长度是动态的，对它的解码只能串行地进行。然而，无 NaN 和非规格化数的设计也一定程度上简化了电路的设计。相比于浮点数系统的成熟，Posit 是一个新提出的、需要进一步研究的数字系统。作者认为在目前，还没有使用 Posit 算法的芯片。

Inefficiencies of Posit Numbers. Despite all the expected benefits of posit numbers, the floating-point format has one important advantage over posit, which is the fixed bit format for the exponent and fraction. As a result, parallel decoding may be used for extracting the exponent and fraction of floating-point numbers. Whereas, decoding the posit fields may only be done serially due to using dynamic ranges. However, not having NaNs and denormals simplifies the circuit to some extent. Nevertheless, unlike the floating-point system, posit is a newly proposed number system yet to be investigated thoroughly. To the best of authors’ knowledge, there is no fabricated chip using posit arithmetic to date.

Number systems can significantly influence the energy-efficiency of computation and data movement in computer systems. For instance, recent studies show how a posit number system may improve the performance of neural networks. As the need for energy-efficient computing is never-ending, it becomes increasingly important to design an efficient number system for future computing systems.

## 其他

About the authors: Payman Behnam is a graduate researcher at the Energy-Efficient Computer Architecture Laboratory, University of Utah, where he is involved in designing novel memory systems and energy-efficient accelerators for computer vision and machine learning applications. Mahdi Nazm Bojnordi is an assistant professor of the School of Computing at the University of Utah, Salt Lake City, UT.

Disclaimer: These posts are written by individual contributors to share their thoughts on the Computer Architecture Today blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGARCH or its parent organization, ACM.