Method for modifying the behavior of a state machine

A method and system for modifying the function of a state machine having a programmable logic device. The method includes the steps of modifying a high-level design of the state machine to obtain a modified high-level design of the state machine with a modified function; generating a programmable logic device netlist from differences in the high-level design and the high-level modified design; and installing the modified function into the state machine by programming the programmable logic device based on the programmable logic device netlist.

FIELD OF THE INVENTION

The present invention relates to the field of modifiable state machines; more specifically, it relates to a method and system for determining and coding modifications to a post fabrication modifiable state machine.

BACKGROUND OF THE INVENTION

Presently, a great majority of integrated circuits employ state machines to control the behavior of the integrated circuit. State machines can be extremely complex in nature and difficult to simulate. Often testing after the integrated circuit has been fabricated discloses that a design error has occurred. Therefore, there is a need to provide both a post-fabrication modifiable state machine, and since these modifications may be very difficult to code, an automated system for coding the modifications to the state machine.

SUMMARY OF THE INVENTION

A first aspect of the present invention is a method for modifying the function of a state machine having a programmable logic device, the method comprising: (a) modifying a high-level design of the state machine to obtain a modified high-level design of the state machine with a modified function; (b) generating a programmable logic device netlist from differences in the high-level design and the modified design; and (c) installing the modified function into the state machine by programming the programmable logic device based on the programmable logic device netlist.

A second aspect of the present invention is a computer system comprising a processor, an address/data bus coupled to the processor, and a computer-readable memory unit adapted to be coupled to the processor, the memory unit containing instructions that when executed by the processor implement a method for modifying the function of a state machine having a programmable logic device, the method comprising the computer implemented steps of: (a) modifying a high-level design of the state machine to obtain a modified high-level design of the state machine with a modified function; (b) generating a programmable logic device netlist from differences in the high-level design and the modified design; and (c) installing the modified function into the state machine by programming the programmable logic device based on the programmable logic device netlist.

DETAILED DESCRIPTION OF THE INVENTION

The term designer refers to a human being operating a design system. Unless otherwise noted, all operations are performed automatically by the design system without designer intervention.

The present invention is described using a field programmable gate array (FPGA) as a programmable element. FPGAs are but one type of programmable logic device (PLD) that may be used. Examples of other types of PLDs that may be used in the present invention include but is not limited to programmable read only memories (PROMs), simple programmable logic devices (SPLD) and such programmable array logic (PAL) devices, generic array logic (GAL) devices and programmable logic arrays (PLAs), complex programmable logic devices (CPLDs) such as erasable programmable logic devices (EPLDs), electrically-erasable programmable logic devices (EEPLDs) and multiple array matrices (MAXs), field programmable interconnect devices (FPICs) and other static random access memory (SRAM) based or antifuse based PLDs.

FIG. 1is a simplified functional block diagram of a related art state machine. InFIG. 1, a state machine100includes next state and control logic105for determining the next state of the state machine and a state latch110. Next state logic and control logic105generates control bits out for controlling the circuits being controlled by the state machine and receives control bits in from the circuits being controlled by the state machine. Next state and control logic105generates next state signals, which are latched by state latch110and receives the current state signals from the state latch. There are several options for modifying state machine100and thus the behavior of the integrated circuit controlled by the state machine. These options will be discussed infra.

FIGS. 2A through 2Eare simplified functional block diagrams of modifiable state machines according to the present invention. InFIG. 2A, state machine100A is similar to state machine100ofFIG. 1, except an FPGA115is inserted in the current state path between state latch110and next state and control logic105and a FPGA120is inserted in the next state path between the state latch and the next state and control logic. FPGAs115and120allow modification of the next state signal before the next state is latched by state latch110and allows modifications to the current state signal from the state latch before the current state is received by next state and control logic105. Modifying either the next state or current state signal will alter the behavior of state machine100A. As fabricated, FPGAs115and120are in a default pass through mode. Multiplexers are not shown but required inFIG. 2A. With the appropriate FPGA wiring configuration multiplexing can be accomplished within the FPGA fabric and does not require additional multiplexers outside of the FPGA fabric.

In most schematic diagrams multiplexers interconnecting inputs, outputs, state machine logic circuits, state machine state latches, FPGAs and internal state paths are not shown but are required. Multiplexers allow bypassing FPGAs or directing signals to the FPGAs so the signals can be changed or their path altered by the programmed FPGAs. Multiplexers are not shown because their placement and interconnection is driven by the specific design requirements of a given application. One of ordinary skill in the art would know where multiplexers should be placed and how they should be interconnected. Multiplexers are placed during the initial integrated design process as illustrated inFIG. 3and described infra.

InFIG. 2B, state machine100B is similar to state machine100A ofFIG. 2A, except a FPGA125is inserted in the control bits out path between next state and control logic105and the circuits being controlled and a FPGA130is inserted in the control bits in path between circuits being controlled and the next state and control logic. FPGAs125and130allow modification of the control bits out and control bits in respectively. Modifying the control bits out will modify the function of the circuits being controlled by state machine100B and modifying control bits in will modify the behavior of the state machine. As fabricated, FPGAs115,120,125and130are in a default pass through mode.

InFIG. 2C, state machine100C is similar to state machine100B ofFIG. 2B, except a FPGA135programmable as a latch is added to state latch110. FPGA135adds additional states to state machine100C. As fabricated, FPGAs115,120,125,130and135are in a default pass through mode.

InFIG. 2D, state machine100D is similar to state machine100C of FIG.2CB, except FPGAs115,120,125,130and135are interconnected by a programmable wire fabric140. Fabric140allows all states and all I/O functions including new bits out and new bits in to be available to all of the FPGAs. As fabricated, FPGAs115,120,125,130and135are in a default pass through mode and all programmable wires are connected to default circuit nodes.

InFIG. 2E, a first state machine145and a second state machine150share the same FPGA155. The output of state machines145is coupled to the input of FPGA155and the input of a first multiplexer160. The output of state machines150is coupled to the input of FPGA155and the input of a second multiplexer165. The output of first multiplexer160is coupled to the input of first state machine145and the output of second multiplexer165is coupled to the input of second state machine150.

FIG. 3is a flowchart of the method of designing and determining the programming required for a FPGA in order to modify the behavior of a modifiable state machine according to the present invention. In step200, an integrated circuit design in a high-level design (HLD) language is generated and the HLD design is stored in a design file205. In step210, FPGAs including multiplexers that would be needed to modify state machine inputs, outputs and internal paths are inserted into the HLD design and a static timing analysis performed (seeFIG. 4and description infra). In step215, design synthesis is performed on the HLD design to generate a netlist, which is stored in design file205. In step220, physical design is completed and a shapes files, used to fabricate a photolithographic mask set used in fabricating the integrated circuit is generated. In step225, the integrated circuit is fabricated and tested.

In step230it is determined if the integrated circuit functions as expected. If in step230, the integrated circuit functions as expected then in step235, the integrated circuit is shipped, otherwise the method proceeds to step240. It should be noted that integrated circuit function covers the cases of (1) a fail due to a design error in the state machine, (2) fails caused by circuit fails or design errors that are correctable by a change to the state machine and (3) changes to a otherwise good integrated circuit to modify its function or performance that are implementable by a change to the state machine. Fails due to defects and all other reasons are or that are not correctable by a change to the state machine are screened out in step225.

In step240, the original HLD design is changed in order to modify the function of the state machine and the new HLD design is stored in design file205. Changing of the original HLD can be done without intervention of the designer other than to point to the original and new HLD files. Alternatively, the designer can provide input to this process to this process in identifying the HDL code to be implemented in the FPGA. In step245, a FPGA extraction tool parses and reads all the lines of the HLD code for the original and new designs and compares them. It extracts out of the new design all lines of code that are different or not found in the original HLD design code. This is done without intervention from the designer other than to point to the two HLD files. Examples of function changes that the compare may find includes but is not limited to (1) new state machine inputs, (2) new state machine outputs, (3) output changes based on input and state, (4) new state machine states and (5) new or changed state decision paths. Examples of the FPGA portion of original and new HLD codes and the extracted HLD code are given infra.

In step250, FPGA synthesis is performed to create a FPGA netlist, which is stored in design file205. The synthesizer knows the available design elements (including the FPGA array or arrays and multiplexers) from the netlist structure synthesized in step215. The synthesizer then synthesizes an FPGA logic structure to support the new or changed logic functions and synthesizes any interconnects to multiplexers that may be needed to bypass the original state machine paths and replace them with paths through the FPGA logic structure. Next, in step255, it is determined if the FPGA is large enough to program the changes required by the FPGA netlist. If the FPGA is not large enough, then re-synthesis of the updated FPGA function can be performed until a solution is found which fits in the available FPGA. If this is ultimately unsuccessful, then in step260, the integrated circuit is scrapped (or used for other PINs) and the method terminates, otherwise the method proceeds to step265. Steps250and255are done without intervention from the designer other than to point to the original netlist and the FPGA netlist.

In step265, the FPGA of the integrated circuit (in hardware) is programmed using the FPGA netlist code as a basis. First, the FPGA netlist is compiled into a SRAM configuration pattern. Second, the compiled pattern is then applied to the SRAM array on the physical integrated circuit in order to program the SRAM. Third, the SRAM “wires” the FPGA array or arrays to activate the changed functions, to activate any new functions and deactivate any obsoleted functions. The preceding description of an SRAM-based FPGA embodiment is described as an example. The present invention is applicable to a variety of other types of PLDs as described supra. Then, in step270, the integrated circuit is retested and in step275, it is determined if the integrated circuit functions as expected. If in step275, the integrated circuit functions as expected then in step235, the integrated circuit is shipped, otherwise the method proceeds to step240. Thus, other than to change the HLD design for the new state machine functions, no significant intervention by the designer is required to produce a physical integrated chip with the new or changed functions.

FIG. 4is a diagram illustrating a static timing analysis as practiced by the present invention. InFIG. 4, the cycle time of a an integrated circuit includes the worst case (longest path) circuit delay and hardwired state machine delay plus any delay through the multiplexers added to the state machine plus FPGA positive slack. Slack is a measure of how much earlier a signal arrives than the specified time it must arrive at. Positive slack provides an operating margin. Based on the amount of positive slack, the designer can determine how large the FPGA can be (the larger, the more delay). The designer can use some or all of the negative slack in order to increase the size of the FPGA.

FIG. 5is a block schematic diagram of an exemplary application utilizing a modifiable state machine. InFIG. 5, a 3-way round robin arbiter300is illustrated. Arbiter300includes a state machine305A including a FPGA310A (or other PLD) and state latches312, and a timer315. Required multiplexers are not shown, but one of ordinary skill in the art would know how to configure multiplexers into the original design HLD as described supra. A first processor320, a second processor325, a third processor330share access to random access memory (RAM)335via a tri-state buffer340. Arbiter300grants access to one processor320,325or330at a time. When more than one processor request access to RAM335at the same time the state machine is hardwired to grant access in the priority in a fixed order, for example, processor320first, processor325second and processor330third. The input signals reqA, reqB, reqC and TimesUp from processor320, processor325, processor330and timer310A respectively to state machine305A are key signals as are the output signals ackA, ackB, ackC and RunTimer to from processor320, processor325, processor330and timer310A respectively from state machine305A.

ReqA, reqB and reqC are requests from the respective processors320,325and330for access to the ADDRESS, WRITE DATA and R/W BIT buses. AckA, ackB and ackC are grants of access to buses ADDRESS, WRITE DATA and R/W BIT by state machine305A to respective processors320,325and330. AddrA, addrB and AddC are RAM335addresses from respective processors320,325and330. WdataA, wdataB and WdataC are write data to RAM335from respective processors320,325and330. RwA, rwB and rwC are read/write bits from respective processors20,325and330to RAM335.

State machine305A (with FPGA in default mode, i.e. original arbiter function and FPGA not used) is illustrated inFIG. 6Aand described infra. A modified version of state machine305A using FPGA to modify the function of arbiter300is illustrated inFIG. 6Band described infra.

FIG. 6Ais a state diagram of the state machine ofFIG. 5fabricated as designed by the present invention. InFIG. 6A, state machine350A is designed to grant access to processors A, B and C (processors320,325and330to RAM335ofFIG. 5) in the priority order A, B, C. When the state machine is idle, the state machine state is 0000. When processor A is granted access, the state machine state is 1001. When processor B is granted access, the state machine state is 0101. When processor C is granted access the state machine state is 0011. Transition between these states can only occur when an input to the state machine matches the values on the state transition path between the current state and the next state. For example transition from state 1001 (GrantA) to state 0101 (GrantB) can only when an input is either 01xx or 11x1, where x is a “don't care bit” and can be 0 or 1. The portion of the HLD code describing state machine350A is given in TABLE I.

FIG. 6Bis a state diagram of the state machine ofFIG. 5as modified by the present invention. InFIG. 6B, state machine350B is a modified version of state machine350A ofFIG. 6Aand is designed to grant access to processors A, B and C (processors320,325and330to RAM335ofFIG. 5) in the priority order C, A, B. When the state machine is idle, the state machine state is 0000. When processor A is granted access, the state machine state is 1001. Notice none of the states of the state machine has changed in this example. When processor B is granted access, the state machine state is 0101. When processor C is granted access the state machine state is 0011. What has changed is the input required to transition from state 0000 (idle) to 0101 (grantB) which was 01xx and is now 010x, to transition from state 0000 (idle) to 0011 (grantC) which was 001x and is now xx1x and to transition from state 0000 (idle) to 1001 (grantA) which was 1xxx and is now 1x0x. These three changes are enclosed in boxes. The portion of the HLD code describing state machine350B is given in TABLE II.

The portion of the HLD code in bold and repeated in TABLE III, shows all the differences between the original HLD code and the new HLD code that would be found in step245ofFIG. 3and that would be synthesized in step250ofFIG. 3to generate a FPGA netlist.

FIG. 7is a block schematic diagram of a portion of the modifiable state machine ofFIG. 5after implementation of the coding to modify the behavior of the state machine according to the present invention. InFIG. 7, a portion of state machine305A ofFIG. 5, modified state machine305B, includes the original hardwired next state logic355, the programmed FPGA310A ofFIG. 5, FPGA310B, and a change of input to state latches312. Multiplexers have not be illustrated inFIG. 7. The FPGA netlist generated from the code of TABLE III (step250ofFIG. 3) supra is listed in TABLE IV.

The FPGA netlist of table IV results in the hardware ofFIG. 7after synthesis. The changes include: (1) directing reqA, reqB and reqC through FPGA310B to new path in_FPGA to next state logic355, (2) redirecting out_HW through FPGA310B to reqA, reqB and reqC, (3) directing pstate_HW(1;0) through FPGA310B to new path pstate_FPGA(1:0) then to state latches312. The paths through (dashed lines) FPGA310B result from the programming of the SRAM (based on the compiled FPGA netlist) that “wires” the gates of FPGA310B.

FIG. 8is a schematic block diagram of a general-purpose computer for practicing the present invention

Generally, the method described herein with respect to modifying a FPGA modifiable state machine is practiced with a general-purpose computer and the method may be coded as a set of instructions on removable or hard media for use by the general-purpose computer.FIG. 8is a schematic block diagram of a general-purpose computer for practicing the present invention. InFIG. 8, computer system400has at least one microprocessor or central processing unit (CPU)405. CPU405is interconnected via a system bus410to a random access memory (RAM)415, a read-only memory (ROM)420, an input/output (I/O) adapter425for a connecting a removable data and/or program storage device430and a mass data and/or program storage device435, a user interface adapter440for connecting a keyboard445and a mouse450, a port adapter455for connecting a data port460and a display adapter465for connecting a display device470.

ROM420contains the basic operating system for computer system400. The operating system may alternatively reside in RAM415or elsewhere as is known in the art. Examples of removable data and/or program storage device430include magnetic media such as floppy drives and tape drives and optical media such as CD ROM drives. Examples of mass data and/or program storage device435include hard disk drives and non-volatile memory such as flash memory. In addition to keyboard445and mouse450, other user input devices such as trackballs, writing tablets, pressure pads, microphones, light pens and position-sensing screen displays may be connected to user interface440. Examples of display devices include cathode-ray tubes (CRT) and liquid crystal displays (LCD).

A computer program with an appropriate application interface may be created by one of skill in the art and stored on the system or a data and/or program storage device to simplify the practicing of this invention. In operation, information for or the computer program created to run the present invention is loaded on the appropriate removable data and/or program storage device430, fed through data port460or typed in using keyboard445.

Thus, both a post-fabrication modifiable state machine and an automated system for coding the modifications to the state machine is provided by the present invention.