Evaluating Polynomials in Hardware Logic

Patent metadata

Field	Value
Publication number	US-2017308355-A1
Application number	US-201715493340-A
Country	US
Kind code	A1
Filing date	Apr 21, 2017
Priority date	Apr 22, 2016
Publication date	Oct 26, 2017
Grant date	—

Abstract

An accurate implementation of a polynomial using floating-point or other rounded arithmetic can be generated using a plurality of hardware logic components which each implement an input polynomial such that the zeros in the input polynomial can be determined correctly. The number of different hardware logic components that are used can be reduced by analysing the set of input polynomials and from it generating a set of polynomial components, where each polynomial in the set of input polynomials which is not also in the set of polynomial components, can be generated from a single one of the polynomial components.

First claim

1 . A method of generating an implementation of one or more polynomials using rounded arithmetic, the method comprising:
receiving, in an input module, a set of input polynomials generated from the one or more polynomials; reducing, in an assessment module, the set of input polynomials to a smaller set of polynomial components from which all the set of input polynomials can be evaluated accurately, by only adding those polynomials from the input set of polynomials which cannot be evaluated using other polynomials in the set of input polynomials or set of polynomial components to the set of polynomial components; and generating an implementation of the one or more polynomials comprising a plurality of interconnected hardware logic elements, each of the hardware logic elements arranged to correctly evaluate one of the polynomial components using the rounded arithmetic and the plurality of hardware logic elements comprising at least one hardware logic element corresponding to each of the polynomial components.

2 . A method according to claim 1 , wherein reducing the set of input polynomials to a smaller set of polynomial components from which all the set of input polynomials can be evaluated accurately comprises:
(i) removing a polynomial q from the set of input polynomials; (ii) determining if there is any variable assignment for which a function F is equal to zero, where:

F


(

x
1

,
…


,

x
m

,

y
1

,
…


,

y
r

)

=

∏

p
z





(

p
z



(
x
)

-

q


(
y
)

)

where p z is the union of the set of input polynomials and the set of polynomial components;
(iii) in response to determining that there is no variable assignment for which a function F is equal to zero, adding the polynomial q to the set of polynomial components and in response to determining that there is a variable assignment for which a function F is equal to zero, not adding the polynomial q to the set of polynomial components; and
repeating (i)-(iii) until all polynomials have been removed from the set of input polynomials.

3 . A method according to claim 2 , wherein removing a polynomial q from the set of input polynomials comprises:
selecting a polynomial q from the set of input polynomials and removing the polynomial q from the set of input polynomials.

4 . A method according to claim 3 , wherein the polynomial q is selected from the set of input polynomials based on pre-defined criteria.

5 . A method according to claim 3 , wherein the polynomial q is selected from the set of input polynomials based on a total degree, number of variables and/or number of terms in each polynomial in set the of input polynomials.

6 . A method according to claim 3 , wherein the polynomial q is selected from the set of input polynomials if it has a least number of variables amongst the polynomials of least total degree.

7 . A method according to claim 2 , further comprising:
filtering p z based on a total degree, number of variables and/or number of terms in each polynomial in the set of input polynomials prior to determining if there is any variable assignment for which a function F is equal to zero.

8 . A method according to claim 7 , wherein p z is filtered such that it comprises only those polynomials that meet all the following criteria:
total degree of p z ≧total degree of q
number of variables of p z ≧number of variables of q
number of terms of p z ≧number of terms of q

9 . A method according to claim 2 , wherein determining if there is any variable assignment for which a function F is equal to zero comprises evaluating F only for variable assignments which cannot be simplified.

10 . A method according to claim 9 , further comprising:
checking if a variable assignment can be simplified by expressing one or more variable assignments in matrix form, putting the matrix into reduced row echelon form and determining if the reduced row echelon form results in a simplification of the matrix.

11 . A method according to claim 2 , wherein determining if there is any variable assignment for which a function F is equal to zero comprises determining if there is any variable assignment for which the single function F is equal to zero.

12 . A method according to claim 1 , further comprising:
performing variable renaming on the received set of input polynomials prior to reducing the set of input polynomials to a smaller set of polynomial components from which all the set of input polynomials can be evaluated accurately.

13 . A method according to claim 12 , wherein performing variable renaming on the received set of input polynomials comprises:
replacing variables in each of the received set of input polynomials with variables from a common set of variables.

14 . A method according to claim 1 , wherein the one or more polynomials have floating point inputs.

15 . A method according to claim 1 , further comprising:
fabricating an integrated circuit comprising the implementation of the one or more polynomials.

16 . A system configured to generate an implementation of one or more polynomials using rounded arithmetic, the system comprising a polynomial component compiler module comprising:
an input module arranged to receive a set of input polynomials generated from the one or more polynomials; an assessment module arranged to reduce the set of input polynomials to a smaller set of polynomial components from which all the set of input polynomials can be evaluated accurately, by only adding those polynomials from the input set of polynomials which cannot be evaluated using other polynomials in the set of input polynomials or set of polynomial components to the set of polynomial components; and an output module arranged to output the s

Assignees

• Imagination Tech Ltd

Inventors

• Drane Theo Alan

Classifications

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F7/483 Primary

  Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)} · CPC title

• G06F7/552 Primary

  Powers or roots {, e.g. Pythagorean sums} · CPC title

• G06F2207/5523

  Calculates a power, e.g. the square, of a number or a function, e.g. polynomials · CPC title