Method and apparatus for reordering in a non-uniform compute device

Patent metadata

Field	Value
Publication number	US-10445094-B2
Application number	US-201615166467-A
Country	US
Kind code	B2
Filing date	May 27, 2016
Priority date	May 27, 2016
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

A data processing apparatus includes a multi-level memory system, one or more first processing unit coupled to the memory system at a first level and one or more second processing units each coupled to the memory system at a second level. A first reorder buffer maintains data order during execution of instructions by the first and second processing units and a second reorder buffer maintains data order during execution of the instructions by an associated second processing unit. An entry in the first reorder buffer is configured, dependent upon an indicator bit, as an entry for a single instruction or a pointer to an entry in the second reorder buffer. An entry in the second reorder buffer includes instruction block start and end addresses and indicators of input and output register. Instructions are released to a processing unit when all inputs, as indicated by the reorder buffers, are available.

First claim

What is claimed is:

1. A data processing apparatus for processing a code block comprising instructions, the data processing apparatus comprising:
a multi-level memory system comprising a first level and a second level, where the first level comprises one or more caches;
one or more host processors each having a first processing unit coupled to a cache of the one or more caches and a plurality of registers for holding data values;
one or more second processing units each coupled to the memory system at the second level;
a first reorder buffer operable to maintain data order during execution of the instructions by the first and second processing units;
a second reorder buffer associated with a processing unit of the one or more second processing units and operable to maintain data order during execution of the instructions by the associated second processing unit; and
an instruction scheduler that routes instructions selectively to one or more of the first and second processing units by:
identifying a block of instructions in the code block marked as being executable by a processing unit of the one or more first processing units and by a processing unit of the one or more second processing units, where the block of instructions has a start address and an end address;
determining, from a marker in the block of instructions, requirements for executing the block of instructions;
determining when and if a processing unit of the one or more second processing units has an ability to satisfy the requirements;
when it is determined that none of the one or more second processing units has the ability to satisfy the requirements, removing the marker and routing the block of instructions to a processing unit of the first processing units; and
when a processing unit of the one or more second processing units is identified as having the ability to satisfy the requirements, routing the block of instructions to the identified second processing unit.
where the first reorder buffer is configured to store a plurality of lines, each line comprising an indicator bit and an entry, where, dependent upon a value of the indicator bit, the entry comprises either an entry for a single instruction or a pointer to an entry in the second reorder buffer for an instruction block,
where the second reorder buffer is configured to store one or more entries for blocks of instructions, an entry for a block of instructions comprising the start address of the block of instructions, the end address of the block of instructions, an indicator of registers of the plurality of registers that provide input values to the block of instructions and an indicator of registers of the plurality of registers for holding output values resulting from execution of the block of instructions, and
where instructions are released to a processing unit of the first and second processing units when all inputs, as indicated by the first and second reorder buffers, are available.

2. The data processing apparatus of claim 1 , where the second level of the memory system comprises a cache memory.

3. The data processing apparatus of claim 1 , where the second level of the memory system comprises a non-cache memory.

4. The data processing apparatus of claim 1 , where the instruction scheduler is further operable to:
write an entry for a single instruction as a first entry of the first reorder buffer when an instruction is routed to one of the first processor units;
write an entry for a block of instructions to the second reorder buffer when the block of instructions is routed to the second processing unit associated with the second reorder buffer; and
write a pointer to the entry in the second reorder buffer as a second entry of the first reorder buffer when a block of instructions is routed to the processing unit associated with the second reorder buffer.

5. The data processing apparatus of claim 1 , further comprising a rename unit that replaces one or more register names in an instruction with one or more register locations in the plurality of registers prior to writing a corresponding entry to the first reorder buffer or an entry to both the first and second reorder buffers.

6. The data processing apparatus of claim 1 , where the second reorder buffer is configured to store the indicator of registers of the plurality of registers that provide input values to the block of instructions as a first bit map, and is further configured to store the indicator of registers of the plurality of registers for holding output values resulting from execution of the block of instructions as a second bit map.

7. The data processing apparatus of claim 1 , further comprising an instruction queue, where instructions are released to the instruction queue when all of the input values, as indicated by the first and second reorder buffers, are available.

8. The data processing apparatus of claim 1 , wherein the first and second reorder buffers comprise first-in, first-out (FIFO) buffers.

9. A data processing apparatus for executing instructions, the data processing apparatus comprising:
a multi-level memory system comprising a first level and a second level, where the first level comprises one or more caches;
one or more host processors each having a first processing unit coupled to a cache of the one or more caches and a plurality of registers for holding data values;
one or more second processing units each coupled to the memory system at a second level;
a reorder buffer that maintains data order during execution of the instructions by the first and second processing units;
an instruction scheduler that routes instructions of the instructions selectively to one or more of the first and second processing units;
where the reorder buffer stores a plurality of lines, each line comprising an indicator bit and an entry, where, dependent upon a value of the indicator bit, the entry comprises either an entry for a single instruction or an entry for a block of instructions,
where an entry for a block of instructions comprises a start address of the block of instructions, an end address of the block of instructions, an indicator of registers of the plurality of registers that provide input values to the block of instructions and an indicator of registers of the plurality of registers for holding output values resulting from execution of the block of instructions, and
where instructions are released to a processing unit of the first and second processing units when all inputs, as indicated by the reorder buffer, are available.

10. The data processing apparatus of claim 9 , where the end address of the block of instructions comprises an offset from the start address of the block of instructions.

11. The data processing apparatus of claim 9 , where the instruction scheduler is further operable to:
write an entry for a single instruction to the reorder buffer when an instruction is routed to one of the first processing units; and
write an entry for a block of instructions to the reorder buffer when a block of instructions is routed to one of the second processing units,
where the indicator bit is set in accordance with the entry.

12. The data processing apparatus of claim 9 , further comprising a rename unit that replaces one or more register names in an instruction with one or more register locations in the plurality of registers prior to writing a corresponding entry to the reorder buffer.

13. The data processing apparatus of claim 9 , where the reorder buffer stores the indicator of registers of the plurality of registers that provide input values to the block of instructions as a first bit map, and further con stores the indic

Assignees

• Advanced Risc Mach Ltd

Inventors

• Beard Jonathan Curtis
• Elsasser Wendy
• Wang Shibo

Classifications

• G06F12/084

  with a shared cache · CPC title

• G06F12/0811 Primary

  with multilevel cache hierarchies · CPC title

• G06F9/32

  Address formation of the next instruction, e.g. by incrementing the instruction counter (G06F9/38 takes precedence) · CPC title

• G06F9/30098

  Register arrangements · CPC title

• G06F2212/452

  Instruction code · CPC title