User interface for developing and executing data flow programs and methods, apparatus, and articles of manufacture for optimizing the execution of data flow programs

• US 6,389,587 B1
• Filed: 02/04/1999
• Issued: 05/14/2002
• Est. Priority Date: 02/04/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lewis, Bradley
• Primary Examiner(s): Dam, Tuan Q.
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/244,136
• Time in Patent Office: 1,195 Days
• Field of Search: 717/1, 717/4, 717/2, 717/3, 717/9, 345/348, 709/101, 707/503, 716/3
• US Class Current: 717/151
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 9/4494 data driven

Abstract

Methods, systems, and articles of manufacture consistent with the present invention provides a development tool that enables computer programmers to design and develop a data flow program for execution in a multiprocessor computer system. The tool displays an interface that enables the programmer to define a region divided into multiple blocks, wherein each block is formed of a set of values associated with a function, and to define sets of the blocks, each block in a set having a state reflected by a designated portion of the program that when executed transforms the values forming the block based on the function. The interface also records any dependencies among the blocks, each dependency indicating a relationship between two blocks and requiring the portion of the program associated with a first block of the relationship to be executed before the portion of the program associated with a second block of the relationship. After program development, blocks are selected for execution of the corresponding, designated portions of the program based on the recorded dependencies.

Claims

1. A computer-implemented method for at least one of reconfiguring the processing flow of an existing software program according to a data flow model, and developing a new software program according to said data flow model, said method comprising:

displaying a screen display; and

permitting a user to;

specify a memory region and divide said memory region into a plurality of blocks, each block of said plurality of blocks defining a set of values associated with a function;

define sets of the blocks, each block in a set having a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said block based on the function; and

assign any dependencies among the blocks wherein each dependency indicates a relationship between a plurality of said blocks based on said predetermined state of each.

2. A data processing system containing a development tool that displays a user interface for at least one of reconfiguring the processing flow of an existing software program according to a data flow model, and developing a new software program according to said data flow model, said user interface comprising:

a first view configured to receive instructions defining a memory region and dividing said memory region into a plurality of blocks, each block of said plurality of blocks defining a set of values associated with a function;

a second view configured to receive instructions defining sets of the blocks, each block in a set having a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said blocks based on the function; and

a third view configured to receive information reflecting any dependencies among the blocks, wherein each dependency indicates a relationship between a plurality of said blocks based on said predetermined state of each block.

3. The graphical user interface of claim 2, wherein a dependency relationship between two blocks requires the portion of the program associated with one of the two blocks to be executed before the portion of the program associated with the other block.

4. A data processing system, comprising:

a memory containing;

a first program;

a development tool for developing a second software program according to a data flow model, including (i) a memory region divided into region into a plurality of blocks, wherein each block in said plurality of blocks defines a set of values associated with a function and has a predetermined state reflected by a designated portion of the first program that when executed transforms the values defined by said block based on the functions, and (ii) any dependencies among the blocks, each wherein dependency indicates a relationship between two blocks and requiring the portion of the first program associated with a first block of the relationship to be executed before the portion of the first program associated with a second block of the relationship; and

at least one processor for running the development tool.

5. The data processing system of claim 4, further comprising:

a plurality of parallel processors for executing the second program in accordance with the stored dependencies.

6. A data processing system for at least one of reconfiguring the processing flow of an existing software program according to a data flow model, and developing a new software program according to said data flow model, said system comprising:

a memory having instructions; and

a processor responsive to the instructions and configured to permit a user to (i) specify a memory region and divide said memory region into a plurality of blocks, each block in said plurality of blocks defining a set of values associated with a function, (ii) define sets of the blocks, each block in a set having a predetermined state reflected by a designated portion of said program that when executed transforms the values defined by said block based on the function, and (iii) assign any dependencies among the blocks wherein each dependency indicates a relationship between a plurality of said blocks based on said predetermined state of each block.

7. A computer-readable medium containing instructions for controlling a data processing system to perform a method for at least one of reconfiguring a processing flow of an existing software program according to a data flow model, and developing a new software program according to said data flow model, said method comprising:

permitting a user to specify a memory region and divide said memory region into a plurality of blocks, each block of said plurality of blocks defining a set of values associated with a function;

permitting a user to define sets of the blocks, each block in a set having a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said block based on the function; and

permitting a user to assign any dependencies among the blocks wherein each dependency indicates a relationship between a plurality of said blocks based on said predetermined state of each block.

8. A computer-readable medium containing instructions for controlling a data processing system to perform a method for at least one of reconfiguring a processing flow of an existing software program according to a data flow model, and developing a new software program according to said data flow model, said method comprising:

displaying a first view configured to receive instructions defining a memory region and dividing said memory region into a plurality of blocks, each block of said plurality of blocks defining a set of values associated with a function;

displaying a second view configured to receive instructions defining sets of the blocks, each block in a set having a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said blocks based on the function; and

displaying a third view configured to receive information reflecting any dependencies among the blocks, wherein each dependency indicates a relationship between a plurality of said blocks based on said predetermined state of each block.

9. The computer-readable medium of claim 8, wherein a dependency relationship between two blocks requires the portion of the program associated with one of the two blocks to be executed before the portion of the program associated with the other block.

10. A method for optimizing execution of a software program according to a data flow model in a multiprocessor computer system, the method comprising:

receiving memory region information, including block information reflecting a plurality of blocks that define a memory region, wherein each block defines a set of values associated with a function and has a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said block based on the function, and dependency information reflecting any dependencies among the blocks, wherein each dependency indicates a relationship between two blocks and requiring the portion of the program associated with a first block of the relationship to be executed before the portion of the program associated with a second block of the relationship; and

forming a queue organizing the memory region information.

11. The method of claim 10, further comprising:

executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue.

12. The method of claim 11, wherein the queue has at least two parts, each part having a priority, and wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, includes:

using a priority assigned to each block to place the blocks in the two parts of the queue.

13. The method of claim 12, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, further includes:

selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority.

14. The method of claim 13, wherein selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, includes:

selecting a block from the high priority part of the queue; and

determining whether all dependency relationships, if any, associated with the selected block from the high priority part of the queue have been satisfied, and initiating execution of the program code associated with that block when it is determined that all dependency relationships, if any, associated with that block have been satisfied.

15. The method of claim 14, wherein selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, includes:

selecting a block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the block selected from the high priority part of the queue have not been satisfied, and initiating execution of the program code associated with the selected block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the selected block from the low priority part of the queue have been satisfied.

16. The method of claim 11, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, includes:

using a priority assigned to each block to place the blocks in at least two queues, each queue having a different priority.

17. The method of claim 16, wherein executing the designated portion of the program associated with each block in accordance with the organization of the queue, further includes:

selecting blocks from the queues based on the priority of each queue with the blocks in the queue having a high priority given preference over blocks in the queue having a low priority.

18. The method of claim 11, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, includes:

pre-fetching available data require for execution of a block when resources to execute the block are available and all of the block'"'"'s dependency relationships have not been satisfied.

19. The method of claim 10, wherein forming a queue organizing the memory region information includes:

generating a directed acyclic graph based on the memory region information with each block having a corresponding node in the graph;

traversing the directed acyclic graph according to a predetermined function; and

placing information identifying each block in the queue based on the traversal of the directed acyclic graph.

20. The method of claim 19, wherein traversing the directed acyclic graph according to a predetermined function includes:

applying weights associated with each block such that no block has a data dependency on a block that has a lesser weight.

21. A system for optimizing a software program based on a data flow model for execution in a multiprocessor computer system, said system comprising:

a memory having a program characterized by memory region information, including block information reflecting a plurality of blocks that define a memory region, wherein each block defines a set of values associated with a function and has a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said block based on the function, and dependency information reflecting any dependencies among the blocks, wherein each dependency indicates a relationship between two blocks and requiring the portion of the program associated with a first block of the relationship to be executed before the portion of the program associated with a second block of the relationship; and

at least one processor configured to form a queue organizing the memory region information.

22. The system of claim 21, wherein the multiprocessor computer system executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue.

23. The system of claim 22, wherein the queue has at least two parts, each part having a priority, and wherein when the processor executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, the processor uses a priority assigned to each block to place the blocks in the two parts of the queue.

24. The system of claim 23, wherein when the processor executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, the processor selects blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority.

25. The system of claim 24, wherein when the processor selects blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, the processor selects a block from the high priority part of the queue, and determines whether all dependency relationships, if any, associated with the selected block from the high priority part of the queue have been satisfied, and initiating execution of the program code associated with that block when it is determined that all dependency relationships, if any, associated with that block have been satisfied.

26. The system of claim 25, wherein when the processor selects blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, the processor selects a block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the block selected from the high priority part of the queue have not been satisfied, and initiating execution of the program code associated with the selected block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the selected block from the low priority part of the queue have been satisfied.

27. The system of claim 22, wherein when the processor executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, the processor uses a priority assigned to each block to place the blocks in at least two queues, each queue having a different priority.

28. The system of claim 27, wherein when the processor executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, the processor selects blocks from the queues based on the priority of each queue with the blocks in the queue having a high priority given preference over blocks in the queue having a low priority.

29. The system of claim 22, wherein when the processor executes the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, the processor pre-fetches available data require for execution of a block when resources to execute the block are available and all of the block'"'"'s dependency relationships have not been satisfied.

30. The system of claim 21, wherein when the processor forms a queue organizing the memory region information, the processor (i) generates a directed acyclic graph based on the memory region information with each block having a corresponding node in the graph, (ii) traverses the directed acyclic graph according to a predetermined function, and (iii) places information identifying each block in the queue based on the traversal of the directed acyclic graph.

31. The system of claim 30, wherein when the processor traverses the directed acyclic graph according to a predetermined function, the processor applies weights associated with each block such that no block has a data dependency on a block that has a lesser weight.

32. A computer-readable medium containing instructions for performing a method for optimizing execution of a software program according to a data flow model in a multiprocessor computer system, the method comprising:

receiving memory region information, including block information reflecting a plurality of blocks that define a memory region, wherein each block defines a set of values associated with a function and has a predetermined state reflected by a designated portion of said program according to said data flow model that when executed transforms the values defined by said block based on the function, and dependency information reflecting any dependencies among the blocks, wherein each dependency indicates a relationship between two blocks and requiring the portion of the program associated with a first block of the relationship to be executed before the portion of the program associated with a second block of the relationship; and

forming a queue organizing the memory region information.

33. The computer-readable medium of claim 32, wherein the method further comprises:

executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue.

34. The computer-readable medium of claim 33, wherein traversing the directed acyclic graph according to a predetermined function includes:

applying weights associated with each block such that no block has a data dependency on a block that has a lesser weight.

35. The computer-readable medium of claim 34, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, further includes:

selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority.

36. The computer-readable medium of claim 35, wherein selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, includes:

selecting a block from the high priority part of the queue; and

determining whether all dependency relationships, if any, associated with the selected block from the high priority part of the queue have been satisfied, and initiating execution of the program code associated with that block when it is determined that all dependency relationships, if any, associated with that block have been satisfied.

37. The computer-readable medium of claim 33, wherein the queue has at least two parts, each part having a priority, and wherein executing the designated portion of the program associated with each block in accordance with the organization of the queue, includes:

using a priority assigned to each block to place the blocks in the two parts of the queue.

38. The computer-readable medium of claim 35, wherein selecting blocks from the two parts of the queues based on the priority of each part of the queue with the blocks in a part of the queue having a high priority given preference over blocks in a part of the queue having a low priority, includes:

selecting a block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the block selected from the high priority part of the queue have not been satisfied, and initiating execution of the program code associated with the selected block from the low priority part of the queue when it is determined that all dependency relationships, if any, associated with the selected block from the low priority part of the queue have been satisfied.

39. The computer-readable medium of claim 38, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, further includes:

selecting blocks from the queues based on the priority of each queue with the blocks in the queue having a high priority given preference over blocks in the queue having a low priority.

40. The computer-readable medium of claim 33, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, includes:

using a priority assigned to each block to place the blocks in at least two queues, each queue having a different priority.

41. The computer-readable medium of claim 33, wherein executing the designated portion of the program associated with each block in accordance with the organization of the memory region information in the queue, includes:

pre-fetching available data require for execution of a block when resources to execute the block are available and all of the block'"'"'s dependency relationships have not been satisfied.

42. The computer-readable medium of claim 32, wherein forming a queue organizing the memory region information includes:

generating a directed acyclic graph based on the memory region information with each block having a corresponding node in the graph;

traversing the directed acyclic graph according to a predetermined function; and

placing information identifying each block in the queue based on the traversal of the directed acyclic graph.