Method, system and software for programming reconfigurable hardware

• US 6,732,354 B2
• Filed: 04/23/2002
• Issued: 05/04/2004
• Est. Priority Date: 04/23/2002
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: QuickSilver Controls, Inc.
• Inventors: Ebeling, W. H. Carl, Hogenauer, Eugene B.
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): RUTTEN, JAMES D
• Application Number:
  US10/127,882
• Publication Number:
  US 20030200538A1
• Time in Patent Office: 742 Days
• Field of Search: 717/119, 717/149, 717/150, 717/114-118, 712/18, 712/37, 712/201, 712/25, 716/16, 716/17
• US Class Current: 717/119
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms

Abstract

The method, system and tangible medium storing computer readable software of the present invention, provide for program constructs, such as commands, declarations, variables, and statements, which have been developed to describe computations for an adaptive computing architecture, rather than provide instructions to a sequential microprocessor or DSP architecture. The invention includes program constructs that permit a programmer to define data flow graphs in software, to provide for operations to be executed in parallel, and to reference variable states and historical values in a straightforward manner. The preferred method, system, and software also includes mechanisms for efficiently referencing array variables, and enables the programmer to succinctly describe the direct data flow among matrices, nodes, and other configurations of computational elements and computational units forming the adaptive computing architecture. The preferred software includes dataflow statements, channel objects, stream variables, state variables, unroll statements, iterators, and loop statements.

Claims

1. A method for programming an adaptive computing integrated circuit for a plurality of functions, the adaptive computing integrated circuit having a plurality of heterogeneous computational elements, the plurality of heterogeneous computational elements capable of being configured and reconfigured for performance of the plurality of functions, the method comprising:

(a) using a first program construct of a plurality of program constructs to provide for execution of a computational block in parallel by a subset of heterogeneous computational elements of the plurality of heterogeneous computational elements, wherein the first program construct is capable of being compiled, mapped and scheduled to select, and to provide configuration information to configure, the subset of heterogeneous computational elements for parallel execution of the computational block;

(b) using a second program construct of the plurality of program constructs to provide for automatic indexing of reference to a buffer object;

(c) using a third program construct of the plurality of program constructs for maintaining a previous value of a variable between process invocations;

(d) using a fourth program construct of the plurality of program constructs to provide for iterations having a predetermined number of iterations at a compile time;

(e) using a fifth program construct to provide for data flow among the plurality of heterogeneous computational elements by defining a channel object having an output data stream from a data producing computational block and an input data stream to a data consuming computational block;

(f) using a sixth program construct of the plurality of program constructs to provide array accessing with a predetermined address pattern; and

wherein the plurality of program constructs are capable of being compiled, mapped and scheduled to select one or more heterogeneous computational elements for performance of the plurality of functions, and further to provide configuration information to determine a plurality of configurations and reconfigurations of the plurality of heterogeneous computational elements for performance of the plurality of functions.

2. The method of claim 1, wherein step (a) further comprises:

using a dataflow command for informing a compiler that included commands are for concurrent performance in parallel.

3. The method of claim 1, wherein steps (b) and (e) further comprise:

using the channel object for providing a buffer for storing data; and

using a stream variable for referencing the channel object.

4. The method of claim 3, wherein the channel object is a buffer instantiated with a declared data type and a size, and wherein the stream variable is declared with a buffer of a plurality of data items of a specified data type.

5. The method of claim 1, wherein step (c) further comprises:

using a state variable for maintaining a plurality of previous values of a variable after the variable has been assigned a plurality of current values.

6. The method of claim 1, wherein step (d) further comprises:

using an unroll command for transforming a loop operation into a predetermined plurality of individual executable operations.

7. The method of claim 1, wherein step (f) further comprises:

using an iterator variable for accessing the array in a predetermined, fixed address pattern.

8. The method of claim 1, wherein the sixth program construct is a declaration which includes a plurality of arguments, the plurality of arguments including an iteration level, an initial value of an index, an increment added to the index for a repeated iteration, and an index limit.

9. The method of claim 1, further comprising:

(g) using a seventh program construct of the plurality of program constructs to provide for a fixed number of loop iterations at run time.

10. The method of claim 9, wherein step (g) further comprises:

using a loop command for informing a compiler that a plurality of included commands contain no branching to locations outside of the loop and that a plurality of loop conditions are fixed.

11. The method of claim 1, wherein the first program construct has a semantics comprising:

a first program construct identifier, followed by a plurality of included program statements.

12. The method of claim 11, wherein the first program construct has a syntax comprising:

a dataflow designation;

a commencement designation and a termination designation following the dataflow designation; and

the plurality of included program statements contained within the commencement designation and the termination designation.

13. The method of claim 1, wherein the fourth program construct has a semantics comprising:

a fourth program construct identifier having a plurality of arguments, followed by program statements for expansion into a plurality of individual commands according to the plurality of arguments.

14. A system for programming an adaptive computing integrated circuit for a plurality of functions, the adaptive computing integrated circuit having a plurality of heterogeneous computational elements, the plurality of heterogeneous computational elements capable of being configured and reconfigured for performance of the plurality of functions, the system comprising:

means for using a first program construct of a plurality of program constructs to provide for execution of a computational block in parallel by a subset of heterogeneous computational elements of the plurality of heterogeneous computational elements, wherein the first program construct is capable of being compiled, mapped and scheduled to select, and to provide configuration information to configure, the subset of heterogeneous computational elements for parallel execution of the computational block;

means for using a second program construct of the plurality of program constructs to provide for automatic indexing of reference to a buffer object;

means for using a third program construct of the plurality of program constructs for maintaining a previous value of a variable between process invocations;

means for using a fourth program construct of the plurality of program constructs to provide for iterations having a predetermined number of iterations at a compile time;

means for using a fifth program construct to provide for data flow among the plurality of heterogeneous computational elements by defining a channel object having an output data stream from a data producing computational block and an input data stream to a data consuming computational block;

means for using a sixth program construct of the plurality of program constructs to provide array accessing with a predetermined address pattern; and

wherein the plurality of program constructs are capable of being compiled, mapped and scheduled to select one or more heterogeneous computational elements for performance of the plurality of functions, and further to provide configuration information to determine a plurality of configurations and reconfigurations of the plurality of heterogeneous computational elements for performance of the plurality of functions.

15. The system of claim 14, wherein the means for using the first program construct further comprises:

means for using a dataflow command for informing a compiler that included commands are for concurrent performance in parallel.

16. The system of claim 14, wherein the means for using the second program construct and the means for using a fifth program construct further comprise:

means for using the channel object for providing a buffer for storing data; and

means for using a stream variable for referencing the channel object.

17. The system of claim 16, wherein the channel object is a buffer instantiated with a declared data type and a size, and wherein the stream variable is declared with a buffer of a plurality of data items of a specified data type.

18. The system of claim 14, wherein the means for using the third program construct further comprises:

means for using a state variable for maintaining a plurality of previous values of a variable after the variable has been assigned a plurality of current values.

19. The system of claim 14, wherein the means for using the fourth program construct further comprises:

means for using an unroll command for transforming a loop operation into a predetermined plurality of individual executable operations.

20. The system of claim 14, wherein the means for using the sixth program construct further comprises:

means for using an iterator variable for accessing the array in a predetermined, fixed address pattern.

21. The system of claim 14, wherein the sixth program construct is a declaration which includes a plurality of arguments, the plurality of arguments including an iteration level, an initial value of an index, an increment added to the index for a repeated iteration, and an index limit.

22. The system of claim 14, further comprising:

means for using a seventh program construct to provide for a fixed number of loop iterations at run time.

23. The system of claim 22, wherein the means for using the seventh program construct further comprises:

means for using a loop command for informing a compiler that a plurality of included commands contain no branching to locations outside of the loop and that a plurality of loop conditions are fixed.

24. The system of claim 14, wherein the first program construct has a semantics comprising:

a first program construct identifier, followed by a plurality of included program statements.

25. The system of claim 24, wherein the first program construct has a syntax comprising:

a dataflow designation;

a commencement designation and a termination designation following the dataflow designation; and

the plurality of included program statements contained within the commencement designation and the termination designation.

26. The system of claim 14, wherein the fourth program construct has a semantics comprising:

a fourth program construct identifier having a plurality of arguments, followed by program statements for expansion into a plurality of individual commands according to the plurality of arguments.

30. The tangible medium storing computer readable software of claim 24, wherein the channel object is a buffer instantiated with a declared data type and a size, and wherein the stream variable is declared with a buffer of a plurality of data items of a specified data type.

32. The tangible medium storing computer readable software of claim 24, wherein the fourth program construct further comprises:

an unroll command for transforming a loop operation into a predetermined plurality of individual executable operations.

27. A tangible medium storing computer readable software for programming an adaptive computing integrated circuit for a plurality of functions, the adaptive computing integrated circuit having a plurality of heterogeneous computational elements, the plurality of heterogeneous computational elements capable of being configured and reconfigured for performance of the plurality of functions, the tangible medium storing computer readable software comprising:

a first program construct of a plurality of program constructs to provide for execution of a computational block in parallel by a subset of heterogeneous computational elements of the plurality of heterogeneous computational elements, wherein the first program construct is capable of being compiled, mapped and scheduled to select, and to provide configuration information to configure, the subset of heterogeneous computational elements for parallel execution of the computational block;

a second program construct of the plurality of program constructs to provide for automatic indexing of reference to a buffer object;

a third program construct of the plurality of program constructs for maintaining a previous value of a variable between process invocations;

a fourth program construct of the plurality of program constructs to provide for iterations having a predetermined number of iterations at a compile time;

a fifth program construct to provide for data flow among the plurality of heterogeneous computational elements by using a channel object having an output data stream from a data producing computational block and an input data stream to a data consuming computational block;

a sixth program construct of the plurality of program constructs to provide array accessing with a predetermined address pattern; and

wherein the plurality of program constructs are capable of being compiled, mapped and scheduled to select one or more heterogeneous computational elements for performance of the plurality of functions, and further to provide configuration information to determine a plurality of configurations and reconfigurations of the plurality of heterogeneous computational elements for performance of the plurality of functions.

28. The tangible medium storing computer readable software programming language of claim 27, wherein the first program construct further comprises:

a dataflow command for informing a compiler that included commands are for concurrent performance in parallel.

29. The tangible medium storing computer readable software of claim 27, wherein the second program construct and the fifth program construct further comprise:

a channel object for providing a buffer for storing data; and

a stream variable for referencing the channel object.

31. The tangible medium storing computer readable software of claim 29, wherein the third program construct further comprises:

a state variable for maintaining a plurality of previous values of a variable after the variable has been assigned a plurality of current values.

33. The tangible medium storing computer readable software of claim 27, wherein the sixth program construct further comprises:

an iterator variable for accessing the array in a predetermined, fixed address pattern.

34. The tangible medium storing computer readable software of claim 27, wherein the sixth program construct is a declaration which includes a plurality of arguments, the plurality of arguments including an iteration level, an initial value of an index, an increment added to the index for a repeated iteration, and an index limit.

35. The tangible medium storing computer readable software of claim 27, further comprising:

a seventh program construct of the plurality of program constructs to provide for a fixed number of loop iterations at run time.

36. The tangible medium storing computer readable software of claim 35, wherein the seventh program construct further comprises:

a loop command for informing a compiler that a plurality of included commands contain no branching to locations outside of the loop and that a plurality of loop conditions are fixed.

37. The tangible medium storing computer readable software of claim 27, wherein the first program construct has a semantics comprising:

a first program construct identifier, followed by a plurality of included program statements.

38. The tangible medium storing computer readable software of claim 37, wherein the first program construct has a syntax comprising:

a dataflow designation;

a commencement designation and a termination designation following the dataflow designation; and

the plurality of included program statements contained within the commencement designation and the termination designation.

39. The tangible medium storing computer readable software of claim 27, wherein the fourth program construct has a semantics comprising:

a fourth program construct identifier having a plurality of arguments, followed by program statements for expansion into a plurality of individual commands according to the plurality of arguments.

40. A method for programming an adaptive computing integrated circuit for a plurality of functions, the adaptive computing integrated circuit having a plurality of heterogeneous computational elements, the plurality of heterogeneous computational elements capable of being configured and reconfigured for performance of the plurality of functions,, the method comprising:

using a first program construct of a plurality of program constructs to provide for execution of a computational block in parallel by a subset of heterogeneous computational elements of the plurality of heterogeneous computational elements, wherein the first program construct is capable of being compiled, mapped and scheduled to select, and to provide configuration information to configure, the subset of heterogeneous computational elements for parallel execution of the computational block, the first program construct defined as a dataflow command for informing a compiler that included commands are for concurrent performance in parallel;

using a second program construct of the plurality of program constructs to provide for data flow among the plurality of heterogeneous computational elements by using a channel object having an output data stream from a data producing computational block and an input data stream to a data consuming computational block, the second program construct further providing for automatic indexing of reference to the channel object, the channel object for providing a buffer for storing data, the second program construct further defined as a stream variable for referencing the channel object;

using a third program construct of the plurality of program constructs for maintaining a previous value of a variable between process invocations, the third program construct defined as a state variable for maintaining a plurality of previous values of a variable after the variable has been assigned a plurality of current values;

using a fourth program construct of the plurality of program constructs to provide for iterations having a predetermined number of iterations at a compile time, the fourth program construct defined as an unroll command for transforming a loop operation into a predetermined plurality of individual executable operations;

using a fifth program construct of the plurality of program constructs to provide array accessing, the fifth program construct defined as an iterator variable for accessing the array in a predetermined, fixed address pattern;

using a sixth program construct of the plurality of program constructs to provide for a fixed number of loop iterations at run time, the sixth program construct defined as a loop command for informing a compiler that a plurality of included commands contain no branching to locations outside of the loop and that a plurality of loop conditions are fixed; and

wherein the plurality of program constructs are capable of being compiled, mapped and scheduled to select one or more heterogeneous computational elements for performance of the plurality of functions, and further to provide configuration information to determine a plurality of configurations and reconfigurations of the plurality of heterogeneous computational elements for performance of the plurality of functions.

41. The method of claim 40, wherein the channel object is a buffer instantiated with a declared data type and a size, and wherein the stream variable is declared with a buffer of a plurality of data items of a specified data type.

42. The method of claim 40, wherein the fifth program construct is a declaration which includes a plurality of arguments, the plurality of arguments including an iteration level, an initial value of an index, an increment added to the index for a repeated iteration, and an index limit.

43. The method of claim 40, wherein the first program construct has a semantics comprising:

a first program construct identifier;

a commencement designation and a termination designation following the first program construct identifier;

and a plurality of included program statements contained within the commencement designation and the termination designation.

44. The method of claim 40, wherein the fourth program construct has a semantics comprising:

a fourth program construct identifier having a plurality of arguments, followed by program statements for expansion into a plurality of individual commands according to the plurality of arguments.

45. A tangible medium storing computer readable software for programming an adaptive computing integrated circuit for a plurality of functions, the adaptive computing integrated circuit having a plurality of heterogeneous computational elements, the plurality of heterogeneous computational elements capable of being configured and reconfigured for performance of the plurality of functions,, the tangible medium storing computer readable software comprising:

a first program construct of a plurality of program constructs to provide for execution of a computational block in parallel by a subset of heterogeneous computational elements of the plurality of heterogeneous computational elements, wherein the first program construct is capable of being compiled, mapped and scheduled to select, and to provide configuration information to configure, the subset of heterogeneous computational elements for parallel execution of the computational block, the first program construct defined as a dataflow command for informing a compiler that included commands are for concurrent performance in parallel;

a second program construct of the plurality of program constructs to provide for data flow among the plurality of heterogeneous computational elements by using a channel object having an output data stream from a data producing computational block and an input data stream to a data consuming computational block, the second program construct further providing for automatic indexing of reference to the channel object, the channel object for providing a buffer for storing data, the second program construct further defined as a stream variable for referencing the channel object, wherein the channel object is a buffer instantiated with a declared data type and a size, and wherein the stream variable is declared with a buffer of a plurality of data items of a specified data type;

a third program construct of the plurality of program constructs for maintaining a previous value of a variable between process invocations, the third program construct defined as a state variable for maintaining a plurality of previous values of a variable after the variable has been assigned a plurality of current values;

a fourth program construct of the plurality of program constructs to provide for iterations having a predetermined number of iterations at a compile time, the fourth program construct defined as an unroll command for transforming a loop operation into a predetermined plurality of individual executable operations;

a fifth program construct of the plurality of program constructs to provide array accessing, the fifth program construct defined as an iterator variable for accessing the array in a predetermined, fixed address pattern;

a sixth program construct of the plurality of program constructs to provide for a fixed number of loop iterations at run time, the sixth program construct defined as a loop command for informing a compiler that a plurality of included commands contain no branching to locations outside of the loop and that a plurality of loop conditions are fixed; and

wherein the plurality of program constructs are capable of being compiled, mapped and scheduled to select one or more heterogeneous computational elements for performance of the plurality of functions, and further to provide configuration information to determine a plurality of configurations and reconfigurations of the plurality of heterogeneous computational elements for performance of the plurality of functions.

46. The tangible medium storing computer readable software of claim 45, wherein the fifth program construct is a declaration which includes a plurality of arguments, the plurality of arguments including an iteration level, an initial value of an index, an increment added to the index for a repeated iteration, and an index limit.

47. The tangible medium storing computer readable software of claim 45, wherein the first program construct has a semantics comprising:

a first program construct identifier;

a commencement designation and a termination designation following the first program construct identifier; and

a plurality of included program statements contained within the commencement designation and the termination designation;

and wherein the fourth program construct has a semantics comprising;

a fourth program construct identifier having a plurality of arguments, followed by program statements for expansion into a plurality of individual commands according to the plurality of arguments.