Method and system for merging directed acyclic graphs representing data flow codes
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/46
G06F-009/45
출원번호
US-0837607
(2004-05-04)
등록번호
US-8578389
(2013-11-05)
발명자
/ 주소
Boucher, Michael L.
출원인 / 주소
Oracle America, Inc.
대리인 / 주소
Marsh Fischmann & Breyfogle, LLP
인용정보
피인용 횟수 :
8인용 특허 :
4
초록▼
Methods and systems facilitating a programmer to program parts of a program in data flow programming to produce directed acyclic graphs (“DAGs”), and then merge the graphs at runtime for efficiency and scalability. Large merged DAG can typically be processed with greater efficiency than the collecti
Methods and systems facilitating a programmer to program parts of a program in data flow programming to produce directed acyclic graphs (“DAGs”), and then merge the graphs at runtime for efficiency and scalability. Large merged DAG can typically be processed with greater efficiency than the collection of smaller DAGs. As a result, smaller DAGs may be created while the execution of the program realizes the increased efficiency of executing a larger DAG based on the merging of the smaller DAGs. In accordance with methods and systems consistent with the present invention, a programmer creates individual data flow directed acyclic graphs in a program.
대표청구항▼
1. A method in a data processing system, comprising the steps of: generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual dire
1. A method in a data processing system, comprising the steps of: generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks;merging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs wherein the step of merging the individual directed acyclic graphs at runtime further comprises: comparing a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, andcreating a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; andexecuting the merged directed acyclic graph while the merged directed acyclic graph is being constructed. 2. The method of claim 1, further comprising the steps of: inserting a first function in a program to indicate a first of the generated individual directed acyclic graphs to be merged; andinserting a second function in the program to indicate a last of the individual generated directed acyclic graphs to be merged. 3. The method of claim 2, wherein the step of merging the individual directed acyclic graphs at runtime further comprises the step of: merging at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph. 4. The method of claim 1, wherein the comparing step further includes: comparing each node in the first one of the individual directed acyclic graphs with each node in the second one of the individual directed acyclic graphs to determine if there are dependencies between the compared nodes. 5. A data processing system, comprising: a memory storing a program that: generates a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between plurality of nodes representing the executable tasks,merges the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs, andcompares a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, and creates a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; anda processor for running the program, wherein the program further executes the merged directed acyclic graph while the merged directed acyclic graph is being constructed. 6. The data processing system of claim 5, further including a second program having a first function in the second program to indicate a first of the generated individual directed acyclic graphs to be merged, and a second function in the second program to indicate a last of the generated individual directed acyclic graphs to be merged. 7. The data processing system of claim 6, wherein the program further merges at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph. 8. The data processing system of claim 5, wherein the program further compares each node in the first one of the individual directed acyclic graphs with each node in the second one of the individual directed acyclic graphs to determine if there are dependencies between the compared nodes. 9. A tangible, non-transitory computer-readable medium containing instructions for controlling a data processing system to perform a method, the method comprising the steps of: generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks; andmerging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs;comparing each node in a first one of the individual directed acyclic graphs with each node in a second one of the individual directed acyclic graphs to determine if there are merged dependencies between the compared nodes;creating a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; andexecuting the merged directed acyclic graph while the merged directed acyclic graph is being constructed. 10. The computer-readable medium of claim 9, wherein the method further comprises the steps of: inserting a first function in a program to indicate a first of the generated individual directed acyclic graphs to be merged; andinserting a second function in the program to indicate a last of the generated individual directed acyclic graphs to be merged. 11. The computer-readable medium of claim 10, wherein the step of merging the individual directed acyclic graphs at runtime further comprises the step of: merging at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph. 12. A data processing system, comprising: means for generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks; andmeans for merging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs, wherein the means for merging the individual directed acyclic graphs at runtime is operable to: compare a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, andcreate a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; andmeans for executing the merged directed acyclic graph while the merged directed acyclic graph is being constructed.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (4)
Asawaree Kalavade ; Pratyush Moghe, Methods and apparatus for evaluating effect of run-time schedules on performance of end-system multimedia applications.
Acker Liane Elizabeth ; Conner Michael Haden ; Martin Andrew Richard, Object oriented framework for specifying the format of compiler output with a template facility.
Johnson, Caryl Erin; Aikin, Kay E; Phelps, David S; Johnson, Alexander; Rindlaub, Nathaniel, Executable graph framework for the management of complex systems.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.