Method and apparatus for an improved stack arrangement and operations thereon

An apparatus for an MRU stack, said apparatus comprising:

• means for specifying a command;
• means for specifying a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value specifying means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, said multiplexers further arranged such that the multiplexer corresponding to said MRU register receives as input an initialization value and an input from each register in the set of registers, including itself, and the other multiplexers in said set of data multiplexers receive as input an initialization value, data from the preceding register and data from itself;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command specifying means for receiving a command as input and further being arranged to transmit an output to a stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value specifying means for receiving a data value as input.

An apparatus for an MRU stack, said apparatus directly or indirectly connected to a stack search requesting unit, stack search requesting unit specifying a command and a data value to said MRU stack, said apparatus comprising:

• means for receiving a command;
• means for receiving a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value receiving means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data value and such that a data value can be inserted into the stack or promoted to the top of the stack within two or less clock cycles;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command receiving means for receiving a command as input and further being arranged to transmit an output to the stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value receiving means for receiving a data value as input.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module, the stack pointer including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data value;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module said stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, said multiplexers further arranged such that the multiplexer corresponding to said MRU register receives as input an initialization value and an input from each register in the set of registers, including itself, and the other multiplexers in said set of data multiplexers receive as input an initialization value, data from the preceding register and data from itself;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module, the stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data value and such that a data value can be inserted into the stack or promoted to the top of the stack within two or less clock cycles;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including stack data having one or more stack data values, said stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said method comprising the steps of:

• searching for an item in the stack data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, the inserting of the item occurring during a single clock cycle.

A method for manipulating data in a stack, said stack including stack data having one or more stack data values, said stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said method comprising the steps of:

• searching for an item in the stack data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including stack data having one or more stack data values, said stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said method comprising the steps of:

• searching for an item in the stack data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, the inserting of the item occurring during two or less clock cycles.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module, the stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, the pointer manipulation associated with the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, the pointer manipulation associated with the inserting of the item occurring during a single clock cycle.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module, the stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, pointer manipulation associated with the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including a stack data module for storing one or more stack data values, said stack further including a stack pointer module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said method comprising the steps of:

• searching for an item in the stack data module using the stack pointer module, the stack pointer module including a set of data multiplexers, including one or more multiplexers, a set of registers, including one or more registers wherein an MRU register specifies, either directly or indirectly, a location of a most-recently-used stack data value and an LRU register specifies, either directly or indirectly, a location of a least-recently-used stack data value, and an address multiplexer, said data multiplexers and registers configured such that for each register in the set of registers, there is a corresponding multiplexer in the set of data multiplexers, said corresponding multiplexer arranged and coupled to its corresponding register to receive one or more inputs and provide an output to the corresponding register, the registers in said set of registers arranged and interconnected by the multiplexers such that data values are specified from a most-recently-used data value down to a least-recently-used data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, the pointer manipulation associated with the inserting of the item occurring during a single clock cycle.

An apparatus for an MRU stack, said apparatus comprising:

• means for receiving a command;
• means for receiving a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value receiving means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said stack pointer module and said stack data module interconnected to allow pointer manipulation associated with the promotion of an item to the top of the stack to occur during a single clock cycle and to allow pointer manipulation associated with the insertion of an item into the stack to occur during a single clock cycle;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command receiving means for receiving a command as input and further being arranged to transmit an output to a stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value receiving means for receiving a data value as input.

An apparatus for an MRU stack, said apparatus comprising:

• means for receiving a command;
• means for receiving a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value receiving means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said stack pointer module and said stack data module interconnected to allow pointer manipulation associated with the promotion of an item to the top of the stack to occur during a single clock;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command receiving means for receiving a command as input and further being arranged to transmit an output to a stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value receiving means for receiving a data value as input.

An apparatus for an MRU stack, said apparatus comprising:

• means for receiving a command;
• means for receiving a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value receiving means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said stack pointer module and said stack data module interconnected to allow a data value to be inserted into the stack in a single clock cycle;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command receiving means for receiving a command as input and further being arranged to transmit an output to a stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value receiving means for receiving a data value as input.

A computer readable medium having stored thereon instructions for causing a computer to implement the following steps:

• searching for an item in a stack, the stack including stack data having one or more stack data values, the stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in the set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, the inserting of the item occurring during a single clock cycle.

A computer readable medium having stored thereon instructions for causing a computer to implement the following steps:

• searching for an item in a stack, the stack including stack data having one or more stack data values, the stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in the set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, pointer manipulation associated with the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used, pointer manipulation associated with the inserting of the item occurring during a single clock cycle.

A computer readable medium having stored thereon instructions for causing a computer to implement the following steps:

• searching for an item in a stack, the stack including stack data having one or more stack data values, the stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in the set of references such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used, pointer manipulation associated with the promoting of the item occurring during a single clock cycle;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

A method for manipulating data in a stack, said stack including stack data having one or more stack data values, said stack further including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references being such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value, said method comprising the steps of:

• searching for an item in the stack data;
• if the item is found in the stack data, then promoting the item such that the item is identified as being the most-recently-used;
• and
• if the item is not found in the stack data, then inserting the item into the stack such that the item is identified as being the most-recently-used.

An apparatus for an MRU stack, said apparatus comprising:

• means for receiving a command;
• means for receiving a data value;
• a stack data module for storing one or more stack data values, said stack data module being coupled to said data value receiving means for receiving a data value as input;
• a stack pointer module for referencing stack data values stored in said stack data module, said stack pointer module being coupled to said stack data module to provide as input a reference to one or more stack data values, said stack pointer module including a stack pointer list having a set of references, the set of references including one or more stack pointers, each stack pointer uniquely specifying a stack data value in the stack data, the one or more stack pointers including an MRU stack pointer specifying the most-recently-used stack data value in the stack data and an LRU stack pointer specifying the least-recently-used stack data value in the stack data, the stack pointers in said set of references being listed such that stack data values are specified from a most-recently-used data value down to a least-recently-used data value;
• and
• a stack control module for the MRU stack, said stack control module being coupled to said command receiving means for receiving a command as input and further being arranged to transmit an output to a stack search requesting unit, said stack control module further being coupled to said stack pointer module to provide operational control of the stack pointer module functions, said stack control module further being coupled to said stack data module to provide control of the accessing of data to and from the stack data module and to receive as input a stack data value, said stack control module further being coupled to said data value receiving means for receiving a data value as input.