Search

US-12625678-B2 - Correctly rounded table-based computation of logarithmic function

US12625678B2US 12625678 B2US12625678 B2US 12625678B2US-12625678-B2

Abstract

A method of computing logarithms, comprising receiving a number, computing an exponent and significand of the received number, selecting a breakpoint value from a plurality of breakpoint values segmenting a range of the significand wherein the selected breakpoint value is the significand's greatest lower bound or lowest upper bound, computing a multiplication of the exponent and a logarithm value of two, computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value, computing an approximated logarithm value of a second intermediate value derived from the first intermediate value, computing a logarithm value of the significand by summing the approximated logarithm value and a logarithm value of the selected breakpoint value, computing a logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two.

Inventors

  • Daniel KHANKIN
  • Tomer Levin
  • Daniel Srebnik

Assignees

  • NEXT SILICON LTD

Dates

Publication Date
20260512
Application Date
20240214

Claims (19)

  1. 1 . A method for efficiently computing correctly-rounded logarithm value in specialized hardware, comprising: using one or more unsigned integer arithmetic circuits of at least one processor configured for logarithmic computations, said at least one processor configured for: computing off-line or computing in advance to real-time computation of a logarithm value for a received number, a plurality of pre-computed logarithm values and corresponding inverse values of the pre-computed logarithm values, each for another one of a plurality of breakpoint values; storing said plurality of pre-computed logarithm values and said corresponding inverse values in a memory device; wherein said at least one processor comprises one or more interconnected computing grids, wherein each of the one or more interconnected computing grid comprises a plurality of reconfigurable logical elements connected to a plurality of memory units via an interconnected network comprising: a plurality of configurable data routing junctions, a plurality of ingress ports, and a plurality of egress ports; in run-time: during each of a plurality of executed computation tasks, analyzing each respective computation task to determine computational requirements and dynamically adjusting a configuration of the one or more interconnected computing grids by: creating a directed acyclic compute graph having nodes corresponding to logarithmic operations and edges corresponding to data movement between operations, mapping said nodes to said reconfigurable logical elements, and configuring said configurable data routing junctions to connect said nodes according to said edges of said compute graph via said plurality of ingress ports and said plurality of egress ports for an optimized processing configuration, said plurality of executed computation tasks comprising: receiving, through an I/O interface, a number and computing an exponent and significand of the received number; selecting a breakpoint value from the plurality of breakpoint values segmenting a range of the significand, the selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand; fetching from said memory device a respective logarithm value of the selected breakpoint value; computing a multiplication of the exponent and a logarithm value of two; computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value; computing an approximated logarithm value of a second intermediate value derived from the first intermediate value; computing a logarithm value of the significand by summing the approximated logarithm value and the fetched respective logarithm value of the selected breakpoint value; computing the logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two; and outputting through said I/O interface, the correctly-rounded logarithm value, wherein storing said pre-computed logarithm values and inverse values in said memory device enables fetching of pre-computed values rather than computing inverse values and logarithm values during execution of the computation tasks.
  2. 2 . The method of claim 1 , wherein the received number is selected from a group consisting of: floating-point, integer, fixed-point, Unum, posit, and logarithmic number system (LNS).
  3. 3 . The method of claim 1 , wherein the at least one processor is configured to compute at least some of the computing steps using at least one arithmetic circuit employing unsigned integer arithmetic.
  4. 4 . The method of claim 1 , wherein said computing the logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two is defined by the formulation: log b ( x ) = e ⁢ log b ( 2 ) + log b ( m ) wherein x is the received number, e is the exponent of the number, m is the significand of the received number, and b is a selected base of the logarithm.
  5. 5 . The method of claim 4 , wherein said computing the logarithm value of the significand by summing the approximated logarithm value and a logarithm value of the selected breakpoint value is defined by the formulation: log b ( m ) = log b ( c k ) + log b ( 1 + r ) wherein c k represents the selected breakpoint value, and r is the first intermediate value.
  6. 6 . The method of claim 5 , wherein each of the plurality of breakpoint values c k is computed according to the formulation: c k = 1 + k 2 N wherein N is a parameter determining a number of breakpoints, and k is an index of a respective breakpoint, wherein k=(0, 1,2, . . . , 2-1) for selecting a breakpoint value which is the greatest lower bound of the significand, and wherein k=(1,2, . . . , 2) for selecting a breakpoint value which is the lowest upper bound of the significand.
  7. 7 . The method of claim 5 , wherein the first intermediate value is computed according to the formulation: r = 1 c k ⁢ ( m - c k ) .
  8. 8 . The method of claim 5 , wherein the approximated logarithm value of the second intermediate value is computed according to the formulation: log b (1+r).
  9. 9 . The method of claim 1 , wherein the inverse value and the logarithm value of the selected breakpoint value are precomputed and fetched from memory.
  10. 10 . The method of claim 9 , wherein at least one of the inverse value and the logarithm value of the selected breakpoint value are stored in the memory in fixed-point format.
  11. 11 . The method of claim 1 , wherein at least one of the inverse value and the logarithm value of the selected breakpoint value are computed in runtime.
  12. 12 . The method of claim 1 , further comprising adjusting a number of the plurality of breakpoint values segmenting the range of the significand according to the value of the received number and selecting the selected breakpoint value accordingly.
  13. 13 . The method of claim 1 , further comprising computing the logarithm value of the received number in at least one additional iteration, wherein each additional iteration comprises: adjusting a number of breakpoint values segmenting the range of the significand according to the logarithm value computed for the received number in a previous iteration, selecting another breakpoint value based on the adjusted number of breakpoint values, and computing the logarithm value of the received number based on the another selected breakpoint value.
  14. 14 . The method of claim 1 , wherein the at least one processor comprises at least one unsigned integer arithmetic circuit configured to compute, based on the inverse value and the logarithm value of the selected breakpoint value which are expressed in fixed-point format, at least one of the first intermediate value, the approximated logarithm value, the logarithm value of the significand, and the logarithm value of the received number.
  15. 15 . The method of claim 1 , further comprising rounding the logarithm value of the received number according to at least one rounding scheme.
  16. 16 . The method of claim 1 , wherein the approximated logarithm value of the second intermediate value is computed by applying minimax polynomial approximation.
  17. 17 . The method of claim 1 , further comprising: collecting a plurality of statistical values comprising a plurality of data-statistic values indicative of the computing of the first intermediate value, the approximated logarithm value, the logarithm value of the significand, and/or the logarithm value of the received number, and analyzing the plurality of statistical values to evaluate hardware utilization.
  18. 18 . A processing apparatus with increased efficiency in computation of correctly-rounded logarithm value in specialized hardware, comprising: an input interface configured to receive a number; at least one processor which comprises one or more interconnected computing grids, wherein each of the one or more interconnected computing grid comprises a plurality of reconfigurable logical elements connected to a plurality of memory units via an interconnected network comprising: a plurality of configurable data routing junctions, a plurality of ingress ports, and a plurality of egress ports; one or more unsigned integer arithmetic circuits of the at least one processor configured to: compute off-line or compute in advance to real-time computation of a logarithm value for the received number, a plurality of pre-computed logarithm values and corresponding inverse values of the pre-computed logarithm values, each for another one of a plurality of breakpoint values; store said plurality of pre-computed logarithm values and said corresponding inverse values in a memory device; in run-time: during each of a plurality of executed computation tasks, analyze each respective computation task to determine computational requirements and dynamically adjust a configuration of the one or more interconnected computing grids by: creating a directed acyclic compute graph having nodes corresponding to logarithmic operations and edges corresponding to data movement between operations, mapping said nodes to said reconfigurable logical elements, and configuring said configurable data routing junctions to connect said nodes according to said edges of said compute graph via said plurality of ingress ports and said plurality of egress ports for an optimized processing configuration, said plurality of executed computation tasks comprising: compute an exponent and significand of the received number; select a breakpoint value from the plurality of breakpoint values segmenting a range of the significand, the selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand; fetch from said memory device a respective logarithm value of the selected breakpoint value; compute a multiplication of the exponent and a logarithm value of two; compute a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value; compute an approximated logarithm value of a second intermediate value derived from the first intermediate value; compute a logarithm value of the significand by summing the approximated logarithm value and the fetched respective logarithm value of the selected breakpoint value; compute the logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two; and an output interface configured to output the correctly-rounded logarithm value computed for the received number wherein storing said pre-computed logarithm values and inverse values in said memory device enables fetching of pre-computed values rather than computing inverse values and logarithm values during execution of the computation tasks, thereby reducing hardware resource utilization and power consumption.
  19. 19 . A method for efficiently computing correctly-rounded logarithm value in specialized hardware, comprising: using one or more unsigned integer arithmetic circuits of at least one processor configured for: computing off-line or computing in advance to real-time computation of a logarithm value for a received number, a plurality of pre-computed binary logarithm values and corresponding inverse values of the pre-computed binary logarithm values, each for another one of a plurality of breakpoint values; storing said plurality of pre-computed binary logarithm values and said corresponding inverse values in a memory device; wherein said at least one processor comprises one or more interconnected computing grids, wherein each of the one or more interconnected computing grid comprises a plurality of reconfigurable logical elements connected to a plurality of memory units via an interconnected network comprising: a plurality of configurable data routing junctions, a plurality of ingress ports, and a plurality of egress ports; in run-time: during each of a plurality of executed computation tasks, analyzing each respective computation task to determine computational requirements and dynamically adjusting a configuration of the one or more interconnected computing grids by: creating a directed acyclic compute graph having nodes corresponding to logarithmic operations and edges corresponding to data movement between operations, mapping said nodes to said reconfigurable logical elements, and configuring said configurable data routing junctions to connect said nodes according to said edges of said compute graph via said plurality of ingress ports and said plurality of egress ports for an optimized processing configuration, said plurality of executed computation tasks comprising: receiving, through an I/O interface, a number and computing, by said logarithm calculator, an exponent and significand of the received number; selecting a breakpoint value from the plurality of breakpoint values segmenting a range of the significand, the selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand; fetching from said memory device a respective binary logarithm value of the selected breakpoint value; computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value; computing an approximated binary logarithm value of a second intermediate value derived from the first intermediate value; computing a binary logarithm value of the significand by summing the approximated binary logarithm value and the fetched respective binary logarithm value of the selected breakpoint value; computing a binary logarithm value of the received number by summing the binary logarithm value of the significand and the exponent; computing a base b logarithm value of the received number by dividing the binary logarithm value of the received number by a binary logarithm value of b; and outputting, through said I/O interface, the correctly-rounded logarithm value, wherein storing said pre-computed logarithm values and inverse values in said memory device enables fetching of pre-computed values rather than computing inverse values and logarithm values during execution of the computation tasks, thereby reducing hardware resource utilization and power consumption.

Description

BACKGROUND The present invention, in some embodiments thereof, relates to computing logarithms for numbers, and, more specifically, but not exclusively, to computing logarithm values for received numbers using precomputed logarithm values of values bounding the significand of the received numbers. As technology advances, the need for stronger processing systems and computing power rapidly increases. Two common metrics used to measure a processing unit's performance are latency and throughput. As used herein, the term “processing circuit” is used to mean any kind of programmable or non-programmable circuit that is configured to carry out a set of mathematical computation operations such as, for example, computing logarithm values of numbers. A processing circuit may comprise hardware, firmware, software and/or a combination thereof. For example, a processing circuit may comprise one or more processors and a memory that carries a program which causes the processing circuit to perform operations when the program is executed by the one or more processors. There exist a variety of methods for improving a processing circuit's performance. Some methods may increase throughput; others may decrease latency. Some methods may both increase throughput and reduce latency, although there is usually a tradeoff between the two metrics. SUMMARY It is an object of the present invention to provide methods, systems and software program products for efficiently computing logarithm values of numbers, specifically correctly rounded logarithm values. The foregoing and other objects are achieved by the features of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures. According to a first aspect of the present invention there is provided a method of computing logarithms, comprising using one or more processors configured for: Receiving a number and computing an exponent and significand of the received number.Selecting a breakpoint value from a plurality of breakpoint values segmenting a range of the significand, the selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand.Computing a multiplication of the exponent and a logarithm value of two.Computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value.Computing an approximated logarithm value of a second intermediate value derived from the first intermediate value.Computing a logarithm value of the significand by summing the approximated logarithm value and a logarithm value of the selected breakpoint value.Computing a logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two.Outputting the logarithm value computed for the received number. According to a second aspect of the present invention there is provided a processing apparatus for computing logarithms, comprising an input interface configured to receive a number and compute an exponent and significand of the received number, one or more processors configured to compute a logarithm value of the received number, and an output interface configured to output the logarithm value computed for the received number. The one or more processors configured to compute a logarithm value of the received number by: Selecting a breakpoint value from a plurality of breakpoint values segmenting a range of the significand. The selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand.Computing a multiplication of the exponent and a logarithm value of two.Computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value.Computing an approximated logarithm value of a second intermediate value derived from the first intermediate value.Computing a logarithm value of the significand by summing the approximated logarithm value and a logarithm value of the selected breakpoint value.Computing the logarithm value of the received number by summing the logarithm value of the significand and the multiplication of the exponent and the logarithm value of two. According to a third aspect of the present invention there is provided a method of computing logarithms, comprising using one or more processors configured for: Receiving a number and computing an exponent and significand of the received number.Selecting a breakpoint value from a plurality of breakpoint values segmenting a range of the significand, the selected breakpoint value is one of: a greatest lower bound, and a lowest upper bound, of the significand.Computing a first intermediate value based on a least significant portion of the significand and an inverse value of the selected breakpoint value.Computing an approximated binary logarithm value of a second intermediate va