Reduction of storage elements in synthesized synchronous circuits

Method and apparatus for reducing a number of storage elements in a synthesized synchronous circuit. In one embodiment, the circuit is represented as a directed, partitioned graph. The graph is divided into a plurality of time-ordered timeslots that are bounded by storage elements. The strongly-connected components (SCCs) in the graph are first identified. For each middle SCC where there is slack between the middle SCC and a first SCC and slack between the middle SCC and a second SCC, a time-slot-relative direction is selected for moving the middle SCC. The direction is selected as a function of a number of storage elements required for moving the middle SCC toward the first SCC versus moving the middle SCC toward the second SCC. The middle SCC is then moved in the selected time-slot-relative direction.

FIELD OF THE INVENTION

Background

Software-implemented designs, or parts thereof, are sometimes re-implemented in hardware for cost and performance reasons. Program loops within the software are synthesized in hardware as synchronous circuits that include interconnected logic units and registers that are synchronously clocked.

Live-in variables to the loop correspond to primary inputs of the circuit, live-out variables correspond to primary outputs, and recurrences correspond to registers or RAMs. This correspondence allows synchronous circuit optimization techniques, along with compiler techniques to be applied to the problem of mapping such loops onto efficient synchronous circuit implementations.

Generally, the result of loop synthesis is a multi-staged pipeline structure consisting of logic and registers. Data flows both forward from the outputs of registers in one stage to the inputs of logic (or registers) in later stages, and backward from the output of logic (or registers) in one stage to the inputs of logic (or registers) in previous stages.

Pipeline compaction is a known technique for reducing the number of registers in pipelined circuit structures. In a circuit design that is represented as a graph with nodes and edges, pipeline compaction iteratively minimizes the slack on all input edges on all strongly connected components (SCCs), moving each SCC backward to the earliest legal timeslot. An SCC is a subset, S, of nodes in a graph such that any node in S is reachable from any other node in S, and S is not a subset of any larger such set.

Even though pipeline compaction is effective in reducing the register requirements of a pipelined circuit design, pipeline compaction does not always produce an optimally reduced circuit.

A system and method that address the aforementioned problems, as well as other related problems, are therefore desirable.

SUMMARY OF THE INVENTION

In various embodiments, the present invention provides a method and apparatus for reducing a number of storage elements in a synthesized synchronous circuit. In one embodiment, the circuit is represented as a directed, partitioned graph. The graph is divided into a plurality of time-ordered timeslots that are bounded by storage elements. The strongly-connected components (SCCs) in the graph are first identified. For each middle SCC where there is slack between the middle SCC and a first SCC and slack between the middle SCC and a second SCC, a time-slot-relative direction is selected for moving the middle SCC. The direction is selected as a function of a number of storage elements required for moving the middle SCC toward the first SCC versus moving the middle SCC toward the second SCC. The middle SCC is then moved in the selected timeslot-relative direction.

DETAILED DESCRIPTION

FIG. 1illustrates an example program loop102synthesized into a hardware implementation104. Blocks106,108,110, and112represent registers, and circles114and116represent logic. The signals that enter the left sides of the registers are enable signals, and the signals that enter the right sides of the registers are initial values. Input data signals enter the tops of the registers and logic, and output data signals exit from the bottom of the registers and logic.

Dashed lines122and124represent time-relative stages of the hardware implementation. The hardware between line122and124is stage122, and the hardware below line124is stage124. It can be seen that some signals feed forward from stage122to stage124, for example, the input data signal to register122, and other signals feed backward from stage124to stage122, for example, the output data signal from logic116feeds back as input data to register110.

It is often the case that pipelining produces circuits with a large number of registers. Because registers occupy chip area, it is desirable to minimize the number of registers in the implementation in order to reduce the cost of implementing the circuit, preferably without reducing the performance of the circuit.

Before describing the example embodiments of the invention,FIGS. 2A,2B,3A,3B, and4A–C are presented as background to introduce terminology and concepts used in the present invention.

InFIG. 2B, graph220is directed and partitioned consistent with the registers202,204, and206. Adder206ofFIG. 2Ais represented as logic circle222inFIG. 2B. Generally, the nodes of such a graph represent logic or function units, edges represent signals, and partition lines, for example,224,226, and228divide the graph into time-relative stages. The intersection of a signal line with a partition line represents a register. For example, the intersection of edge230with partition line224corresponds to register202, the intersection of the edge with partition line226corresponds to register204, and the intersection of edge232with partition line228corresponds to register208. The region bounded by partition lines is also referred to as a “timeslot,” with an earlier timeslot positioned above a later timeslot. The collection of timeslots is sometimes referred to as a schedule.

In some synthesized designs certain nodes or sets of nodes can be moved from one timeslot to another without changing the behavior of the circuit relative to the input signals and output signals. The input/output signal lines are said to have “slack” relative to the node or set of nodes.

FIG. 3Ais an graph of an example circuit in which two input signals lines302,304have slack relative to an adder node306. Each of the two input signals302and304is delayed by two registers/timeslots as illustrated by partition lines308and310. The output signal312is provided as input to register layer (partition line)314.FIG. 3Bshows that if the adder node is moved one timeslot earlier, one layer of registers is removed relative to the input signals302and304, and a register layer is added to the output signal. Register layer310becomes an output register layer. By moving the adder node to the earlier timeslot, the slack is removed on the input signal lines. Relative to the input and output signals, the behavior of the circuit ofFIG. 3Bis the same as the circuit ofFIG. 3A.

As stated above, it is sometimes possible to reduce the number of pipeline stages, and hence registers, by reducing the slack between SCCs. Recall that an SCC of a graph is a subset, S, of nodes in the graph such that any node in S is reachable from any other node in S, and S is not a subset of any larger such set of nodes. Relative to the present invention, any node that is not a member of any other SCC is an SCC with that node as the only member.

Whether moving an SCC increases or decreases the number of storage elements or registers required in the design depends on the data widths leading into or out of an SCC and whether the SCC is moved earlier or later in the timeslot schedule. By considering whether the required number of storage elements increases or decreases in each case where slack can be removed in either backward or forward timeslot-relative directions, a greater reduction in the number of required storage elements is achieved.

FIG. 4Ais a partitioned directed graph of an example circuit. SCC402is separated from SCC404by register layers412and414, and SCC404is separated from SCC406by register layers416and418. Register layers414have each have a data width of 4 bits, and register layers416and418each have data widths of 8 bits. With the organization of SCCs and register layers ofFIG. 4A, a total of 24 bits of storage is required (4+4+8+8=24). With the present invention, the differences in data widths between backward and forward in the time schedule biases the direction in which the SCC is moved.

If SCC404is moved backward in the time schedule toward SCC402, as shown inFIG. 4B, the 4-bit register layer414ofFIG. 4Abecomes an 8-bit register layer414′ inFIG. 4B. Moving SCC404back in the schedule increases the required storage from 24 bits to 28 bits (4+8+8+8=28). Thus, even though the slack is reduced between SCC402and SCC404, an associated cost is increased storage requirements.

If SCC404is moved forward in the schedule toward SCC406(relative toFIG. 4A), as shown inFIG. 4C, the 8-bit register layer416ofFIG. 4Abecomes a 4-bit register layer416′. This movement of SCC404decreases the required storage from 24 bits to 20 bits (4+4+4+8=20).

FIG. 5is a flowchart of an example process for reducing the storage element requirements by movement of SCCs in accordance with one embodiment of the invention. The process begins by performing pipeline compaction to move the SCCs to the earliest feasible point in the schedule, and the result is saved as a first circuit description (step502). The pipeline compaction can be performed using current or improved methods. The first circuit description is then further processed by reducing the slack between SCCs (step504) in accordance with the process ofFIG. 6. The result is a second circuit description which is also saved.

The storage element requirements of the second circuit description are then determined (step506). In an example embodiment, the storage element requirements are determined by counting the numbers of bits required by the registers in the circuit description.

Using the first circuit description as a starting point, the SCCs are then moved to the latest point in the schedule using pipeline compaction in the forward direction, thereby forming a third circuit layout (step508). The third circuit description is then further processed by reducing the slack between SCCs (step510) to produce a fourth circuit description.

The storage element requirements of the fourth circuit description are then determined (step512) in the same manner as for the second circuit description. The one of the second and fourth circuit descriptions that has the lesser storage requirements is selected as the final circuit description (step514).

FIG. 6is a flowchart of an example process for reducing the slack between SCCs. The SCCs in the circuit description are initially marked as “unprocessed”, which connotes that the SCCs have not yet been processed (step602). As long as there are unprocessed SCCs (decision step604), the process obtains an unprocessed SCC (step606) and proceeds to check whether it is legal to move the selected SCC forward in the schedule (decision step608).

A forward move is legal if all the output edges from the SCC have slack. Another aspect of whether a move is legal relates to the initiation interval of the circuit definition, which affects the number of timeslots the SCC can be moved. If an SCC does not share any resources, for example, function units, logic, etc., with any other SCC, the SCC may be moved an integral number of timeslots. If the SCC does share resources with another SCC, the SCC may be moved n timeslots, where n is an integral multiple of the initiation interval.

Before moving the SCC forward, the process checks whether the forward move would reduce the requirements for storage elements (decision step610) relative to the storage element requirements of the current circuit description. The storage element requirements are determined as previously described. If moving the SCC forward would reduce the storage element requirements, the SCC is moved forward (step612), the SCC is designated as “processed”, and the process returns to step604.

If moving the SCC forward would not reduce the storage element requirements, the process proceeds to check whether moving the SCC backward is legal (step616). A move backward is legal if all the input edges have slack, with the size of the move restricted by the initiation interval. If moving the SCC backward is legal, the process checks whether the move would reduce the storage element requirements relative to the current circuit definition (decision step618). If moving the SCC backward reduces the storage element requirements, the SCC is moved backward (step620) and designated as “processed” (step614).

If the SCC is not moved, the SCC is designated as processed, and the process proceeds to check the other SCCs. Once all the SCCs have been processed (decision step604), the process checks whether any of the SCCs were moved, either forward or backward (decision step622). If so, the process is repeated, beginning with marking all the SCCs as unprocessed (step602). Otherwise, the process is complete, and control is returned to the process ofFIG. 5.

The present invention is believed to be applicable to a variety of optimization methods and has been found to be particularly applicable and beneficial in reducing storage element requirements in a pipelined synchronous circuit. Other aspects and embodiments of the present invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and illustrated embodiments be considered as examples only, with a true scope and spirit of the invention being indicated by the following claims.