Methods for automatically pipelining loops

Abstract

A method and an apparatus for creating a representation of a circuit with a pipelined loop from an HDL source code description. It infers a circuit including a pipelined loop which has cycle level simulation behavior matching that of the source HDL. Loop carry dependencies and memory and signal I/O accesses within the loop are scheduled correctly.

1. A method performed by a data processing system having a memory, comprising the steps of:
 parsing a text description of a circuit, said text description stored in the memory, said text description including a loop with a delayed signal assignment having a delay value;  
 translating said text description into a digital circuit representation in said memory, said digital circuit representation including a pipeline; and  
 setting a latency of said pipeline equal to said delay value.  
 
     
     
       2. The method of  claim 1 , wherein said loop further includes N wait statements, where N is greater than zero, said method further comprising the step of setting an initiation interval of said pipeline equal to N. 
     
     
       3. The method of  claim 1 , wherein said text description is written in Verilog and said delayed signal assignment uses a Verilog “#” operator. 
     
     
       4. The method of claim  3    2 , wherein said wait statements use  transition on Verilog “@posedge” statements. 
     
     
       5. The method of claim  3    2 , wherein said wait statements use  transition on Verilog “@negedge” statements. 
     
     
       6. The method of claim of claim  1    2 , wherein said text description is written in VHDL, said delayed signal assignment uses a VHDL “after” clause, and said wait statements use VHDL “wait” statements. 
     
     
       7. A method, performed by a data processing system having, a memory, of building a digital circuit representation including a pipeline in the memory from a textual description of a loop, comprising the steps of:
 identifying a loop carry dependency in said loop;  
 identifying a producer operation of said loop carry dependency;  
 identifying a consumer operation of said loop carry dependency;  
 determining a number, n, of cycles within which said produce operation must be scheduled after said consumer operation;  
 instantiating a placeholder node in said memory;  
 node-locking said placeholder node so that it must be scheduled n cycles after said consumer operation; and  
 constraining said producer operation to be scheduled before said placeholder node.  
 
     
     
       8. The method of  claim 7 , wherein the step of node-locking said placeholder node further comprises the step of creating a template structure in said memory which includes said placeholder node and said consumer operation. 
     
     
       9. The method of  claim 8 ,
 wherein said producer operation is included in a second template structure in said memory, and  
 wherein the step of constraining said producer operation further comprises the step of constraining said second template structure to be scheduled before said template structure.  
 
     
     
       10. The method of  claim 7 , wherein n is equal to an initiation interval of said pipeline multiplied by a number of iterations of said loop which execute before data produced by said producer operation is consumed by said consumer operation. 
     
     
       11. A method, performed by a data processing system having a memory, of building a digital circuit representation in said memory, said digital circuit representation including a pipeline derived from a textual description of a loop, said method comprising the steps of:
 identifying an access dependency of said loop;  
 identifying a first access operation of said access dependency;  
 identifying a second access operation of said access dependency;  
 determining a number, n, of cycles within which said second access operation must be scheduled after said first access operation;  
 instantiating a placeholder node in said memory;  
 node-locking said placeholder node so that it must be scheduled n cycles after said first access operation; and  
 constraining a scheduling order of said second access operation and said placeholder node.  
 
     
     
       12. The method of  claim 11 ,
 wherein said first access operation is chosen from the  a group of access operations including a memory read, a memory write, a signal write and a port write,  
 said second access operation is chosen from the group of access operations including a memory read, a memory write, a signal read, a signal write, a port read and a port write, and  
 the step of constraining said scheduling order of said second access operation and said placeholder node further includes the step of forcing said second access operation to be scheduled before said placeholder node.  
 
     
     
       13. The method of  claim 11 ,
 wherein said first access operation is chosen from the  a group of access operations including a memory read, a memory write, a signal read, a signal write, a port read and a port write,  
 said second access operation is chosen from the group of access operations including a memory read, a memory write, a signal write and a port write, and  
 the step of constraining said scheduling order of said second access operation and said placeholder node further includes the step of forcing said second access operation to be scheduled before said placeholder node.  
 
     
     
       14. The method of  claim 11 ,
 wherein said first access operation is chosen from the  a group of access operations including a signal read and a port read,  
 said second access operation is chosen from the group of access operations including a signal read and a port read, and  
 the step of constraining said scheduling order of said second access operation and said placeholder node further includes the step of forcing said second access operation to be scheduled simultaneous with, or before said placeholder node.  
 
     
     
       15. The method of  claim 11 , wherein the step of constraining said scheduling order of said second access operation and said placeholder node further includes the step of forcing said second access operation to be scheduled before said placeholder node. 
     
     
       16. The method of  claim 11 , wherein the step of node-locking said placeholder node further includes the step of creating a template which includes said placeholder node and said first access operation. 
     
     
       17. The method of  claim 11 , wherein n is equal to an initiation interval of said pipeline multiplied by a number of iterations of said loop which execute between said first access operation and said second access operation. 
     
     
       18. A system for building, in a memory, a digital circuit representation which implements the behavior of a text description in said memory, said system having a processor coupled to a memory unit wherein said processor is programmed to perform logic processing, said system comprising:
 parsing logic for parsing said text description into a parsed text description, said text description including a loop with a delayed signal assignment having a delay value;  
 translating logic for translating said parsed text description into said digital circuit representation, said digital circuit including a pipeline; and  
 latency setting logic for setting a latency value of said pipeline to be said delay value of said delayed signal assignment.  
 
     
     
       19. A system as described in  claim 18 , wherein said pipeline implements said loop. 
     
     
       20. A system as described in  claim 19 , wherein said loop further includes a number, n, of wait statements, said system further comprising initiation interval setting logic for setting an initiation interval of said pipeline to be equal to n. 
     
     
       21. A computer program product comprising:
 a computer usable medium having computer readable code embodied therein for building a digital circuit representation from a text description of a digital circuit, the computer program product comprising:  
 computer readable program code devices configured to cause a computer to effect parsing said text description, said text description including a loop with a delayed signal assignment having a delay value;  
 computer readable program code devices configured to cause a computer to effect translating said text description into said digital circuit representation including a pipeline; and  
 computer readable program code devices configured to cause a computer to effect setting a latency of said pipeline equal to said delay value.  
 
     
     
       22. The computer program product of  claim 1  wherein said loop further includes N wait statements, where N is greater than zero, said computer program product further comprising computer readable program code devices configured to cause a computer to effect setting an initiation interval of said pipeline equal to N. 
     
     
       23. The method of  claim 1 , wherein said loop further includes N clock statements, where N is greater than zero, said method further comprising the step of setting an initiation interval of said pipeline equal to N. 
     
     
       24. A system as described in  claim 18 , wherein said loop further includes a number, n, of clock statements, said system further comprising initiation interval setting logic for setting an initiation interval of said pipeline to be equal to n. 
     
     
       25. The computer program product of  claim 21  wherein said loop further includes N clock statements, where N is greater than zero, said computer program product further comprising computer readable program code devices configured to cause a computer to effect setting an initiation interval of said pipeline equal to N. 
     
     
       26. A method performed by a data processing system having a memory, comprising the steps of:
   parsing a text description of a circuit, said text description stored in the memory, said text description including a loop with N wait statements, where N is greater than zero;        translating said text description into a digital circuit representation in said memory, said digital circuit representation including a pipeline; and        setting an initiation interval of said pipeline equal to N.     
     
     
       27. The method of  claim 26 , wherein the wait statements are VHDL wait statements. 
     
     
       28. The method of  claim 26 , wherein the wait statements transition on Verilog HDL @posedge statements. 
     
     
       29. The method of  claim 26 , wherein the wait statements transition on Verilog HDL @negedge statements. 
     
     
       30. A system for building, in a memory, a digital circuit representation which implements the behavior of a text description in said memory, said system having a processor coupled to a memory unit wherein said processor is programmed to perform logic processing, said system comprising:
   parsing logic for parsing said text description into a parsed text description, said text description including a loop with N wait statements, where N is greater than zero;        translating logic for translating said parsed text description into said digital circuit representation, said digital circuit including a pipeline; and        initiation interval setting logic for setting an initiation interval of said pipeline equal to N.     
     
     
       31. The system of  claim 30 , wherein the wait statements are VHDL wait statements. 
     
     
       32. The system of  claim 30 , wherein the wait statements transition on Verilog HDL @posedge statements. 
     
     
       33. The system of  claim 30 , wherein the wait statements transition on Verilog HDL @negedge statements. 
     
     
       34. A computer program product comprising a computer usable medium having computer readable code embodied therein for building a digital circuit representation from a text description of a digital circuit, the computer program product comprising:
   computer readable program code devices configured to cause a computer to effect parsing said text description, said text description including a loop with N wait statements, where N is greater than zero;        computer readable program code devices configured to cause a computer to effect translating said text description into said digital circuit representation including a pipeline; and        computer readable program code devices configured to cause a computer to effect setting an initiation interval of said pipeline equal to N.     
     
     
       35. The method of  claim 34 , wherein the wait statements are VHDL wait statements. 
     
     
       36. The method of  claim 34 , wherein the wait statements transition on Verilog HDL @posedge statements. 
     
     
       37. The method of  claim 34 , wherein the wait statements transition on Verilog HDL @negedge statements. 
     
     
       38. A method performed by a data processing system having a memory, comprising the steps of:
   parsing a text description of a circuit, said text description stored in the memory, said text description including a loop with N clock statements, where N is greater than zero;        translating said text description into a digital circuit representation in said memory, said digital circuit representation including a pipeline; and        setting an initiation interval of said pipeline equal to N.     
     
     
       39. A system for building, in a memory, a digital circuit representation which implements the behavior of a text description in said memory, said system having a processor coupled to a memory unit wherein said processor is programmed to perform logic processing, said system comprising:
   parsing logic for parsing said text description into a parsed text description, said text description including a loop with N clock statements, where N is greater than zero;        translating logic for translating said parsed text description into said digital circuit representation, said digital circuit including a pipeline; and        initiation interval setting logic for setting an initiation interval of said pipeline equal to N.     
     
     
       40. A computer program product comprising a computer usable medium having computer readable code embodied therein for building a digital circuit representation from a text description of a digital circuit, the computer program product comprising:
   computer readable program code devices configured to cause a computer to effect parsing said text description, said text description including a loop with N clock statements, where N is greater than zero;        computer readable program code devices configured to cause a computer to effect translating said text description into said digital circuit representation including a pipeline; and        computer readable program code devices configured to cause a computer to effect setting an initiation interval of said pipeline equal to N.