US5764951A — Methods for automatically pipelining loops

Claim 1

Independent Claim 75 words

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.

Claim 2

Independent Claim 75 words

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.

Claim 3

Dependent Claim 36 words

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.

Claim 4

Dependent Claim 23 words

The method of claim 1, wherein said text description is written in Verilog and said delayed signal assignment uses a Verilog "#" operator.

Claim 5

Dependent Claim 13 words

The method of claim 3, wherein said wait statements use Verilog "@posedge" statements.

Claim 6

Dependent Claim 13 words

The method of claim 3, wherein said wait statements use Verilog "@negedge" statements.

Claim 7

Dependent Claim 30 words

The method of claim 1, 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.

Claim 8

Independent Claim 113 words

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 producer 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.

Claim 9

Independent Claim 113 words

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 producer 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.

Claim 10

Dependent Claim 34 words

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.

Claim 11

Dependent Claim 45 words

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.

Claim 12

Dependent Claim 38 words

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 is consumed by said consumer.

Claim 13

Independent Claim 124 words

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.

Claim 14

Independent Claim 124 words

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.

Claim 15

Dependent Claim 98 words

The method of claim 11, wherein said first access operation is chosen from the 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.

Claim 16

Dependent Claim 98 words

The method of claim 11, wherein said first 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, 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.

Claim 17

Dependent Claim 83 words

The method of claim 11, wherein said first access operation is chosen from the 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.

Claim 18

Dependent Claim 39 words

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.

Claim 19

Dependent Claim 31 words

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.

Claim 20

Dependent Claim 37 words

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.

Claim 21

Independent Claim 112 words

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.

Claim 22

Independent Claim 112 words

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.

Claim 23

Dependent Claim 13 words

A system as described in claim 18, wherein said pipeline implements said loop.

Claim 24

Dependent Claim 39 words

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.

Claim 25

Dependent Claim 113 words

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.

Claim 26

Dependent Claim 113 words

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.

Claim 27

Dependent Claim 49 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-06-08	2001-12-08	2002-06-09	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-06-08	2005-12-08	2006-06-09	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-06-08	2009-12-08	2010-06-09	$7700.00	Window Closed / Lapsed

Methods for automatically pipelining loops

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag