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 § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-12, 14, 17- is/are rejected under 35 U.S.C. 103 as being unpatentable over Kipnis et al [hereinafter Kip] (US PG PUB 20130254441) in further view of Agrawal (US PG PUB 20240094908).
As per Claim 1, 12, 17, 18, 21 Kip discloses, hardware for performing multiple compression algorithms that compress data exhibiting different types of data redundancy patterns (The ECC encoder 112 may be configured to encode data using an ECC encoding scheme, such as a Reed Solomon encoder, a Bose-Chaudhuri-Hocquenghem (BCH) encoder, a low-density parity check (LDPC) encoder, a Turbo Code encoder, an encoder configured to encode according to one or more other ECC encoding schemes, or any combination thereof. The ECC encoder 112 may be configurable to apply different ECC encoding schemes based on a size of the data. For example, the ECC encoder 112 may be configurable to apply a first encoding scheme to uncompressed data, or to apply a second, more powerful encoding scheme using more parity bits, to compressed data. 0019) a memory; one or more in-memory processors; and a host processor to:” (The data storage device 106 may be a memory card, such as a Secure Digital SD® card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). As another example, the data storage device 106 may be configured to be coupled to the host device 104 as embedded memory, such as eMMC® (trademark of JEDEC Solid State Technology Association, Arlington, Va.) and eSD, as illustrative examples. 0115) issue processing-in-memory requests instructing the one or more in- memory processors to scan a block of the memory for one or more to identify a type of data redundancy patterns pattern of the different types of data redundancy patterns” (The compression method, if any, to be applied to the data set 102 may be selected based upon the estimated compression ratio 144. 0018 The ECC encoder 112 may be configurable to apply different ECC encoding schemes based on a size of the data. For example, the ECC encoder 112 may be configurable to apply a first encoding scheme to uncompressed data, or to apply a second, more powerful encoding scheme using more parity bits, to compressed data. 0019), and identify a compression algorithm of the multiple compression algorithms based on the one or more data redundancy patterns corresponding to the type of data redundancy pattern(Also, the ECC encoder 112 may determine a type of error encoding to apply to a representation 130 of the data set 102 based on the estimated compression ratio 144. 0021); and issue a memory request to access a memory address in the block of the memory, the memory request causing data of the memory address to be communicated from the block of the memory to the reconfigurable hardware device to be compressed using the compression algorithm (The ECC encoder 112 may receive the estimated compression ratio 144 from the compression ratio estimator 140, and the ECC encoder 112 or the controller 110 may determine the type of error correction code encoding to be applied to the data set 102 based on the estimated compression ratio 144. The output of the ECC encoder 112 may be the encoded representation 132 of the data set 102, which may be stored in the memory 108. 0025)
Agrawal discloses, “computing device, comprising: a reconfigurable hardware device having reconfigurable hardware for performing multiple compression algorithms that compress data exhibiting different types of data redundancy patterns” (An embodiment wherein at least one of the write engine and the compression engine is implemented using a Field Programmable Gate Array (FPGA) ... 0162)
Kip and Agrawal are analogous art because they are from the same field of endeavor, that being memory devices. It would have been obvious to one having ordinary skill in the art before the effective filing date of the claimed invention to modify the computing device disclosed by Kip to use the FPGA reconfigurable hardware of Argawal. The motivation would have been to improve utilize the very well known technique of FGPA and reconfigurable hardware for implementing the compression engine. (the compression engine is implemented using a Field Programmable Gate Array (FPGA) 0162)
Additional unpatentable claim elements of Claim 12 are disclose as indicated by rejections presented below for Claim 9 and 10.
As per Claim 2, 14, 19 Kip discloses, The computing device of claim 1, wherein the processing-in-memory requests further instruct the one or more in-memory processors to store, in a compressibility check region of the memory, metadata indicating the compression algorithm and a compressibility of the data in the block of the memory (Further, because the compressor 114 may include circuitry to generate hash values (that can be used to determine an estimated compression ratio, a type of compression to apply to the data set 102, and/or a type of ECC encoding to apply), the compression ratio estimator 140 may be implemented using existing processing hardware for reduced cost of manufacturing and die area savings, as described in further detail with respect to FIG. 2 0026)
As per Claim 3, Kip discloses, wherein the computing device further includes a memory controller, and the memory request causes the memory controller to: read the data of the memory address from the block of the memory; read the metadata from the compressibility check region; and issue, based on the compressibility indicating that the data is compressible, a compression request including the data and the metadata to the reconfigurable hardware device, the compression request instructing the reconfigurable hardware device to compress the data using the compression algorithm (processing a data set prior to storage in a memory of a data storage device. An estimated compression ratio is determined that is associated with applying compression to the data set, at 502. The estimated compression ratio is based on hash values of a subset of the data set. For example, the subset may include fewer data elements than a count of data elements in the data set. The data set may be processed prior to storage in a memory of a data storage device and the processing is determined based on the estimated compression ratio, at 504. For example, processing may be determined to include data compression prior to error encoding, or processing may include performing error correction code encoding prior to storage in the data storage device without compressing the data set prior to performing the error correction code encoding 0053)
As per Claim 4, Kip discloses, wherein the host processor is configured to issue the processing-in-memory requests based on a workload or a phase of the workload accessing the block of the memory (The controller 110 may receive the data set 102, e.g., from a host device such as the host device 104 of FIG. 1. The data set 102 may be input to the hash value generator 216. The hash value generator 216 may generate a plurality of hash values based on the data set 102. For example, the hash value generator 216 may be configurable to generate a hash value corresponding to each data element of a subset of the data set, such as the subset 142 of the data set 102 of FIG. 1 0028)
A per Claim 5, Kip discloses, wherein the host processor is configured to issue the processing-in-memory requests preemptively before the host processor begins executing the workload or the phase of the workload based on one or more memory access patterns associated with the workload (The estimated compression ratio calculator 218 may determine an estimated compression ratio based on the tally of hash value collisions received from the hash value collision counters 232. For example, the higher the number of collisions counted, the greater the estimated compression ratio. The counts of the collisions of the hash values 230 of the subset 142 of the data set 102 may be used to calculate the estimated compression ratio 144 of FIG. 1. For example, the estimated compression ratio may be calculated by comparing the number of collisions to an expected number of collisions in a uniform distribution of data values. 0031)
As per Claim 6, Kip discloses, wherein to identify the compression algorithm, the one or more in-memory processors are configured to scan a sub-region of the block of the memory, and identify the compression algorithm that is applicable to the block of the memory based on the type of data redundancy pattern exhibited by the sub-region (For example, the subset of the data set 302 may be selected to include data elements Cm, Cn, and Cp. In an embodiment, the data elements selected to be included in the subset of the data set 302 may be uniformly selected from all data elements of the data set 302 0039)
As per Claim 7, Kip discloses, wherein to identify the compression algorithm, the one or more in-memory processors are configured to scan a subset of memory rows in the block of the memory, and identify the compression algorithm that is applicable to the block of the memory based on the type of data redundancy pattern exhibited by the subset of memory rows (The estimated compression ratio 144 may be determined from the subset 142 of the data set 102, and the estimated compression ratio 144 may be output from the compression ratio estimator 140 to a compressor 114. (0017)
As per Claim 8, Kip discloses, wherein to scan the block of the memory, the one or more in-memory processors are configured to scan at least a portion of a memory row in the block of the memory across multiple banks of the memory (For example, the subset of the data set 302 may be selected to include data elements Cm, Cn, and Cp. In an embodiment, the data elements selected to be included in the subset of the data set 302 may be uniformly selected from all data elements of the data set 302 0039)
Agrawal discloses, in parallel (Such multiple compression/decompression operations might be performed in parallel using multiple compression engines 430 of FIG. 4/decompression engines 450 of FIG. 5, to re duce latency. 0103)
Kip and Agrawal are analogous art because they are from the same field of endeavor, that being memory devices. It would have been obvious to one having ordinary skill in the art before the effective filing date of the claimed invention to modify the computing device disclosed by Kip to use the FPGA reconfigurable hardware of Argawal which can implement compression/decompression in parallel . The motivation would have been to improve utilize the very well known technique of FGPA and reconfigurable hardware for implementing the compression engine. (the compression engine is implemented using a Field Programmable Gate Array (FPGA) 0162 Such multiple compression/decompression operations might be performed in parallel using multiple compression engines 430 of FIG. 4/decompression engines 450 of FIG. 5, to re duce latency. 0103)
As per Claim 9, Kip discloses, receive, from the reconfigurable hardware device, compressed data including the data as compressed using the compression algorithm; and store, the compressed data and metadata indicating the compression algorithm. (The compressor 114 may be configured to compress a data set, such as the data set 102, according to a selected compression method or according to a combination of compression methods. The compression method, if any, to be applied to the data set 102 may be selected based upon the estimated compression ratio 144. By compressing the data set 102 to form a representation 130 of the data set 102 and storing the representation 130 of the data set 102, less space may be occupied in the memory 108 than if the (uncompressed) data set 102 had been stored. 0018)
Agrawal discloses, wherein the host processor is further configured to: … in a cache of the host processor (Compression engine 430 may test compression algorithms against the data (or compressible units of the data) while the data sits in buffer 435, and/or compress the data while the data sits in buffer 435. Once the data is compressed, compression engine 430 may transfer the data to the memory of appliance 305. 0079 Once the device address where the data is stored and the compression type of the data is known, decompression engine 450 may read the data from the device address in the memory of appliance 305 and decompress it according to the compression type. 0083)
Kip and Agrawal are analogous art because they are from the same field of endeavor, that being memory devices. It would have been obvious to one having ordinary skill in the art before the effective filing date of the claimed invention to modify the computing device disclosed by Kip to use the FPGA reconfigurable hardware of Argawal implemented at the host. The motivation would have been to improve utilize the very well known technique of FGPA and reconfigurable hardware for implementing the compression engine at the memory itself as in Kip or at the host as in Argawal. (Fig 4. Aside from writing data to appliance 305, applications may also want to read data from appliance 305. 0082-004)
As per Claim 10, Kip and Argawal discloses, the compressed data to the reconfigurable hardware device, thereby causing the reconfigurable hardware device to generate decompressed data by decompressing the compressed data using the compression algorithm indicated by the metadata. (The compressor 114 may be configured to compress a data set, such as the data set 102, according to a selected compression method or according to a combination of compression methods. The compression method, if any, to be applied to the data set 102 may be selected based upon the estimated compression ratio 144. By compressing the data set 102 to form a representation 130 of the data set 102 and storing the representation 130 of the data set 102, less space may be occupied in the memory 108 than if the (uncompressed) data set 102 had been stored. 0018)
Argawal discloses “wherein the host processor is configured to: receive an additional memory request to access the memory address; and communicate, based on the memory address hitting in the cache (and communicate, based on the memory address hitting in the cache, (An SRAM Cache may be used for read-modify-write (RMW) of compressed data, and to store an uncompressed copy of the compressed data. 0131)
Kip and Agrawal are analogous art because they are from the same field of endeavor, that being memory devices. It would have been obvious to one having ordinary skill in the art before the effective filing date of the claimed invention to modify the computing device disclosed by Kip to use the FPGA reconfigurable hardware of Argawal implemented at the host using a cache. The motivation would have been to improve utilize the very well known technique of FGPA and reconfigurable hardware for implementing the compression engine at the memory itself as in Kip or at the host as in Argawal. (An SRAM Cache may be used for read-modify-write (RMW) of compressed data, and to store an uncompressed copy of the compressed data. 0131)
As per Claim 11, Kip and Agrawal disclose, wherein the host processor is configured to: receive, from the reconfigurable hardware device, the decompressed data; and store, in an additional cache of the host processor, the decompressed data(An SRAM Cache may be used for read-modify-write (RMW) of compressed data, and to store an uncompressed copy of the compressed data. 0131) It would have been obvious for one of ordinary skill in the art to utilize the well known technique of multiple caches to stores various data in a processor.
As per claim 22, Kip discloses, wherein the block of memory exhibits, as the redundancy patterns, repeated values or repeated patterns of values. (ne technique to compress data is to create a data representation from which redundant portions have been removed. For example, a data set may include a plurality of data elements in a string, and a portion of one or more of the data elements may be identical. A data representation of the data set may be formed by eliminating redundant (identical) data portions of the data set. The representation of the data set can be stored and upon request, such as a read request, the data set can be reconstituted to its original form by replacing the redundant portions that were removed in order to form the representation of the data set. 0003)
As per Claim 23, Kip discloses, wherein the computing device includes a memory module, the memory is mounted on the memory module, and the one or more in-memory processors are embedded within the memory module (The data storage device 106 may be a memory card, such as a Secure Digital SD® card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). As another example, the data storage device 106 may be configured to be coupled to the host device 104 as embedded memory, such as eMMC® (trademark of JEDEC Solid State Technology Association, Arlington, Va.) and eSD, as illustrative examples. 0115)
Claim(s) 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Kipnis et al [hereinafter Kip] (US PG PUB 20130254441) in further view of Agrawal (US PG PUB 20240094908) and in further view of Kever (US PG PUB US20030131184)
As per Claim 15, Kever discloses wherein to communicate the compressed data, the host processor is configured to identify the compressed data within a cache line of the cache based on the size of the compressed data (That is, the number of available tags is predetermined by a size of a tag array used to reference the cache data array. If data were to be stored in compressed form in a cache data array, a tag structure for such a cache would include enough entries to represent all lines of data that might be present in the data array. For example, if two or fewer lines of data could be packed into a data storage line that would fit one uncompressed line of data, a tag structure would need twice as many entries as would be needed for a cache with no compression. 0019 For example, if a compression ratio of 0.5 or 0.25 is allowed, four times as many elements 254 would be used as for storing an uncompressed data array in the cache 200. In embodiments in which up to four lines of compressed data could be compressed into one data storage line 238, lines of data 226 could occupy 0.25, 0.5, or 0.75 of a data storage line 238 0033)
Kip, Agrawal, and Kever are analogous art because they are from the same field of endeavor, that being memory devices. It would have been obvious to one having ordinary skill in the art before the effective filing date of the claimed invention to modify the computing device disclosed by Kip and Argawal to use a cache line method of storing compressed data indicated by compressed size from the teachings of Kever. The motivation would have been to improve utilize the well known technique of cache line compression and tag line identification based on size from Kever. (if two or fewer lines of data could be packed into a data storage line that would fit one uncompressed line of data, a tag structure would need twice as many entries as would be needed for a cache with no compression. 0033)
Response to Arguments
Applicant’s arguments with respect to claim(s) have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KENNETH M LO whose telephone number is (571)272-9774. The examiner can normally be reached M-F 830a - 6pm.
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, John Cottingham can be reached at 571-272-9877. 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.
KENNETH M. LO
Supervisory Patent Examiner
Art Unit 2136
/KENNETH M LO/ Supervisory Patent Examiner, Art Unit 2116
Prosecution Insights