Optimization of a data flow program based on access pattern information

Patent metadata

Field	Value
Publication number	US-9335977-B2
Application number	US-201314050084-A
Country	US
Kind code	B2
Filing date	Oct 9, 2013
Priority date	Jul 28, 2011
Publication date	May 10, 2016
Grant date	May 10, 2016

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.

First claim

We claim:

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;
generating a program that implements the functionality of the data flow diagram based at least in part on the access pattern information, wherein the functionality comprises digital signal processing (DSP) and communications, industrial test and measurement, or industrial automation and control; and
configuring a hardware device according to the generated program.

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 a respective cycle during execution of the actor and specifies a 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 a 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 a respective cycle during execution of the actor and specifies a 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 said generating the program comprises optimizing one or more features of the program based at least in part on the access pattern information.

13. The non-transitory computer accessible memory medium of claim 12 , 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.

14. The non-transitory computer accessible memory medium of claim 12 , wherein the one or more features of the program to be optimized include one or more of: buffer size, throughput, or latency.

15. The non-transitory computer accessible memory medium of claim 12 , 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.

16. The non-transitory computer accessible memory medium of claim 12 , 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.

17. The non-transitory computer accessible memory medium of claim 16 , 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.

18. The non-transitory computer accessible memory medium of claim 16 , 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.

19. The non-transitory computer accessible memory medium of claim 16 ,
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.

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

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

22. The non-transitory computer accessible memory medium of claim 16 , 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.

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

Assignees

• Nat Instr Corp

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

Classifications

• G06F9/4494

  data driven · CPC title

• G06F8/34 Primary

  Graphical or visual programming · CPC title

• G06F30/33

  Design verification, e.g. functional simulation or model checking · CPC title

• G06F30/34

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F17/5022

  Physics · mapped topic