Cache for instruction set architecture using indexes to achieve compression

• US 7,568,086 B2
• Filed: 03/07/2007
• Issued: 07/28/2009
• Est. Priority Date: 10/28/2002
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Ramchandran, Amit
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US11/683,026
• Publication Number:
  US 20070150656A1
• Time in Patent Office: 874 Days
• Field of Search: 712/220, 707/101, 717/152, 717/153, 717/154
• 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. An adaptive computing machine configured to execute 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:

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

when the primary instruction is an explicit caching instruction, storing at least one control word associated with the primary instruction in an instruction storage unit and executing the primary instruction; and

when the primary instruction is a compressed instruction, retrieving, from the instruction storage unit, the at least one previously stored control word using the compressed instruction to execute the compressed instruction.

2. The system of claim 1, wherein the explicit caching instruction stores a control word set comprising a plurality of instructions from the set of instructions.

3. The system of claim 2, wherein the explicit caching instruction stores a control word set comprising a plurality of index values, each index value associated with a storage element within the instruction storage unit.

4. The system of claim 2, wherein the explicit caching instruction stores the control word set in association with at least one index value.

5. The system of claim 4, wherein the explicit caching instruction stores each control word in the control word set 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.

6. The system of claim 1, wherein the explicit caching instruction stores the control word set in association with an index value.

7. The system of claim 6, wherein the compressed instruction includes the index value for retrieving the control word set to execute the compressed instruction.

8. A system configured to execute a set of instructions, the system comprising:

multiple interconnected adaptable execution nodes, each adaptable execution node including;

a cache memory configured to store compressed control words;

data processing elements that are configured by the control words; and

a nodal sequencer configured to receive the set of instructions, decode the set of instructions to produce control words, output the control words to the data processing elements, and store at least one of the control words in the cache memory when an instruction in the set of instructions is an explicit caching instruction, wherein the at least one of the control words is a control word set that represents a compressed instruction.

9. The system of claim 8, wherein the control word set includes a flag.

10. The system of claim 9, wherein the flag indicates that a portion of the control word set includes at least one index that specifies another control word set that is stored in the cache memory.

11. The system of claim 9, wherein the flag indicates that a portion of the control word set includes control word bits.

12. The system of claim 8, wherein the nodal sequencer is further configured to decode a first compressed instruction in the set of instructions by reading the control word set from the cache memory using an index specified by the first compressed instruction.

13. The system of claim 8, wherein the control word set includes at least one index that specifies another control word set that is stored in the cache memory.

14. The system of claim 8, wherein the nodal sequencer is further configured to store the control word set in multiple entries of the cache memory when a single explicit caching instruction is received.

15. The system of claim 8, wherein the control words determine connections between the data processing elements.

16. The system of claim 8, wherein the control words determine execution flow of the set of program instructions.

17. The system of claim 8, wherein each bit of a control word is associated with one of the data processing elements.

18. The system of claim 8, wherein each bit of a control word is associated with a connection between two of the data processing elements.