Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm for Evaluating Cubic Polynomials Using an Arbitrary SIMD Register Width

IP.com Disclosure Number: IPCOM000006390D
Publication Date: 2001-Dec-28
Document File: 6 page(s) / 43K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a forward differencing algorithm for evaluating cubic polynomials using an arbitrary single instruction, multiple data (SIMD) register width. The disclosed algorithm can be used on any microprocessor that has SIMD registers and instructions. The SIMD width can vary and the performance of this algorithm can be scaled with increasing SIMD width. The disclosed algorithm is particularly useful for evaluating parametric curves and surfaces that are based on cubic polynomials, as are commonly found in graphic-intensive and animation programs.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 28% of the total text.

Algorithm for Evaluating Cubic Polynomials Using an Arbitrary SIMD Register Width

Disclosed is a forward differencing algorithm for evaluating cubic polynomials using an arbitrary single instruction, multiple data (SIMD) register width. The disclosed algorithm can be used on any microprocessor that has SIMD registers and instructions. The SIMD width can vary and the performance of this algorithm can be scaled with increasing SIMD width. The disclosed algorithm is particularly useful for evaluating parametric curves and surfaces that are based on cubic polynomials, as are commonly found in graphic-intensive and animation programs.

The disclosed algorithm differs from other algorithms currently in use by taking advantage of SIMD instructions and registers and the negative relationship between SMID width and the number of operations per result (that is, performance increases with SMID width).

Forward differencing is an iterative method for evaluating polynomials. The disclosed algorithm evaluates a polynomial at a parametric value ti from a previous value ti-1 and the difference d1, i-1 between the previous value of the polynomialand the value at ti. This discussion focuses solely on evaluating cubic polynomials, but forward differencing may be used to evaluate polynomials of any degree. The following pseudo-code represents the disclosed algorithm:

Parameters:  a, b, c, d, n, tmax

// calculate the initial x and delta values

x(0) = d                                // x(0) = a*03+b*02+c*0+d

h = tmax / n

d1,0 = a*h3 + b*h2 + c*h

d2,0 = 6*a*h3 + 2*b*h2

d3 = 6*a*h3

SIMD registers: A, B

A = {x(0), d1,0, d2,0, d3}

// one result per iteration of this loop

for (i=1; i,n+1; i++)

{

             x(ti)= x(ti-1)+ d1,i-1

             d1,i = d1,i-1 + d2,i-1

             d2,i = d2,i-1 + d3

}

The cubic polynomial x(t)=a*t3+b*t2+c*t+d is evaluated at n+1 points in the parametric interval t=[0, tmax]. The parametric stepping interval h is equal to tmax/n. For cubic polynomials, the I-th point x(ti), (where 0<=I<n+1 and ti=h*I) on the curve is computed as follows:

x(ti) = x(ti-1) + d1, i-1
d1, i-1 += d2, i-1

d2, i += d3

Note that d3  is a constant, whereas d1 anddchange over the interval t.

The first point x(t0) and the first set of deltas d1,0, d2,0, andd3 are calculated separately from the rest of the points and deltas. The first point is just x(t) directly evaluated at t=0. The first set of deltas is calculated as follows:

d1,0 = a*h3+b*h2+c*h

d2,0 = 6*a*h3+2*b*h2

d3 = 6*a*h3

Two methods of implementing the disclosed forward-differencing algorithm to take advantage of SIMD instructions are presented. Method 1 yields one result per iteration of the main loop. Method 2 yields a number of results equivalent to the SIMD width per iteration of the main loop.

Method 1: Single result per iteration

The single result per iteration method requires x(ti-1), d1, i-1, d2, i-1, d3 to be arranged in  a single SIMD register (in that order). Four SIMD elements are required to load these four values in a single SIMD register, so the minimum SIMD w...