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 .
This Office Action is in response to Applicant’s preliminary amendment submitted on 12/5/2023. By this amendment claims 2-6, 8-10, 12-13, and 15 are amended. Therefore, claims 1-15 have been examined
Priority
Acknowledgment is made of applicant’s claim for foreign priority under 35 U.S.C. 119 (a)-(d). The certified copy has been filed in parent Application No. EP21182331, filed on 29 June 2021.
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-4, 6-8, 10-11, and 14-15 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20090249356 A1 (hereinafter referred to as He) in view of “mpmc_bounded_queue.h” (pub. 2017, hereinafter referred to as Craflin).
As per claim 1 – He teaches an electronic system comprising: a producer of a sequence of work items (Multiprocessing system 101 further includes multiprocessor 160, which for example, may include a producer thread 163 of processor 161 and a consumer thread 164 of processor 162 – [0018]) a circular buffer for queueing the work items produced by the producer (FIG. 1 illustrates one embodiment of a multiprocessing system 101 using a lock-free circular queue for inter-thread communication – [0016]) and a consumer of the work items from the circular buffer (Multiprocessing system 101 further includes multiprocessor 160, which for example, may include a producer thread 163 of processor 161 and a consumer thread 164 of processor 162 – [0018]) wherein: the circular buffer comprises a plural number of slots for queuing the work items in a queue (Multiprocessing system 101 includes local memory bus(ses) 170 coupled with an addressable memory 110 to store data 112-115 in a circular queue 11 including queue tail index 119 and queue head index 116, and also to store machine executable instructions for accessing the circular queue 111 – [0016]).
He does not teach these limitations:
each slot in the circular buffer comprising a descriptor field for holding one work item and a sequence number field for holding a corresponding sequence number indicating how many work items came before in the sequence from the producer; the circular buffer further comprises a head field arranged to hold a head sequence number specifying the sequence number of the head slot, and a tail field arranged to hold a tail sequence number specifying the sequence number of the tail slot; the producer is configured so as, in order to enqueue a new work item into the queue, to increment the tail sequence number in the tail field, and write the new work item to the slot that was the tail slot prior to the increment of the tail sequence number.
However, Craflin, in an analogous art, teaches them as can be seen in the in-line citations below:
each slot in the circular buffer comprising a descriptor field for holding one work item and a sequence number field for holding a corresponding sequence number indicating how many work items came before in the sequence from the producer (Lines 34-45 and 117-121; Lines 34-45 teach the initialization of a queue of cell_t type items, which are shown to have associated sequence and data fields in lines 117-121. Each cell of the queue contains a sequence and data field, which store the data and sequence number for whichever task is supposed to be stored in the cell. The sequence number indicated how many work items came before it because it was directly determined through the enqueue_pos field of the queue, which stores a running total of the number of tasks to be enqueued); the circular buffer further comprises a head field arranged to hold a head sequence number specifying the sequence number of the head slot, and a tail field arranged to hold a tail sequence number specifying the sequence number of the tail slot (Lines 128 and 130; These lines teach an enqueue and dequeue position, which correspond to the “head” and “tail” fields of the claim limitation); the producer is configured so as, in order to enqueue a new work item into the queue, to increment the tail sequence number in the tail field, and write the new work item to the slot that was the tail slot prior to the increment of the tail sequence number (Lines 75-76 and 84; Lines 75-76 demonstrate a CAS function that increments the enqueue position to if it the position is as expected. The push function corresponds to the primary function of the “producer” of the claim limitation; Line 84 shows storing the data in the data field of the cell that corresponded to the enqueue position before the CAS increment, which corresponds to “write the new work item to the slot that was the tail slot prior to the increment of the tail sequence number”) and the consumer is configured to track, based on how many work items in the sequence the consumer has consumed from the queue so far, a next expected sequence number being the sequence number of the work item to consume next (Lines 89-114; Line 92 teaches obtaining pos from dequeue_pos, which corresponds to “a next expected sequence number”); the consumer being configured so as, in order to consume a next work item from the work queue, to poll the sequence number of the head slot to check whether it equals the expected sequence number, and on condition thereof consume said next work item (Lines 89-114; Line 98 teaches calculating the difference between the current number in the sequence and the current dequeue position sequence number, which corresponds to the limitation).
Therefore, it would have been obvious for one of ordinary skill in the art before the effective filing date to implement the sequencing number checking method of Craflin to the overall consumer message receiving process taught in He. This combination would have been obvious to one of ordinary skill in the art at the time of filing because the process of the consumers checking sequence numbers allows the circular buffer to be lock free, which improves overall efficiency.
As per claim 2 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches:
wherein each of the slots in the circular buffer has an associated index i, and in order to perform said write, the producer is configured to determine the index i_w of the slot to which to perform the write by: i_w equals S tail modulo N, where S_tail is the sequence number of the slot that was the tail slot prior to the increment of the tail sequence number, and N is the number of slots in the circular buffer (Line 69; Line 69 teaches determining the cell to push the data to using the enqueue position and a buffer mask, which is used to account for the circular nature of the queue. This corresponds to the limitations of the claim).
As per claim 3 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches:
wherein the consumer is configured to perform the consuming of the next work item by: servicing the next work item from the descriptor field of the head slot, and incrementing the head sequence number to mark the head slot as consumed (Lines 89-113; These lines teach a pop function of the circular queue. This function increments the dequeue position, which corresponds to the “head” of the claim, and storing the data from the current cell into an argument to the pop function to be serviced later. This process corresponds to the process described in the claim limitation).
As per claim 4 – The combination of He and Craflin teach the system of claim 3. Craflin further teaches:
wherein: each of the slots in the circular buffer has an associated index i; the circular buffer is arranged to be initialized with a respective sequence number S in the sequence number field of each slot such that S modulo N does not equal i, where N is the number of slots in the circular buffer; and order to perform said consuming of the next data item, the consumer is configured to determine the index i_c of the slot from which to consume by: i_c = S_head modulo N, where S_head is the sequence number of the head slot prior to the increment of the head sequence number (Line 95; pos & buffer_mask results in the index in the queue to be popped from, which teaches the claim limitation).
As per claim 6 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches:
wherein the increment of the tail sequence number is atomic (Lines 75-76; The compare_exchange_weak function is atomic).
As per claim 7 – The combination of He and Craflin teach the system of claim 6. Craflin further teaches:
wherein the producer is configured to perform the increment of the tail sequence number by a compare-and-swap instruction which: takes as arguments I) an address of the tail slot, II) an old, expected value of the tail sequence number, and III) a new, incremented value; and atomically compares the old value with the value in the address, and if they are the same replace the value in the address with the new value (Lines 63 – 87; The compare_exchange_weak function called on line(s) 75-76 performs the process mentioned in claim 7, with enqueue_pos_ corresponding to “the address of the tail slot” and the arguments pos and pos + 1 corresponding to “an old, expected value of the tail sequence number” and “a new incremented value” respectively).
As per claim 8 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches:
wherein the producer comprises multiple producing entities, each being configured to produce and enqueue a respective one or more of the sequence of work items (Line 1 of Craflin explicitly states it is code for a multi-producer/multi-consumer bounded queue. The multi-producer nature is further taught by the use of atomic CAS operations, which only serve a purpose with multiple consumers/producers) by performing, for each of the respective one or more work items, a respective instance of said incrementing of the tail sequence number and then afterwards said writing of the work item; the incrementing of the tail sequence number thereby reserving, for the respective producing entity, the slot that was the tail slot prior to the increment (Lines 63-87; The push function of Craflin teaches the CAS operation on line 75-76 and the writing of the work item on line 84).
As per claim 10 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches:
wherein the producer is configured to check whether there is room in the circular buffer before the enqueuing of the new work item, and to perform the enqueuing on condition thereof; the producer being configured to perform said check by: checking that the head sequence number in the head field plus the number of slots in the circular buffer is greater than the tail sequence number in the tail field (Lines 63-87; On line 72, the difference between the enqueue position and the sequence number of the corresponding cell in the queue. If the sequence number is smaller, it means the queue is full and a Boolean value of false is returned for the function. This is effectively teaching the process of the claim).
As per claim 11 – The combination of He and Craflin teach the system of claim 10. Craflin further teaches:
wherein the producer is configured to determine whether said increment is successful, and to perform the write on condition thereof, but otherwise loop back to checking whether there is room in the circular buffer (Lines 73-83; These lines teach attempting to perform a CAS operation and, if the operation fails, obtaining a new enqueue position and attempting the process again).
As per claim 14 – The limitations of claim 14 are identical to those of claim 1. Therefore, claim 14 is rejected under the same basis as claim 1.
As per claim 15 – The limitations of claim 15 are identical to those of claim 1. Therefore, claim 15 is rejected under the same basis as claim 1.
Claim(s) 5 is/are rejected under 35 U.S.C. 103 as being unpatentable over He in view of Craflin further in view of US 20190065371 A1 (hereinafter referred to as Tsirkin).
As per claim 5 – The combination of He and Craflin teach the system of claim 1. It does not teach the following limitation:
wherein the consumer is configured to consume a group of n next work items, n being greater than 1 by: servicing the n work items before incrementing the head sequence number, and then incrementing the head sequence number by n in a single increment.
However, Tsirkin, in an analogous art, teaches it as can be seen in the in-line citation below:
wherein the consumer is configured to consume a group of n next work items, n being greater than 1 by: servicing the n work items before incrementing the head sequence number, and then incrementing the head sequence number by n in a single increment (Fig. 4; The loop of Figure 4 demonstrates retrieving the memory entry for a specified number of slots and incrementing the head pointer by the specified amount).
Therefore, it would have been obvious for one of ordinary skill in the art before the effective filing date to include the method of consumers processing batches of slots of Tsirkin to the consuming process already taught by He and Craflin. This modification would have been obvious to one of ordinary skill in the art at the time of filing because of the mentioned benefit in Tsirkin of “reduced cache line bounces” and “preventing slowdown while waiting for cache invalidation” (Tsirkin, [0018]).
Claim(s) 9 is/are rejected under 35 U.S.C. 103 as being unpatentable over He in view of Craflin further in view of US 6725296 B2 (hereinafter referred to as Craddock).
As per claim 9 – The combination of He and Craflin teach the system of claim 1. Craflin further teaches wherein:
each work item comprises a pointer to a respective piece of target data in memory, to be operated upon by the work item (One or ordinary skill in the art will understand that the data stored in the cell structs are pointers to locations in memory).
It does not teach:
the consumer is configured to post, after having serviced a work item, an acknowledgment of completion to a memory location at or adjacent to an address of the respective target data in memory; and the producer is configured to read the acknowledgement from said memory location.
However, Craddock, in an analogous art, teaches the limitation as can be seen in the in-line citations below:
the consumer is configured to post, after having serviced a work item, an acknowledgment of completion to a memory location at or adjacent to an address of the respective target data in memory; and the producer is configured to read the acknowledgement from said memory location (With reference now to FIG. 4, a diagram illustrating processing of work requests is depicted in accordance with a preferred embodiment of the present invention. In FIG. 4, a receive work queue 400, send work queue 402, and completion queue 404 are present for processing requests from and for consumer 406. These requests from consumer 402 are eventually sent to hardware 408. In this example, consumer 406 generates work requests 410 and 412 and receives work completion 414 – [30]; Craddock teaches hardware posting completion queue elements to a completion queue, which are then acknowledged by a consumer, which performs the function of the “producer” of the claim).
Therefore, it would have been obvious for one of ordinary skill in the art before the effective filing date to utilize a completion queue to improve the overall work queue processing system taught by He and Craflin. This addition would have been obvious to one of ordinary skill in the art at the time of filing because completion queues were shown to be effective in communicating to the consumer that their work requests had been completed.
Claim(s) 12-13 is/are rejected under 35 U.S.C. 103 as being unpatentable over He in view of Craflin further in view of the Non-Patent Literature document provided in the IDS titled “NVM Express” (hereinafter referred to as NVMe).
As per claim 12 – The combination of He and Craflin teach the system of claim 1. NVMe further teaches:
wherein the producer comprises a CPU and the consumer comprises a peripheral (NVM Express (NVMe) is a register level interface that allows host software to communicate with a non volatile memory subsystem. This interface is optimized for Enterprise and Client solid state drives, typically attached to the PCI Express interface – [pg. 8]; The non-volatile memory subsystem corresponds to a “peripheral”).
As per claim 13 – The combination of He and Craflin teach the system of claim 1. NVMe further teaches:
wherein the circular buffer, producer and consumer are connected to one another via a PCIe bus (Figure 2 below demonstrates a host having submission queues connected with a controller. The controller is shown in more detail in Figure 3, which also shows the connection via a PCIe bus).
PNG
media_image1.png
261
391
media_image1.png
Greyscale
PNG
media_image2.png
278
659
media_image2.png
Greyscale
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JOSEPH MAXEN LANE whose telephone number is (571)272-8027. The examiner can normally be reached M-F from 7:30 A.M. - 5 P.M.
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, April Y. Blair can be reached at (571) 270-1014. 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.
/JOSEPH MAXEN LANE/Examiner, Art Unit 2196
/HIREN P PATEL/Primary Examiner, Art Unit 2196
Prosecution Insights