# US 9,436,476 B2 · Method and apparatus for sorting elements in hardware structures > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,476 B2 - Document ID: US9436476B2 - Status: Granted - Kind: B2 - Application number: 14/052,571 - Filed: 2013-10-11 - Published: 2014-09-18 - Granted: 2016-09-06 - Earliest claimed: 2013-03-15 - Assignees: Soft Machines, Inc. - Applicants: Soft Machines, Inc. - Inventors: Mohammad A. Abdallah; Mandeep Singh - Web page: https://patentgrep.com/patent/US9436476B2 ## CPC - G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags} - G06F 9/3834: {Maintaining memory consistency} - G06F 9/3854: {Instruction completion, e.g. retiring, committing or graduating} - G06F 9/3858: {Result writeback, i.e. updating the architectural state or memory} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for sorting elements in hardware structures is disclosed. The method comprises selecting a plurality of elements to order from an unordered input queue (UIQ) within a predetermined range in response to finding a match between at least one most significant bit of the predetermined range and corresponding bits of a respective identifier associated with each of the plurality of elements. The method further comprises presenting each of the plurality of elements to a respective multiplexer. Further the method comprises generating a select signal for an enabled multiplexer in response to finding a match between at least one least significant bit of a respective identifier associated with each of the plurality of elements and a port number of the ordered queue. Finally, the method comprises forwarding a packet associated with a selected element identifier to a matching port number of the ordered queue from the enabled multiplexer. ## Claims ### Claim 1 A method for sorting elements in hardware structures, said method comprising: selecting a plurality of elements to order from an unordered input queue (UIQ) within a range in response to finding a match between at least one most significant bit of said range and corresponding bits of a respective identifier operable to tag each of said plurality of elements, wherein said UIQ comprises a plurality of out of order elements; presenting each of said plurality of elements to a respective multiplexer; and generating a select signal for an enabled multiplexer corresponding to each element in said plurality of elements in response to finding a match between at least one least significant bit of a respective identifier operable to tag each of said plurality of elements and a port number of an ordered retirement queue. ### Claim 2 (depends on 1) The method of claim 1, further comprising: forwarding a packet corresponding to a selected element identifier to a matching port number of said ordered queue from said enabled multiplexer. ### Claim 3 (depends on 2) The method of claim 2, further comprising: generating a write enable for said matching port number by performing a logical OR operation of said select signal; and writing said packet into said matching port number of said ordered queue. ### Claim 4 (depends on 2) The method of claim 2, wherein said UIQ is disposed in a module of a pipeline for an out of order microprocessor, wherein said module is selected from a group consisting of: a register file and a load-store queue. ### Claim 5 (depends on 4) The method of claim 4, wherein said selecting and said generating are performed in response to a communication protocol controlled by a reorder buffer in said pipeline. ### Claim 6 (depends on 5) The method of claim 5, wherein said communication protocol communicates said range and a number of elements to be ordered to said module. ### Claim 7 (depends on 6) The method of claim 6, wherein said ordered queue comprises elements to be retired from said module in a retirement cycle of said pipeline. ### Claim 8 (depends on 5) The method of claim 5, wherein a respective identifier for each of said plurality of elements corresponds to a location in said reorder buffer wherein said plurality of elements are stored prior to being entered into said UIQ. ### Claim 9 (depends on 4) The method of claim 4, wherein said plurality of elements are entered into said UIQ of said register file from a write back module of said pipeline. ### Claim 10 (depends on 4) The method of claim 4, wherein said plurality of elements are entered into said UIQ of said register file from a reorder buffer in said pipeline. ### Claim 11 A processor unit configured to perform a method for sorting elements in hardware structures, said method comprising: selecting a plurality of elements to order from an unordered input queue (UIQ) within a range in response to finding a match between at least one most significant bit of said range and corresponding bits of a respective identifier operable to tag each of said plurality of elements, wherein said UIQ comprises a plurality of out of order elements; presenting each of said plurality of elements to a respective multiplexer; and generating a select signal for an enabled multiplexer corresponding to each element in said plurality of elements in response to finding a match between at least one least significant bit of a respective identifier operable to tag each of said plurality of elements and a port number of an ordered retirement queue. ### Claim 12 (depends on 11) The process unit as described in claim 11, wherein said method further comprises: forwarding a packet corresponding to a selected element identifier to a matching port number of said ordered queue from said enabled multiplexer. ### Claim 13 (depends on 12) The processor unit as described in claim 12, wherein said method further comprises: generating a write enable for said matching port number by performing a logical OR operation of said select signal; and writing said packet into said matching port number of said ordered queue. ### Claim 14 (depends on 12) The processor unit as described in claim 12, wherein said processor unit is an out of order microprocessor and wherein said UIQ is maintained in a module of a pipeline for said out of order microprocessor, wherein said module is selected from a group consisting of: a register file and a load-store queue. ### Claim 15 (depends on 14) The processor unit as described in claim 14, wherein said selecting and said generating are performed in response to a communication protocol controlled by a reorder buffer in said pipeline. ### Claim 16 (depends on 15) The processor unit as described in claim 15, wherein said communication protocol communicates said range and a number of elements to be ordered to said module. ### Claim 17 (depends on 16) The processor unit as described in claim 16, wherein said ordered queue comprises elements to be retired from said module in a retirement cycle of said pipeline. ### Claim 18 (depends on 15) The processor unit as described in claim 15, wherein a respective identifier for each of said plurality of elements corresponds to a location in said reorder buffer wherein said plurality of elements are stored prior to being entered into said UIQ. ### Claim 19 (depends on 14) The processor unit as described in claim 14, wherein said plurality of elements are entered into said UIQ of said register file from a write back module of said pipeline. ### Claim 20 (depends on 14) The processor unit as described in claim 14, wherein said plurality of elements are entered into said UIQ of said register file from a reorder buffer in said pipeline. ### Claim 21 An apparatus for sorting elements in hardware structures, said apparatus comprising: a memory; a processor communicatively coupled to said memory, wherein said processor is configured to process instructions out of order, and further wherein said processor is configured to: select a plurality of elements to order from an unordered input queue (UIQ) within a range in response to finding a match between at least one most significant bit of said range and corresponding bits of a respective identifier operable to tag each of said plurality of elements, wherein said UIQ comprises a plurality of out of order elements; present each of said plurality of elements to a respective multiplexer; and generate a select signal for an enabled multiplexer corresponding to each element in said plurality of elements in response to finding a match between at least one least significant bit of a respective identifier operable to tag each of said plurality of elements and a port number of an ordered retirement queue. ### Claim 22 (depends on 21) The apparatus of claim 21, wherein the processor is further configured to: forward a packet corresponding to a selected element identifier to a matching port number of said ordered queue from said enabled multiplexer. ### Claim 23 (depends on 22) The apparatus of claim 22, wherein said processor is further configured to: generate a write enable for said matching port number by performing a logical OR operation of said select signal; and write said packet into said matching port number of said ordered queue. ### Claim 24 (depends on 22) The apparatus of claim 22, wherein said plurality of elements correspond with said instructions processed out of order by said processor.