Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1999-05-25
2001-04-03
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C710S019000, C710S267000, C714S039000, C716S030000, C716S030000
Reexamination Certificate
active
06212625
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to finite state machines for microcontrollers, and more particularly to a general purpose dynamically programmable state engine for executing finite state machines.
2. Description of the Related Art
MICROCONTROLLERS
As technology advances, computer system components are providing specific services which previously were offered by a microprocessor or the computer system as a whole. A centerpiece of this advancing technology is known as a microcontroller, or embedded controller, which in effect is a microprocessor as used in a personal computer, but with a great deal of additional functionality combined onto the same monolithic semiconductor substrate (i.e., chip). In a typical personal computer, the microprocessor performs the basic computing functions, but other integrated circuits perform functions such as communicating over a network, controlling the computer memory, and providing input/output with the user.
In a typical microcontroller, many of these functions are embedded within the integrated circuit chip itself. A typical microcontroller, such as the Am186EM or AM186ES by Advanced Micro Devices, Inc., of Sunnyvale, Calif., not only includes a core microprocessor, but further includes a memory controller, a direct memory access (DMA) controller, an interrupt controller, and both asynchronous and synchronous serial interfaces. In computer systems, these devices are typically implemented as separate integrated circuits, requiring a larger area and increasing the size of the product. By embedding these functions within a single chip, size is dramatically reduced, often important in consumer products.
From a consumer products designer's viewpoint, often the particular combination of added features make a particular microcontroller attractive for a given application. Many microcontrollers are available that use the standard x86 microprocessor instructions, allowing for software to be easily developed for such microcontrollers. Because of the similar execution unit instruction sets, the added features often become principal differentiating criteria between particular microcontrollers.
In implementing microcontrollers in embedded systems, another common requirement or desirable feature is the reduction of the bandwidth needed by any particular portion of the microcontroller in negotiating with other portions. For example, the core of a microcontroller is the execution unit, which is essentially a microprocessor core. An execution unit should be free to perform the programmed task to which it is dedicated, rather than spending time waiting on other units within the microcontroller.
STATE MACHINES
For many system control applications, sequential logic designers are utilizing state machines rather than complex microprocessors to provide speed and sufficient functionality without undue complexity. One advantage of transferring certain functions from a microprocessor to a state machine is freeing the microprocessor to perform other functions. Examples of functions which have been efficiently translated into state machines include vector control for a Fast Fourier Transform (FFT) algorithm, addressing by a controller, encoding and decoding, encryption and decryption, arbitration, event monitoring, and simple control functions.
A state machine is essentially a digital device that traverses through a predetermined sequence of states in an orderly fashion. A simple state machine includes two essential elements: combinatorial logic and memory. The memory is used to store the state of the machine. The combinatorial logic may be viewed as two distinct functional blocks: the next state decoder and the output decoder. The next state decoder determines the next state of the state machine while the output decoder generates the actual outputs. A state machine traverses through a sequence of states, where the next state is determined by the next state decoder, depending upon the current state and input conditions. A state machine also provides sequences of output signals and/or actions based upon state transitions. The outputs are generated by the output decoder based upon the current state and input conditions. There are two widely known types of state machines: Mealy and Moore. Moore state machine outputs are a function of the current state only. In Mealy-type state machines, the outputs are functions of both the current state and the input conditions.
Parts of digital systems whose outputs depend on their past inputs as well as their current ones can be modeled as finite state machines. A finite state machine provides a finite number of states and transitions, with each transition originating in a state and leading to a state. The “history” of a finite state machine is summed up in the value of its internal state. When a new input is presented to a finite state machine, an output is generated which depends on this input and the current state of the finite state machine. The finite state machine is then moved into a new state, referred to as the next state. The next state depends on both the input and the current state. Finite state machines, which may be considered abstract models for synchronous sequential machines, have become an integral part of logic circuits.
One traditional approach to executing or evaluating a finite state machine has been loading a state table file. A state table file, which is typically generated by a compiler, is commonly in the form of a hardware description file. The state information for executing the finite state machine may be extracted from the state table file by a compiler or state machine analyzer. Using the extracted state information, a compiler or state machine analyzer may generate a data structure representing the finite state machine.
So far as is known, prior art compilers and state machine analyzers have not provided for dynamic execution of finite state machines or a methodology for executing different types of finite state machines.
SUMMARY OF THE INVENTION
Briefly, a system according to the present invention may provide a general purpose dynamically programmable state engine for executing a finite state machine. The general purpose dynamically programmable state engine may include an input and filter unit, a storage unit, a transition unit, and an action generation unit. The storage unit stores a plurality of state entries. Each state entry in the storage unit may include a state identifier, a symbol identifier, a plurality of state attributes, and a next state. The input and filter unit receives inputs and translates the inputs to symbols. The symbols are provided to the transition unit. The transition unit maintains a current state and locates a state entry in the state and transition storage unit having a state identifier matching the current state and a symbol identifier matching a current symbol. The transition unit also sets the current state to a next state of a matching entry. When a matching entry is a terminating entry, an action generation unit for processing the terminating entry is activated.
A state engine in accordance with the present invention permits execution of a finite state machine to be independent of the hardware implementation of the finite state machine. The state engine also provides for dynamic execution of a finite state machine. Another aspect of the state engine is the capability of executing a plurality of finite state machines.
REFERENCES:
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 5450598 (1995-09-01), Kaplan et al.
patent: 5481717 (1996-01-01), Gaboury
patent: 5517432 (1996-05-01), Chandra et al.
patent: 5537580 (1996-07-01), Giomi et al.
patent: 5539680 (1996-07-01), Palnitkar et al.
patent: 5706473 (1998-01-01), Yu et al.
Registered Logic Design, Rev. A, Advanced Micro Devices, Inc., Feb. 1996, Chapter 5, pp. 40-59.
State Machine Design, Rev. A, Advanced Micro Devices, Inc., Jun. 1993, Chapter 5, pp. 60-71.
Advanced Micro Devices , Inc.
Akin Gump Strauss Hauer & Feld L.L.P.
Pan Daniel H.
LandOfFree
General purpose dynamically programmable state engine for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with General purpose dynamically programmable state engine for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General purpose dynamically programmable state engine for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2538491