DETAILED ACTION
This action is in response to communication filed on 10/8/2024.
Claims 1-20 are pending.
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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 5/9/2025 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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 of this title, 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 set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied 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.
Claims 1-3, and 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over Kumar et al. (US 2017/0063564) in view of Klenk et al. (US 2021/0036877).
Regarding claim 20, Kumar discloses a method for multicasting within a network-on-chip, comprising:
generating a multicast message at an origin node of a network of nodes, wherein the multicast message includes definitions of destination nodes for the multicast message (Kumar discloses generating the multicast message at an origin (source component/node) and including definitions of destinations (e.g., “set of destinations” in the message), which are used to determine forwarding; [0059] “a source component injects a multicast message at a NoC node with which it is connected, which acts as a source node. The source node then transmits a copy of this message on each of its multicast tree edge…Additionally, when the message reaches a NoC node, the NoC node also examines whether the destination set for the multicast message contains any host that is connected to it”);
identifying addressed nodes from the definitions of destination nodes to determine message routing propagation (Kumar discloses identifying addressed nodes from definitions to determine routing propagation; [0032] “Nodes of a multicast tree may incorporate filters at each of their ports, which can be configured to assess each multicast message as it arrives in order to decide whether the message should be passed on down the tree based on the intended destination nodes mentioned in the message and nodes that can be accessed through the evaluating current node”),
propagating the multicast message to a receiving node of a network of nodes, wherein the receiving node is communicatively connected to one of the addressed nodes (Kumar discloses propagating to a receiving (intermediate) node connected to addressed (destination) nodes because the message is routed over intermediate nodes in the tree, each connected to sub-trees leading to destinations; [0031] “Multicast environment is achieved with transmission of a single message from a source component, which gets replicated in the NoC during routing towards the destination components indicated in the message” and [0032] “transmit the message by selecting an appropriate message tree. Nodes of a multicast tree may incorporate filters at each of their ports, which can be configured to assess each multicast message as it arrives in order to decide whether the message should be passed on down the tree based on the intended destination nodes mentioned in the message and nodes that can be accessed through the evaluating current node”);
propagating, via the receiving node, the multicast message to at least a first subset of the addressed nodes (Kumar discloses propagating via receiving (intermediate) node to a subset of addressed nodes because filters at the node replicate and pass the message only to sub-trees containing intended destinations, forming subsets along different routes; [0027] “Once transmitted by the source component/agent, the message is replicated within the NoC at various nodes in multiple messages, and message copies continue to be routed along different routes leading towards the destinations components/agents” and [0032] “Nodes of a multicast tree may incorporate filters at each of their ports, which can be configured to assess each multicast message as it arrives in order to decide whether the message should be passed on down the tree based on the intended destination nodes mentioned in the message and nodes that can be accessed through the evaluating current node”); and
processing the multicast message at each node of the first subset of the addressed nodes (Kumar discloses processing at a subset, with a second subset not processing based on criteria ; [0032] “Nodes of a multicast tree may incorporate filters at each of their ports, which can be configured to assess each multicast message as it arrives in order to decide whether the message should be passed on down the tree based on the intended destination nodes mentioned in the message and nodes that can be accessed through the evaluating current node” and [0036] “A multicast message can either be sent to all NoC nodes as and when encountered (which can then be absorbed by actual destination nodes for forwarding to their respective SoC components) or can only be sent to nodes that fall along the edges of the destination nodes mentioned in the multicast message”).
However, the prior art does not explicitly disclose the following:
wherein the definitions include a location range for the addressed nodes and one or more exclusion criteria;
wherein a second subset of the addressed nodes that does not process the multicast message is determined by the one or more exclusion criteria.
Klenk in the field of the same endeavor discloses technique for sharing computational load with network devices. In particular, Klenk discloses the following:
wherein the definitions include a location range for the addressed nodes and one or more exclusion criteria (Klenk discloses definitions including a location range and exclusion criteria; [0046] “Regions of addresses in the shared global address space can be defined as multicast regions, and packets addressed to addresses in these multicast regions can be treated as primitives for implementing in-network computations” and [0020] “The multicast region table maps ranges of addresses in a shared global address space to multicast regions” and [0159] “an endpoint can trigger a Multicast primitive through a DMA engine simply by executing a load/store operation using a particular address in the VAS mapped to the MCR”); and
wherein a second subset of the addressed nodes that does not process the multicast message is determined by the one or more exclusion criteria (Klenk discloses exclusion criteria determining non-processing subsets; [0010] “identifying the one or more participating endpoints based on information included in a corresponding entry of the multicast region table” and [0155] “determines that the destination address is associated with a network address corresponding to the MCR. Responsive to determining the network address corresponds with the MCR, the logic 130 looks up an entry in the MCR table 132 corresponding to the MCR in order to identify the participating endpoints in the network” and [0156] “the logic 130 of the network device 110 is configured to replicate the packet by generating a copy of the packet transmitted to each participating endpoint”).
Therefore, it would have been obvious to combine the prior art to include Klenk’s range-based mapping with exclusion to reduce message overhead in large-scale NoCs by compactly representing groups via ranges instead of lists, enabling efficient in-network routing for parallel workloads (Klenk [0045] “A technique for sharing computational load with network devices is disclosed. Network devices are designed with a multicast capability that enables certain operations, such as a reduce operation, to be moved from conventional endpoints to the network device”).
Regarding claim(s) 1, do(es) not teach or further define over the limitation in claim(s) 20 respectively. Therefore claim(s) 1 is/are rejected for the same rationale of rejection as set forth in claim(s) 20 respectively. Further, the ‘first node’ of claim 1 corresponds to the ‘receiving node’ in the claim 20 analysis, and the ‘definition of one or more addressed nodes’ is taught by the combined references’ destination definitions (including ranges from Klenk where applicable).
Regarding claim 2, Kumar-Klenk discloses the method of claim 1, wherein the definition of the one or more addressed nodes includes first information to determine a start node and an end node (Kumar [0017] “Flows traversing over various NoC channels are affected by the routes taken by various flows. In a mesh or Torus NoC, there may exist multiple route paths of equal length or number of hops between any pair of source and destination nodes”),
wherein the start node and the end node define a grid of the addressed nodes (Klenk [00564] “The MCR address start field includes the first address in the address range for the particular MCR corresponding to the entry. The size field includes the size of the MCR” and [0153] “The memory allocation refers to a range of addresses allocated within a virtual address space (VAS) local to the endpoint” and [0186] “the network address is compared to entries in the multicast region table to determine if the network address is included in a range of addresses in a global shared address space allocated to a multicast region”), and
wherein the multicast message propagates within the grid of the addressed nodes towards the end node (Kumar [0025] “Consider an example wherein there are 16 CPUs and 2 memories that need to be placed in a 3×6 mesh organization. Let the first set of 8 CPUs communicate with the first memory MEM1 and the second set of 8 CPUs communicate with the second memory MEM2 as illustrated in FIG. 4(a). The CPUs and memories may be placed in a 3×6 mesh in sequential order as shown in FIG. 4(b), wherein each host occupies a cell in the mesh and is directly connected to the router of the cell, without consideration of the traffic between various hosts”).
Regarding claim 3, Kumar-Klenk discloses the method of claim 2, wherein the one or more exclusion criteria include second information to identify the second subset of the addressed nodes (Klenk [0054] “the MCR identifier field includes a unique identifier for each distinct MCR in the global address space. The MCR address start field includes the first address in the address range for the particular MCR corresponding to the entry. The size field includes the size of the MCR. The size field designates the number of consecutive addresses in the MCR. The target identifier field includes a list of endpoint identifiers configured to participate in a multicast computation for the MCR”).
Regarding claim 17, Kumar-Klenk discloses the method of claim 1, wherein the definition of the one or more addressed nodes and the one or more exclusion criteria are located within a FLIT header of the multicast message (Kumar [0014] “The first flit is the header flit, which holds information about this packet's route and key message level info along with payload data and sets up the routing behavior for all subsequent flits associated with the message”).
Regarding claim 18, Kumar-Klenk discloses the method of claim 1, wherein propagating, via the first node, the multicast message to at least a first subset of the addressed nodes comprises sending the multicast message through nodes not included in the addressed nodes (Kumar [0059] “The source node then transmits a copy of this message on each of its multicast tree edge. Subsequently, any NoC node that receives a multicast message sends a copy of the message on all its multicast edges except to the one from which it received the message. For instance, in case the source node 6 sends the multicast message to node 11, node 11 would send a copy of the message to all its edges i.e. to nodes 10, 12 and 16, except sending it back to node 6. Additionally, when the message reaches a NoC node, the NoC node also examines whether the destination set for the multicast message contains any host that is connected to it. For instance, each of the nodes 11, 12, 10, and 16 would assess if the destination node, say node 17, is connected thereto. If it is, it also sends a copy of the message to the ejection ports to which the destination hosts are connected. This process continues until leaf nodes of the multicast trees are reached” and [0027] “Once transmitted by the source component/agent, the message is replicated within the NoC at various nodes in multiple messages, and message copies continue to be routed along different routes leading towards the destinations components/agents”).
Regarding claim(s) 19, do(es) not teach or further define over the limitation in claim(s) 20 respectively. Therefore claim(s) 19 is/are rejected for the same rationale of rejection as set forth in claim(s) 20 respectively. Further, the ‘network of computational nodes’ with NIU and processing core corresponds to the NoC nodes and components in Kumar’s system (e.g., routers and agents), the ‘communication paths’ to Kumar’s links, and the configuration to perform the multicast steps (receiving, propagating, processing with exclusions) is taught by the combined reference as detailed in claim 20 analysis.
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Kumar et al. (US 2017/0063564) in view of Klenk et al. (US 2021/0036877) in view of Parle et al. (US 2024/0289132).
Regarding claim 4, Kumar-Klenk discloses the invention substantially, however the prior art does not explicitly disclose the method of claim 3, wherein the second subset of nodes comprises a sub-grid within the grid of the addressed nodes.
Parle in the field of the same endeavor discloses techniques for a programmatic multicast technique enabling one thread to request data on behalf of one or more other threads. In particular, Parle teaches the following:
wherein the second subset of nodes comprises a sub-grid within the grid of the addressed nodes (Parle discloses sub-grid (tiles) for subset in NoC multicast because the CGAs are gird-like arrays of CTAs (tiles/sub-grides in GPU NoC), and multicast targets subsets of CTAs/SMs within the CGA, with credits/assignment excluding non-destination subsets; [0128] “For multicast packets, the creditor 904 is configured to obtain credits for each destination of the multicast packet. The creditor 904 for example determines the number of CPCs to which the packet is to be multicast and, together with vc credit logic 912, obtains credits for each CPC to which the packet is directed”).
Therefore, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed to combine the prior art with Parle for efficient bandwidth in tiled/grid NoCs, enabling smaller tile (sub-grid) sizes (Parle [abstract] “The multicast is designed to reduce cache (for example, layer 2 cache) bandwidth utilization enabling strong scaling and smaller tile sizes”)
Claims 5, 12-13 are rejected under 35 U.S.C. 103 as being unpatentable over Kumar et al. (US 2017/0063564) in view of Klenk et al. (US 2021/0036877) in view of Minkin et al. (US 2023/0289292).
Regarding claim 5, Kumar-Klenk discloses the method of claim 2, wherein the grid comprises a rectangular grid Kumar; [0038]; “FIGS. 1(a), 1(b) 1(c) and 1(d) illustrate examples of Bidirectional ring, 2D Mesh, 2D Torus, and 3D Mesh NoC Topologies”) and wherein the definition of the plurality of addressed nodes comprises a start coordinate for the first node and an end coordinate for the end node (Klenk; [0053]; “the fabric manager 150 is allocated a range of addresses within the global address space that can be used for MCRs. A host device can then request the fabric manager 150 to create an MCR for use in a particular algorithm implemented by a number of endpoints”).
However, the prior art does not explicitly disclose wherein the end node is located at an opposite corner of the rectangular grid from the first node.
Minkin in the field of the same endeavor disclose techniques for handling memory accesses to blocks of data by a parallel processor. In particular, Minkin teaches the following:
wherein the end node is located at an opposite corner of the rectangular grid from the first node (Minkin discloses start coordinate for first node and end coordinate (derived as start + boxSize) at opposite corner because the tensor is a rectangular multidimensional grid, and boxSize defines the rectangular block from start to opposite corner (e.g., from (x,y) to (x+boxSize[0], y+boxSize[1] in 2D)); [0078] “As shown in FIG. 5B, the TMAU instruction parameters include just the starting coordinate of the block (e.g., (x, y)). The starting coordinate for an n-dimensional vector accordingly will be an n-dimensional tuple” and [0090] “The innermost loop provides for iterating over elements along dimension 0 (of the dimensions 0-4) by starting from the requested block's coordinate in dimension 0 (blockstart0) and incrementing the current coordinate c0 in dimension 0 by the traversal stride for dimension 0 (“tensorDescriptor.traversalStride[0]”) to a dimension 0 coordinate that exceeds the box size in dimension 0 (“blockStart0+tensorDescriptor.boxSize[0]”; block boundary is exceeded)”).
Therefore, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed to combine the prior art with Minkin’s coordinate-based ranges to compactly represent rectangular subsets of nodes in mesh grids, optimizing multicast for structured data like tensors in parallel NoCs (Minkin [0071] “The SM may access the block 312 by merely providing the origin point 316 for the block by its coordinates in the tensor's coordinate system—the coordinate pair x, y”)
Regarding claim 12, Kumar-Klenk-Minkin discloses the method of claim 5, wherein the one or more exclusion criteria further comprises an identification of consecutive nodes within the rectangular grid as the second subset of the addressed nodes (Minkin discloses identification of consecutive nodes (elements in tensor block that are out-of-bounds, which are contiguous/sequential along dimensions) within rectangular grid (multidimensional tensor as n-dimensional array/grid) as second subset (out-of-bounds elements forced to zero/NaN, effectively excluded from normal processing) because the tensor is a grid of elements (nodes), and out-of-bounds criteria identify consecutive elements crossing boundaries as a subset for special handling (exclusion via value assignment); [0074] “The TMAU must properly handle out-of-bound conditions where the requested block may cross tensor boundaries in global memory. FIG. 4B illustrates some examples where requested blocks reach outside of the 2D tensor. If any requested element is located outside of the tensor, then it's value may be forced either to zero or some other predefined special constant (e.g., a not-a-number (NAN) value)” and [0069] “The tensor 302 is accessed by the SM in blocks of a size smaller than the entire tensor, such as, for example, the box 306. The tensor parameters shown in FIG. 3A include the number of dimensions of the tensor, size of each dimension, stride for each dimension, and element size in the tensor. The block to be accessed within the tensor is characterized by the size of each dimension of the block” and [0071] “The tensor height H and width W are defined, and also the element size 310. The tensor 308 is padded with padding 314 in the x-direction. Thus, the tensor stride in the x-direction includes the width of the padding. The block 312 is data that is required by a kernel, and also has its own height (block height) and width (block width)”).
Regarding claim 13, Kumar-Klenk-Minkin discloses the method of claim 12, wherein the consecutive nodes comprise one or more rows within the rectangular grid or one or more columns within the rectangular grid (Kumar [0057] “Consider an example NoC topology 500 shown in FIG. 5(a). Squares in FIG. 5(a) indicate NoC routers, also interchangeably referred to as NoC nodes or simply “nodes” hereinafter, and lines between them indicate NoC channels. As illustrated in FIG. 5(a), each node can be configured with multiple ports for bi-directional or multi-directional transmission of message transactions. For instance, ports of node 0 are connected with ports of node 1 and 5. Similarly, ports of node 7 are connected with ports of nodes 2, 6, 7, and 9”).
Allowable Subject Matter
Claims 6-11, 14-15 and 16 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.
Conclusion
For the reason above, claims 1-5, 12-13 and 17-20 have been rejected and remain pending.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JIMMY H TRAN whose telephone number is (571)270-5638. The examiner can normally be reached Monday-Friday 9am-5pm PST.
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, Chris Parry can be reached at 571-272-8328. 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.
JIMMY H TRAN
Primary Examiner
Art Unit 2451
/JIMMY H TRAN/Primary Examiner, Art Unit 2451