Method of using clock cycle-time in determining loop schedules during circuit design

An apparatus for determining validity of a proposed loop iteration schedule comprising:

• means for assigning latencies to dependence graph operations;
• means for calculating omegas for each edge associated with said dependence graph;
• means for determining existence of a placement of clock cycle-boundaries in said dependence graph wherein for every recurrence cycle in said dependence graph, a total number of clock cycle-boundaries so placed equals a proposed initiation interval multiplied by a sum of the omegas for the edges belonging to the recurrence cycle of said dependence graph and a maximum delay between successive clock cycle-boundaries so placed is no greater than a proposed clock cycle-time;
• and
• means for determining validity of proposed iteration schedule vectors.

A computer product program comprising

• a memory having computer readable code embodied thereon for implementing a method comprising steps of:
• assigning latencies to dependence graph operations;
• calculating omegas for each edge associated with said dependence graph operations;
• determining existence of a placement of clock cycle-boundaries in said dependence graph, wherein for every recurrence cycle in said dependence graph, a total number of clock cycle-boundaries so placed equals a proposed initiation interval multiplied by a sum of the omegas for the edges belonging to the recurrence cycle of said dependence graph, and a maximum delay between successive clock cycle-boundaries so placed is no greater than a proposed clock cycle-time;
• and
• determining validity of proposed iteration schedule vectors.

A computer product program comprising a memory having computer readable code embodied thereon for implementing a method comprising steps of:

• receiving a dependence graph including operations and edges between the operations, the dependence graph having at least one recurrence cycle wherein for every recurrence cycle in the dependence graph, a total number of clock cycle-boundaries equals a proposed initiation interval multiplied by a sum of omegas for edges belonging to the recurrence cycle;
• receiving a performance specification;
• receiving at least one latency for each operation of the dependence graph, the latency comprising a real time delay;
• and
• determining existence of a placement of clock cycle-boundaries in the dependence graph such that all dependence and timing constraints are satisfied for the performance specification.

A computer product program comprising a memory having computer readable code embodied thereon for implementing a method comprising steps of:

• receiving a dependence graph including operations and edges between the operations, the dependence graph having at least one recurrence cycle wherein recurrence cycles are enumerated and placement of clock cycle-boundaries along each said recurrence cycle further includes a condition that the clock cycle-boundaries so placed are consistent with previous clock cycle-boundary placements;
• receiving a performance specification;
• receiving at least one latency for each operation of the dependence graph, the latency comprising a real time delay;
• and
• determining existence of a placement of clock cycle-boundaries in the dependence graph such that all dependence and timing constraints are satisfied for the performance specification.

A method comprising steps of:

• assigning latencies to dependence graph operations;
• calculating omegas for each edge associated with said dependence graph operations;
• determining existence of a placement of clock cycle-boundaries in said dependence graph, wherein for every recurrence cycle in said dependence graph, a total number of clock cycle-boundaries so placed equals a proposed initiation interval multiplied by a sum of the omegas for the edges belonging to the recurrence cycle or said dependence graph, and a maximum delay between successive clock cycle-boundaries so placed is no greater than a proposed clock cycle-time;
• and
• determining validity of proposed iteration schedule vectors.