Optimization of a Data Flow Program Based on Access Pattern Information

• US 20140040855A1
• Filed: 10/09/2013
• Published: 02/06/2014
• Est. Priority Date: 07/28/2011
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Wang, Guoqiang, Ravindran, Kaushik, Limaye, Rhishikesh, Yang, Guang, Ghosal, Arkadeb, Andrade, Hugo A., Allen, John R., Kornerup, Jacob, Wong, Ian C., Correll, Jeffrey N., Trimborn, Michael J.
• Granted Patent: US 9,335,977 B2
• Time in Patent Office: Days
• US Class Current: 717/107
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/343 Logical level
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 9/4494 data driven

Abstract

System and method for optimizing a data flow diagram based on access pattern information are described. Access pattern information for a data flow diagram may be received. The data flow diagram may include a plurality of interconnected actors, e.g., functional blocks, visually indicating functionality of the data flow diagram. The access pattern information may include one or more of: input pattern information specifying cycles on which tokens are consumed by at least one of the actors, or output pattern information specifying cycles on which tokens are produced by at least one of the actors. A program that implements the functionality of the data flow diagram may be generated based at least in part on the access pattern information.

Claims

1. A non-transitory computer accessible memory medium that stores program instructions executable by a processor to implement:

receiving access pattern information for a data flow diagram, wherein the data flow diagram includes a plurality of interconnected actors visually indicating functionality of the data flow diagram, wherein the access pattern information includes one or more of;

a) input pattern information specifying the time at which tokens are consumed by at least one of the actors, or b) output pattern information specifying the time at which tokens are produced by at least one of the actors; and

generating a program that implements the functionality of the data flow diagram based at least in part on the access pattern information.

2. The non-transitory computer accessible memory medium of claim 1, wherein the access pattern information includes input pattern information specifying the time at which tokens are consumed by a plurality of the actors.

3. The non-transitory computer accessible memory medium of claim 1, wherein the input pattern information for an actor comprises information indicating when the actor'"'"'s input tokens are consumed relative to the beginning of the at least one actor'"'"'s execution.

4. The non-transitory computer accessible memory medium of claim 1, wherein the input pattern information specifies the particular time at which input tokens are consumed by the actor.

5. The non-transitory computer accessible memory medium of claim 1, wherein the input pattern information comprises a plurality of values, wherein each of the values corresponds to one of the cycles during the execution of the actor and specifies the number of tokens consumed by the actor on that cycle.

6. The non-transitory computer accessible memory medium of claim 1, wherein the access pattern information includes output pattern information specifying the time at which tokens are produced by a plurality of the actors.

7. The non-transitory computer accessible memory medium of claim 1, wherein the output pattern information for an actor comprises information indicating when the actor'"'"'s output tokens are produced relative to the beginning of the at least one actor'"'"'s execution.

8. The non-transitory computer accessible memory medium of claim 1, wherein the output pattern information specifies the particular the time at which output tokens are produced by the actor.

9. The non-transitory computer accessible memory medium of claim 1, wherein the output pattern information comprises a plurality of values, wherein each of the values corresponds to one of the cycles during the execution of the actor and specifies the number of tokens produced by the actor on that cycle.

10. The non-transitory computer accessible memory medium of claim 1, wherein the program instructions are further executable by a processor to implement:

converting the data flow diagram into an intermediate representation, wherein said generating the program comprises generating the program from the intermediate representation.

11. The non-transitory computer accessible memory medium of claim 1, wherein the program instructions are further executable by a processor to implement:

receiving input specifying additional information for the data flow diagram, wherein the additional information includes one or more of;

one or more execution times for one or more of the actors;

or

one or more initiation intervals for one or more of the actors;

wherein said generating the program is further based on the additional information.

12. The non-transitory computer accessible memory medium of claim 1, wherein the program instructions are further executable by a processor to implement:

configuring a hardware device according to the generated program.

13. The non-transitory computer accessible memory medium of claim 1, wherein said generating the program comprises optimizing one or more features of the program based at least in part on the access pattern information.

14. The non-transitory computer accessible memory medium of claim 13, wherein the program instructions are further executable by a processor to implement:

receiving user input specifying the one or more features of the program to be optimized.

15. The non-transitory computer accessible memory medium of claim 13, wherein the one or more features of the program to be optimized include one or more of:

buffer size, throughput, or latency.

16. The non-transitory computer accessible memory medium of claim 13, wherein said optimizing the one or more features of the program comprises optimizing one or more of the following based at least in part on the access pattern information:

throughput of terminals on the actors;

throughput of the program;

clock rate of the program;

a size of a buffer between actors;

or

latency between actor inputs and corresponding actor outputs.

17. The non-transitory computer accessible memory medium of claim 13, wherein said optimizing the one or more features of the program comprises:

automatically formulating an objective function based on the one or more features of the program to be optimized;

automatically generating one or more constraints for the objective function based at least in part on the access pattern information;

applying a solver to the objective function to find at least one minimum value or maximum value that at least one variable of the objective function can take on, subject to the one or more constraints; and

configuring the program according to the at least one minimum value or maximum value, wherein said configuring optimizes the one or more features of the program.

18. The non-transitory computer accessible memory medium of claim 17, wherein said automatically generating the one or more constraints for the objective function comprises automatically generating one or more of:

at least one producer-consumer constraint;

at least one auto-concurrency constraint;

at least one buffer size constraint;

or

at least one resource utilization constraint.

19. The non-transitory computer accessible memory medium of claim 17, wherein said automatically generating the one or more constraints for the objective function comprises automatically generating one or more of:

a linear constraint;

a quadratic constraint;

a difference constraint;

or a propositional logic constraint.

20. The non-transitory computer accessible memory medium of claim 17,

wherein said automatically generating the one or more constraints for the objective function comprises automatically generating a quadratic constraint;

and

wherein the method further comprises transforming the quadratic constraint into a linear constraint.

21. The non-transitory computer accessible memory medium of claim 17, wherein the one or more constraints are all integer linear constraints.

22. The non-transitory computer accessible memory medium of claim 17, wherein the solver returns an approximation to the at least one minimum value or maximum value rather than an exact value.

23. The non-transitory computer accessible memory medium of claim 17, wherein the solver is one of a mixed integer linear programming (MILP) solver, mixed integer quadratic constraints programming (MIQCP solver), or satisfiability modulo theories (SMT) solver.

24. The non-transitory computer accessible memory medium of claim 17, wherein said generating the one or more constraints comprises using a technique for optimizing functions.

25. The non-transitory computer accessible memory medium of claim 17, wherein said generating the one or more constrains comprises transforming the constraints using a technique for optimizing functions.

26. The non-transitory computer accessible memory medium of claim 17, wherein said generating the one or more constrains comprises simulating execution of the data flow diagram.

27. The non-transitory computer accessible memory medium of claim 17, wherein said generating the one or more constraints uses a scheduling scheme.

28. The non-transitory computer accessible memory medium of claim 27, wherein the scheduling scheme is a static fine-grained scheduling scheme.

29. The non-transitory computer accessible memory medium of claim 1, wherein the data flow diagram is hierarchical, comprising one or more sub-diagrams.

30. The non-transitory computer accessible memory medium of claim 1, wherein each actor comprises a respective functional block.

31. A method comprising:

utilizing a computer to perform;

receiving access pattern information for a data flow diagram, wherein the data flow diagram includes a plurality of interconnected actors visually indicating functionality of the data flow diagram, wherein the access pattern information includes one or more of;

a) input pattern information specifying the time at which tokens are consumed by at least one of the actors, or b) output pattern information specifying the time at which tokens are produced by at least one of the actors; and

generating a program that implements the functionality of the data flow diagram based at least in part on the access pattern information.

32. A non-transitory computer accessible memory medium that stores program instructions executable by a processor to implement:

receiving access pattern information for a data flow specification, wherein the data flow specification specifies a plurality of functional actors that perform functionality according to a data flow model of computation, wherein the access pattern information includes one or more of;

a) input pattern information specifying the time at which tokens are consumed by at least one of the functional actors, or b) output pattern information specifying the time at which tokens are produced by at least one of the functional actors; and

generating a program that implements the functionality based on the data flow specification and the access pattern information.