# US 2025/0085974 A1 · Method and device for selecting entry of queue in out-of-order processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0085974 A1
- Document ID: US20250085974A1
- Status: Published application
- Kind: A1
- Application number: 18/580,047
- Filed: 2023-06-13
- Published: 2025-03-13
- Earliest claimed: 2023-01-06
- Assignees: Beijing Vcore Technology Co., Ltd.
- Applicants: Beijing Vcore Technology Co., Ltd.
- Inventors: Zusong LI; Dandan HUAN
- Web page: https://patentgrep.com/patent/US20250085974A1

## CPC

- G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A method for selecting an entry of a queue in an out-of-order processor includes: acquiring a tag value of each entry in the queue; generating a mask bit vector of the queue based on the tag value of each entry; generating an executable bit vector of the queue based on whether a corresponding entry in the queue satisfies an executable condition; generating a selection bit vector of the queue based on the mask bit vector and the executable bit vector; and determining an entry corresponding to a target bit in the selection bit vector as an executable entry, in which the target bit is a first bit in the selection bit vector, and a value of the first bit is equal to a first preset value.

## Claims

### Claim 1

A method for selecting an entry of a queue in an out-of-order processor, comprising:
acquiring a tag value of each entry in the queue;
generating a mask bit vector of the queue based on the tag value of each entry;
generating an executable bit vector of the queue based on indication information of each entry in the queue, wherein the indication information is configured to indicate whether a corresponding entry satisfies an executable condition;
generating a selection bit vector of the queue based on the mask bit vector and the executable bit vector; and
determining an entry corresponding to a target bit in the selection bit vector as an executable entry, wherein the target bit is a first bit in the selection bit vector, and a value of the first bit is equal to a first preset value.

### Claim 2 (depends on 1)

The method according to claim 1, wherein each entry has a corresponding ID number, and a tail entry comprised in the entries of the queue is switched as instructions are written into the queue, wherein in response to the tail entry switching from a last entry of the queue to a first entry of the queue, an ID number corresponding to the tail entry is flipped;
wherein the method further comprises:
in an initialization state, determining the tag value of each entry as a preset first tag value;
after the instructions are written into the queue, determining a number of flips for the ID number corresponding to the tail entry; and
determining the tag value of each entry in the queue based on the number of flips.

### Claim 3 (depends on 2)

The method according to claim 2, wherein determining the tag value of each entry in the queue based on the number of flips comprises:
in response to the number of flips being 0, determining the tag value of each entry in the queue as the preset first tag value;
in response to the number of flips being an odd number, determining a tag value of a target entry in the queue as a preset second tag value; and
in response to the number of flips being other even numbers than 0, determining the tag value of the target entry in the queue as the preset first tag value;
wherein the target entry comprises the first entry and each entry between the first entry and the tail entry.

### Claim 4 (depends on 3)

The method according to claim 3, wherein determining the tag value of each entry in the queue based on the number of flips further comprises:
in response to the number of flips being the odd number, determining a tag value of other entry than the target entry in the queue as the preset first tag value; and
in response to the number of flips being other even number than 0, determining the tag value of the other entry than the target entry as the preset second tag value.

### Claim 5 (depends on 1)

The method according to claim 1, wherein generating the mask bit vector of the queue based on the tag value of each entry comprises:
determining a tag value of a head entry comprised in the entries of the queue;
obtaining a processed tag value of each entry by performing an exclusive-OR (XOR) processing on the tag value of each entry and the tag value of the head entry; and
generating the mask bit vector of the queue based on the processed tag value of each entry.

### Claim 6 (depends on 1)

The method according to claim 1, wherein indication information of each entry comprises first indication information for indicating whether an instruction in the corresponding entry is valid and second indication information for indicating whether a state of the corresponding entry satisfies an execution condition, and
in response to the first indication information indicating the instruction in the corresponding entry is valid and the second indication information indicating the state of the corresponding entry satisfies the execution condition, the corresponding entry satisfies the executable condition,
wherein the first indication information is a value of a valid bit of the corresponding entry and the second indication information comprises a value of a ready bit of the corresponding entry;
generating the executable bit vector of the queue based on the indication information of each entry in the queue comprises:
generating the executable bit vector of the queue based on the value of the valid bit and the value of the ready bit of each entry in the queue.

### Claim 7 (depends on 6)

The method according to claim 6, wherein each entry is numbered sequentially with an integer between 0 and N-1, and N is a number of entries in the queue;
generating the executable bit vector of the queue based on the value of the valid bit and the value of the ready bit of each entry in the queue comprises:
obtaining a valid ready bit vector with N bits by performing a bitwise AND operation on the value of the valid bit and the value of the ready bit of each entry; and
generating an executable bit vector with M bits based on the valid ready bit vector;
wherein in response to N being a power of 2, M is twice N; in response to N being not the power of 2, M is twice X, wherein X is a power of 2 greater than N and closest to N.

### Claim 8 (depends on 7)

The method according to claim 7, wherein generating the executable bit vector with the number of bits being M based on the valid ready bit vector comprises:
obtaining the executable bit vector by taking values of the N bits of the valid ready bit vector as values of a 0th bit to an (N-1)th bit of the executable bit vector and taking values of the N bits of the valid ready bit vector as values of an (M/2)th bit to an (M/2+N-1)th bit of the executable bit vector;
wherein in response to the N being not the power of 2, values of other bits of the executable bit vector than the 0th bit to the (N-1)th bit and the (M/2)th bit to the (M/2+N-1)th bit are equal to second preset values.

### Claim 9 (depends on 1)

The method according to claim 1, wherein a number of bits of the mask bit vector is N; and generating the selection bit vector of the queue based on the mask bit vector and the executable bit vector comprises:
performing a bitwise NOT operation on values of a 0th bit to an (N-1)th bit of the mask bit vector, performing a bitwise AND operation on values of the 0th bit to the (N-1)th bit after the bitwise NOT operation and values of a 0th bit to an (N-1)th bit of the executable bit vector, and taking values of N bits after the bitwise AND operation as values of a 0th bit to an (N-1)th bit of the selection bit vector;
taking values of an Nth bit to an (M-1)th bit of the executable bit vector as values of an Nth bit to an (M-1)th bit of the selection bit vector; and
generating the selection bit vector based on the values of the 0th bit to the (N-1)th bit of the selection bit vector and the values of the Nth bit to the (M-1)th bit of the selection bit vector.

### Claim 10 (depends on 1)

The method according to claim 1, wherein determining the entry corresponding to the target bit in the selection bit vector as the executable entry comprises:
obtaining a target code by performing a position encoding on the target bit;
obtaining a processed code by deleting a value of a highest bit in the target code; and
taking the processed code as an executable entry ID number, and determining an entry corresponding to the executable entry ID number as the executable entry.

### Claim 11 (depends on 7)

The method according to claim 7, wherein after determining the entry corresponding to the target bit in the selection bit vector as the executable entry, the method further comprises:
determining whether a number of executable entries reaches a target number; and
in response to determining that the number of executable entries does not reach the target number, determining a bit of the valid ready bit vector corresponding to the executable entry is invalid, and skipping to the step of generating the executable bit vector with the number of bits being M based on the valid ready bit vector, until the determined number of executable entries reaches the target number.

### Claim 12

(canceled)

### Claim 13

An electronic device, comprising:
at least one processor; and
a memory communicatively connected to the at least one processor and stored with instructions executable by the at least one processor,
wherein the at least one processor is configured to:
acquire a tag value of each entry in a queue;
generate a mask bit vector of the queue based on the tag value of each entry;
generate an executable bit vector of the queue based on indication information of each entry in the queue, wherein the indication information is configured to indicate whether a corresponding entry satisfies an executable condition;
generate a selection bit vector of the queue based on the mask bit vector and the executable bit vector; and
determine an entry corresponding to a target bit in the selection bit vector as an executable entry, wherein the target bit is a first bit in the selection bit vector, and a value of the first bit is equal to a first preset value.

### Claim 14

A non-transitory computer-readable storage medium having computer instructions stored thereon, wherein the computer instructions are configured to cause a computer to perform a method for selecting an entry of a queue in an out-of-order processor, the method comprising:
acquiring a tag value of each entry in the queue;
generating a mask bit vector of the queue based on the tag value of each entry;
generating an executable bit vector of the queue based on indication information of each entry in the queue, wherein the indication information is configured to indicate whether a corresponding entry satisfies an executable condition;
generating a selection bit vector of the queue based on the mask bit vector and the executable bit vector; and
determining an entry corresponding to a target bit in the selection bit vector as an executable entry, wherein the target bit is a first bit in the selection bit vector, and a value of the first bit is equal to a first preset value.

### Claim at position 15

-16. (canceled)

### Claim 17 (depends on 13)

The electronic device according to claim 13, wherein each entry has a corresponding ID number, and a tail entry comprised in the entries of the queue is switched as instructions are written into the queue, wherein in response to the tail entry switching from a last entry of the queue to a first entry of the queue, an ID number corresponding to the tail entry is flipped, wherein the at least one processor is further configured to:
in an initialization state, determine the tag value of each entry as a preset first tag value;
after the instructions are written into the queue, determine a number of flips for the ID number corresponding to the tail entry; and
determine the tag value of each entry in the queue based on the number of flips.

### Claim 18 (depends on 17)

The electronic device according to claim 17, wherein the at least one processor is further configured to:
in response to the number of flips being 0, determine the tag value of each entry in the queue as the preset first tag value;
in response to the number of flips being an odd number, determine a tag value of a target entry in the queue as a preset second tag value; and
in response to the number of flips being other even numbers than 0, determine the tag value of the target entry in the queue as the preset first tag value;
wherein the target entry comprises the first entry and each entry between the first entry and the tail entry.

### Claim 19 (depends on 18)

The electronic device according to claim 18, wherein the at least one processor is further configured to:
in response to the number of flips being the odd number, determine a tag value of other entry than the target entry in the queue as the preset first tag value; and
in response to the number of flips being other even number than 0, determine the tag value of the other entry than the target entry as the preset second tag value.

### Claim 20 (depends on 13)

The electronic device according to claim 13, wherein the at least one processor is further configured to:
determine a tag value of a head entry comprised in the entries of the queue;
obtain a processed tag value of each entry by performing an exclusive-OR (XOR) processing on the tag value of each entry and the tag value of the head entry; and
generate the mask bit vector of the queue based on the processed tag value of each entry.

### Claim 21 (depends on 13)

The electronic device according to claim 13, wherein indication information of each entry comprises first indication information for indicating whether an instruction in the corresponding entry is valid and second indication information for indicating whether a state of the corresponding entry satisfies an execution condition, and
in response to the first indication information indicating the instruction in the corresponding entry is valid and the second indication information indicating the state of the corresponding entry satisfies the execution condition, the corresponding entry satisfies the executable condition,
wherein the first indication information is a value of a valid bit of the corresponding entry and the second indication information comprises a value of a ready bit of the corresponding entry;
wherein the at least one processor is further configured to:
generate the executable bit vector of the queue based on the value of the valid bit and the value of the ready bit of each entry in the queue.

### Claim 22 (depends on 21)

The electronic device according to claim 21, wherein each entry is numbered sequentially with an integer between 0 and N-1, and Nis a number of entries in the queue, wherein the at least one processor is further configured to:
obtain a valid ready bit vector with N bits by performing a bitwise AND operation on the value of the valid bit and the value of the ready bit of each entry; and
generate an executable bit vector with M bits being based on the valid ready bit vector;
wherein in response to N being a power of 2, M is twice N; in response to N being not the power of 2, M is twice X, wherein X is a power of 2 greater than N and closest to N.

### Claim 23 (depends on 22)

The electronic device according to claim 22, wherein the at least one processor is further configured to:
obtain the executable bit vector by taking values of the N bits of the valid ready bit vector as values of a 0th bit to an (N-1)th bit of the executable bit vector and taking values of the N bits of the valid ready bit vector as values of an (M/2)th bit to an (M/2+N-1)th bit of the executable bit vector,
wherein in response to the N being not the power of 2, values of other bits of the executable bit vector than the 0th bit to the (N-1)th bit and the (M/2)th bit to the (M/2+N-1)th bit are equal to second preset values.
