Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1-2, 7-11, and 16-20 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Burkhard (US 5924091 A).
Regarding claim 1, Burkhard teaches an apparatus for graphics processing, comprising:
a memory (col. 5, line 66 – col. 6, line 5: “The invention may be embodied on a computer system such as the system 100 of FIG. 1A, which comprises a central processor 101, a main memory 102, an input/output controller 103, a keyboard 104, a pointing device 105 (e.g., mouse, track ball, pen device, or the like), a screen display device 106, and a mass storage 107 (e.g., hard or fixed disk, optical disk, magneto-optical disk, or flash memory).”); and
a processor coupled to the memory (col. 5, line 66 – col. 6, line 5, as above) and, based at least in part on information stored in the memory, the processor is configured to:
compute a plurality of histograms by counting radix digits of a set of data (col. 30, lines 55-59: “In the event that the method has not reverted to simple insert sort, the method continues on to line 31 for undertaking radix sorting. Here, the method will undertake to compute histograms based on the size of the radix. Since the preferred embodiment employs a radix of 8, these histograms will be referred to as "character histograms."”; col. 31, lines 10-18: “Now, the method will construct a character histogram--that is, how many counts of each bit pattern exist in the bin for a particular set of bits under examination. Here, the method is interested in finding that set of bits which has the lowest number of elements in it. Because the radix employed is radix 8, at most 256 unique values can exist for a given set of bits. The method proceeds by subdividing the data into various bins and tracks which group has the least number of members.”);
determine a plurality of global offsets over the computed plurality of histograms (col. 31, lines 4-9: “At lines 38-39, the offset and compare type data members from the appropriate sort plan entry are read into local variables, offset and cmptype. In other words, from the sort plan index the method can determine where to look in the record (i.e., offset) and what type of comparison is required (cmptype).”);
determine a plurality of local offsets based on the plurality of global offsets or refrain from determining the plurality of local offsets based on the plurality of global offsets (col. 21, line 60 – col. 22, line 46: “Depending on data type, the length offset (i.e., .sub.-- lenoffset) data member and current length (i.e., .sub.-- curlen) data member are filled in as well. For character types, for instance, this information is filled in at lines 43-44. For an integer type, on the other hand, the information is not required and is, therefore, not filled in (as illustrated by the integer case arm at lines 63-68). At the conclusion of the switch or case statement (of lines 32-83), the comparison type and offset data members of the sort plan have been appropriately filled out. If required (based on type), the length offset and current length data members are filled in as well.”));
sort the set of data based on the plurality of global offsets and the plurality of local offsets (col. 21, lines 48-59: “At line 32, a switch statement is established which switches on data type (i.e., .sub.-- type). Here, the comparison type and offset data members of the sort plan are filled out, based on the particular type of the key. For instance, a character data type (tested at line 33) or a variable-length character data type (tested at line 34), lead to the constructor storing a comparison type (i.e., .sub.-- cmptype) of HS.sub.-- UNSIGNED at line 36 for a fixed-length character string (tested at line 35), or storing a comparison type of HS.sub.-- VARCHAR (at line 39). Additionally, the passed-in offset (i.e., the offset passed-in to the constructor) is stored in the sort plan offset data member (e.g., at line 37).”); and
output an indicator of the sorted set of data (col. 6, lines 23-25: “The system also includes a user interface 160 for receiving user commands as input and displaying user data as output.”).
Regarding claim 2, Burkhard teaches the apparatus of claim 1, wherein, to compute the plurality of histograms by counting the radix digits of the set of data and to determine the plurality of global offsets over the computed plurality of histograms, the processor is configured to:
execute a kernel based on the set of data to compute the plurality of histograms and determine the plurality of global offsets (col. 6, lines 18-23: “Software system 150, which is stored in system memory 102 and on disk memory 107, includes a kernel or operating system (OS) 140 and a windows shell 145. One or more application programs, such as application software 155, may be "loaded" (i.e., transferred from storage 107 into memory 102) for execution by the system 100.”).
Regarding claim 7, Burkhard teaches the apparatus of claim 1, wherein, to compute the plurality of histograms by counting the radix digits of the set of data, the processor is configured to:
split the set of data into a plurality of bit segments having a threshold number of bits (col. 5, lines 1-7: “The sort plan itself is broken down into an array of entries; each entry describes the number of bits to examine (e.g., the number 8 for a radix 8 sort), together with information on how to interpret the bits. The group of bits (radix) can be an arbitrary number of bits, for instance, ranging from 8 to 32 bits.”); and
count the threshold number of bits of the radix digits of the set of data for each pass of the plurality of bit segments (col. 31, lines 10-14: “Now, the method will construct a character histogram--that is, how many counts of each bit pattern exist in the bin for a particular set of bits under examination. Here, the method is interested in finding that set of bits which has the lowest number of elements in it.”).
Regarding claim 8, Burkhard teaches the apparatus of claim 1, wherein, to output the indicator of the sorted set of data, the processor is configured to at least one of:
store the indicator of the sorted set of data (col. 3, lines 34-40: “With quicksort, a value or "comparand" is selected for partitioning the array into two parts. Those elements having a value greater than or equal to the partition value are stored on one side, and those having a value less than the partition value are stored on the other side. The process is repeated for each remaining part until the array is sorted; as such, the process is essentially recursive.”); or
transmit the indicator of the sorted set of data (col. 6, lines 20-23: “One or more application programs, such as application software 155, may be "loaded" (i.e., transferred from storage 107 into memory 102) for execution by the system 100.”).
Regarding claim 9, Burkhard teaches the apparatus of claim 1, wherein, to determine the plurality of global offsets over the computed plurality of histograms and to determine the plurality of local offsets or refrain from determining the plurality of local offsets, the processor is configured to:
calculate the plurality of global offsets over the computed plurality of histograms (col. 30, line 55 – col. 31, line 9: “In the event that the method has not reverted to simple insert sort, the method continues on to line 31 for undertaking radix sorting. Here, the method will undertake to compute histograms based on the size of the radix. Since the preferred embodiment employs a radix of 8, these histograms will be referred to as "character histograms." If the method has at this point examined all the keys (i.e., keynum is equal to .sub.-- keysize, tested at line 34), then the method has completed its comparison for this bin. This is indicated by setting bin number 0 (i.e., a reserved bin) to rows, thereby marking the end. Otherwise, the method proceeds to the "else" statement beginning at line 36.
At this point, a radixsort is to be performed, therefore the method refers to the sort plan for determining how to interpret the bits. Specifically, at line 37, the method grabs an index from the MSD array (using keynum), for determining which sort plan entry to use.
At lines 38-39, the offset and compare type data members from the appropriate sort plan entry are read into local variables, offset and cmptype. In other words, from the sort plan index the method can determine where to look in the record (i.e., offset) and what type of comparison is required (cmptype).”); and
calculate the plurality of local offsets or refrain from calculating the plurality of local offsets (col. 22, lines 44-45: “If required (based on type), the length offset and current length data members are filled in as well.” NOTE: “If required” here is interpreted as meaning there are circumstances wherein the offsets may or may not be calculated.).
Claim 10 is substantially similar to claim 1, and differs primarily in that it teaches a method, rather than an apparatus. It is therefore rejected on a similar basis to claim 1.
Claim 11 is substantially similar to claim 2, and differs primarily in that it depends on claim 10, as opposed to claim 1. It is therefore rejected on a similar basis to claim 2.
Claim 16 is substantially similar to claim 7, and differs primarily in that it depends on claim 10, as opposed to claim 1. It is therefore rejected on a similar basis to claim 7.
Claim 17 is substantially similar to claim 8, and differs primarily in that it depends on claim 10, as opposed to claim 1. It is therefore rejected on a similar basis to claim 8.
Claim 18 is substantially similar to claim 9, and differs primarily in that it depends on claim 10, as opposed to claim 1. It is therefore rejected on a similar basis to claim 9.
Claim 19 is substantially similar to claim 1, and differs primarily in that it teaches a computer-readable medium storing computer executable code, rather than an apparatus. It is therefore rejected on a similar basis to claim 1.
Claim 20 is substantially similar to claim 2, and differs primarily in that it depends on claim 19, as opposed to claim 1. It is therefore rejected on a similar basis to claim 2.
Allowable Subject Matter
Claims 3-6 and 12-15 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Regarding claim 3, no sources found in the field of endeavor of image data processor architectures make mention of refraining from determining a plurality of local offsets in response to a performed reduction indicating a uniformity. It is the opinion of the examiner that this element of claim 3 is both necessary to the claimed invention and unique enough to constitute patentable subject matter.
Claim 4 depends from claim 3, and is therefore allowable for similar reasons to claim 3.
Regarding claim 5, no sources found in the field of endeavor of image data processor architectures make mention of executing a plurality of kernels to determine the plurality of local offsets in response to a performed reduction indicating a non-uniformity. It is the opinion of the examiner that this element of claim 5 is both necessary to the claimed invention and unique enough to constitute patentable subject matter.
Claim 6 depends from claim 5, and is therefore allowable for similar reasons to claim 5.
Claim 12 is substantially similar to claim 3, and differs only in that it depends from the method of claim 10 rather than the apparatus of claim 1. As such, it is considered in condition for allowance for similar reasons to claim 3.
Claim 13 is substantially similar to claim 4, and differs only in that it depends from the method of claim 12 rather than the apparatus of claim 3. As such, it is considered in condition for allowance for similar reasons to claim 4.
Claim 14 is substantially similar to claim 5, and differs only in that it depends from the method of claim 10 rather than the apparatus of claim 1. As such, it is considered in condition for allowance for similar reasons to claim 5.
Claim 15 is substantially similar to claim 6, and differs only in that it depends from the method of claim 14 rather than the apparatus of claim 5. As such, it is considered in condition for allowance for similar reasons to claim 6.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RYAN A BARHAM whose telephone number is (571)272-4338. The examiner can normally be reached Mon-Fri, 8:30am-5pm EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Xiao Wu, can be reached at (571) 272-7761. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/RYAN ALLEN BARHAM/Examiner, Art Unit 2613
/XIAO M WU/Supervisory Patent Examiner, Art Unit 2613