# US 11,308,057 B2 · System and method for multiplexer tree indexing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,057 B2 - Document ID: US11308057B2 - Status: Granted - Kind: B2 - Application number: 15/824,771 - Filed: 2017-11-28 - Published: 2018-06-14 - Granted: 2022-04-19 - Earliest claimed: 2016-12-12 - Assignees: Advanced Micro Devices, Inc. - Applicants: Advanced Micro Devices, Inc. - Inventors: Steven R. Havlir; Patrick J. Shyvers - Web page: https://patentgrep.com/patent/US11308057B2 ## CPC - G06F 16/2264: {Multidimensional index structures} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/2255: {Hash tables} - G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the at least one bit from the address lookup is a predetermined number of bits. ### Claim 3 (depends on 1) The method of claim 1, wherein the multiplexer tree uses different address bits from the lookup address as select bits for each level in a particular path in the multiplexer tree. ### Claim 4 (depends on 1) The method of claim 1, wherein multiple address bits from the lookup address are hashed at certain levels of the multiplexer tree. ### Claim 5 (depends on 1) The method of claim 1, wherein the determining, by the multiplexer tree, the index into the table includes performing column reduction using the lookup address. ### Claim 6 (depends on 5) The method of claim 5, wherein address bits not used for row reduction are used as input bits for the column reduction. ### Claim 7 (depends on 6) The method of claim 6, wherein hashed selection bits from a corresponding row reduction are used for the column reduction. ### Claim 8 (depends on 1) The method of claim 1, wherein the lookup address includes at least one of global history, linear address, physical address, thread identifier, page attributes, and a pointer. ### Claim 9 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. ### Claim 10 (depends on 9) The system of claim 9, wherein the at least one bit from the address lookup is a predetermined number of bits. ### Claim 11 (depends on 9) The system of claim 9, wherein the multiplexer tree uses different address bits from the lookup address as select bits for each level in a particular path in the multiplexer tree. ### Claim 12 (depends on 9) The system of claim 9, wherein multiple address bits from the lookup address are hashed at certain levels of the multiplexer tree. ### Claim 13 (depends on 9) The system of claim 9, wherein the multiplexer tree further includes one or more column multiplexers, wherein the one or more column multiplexers are configured to perform column reduction in parallel with the hashing and row reduction performed by the plurality of row multiplexers_using the lookup address to select a column. ### Claim 14 (depends on 13) The system of claim 13, wherein bits from the lookup address not used for row reduction are used as input bits for the column reduction. ### Claim 15 (depends on 14) The system of claim 14, wherein hashed selection bits from a corresponding row reduction are used for the column reduction. ### Claim 16 (depends on 9) The system of claim 9, wherein the lookup address includes at least one of global history, linear address, physical address, thread identifier, page attributes, and a pointer. ### Claim 17 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. ### Claim 18 (depends on 17) The multiplexer tree circuit of claim 17, further comprising one or more column multiplexers, wherein the one or more column multiplexers are configured to perform column reduction in parallel with the hashing and row reduction performed by the plurality of row multiplexers using the lookup address to select a column, wherein bits from the lookup address not used for row reduction are used as input bits for the column reduction, and wherein hashed selection bits from a corresponding row reduction are used for the column reduction.