Speculative load of look up table entries based upon coarse index calculation in parallel with fine index calculation

• US 20050198054A1
• Filed: 03/04/2005
• Published: 09/08/2005
• Est. Priority Date: 03/04/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Sankaran, Jagadeesh
• Granted Patent: US 7,177,876 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 1/03 working, at least partly, by table look-up G06F1/025 takes precedence
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/3016 Decoding the operand specifier, e.g. specifier format
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A computer implemented method accesses data in a look up table via an index divided into a coarse index and a fine index. The method calculates the coarse index and fetches plural look up table entries. While the fetch is in progress, the method calculates the fine index. The method determines and extracts the look up table entry corresponding to the combined coarse and fine indexes Fetching plural look up table entries includes executing a single word load instruction, a doubleword load instruction or a pair of sequential or simultaneous single word load instructions. Extracting the look up table entry may include a section select move instruction, an extract and zero-extend a bit field instruction or a shift and mask operation.

Claims

1. A computer implemented method for accessing data in a look up table at locations in a memory determined by an index comprising the steps of:

dividing the index into a coarse index requiring a first amount of calculation and a fine index requiring a second amount of calculation greater than said first amount;

calculating said coarse index;

fetching plural look up table entries from a memory to a data register file corresponding to said coarse index;

while said plural look up table entries are being transferred from said memory to said data register file, calculating said fine index;

determining the look up table entry corresponding to a combination of said coarse index and said fine index; and

extracting said determined look up table entry from said data register file.

2. The computer implemented method of claim 1, wherein:

said index is a two dimensional quantity, a first dimension of said index corresponding to said coarse index and a second dimension of said index corresponding to said fine index.

3. The computer implemented method of claim 2, wherein:

said look up table consists of a regular array having a first predetermined number of sets of entries in said first dimension and having a second predetermined number of entries in each of said set of entries.

4. The computer implemented method of claim 2, wherein:

said look up table consists of a sparsely populated array having a first predetermined number of sets of entries in said first dimension and at least two different numbers of entries in two differing sets of entries.

5. The computer implemented method of claim 4, wherein:

said sparsely populated array of said look up table is disposed in memory with the first entry of each set of entries immediately following a last entry of a previous set of entries.

6. The computer implemented method of claim 1, wherein:

said memory consists of a plurality of memory words having a first predetermined bit length;

said look up table entries each have a second predetermined bit length, said first predetermined bit length being an integral multiple of said second predetermined bit length;

said look up table is stored in memory as said integral multiple of entries in each memory word; and

said data register file consists of a plurality of data registers, each data register having said first predetermined bit length;

said step of fetching plural look up table entries from a memory consists of executing a word load instruction to move a memory word from said memory to an instruction specified one of said plurality of data registers of said data register file.

7. The computer implemented method of claim 6, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

storing data in a data register indicative of a section within a data register corresponding to a location within said data register storing said determined look up table entry, and

executing a section select move instruction having a first source register field indicating a data register storing said plurality of look up table entries, a second source register field indicating a data register storing said data indicative of said section and a destination register field indicating a data register to store a resultant of said section select move instruction.

8. The computer implemented method of claim 6, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

storing first data in a data register indicative of a left shift amount and second data in said data register indicative of a right shift amount corresponding to a location within said data register storing said determined look up table entry, and

executing an extract and zero-extend a bit field instruction having a first source register field indicating a data register storing said plurality of look up table entries, a second source register field indicating a data register storing said first and second data, and a destination register field indicating a data register to store a resultant of said extract and zero-extend a bit field instruction.

9. The computer implemented method of claim 6, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

storing a right shift amount in a first data register corresponding to a location within said data register storing said determined look up table entry,

storing a mask in a second data register, said mask having 1'"'"'s at a number of least significant bit positions equal to said second predetermined bit length and 0'"'"'s at all other bit positions,

executing a shift instruction having a first source register field indicating a data register storing said plurality of look up table entries, a second source register field indicating said first data register storing said right shift amount, and a destination register field indicating a destination data register to store a resultant of said shift instruction, and

executing and AND instruction having a first source register field indicating said destination data register of said shift instruction, a second source register field indicating said second data register storing said mask, and a destination register field indicating a destination data register to store a resultant of said AND instruction.

10. The computer implemented method of claim 1, wherein:

said memory consists of a plurality of memory words having a first predetermined bit length;

said look up table entries each have a second predetermined bit length, said first predetermined bit length being an integral multiple of said second predetermined bit length;

said look up table is stored in memory as said integral multiple of entries in each memory word; and

said data register file consists of a plurality of data registers, each data register having said first predetermined bit length;

said step of fetching plural look up table entries from a memory comprises moving two consecutive memory words from said memory to an instruction specified pair of said plurality of data registers of said data register file.

11. The computer implemented method of claim 10, wherein:

said step of moving data from two consecutive memory words from said memory to an instruction specified pair of said plurality of data registers of said data register file consists of executing a doubleword load instruction.

12. The computer implemented method of claim 11, wherein:

said instruction specified pair of said plurality of data registers consists of a data register designated by an instruction source register field and a corresponding data register.

13. The computer implemented method of claim 12, wherein:

said plurality of data registers of said data register file are denominated by register number;

said instruction source register field designates a register number; and

said data register corresponding to said data register denominated by said register number of said instruction source register field is a data register denominated by a next sequential register number.

14. The computer implemented method of claim 10, wherein:

said step of moving data from two consecutive memory words from said memory to an instruction specified pair of said plurality of data registers of said data register file comprises executing a first word load instruction to move a memory word from said memory to a first instruction specified one of said plurality of data registers of said data register file and executing a second word load instruction to move a memory word from a next sequential location to a second instruction specified one of said plurality of data registers of said data register file.

15. The computer implemented method of claim 14, wherein:

said step of moving data from two consecutive memory words from said memory to an instruction specified pair of said plurality of data registers of said data register file comprises sequentially executing said first word load instruction and said second word load instruction.

16. The computer implemented method of claim 14, wherein:

said step of moving data from two consecutive memory words from said memory to an instruction specified pair of said plurality of data registers of said data register file comprises simultaneously executing said first word load instruction and said second word load instruction.

17. The computer implemented method of claim 10, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

determining which of said pair of instruction designated data registers stores said determined look up table entry,

storing data in a data register indicative of a section within a data register corresponding to a location within said determined data register storing said determined look up table entry, and

executing a section select move instruction having a first source register field indicating said determined data register storing said determined look up table entry, a second source register field indicating a data register storing said data indicative of said section and a destination register field indicating a data register to store a resultant of said section select move instruction.

18. The computer implemented method of claim 10, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

determining which of said pair of instruction designated data registers stores said determined look up table entry,

storing first data in a data register indicative of a left shift amount and second data in said data register indicative of a right shift amount corresponding to a location within said determined data register storing said determined look up table entry, and

executing an extract and zero-extend a bit field instruction having a first source register field indicating said determined data register storing said determined look up table entry, a second source register field indicating a data register storing said first and second data, and a destination register field indicating a data register to store a resultant of said extract and zero-extend a bit field instruction.

19. The computer implemented method of claim 10, wherein:

said step of extracting said determined look up table entry from said data register file consists of;

determining which of said pair of instruction designated data registers stores said determined look up table entry,

storing a right shift amount in a first data register corresponding to a location within said data register storing said determined look up table entry,

storing a mask in a second data register, said mask having 1'"'"'s at a number of least significant bit positions equal to said second predetermined bit length and 0'"'"'s at all other bit positions,

executing a shift instruction having a first source register field indicating said determined data register storing said determined look up table entry, a second source register field indicating said first data register storing said right shift amount, and a destination register field indicating a destination data register to store a resultant of said shift instruction, and

executing and AND instruction having a first source register field indicating said destination data register of said shift instruction, a second source register field indicating said second data register storing said mask, and a destination register field indicating a destination data register to store a resultant of said AND instruction.