Method and apparatus for automatically generating hardware from algorithms described in MATLAB
Digital circuit is synthesized from algorithm described in the MATLAB programming language. A MATLAB program is compiled into RTL-VHDL, which is synthesizable using system-specific tools to develop ASIC or FPGA configuration. Intermediate transformations and optimizations are performed to obtain highly optimized description in RTL-VHDL or RTL Verilog of given MATLAB program. Optimizations include levelization, scalarization, pipelining, type-shape analysis, memory optimizations, precision analysis and scheduling.
1. A method for compiling a functional description expressed in an interpretive, algorithmic language into target code for selected hardware, the method comprising the steps of:
parsing the functional description expressed in the interpretive, algorithmic language with at least one variable of unknown type or dimension into an abstract syntax tree;
inferring a type and dimension for the variable of unknown type or dimension by analyzing the usage of the variable of unknown type or dimension in the abstract syntax tree;
assigning the inferred type or dimension to the variable of unknown type or dimension;
transforming compound statements in the abstract syntax tree into a series of single statements; and
translating the abstract syntax tree into a register transfer level format.
2. The method for compiling a functional description of claim 1 , further comprising the steps of:
receiving a user directive file including at least one user defined directive selected from the group consisting of constraint directives, assertions, and compiler hints; and
annotating the functional description according to the user directive file.
3. The method for compiling a functional description of claim 1 , further comprising the steps of:
analyzing a value range of the at least one variable of unknown type or dimension; and
assigning a required precision for the at least one variable of unknown type or dimension.
4. The method for compiling a functional description of claim 3 , further comprising the step of:
parsing a real variable of unknown type or dimension into an integer part and a fractional part, wherein said real variable of unknown type or dimension is one of said at least one variable of unknown type or dimension.
5. The method for compiling a functional description of claim 1 , further comprising the steps of:
analyzing array access patterns across loop iterations; and
replacing a statement in a loop including a memory access with multiple statements including the memory access to reduce the number of individual memory accesses.
6. The method for compiling a functional description of claim 1 , further comprising the steps of:
analyzing compound loop structures to identify pipeline opportunities; and
applying the pipeline algorithm to pipeline opportunities to generate nodes corresponding to the loop body, predicate nodes corresponding to loop conditional statements, and a schedule for scheduling pipeline operations.
7. The method for compiling a functional description of claim 1 , wherein the step of transforming compound statements in the abstract syntax tree into a series of single statements comprises the step of:
expanding a matrix operation into at least one loop.
8. The method for compiling a functional description of claim 1 , wherein the step of transforming compound statements in the abstract syntax tree into a series of single statements comprises the step of:
deconstructing a compound statement into at least one simple statement.
9. A system for compiling a functional description expressed in an interpretive, algorithmic language into target code for selected hardware comprising:
a parser for parsing the functional description expressed in the interpretive, algorithmic language with at least one variable of unknown type or dimension into an abstract syntax tree;
a type-shape analyzer, coupled to the parser, for inferring a type and a dimension to the variable of unknown type or dimension by analyzing use of the variable of unknown type or dimension in the abstract syntax tree;
a statement deconstructor, coupled to the type-shape analyzer, for transforming a compound statement in the abstract syntax tree into at least one simple statement; and
a translator, coupled to the statement deconstructor, for translating the abstract syntax tree into a register transfer level format.
10. The system for compiling a functional description of claim 9 , further comprising:
a user directive file, coupled to the parser, for annotating the functional description with at least one user defined directive selected from the group consisting of constraint directives, assertions, and compiler hints.
11. The system for compiling a functional description of claim 9 , further comprising:
a precision analyzer, coupled to the type-shape analyzer, for determining the precision of the at least one variable of unknown type or dimension.
12. The system for compiling a functional description of claim 11 , further comprising:
a real number parser, coupled to the precision analyzer, for parsing a real number into an integer part and a fractional part.
13. The system for compiling a functional description of claim 9 , further comprising:
a memory access optimizer, coupled to the statement deconstructor, for analyzing array access patterns across loop iterations and replacing a statement in a loop including a memory access with multiple statements including the memory access to reduce the number of individual memory accesses.
14. The system for compiling a functional description of claim 9 , further comprising:
a pipeline optimizer, coupled to the statement deconstructor, for analyzing compound loop structures to identify pipeline opportunities and applying the pipeline algorithm to pipeline opportunities to generate nodes corresponding to the loop body, predicate nodes corresponding to loop conditional statements, and a schedule for scheduling pipeline operations.
15. The system for compiling a functional description of claim 9 , wherein the statement deconstructor for transforming a compound statement in the abstract syntax tree into at least one simple statement comprises:
a scalarizer, coupled to the type-shape analyzer, for expanding a matrix operation into at least one loop.
16. One or more computer readable storage devices having computer readable code embodied on said computer readable storage device, said computer readable code for programming one or more computers to perform a method for compiling a functional description expressed in an interpretive, algorithmic language into target code for selected hardware, the method comprising the steps of:
parsing the functional description expressed in the interpretive, algorithmic language with at least one variable of unknown type or dimension into an abstract syntax tree;
inferring a type and dimension for the variable of unknown type or dimension by analyzing the usage of the variable of unknown type or dimension in the abstract syntax tree;
assigning the inferred type and dimension to the variable of unknown type or dimension;
transforming compound statements in the abstract syntax tree into a series of single statements; and
translating the abstract syntax tree into a register transfer level format.
17. The method of claim 16 , further comprising the steps of:
receiving a user directive file including at least one user defined directive selected from the group consisting of constraint directives, assertions, and compiler hints; and
annotating the functional description according to the user directive file.
18. The method of claim 16 , further comprising the steps of:
analyzing a value range of the at least one variable of unknown type or dimension; and
assigning a required precision for the at least one variable of unknown type or dimension.
19. The method of claim 16 , further comprising the steps of:
analyzing array access patterns across loop iterations; and
replacing a statement in a loop with a memory access with multiple statements with the memory access to reduce the number of individual memory accesses.
20. The method of claim 16 , further comprising the steps of:
analyzing compound loop structures to identify pipeline opportunities; and
applying the pipeline algorithm to pipeline opportunities to generate nodes corresponding to the loop body, predicate nodes corresponding to loop conditional statements, and a schedule for scheduling pipeline operations.