State splitting for level reduction

• US 5,617,573 A
• Filed: 05/23/1994
• Issued: 04/01/1997
• Est. Priority Date: 05/23/1994
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Knapp, Steven K., Huang, Alan Y., Kwatra, Sanjeev
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Seto, Jeffrey K.
• Application Number:
  US08/247,445
• Time in Patent Office: 1,044 Days
• Field of Search: 395/775, 326/46, 326/40, 326/17
• US Class Current: 712/200
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

A method of state splitting in a state machine includes determining a number N of logic levels, i.e. CLB levels, for each state in a state machine. Number N is equal to N_i-1 +log_k f_i wherein "k" is the number of input lines to a CLB, "i" is a particular node in a particular hierarchial level in the Boolean logic, and "f" is the number of fanin transitions to the particular node. An average number N(AV) as well as a maximum number N(MAX) of CLBs to implement the states in the state machine are also determined. Then, predetermined exit criteria are checked. One exit criterion includes determining that the maximum number N(MAX) is not associated with a state register, but is instead associated with an output, for example. Another exit criterion includes providing a ratio by dividing the maximum number N(MAX) by the average number N(AV). If the ratio is less than or equal to a split-factor, then this exit criterion is met. In one embodiment, the split factor is between 1.5 and 2.0. Yet another exit criterion includes determining that the state being analyzed has one or two fanin transitions. If none of the exit criteria are met, then the state associated with the maximum number N(MAX) is split into at least two states. The method is further optimized by repeating all steps until at least one exit criterion is met. State splitting in accordance with the present invention typically reduces the levels of CLBs by approximately 20%, thereby significantly reducing delay in the state machine.

Claims

1. A method of state splitting in a state machine including the steps of:

(a) determining a number N of logic levels for each state in said state machine, wherein said number N is equal to;

space="preserve" listing-type="equation">N.sub.i-1 +log.sub.k f.sub.i

wherein

k is the number of input lines to a CLB,

i is a particular node in a particular hierarchial level in a Boolean logic network representing said state machine, and

f is the number of fanin transitions to said particular node;

(b) determining an average number N(AV) of CLB levels of the states in said state machine;

(c) determining the state having a maximum number N(MAX) of CLB levels in said state machine;

(d) splitting the state associated with said maximum number N(MAX) into two states if predetermined exit criteria are not met.

2. The method of state splitting of claim 1 wherein said predetermined exit criteria includes dividing said maximum number N(MAX) by said average number N(AV) to obtain a ratio, and determining whether said ratio is greater than a split factor.

3. The method of state splitting of claim 2 wherein said split factor is between approximately 1.5 and approximately 2.0.

4. The method of state splitting of claim 2 wherein said split factor is approximately 1.5.

5. The method of state splitting of claim 2 wherein said predetermined exit criteria includes determining whether said maximum number N(MAX) is associated with a state register.

6. The method of state splitting of claim 5 wherein said predetermined exit criteria includes determining whether said state having said maximum number N(MAX) provides less than two fanin transitions.

7. The method of state splitting of claim 2 wherein step (d) results in two states having a substantially equal number of fan-in transitions.

8. The method of state splitting of claim 2 wherein step (d) is performed using a Fiduccia-Metheyes procedure.

9. The method of state splitting of claim 1 wherein step (a) includes rounding to the lower integer if N is estimated at an intermediate level.

10. The method of state splitting of claim 1 wherein step (a) includes rounding to the upper integer if N is estimated at a root level.