System and method for multiplexer tree indexing
AssigneeAdvanced Micro Devices, Inc.
InventorsSteven R. Havlir, Patrick J. Shyvers
Life of this patent
Estimating the term…
Abstract
Described herein is a system and method for multiplexer tree (muxtree) indexing. Muxtree indexing performs hashing and row reduction in parallel by use of each select bit only once in a particular path of the muxtree. The muxtree indexing generates a different final index as compared to conventional hashed indexing but still results in a fair hash, where all table entries get used with equal distribution with uniformly random selects.
Claims18
A method for accessing data stored as a table in a storage medium, the method comprising:
- receiving, at a multiplexer tree, a read access request for the table, the read access request including at least a lookup address;
- determining, by the multiplexer tree, an index into the table by performing-hashing and row reduction in parallel, wherein the row reduction uses at least one bit from the lookup address without repeating the use of the at least one bit with respect to traversing a particular path in the multiplexer tree to select at least one row;
- and
- accessing a selected storage element in the table based on the selected at least one row,
- wherein the multiplexer tree uses each address bit in the lookup address as a select bit at least once in a particular path in the multiplexer tree.
A system for accessing data stored as a table in a storage medium, the system comprising:
- a processor;
- the storage medium;
- and
- a multiplexer tree connected to the storage medium and the processor, the multiplexer tree including a plurality of row multiplexers, wherein the multiplexer tree is configured to:
- receive a read access request from the processor to access the table, the read access request including at least a lookup address;
- determine an index into the table by performing hashing and row reduction in parallel, wherein the row reduction uses at least one bit from the lookup address without repeating the use of the at least one bit with respect to traversing a particular path in the multiplexer tree to select at least one row;
- and
- access a selected storage element in the table based on the selected at least one row,
- wherein the multiplexer tree uses each address bit in the lookup address as a select bit at least once in a particular path in the multiplexer tree.
A multiplexer tree circuit comprising:
- circuitry configured to receive a read access request for data stored as a table in a storage medium, the read request including at least a lookup address;
- a plurality of row multiplexers, wherein the plurality of row multiplexers are configured to perform hashing and row reduction in parallel and each row multiplexer uses at least one bit from the lookup address without repeating the use of the at least one bit with respect to traversing a particular path in the multiplexer tree to select at least one row;
- and
- circuitry configured to access a selected storage element in the table based on the selected at least one row,
- wherein each address bit in the lookup address is used as a select bit at least once in a particular path in the multiplexer tree.
Dependencies are inferred from the claim text.