Reconfigurable data cache controller

• US 6,507,898 B1
• Filed: 02/18/1998
• Issued: 01/14/2003
• Est. Priority Date: 04/30/1997
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Wong, Kevin Chee-Hoong, Gibson, Ian
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US09/025,770
• Time in Patent Office: 1,791 Days
• Field of Search: 711/118, 711/119, 711/120, 711/168, 711/5, 365/230.03
• US Class Current: 711/168
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

Apparatus for supplying multiple, separately addressed data items from a data table in external memory.

The apparatus comprises a cache memory (230) having n separately addressable memories banks organised as m cache-lines and n programmable address generators (1881) each coupled to a corresponding one of said n memory banks. The generators (1881) using an index to generate multiple addresses to simultaneously retrieve multiple data items from the memory banks. A data organizer (1892) positions the retrieved data in an output packet.

Claims

1. Apparatus for supplying multiple, separately addressed data items from a data table in an external memory, said apparatus comprising:

a controller for configuring said apparatus to operate in any one of a plurality of modes of operation;

a cache memory that includes n separately addressable memory banks organized as m cache-lines, where n and m are both a plurality;

n address generators each coupled to a corresponding one of the n memory banks, for generating multiple addresses to retrieve the multiple data items from the memory banks,

wherein each of said multiple address is generated according to an index and a current one of the plurality of modes of operation; and

a data organizer for positioning the retrieved data items in an output packet, wherein said data organizer positions the retrieved data items in the output packet in a manner determined by the current mode of operation.

2. Apparatus as claimed in claim 1,

wherein each generated address includes a tag address and a line address, and

wherein said apparatus further comprises:

a tag memory for storing tag addresses of corresponding lines of said cache memory;

a line-valid memory for storing line-valid statuses of corresponding lines of said cache memory;

n tag comparators, each adapted to compare a tag address of a generated address with a tag address stored in said tag memory corresponding to a line address of the generated address, such that, when there is a match and a line-valid status for that line is also asserted, a hit signal is generated;

a cache controller for controlling retrieval from said cache memory of the multiple data items in response to asserted hit signals, and for controlling a fetching of one or more lines containing one or more of the data items from the external memory when associated hit signals are not asserted; and

a data organizer for positioning the retrieved data in an output packet.

3. Apparatus as claimed in claim 1,

wherein each generated address includes a tag address and a line address, and

wherein said apparatus comprises:

a tag memory and n tag comparators, wherein each tag comparator is adapted to compare a tag address of a generated address with a tag address stored in said tag memory, and each tag comparator is adapted to compare only those parts of the tag addresses determined by the current mode of operation.

4. Apparatus as claimed in claim 2, wherein each multiple address is generated in a form of a complete external memory address.

5. Apparatus as claimed in claim 4, wherein each memory bank includes m bank-lines, and each cache-line includes a bank-line from each memory bank.

6. Apparatus as claimed in claim 5,

wherein each complete generated address includes a tag address, a line address, a bank address, and a byte address;

and

wherein the tag address included in the complete generated address is compared with the tag address stored in said tag memory, the line address is used for addressing a relevant cache-line in the cache memory, the bank address is used for addressing a relevant bank of the memory banks, and the byte address is used for addressing a relevant byte of the bank-line.

7. Apparatus as claimed in claim 1, wherein

each address generator generates an index address in response to the index and the current mode of operation, and

the index address is added to a base address to generate a complete external memory address.

8. Apparatus as claimed in claim 1, wherein said cache memory is a direct mapped cache.

9. Apparatus as claimed in claim 6, wherein one or more of the bank-lines are retrieved from said cache memory in response to corresponding generated addresses.

10. Apparatus as claimed in claim 9, wherein

the multiple data items are one byte sized;

and

said data organizer comprises a selector for selecting the data items from the retrieved bank-lines in response to byte addresses of corresponding generated addresses.

11. Apparatus as claimed in claim 1,

wherein each generated multiple address is generated according to the current one of the plurality of modes of operation, a base address, and an index, and

wherein said n address generators includes n different combinational logic circuits, each having as their inputs:

a base address, the current mode of operation, and the index, and each having as an output a generated address in a form of a complete external memory address.

12. A method for supplying multiple, separately addressed data items from a data table in an external memory via a cache apparatus comprising a cache memory that includes n separately addressable memory banks, said method comprising the steps of:

configuring the cache apparatus to operate in any one of a plurality of modes of operation;

generating multiple addresses to retrieve the multiple data items from the memory banks,

wherein each said generated multiple address is generated according to an index and a current one of the plurality of modes of operation; and

positioning the retrieved data items in an output packet in a manner determined by the current mode of operation.

13. A method for supplying multiple, separately addressed data items from a data table in an external memory via a cache apparatus comprising a cache memory that includes n separately addressable memory banks, said method comprising the steps of:

configuring the cache apparatus to operate in any one of a plurality of modes of operation; and

generating multiple addresses to retrieve the multiple data items from the memory banks,

wherein each generated multiple address is generated according to an index and a current one of the plurality of modes of operation, and each generated address includes a tag address and a line address, and

wherein said method further comprises the steps of;

storing tag addresses of corresponding lines of the cache memory in a tag memory;

storing line-valid statuses of corresponding lines of the cache memory in a line-valid memory;

comparing, for each generated multiple address, a tag address of a generated address with a tag address stored in the tag memory corresponding to a line address of the generated address, such that, when there is a match and a line-valid status for that line is also asserted, a hit signal is generated;

controlling simultaneous retrieval from the cache memory of the multiple data items in response to the asserted hit signals, and controlling a fetching of one or more lines containing one or more of the data items from the external memory when associated hit signals are not asserted; and

positioning the retrieved data items in an output packet in a manner determined by the current mode of operation.

14. Method as claimed in claim 13, wherein each generated address includes a tag address and a line address, and

wherein said method further comprises the step of:

comparing the tag address of a generated address with a tag address stored in a tag memory corresponding to a line address of the generated address, wherein only those parts of the tag addresses determined by the current mode of operation are compared.

15. Method as claimed in claim 13, wherein each multiple address is generated in a form of a complete external memory address.

16. Method as claimed in claim 15, wherein each memory bank includes m bank-lines, and each cache-line includes a bank-line from each memory bank.

17. Method as claimed in claim 16,

wherein each complete generated address includes a tag address, a line address, a bank address, and a byte address, and

wherein the tag address included in the complete generated address is compared with a tag address stored in the tag memory, the line address is used for addressing a relevant cache-line in the cache memory, the bank address is used for addressing a relevant bank of the memory banks, and the byte address is used for addressing a relevant byte of the bank-line.

18. Method as claimed in claim 15, 16 or 17, further comprising the step of:

generating an index address in response to the index and the current mode of operation, and the index address is added to a base address to generate a complete external memory address.

19. Method as claimed in claim 13, wherein the cache memory is a direct mapped cache.

20. Method as claimed in claim 16, wherein one or more of the bank-lines are retrieved from the cache memory in response to corresponding generated addresses.

21. Method as claimed in claim 20,

wherein the multiple data items are one byte sized, and

wherein said method further comprises the step of selecting the multiple data items from the retrieved bank-lines in response to byte addresses of corresponding generated addresses.

22. Method as claimed in claim 13, wherein each generated multiple address is in a form of a complete external memory address and is generated according to the current one of the plurality of modes of operation, a base address, and the index.

23. Apparatus for supplying multiple, separately addressed data items from a data table in an external memory, said apparatus comprising:

a controller for configuring said apparatus to operate in any one of a plurality of modes of operation;

a cache memory that includes n separately addressable memories banks organized as m cache-lines, where each memory bank includes m bank-lines, and each cache-line includes a bank-line from each memory bank, and where n and m are both a plurality;

n address generators, each coupled to a corresponding one of the n memory banks, for generating multiple addresses to simultaneously retrieve the multiple data items from the memory banks, wherein each generated multiple address is generated according to an index, and a current one of the plurality of modes of operation, and wherein each generated address includes a tag address, a line address, and a bank address;

a tag memory for storing tag addresses of corresponding cache-lines of said cache memory;

a line-valid memory for storing line-valid statuses of corresponding cache-lines of said cache memory;

n tag comparators, each comparing a tag address of a generated address with a tag address stored in said tag memory corresponding to a live address of the generated address, such that, when there is a match and a line-valid status for that line is also asserted, a hit signal is generated;

a cache controller for controlling retrieval from said cache memory of the data items in response to the asserted hit signals, and for controlling a fetching of one or more lines containing one or more of the data items from the eternal memory when associated hit signals are not asserted; and

a data items organizer for positioning the retrieved data in an output packet in a manner determined by the current mode of operation.

24. Apparatus as claimed in claim 23, wherein each tag comparator compares only those parts of the tag addresses determined by the current mode of operation.

25. Apparatus as claimed in claim 23, wherein each multiple address is generated in a form of a complete external memory address.

26. Apparatus as claimed in claim 25,

wherein each complete generated address includes a tag address, a line address, a bank address, and a byte address; and

wherein the tag address included in the complete generated address is compared with a tag address stored in said tag memory, the line address is used for addressing a relevant cache-line in the cache memory, the bank address is used for addressing a relevant bank of the memory banks, and the byte address is used for addressing a relevant byte of the bank-line.

27. Apparatus as claimed in claim 23, wherein each address generator generates an index address in response to the index and the current mode of operation, and the index address is added to a base address to generate a complete external memory address.

28. Apparatus as claimed in claim 23, wherein said cache memory is a direct mapped cache.

29. Apparatus as claimed in claim 23, wherein one or more of the bank-lines are retrieved from said cache memory in response to corresponding generated addresses.

30. Apparatus as claimed in claim 29, wherein

the multiple data items are one byte sized, and

said data organizer comprises a selector for selecting data items from the retrieved bank-lines in response to byte addresses of corresponding generated addresses.

31. Apparatus as claimed in claim 23, wherein said n address generators include n different combinational logic circuits, each including as their inputs:

a base address, the current mode of operation, and the index, and each including as an output a generated address in a form of a complete external memory address.

32. Apparatus as claimed in claim 23, wherein the current mode of operation is dependent upon the table stored in the external memory.

33. Apparatus for supplying addressed data items from a data table in an external memory, said apparatus comprising:

a controller for configuring said apparatus to operate in any one of a plurality of modes of operation;

a cache;

an address generator, coupled to said cache memory, for generating one or more addresses to retrieve one or more data items from said cache memory, wherein each generated address is generated according to an index and a current one of the plurality of modes of operation; and

a data organizer for positioning the retrieved data items in an output packet, wherein said data organizer positions the retrieved data items in the output packet in a manner determined by the current mode of operation.

34. A method for supplying addressed data items from a data table in external memory via a cache apparatus comprising a cache memory, the method comprising the steps of:

configuring the cache apparatus to operate in any one of a plurality of modes of operation;

generating one or more addresses to retrieve one or more data items from the cache memory, wherein each generated address is generated according to an index and a current one of the plurality of modes of operation; and

positioning the retrieved data items in an output packet in a manner determined by the current mode of operation.