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
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 (i.e., changing from AIA to pre-AIA ) 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, 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.
Claims 1-6 and 13-14 are rejected under 35 U.S.C. 103 as being unpatentable over Bakhoda et al., “Throughput-Effective On-Chip Networks for Manycore Accelerators,” 2010 (hereinafter Bakhoda) in view of Furhad et al., “An extended Diagonal Mesh Topology for Network-on-Chip Architectures,” 2015 (hereinafter Furhad).
As per claim 1, Bakhoda teaches an accelerator (see abstract) comprising:
switches having a mesh topology (see abstract, Bakhoda teaches a baseline architecture having a 2D mesh topology and illustrate compute-node routers and memory-controller-node routers in the baseline mesh. The claimed “switches” read on “routers in the NoC; see also table III which identifies the baseline interconnect topology as “Mesh”); and
processing units connected to the switches (Fig. 4 shows a computer node connected to a router. Each compute node includes SIMD pipelines, warp execution resources, L1 caches, and shared memory. Thus, each compute node/processing unit is connected to a corresponding router/switch), respectively,
wherein the mesh topology comprises nodes corresponding to the switches (see abstract wherein mesh includes compute-node routers and memory-controller-node routers. These routers/switches are the claimed nodes of the metho topology), and edges configured to connect the nodes (see Fig. 3 and abstract which identifies a metho topology and discusses router/channel parameters, including channel latency and channel width; see also last paragraph of page 5), and
wherein the nodes comprise a given node that is connected to all of its orthogonally adjacent nodes in the mesh topology that are orthogonally adjacent to the given node (See Fig. 15, wherein a 2D mesh routers have north/south/east/west mesh connections, as shown in the router-connection discussion and Figure 15; see also Figure 3);
Bakhoda does not expressly teach diagonal mesh links However, the secondary prior art Furhad teaches this feature. Furhad’s XDMesh is derived from a traditional mesh by inserting diagonal links between nodes situated in the diagonal direction (see abstract and second paragraph of page 2). Furhad further teaches that diagonal links reduce communication delay, hop count, latency, and energy consumption. Therefore, modifying Bakhoda’s mesh routers to include Furhad’s diagonal links results in a node connected to a selected/set number of diagonally adjacent nodes.
Accordingly, it would have been obvious to one of ordinary skill in the art, before the effective filling of the claimed invention, to modify Bakhoda’s mesh NoC accelerator to include Furhad’s diagonal links to reduce communication delay, hop count, latency, and energy consumption.
As per claim 2, Bakhoda in view of Furhad further teach the accelerator of claim 1, wherein the mesh topology is a 2D mesh topology (see Bakhoda last paragraph of page 5) and the set number is one (Furhad teaches a router architecture for XDMesh having right, left, top, bottom, and diagonal channel capability. Furhad also teaches inserting diagonal links between diagonally situated nodes. Thus, in the combined Bakhoda/Furhad mesh, a node can be connected to a selected single diagonal adjacent node).
As per claim 3, Bakhoda in view of Furhad further teach the accelerator of claim 2,
wherein the nodes comprise a first node that is a corner node, a second node that is an edge node, and a third node that is an interior node (Bakhoda’s finite 2D mesh layout includes routers arranged in rows and columns. A finite rectangular 2D mesh inherently includes corner nodes, edges nodes, and interior nodes; see last paragraph of page 5 and Fig. 3),
wherein the first node is connected to all of two orthogonally adjacent nodes that are orthogonally adjacent to the first node (In a finite 2D mesh, a corner node has two available orthogonal neighbors. Bakhoda/Furhad teach the 2D mesh with horizontal/vertical connections; therefore, a corner node is connected to its two available orthogonal neighbors), and is connected to one diagonally adjacent node that is diagonally adjacent to the first node (Furhad teaches diagonal links between nodes situated in the diagonal direction. For a 2D corner node, the inward diagonal node is the available diagonal adjacent node, see Furhad abstract and Fig. 2),
wherein the second node is connected to all of three orthogonally adjacent nodes that are orthogonally adjacent to the second node (in a finite 2D mesh, an edge-but-not-corner node had three available orthogonal neighbors. This follows from Bakhoda/Furhad’s 2D mesh of horizontal/vertical router links), and is connected to one diagonally adjacent node between two diagonally adjacent nodes that are diagonally adjacent to the second node (a 2D edge node has two inward diagonal candidates Furhad teaches inserting diagonal links between diagonally situated mesh nodes. Selecting one of the two available diagonal candidates corresponds to the claimed one diagonally adjacent nodes, see Furhad section 3.1 Proposed Topology), and
wherein the third node is connected to all of four orthogonally adjacent nodes that are orthogonally adjacent to the third node (in a 2D mesh, an interior node has four orthogonal neighbors: up, down, left, and right. Bakhoda’s router connections identify north/south/east/west router links in a 2D mesh), and is connected to one diagonally adjacent node among four diagonally adjacent nodes that are diagonally adjacent to the third node (a 2D interior node has four diagonal candidates. Furhad teaches diagonal links between diagonally situated nodes and diagonal routing choices. Selecting one diagonal neighbor among the four diagonal candidates is a predictable implementation of Furhad’s diagonal-link teaching).
As per claim 4, Bakhoda in view of Furhad further teach the accelerator of claim 1, wherein the mesh topology is a 3D mesh topology (Bakhoda teaches a scalable manycore mesh NoC architecture and chooses a 2D mesh because it is a regular, simple, and scalable. However, extending a regular 2D mesh to a 3D mesh would have been an obvious design variation where additional integration density or stacked/layered interconnect is desired. It’s also implies from Bakhoda that it’s capable of being 3D) and the set number is four (Furhad teaches adding diagonal links to a mesh to reduce hop count, latency, and energy consumption. In a 3D mesh, selecting four diagonal neighbors is a predictable design choice that balances the benefit of diagonal shortcuts against added wiring/router port cost). It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to extend the known regular mesh/diagonal-link concept to 3D and to select a finite subset of diagonal neighbors, such as four, to reduce hop count while limiting wiring and router complexity.
As per claim 5, Bakhoda in view of Furhad further teach the accelerator of claim 4,
wherein the nodes comprise a first node that is a corner node, a second node that is an edge node, a third node that is a face node and a fourth node that is an interior node (a finite 3D mesh inherently includes corner nodes, edge nodes, face nodes, and interior nodes. This follows from extending Bakhoda’s finite 2D mesh layout to a 3D mesh),
wherein the first node is connected to all of three orthogonally adjacent nodes that are orthogonally adjacent to the first node (In a 3D mesh, a corner node has three available orthogonal neighbors. This is the direct 3D counterpart of Bakhoda/Furhad’s horizontal/vertical orthogonal mesh links), and is connected to four diagonally adjacent nodes that are diagonally adjacent to the first node (Furhad teaches adding diagonal links between diagonally situated nodes. In the obvious 3D extension, the corner node may be connected to four diagonal neighbors to provide diagonal shortcuts while controlling the number of added links),
wherein the second node is connected to all of four orthogonally adjacent nodes that are orthogonally adjacent to the second node (In a 3D mesh, an edge-but-not-corner node has four available orthogonal neighbors. This is a geometric consequence of a finite 3D mesh), and is connected to four diagonally adjacent nodes among seven diagonally adjacent nodes that are diagonally adjacent to the second node (In a 3D mesh, an edge node has seven diagonal candidates. Selecting four diagonal candidates is an obvious fixed-subset design choice in view of Furhad’s diagonal-link teaching),
wherein the third node is connected to all of five orthogonally adjacent nodes that are orthogonally adjacent to the third node (in a 3D mesh, a face-but-edge node has five available orthogonal neighbors), and is connected to four diagonally adjacent nodes among 12 diagonally adjacent nodes that are diagonally adjacent to the third node (in a 3D mesh, a face node has 12 diagonal candidates. Selecting four of those candidates is an obvious fixed-number diagonal design in view of Furhad), and
wherein the fourth node is connected to all of six orthogonally adjacent nodes that are orthogonally adjacent to the fourth node (in a 3D mesh, an interior node has six orthogonal neighbors), and is connected to four diagonally adjacent nodes among 20 diagonally adjacent nodes that are diagonally adjacent to the fourth node (In a 3D mesh, an interior node has twenty diagonal candidates. Selecting four of those candidates follows from the same fixed-subset diagonal-link design rationale).
As per claim 6, Bakhoda in view of Furhad further teach the accelerator of claim 1, wherein a first switch among the switches is connected to one or more processing units among the processing units (Bakhoda’s compute node is connected to a router. The router corresponds to the claimed switch, and the compute node/compute core corresponds to the claimed processing unit), and
wherein a first processing unit among the processing units is connected to one switch among the switches (Bakhoda’s Figure 4 shows one compute node associated with one router, which reads on a first processing unit connected to one switch).
As per claim 13, Bakhoda in view of Furhad further teach the accelerator of claim 1, wherein each of the processing units comprises a memory and a graphics processing unit (GPU) or a neural processing unit (NPU) (see Bakhoda abstract).
As per claim 14, Bakhoda in view of Furhad further teach the accelerator of claim 13, wherein the processing units respectively corresponding to corner nodes located at corners of the mesh topology comprise respective interfaces for connection to an external device (see Fig. 1 and abstract, wherein Bakhoda teaches NoC nodes having interface to off-chip GDDR through memory-controller nodes).
Claims 7-12 and 15-20 are rejected under 35 U.S.C. 103 as being unpatentable over in view of Furhad, and further in view of Lakhotia et al., “In-network Allreduce with Multiple Spanning Trees on PolarFly,” SPAA 2023 (hereinafter Lakhotia).
As per claim 7, Bakhoda in view of Furhad teaches the manycore accelerator mesh NoC with diagonal links to the mesh. However, they did not specify performing operations on variables simultaneous using spanning tress of the nodes.
Lakhotia teaches using multiple spanning trees embedded in a network topology to perform Allreduce operations in parallel (see abstract section 1.1, optimizing Allreduce bandwidth). Apply this to Bakhoda in view of Furhad’s mesh accelerator would have predictably allowed simultaneous collective operations over the mesh nodes.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to apply Lakhotia’s multiple-spanning-tree Allreduce technique to the Bakhoda in view of Furhad mesh accelerator for the purpose of allowing concurrent insertion of disjoint sub-vectors in different tress to exploit data parallelism.
As per claim 8, Lakhotia further teaches wherein the spanning trees are disjoint spanning trees that do not share edges (see second paragraph of page 2 and section 1.4, “edge-disjoint trees” wherein the edge-disjoint tree solution offers “no congestion,” and further state the bandwidth result follows from the fact that the spanning trees are edge-disjoint. Edge-disjoint trees do not share edges).
As per claim 9, Lakhotia further teaches wherein the accelerator of claim 8, wherein the operations are all-reduce operations on the variables (see abstract).
As per claim 10, Bakhoda, Furhad and Lakhotia further teach the accelerator of claim 8, wherein the mesh topology is a 2D mesh topology and a number of the variables is four or less, or the mesh topology is a 3D mesh topology and a number of the variables is eight or less (Bakhoda teaches the implied 3D mesh, and Lakhotia teaches scalar and vector Allreduce, see abstract, including parallelization over vector elements. A scalar or up-to-four-element/vector-variable implementation satisfies the claimed numerical limit).
As per claim 11, Lakhotia further teaches wherein each of the disjoint spanning trees has a corresponding corner node in the mesh topology as a root node thereof (see abstract and section 4.3).
As per claim 12, Lakhotia further teaches:
perform an all-reduce operation using values corresponding to a first variable assigned to the processing units (Lakhotia abstract teaches Allreduce using an input from each node and distributing the reduction result to all nodes. In the combined Bakhoda/Furhad accelerator, those node inputs correspond to values assigned to the processing units connected to the mesh routers) according to a structure of a first disjoint spanning tree among the disjoint spanning trees (Lakhotia teaches computing Allreduce on spanning-tree topologies and further teaches edge-disjoint spanning trees. See section 4.3 and 5.1);
store a result value of the all-reduce operation in one or more processing units corresponding to the root node of the first disjoint spanning tree (see abstract and section 4.3); and
transmit the result value to processing units corresponding to nodes except the root node of the first disjoint spanning tree among the nodes according to the structure of the first disjoint spanning tree (see section 4.3 and 5.1, Lakhotia teaches that after the final reduction output is computed at the root, the output is broadcast to all nodes by traversing down the same tree).
As per claim 15, Lakhotia teaches that spanning trees are generated from selected node groupings and roots in the physical network topology (see abstract and section 4.3). It would have been obvious to determine the spanning trees in the Bakhoda/Furhad mesh based on subgroup of the selected mesh nodes, such as corner nodes or other designed first nodes, to organize multiple Allreduce trees.
As per claim 16, it’s rejected for the same reasons set forth above in claims 1, 7, and 15. Bakhoda teaches the accelerator system, mesh NoC, router/switches, compute nodes, and checkerboard mixed-connectivity organization using full routers and half routers. Furhad teaches adding diagonal links to the selected mesh nodes/block. Lakhotia teaches determining spanning trees based on the physical topology and configuring the network to perform tree-based Allreduce operations.
As per claim 17, it’s rejected for the same reasons set forth above in claims 7-10.
As per claim 18, it’s rejected for the same reasons set forth above in claims 11 and 12.
As per claim 19, it’s rejected for the same reasons set forth above in claims 1 and 7.
As per claim 20, it’s rejected for the same reasons set forth above in claims 1 and 7.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Olofsson US PG-Pub 2010/0111088 A1 teach mesh network topology with processing unit and interface.
Beshai US PG-Pub 2012/0045204 A1 teaches Network with a fast-switching optical core providing widely varying flow-rate allocations.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to IDRISS N ALROBAYE whose telephone number is (571)270-1023. The examiner can normally be reached Mon-Fri, 8am-4:30pm.
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-1400. 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.
/IDRISS N ALROBAYE/Supervisory Patent Examiner, Art Unit 2181
Prosecution Insights