Determination of timing configurations for program dataflow models

Patent metadata

Field	Value
Publication number	US-10467059-B2
Application number	US-201715471792-A
Country	US
Kind code	B2
Filing date	Mar 28, 2017
Priority date	Mar 31, 2016
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

Abstract

A method for determining timing constraints in dataflow models is disclosed. The method includes receiving node information specifying a plurality of dataflow nodes, as well as coupling between various ones of the dataflow nodes. The method further comprising receiving timing information specifying timing constraints for at least some of the dataflow nodes. Based on the node information, the couplings between the nodes, and the timing information, a timeline dependency graph (TDG). The timeline dependency graph illustrates a timeline, mappings between nodes with side effects to firing times of those nodes on the timeline, and dependencies between nodes.

First claim

What is claimed is:

1. A method, comprising:
by a computer system comprising a processor and a non-transitory memory medium:
storing, in the memory medium, node information for a plurality of dataflow nodes, wherein each of the nodes is a program function that consumes data on at least one input and produces data on at least one output, and wherein the node information includes couplings between particular ones of the nodes;
storing, in the memory medium, timing constraints for one or more of the nodes;
generating, using the processor, a timeline dependency graph (TDG) based on the node information, couplings between particular ones of the nodes, and the timing constraints, wherein the TDG includes a timeline, mappings between particular ones of the nodes that have side effects, on the timeline, to their respective firing times, and dependencies between nodes;
displaying the TDG on a display unit coupled to the computer system; and
mapping the plurality of dataflow nodes onto different ones of a plurality of heterogeneous hardware elements of a target system, wherein said mapping is performed based at least in part on a determination that the plurality of dataflow nodes comprises a valid program operation, and wherein the plurality of dataflow nodes are executable on the different ones of the plurality of heterogenous hardware elements according to the mapping.

2. The method as recited in claim 1 , wherein the side effects for particular ones of the nodes comprise interaction with a physical environment via input/output (I/O) through those nodes.

3. The method as recited in claim 1 , wherein the node information specifies consumption rates and production rates for multiple ones of the plurality of data flow nodes within a multi-rate dataflow program.

4. The method as recited in claim 1 , wherein at least a portion of the timing information specifies timing constraints using absolute time.

5. The method as recited in claim 1 , wherein at least a portion of the timing information specifies timing constraints using period information and offset information.

6. The method as recited in claim 1 , wherein at least a portion of the timing information specifies timing constraints using event-trigger information.

7. The method as recited in claim 1 , wherein the dependencies include dependencies between nodes having side effects and nodes having no side effects.

8. The method as recited in claim 1 , wherein the TDG indicates whether a data flow program comprising the plurality of dataflow nodes is valid based on the timing constraints.

9. The method as recited in claim 1 , wherein the TDG is configured to indicate the consistency, deadlock, latency bounds on paths, and period information of each node.

10. The method as recited in claim 1 , further comprising determining all possible interleavings for a data flow program between event triggered and time-triggered nodes.

11. A system comprising:
at least one processor;
a display unit; and
a storage device storing a multi-rate dataflow program and a plurality of instructions that, when executed by the at least one processor, cause the system to:
store, in the storage device, node information for a plurality of dataflow nodes of the multi-rate dataflow program, wherein each of the nodes is a program function that consumes data on at least one input and produces data on at least one output, and wherein the node information includes couplings between particular ones of the nodes;
store, in the storage device, timing constraints for one or more of the nodes;
generate, using the processor, a timeline dependency graph (TDG) based on the node information, couplings between particular ones of the nodes, and the timing constraints, wherein the TDG includes a timeline, mappings between particular ones of the nodes that have side effects, on the timeline, to their respective firing times, and dependencies between nodes;
display, on the display unit, the TDG;
map the plurality of dataflow nodes onto different ones of a plurality of heterogeneous hardware elements of a target system, wherein said mapping is performed based at least in part on a determination that the multi-rate dataflow program comprises a valid program operation, and wherein the plurality of dataflow nodes are executable on the different ones of the plurality of heterogenous hardware elements according to the mapping.

12. The system as recited in claim 11 , wherein the side effects for particular ones of the nodes comprise interaction with a physical environment via input/output (I/O) through those nodes.

13. The system as recited in claim 11 , wherein the node information specifies consumption rates and production rates for multiple ones of the plurality of data flow nodes within the multi-rate dataflow program.

14. The system as recited in claim 11 , wherein the node information specifies one or more of the following:
timing constraints using absolute time;
timing constraints using period information and offset information;
timing constraints using event-trigger information.

15. The system as recited in claim 11 , wherein the dependencies include dependencies between nodes having side effects and nodes having no side effects.

16. The system as recited in claim 11 , wherein the storage device further includes instructions that, when executed by the at least one processor, determine whether a data flow program is schedulable on a hardware platform based on the timing information, a scheduling policy, and worst-case execution times for the nodes, and includes further instructions, that when executed by the at least one processor responsive to determining that the dataflow program is not schedulable, perform at least one of the following:
inserting one or more downsample or upsample nodes on a failing path;
adjusting initial timing tokens;
adjusting period on one or more nodes;
adjusting one or more latency parameters; or
configuring one or more phase delay parameters.

17. The system as recited in claim 11 , wherein the timing information further includes a synchronization error for synchronization between the nodes.

18. A non-transitory computer readable medium storing instructions that, when executed by a processor of a computer system, cause the computer system to perform the following:
store node information for a plurality of dataflow nodes of a multi-rate dataflow program, wherein each of the nodes is a program function that consumes data on at least one input and produces data on at least one output, and wherein the node information includes couplings between particular ones of the nodes;
store timing constraints for one or more of the nodes;
generate, using the processor, a timeline dependency graph (TDG) based on the node information, couplings between particular ones of the nodes, and the timing constraints, wherein the TDG includes a timeline, mappings between particular ones of the nodes that have side effects, on the timeline, to their respective firing times, and dependencies between nodes;
display the TDG on a display unit coupled to the computer system;
map the plurality of dataflow nodes onto different ones of a plurality of heterogeneous hardware elements of a target system, wherein said mapping is performed based at least in part on a determination that the multi-rate dataflow program comprises a valid program operation, and wherein the plurality of dataflow nodes are executable on the different ones of the plurality of heterogenous hardware elements according to the mapping.

19. The computer read

Assignees

• Nat Instruments Corp

Inventors

• Derler Patricia
• Ravindran Kaushik
• Andrade Hugo A
• Prasad Ankita
• Ghosal Arkadeb
• Tran Trung N
• Limaye Rhishikesh
• Kornerup Jacob

Classifications

• G06F13/4068

  Electrical coupling · CPC title

• G06F13/366 Primary

  using a centralised polling arbiter · CPC title

• G06F9/5011 Primary

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title