Implementing Fixed-Point Polynomials in Hardware Logic
AssigneeImagination Technologies Limited
InventorTheo Alan Drane
Life of this patent
Estimating the term…
Abstract
A method implements fixed-point polynomials in hardware logic. In an embodiment the method comprises distributing a defined error bound for the whole polynomial between operators in a data-flow graph for the polynomial and optimizing each operator to satisfy the part of the error bound allocated to that operator. The distribution of errors between operators is updated in an iterative process until a stop condition (such as a maximum number of iterations) is reached.
Claims19
A method of generating an implementation of a fixed-point polynomial with rational coefficients in hardware logic that satisfies a defined error bound, the method comprising:
- receiving, in the hardware logic, the polynomial as a data-flow graph comprising one or more nodes, wherein each node is either a sum-of-products operator or a constant division operator;
- computing, in the hardware logic, an error bound for each node in the data-flow graph based on the defined error bound for the polynomial;
- optimizing, in the hardware logic, a single summation array for each node using a truncation scheme and the error bound for each node;
- calculating, in the hardware logic, an updated error bound for each node in the data-flow graph, wherein the calculating of updated error bounds redistributes error bounds between nodes to allow for synthesis of the fixed-point polynomial with a reduced physical size whilst satisfying the defined error bound;
- and
- further optimizing, in the hardware logic, the single summation array for each node using the truncation scheme and the updated error bound for the node.
An apparatus configured to perform lossy synthesis of a fixed-point polynomial with rational coefficients and generate an implementation of the fixed-point polynomial in RTL, the apparatus comprising:
- a processor;
- and
- a memory comprising computer executable instructions which, when executed, cause the processor to:
- receive the polynomial as a data-flow graph comprising one or more nodes, wherein each node is either a sum-of-products operator or a constant division operator;
- compute an error bound for each node in the data-flow graph based on the defined error bound for the polynomial;
- optimize a single summation array for each node using a truncation scheme and the error bound for each node;
- calculate an updated error bound for each node in the data-flow graph, wherein the calculating of updated error bounds redistributes error bounds between nodes to allow for synthesis of the fixed-point polynomial with a reduced physical size whilst satisfying the defined error bound;
- and
- further optimize the single summation array for each node using the truncation scheme and the updated error bound for the node.
An apparatus configured to compare two or more array summations when implemented in hardware logic, the apparatus comprising:
- a processor;
- and
- a memory comprising computer executable instructions which, when executed, cause the processor to:
- receive RTL data describing the two or more array summations;
- and
- calculating, for each array summation, a cost function using:
- area
-
-
- (
- array
-
- (
- h
- ,
- w
- ,
- pp
- )
- )
- ≈
- 7
-
- pp
-
- (
- 1
- -
- (
- 2
- 3
- )
- f
- )
- +
- w
- 2
-
- (
- 2
-
- ⌈
- log
- 2
-
- w
- ⌉
- +
- 11
- )
- where
-
-
- f
- =
- ⌈
- log
- 2
-
- h
- -
- 1
- log
- 2
-
- 3
- -
- 1
- ⌉
- where w is a width of the array, h is a height of the array and pp is a number of bits in the array,
- wherein the cost functions calculated for each array summation provide for several candidate RTL implementations to be compared and an RTL implementation with an optimal cost function to be selected for implementation in hardware.
Dependencies are inferred from the claim text.