Parallelized multiple dispatch system and method for ordered queue arbitration

Patent metadata

Field	Value
Publication number	US-2016259648-A1
Application number	US-201514643051-A
Country	US
Kind code	A1
Filing date	Mar 10, 2015
Priority date	Mar 3, 2015
Publication date	Sep 8, 2016
Grant date	—

Abstract

A parallelized multiple dispatch ordered queue including an ordered queue, qualify logic, ordered select logic, and dispatch logic. The ordered queue stores candidates in order from oldest to youngest into multiple entries. The ordered queue is divided into N groups in which an i'th group includes every i'th entry of every N entries of the ordered queue, wherein i is an integer less than or equal to N. The qualify logic determines whether any candidate is ready to be dispatched. The ordered select logic respectively determines the oldest candidate in each group that is ready to be dispatched. The dispatch logic dispatches the oldest ready candidates in parallel. The shift logic shifts the stored candidates in the ordered queue to fill any vacant entries between remaining ones of the stored candidates without changing an order of the remaining ones of the stored candidates in the ordered queue. The ordered queue may have any size or depth and N is any suitable integer determining the number of candidates (e.g., instructions) that may be dispatched in parallel.

First claim

What is claimed is:

1 . A parallelized multiple dispatch ordered queue, comprising:
an ordered queue that is configured to store candidates in order from oldest to youngest into a plurality of entries, wherein said ordered queue is divided into N groups in which an i'th group includes every i'th entry of every N entries of the ordered queue, wherein i is an integer less than or equal to N; qualify logic that determines whether any of said stored candidates in said ordered queue is ready to be dispatched from said ordered queue; ordered select logic that respectively determines an oldest candidate in each group of said ordered queue that is ready to be dispatched; dispatch logic that dispatches candidates from said N groups in parallel, wherein said dispatch logic dispatches said oldest candidate in each group that is ready to be dispatched and leaving at least one vacant entry in said ordered queue; and shift logic that shifts said stored candidates in said ordered queue to fill said vacant entry between remaining ones of said stored candidates without changing an order of said remaining ones of said stored candidates in said ordered queue.

2 . The parallelized multiple dispatch ordered queue of claim 1 , wherein N is 2 dividing the ordered queue into an even group and an odd group.

3 . The parallelized multiple dispatch ordered queue of claim 1 , wherein N is 4 dividing the ordered queue into 4 groups, which include a first group including entries whose entry numbers are 4n, a second group including entries whose entry numbers are 4n+1, a third group including entries whose entry numbers are 4n+2 and a fourth group including entries whose entry numbers are 4n+3, wherein n is an integer greater than or equal to 0.

4 . The parallelized multiple dispatch ordered queue of claim 1 , wherein N is 3 dividing the ordered queue into 3 groups, which include a first group including entries whose entry numbers are 3n, a second group including entries whose entry numbers are 3n+1, a third group including entries whose entry numbers are 3n+2, wherein n is an integer greater than or equal to 0.

5 . The parallelized multiple dispatch ordered queue of claim 1 , wherein said stored candidates comprise instructions of a microprocessor, and wherein said qualify logic determines whether any stored instruction is ready for execution by the microprocessor.

6 . The parallelized multiple dispatch ordered queue of claim 5 , wherein said dispatch logic dispatches up to N instructions at a time to N execution units of the same type.

7 . The parallelized multiple dispatch ordered queue of claim 1 , wherein:
said qualify logic asserts a plurality of ready signals indicating which of said stored candidates are ready to be dispatched; and wherein said ordered select logic comprises a plurality of multiplexers, each controlled by at least one of said plurality of ready signals.

8 . The parallelized multiple dispatch ordered queue of claim 1 , wherein:
said qualify logic asserts a plurality of ready signals indicating which of said stored candidates are ready to be dispatched; and wherein said ordered select logic comprises a plurality of stacks of multiplexers, wherein each stack of multiplexers corresponds to each of said N groups, wherein each multiplexer is controlled by at least one of said plurality of ready signals, and wherein each said stack of multiplexers outputs said oldest candidate of a corresponding one of said N groups that is ready to be dispatched.

9 . The parallelized multiple dispatch ordered queue of claim 1 , wherein: said oldest candidate in each group that is ready to be dispatched is a candidate that is stored in an entry with a smallest entry number among all the entries storing said stored candidates that are ready to be dispatched in each group.

10 . A microprocessor, comprising:
a register alias table that issues instructions in program order to a parallelized multiple dispatch ordered queue; wherein said parallelized multiple dispatch ordered queue comprises:
an ordered queue that is configured to store said instructions in program order received from said register alias table from oldest to youngest into a plurality of entries, wherein said ordered queue is divided into N groups in which an i'th group includes every i'th entry of every N entries of the ordered queue, wherein i is an integer less than or equal to N;
qualify logic that determines whether any of said stored instructions in said ordered queue is ready to be dispatched from said ordered queue for execution;
ordered select logic that respectively determines an oldest instruction in each group of said ordered queue that is ready to be dispatched;
dispatch logic that dispatches instructions from said N groups in parallel, wherein said dispatch logic dispatches said oldest instruction in each group that is ready to be dispatched leaving a vacant entry in said ordered queue; and
shift logic that shifts said instructions stored in said ordered queue to fill said vacant entry between remaining ones of said stored instructions without changing program order of said remaining ones of stored instructions in said ordered queue; and
N execution units of the same type, each configured to execute said instructions stored in said ordered queue.

11 . The microprocessor of claim 10 , wherein N is 2 to divide said ordered queue into an even group and an odd group for execution by 2 execution units of the same type.

12 . The microprocessor of claim 10 , wherein N is 4 to divide said ordered queue into four groups for execution by 4 execution units of the same type, wherein said four groups include a first group including entries whose entry numbers are 4n, a second group including entries whose entry numbers are 4n+1, a third group including entries whose entry numbers are 4n+2 and a fourth group including entries whose entry numbers are 4n+3, wherein n is an integer greater than or equal to 0.

13 . The microprocessor of claim 10 , wherein:
said qualify logic asserts a plurality of ready signals indicating which of said stored instructions are ready to be dispatched to one of said N execution units; and wherein said ordered select logic comprises a plurality of multiplexers, each controlled by at least one of said plurality of ready signals.

14 . The microprocessor of claim 10 , wherein:
said qualify logic asserts a plurality of ready signals indicating which of said stored instructions are ready to be dispatched to one of said N execution units; and wherein said ordered select logic comprises a plurality of stacks of multiplexers, wherein each stack of multiplexers corresponds to each of said N groups, wherein each multiplexer is controlled by at least one of said plurality of ready signals, and wherein each said stack of multiplexers outputs said oldest instruction of a corresponding one of said N groups that is ready to be dispatched.

15 . A method of dispatching multiple candidates from an ordered queue in parallel, comprising:
storing candidates in order into an ordered queue from oldest to youngest, in which the ordered queue is divided into N groups in which an i'th group includes every i'th entry of every N entries of the ordered queue, wherein i is an integer less than or equal to N; determining whether any of the stored candidates in the ordered queue is ready to be dispatched from the ordered queue; determining an oldest candidate respectively in each group of the ordered queue that is ready to be dispatched; dispatching candidates from the N groups in parallel including said oldest candidate in each group that

Assignees

• Via Alliance Semiconductor Co Ltd

Inventors

• Di Qianli
• Wang Jianbin
• Li Weili
• Yu Xiaoyuan
• Gao xin yu

Classifications

• G06F9/3836 Primary

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title

• G06F9/3855 Primary

  Physics · mapped topic

• G06F9/3851

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/3856

  Reordering of instructions, e.g. using queues or age tags · CPC title