Cache for instruction set architecture using indexes to achieve compression

• US 7,194,605 B2
• Filed: 07/24/2003
• Issued: 03/20/2007
• Est. Priority Date: 10/28/2002
• Status: Active Grant

• Current Assignee: QST Holdings LLC
• Original Assignee: NVIDIA Corporation
• Inventors: Ramchandran, Amit
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US10/628,083
• Publication Number:
  US 20040093479A1
• Time in Patent Office: 1,335 Days
• Field of Search: 712/220, 712/207
• US Class Current: 712/220
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/287 Multiplexed DMA G06F13/30 takes precedence
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/3012 Organisation of register space, e.g. banked or distributed register file
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method for compressing a set of instructions in an adaptive computing machine includes identifying frequently executed instructions, inserting an explicit caching instruction associating the identified instructions with an index value in the set of instructions before the identified instructions and replacing at least one instance of the frequently executed instructions subsequent to the explicit caching instruction with a compressed instruction referencing the index value. One or more instructions can be identified for compression, including groups of consecutive or non-consecutive instructions. The explicit caching instruction directs a node in an adaptive computing machine to store instructions in an instruction storage unit in association with an index value. Instructions stored in the storage unit are retrievable with reference to the index value. The compressed instruction may include one or more references to index values, and can include a sequence of index values indicating the sequence of execution of the associated instructions.

Claims

1. A method for compressing a set of instructions for a node in a adaptive computing machine, the method comprising:

identifying frequently executed instruction in the set of instructions for an information processing device;

inserting an explicit caching instruction in the set of instructions before the identified instruction, wherein the explicit caching instruction associates the identified instruction with at least one index value, the at least one index value referencing an area of an instruction storage unit; and

replacing at least one instance of the frequently executed instruction subsequent to the explicit caching instruction with a compressed instruction referencing the at least one index value, wherein the compressed instruction directs an information processing device to execute the identified instruction associated with the at least one index value wherein the frequently executed instruction is accessible from the instruction storage unit using the at least one index value.

2. The method of claim 1, wherein the step of identifying includes identifying a subset from the set of instructions comprising a plurality of instructions.

3. The method of claim 2, wherein the subset comprises a plurality of consecutive instructions from the set of instructions.

4. The method of claim 2, wherein the explicit caching instruction directs an information processing device to store the subset of instructions in an instruction storage unit in association with the at least one index value.

5. The method of claim 4, wherein the instruction storage unite has a storage element associated with the at least one index value, such that the subset of instructions stored in the storage element can be retrieved with reference to the at least one index value.

6. The method of claim 4, wherein the instruction storage unit has a plurality of storage elements, each storage element associated with an index value, and the explicit caching instruction directs an information processing device to store each instruction of the subset of instructions in one of the plurality of storage elements, such that each one of the instructions can be retrieved with reference to the index value associated with the storage element.

7. The method of claim 2, wherein the subset of instructions is part of an inner loop.

8. The method of claim 1, wherein the explicit caching instruction directs a node in an adaptive computing machine to store the identified instruction in the instruction storage unit in association with the at least one index value.

9. The method of claim 8, wherein the instruction storage unit has a storage element associated with the at least one index value, such that the instruction stored In the storage element can be retrieved with reference to the at least one index value.

10. The method of claim 6 wherein the compressed instruction includes a plurality of references to the index values, each reference to the index values directing an information processing device to execute the instruction stored in the storage element associated with the referenced index value.

11. The method of claim 10 wherein the plurality of references to the index values are arranged In a sequence indicating the sequence of execution of the associated instructions.

12. A method for executing a set of instructions for an information processing device, the method comprising:

retrieving a primary instruction within the set of instructions from a memory;

when the primary instruction is an explicit caching instruction, storing at least one instruction subsequent to the primary Instruction in an instruction storage unit; and

when the primary instruction is a compressed instruction, retrieving, from the instruction storage unite, the at least one previously stored instruction using the compressed instruction and executing the at least one previously stored instruction.

13. The method of claim 12, wherein the explicit caching instruction stores a subset comprising a plurality of instructions from the set of instructions.

14. The method of claim 13, wherein the explicit caching instruction sores a subset comprising a plurality of consecutive instructions from the set of instructions.

15. The method of claim 13, wherein the explicit caching instruction stores the subset of instructions in association with at least one index value.

16. The method of claim 15, wherein the explicit caching instruction stores each of the subset of instructions in one of a plurality of storage elements, each storage element associated with an index value, such that each one of the instructions can be retrieved with reference to the at least one index value associated with the storage element.

17. The method of claim 12, wherein the explicit caching instruction stores the at least one instruction in association with an index value.

18. The method of claim 17, wherein the compressed instruction includes the index value for retrieving and executing the at least one instruction associated with the index value.

19. An adaptive computing machine configured to compress a set of instructions for a node, wherein the adaptive computing machine comprises one or more processors and a memory containing logic that, when processed by the one or more processors, cause the one or more processors to perform a set of steps comprising:

identifying frequently executed instruction in the set of instructions for an information processing device;

inserting an explicit caching instruction in the set of instructions before the identified instruction, wherein the explicit caching instruction associates the identified instruction with at least one index value, the at least on index value referencing an area of an instruction storage unit; and

replacing at least one instance of the frequently executed instruction subsequent to the explicit caching instruction with a compressed instruction referencing the at least on index value, wherein the frequently executed instruction is accessible from the instruction storage unit using the at least one index value.