DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending.
Claim Objections
Claims 1, 3-6, 12-13, 15, 17 and 20 are objected to because of the following informalities:
-- determining a location -- should be -- determining [a] the starting location in claim 3 line 1, claim 16 line 1.
-- determining candidate locations -- should be -- determining the candidate locations in claim 1, line 11, claim 4 line 1, claim 15 line 13, claim 17 line 2, claim 20 line 15.
-- determining a predetermined number -- should be -- determining [a] the predetermined number -- in claim 5 line 1, claim 6 line 1.
-- a critical node -- should be -- [a] the critical node -- in claim 12 line 2, claim 13 line 2, 5.
Appropriate correction is required.
Specification
The disclosure is objected to because of the following informalities:
-- configure -- should be -- configured-- in [0134].
-- name of the inventors -- should be deleted from page 1.
-- 3.4 -- should be --3[[.]] or 4 -- in [0006].
-- software elements such as a CPU -- should be amended in [0011].
-- CPU , GPU -- is abbreviated without reciting full form in [0005].
Appropriate correction is required.
Drawing
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because:
Reference character 521-526 and associated labels are oriented in different direction i.e. vertical in contrast to other horizontal labels in fig. 5.
reference character “845” has been used to designate both Node Assignment Unit and Edge Assignment Unit in fig. 8.
they do not include the following reference sign(s) mentioned in the description: 846 as described in [0112].
Missing description of fig. 10’
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. - An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: placer and router is configured to: receive /repeat/ determine/select/assign in claim 15.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification ([0112] fig. 8) as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 are rejected under 35 U.S.C. 112 (b) as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or joint inventor regards as the invention.
The following claim language is not clearly understood:
Claim 1 recites “assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of reconfigurable processor”. It is unclear edge is assigned to links or switch or both.
Claims 15 and 20recite elements of claim 1 and have similar deficiency as claim 1. Therefore, they are rejected for the same rational. Remaining dependent claims 2-14 and 16-19 are also rejected due to similar deficiency inherited from the rejected independent claims.
* Applicant is advised to at least indicate support present in the specification for further defining/clarifying the claim language in case Applicant believe amendments would unduly narrow the scope of the claim.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 15-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter.
Claim 15 is rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. Independent claim 15 recites a “placer and router”, which includes multiple modules and/or tools, according to the specification ([0112] fig. 8), and module may be implemented entirely as hardware, software or combination of software and hardware, according to the specification ([0200]). Thus, placer and router, which includes multiple modules/tools, may be entirely made of software and therefore do not fall withing one of the four statutory category subject matter. Applicant is advised to recite a hardware for example a processor to overcome 35 U.S.C. 101 statutory subject matter objections.
Claims 16-19 are dependent claims of claim 15 and do not cure the deficiency of the independent claim 15. Therefore, they are rejected for the same reason.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more or integrating into practical application.
Claims 1-20 are directed to an abstract idea. Examples of abstract ideas include at least Mathematical concepts, Mental process and Certain Methods of organizing human activity. Independent claim 1 is directed to “determining/selecting/ assigning candidate location on the reconfigurable processor to the nodes of the sorted operation unit graph” at a high level of generality.
Step 1
As described in MPEP § 2106, subsection III, Step 1 of the eligibility analysis asks: Is the claim to a process, machine, manufacture or composition of matter?
Claim 1 recites a method, which falls within the “process” category of 35 U.S.C. § 101. Claim 15 recites a placer and router for placement and routing without any hardware, and therefore do not fall one of the four statutory category subject matter. Claim 20 recites a “non-transitory computer-readable storage medium, which falls within the “manufacture / machine” category of 35 U.S.C. § 101. Thus, the analysis determines whether the claims recite a judicial exception and fail to integrate the exception into practical application. See Memorandum, 84 Fed. Re. 54-55. If both elements are satisfied, the claims are directed to a judicial exception under the first step of the Alice/Mayo test, See id.
Step 2A Prong One
As described in MPEP § 2106, subsection III, Step 2A of the Office’s eligibility analysis is the first part of the Alice/Mayo test, i.e., the Supreme Court’s "framework for distinguishing patents that claim laws of nature, natural phenomena, and abstract ideas from those that claim patent-eligible applications of those concepts." Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 217-18, 110 USPQ2d 1976, 1981 (2014) (citing Mayo, 566 U.S. at 77-78, 101 USPQ2d at 1967-68).
Step 2A is a two-prong inquiry, in which examiners determine in Prong One whether a claim recites a judicial exception, and if so, then determine in Prong Two if the recited judicial exception is integrated into a practical application of that exception.
Claim Elements
i
1. A method of operating a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor, comprising:
preamble
ii
receiving an architectural specification of the reconfigurable processor;
information gathering i.e. insignificant extra solution activity
iii
receiving the sorted operation unit graph having an ordered sequence of nodes and edges that interconnect nodes in the ordered sequence of nodes;
information gathering i.e. insignificant extra solution activity
iv
repeating as long as the ordered sequence of nodes comprises at least one unassigned node:
v
in order of the ordered sequence of nodes, retrieving a first unassigned node from the ordered sequence of nodes as a current node;
information gathering i.e. insignificant extra solution activity
vi
determining a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node;
mental processing abstract idea
vii
determining candidate locations on the reconfigurable processor for placing the current node based on the starting location;
mental process abstract idea
viii
for each candidate location of the candidate locations, determining a valuation associated with placing the current node at the candidate location;
mental process abstract idea
ix
selecting among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion; assigning the current node to the target location; and
mental process abstract idea
x
assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor.
mental process abstract idea
The overall process described by steps [vi]-[x] describes “concepts performed in the human mind” or “observation, evaluation, judgement, opinion.” Memorandum, 84 Fed. Reg, 52. Thus steps [vi]-[x] recite the abstract concept of [m]ental processes.” Id. For example, claim 1 step [vi] recites “determining a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node”, which is directed to determining a starting location, which can be performed by human mind alone or with the help of pen and paper, except for the implementation using reconfigurable processor. Claim 1 step [vii] recites “determining candidate locations on the reconfigurable processor for placing the current node based on the starting location”, which is directed to determining different candidate locations relative to the starting location, and can be performed by human mind alone or with the help of pen and paper except for implementation using reconfigurable processor. Claim 1 step [viii] recites “for each candidate location of the candidate locations, determining a valuation associated with placing the current node at the candidate location”, which is directed to determining valuation associated with placing the node at the candidate location, and can be performed by human mind alone or with the help of pen and paper except for implementation using reconfigurable processor. Claim 1 step [ix] recites “selecting among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion; assigning the current node to the target location”, which is directed to selecting location based on given criterion, and can be performed by human mind alone or with the help of pen and paper. Claim 1 step [x] recites “assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor”, which is directed to assigning edge of the graph to link and switches”, and can be performed by human mind alone or with the help of pen and paper. Therefore, steps [vi]-[x] resembles the idea of performing observation, evaluation, judgement and opinion according to the broadest reasonable interpretations of the claim elements and can be performed by human mind alone or with the aid of pen and paper. The courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011).
Thus, claim 1 recites a judicial exception of Mental Process. For these same reasons, claims 15 and 20 recite Mental Process judicial exception.
Step 2A, Prong Two
As described in MPEP § 2106, subsection III, Step 2A of the Office’s eligibility analysis is the first part of the Alice/Mayo test, i.e., the Supreme Court’s "framework for distinguishing patents that claim laws of nature, natural phenomena, and abstract ideas from those that claim patent-eligible applications of those concepts." Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 217-18, 110 USPQ2d 1976, 1981 (2014) (citing Mayo, 566 U.S. at 77-78, 101 USPQ2d at 1967-68).
Step 2A is a two-prong inquiry, in which examiners determine in Prong One whether a claim recites a judicial exception, and if so, then determine in Prong Two if the recited judicial exception is integrated into a practical application of that exception.
Because claims 1, 15 and 20 recite a judicial exception, Analysis determines if the claims recites additional elements that integrate the judicial exception into practical application.
In addition to the limitations of claim 1 discussed above that recite the mental process abstract concepts, claim 1 also recites additional steps [i]-[v]. Claim 1 in step [i] recites “method of operating a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor”, which recites an intended use and may not integrate the abstract idea into practical application. Claim 1 step [ii], [iii] and [v] recites receiving specification, sorted operation unit graph, retrieving node from the sequence respectively, all of which is directed to insignificant information gathering, and adding insignificant extra-solution activity to the judicial exception may not integrate the judicial exception into practical application. See MPEP § 2106.04(d) I. § 2106.05(g). Claim 1 step [iv] recites “repeating as long as the ordered sequence of nodes comprises at least one unassigned node”, which is directed to repeating the step of retrieving information and /or mental process abstract ideas. Therefore, these do not impose further limitations in a manner to integrate the abstract idea into practical application.
Thus, claim 1 recites a judicial exception of Mental Process without integrating the abstract idea into practical application. For these same reasons and based on similar analysis as above, claims 15 and 20 also recites judicial exception of Mental Process without integrating the abstract idea into practical application.
Step 2B
As described in MPEP § 2106, subsection III, Step 2B of the Office’s eligibility analysis is the second part of the Alice/Mayo test, i.e., the Supreme Court’s "framework for distinguishing patents that claim laws of nature, natural phenomena, and abstract ideas from those that claim patent-eligible applications of those concepts." Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 217, 110 USPQ2d 1976, 1981 (2014) (citing Mayo, 566 U.S. 66, 101 USPQ2d 1961 (2012)).
Step 2B asks: Does the claim recite additional elements that amount to significantly more than the judicial exception.
Because claims 1, 15 and 20 are directed to judicial exception, analysis must determine, according to Alice, whether these claims recite an element, or combination of elements that is enough to ensure that the claim is directed to significantly more than a judicial exception.
The Memorandum, Section III (B) (footnote 36) states:
In accordance with existing guidance, an Examiner’s conclusion that an additional element (or combination of elements) is well understood, routine, conventional activity must be supported with a factual determination. For more information concerning evaluation of well-understood, routine, convention activity, see MPEP 2106.05(d), as modified by the USPTO Berkheimer Memorandum.
The Berkheimer Memorandum, Section III(A)(1) states:
A Specification demonstrates the well-understood, routine, conventional nature of additional elements when it describes the additional elements as well-understood or routine or conventional (or an equivalent term), as a commercially available product, on in a manner that indicates that the additional elements are sufficiently well-known that the specification does not need to describe the particulars of such additional elements to satisfy 35 §U.S.C. 112(a). A finding that an element is well-understood, routine, or conventional cannot be based only on the fact that the specification is silent with respect to describing such element.
In addition to the limitations of claim 1 discussed above that recite the mental process abstract concepts, claim 1 also recites additional steps [i]-[v]. Claim 1 in step [i] recites “method of operating a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor”, which recites an intended use and do not amount to significantly more. Claim 1 step [ii], [iii] and [v] recites receiving specification, sorted operation unit graph, retrieving node from the sequence respectively, all of which is directed to insignificant information gathering, and is therefore do not amount to significantly more. Claim 1 step [iv] recites “repeating as long as the ordered sequence of nodes comprises at least one unassigned node”, which is directed to repeating the step of retrieving information and /or mental process abstract ideas. Therefore, these are merely repeating the information retrieval and/or mental process abstract idea. Retrieving information do not amount to significantly more. Further, the Specification does not provide additional details that would distinguish the recited components from generic implementation in the combination.
Thus, claim 1 recites a judicial exception of Mental Process without integrating the abstract idea into practical application and do not amount to significantly more. For these same reasons and based on similar analysis as above, claims 15 and 20 also recites judicial exception of Mental Process without integrating the abstract idea into practical application and do not amount to significantly more.
Dependent claim 2 recites the reconfigurable processor comprises arrays of coarse-grained reconfigurable (CGR) units, which is well-understood, routine and conventional ([0003]), and is neither inventive nor provide improvement to the already known technology or technical field.
Dependent claim 3 recites “determining a location of a most recently assigned node of the already assigned nodes as the starting location on the reconfigurable processor”; “determining a location of one of the already assigned nodes as the starting location on the reconfigurable processor, wherein an edge with a highest bandwidth requirement connects the current node with the one of the already assigned nodes; or determining a location with a minimum gravitational pull that the current node experiences through connections with the already assigned nodes as the starting location on the reconfigurable processor, wherein connections with a higher bandwidth requirement exert a higher attraction force than connections with a lower bandwidth requirement”, which is directed to determining a starting location based on given criteria of bandwidth, gravitational pull, and can be performed by human mind alone or with the help of pen and paper.
Dependent claim 4 recites “determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location, wherein a suitable candidate location of the predetermined number of suitable candidate locations includes circuitry that is unassigned and able to implement the current node”, which is directed to a combination of observation, evaluation, judgement and opinion and can be performed by human mind alone or with the help of pen and paper. Claims 5-6 also recites similar limitations and are directed to mental process abstract idea.
Dependent claims 7-10 is directed to valuation associated with placing the current node at the candidate location based on one or more criterion, which can be performed by human mind alone or with the help of pen and paper.
Dependent claim 11 recites determining whether the current node is a critical node, which is directed to characterizing the node, and neither inventive nor provide improvement to the technology / technical field.
Dependent claim 12 recites in response to determining that the current node is a critical node: determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location; and for each one of the first predetermined number of candidate locations, determining a second predetermined number of candidate locations on the reconfigurable processor for placing unplaced neighbors of the current node, which is a combination of observation, evaluation, judgement and opinion and can be performed by human mind alone or with the help of pen and paper.
Dependent claim 13 recites in response to determining that the current node is a critical node: determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location; and in response to determining that the current node is not a critical node: determining a second predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location, wherein the second predetermined number of candidate locations is smaller than the first predetermined number of candidate locations, which is a combination of observation, evaluation, judgement and opinion and can be performed by human mind alone or with the help of pen and paper.
Dependent claim 14 recites determining whether an edge with a relative bandwidth requirement above a predetermined threshold connects the current node with an already assigned node of the already assigned nodes, or determining whether the current node has more than a predetermined number of neighbor nodes, which is directed to mental process abstract idea and can be performed by human mind alone or with the help of pen and paper.
Based on similar analysis as above, dependent claims 16-19 recite claim elements that are either abstract idea or additional claim elements, that individually or in combination, are either generic computing methods/components or insignificant pre/post solution activity and neither integrate into practical application nor amount to significantly more.
Therefore, the claim(s) 1-20 are rejected under 35 U.S.C. 101 as being directed to judicial exception without integrating into practical application or significantly more.
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.
Claims 1-4, 6-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Coene et al. (US 2007/0220522 A1, hereafter Coene) in view of Ying et al. (US 2022/0217054 A1, hereafter Ying).
As per claim 1, Coene teaches the invention substantially as claimed including a method of operating a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor, comprising ([0009] mapping tasks of at least one application on processing units of reconfigurable array, graph representation of the computation engine):
receiving an architectural specification of the reconfigurable processor ([0196] architecture, interconnect strategies, cluster group sizes, cluster architecture [0199] architecture description);
receiving the sorted operation unit graph having an ordered sequence of nodes and edges that interconnect nodes in the ordered sequence of nodes ([0009] receiving a suitable graph representation of the computation engine, computational elements of the computation engine being represented as vertices [0162] edges E can model the connectivity that exists between the architecture resources [0140] set of edges E can contain the switches connecting these resources);
repeating as long as the ordered sequence of nodes comprises at least one unassigned node ([0143] placing starting vertex, data structure, placing all of its successors, data structure, queue, such as FIFO/stack/LIFO, priority queue [0075] iterative placement algorithm [0099] constructive placement algorithm [0100] select and place repeatedly until all modules are placed):
in order of the ordered sequence of nodes, retrieving a first unassigned node from the ordered sequence of nodes as a current node ([0143] placing starting vertex, data structure, placing all of its successors, data structure, queue, such as FIFO/stack/LIFO, priority queue [0100] select function, determine, order, unplaced modules are added, order, determined by how strongly the unplaced modules are connected to the placed components);
determining a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node ([0089] source vertex [0141] starting the search at the source vertex and looking for destination vertex [0101] place function finds the best position for the module chosen by select; every possible position adjacent to the current partial placement );
determining candidate locations on the reconfigurable processor for placing the current node based on the starting location ( [0141] starting the search at the source vertex and looking for destination vertex [0101] place function; value every possible position adjacent to the current partial placement);
for each candidate location of the candidate locations, determining a valuation associated with placing the current node at the candidate location ([0101] calculate the score for every possible position adjacent to the current partial placement [0009] cluster growth algorithm uses a key value derived from the distance between the source vertex and a current vertex and estimated distance between a current vertex and a destination vertex);
selecting among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion ( [0101] module, placed, at the candidate position with the highest score [0009] placement algorithm [0172] placer, various placement alternatives, total mapping cost [0178] best-so-far);
assigning the current node to the target location ([0101] module, placed, at the candidate position with the highest score); and
assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor ([0162] edges E can model the connectivity that exists between the architecture resources [0164] path through edge j to vertex i [0140] set of edges E can contain the switches connecting these resources).
Coene doesn’t specifically teach sorted operation unit graph having an ordered sequence of nodes.
Ying, however, teaches sorted operation unit graph having an ordered sequence of nodes ([0021] topological sorting, DAG graph, acquiring, linear sequence of all nodes in the DAG graph).
It would have been obvious to one of ordinary skills in the art before the effective filing date of the claimed invention to combine the teachings of Coene with the teachings of Ying of topological order traversal of the graph to improve efficiency and allow sorted operation unit graph having an ordered sequence of nodes to the method of Coene as in the instant invention. The combination would have been obvious because applying the topological sorting of DAG graph as taught by Ying to the method of obtaining graph as taught by Coene to yield predictable result with improved efficiency.
As per claim 2, Coene teaches wherein the reconfigurable processor comprises arrays of coarse-grained reconfigurable (CGR) units ([0013] coarse-grain configurable array).
As per claim 3, Coene teaches wherein determining a starting location on the reconfigurable processor further comprises ([0089] starting, source vertex):
determining a location of a most recently assigned node of the already assigned nodes as the starting location on the reconfigurable processor ([0101] possible adjacent to the current [0113] start from random initial placement [0123] initial set or population of random placements);
determining a location of one of the already assigned nodes as the starting location on the reconfigurable processor ([0101] possible adjacent to the current partial placement [0113] start from random initial placement [0123] initial set or population of random placements ), wherein an edge with a highest bandwidth requirement connects the current node with the one of the already assigned nodes; or
determining a location with a minimum gravitational pull that the current node experiences through connections with the already assigned nodes as the starting location on the reconfigurable processor ([0101] possible adjacent to the current partial placement [0113] start from random initial placement [0123] initial set or population of random placements [0117] force, spring, proportional to the amount of compression or stretching that is applied to it; forces exerted by modules B-E are graphically represented as springs in the star-wire model fig. 8A/B [0118] forces exerted by modules connected by nets [0120] initial placement, choose, module, place it its minimum-force location), wherein connections with a higher bandwidth requirement exert a higher attraction force than connections with a lower bandwidth requirement.
As per claim 4, Coene teaches wherein determining candidate locations on the reconfigurable processor for placing the current node based on the starting location further comprises:
determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location ([0141] starting the search at the source vertex and looking for destination vertex [0101] place function; value every possible position adjacent to the current partial placement; calculate the score for every possible position adjacent to the current partial placement [0009] cluster growth algorithm uses a key value derived from the distance between the source vertex and a current vertex and estimated distance between a current vertex and a destination vertex);),
wherein a suitable candidate location of the predetermined number of suitable candidate locations includes circuitry that is unassigned and able to implement the current node ([0101] module, placed, at the candidate position with the highest score, place function; value every possible position adjacent to the current partial placemen [0009] placement algorithm ( [0141] starting the search at the source vertex and looking for destination vertex [0172] placer, various placement alternatives, total mapping cost [0178] best-so-far).
As per claim 6, Coene teaches wherein determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location further comprises ([0101] place function; value every possible position adjacent to the current partial placement; calculate the score for every possible position adjacent to the current partial placement):
iteratively moving with increasing distance from the starting location in a same row, a same column, and diagonally ([0132] fig. 10 propagated from the source to the closes sink; cel S labelled i are labelled as i+1).
As per claim 7, Coene teaches wherein determining the valuation associated with placing the current node at the candidate location further comprises:
determining the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes ( [0101] calculates the score for every possible position adjacent to the current partial placement. The module is then placed at the candidate position with the highest score [0087] length of interconnection).
As per claim 8, Coene teaches wherein determining the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes further comprises ([0101] module, placed, at the candidate position with the highest score, place function; value every possible position adjacent to the current partial placemen):
determining a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes;
determining a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes weighted with associated bandwidth requirements;
determining a number of switches required for connecting the current node with the already assigned nodes ([0200] directed graph, set of Edges containing the switches connecting the resources i.e. number of switch is same as number of edges); or
determining a channel usage required for connecting the current node with the already assigned nodes ([0162] routing channel with 4 tracks can have a capacity of 4, occupancy is the number of signals that are currently using the resource; table 3 ).
As per claim 9, Ying teaches wherein determining the valuation associated with placing the current node at the candidate location further comprises:
determining a weighted sum of two or more criteria associated with placing the current node at the candidate location ([0041] layer score calculation function, weighted average value, sum of flow direction weight values involved in the path).
As per claim 10, Coene teaches wherein determining the valuation associated with placing the current node at the candidate location further comprises:
determining a first criterion associated with placing the current node at the candidate location ([0218] mapping cost function, base cost); and
determining a second criterion associated with placing the current node at the candidate location for breaking ties between two candidate locations of the candidate locations that have a same first criterion ([0218] mapping cost function, base cost, history of congestion ).
As per claim 11, Coene teaches determining whether the current node is a critical node ([0218] node usage, node overuse).
As per claim 12, Coene teaches further comprising:
in response to determining that the current node is a critical node ([0218] node usage, node overuse):
determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location ([0101] score, every possible position adjacent to the current partial placement [0113] start from random initial placement [0123] initial set or population of random placements); and
for each one of the first predetermined number of candidate locations, determining a second predetermined number of candidate locations on the reconfigurable processor for placing unplaced neighbors of the current node ([0100] performing two functions repeatedly [0101] score, every possible position adjacent to the current partial placement [0113] start from random initial placement [0123] initial set or population of random placements).
As per claim 13, Coene teaches further comprising:
in response to determining that the current node is a critical node ([0218] node usage, node overuse):
determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location ([0101] score, every possible position adjacent to the current partial placement); and
in response to determining that the current node is not a critical node ([0218] node usage, node overuse i.e. can also detect node is not a critical):
determining a second predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location ([0101] score, every possible position adjacent to the current partial placement);
wherein the second predetermined number of candidate locations is smaller than the first predetermined number of candidate locations ([0006] as the number of processing units is increased, the number of possible placement positions increases quickly).
As per claim 14, Coene teaches wherein determining whether the current node is a critical node further comprises:
determining whether an edge with a relative bandwidth requirement above a predetermined threshold connects the current node with an already assigned node of the already assigned nodes, or
determining whether the current node has more than a predetermined number of neighbor nodes ([0009] placement algorithm, processing units is fewer / greater than a first /second/ third / fourth predetermined threshold).
Claim 15 recites a placer and router for elements of claim 1. Therefore, it is rejected for the same rationales.
Claim 16 recites a placer and router for elements of claim 3. Therefore, it is rejected for the same rationales.
Claim 17 recites a placer and router for elements of claim 4. Therefore, it is rejected for the same rationales.
Claim 18 recites a placer and router for elements of claim 7. Therefore, it is rejected for the same rationales.
Claim 19 recites a placer and router for elements of claim 8. Therefore, it is rejected for the same rationales.
Claim 20 recites non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to perform limitations similar to claim 1. Therefore, it is rejected for the same rationale.
Claims 5 is/are rejected under 35 U.S.C. 103 as being unpatentable over Coene in view of Ying, as applied to above claims, and further in view of Dong et al. (US 2022/0121928 A1, hereafter Dong).
As per claim 5, Coene teaches wherein determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location further comprises ([0101] place function; value every possible position adjacent to the current partial placement; calculate the score for every possible position adjacent to the current partial placement):
moving from the starting location in direction of a location of an already assigned node of the already assigned nodes ([0101] place function; value every possible position adjacent to the current partial placement; calculate the score for every possible position adjacent to the current partial placement), wherein the already assigned node has a connection with a highest bandwidth requirement with the current node among all connections that the current node has with the already assigned nodes ([0101] place function; value every possible position adjacent to the current partial placement; calculate the score for every possible position adjacent to the current partial placement).
Coene and Ying, in combination, do not specifically teach connections with a highest bandwidth requirement.
Dong, however, teaches connections with a highest bandwidth requirement ( [0142] fig. 5 job requires increased bandwidth, grouping of nodes, set of the network configurations [0145] particular nodal configuration, there may be a bandwidth network optimized configuration [0150] identify the computational burden imposed by the processing task and/or a priority associated with the processing task, and use these characteristics to select from scalability, bandwidth, or latency optimized [0157] profile specifying a second configuration having connections set to provide increased bandwidth than the first configuration).
It would have been obvious to one of ordinary skills in the art before the effective filing date of the invention was made to combine the teachings of placement and routing of processing array of reconfigurable processor as taught by the combination of Coene and Ying with the teachings of Dong of configuration of nodes having increased bandwidth for the job requiring increased bandwidth to improve throughput and allow connections with a highest bandwidth requirement to the method of Coene and Ying as in the instant invention. The combination would have been obvious because applying the known method of nodal configuration with higher bandwidth for jobs requiring higher bandwidth as taught by Dong to the placement and routing of processing array of reconfigurable processor as taught by the combination of Coene and Ying to yield expected results and improved efficiency.
Examiners Note
Applicant is further reminded of that the cited paragraphs and in the references as applied to the claims above for the convenience of the applicant(s) and although the specified citations are representative of the teachings of the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested from the applicant in preparing responses, to fully consider all of the references in entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner.
Allowable Subject Matter
Claims 13 , 14 (i.e. 1+13+14 - only first part of or limitations of claim 14 ) 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
Authorization for Internet Communication
Applicant is encouraged to submit an authorization to communicate with the Examiner via the internet by making the following statement (MPEP 502.03)
“Recognizing that internet communications are not secure, I hereby authorize the USPTO to communicate with the undersigned and practitioners in accordance with 37 CFR 1.33 and 37 CFR 1.34 concerning any subject matter of this application by video conferencing, instant messaging, or electronic mail. I understand that a copy of these communications will be made of record in the application file.”
Please note that the above statement can only by submitted via Central Fax (not Examiner’s Fax), Regular postal mail, or EFS Web using PTO/SB/439.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ABU ZAR GHAFFARI whose telephone number is (571)270-3799. The examiner can normally be reached on Monday-Thursday 9:00 - 17:00 Hrs.
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, Aimee Lee can be reached on 571-272-4169. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/ABU ZAR GHAFFARI/Primary Examiner, Art Unit 2195