Method and apparatus for modeling dataflow systems and realization to hardware

• US 20020178285A1
• Filed: 05/23/2002
• Published: 11/28/2002
• Est. Priority Date: 05/25/2001
• Status: Active Grant

• Current Assignee: Annapolis Micro Systems, Inc.
• Original Assignee: Annapolis Micro Systems, Inc.
• Inventors: Marshall, Lawrence M. Jr., Smith, Teresa G., Sullivan, James J., Hawver, Dennis M., Gray, Michael N., Hudson, Rhett D., Donaldson, Robert L., Klewin, Michael P., Peterson, James B.
• Granted Patent: US 7,509,647 B2
• Time in Patent Office: Days
• US Class Current: 709/237
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation

Abstract

In hardware, performing computations on a stream typically requires handshaking signals to provide flow control. Many different handshaking protocols are available, and they are typically implemented in an ad hoc manner suited to the current design. An approach according to the invention uses a subset of the possible flow-control protocols in an effort to achieve a maximum amount of flexibility and reusability, while requiring only a moderate level of overhead when compared to manually-designed systems.

Claims

1. A method of modeling a dataflow architecture comprising the steps of:

storing in a memory indicia representative of a dataflow architecture having components responsive to intercommunication protocols; and

processing conversions among the intercommunication protocols to determine control structures required to implement said dataflow architecture.

2. A method as recited in claim 1, wherein the indicia stored in memory and the control structures are translated into a description of an implementation of said dataflow architecture.

3. A method as recited in claim 2, where the description of an implementation is the EDIF netlisting language.

4. A method as recited in claim 2, where the description of an implementation is structural VHDL.

5. A method as recited in claim 2, where the description of an implementation is structural Verilog.

6. A method as recited in claim 2, where the description of an implementation is further translated into a physical implementation of the dataflow architecture.

7. A method as recited in claim 6, wherein the physical implementation is configuration data for a FPGA.

8. A method as recited in claim 6, wherein the physical implementation is a layout for an Application Specific Integrated Circuit (ASIC).

9. A method as recited in claim 6, wherein the physical implementation is object code for a general-purpose processor.

10. An apparatus resulting from the method recited in claim 2.

11. A method as recited in claim 2, wherein one of the intercommunications protocols is a VDL protocol comprising:

a data signal and a valid signal, wherein the valid signal indicates that the data on the data signal is valid; and

a pull signal which propagates in a direction opposite to a direction of propagation of the data signal and the valid signal and which, wherein the pull signal indicates that data on the data signal has been consumed, and

wherein the pull signal may reference values of the data signal and the valid signal separated from it by a fixed amount of time, said time being a skew.

12. A method as recited in claim 2, wherein one of intercommunications protocols, is a VDR protocol comprising:

a data signal and a valid signal, wherein the valid signal indicates that data on the data signal is valid

a ready signal which propagates in a direction opposite to a direction of propagation of the data and valid signals and which indicates that data on the data signal which has been indicated as valid by the valid signal will be consumed, and

where the ready signal may reference values of the data and valid signals separated from it by some fixed amount of time, said time being a skew

13. A method as recited in claim 2, wherein one of the intercommunications protocols is a PDR protocol comprising:

a data signal and a push signal, wherein the push signal indicates that data on the “

data”

signal must be consumed

a ready signal which propagates in a direction opposite to a direction of propagation of the data signal and the push signal and which indicates that the data on the data signal may be signaled as pushed data by the push signal, and

wherein the ready signal may reference values of the data and push signals separated from it by some fixed amount of time, said time being a skew.

14. A method as recited in claim 2, wherein one of the intercommunications protocols is a DX protocol comprising:

a data signal;

an associated domain for which values on any two data signals associated with the same domain are separated from one another by a fixed amount of time, said time being a skew

15. A method as recited in claim 2, wherein the intercommunications protocols comprise at least one of a VDL protocol, a VDR protocol, a PDR protocol a DX protocol;

and a PDX protocol.

16. A method as recited in claim 15, wherein one of the conversions among intercommunications protocols is a PullCast conversion, comprising a conversion from a dataflow stream using the VDL protocol with a skew of zero and producing a dataflow stream using the VDR protocol with a skew of zero

17. A method as recited in claim 15, wherein one of the conversions among intercommunications protocols is a PushCast conversion comprising a conversion from a dataflow stream using the VDR protocol with a particular skew and producing a dataflow stream using the PDR protocol with a same skew.

18. A method as recited in claim 15, wherein one of the conversions among intercommunications protocols is a ClearSkew conversion comprising a conversion from a dataflow stream using a first protocol with a particular skew and producing a dataflow stream using a different protocol with zero skew.

19. A method as recited in claim 15, wherein one of the conversions among intercommunications protocols is a Synchronize conversion comprising a conversion from a dataflow stream using the VDL protocol with a skew of zero and producing a dataflow stream using the DX protocol with zero skew.

20. A method as recited in claim 15, wherein one of the conversions among intercommunications protocols is a GetPush conversion comprising a conversion from a dataflow stream using the DX protocol with a particular skew and producing a dataflow stream using the PDR protocol with the same skew as the particular skew.

21. A method as recited in claim 15, wherein one of the conversions among protocols is an AddSkew conversion comprising a conversion from a dataflow stream using a particular protocol with a particular skew and producing a dataflow stream with the same protocol and a larger skew than the particular skew.

22. A method as recited in claim 15 comprising at least one of a Clearskew conversion, a PullCast conversion, a PushCast conversion, a Synchronize conversion, a GetPush conversion, an AddSkew conversion,.

23. A method as recited in claim 16, wherein the PullCast conversion is implemented by propagating the data and valid signals of a VDL protocol stream as the respective data and valid signals of the VDR protocol and the pull signal of the VDL protocol as the result of a logical AND operation of the valid signal of the VDL protocol and the ready signal of the VDR protocol.

24. A method as recited in claim 17, wherein the PushCast conversion is implemented by propagating the data signal of a VDR protocol stream as the data signal of the PDR protocol, the push signal of the PDR protocol as the result of a logical AND operation of the valid signal of the VDR protocol and the ready signal of the PDR protocol delayed by the skew, and the ready signal of the PDR protocol is propagated as the ready signal of the VDR protocol.

25. A method as recited in claim 18, wherein the implementation of the ClearSkew comprises:

pushing a value of a data signal of a PDR protocol into a first-in-first-out FIFO data storage mechanism, whenever a push signal of the PDR protocol is asserted;

basing a ready signal of the PDR protocol on the number of data values stored in the FIFO, such that if a maximum number of values that the FIFO can store less a number of currently stored values is less than a skew of the PDR protocol, the ready signal of the PDR protocol is asserted.

pulling a value of the data signal of a VDL protocol from the FIFO, whenever the pull of the VDL protocol signal is asserted, and

asserting the valid signal of the VDL protocol whenever there are data values stored in the FIFO.

26. A method as recited in claim 19, wherein the implementation of the Synchronize conversion comprises:

propagating a data signal of the VDL protocol to a data signal of the DX protocol,

feeding a valid signal of the VDL protocol to a global, many-input, logical AND operation associated with a domain of the DX protocol; and

driving a pull signal of the VDL protocol with an output of the global, many-input logical AND operation.

27. A method as recited in claim 20, wherein the implementation of the GetPush conversion comprises:

propagating a “

data”

signal of the DX protocol to a “

data”

signal of the PDR protocol;

feeding the “

ready”

signal of the PDR protocol to a global, many-input, logical AND operation associated with a domain of the DX protocol; and

driving a “

push”

signal of the PDR protocol with an output of the global, many-input logical AND operation, delayed by a skew of the PDR protocol.

28. A method as recited in claim 21, wherein the implementation of the AddSkew conversion comprises:

propagating an original data signal of the protocol to a final data signal through a component with fixed delay;

propagating an original push or valid signal of the protocol, if one exists, to a final push or valid signal through a component with fixed delay equivalent to that used to propagate the “

data”

signal;

propagating an original pull or ready signal of the protocol, if one exists, to a final pull or ready signal through a component with fixed delay;

the difference in skew between the original and final signals being equivalent to a sum of the delay for the data signal and the delay for the ready or pull signal.

29. A method as recited in claim 22 wherein:

said Pull Cart conversion propagates the data and valid signals of a VDL protocol stream as the respective data and valid signals of the VDR protocol and the pull signal of the VDL protocol as the result of a logical AND operation of the valid signal of the VDL protocol and the ready signal of the VDR protocol;

said Push Cart conversion propagates the data signal of a VDR protocol stream as the data signal of the PDR protocol, the push signal of the PDR protocol as the result of a logical AND operation of the valid signal of the VDR protocol and the ready signal of the PDR protocol delayed by the skew, and the ready signal of the PDR protocol is propagated as the ready signal of the VDR protocol;

said Clear Skew conversion comprises pushing a value of a data signal of a PDR protocol into a first-in-first-out FIFO data storage mechanism, whenever a push signal of the PDR protocol is asserted;

basing a ready signal of the PDR protocol on the number of data values stored in the FIFO, such that if a maximum number of values that the FIFO can store less a number of currently stored values is less than a skew of the PDR protocol, the ready signal of the PDR protocol is asserted.

pulling a value of the data signal of a VDL protocol from the FIFO, whenever the pull of the VDL protocol signal is asserted, and

asserting the valid signal of the VDL protocol whenever there are data values stored in the FIFO;

said Synchronize conversion comprises propagating a data signal of the VDL protocol to a data signal of the DX protocol,

feeding a valid signal of the VDL protocol to a global, many-input, logical AND operation associated with a domain of the DX protocol; and

driving a pull signal of the VDL protocol with an output of the global, many-input logical AND operation;

said GetPush conversion comprises propagating a “

data”

signal of the DX protocol to a “

data”

signal of the PDR protocol;

feeding the “

ready”

signal of the PDR protocol to a global, many-input, logical AND operation associated with a domain of the DX protocol; and

driving a “

push”

signal of the PDR protocol with an output of the global, many-input logical AND operation, delayed by a skew of the PDR protocol; and

said Skew conversion comprises propagating an original data signal of the protocol to a final data signal through a component with fixed delay;

propagating an original push or valid signal of the protocol, if one exists, to a final push or valid signal through a component with fixed delay equivalent to that used to propagate the “

data”

signal;

propagating an original pull or ready signal of the protocol, if one exists, to a final pull or ready signal through a component with fixed delay;

the difference in skew between the original and final signals being equivalent to a sum of the delay for the data signal and the delay for the ready or pull signal.

30. A method as recited in claim 2, wherein:

component defines a transformation of values present at the input ports of the component to values at output ports of the component;

characteristic properties associated with instances of the component influence behavior of the dataflow architecture;

an algorithm for creating a description of an implementation of a said component is based on the properties of that component, the properties of the ports associated with that component, and interconnection of the ports of that component with the ports of another component.

31. A method as recited in claim 30, wherein:

a port associated with a component represents potential interconnections with another component;

characteristic properties associated with port instances influence behavior of the dataflow architecture;

an algorithm for creating a description of an implementation of a said port is based on properties of that port, and interconnection of that port with another port;

32. A method as recited in claim 31, wherein:

interconnections between the ports represent an ability of the ports to communicate using a common interconnection protocol;

characteristic properties of interconnection instances influence behavior of the dataflow architecture;

an algorithm for creating a complete description of an implementation of a said interconnection is based on properties of the interconnection, and the ports that the interconnection interconnects.

33. A method as recited in claim 31, wherein one of the characteristic properties associated with a port determines the interconnection protocol that must be used by other ports to interact with said port.

34. A method as recited in claim 33, where the description of the implementation of the interconnection protocol associated with the port of a component comprises a data portion and a control portion.

35. A method as recited in claim 34, where resources allocated to the data portion and accuracy of the data portion in a description of a port in a description of the implementation are determined by resources allocated to the data portion and accuracy of the data portion of the ports to which the particular port is connected.

36. A method as recited in claim 35, where sizing of the data portion and the accuracy of the data portion of an intercommunication protocol are dynamically recomputed in response to changes in the resources allocated to the data portion and the accuracy of the data portion of the ports to which the particular port is connected.

37. A method as recited in claim 36, where the intercommunication protocol used to implement the control portion of a port of a particular component is determined by the intercommunication protocols associated with the ports to which said port is connected.

38. A method as recited in claim 37, where the determination of the intercommunication protocol used to implement the control portion of a port of a particular component can be dynamically recomputed in response to changes in the intercommunication protocol used to implement the control portion of the ports to which the particular port is connected.

39. A method as recited in claim 38, where a particular component changes the properties of its ports based on properties of the ports of other components with which the ports of the particular component are associated via interconnections.

40. A method as recited in claim 39, where a particular component may dynamically recomputes the properties of its ports in response to changes in properties of ports of other components with which the ports of the particular component are associated via interconnections.

41. A method as recited in claim 40, where the determination of the resources allocated to the data portion and the accuracy of the data portion of an intercommunication protocol can be made fixed.

42. A method as recited in claim 41, where the intercommunication protocol used to implement the control portion of a port of the particular component can be made fixed.

43. A method as recited in claim 42, where one of the properties of a port determines whether the port must be connected to another port or whether its connection to another port is optional.

44. A method as recited in claim 43, where the description of the implementation of the particular component is determined based on a presence or absence of connections to the optional ports of the component.

45. A method as recited in claim 44, where a component can provide an estimate of resources required to build the component using an algorithm computationally simpler than an algorithm required to build the component.

46. A method as recited in claim 45, where the description of the implementation of an interconnection is based on the ports associated with the interconnection, the properties of said ports, and the properties of the interconnection itself.

47. A method as recited in claim 46, where an abstract representation being translated into indicia comprises a formal language describing instances of the components and the interconnections between the ports of the components.

48. A method as recited in claim 47, where the abstract representation being translated into indicia comprises a graphical depiction of the components and the interconnections between the ports of the components.

50. A method as recited in claim 49, wherein simulating a data flow operation further comprises simulating at least one data flow protocol from a plurality of protocols.

51. A method as recited in claim 50, comprising simulating a VDR protocol by executing with said processor programmed steps corresponding to indicia stored in said memory, wherein said data signal is valid only during a time period when said valid signal and a ready signal are asserted simultaneously.

52. A method as recited in claim 51, wherein simulating said VDR protocol comprises executing steps corresponding to indicia stored in said memory wherein transmission of data from one data flow component to another dataflow component cannot be undone.

53. A method as recited in claim 52, wherein simulating said VDR protocol comprises executing programmed steps corresponding to indicia for a program rule stored in said memory wherein said data signal becomes valid at a later times than said valid signal.

54. A method as recited in claim 53, wherein a said later time corresponds to skew represented by a number of clock cycles.

55. A method as recited in claim 54, wherein said skew is a number of said clock cycles of delay between a time when asserting a ready signal of a selected dataflow component and a time when valid data is present on a data signal of said selected dataflow component.

56. A method as recited in claim 54, further comprising simulating a pipelined computational unit by applying skew to synchronize said valid signal with said data signal.

57. A method as recited in claim 56, wherein said valid signal is delayed in time by a same delay as the delay experienced by said data signal.

58. A method as recited in claim 57, wherein said a simulation of a computation unit introduces said delay experienced by said data signal.

59. A method as recited in claim 58, wherein a delay of said valid signal is introduced by inserting a delay of a fixed number of clock cycles between an input valid signal and an output valid signal of said dataflow component.

60. A method as recited in claim 50, comprising simulating a PDR protocol by executing within said processor programmed steps corresponding to indicia stored in said memory, wherein said dataflow component has a push signal that may be asserted only when said ready signal is asserted.

61. A method as recited in claim 60, wherein said push signal and said ready signal are not initially asserted in a same clock cycle.

62. A method as recited in claim 61, wherein data appearing on said data signal of said dataflow component when said push signal and said ready signal are asserted must be consumed by a second dataflow component.

63. A method as recited in claim 62, wherein said ready signal is subjected to a delay in time of a number of clock cycles forming a skewed ready signal and a logical AND of said skewed ready signal and said valid signal forms said push signal.

64. A method as recited in claim 63 wherein said dataflow component is simulated to have a input valid signal, an input data signal, an output data signal, a common input ready signal and output ready signal and an output push signal, said push signal being a logical AND of said skewed ready signal and said input valid signal.

65. A method as recited in claim 50, comprising simulating a PDL protocol by executing in a processor programmed steps corresponding to indicia stored in said memory, wherein said dataflow component has a pull signal asserted when data incoming to said dataflow component is guaranteed to be consummable by said dataflow component

66. A method as recited in claim 65, wherein said ready signal of said dataflow component is subjected to a delay in time of a number of clock cycles forming a skewed ready signal and a logical AND of said skewed ready signal and said valid signal forms said pull signal.

67. A method as recited in claim 66, wherein said dataflow component is simulated to have a common input valid signal and output valid signal, an input data signal, an output data signal, an input ready signal and an output pull signal, said pull signal being a logical AND of said skewed ready signal and said common input valid signal and output valid signal.

68. A method as recited in claim 49, comprising simulating a VDL protocol by executing a processor programmed steps corresponding to indicia stored in said memory, wherein said dataflow component has a pull signal amended only when a valid signal of said dataflow component is asserted.

69. A method as recited in claim 68, wherein a bus using said VDL protocol does not have a skew represented by a number of clock cycles greater than zero.

70. A method as recited in claim 49, wherein said dataflow components are connected via a DFC bus.

71. A method as recited in claim 70, wherein skew accumulates on said bus, and said skew accumulated in said bus is cleared by setting a reserve of memory space in a first-in-first-out memory and asserting an almost full signal when memory space available in said first-in-first-out memory is equal to or less than said reserve.

72. A method as recited in claim 71, wherein said reserve is set to the skew of incoming PDR signals.

73. A method as recited in claim 72, wherein said first-in-first-out memory supplies data to a part of a dataflow component connected at a location downstream of said first-in-first-out memory.

74. A method as recited in claim 49, comprising simulating a PDL protocol by executing in a processor programmed with steps corresponding to indicia stored in a memory, wherein said dataflow component has a pull signal and a push signal that cannot both be asserted or de-asserted simultaneously.

75. A method as recited in claim 49, comprising stimulating, by executing in a processor programmed with steps corresponding to indicia stored in a memory, a fanout operator for routing data from an output port of a dataflow component to input ports of a plurality of dataflow components, said fanout operator asserting a valid signal to a valid input port of said plurality of dataflow components until all of said plurality of dataflow components consumes said data.

76. A method as recited in claim 49 comprising simulating, by executing in a processor programmed with steps corresponding to indicia stored in a memory, a synchronize operator, wherein a plurality of valid inputs to particular dataflow components having a plurality of dataflow inputs are combined to allow components push and pull outputs to be produced by said plurality of dataflow components only during times when all of said plurality of valid signals are asserted.

77. A method as recited in claim 76 wherein said push and pull outputs are produced depending upon assertion of a plurality of ready signals.

78. A method as recited in claim 49 comprising simulating, by executing in a processor programmed with steps corresponding to indicia stored in a memory, a DX protocol, wherein push signals of a multiple input operation are identical and data consumption at outputs of said operator is synchronized.

79. A method as recited in claim 78 wherein a DX bus belongs to a push domain directly related to an operation generating original DX signals.

80. A method as recited in claim 79 wherein a ready output of a dataflow component in said DX protocol is a logical AND of all ready inputs of said components.

49. A method of modeling a processing system comprising the steps of:

storing in a memory indicia representative of a data flow component responsive to at least a data signal and a valid signal;

in a processor simulating a data flow operation from characteristics of said data flow component.