Method and processing apparatus for performing arithmetic operation

Patent metadata

Field	Value
Publication number	US-10540145-B2
Application number	US-201916358486-A
Country	US
Kind code	B2
Filing date	Mar 19, 2019
Priority date	Sep 18, 2015
Publication date	Jan 21, 2020
Grant date	Jan 21, 2020

Abstract

A method of performing an arithmetic operation by a processing apparatus includes determining a polynomial expression approximating an arithmetic operation to be performed on a variable; adaptively determining upper bits for addressing a look-up table (LUT) according to a variable section to which the variable belongs; obtaining coefficients of the polynomial expression from the LUT by addressing the LUT using a value of the upper bits; and performing the arithmetic operation by calculating a result value of the polynomial expression using the coefficients.

First claim

What is claimed is:

1. An apparatus comprising:
a memory configured to store a look-up table; and
a processor including:
a converter that determines a first polynomial expression that approximates an arithmetic operation to be performed on a first variable having n bits, and that determines a second polynomial expression that approximates the arithmetic operation to be performed on a second variable having n bits;
an addressing circuit that sets a first address of the look-up table using m bits of the n bits of the first variable, and that sets a second address of the look-up table using k bits of the n bits of the second variable;
an obtainer circuit that obtains first coefficients of the first polynomial expression from the look-up table using a value of the m bits, and that obtains second coefficients of the second polynomial expression from the look-up table using a value of the k bits; and
a calculator that calculates a first result value of the first polynomial expression using the first coefficients, and that calculates a second result value of the second polynomial expression using the second coefficients,

wherein each of n, m and k is a positive integer,
m is less than n,
k is less than n, and is less than m, and
a difference between the first polynomial expression and the arithmetic operation is greater than a difference between the second polynomial expression and the arithmetic operation.

2. The apparatus of claim 1 , wherein the m bits are upper bits of the n bits of the first variable, and
the k bits are upper bits of the n bits of the second variable.

3. The apparatus of claim 2 , wherein the addressing circuit adaptively determines the m bits for addressing the look-up table according to a first variable section of a plurality of variable sections, and determines the k bits for addressing the look-up table according to a second variable section of the plurality of variable sections,
each of the plurality of variable sections is obtained by splitting a range of each variable that is input to the arithmetic operation, and
sizes of the plurality of variable sections are non-uniform.

4. The apparatus of claim 3 , wherein when a size of a variable section increases, the number of the upper bits decreases, and
when a size of the variable section decreases, the number of the upper bits increases.

5. The apparatus of claim 1 , wherein the arithmetic operation includes a square root operation, an inverse square root operation, a reciprocal operation, a log operation, an exponential operation, a power series operation, or a trigonometric operation.

6. The apparatus of claim 1 , wherein values of m and k are determined based on a type of the arithmetic operation.

7. The apparatus of claim 1 , wherein a first input variable of the first polynomial expression is a value of (n−m) bits of the first variable, and
the calculator calculates the first result value of the first polynomial expression using the first input variable and the first coefficients.

8. An apparatus comprising:
a memory configured to store a look-up table; and
a processor including:
a converter that determines a first polynomial expression that approximates an arithmetic operation to be performed on a first variable having n bits, and that determines a second polynomial expression that approximates the arithmetic operation to be performed on a second variable having n bits;
an addressing circuit that sets a first address of the look-up table using m bits of the n bits of the first variable, and that sets a second address of the look-up table using k bits of the n bits of the second variable;
an obtainer circuit that obtains first coefficients of the first polynomial expression from the look-up table using the m bits, and that obtains second coefficients of the second polynomial expression from the look-up table using the k bits; and
a calculator that calculates a first result value of the first polynomial expression using the first coefficients, and that calculates a second result value of the second polynomial expression using the second coefficients,

wherein each of n, m and k is a positive integer,
m is less than n, and
k is less than n, and is different from m.

9. The apparatus of claim 8 , wherein a difference between the first polynomial expression and the arithmetic operation is greater than a difference between the second polynomial expression and the arithmetic operation, and
m is greater than k.

10. The apparatus of claim 8 , wherein the m bits are upper bits of the n bits of the first variable, and
the k bits are upper bits of the n bits of the second variable.

11. The apparatus of claim 8 , wherein the addressing circuit adaptively determines the m bits for addressing the look-up table according to a first variable section of a plurality of variable sections, and determines the k bits for addressing the look-up table according to a second variable section of the plurality of variable sections,
each of the plurality of variable sections is obtained by splitting a range of each variable that is input to the arithmetic operation, and
sizes of the plurality of variable sections are non-uniform.

12. The apparatus of claim 11 , wherein a degree of non-uniformity of the sizes of the plurality of variable sections varies based on a type of the arithmetic operation.

13. The apparatus of claim 8 , wherein values of m and k are determined based on a type of the arithmetic operation.

14. The apparatus of claim 8 , wherein a first input variable of the first polynomial expression is a value of (n−m) bits of the first variable, and
the calculator calculates the first result value of the first polynomial expression using the first input variable and the first coefficients.

15. The apparatus of claim 8 , wherein each of the first result value and the second result value is a result of performing the arithmetic operation.

16. A device comprising:
a converter that determines a first polynomial expression that approximates an arithmetic operation to be performed on a first variable having n bits, and that determines a second polynomial expression that approximates the arithmetic operation to be performed on a second variable having n bits;
an addressing circuit that sets a first address of a look-up table using m bits of the n bits of the first variable, and that sets a second address of the look-up table using k bits of the n bits of the second variable;
an obtainer circuit that obtains first coefficients of the first polynomial expression from the look-up table using a value of the m bits, and that obtains second coefficients of the second polynomial expression from the look-up table using a value of the k bits; and
a calculator that calculates a first result value of the first polynomial expression using the first coefficients, and that calculates a second result value of the second polynomial expression using the second coefficients,
wherein each of n, m and k is a positive integer,
m is less than n,
k is less than n, and is less than m, and
a first error between the first polynomial expression and the arithmetic operation is greater than a second error between the second polynomial expression and the arithmetic operation.

17. The device of claim 16 , wherein the look-up table is stored in an external memory device.

18. The device of claim 16 , further comprising a memory that stores the look-up table.

19. The device of claim 16 , wherein the addressing circuit adaptively determines the m bits according to a first

Assignees

• Samsung Electronics Co Ltd

Inventors

• Yu Hyeongseok

Classifications

• G06F9/30029

  Logical and Boolean instructions, e.g. XOR, NOT · CPC title

• G06F12/1009

  using page tables, e.g. page table structures · CPC title

• G06F9/3001 Primary

  Arithmetic instructions · CPC title

• G06F7/5525

  Roots or inverse roots of single operands · CPC title

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title