Implementing a class oriented data flow program on a programmable hardware element
View Patent ↗System and method for converting a class oriented data flow program to a structure oriented data flow program. A first data flow program is received, where the first data flow program is an object oriented program comprising instances of one or more classes, and wherein the first data flow program is executable to perform a first function. The first data flow program is automatically converted to a second data flow program, where the second data flow program does not include the instances of the one or more classes, and where the second data flow program is executable to perform the first function. The second data flow program is stored on a computer memory, where the second data flow program is configured to be deployed to a device, e.g., a programmable hardware element, and where the second data flow program is executable on the device to perform the first function.
1. A non-transitory computer accessible memory medium that stores program instructions executable by a processor to:
receive a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, and wherein the first data flow program is executable to perform a first function; and
automatically convert the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein, to automatically convert the first data flow program to a second data flow program, the program instructions are executable to convert the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein to automatically convert the first data flow program, the program instructions are further executable to:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation, replace the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if an input class specified for the subprogram is an ancestor class of a corresponding child class specified as input in the invocation:
clone the subprogram, thereby generating a clone subprogram;
replace any reference to the ancestor class in inputs of the clone subprogram with a reference to the child class; and
replace the subprogram invocation with an invocation of the clone subprogram;
iii) perform a) with respect to the subprogram; and
iv) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replace any reference to the ancestor class in the output of the data flow program with a reference to the child class returned by the subprogram invocation; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replace each instance of each class with the corresponding structure for that class; and
compile the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.
2. The non-transitory computer accessible memory medium of claim 1 ,
wherein the second data flow program is configured to be compiled by a compiler which does not support classes.
3. The non-transitory memory medium of claim 1 , wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class.
4. The non-transitory computer accessible memory medium of claim 1 ,
wherein the programmable hardware element does not support dynamic memory operations.
5. The non-transitory computer accessible memory medium of claim 1 ,
wherein the first data flow program is not deployable onto the programmable hardware element.
6. The non-transitory computer accessible memory medium of claim 1 , wherein the program instructions are further executable to:
perform type checking to insure that all operations specified in the program can be converted to operations supported by the programmable hardware element; and
generate an error if the type checking determines that any operations specified by the program cannot be converted to operations supported by the programmable hardware element.
7. The non-transitory computer accessible memory medium of claim 6 , wherein said type checking and said generating an error are performed by a compiler.
8. The non-transitory computer accessible memory medium of claim 1 , wherein the program instructions are further executable to:
deploy the hardware configuration program to the programmable hardware element, wherein the hardware configuration program is executable on the programmable hardware element to perform the first function.
9. The non-transitory computer accessible memory medium of claim 1 ,
wherein the first data flow program comprises a graphical data flow program, comprising a plurality of interconnected nodes that visually indicate functionality of the program.
10. The non-transitory computer accessible memory medium of claim 1 , wherein the first data flow program comprises a text-based data flow program.
11. The non-transitory computer accessible memory medium of claim 1 , wherein the program instructions are further executable to:
determine whether every dynamic dispatch subprogram invocation in the first data flow program is resolvable to a static invocation of a class-specific subprogram at compile time; and
generate an error if any dynamic dispatch subprogram invocation in the first data flow program is not resolvable to a static invocation of a class-specific subprogram at compile time.
12. The non-transitory computer accessible memory medium of claim 1 , wherein to automatically convert the first data flow program, the program instructions are executable to:
convert any instance of a parent class constant with a value of a child class to a constant of the child class; and
convert the constant of the child class to a constant of a corresponding data type.
13. The non-transitory computer accessible memory medium of claim 1 ,
wherein the one or more classes comprise at least one descendant class that has ancestor classes;
wherein at least some data types of instances at run-time cannot be statically determined;
wherein for at least one instance of a class that can be statically determined to be of a particular class, said converting comprises converting the at least one instance to a corresponding structure comprising data elements corresponding to data elements of the particular class and any ancestor classes; and
wherein for at least one instance of a class that requires dynamic determination of class type, said converting comprises converting the at least one instance to a generic structure configured to contain all data members of any class and its ancestor classes.
14. The non-transitory computer accessible memory medium of claim 13 , wherein the program instructions are further executable to:
analyze a class hierarchy of the first data flow program to determine a union of data members of the classes in the class hierarchy; and
determine the generic structure based on the determined union, wherein the generic structure is configured to store all data members of any class in the class hierarchy of the first data flow program and its ancestor classes.
15. The non-transitory computer accessible memory medium of claim 14 , wherein the generic structure comprises 1) an enum for denoting a runtime data type of the generic structure, and 2) a set of elements sufficient for representing data for any class in the class hierarchy and its ancestor classes, wherein the enum is configured to be set at runtime to denote the data type of the structure as dynamically determined at runtime.
16. A computer-implemented method, comprising using a computer to perform:
receiving a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, and wherein the first data flow program is executable to perform a first function;
automatically converting the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein said automatically converting the first data flow program to a second data flow program comprises converting the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein said automatically converting the first data flow program comprises:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation, replacing the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if an input class specified for the subprogram is an ancestor class of a corresponding child class specified as input in the invocation:
cloning the subprogram, thereby generating a clone subprogram;
replacing any reference to the ancestor class in inputs of the clone subprogram with a reference to the child class; and
replacing the subprogram invocation with an invocation of the clone subprogram;
iii) performing a) with respect to the subprogram; and
iv) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replacing any reference to the ancestor class in the output of the data flow program with a reference to the child class returned by the subprogram invocation; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replacing each instance of each class with the corresponding structure for that class; and
compiling the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.
17. A system, comprising:
means for receiving a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, and wherein the first data flow program is executable to perform a first function;
means for automatically converting the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein said automatically converting the first data flow program to a second data flow program comprises converting the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein said automatically converting the first data flow program comprises:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation, replacing the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if an input class specified for the subprogram is an ancestor class of a corresponding child class specified as input in the invocation:
cloning the subprogram, thereby generating a clone subprogram;
replacing any reference to the ancestor class in inputs of the clone subprogram with a reference to the child class; and
replacing the subprogram invocation with an invocation of the clone subprogram;
iii) performing a) with respect to the subprogram; and
iv) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replacing any reference to the ancestor class in the output of the data flow program with a reference to the child class returned by the subprogram invocation; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replacing each instance of each class with the corresponding structure for that class; and
means for compiling the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.
18. A non-transitory computer accessible memory medium that stores program instructions executable by a processor to:
receive a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, and wherein the first data flow program is executable to perform a first function;
automatically convert the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein, to automatically convert the first data flow program to a second data flow program, the program instructions are executable to convert the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein to automatically convert the first data flow program, the program instructions are further executable to:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input can be statically determined, replace the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input cannot be statically determined, replace the subprogram invocation with multiple static subprogram invocations comprising a respective static invocation for each class that implements an override of the dynamic dispatch invocation, and a programming structure configured to evaluate the type of the dispatch input and select which of the static invocations to invoke;
iii) if an input class specified for the subprogram can be statically determined and is an ancestor class of a corresponding child class specified as input in the invocation:
clone the subprogram, thereby generating a clone subprogram;
replace any reference to the ancestor class in inputs of the clone subprogram with a reference to the descendent class; and
replace the subprogram invocation with an invocation of the clone subprogram;
iv) if an input class specified for the subprogram cannot be statically determined:
clone the subprogram, thereby generating a clone subprogram;
mark any reference to the input class in the inputs of the clone subprogram as requiring dynamic determination of class type; and
replace the subprogram invocation with an invocation of the clone subprogram;
v) perform a) with respect to the subprogram;
vi) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replace any reference to the ancestor class in the output of the data flow program with a reference to the descendent class returned by the subprogram invocation; and
vii) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is marked as dynamic:
mark any reference to the marked class in the output of the data flow program as requiring dynamic determination of class type; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replace each instance of each class with the corresponding structure for that class, wherein to replace each instance, the program instructions are executable to:
for at least one instance of a class that can be statically determined to be of a particular class, replace the instance with a corresponding class-specific structure comprising data elements corresponding to data elements of the particular class and any ancestor classes; and
for at least one instance of a class that requires dynamic determination of class type, replace the instance with a generic structure configured to contain all data members of any class and its ancestor classes; and
compile the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.
19. The non-transitory computer accessible memory medium of claim 18 ,
wherein the second data flow program is configured to be compiled by a compiler which does not support classes.
20. The memory medium of claim 18 , wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class.
21. The non-transitory computer accessible memory medium of claim 18 ,
wherein the programmable hardware element does not support dynamic memory operations.
22. The non-transitory computer accessible memory medium of claim 18 ,
wherein the first data flow program is not deployable onto the programmable hardware element.
23. The non-transitory computer accessible memory medium of claim 18 , wherein the program instructions are further executable to:
perform type checking to insure that all operations specified in the program can be converted to operations supported by the programmable hardware element; and
generate an error if the type checking determines that any operations specified by the program cannot be converted to operations supported by the programmable hardware element.
24. The non-transitory computer accessible memory medium of claim 23 , wherein said type checking and said generating an error are performed by a compiler.
25. The non-transitory computer accessible memory medium of claim 18 , wherein the program instructions are further executable to:
deploy the hardware configuration program to the programmable hardware element, wherein the hardware configuration program is executable on the programmable hardware element to perform the first function.
26. The non-transitory computer accessible memory medium of claim 18 ,
wherein the first data flow program comprises a graphical data flow program, comprising a plurality of interconnected nodes that visually indicate functionality of the program.
27. The non-transitory computer accessible memory medium of claim 18 ,
wherein the first data flow program comprises a text-based data flow program.
28. The non-transitory computer accessible memory medium of claim 18 , wherein the program instructions are further executable to:
determine whether every dynamic dispatch subprogram invocation in the first data flow program is resolvable to a static invocation of a class-specific subprogram at compile time; and
generate an error if any dynamic dispatch subprogram invocation in the first data flow program is not resolvable to a static invocation of a class-specific subprogram at compile time.
29. The non-transitory computer accessible memory medium of claim 18 , wherein to automatically convert the first data flow program, the program instructions are executable to:
convert any instance of a parent class constant with a value of a child class to a constant of the child class; and
convert the constant of the child class to a constant of a corresponding data type.
30. The non-transitory computer accessible memory medium of claim 18 ,
wherein the one or more classes comprise at least one descendant class that has ancestor classes;
wherein at least some data types of instances at run-time cannot be statically determined;
wherein for at least one instance of a class that can be statically determined to be of a particular class, said converting comprises converting the at least one instance to a corresponding structure comprising data elements corresponding to data elements of the particular class and any ancestor classes; and
wherein for at least one instance of a class that requires dynamic determination of class type, said converting comprises converting the at least one instance to a generic structure configured to contain all data members of any class and its ancestor classes.
31. The non-transitory computer accessible memory medium of claim 30 , wherein the program instructions are further executable to:
analyze a class hierarchy of the first data flow program to determine a union of data members of the classes in the class hierarchy; and
determine the generic structure based on the determined union, wherein the generic structure is configured to store all data members of any class in the class hierarchy of the first data flow program and its ancestor classes.
32. The non-transitory computer accessible memory medium of claim 31 , wherein the generic structure comprises 1) an enum for denoting a runtime data type of the generic structure, and 2) a set of elements sufficient for representing data for any class in the class hierarchy and its ancestor classes, wherein the enum is configured to be set at runtime to denote the data type of the structure as dynamically determined at runtime.
33. A computer-implemented method, comprising using a computer to perform:
receiving a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, wherein the first data flow program is executable to perform a first function; and
automatically converting the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein said automatically convert the first data flow program to a second data flow program comprises convert the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein said automatically converting the first data flow program comprises:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input can be statically determined, replacing the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input cannot be statically determined, replacing the subprogram invocation with multiple static subprogram invocations comprising a respective static invocation for each class that implements an override of the dynamic dispatch invocation, and a programming structure configured to evaluate the type of the dispatch input and select which of the static invocations to invoke;
iii) if an input class specified for the subprogram can be statically determined and is an ancestor class of a corresponding child class specified as input in the invocation:
cloning the subprogram, thereby generating a clone subprogram;
replacing any reference to the ancestor class in inputs of the clone subprogram with a reference to the descendent class; and
replacing the subprogram invocation with an invocation of the clone subprogram;
iv) if an input class specified for the subprogram cannot be statically determined:
cloning the subprogram, thereby generating a clone subprogram;
marking any reference to the input class in the inputs of the clone subprogram as requiring dynamic determination of class type; and
replacing the subprogram invocation with an invocation of the clone subprogram;
v) performing a) with respect to the subprogram;
vi) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replacing any reference to the ancestor class in the output of the data flow program with a reference to the descendent class returned by the subprogram invocation; and
vii) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is marked as dynamic:
marking any reference to the marked class in the output of the data flow program as requiring dynamic determination of class type; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replacing each instance of each class with the corresponding structure for that class, comprising:
for at least one instance of a class that can be statically determined to be of a particular class, replacing the instance with a corresponding class-specific structure comprising data elements corresponding to data elements of the particular class and any ancestor classes; and
for at least one instance of a class that requires dynamic determination of class type, replacing the instance with a generic structure configured to contain all data members of any class and its ancestor classes; and
compiling the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.
34. A system, comprising:
means for receiving a first data flow program, wherein the first data flow program is an object oriented program comprising instances of one or more classes, wherein the first data flow program is executable to perform a first function; and
means for automatically converting the first data flow program to a second data flow program, wherein the second data flow program does not include the instances of the one or more classes, and wherein the second data flow program is executable to perform the first function, wherein the first data flow diagram utilizes a plurality of classes from a class inheritance hierarchy, wherein said automatically convert the first data flow program to a second data flow program comprises convert the instances of the one or more classes to a corresponding one or more structures, wherein each of the one or more structures comprises data elements corresponding to data elements of the corresponding class and any ancestor classes, wherein the first data flow program comprises one or more data flow subprograms, and wherein said automatically converting the first data flow program comprises:
a) for each subprogram invocation in the data flow program:
i) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input can be statically determined, replacing the subprogram invocation with a static invocation of a class-specific implementation of the subprogram;
ii) if the subprogram invocation is a dynamic dispatch invocation and the type of the dispatch input cannot be statically determined, replacing the subprogram invocation with multiple static subprogram invocations comprising a respective static invocation for each class that implements an override of the dynamic dispatch invocation, and a programming structure configured to evaluate the type of the dispatch input and select which of the static invocations to invoke;
iii) if an input class specified for the subprogram can be statically determined and is an ancestor class of a corresponding child class specified as input in the invocation:
cloning the subprogram, thereby generating a clone subprogram;
replacing any reference to the ancestor class in inputs of the clone subprogram with a reference to the descendent class; and
replacing the subprogram invocation with an invocation of the clone subprogram;
iv) if an input class specified for the subprogram cannot be statically determined:
cloning the subprogram, thereby generating a clone subprogram;
marking any reference to the input class in the inputs of the clone subprogram as requiring dynamic determination of class type; and
replacing the subprogram invocation with an invocation of the clone subprogram;
v) performing a) with respect to the subprogram;
vi) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is a descendant class of the class specified as output of the data flow program:
replacing any reference to the ancestor class in the output of the data flow program with a reference to the descendent class returned by the subprogram invocation; and
vii) if an output class returned by the subprogram invocation is returned as an output of the data flow program and the output class returned by the subprogram invocation is marked as dynamic:
marking any reference to the marked class in the output of the data flow program as requiring dynamic determination of class type; and
b) for the first data flow program and each subprogram invoked directly or indirectly by the first data flow program:
replacing each instance of each class with the corresponding structure for that class, comprising:
for at least one instance of a class that can be statically determined to be of a particular class, replacing the instance with a corresponding class-specific structure comprising data elements corresponding to data elements of the particular class and any ancestor classes; and
for at least one instance of a class that requires dynamic determination of class type, replacing the instance with a generic structure configured to contain all data members of any class and its ancestor classes; and
means for compiling the second data flow program into a hardware configuration program, wherein the hardware configuration program is configured to be deployed onto a programmable hardware element.