Vectorized table lookup

• US 6,446,198 B1
• Filed: 09/30/1999
• Issued: 09/03/2002
• Est. Priority Date: 09/30/1999
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Sazegari, Ali
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/409,669
• Time in Patent Office: 1,069 Days
• Field of Search: 712/7, 712/300
• US Class Current: 712/300
• 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 7/764 Masking
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30038 using a mask
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06

Abstract

A lookup operation is carried out on a data table by logically dividing the data table into a number of smaller sets of data that can be indexed with a single byte of data. Each set of data consists of two vectors, which constitute the operands for a permute instruction. Only a limited number of bits are required to index into the table during the execution of this instruction. The remaining bits of each index are used as masks into a series of select instructions. The select instruction chooses between two vector components, based on the mask, and places the selected components into a new vector. The mask is generated by shifting one of the higher order bits of the index to the most significant position, and then propagating that bit throughout a byte, for example by means of an arithmetic shift. This procedure is carried out for all of the index bytes in the vector, to generate a select mask. The select mask is then used during a select operation, to choose between the results of permute instructions on different ones of the logically divided sets of data. Multi-byte table entries are retrieved by replicating each index value and adding consecutive values to form multiple consecutive index values that are then used in multiple permute operations.

Claims

1. A method for performing a lookup operation for a table stored in a computer memory, comprising the steps of:

storing an index vector containing multiple index values which respectively designate locations in the table;

performing a plurality of permute operations on different respective sets of data within said table, in accordance with the values in said index vector, to produce a plurality of intermediate result vectors; and

performing at least one select operation on said intermediate result vectors to produce a final result vector of entries from said data table.

2. The method of claim 1 wherein each permute operation is performed on a pair of vectors containing data within said table, and said plurality of permute operations are respectively performed on different pairs of table data vectors.

3. The method of claim 1 wherein each index value contains a predetermined number of data bits, and said permute operations are performed in accordance with some of the data bits in each index value, and wherein said select operation is carried out in accordance with at least one other data bit of each index value.

4. The method of claim 3 wherein the step of performing a select operation comprises the steps of generating a selection mask from said other data bit in each index value, and selectively choosing data values from different intermediate result vectors in accordance with said mask, to produce said final result vector.

5. The method of claim 4 wherein the step of generating a selection mask includes the steps of replicating said other bit throughout said predetermined number of bits, for each index value.

6. The method of claim 5 wherein said replicating step comprises shifting said other bit to a most significant position within said predetermined number of bits, and propagating the value of the most significant bit throughout said predetermined number of bits.

7. The method of claim 6 wherein said propagating step is carried out by means of arithmetic shift operations.

8. The method of claim 3 wherein said predetermined number of bits is one byte.

9. The method of claim 1 further including the steps of:

duplicating the original index values in said index vector to produce plural index vectors containing multiple copies of each original index value;

adding consecutive values to the respective copies of the index values to produce consecutive index values in said plural index vectors; and

performing permute operations in accordance with each of said plural index vectors to retrieve data at consecutive locations within said table.

10. A method for performing a lookup operation for a table stored in a computer memory, comprising the steps of:

storing an index vector containing multiple original index values which respectively designate locations in the table;

duplicating the original index values in said index vector to produce multiple copies of each original index value;

adding consecutive values to the respective copies of the index values to produce consecutive index values; and

performing permute operations in accordance with each of said consecutive index values to retrieve data at consecutive locations within said table.

11. The method of claim 10 wherein each original index value comprises one byte of data, and said index values are duplicated to produce two copies of each index value, to thereby retrieve two consecutive bytes of data from said table for each original index value.

12. The method of claim 10 wherein each original index value comprises one byte of data, and said index values are duplicated to produce four copies of each index value, to thereby retrieve four consecutive bytes of data from said table for each original index value.

13. A computer-readable medium containing a program which executes the steps of:

performing a plurality of permute operations on different respective sets of data within a data table, in accordance with values in an index vector containing multiple index values which respectively designate locations in the table, to produce a plurality of intermediate result vectors; and

performing at least one select operation on said intermediate result vectors to produce a final result vector containing entries from said data table.

14. The computer-readable medium of claim 13 wherein each permute operation is performed on a pair of vectors containing data within said table, and said plurality of permute operations are respectively performed on different pairs of table data vectors.

15. The computer-readable medium of claim 13 wherein the step of performing a select operation comprises the steps of generating a selection mask from at least one data bit in each index value, and selectively choosing data values from different intermediate result vectors in accordance with said mask, to produce said final result vector.

16. The computer-readable medium of claim 15 wherein the step of generating a selection mask includes the steps of replicating said other bit throughout a predetermined number of bits, for each index value.

17. A method for performing a lookup operation in a table stored in a computer memory, comprising the steps of:

storing an index vector containing multiple index values which respectively designate locations in the table;

performing a plurality of permute operations on different respective sets of data within said table, in accordance with the values in said index vector, to produce a plurality of intermediate result vectors;

generating a selection mask from at least one data bit in each index value, and

performing at least one select operation on said intermediate result vectors in accordance with said selection mask, to produce a final result vector of entries from said table.

18. The method of claim 17 wherein each permute operation is performed on a pair of vectors containing data within said table, and said plurality of permute operations are respectively performed on different pairs of table data vectors.

19. The method of claim 17 wherein each index value contains a predetermined number of data bits, and said permute operations are performed in accordance with some of the data bits in each index value, and said selection mask is generated from at least one other data bit of each index value.

20. The method of claim 17 wherein the step of generating a selection mask includes the steps of replicating said one data bit throughout a predetermined number of bits, for each index value.

21. The method of claim 20 wherein said replicating step comprises shifting said one data bit to a most significant position within said predetermined number of bits, and propagating the value of the most significant bit throughout said predetermined number of bits.

22. The method of claim 20 wherein said predetermined number of bits is equal to one byte.

23. A computer-readable medium containing a program which executes the steps of:

duplicating index values in an index vector containing multiple original index values which respectively designate locations in a data table, to produce multiple copies of each original index value;

adding consecutive values to the respective copies of the index values to produce consecutive index values; and

performing permute operations in accordance with each of said consecutive index values to retrieve data at consecutive locations within said table.

24. The computer-readable medium of claim 23 wherein each original index value comprises one byte of data, and said index values are duplicated to produce two copies of each index value, to thereby retrieve two consecutive bytes of data from said table for each original index value.

25. The computer-readable method of claim 23 wherein each original index value comprises one byte of data, and said index values are duplicated to produce four copies of each index value, to thereby retrieve four consecutive bytes of data from said table for each original index value.

26. A computer system, comprising:

a memory which stores a table of data values;

a first register which stores a vector of index values that respectively designate locations in a table stored in said memory; and

a vector processing unit which performs plural permute operations on different respective sets of data stored in said memory, in accordance with the index values stored in said first register, to load values from said memory into a plurality of intermediate result registers;

processes at least one data bit of each index value in said first register to generate a mask; and

performs a select operation on the values in said intermediate result registers in accordance with said mask to selectively load data values from a stored table into a final result register.

27. The computer system of claim 26 wherein said processing unit performs said permute operations in accordance with some of the data bits in each index value, and generates said mask in accordance with at least one other data bit of each index value.

28. The computer system of claim 27 wherein said processing unit generates said mask by replicating said other bit throughout a predetermined number of bits, for each index value.

29. The computer system of claim 28 wherein said processing unit shifts said other bit to a most significant position within said predetermined number of bits, and propagates the value of the most significant bit throughout said predetermined number of bits.

30. The computer system of claim 28 wherein said predetermined number of bits is one byte.

31. The computer system of claim 26 wherein said processing unit duplicates the index values in said first register to produce multiple copies of each original index value, adds consecutive values to the respective copies of the index values to produce consecutive index values, and performs a permute operation in accordance with each of said plural index vectors to retrieve data at consecutive locations within said table.