Managing parameters for graph-based computations
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/44
G09G-005/00
출원번호
UP-0169014
(2005-06-27)
등록번호
US-7716630
(2010-06-03)
발명자
/ 주소
Wholey, J. Skeffington
Larson, Brond
출원인 / 주소
Ab Initio Technology LLC
대리인 / 주소
Fish & Richardson P.C.
인용정보
피인용 횟수 :
31인용 특허 :
10
초록▼
Ordering parameters in a graph-based computation includes determining a desired first ordering of a set of parameters associated with graph elements in a computation graph; determining an ordering constraint for the set of parameters; and determining a second ordering of the set of parameters that s
Ordering parameters in a graph-based computation includes determining a desired first ordering of a set of parameters associated with graph elements in a computation graph; determining an ordering constraint for the set of parameters; and determining a second ordering of the set of parameters that satisfies the ordering constraint according to the desired first ordering.
대표청구항▼
What is claimed is: 1. A method for ordering parameters in a graph-based computation including: determining, by a processor, a desired first ordering of a set of parameters associated with graph elements in a computation graph; determining, by the processor, an ordering constraint for the set of pa
What is claimed is: 1. A method for ordering parameters in a graph-based computation including: determining, by a processor, a desired first ordering of a set of parameters associated with graph elements in a computation graph; determining, by the processor, an ordering constraint for the set of parameters; and determining, by the processor, a second ordering of the set of parameters that satisfies the ordering constraint according to the desired first ordering; wherein determining the second ordering includes, for each of multiple constrained parameters in the set, associating with the constrained parameter one or more other parameters that constrain the order of the constrained parameter in the second ordering according to the ordering constraint, and for each of multiple iterations, selecting different subsets of one or more parameters in the set to be assigned positions in the second ordering based at least in part on how many other parameters are associated with a given parameter in the subset. 2. The method of claim 1, further including accepting a specification of the computation graph wherein the desired first ordering is based on an order in which the graph elements appear in the specification. 3. The method of claim 1, wherein the graph imposes the ordering constraint. 4. The method of claim 1, further including determining values of the parameters according to the second ordering. 5. The method of claim 4, wherein determining values of the parameters includes prompting for user input. 6. The method of claim 5, further including: determining a parameter value for a first of the parameters based on a user response to the prompting, and executing the graph using the determined parameter value as the value for the first parameter. 7. The method of claim 1, wherein determining the ordering constraint includes determining dependencies between values of the parameters. 8. The method of claim 7, wherein the ordering constraint includes ordering a first parameter after a second parameter if the first parameter depends on the second parameter. 9. The method of claim 1, wherein the ordering constraint correspond to one or more directed acyclic graphs, wherein each vertex of the one or more directed acyclic graphs corresponds to a parameter in the set. 10. The method of claim 1, wherein determining the second ordering includes performing a topological sort of the parameters in the set based on the ordering constraint. 11. The method of claim 1, wherein satisfying the ordering constraint according to the desired first ordering includes preserving a similarity to the first ordering for at least some parameters that are not required to be reordered to satisfy the ordering constraint. 12. The method of claim 1, wherein the one or more other parameters that constrain the order of the constrained parameter in the second ordering according to the ordering constraint include parameters upon which the constrained parameter depends. 13. The method of claim 1, wherein a first selected subset of one or more parameters in the set to be assigned positions in the second ordering includes at least one parameter that is not a constrained parameter. 14. The method of claim 13, wherein a second selected subset of one or more parameters in the set to be assigned positions in the second ordering includes at least one parameter that is a constrained parameter. 15. The method of claim 14, wherein each parameter in the second subset is assigned to a position in the second ordering after all of the parameters in the first subset. 16. The method of claim 15, wherein a third selected subset of one or more parameters in the set to be assigned positions in the second ordering includes at least one parameter that is not a constrained parameter. 17. The method of claim 16, wherein each parameter in the third subset is assigned to a position in the second ordering after all of the parameters in the second subset. 18. The method of claim 1, wherein subsets selected in different iterations do not overlap. 19. The method of claim 18, wherein each parameter in a given subset selected in an iteration after a previous iteration in which a previous subset was selected is assigned to a position in the second ordering after all of the parameters in the previous subset. 20. The method of claim 19, wherein determining the second ordering includes, for each iteration: removing associations between constrained parameters not in any previous subset and any associated parameters that constrain the order of the constrained parameters that were in a previous subset; and after removing the associations, sorting all of the parameters not in any previous subset first by how many other parameters are associated with a given parameter and second by the given parameter's position in the first ordering. 21. The method of claim 1, wherein associating with the constrained parameter one or more other parameters that constrain the order of the constrained parameter in the second ordering according to the ordering constraint includes identifying the other parameters on which the constrained parameter depends in a data structure in association with the constrained parameter. 22. The method of claim 21, wherein selecting the different subsets in the multiple iterations includes iteratively sorting parameters in a list of non-eliminated parameters and eliminating parameters according to dependency constraints represented by the data structure. 23. The method of claim 22, wherein sorting parameters includes ordering parameters first by the number of non-eliminated parameters on which they depend from lowest to highest, and then by their position in the first ordering from lowest to highest. 24. Software stored on a computer-readable medium, for ordering parameters in a graph-based computation, the software including instructions for causing a computer system to: determine a desired first ordering of a set of parameters associated with graph elements in a computation graph; determine an ordering constraint for the set of parameters; and determine a second ordering of the set of parameters that satisfies the ordering constraint according to the desired first ordering; wherein determining the second ordering includes, for each of multiple constrained parameters in the set, associating with the constrained parameter one or more other parameters that constrain the order of the constrained parameter in the second ordering according to the ordering constraint, and for each of multiple iterations, selecting different subsets of one or more parameters in the set to be assigned positions in the second ordering based at least in part on how many other parameters are associated with a given parameter in the subset. 25. A system for ordering parameters in a graph-based computation, the system including: means for determining a desired first ordering of a set of parameters associated with graph elements in a computation graph; means for determining an ordering constraint for the set of parameters; and means for determining a second ordering of the set of parameters that satisfies the ordering constraint according to the desired first ordering; wherein determining the second ordering includes, for each of multiple constrained parameters in the set, associating with the constrained parameter one or more other parameters that constrain the order of the constrained parameter in the second ordering according to the ordering constraint, and for each of multiple iterations, selecting different subsets of one or more parameters in the set to be assigned positions in the second ordering based at least in part on how many other parameters are associated with a given parameter in the subset.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (10)
Steven M. Hoffberg ; Linda I. Hoffberg-Borghesani, Adaptive pattern recognition based control system and method.
Amado Carlos Armando (444 Brickell Avenue #51-111 Miami FL 33131-2400), Method and apparatus for applying if-then-else rules to data sets in a relational data base and generating from the resu.
Sheard Nicolas C. ; Fischer Larry J. ; Matthews Richard W. ; Gurla Himabindu ; Hu Qilin ; Zheng Wendy J. ; Mow Boyle Y., Visual data integration system and method.
Tarditi, Jr., David Read; Harris, Timothy Lawrence; Plesko, Mark Ronald; Shinnar, Avraham E., Compiler support for optimizing decomposed software transactional memory operations.
Douros, Bryan Phil; Atterbury, Matthew Darcy; Stanfill, Craig W.; Wholey, III, Joseph Skeffington; Bromley, H. Mark, Processing transactions in graph-based applications.
Bond, Barry Clayton; Sewelson, Vivian; Leijin, Daniel Johannes Pieter; Litchev, Lubomir Boyanov, Reusing expression graphs in computer programming languages.
Wakeling, Tim; Buxbaum, Mark; Staknis, Mark, Task managing application for performing tasks based on messages received from a data processing application initiated by the task managing application.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.