DETAILED ACTION
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 .
Response to Arguments
Applicant's arguments filed 03/16/26 have been fully considered but they are not persuasive.
Regarding claim 1,
The applicant argues that the prior art does not teach the amended limitation selecting routing based on the origin of the flit.
However the examiner disagrees, because the routing is selected based on whether the origin of the flit has a xy routing available or not.
[0040] Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination. The default routing circuit at all routers upon receiving a message at any input port, looks up the destination ID, and forwards the message along the X-axis towards the destination if the x-coordinate of the destination router is not the same as the x-coordinate of the router, else along the Y-axis towards the destination. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn. Thus, special circuitry will be needed to handle these messages. In path 1, the first turn does not need any special circuitry, because node A is directly connected to the router 1 physically, and router 1 will treat a message arriving from node A as a regular message arriving on its top directional port, and the default X-Y routing circuit will turn the message to the right. When the message reaches router 2, it cannot continue as there are no more routers on the right, and it must make X-Y turn, which will need special circuitry. In path 2, router 1 needs special circuitry to not perform an X-Y turn which is what the default routing circuit of router 1 will do.
PNG
media_image1.png
437
467
media_image1.png
Greyscale
Hence it is based on the location of the origin of the flit and the surrounding router paths which still reads upon the limitation of claim 1 “based on the origin”. For example, if the starting/origin router was router B (fig. 5), then the system would select XY routing because there is an available XY routing. if the starting/origin router is router A (fig. 5), then the system would select YX routing since there is not an available XY routing. One of ordinary skill in the art would interpret the above as teaching the limitation “selecting, based on the origin of the flit, between vertical-to-horizontal dimension routing and horizontal-to-vertical dimension routing”.
All other arguments are fully addressed above.
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)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claim(s) 1-10, 15-24, 30 is/are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Kumar (Pub No 20170063610)
Regarding claim 1 and 15 and 30,
Kumar teaches A method comprising:
an interconnect associated with a two-dimensional (2D) coordinate system; and a switch coupled to the interconnect;
the switch determining a route path for a flit within a chip based (network on chip para [0018]) on a mixed-dimension order routing method, the flit originating at an origin, the mixed-dimension order routing method selecting, based on the origin of the flit, between vertical-to-horizontal dimension routing and horizontal-to-vertical dimension routing; and (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
routing the flit via an interconnect of the chip based on the route path determined, the interconnect associated with a two-dimensional (2D) coordinate system, the vertical-to-horizontal dimension routing and horizontal-to-vertical dimension routing relative to the 2D coordinate system. (interpreted as A packet is first routed over the x-axis till the packet reaches node ‘04’ where the x-coordinate of the node is the same as the x-coordinate of the destination node. The packet is next routed over the y-axis until the packet reaches the destination node, see para [0010])
Regarding claim 2 and 16,
Kumar teaches The method of claim 1, wherein the flit is a portion of a packet or the packet in its entirety. (interpreted as A packet is first routed over the x-axis till the packet reaches node ‘04’ where the x-coordinate of the node is the same as the x-coordinate of the destination node. The packet is next routed over the y-axis until the packet reaches the destination node, see para [0010])
Regarding claim 3 and 17,
Kumar teaches The method of claim 1, wherein the 2D coordinate system includes an x-axis and a y-axis and wherein: the vertical-to-horizontal dimension routing includes turning from a vertical direction to a horizontal direction; and the horizontal-to-vertical dimension routing includes turning from the horizontal direction to the vertical direction, the horizontal direction and vertical direction parallel to the x-axis and y-axis, respectively. (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
Regarding claim 4 and 18,
Kumar teaches The method of claim 1, wherein the interconnect forms a 2D mesh structure of a plurality of nodes, wherein a node of the plurality of nodes includes a switch, and wherein the routing includes transmitting, via the switch, the flit to another node of the plurality of nodes. (interpreted as Messages are injected by the source and are routed from the source node to the destination over multiple intermediate nodes and physical links. The destination node then ejects the message and provides it to the destination, see para [0006])
Regarding claim 5 and 19,
Kumar teaches the method of claim 1, wherein the mixed-dimension order routing method includes: employing the horizontal-to-vertical dimension routing in an event the origin is a device located at an edge of the interconnect of the chip; and employing the vertical-to-horizontal dimension routing otherwise. and (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
Regarding claim 6 and 20,
Kumar teaches The method of claim 5, wherein positive y-coordinates and positive x-coordinates of the 2D coordinate system are associated with rows and columns of the interconnect, respectively, wherein the positive x-coordinates increase in an east direction of the interconnect, wherein the edge is a right edge of the interconnect, and wherein the right edge is located in the east direction. (interpreted as In a 3×3 standard mesh NoC, a node can be identified with 4-bit ID, 2 bits for an x-coordinate and 2 bits for a y-coordinate (assuming dimension based ID, which is useful in dimension ordered routing). With virtual routers, the dimension order will become 5×5, and with dimension based ID, we will need 3 bits for the x-coordinate and 3 bits for the y-coordinate to identify all nodes in the system. Routing needs to be done looking at the expanded node IDs. Second, when a virtual node receives and transmits a message, then a fixed dimension ordered route which is often used in a standard mesh cannot always be taken. In dimension ordered routing, routing is performed along the X or Y axis until the x- or y-coordinate of the destination node ID is reached, and then a single turn is made and the route is traversed along the other axis, see para [0039]. Also see fig. 2 xy coordinates 00-44)
Regarding claim 7 and 21,
Kumar teaches The method of claim 1, further comprising avoiding routing deadlock by employing the mixed-dimension order routing method, the routing deadlock otherwise preventing transmission of the flit via the interconnect. (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
Regarding claim 8 and 22,
Kumar teaches The method of claim 1, further comprising reducing congestion in the interconnect by employing the mixed-dimension order routing method, the congestion reduced relative to employing a different routing method that employs the horizontal-to-vertical dimension routing, exclusively, or the vertical-to-horizontal routing, exclusively. (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
Regarding claim 9 and 23,
Kumar teaches The method of claim 8, wherein the interconnect includes a top row, bottom row, and a plurality of columns, wherein the reducing includes reducing the congestion in the top row, the bottom row, a column of the plurality of columns, or a combination thereof, and wherein the congestion in the top row, bottom row, or column is due to traffic received from a respective edge device coupled to the top row, bottom row, or column, the respective edge device external to the interconnect. (interpreted as Consider a mesh designed such that all messages take an X-Y route, i.e. messages first traverse along X-axis, take a turn, and then traverse along Y-axis to reach to the destination…. If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
Regarding claim 10 and 24,
Kumar teaches The method of claim 1, wherein the mixed-dimension order routing method includes prohibiting, at most, a first turn type and a second turn type, the first turn type and second turn type from a plurality of clockwise turn types and a plurality of counter-clockwise turn types, respectively. (interpreted as If we use virtual routers as illustrated in FIG. 5, then there is no available X-Y route from node A to node B. Two possible paths are illustrated in FIG. 5. Path 1 needs multiple turns: first a Y-X turn, then an X-Y turn, and finally an X-Y turn again before reaching the destination node. Path 2 takes a single Y-X turn, see para [0040]. See x-y routing in fig 2. And see y-x routing in fig. 5)
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.
Claim(s) 11, 13, 25, 27, and 29 is/are rejected under 35 U.S.C. 103 as being unpatentable over Kumar (Pub No 20170063610) further in view of Karanam (Pub No 20190007300)
Regarding claim 11 and 25,
Kumar teaches The method of claim 1, wherein positive y-coordinates and positive x-coordinates of the 2D coordinate system are associated with rows and columns of the interconnect, respectively, wherein the positive y-coordinates decrease in a north direction, wherein the positive x-coordinates increase in an east direction (interpreted as FIG. 2 illustrates an example of XY routing in a two dimensional mesh. More specifically, FIG. 2 illustrates XY routing from node ‘34’ to node ‘00’. In the example of FIG. 2, each component is connected to only one port of one router. A packet is first routed over the x-axis till the packet reaches node ‘04’ where the x-coordinate of the node is the same as the x-coordinate of the destination node. The packet is next routed over the y-axis until the packet reaches the destination node, see para [0010])
Although Kumar teaches deadlock prevention routing, Kumar does not teach preventing the specific east to north turn.
Karanam teaches wherein the mixed-dimension order routing method includes: prohibiting the flit from traversing the interconnect in the east direction and turning to traverse the interconnect in the north direction. (interpreted as [0005] In FIG. 1B, channels or links between nodes of a network such as full 2D mesh network 100 are shown using two conceptual cycles 102 and 104. Cycle 102 may be a clockwise cycle with four turns 102a-d and cycle 104 may be an anti-clockwise cycle with four turns 104a-d. A data packet traversing in either one of these cycles 102 or 104 may encounter a deadlock. To free the data packet from a deadlock, restrictions may be placed in one or more of the abovementioned turns of cycles 102/104, see para [0005]. See 104c turn east to north, fig. 1b)
It would have been obvious to one of ordinary skill in the art to combine the deadlock free routing via xy routing taught by Kumar with the restricting of routes/turns to prevent deadlocks as taught by Karanam for the benefit of restricting only a few turns/routes so the others can be still used.
Regarding claim 13 and 27,
Kumar teaches The method of claim 1, wherein positive y-coordinates and positive x-coordinates of the 2D coordinate system are associated with rows and columns of the interconnect, respectively, wherein the positive y-coordinates increase in a south direction, wherein the positive x-coordinates increase in an east direction, (interpreted as FIG. 2 illustrates an example of XY routing in a two dimensional mesh. More specifically, FIG. 2 illustrates XY routing from node ‘34’ to node ‘00’. In the example of FIG. 2, each component is connected to only one port of one router. A packet is first routed over the x-axis till the packet reaches node ‘04’ where the x-coordinate of the node is the same as the x-coordinate of the destination node. The packet is next routed over the y-axis until the packet reaches the destination node, see para [0010])
Although Koomar teaches deadlock free routing (para [0009]-[0010], Koomar does not teach preventing a specific turn (e.g. east to south).
Karanam and wherein the mixed-dimension order routing method includes: prohibiting the flit from traversing the interconnect in the east direction and turning to traverse the interconnect in the south direction. (interpreted as [0005] In FIG. 1B, channels or links between nodes of a network such as full 2D mesh network 100 are shown using two conceptual cycles 102 and 104. Cycle 102 may be a clockwise cycle with four turns 102a-d and cycle 104 may be an anti-clockwise cycle with four turns 104a-d. A data packet traversing in either one of these cycles 102 or 104 may encounter a deadlock. To free the data packet from a deadlock, restrictions may be placed in one or more of the abovementioned turns of cycles 102/104, see para [0005]. See 102b turn east to south, fig. 1b)
It would have been obvious to one of ordinary skill in the art to combine the deadlock free routing via xy routing taught by Kumar with the restricting of routes/turns to prevent deadlocks as taught by Karanam for the benefit of restricting only a few turns/routes so the others can be still used.
Regarding claim 29,
Kumar teaches The circuit of claim 15, however does not teach wherein the circuit is an integrated circuit.
Karanam teaches wherein the circuit is an integrated circuit. (interpreted as it will be recognized that various actions described herein can be performed by specific circuits (e.g., application specific integrated circuits (ASICs)), by program instructions being executed by one or more processors, or by a combination of both, see para [0025])
It would have been obvious to one of ordinary skill in the art to combine the circuits taught by Kumar with the integrated circuits as taught by Karanam for the benefit of performing the same function using other known in the art components such as integrated circuits to perform the same function.
Allowable Subject Matter
Claim 12, 14, 26, 28 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 12 and 26,
Kumar teaches The method of claim 11, wherein a top row of the interconnect is associated with the north direction, wherein the prohibiting includes an exception, and wherein the exception enables the flit, traversing the interconnect in the east direction, to turn to traverse the interconnect in the north direction in an event the flit is heading in the east direction along the top row and turning in the north direction to a traffic sink.
Regarding claim 14 and 28,
Kumar teaches The method of claim 13, wherein a bottom row of the interconnect is associated with the south direction, wherein the prohibiting includes an exception, and wherein the exception enables the flit, traversing the interconnect in the east direction, to turn to traverse the interconnect in the south direction in an event the flit is heading in the east direction along the bottom row and turning in the south direction to a traffic sink.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BAO G NGUYEN whose telephone number is (571)272-7732. The examiner can normally be reached M-F 10pm - 6: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, Huy Vu can be reached at 571-272-3155. 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.
/BAO G NGUYEN/Examiner, Art Unit 2461
/HUY D VU/Supervisory Patent Examiner, Art Unit 2461
Prosecution Insights