Back to results
US 8,543,528 B2Granted
Exploitation of transition rule sharing based on short state tags to improve the storage efficiency
AssigneeInternational Business Machines Corporation
InventorJan van Lunteren
Life of this patent
Estimating the term…
Abstract
A mechanism is provided with an address generator that is operative to receive a current state vector and a current input value, and the address generator is operative to generate a memory address corresponding to a transition rule in response to the current state vector and the current input value. A transition rule memory includes a memory addresses, and the memory address is a location in the transition rule memory. The transition rule is a transition rule vector that includes a short state tag field. The short state tag field includes fewer bits than the current state vector.
Claims17
An apparatus, comprising:
- an address generator operative to receive a current state vector and a current input value, wherein the address generator is operative to generate a memory address corresponding to a transition rule in response to the current state vector and the current input value;
- a transition rule memory comprising a plurality of memory addresses, wherein the memory address is a location in the transition rule memory;
- and
- a rule selector;
- wherein the transition rule is a transition rule vector comprising a short state tag field;
- wherein the short state tag field comprises fewer bits than the current state vector;
- wherein the rule selector is operative to ensure that the short state tag field is not an error by correlating the memory address to the short state tag field since the memory address is derived from the current state vector;
- and
- wherein when the rule selector determines that there is no correlation between the memory address and the short state tag field, the rule selector is operative to recognize the error.
6 more elements
An apparatus, comprising:
- a transition rule memory comprising a plurality of memory addresses which are locations in the transition rule memory;
- a pattern compiler operative to:
- determine input values for states;
- determine next states for the states;
- for the states that have matching input values and matching next states, determine that the states have a shared rule;
- and
- for the states that have the shared rule, store the share rule in the transition rule memory at a same memory address to be utilized by the states that have the shared rule;
- wherein for the states that have the shared rule, the pattern compiler is operative to assign unique current state vectors each differing in three significant bits;
- and
- wherein the pattern compiler is operative to assign mask vectors for the states that have the shared rule.
7 more elements
A method for transition rule sharing, comprising:
- receiving by an address generator a current state vector and a current input value,
- generating a memory address corresponding to a transition rule in response to the current state vector and the current input value;
- wherein the memory address is a location in the transition rule memory;
- and
- wherein the transition rule is a transition rule vector comprising a short state tag field;
- providing the short state tag field with fewer bits than the current state vector;
- wherein a rule selector is operative to ensure that the short state tag field is not an error by correlating the memory address to the short state tag field since the memory address is derived from the current state vector;
- and
- wherein when the rule selector determines that there is no correlation between the memory address and the short state tag field, the rule selector is operative to recognize the error.
6 more elements
A method for transition rule sharing, comprising:
- determining input values for states;
- determining next states for the states;
- for the states that have matching input values and matching next states, determining that the states have a shared rule;
- for the states that have the shared rule, storing the share rule in a transition rule memory at a same memory address to be utilized by the states that have the shared rule;
- wherein for the states that have the shared rule, the pattern compiler is operative to assign unique current state vectors each differing in three significant bits;
- and
- wherein the pattern compiler is operative to assign mask vectors for the states that have the shared rule.
4 more elements
Dependencies are inferred from the claim text.