News Column

Patent Issued for Processing Order with Integer Inputs and Floating Point Inputs

July 15, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- According to news reporting originating from Alexandria, Virginia, by VerticalNews journalists, a patent by the inventors Engh-Halstvedt, Andreas Due (Trondheim, NO); Nystad, Jorn (Trondheim, NO), filed on May 25, 2011, was published online on July 1, 2014.

The assignee for this patent, patent number 8766991, is ARM Limited (Cambridge, GB).

Reporters obtained the following quote from the background information supplied by the inventors: "This invention relates to the field of data processing systems. More particularly, this invention relates to the ordering of processing operations within data processing systems.

"It is known to provide data processing systems which use a plurality of input values in order to generate one or more result values. The input values may need to be fetched from a memory system. In some memory systems the input values may be returned in a variable order. Accordingly, in some known systems processing of the input values to generate the one or more result values does not take place until all of the input values have been received. This has the disadvantage that the input values need to be stored until they are used and that the processing may be delayed due to waiting for all the input values to be received before starting the processing.

"In some data processing systems there is a strict requirement that a given set of input values should always produce the same results. In order to help in meeting this requirement it is known to enforce a requirement that processing operations performed to generate the results from the inputs should always be performed in the same order. This avoids the possibility that the results will be dependent upon the order in which processing operations are performed."

In addition to obtaining background information on this patent, VerticalNews editors also obtained the inventors' summary information for this patent: "Viewed from one aspect the present invention provides apparatus for processing data comprising:

"processing circuitry configured to compute one or more result values as a function of a plurality of input values;

"a memory configured to store said plurality of input values;

"load circuitry configured to issue one or more memory access requests to said memory to retrieve said plurality of input values from said memory and to supply said plurality of input values to said processing circuitry; wherein

"said plurality of input values are retrieved in a variable order from said memory; and

"said processing circuitry is configured such that:

"(i) when said plurality of input values are integer format values, said processing circuitry performs processing upon said plurality of input values to compute said one or more result values in a variable order that is dependent upon said variable order in which said plurality of input values are retrieved from said memory; and

"(ii) when said plurality of input values are floating point format values, said processing circuitry performs processing upon said plurality of input values to compute said one or more result values in a fixed order that is independent of said variable order in which said plurality of input values are retrieved from said memory.

"The present technique recognises that when the input values are in an integer format, then it may be safe to vary the order in which those input values are processed to generate the one or more result values. Accordingly, the order in which the input value is processed may be dependent upon the order in which the input values are retrieved from the memory. The easing of this constraint may permit for a reduction in the storage requirements of input values before they are consumed as well as permitting processing to commence sooner and potentially finish sooner. When the plurality of input values are floating point format values, then the processing circuitry does not permit a variable ordering in how the input values are processed. This both recognises and solves the problem that the result value may be dependent upon the order in which the input values are consumed when the input values are floating point format values.

"The function relating the one or more result values to the plurality of input values can have a variety of different forms. The present technique is particularly useful when this function is associative when the plurality of input values are integer format values and is non-associative when the plurality of input values are floating point format values.

"The variable order in which integer format input values are processed may vary in a number of different ways. In some embodiments the variable order may be the same as the order in which the plurality of input values are retrieved from the memory. This reduces the amount of temporary storage which needs to be provided for the input values when they are retrieved from the memory.

"The fixed order in which the plurality of input values are processed when they have floating point formats may be such that in some embodiments the processing circuitry is configured to wait until all of the plurality of input values have been retrieved from the memory before commencing to compute the one or more result values in accordance with the processing in the fixed order.

"The load circuitry may store the plurality of input values in a cache memory when they are retrieved from the memory (the memory may be a memory system, including higher levels of cache memory, main volatile memory and potentially further non-volatile memory) and the processing circuitry may read the input values from this cache memory.

"The input values may be separately locked within the cache memory when they are stored in to the cache memory by the load circuitry. Each of the input values may then be separately unlocked within the cache memory when processing of that input value by the processing circuitry is finished. In this way, the input values are unlocked within the cache memory as soon as they are no longer required thus releasing space within the cache memory for the use by other data.

"In order that the processing circuitry may determine when input values have been retrieved from memory, the load circuitry may be configured to set one or more flag bits associated with respective ones of the input values to indicate to the processing circuitry when each of the respective input values has been retrieved from the memory. The processing circuitry may examine these flag bits to determine when an input value is ready for the processing even when this has been received out-of-order with respect to the order in which those input values were requested from the memory.

"The cache memory may have a plurality of cache lines in which an individual input value is stored either in a single cache line or spread across two cache lines. The flag bits set by the load circuitry may provide a flag bit for each cache line indicating that at least a portion of a respective one of the plurality of input values is stored within that cache line.

"The present techniques may be applied in a variety of different processing fields. However, the field of graphics processing units is particularly data intensive and uses both integer format values and floating bit format values. In particular, the processing circuitry may be a texture pipeline within a graphics processing unit.

"The graphics processing unit may perform filtering operations which require relatively large numbers of input values to be retrieved from memory. For example, the texture pipeline may be configured to perform a bilinear filtering operation upon four input texture values, possibly in a single pass through the texture pipeline, or a trilinear filtering operation upon eight input texture values, possibly in two passes through the texture pipeline with one or more result values being accumulated upon each pass. It is also possible that the filtering operation is an anisotropic filtering operation performed upon 4N input texture values, where N is an integer value greater than 2, in possibly N passes through the texture pipeline with result values being accumulated upon each pass.

"When more than one pass through the texture pipeline is employed with texture values that are integer format values, then the texture values may be divided in to groups of four texture values in dependence upon the order in which the texture values are retrieved from the memory. Thus, as texture values are retrieved they may be collected in to groups of four and dispatched for processing through the texture pipeline without waiting for later arriving texture values. This reduces the storage requirements for the texture values and improves the speed with which the final result will be achieved.

"Viewed from another aspect the present invention provides apparatus for processing data comprising:

"processing means for computing one or more result values as a function of a plurality of input values;

"memory means for storing said plurality of input values;

"load means for issuing one or more memory access requests to said memory means to retrieve said plurality of input values from said memory means and to supply said plurality of input values to said processing means; wherein

"said plurality of input values are retrieved in a variable order from said memory means; and

"said processing means is configured such that:

"(i) when said plurality of input values are integer format values, said processing means performs processing upon said plurality of input values to compute said one or more result values in a variable order that is dependent upon said variable order in which said plurality of input values are retrieved from said memory means; and

"(ii) when said plurality of input values are floating point format values, said processing means performs processing upon said plurality of input values to compute said one or more result values in a fixed order that is independent of said variable order in which said plurality of input values are retrieved from said memory means.

"Viewed from a further aspect the present invention provides a method of processing data comprising the steps of:

"storing a plurality of input values within a memory;

"issuing one or more memory access requests to said memory to retrieve said plurality of input values from said memory means; and

"computing one or more result values as a function of a plurality of input values; wherein

"said plurality of input values are retrieved in a variable order from said memory means; and

"said processing means is configured such that:

"(i) when said plurality of input values are integer format values, performing processing upon said plurality of input values to compute said one or more result values in a variable order that is dependent upon said variable order in which said plurality of input values are retrieved from said memory; and

"(ii) when said plurality of input values are floating point format values, performing processing upon said plurality of input values to compute said one or more result values in a fixed order that is independent of said variable order in which said plurality of input values are retrieved from said memory.

"The above and other objects, features and advantages of this invention will be apparent from the following detailed description of illustrative embodiments which is to be read in connection with the accompanying drawings."

For more information, see this patent: Engh-Halstvedt, Andreas Due; Nystad, Jorn. Processing Order with Integer Inputs and Floating Point Inputs. U.S. Patent Number 8766991, filed May 25, 2011, and published online on July 1, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8766991.PN.&OS=PN/8766991RS=PN/8766991

Keywords for this news article include: ARM Limited, Information Technology, Information and Data Processing.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters