EFFICIENT INSTRUCTION PROCESSING FOR SPARSE DATA

• US 20170192793A1
• Filed: 12/31/2015
• Published: 07/06/2017
• Est. Priority Date: 12/31/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ruwase, Olatunji, Seshadri, Vivek, Chilimbi, Trishul A.
• Granted Patent: US 10,592,252 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3869 Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
• CPC Class Codes: G06F 9/3873 Variable length pipelines, e.g. elastic pipeline

Abstract

Efficient instruction processing for sparse data includes extensions to a processor pipeline to identify zero-optimizable instructions that include at least one zero input operand, and bypass the execute stage of the processor pipeline, determining the result of the operation without executing the instruction. When possible, the extensions also bypass the writeback stage of the processor pipeline.

Claims

1. A method implemented according to a processor pipeline, the method comprising:

fetching an instruction to be processed, the instruction comprising a first input operand, a second input operand, and a destination operand;

determining that the instruction to be processed is a zero-optimizable instruction;

determining that the first input operand of the instruction is a zero value; and

based on the first input operand of the instruction being a zero value, determining a result of the instruction while bypassing an execute stage of the processor pipeline.

2. A method as recited in claim 1, wherein determining that the instruction to be processed is a zero-optimizable instruction comprises:

comparing an opcode associated with the instruction to a list of opcodes associated with zero-optimizable instructions; and

determining that the opcode associated with the instruction matches an opcode in the list of zero-optimizable instructions.

3. A method as recited in claim 1, wherein determining a result of the instruction while bypassing an execute stage of the processor pipeline comprises:

determining that the instruction is an addition instruction; and

determining that the result of the instruction is equal to the second input operand.

4. A method as recited in claim 1, wherein determining a result of the instruction while bypassing an execute stage of the processor pipeline comprises:

determining that the instruction is a multiplication instruction; and

determining that the result of the instruction is equal to zero.

5. A method as recited in claim 1, wherein the list of zero-optimizable instructions includes:

an addition instruction; and

a multiplication instruction.

6. A method as recited in claim 5, wherein the list of zero-optimizable instructions further includes a subtraction instruction.

7. A method as recited in claim 5, wherein the list of zero-optimizable instructions further includes a division instruction.

8. A method as recited in claim 1, further comprising:

determining, based on the result of the instruction, whether or not to bypass a writeback stage of the processor pipeline.

9. A method as recited in claim 8, wherein determining, based on the result of the instruction, whether or not to bypass the writeback stage of the processor pipeline comprises:

comparing the result of the instruction to a current value of the destination operand;

when the result of the instruction is equal to the current value of the destination operand, determining to bypass the writeback stage of the processor pipeline; and

when the result of the instruction is not equal to the current value of the destination operand, processing the instruction by proceeding to the writeback stage of the processor pipeline.

10. A method as recited in claim 8, further comprising:

when it is determined to bypass the writeback stage of the processor pipeline, proceeding to a commit stage of the processor pipeline without processing the writeback stage of the processor pipeline.

11. A processor comprising:

a processor pipeline to direct performance of fetch, decode, execute, writeback, and commit stages; and

extensions to the processor pipeline, the extensions to the processor pipeline configured to detect and direct processing of zero-optimizable instructions.

12. A processor as recited in claim 11, wherein the extensions to the processor pipeline comprise:

a stage configured to detect zero-optimizable instructions; and

a stage to bypass the execute stage of the processor pipleline.

13. A processor as recited in claim 11, wherein the extensions to the processor pipeline comprise:

a stage configured to detect zero-optimizable instructions; and

a stage to bypass the execute and writeback stages of the processor pipeline.

14. A processor as recited in claim 11, wherein the extensions to the processor pipeline comprise:

a stage configured to detect zero-optimizable instructions;

a stage to bypass the execute stage of the processor pipleline; and

a stage to bypass the execute and writeback stages of the processor pipeline.

15. A device comprising:

an instruction cache configured to store instructions to be processed; and

a processor, communicatively coupled to the instruction cache, wherein the processor is configured to;

fetch an instruction from the instruction cache;

determine whether the instruction is a zero-optimizable instruction;

when the processor determines that the instruction is a zero-optimizable instruction, determine whether an input operand of the instruction has a value of zero; and

when an input operand of the instruction has a value of zero, determine a result of the instruction without executing the instruction.

16. A device as recited in claim 15, wherein the processor is configured to determine whether the instruction is a zero-optimizable instruction based, at least in part, on an opcode associated with the instruction.

17. A device as recited in claim 15, wherein the processor is configured to determine that the instruction is a zero-optimizable instruction when the instruction includes at least one of:

an addition instruction;

a subtraction instruction;

a multiplication instruction;

or

a division instruction.

18. A device as recited in claim 15, wherein:

the device further comprises a data cache for storing results of processed instructions; and

the processor is further configured to based, at least in part, on a result of the instruction determined without executing the instruction, determine whether or not to write the result of the instruction to the data cache.

19. A device as recited in claim 18, wherein the processor is configured to determine whether or not to write the result of the instruction to the data cache by comparing the result of the instruction to a current value of a destination operand associated with the instruction.

20. A device as recited in claim 19, wherein the processor is configured to commit the instruction without writing the result of the instruction to the data cache when the result of the instruction is equal to the current value of the destination operand associated with the instruction.