Systems and methods for addressing a cache with split-indexes

• US 9,916,252 B2
• Filed: 05/19/2015
• Issued: 03/13/2018
• Est. Priority Date: 05/19/2015
• Status: Active Grant

• Current Assignee: Movidius Ltd. (Intel Corporation)
• Original Assignee: Linear Algebra Technologies Limited
• Inventors: Richmond, Richard
• Primary Examiner(s): Rossiter, Sean D
• Application Number:
  US14/716,588
• Publication Number:
  US 20160342521A1
• Time in Patent Office: 1,029 Days
• Field of Search: 711122
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0884 Parallel mode, e.g. in parallel with main memory or CPU
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/455 Image or video data

Abstract

Cache memory mapping techniques are presented. A cache may contain an index configuration register. The register may configure the locations of an upper index portion and a lower index portion of a memory address. The portions may be combined to create a combined index. The configurable split-index addressing structure may be used, among other applications, to reduce the rate of cache conflicts occurring between multiple processors decoding the video frame in parallel.

Claims

1. A method for storing elements from a main memory into a cache, the method comprising:

associating respective ones of a plurality of cache lines of a cache memory with different ones of a plurality of indexes;

defining a first set of bits of a first address associated with a first memory location of the main memory as a first index portion and defining a second set of bits of the first address as a second index portion;

generating, with the cache, a first combined index by concatenating the first index portion and the second index portion; and

storing data from at least the first memory location to a first cache line of the plurality of cache lines based on the first combined index.

2. The method of claim 1, further including defining a third set of bits of the first address as an offset, the offset determining a position within the first cache line of the first memory location.

3. The method of claim 2, further including:

defining a fourth set of bits of the first address as a lower tag and a fifth set of bits of the first address as an upper tag; and

generating a combined tag that identifies the first address stored in the first cache line, the combined tag generated by concatenating the lower tag and the upper tag.

4. The method of claim 1, further including storing, within the plurality of cache lines, a plurality of blocks of data from a frame of a high-definition video stored in the main memory.

5. The method of claim 4, wherein the frame of the high-definition video complies with an H.264 video format.

6. The method of claim 4, further including mapping at least two of the plurality of blocks of data from one row of the frame of the high-definition video to one cache line of the plurality of cache lines.

7. The method of claim 1, further including scheduling read and write requests to the cache memory from a first processor and a second processor.

8. The method of claim 7, further including scheduling read and write requests to the cache memory from a third processor.

9. The method of claim 7, further including:

reading, via the first processor, a first block of data located in a first column of the main memory;

reading, via the second processor, a second block of data located in the first column of the main memory; and

simultaneously storing the first block of data and the second block of data into the cache memory.

10. The method of claim 1, further including:

defining a first set of bits of a second address associated with a second memory location of the main memory as a third index portion and defining a second set of bits of the second address as a fourth index portion;

generating a second combined index by concatenating the third index portion and the fourth index portion; and

storing data from at least the second memory location to a second cache line of the plurality of cache lines based on the second combined index.

11. A cache for storing data elements from a main memory, the cache comprising:

a plurality of cache lines referenced by different ones of a plurality of indexes;

an index configuration register to define a first set of bits of a first address associated with a first memory location of the main memory as a first index portion and to define a second set of bits of the first address as a second index portion;

an index generation module to receive the first index portion and the second index portion as defined by the index configuration register, and to generate a first combined index by concatenating the first index portion and the second index portion; and

a memory address mapping module to map at least the first memory location to a first cache line of the plurality of cache lines based on the first combined index.

12. The cache of claim 11, wherein the index configuration register is further to define a third set of bits of the first address as an offset, wherein the offset to determine a position within the first cache line of the first memory location.

13. The cache of claim 12, wherein the index configuration register is further to define a fourth set of bits of the first address as a lower tag and a fifth set of bits of the first address as an upper tag, and to generate a combined tag that identifies the first address stored in the first cache line, the index configuration register to generate the combined tag by concatenating the lower tag and the upper tag.

14. The cache of claim 11, wherein the plurality of cache lines is to store a plurality of blocks of data from a frame of a high-definition video stored in the main memory.

15. The cache of claim 14, wherein the frame of the high-definition video complies with an H.264 video format.

16. The cache of claim 14, wherein the memory address mapping module is further to map at least two of the plurality of blocks of data from one row of the frame of the high-definition video to one cache line of the plurality of cache lines.

17. The cache of claim 11, further including an access arbitration module configured to schedule read and write requests to the cache from a first processor and a second processor.

18. The cache of claim 17, wherein the access arbitration module is further to permit simultaneous read and write requests to different cache lines from the plurality of cache lines by the first processor and the second processor.

19. The cache of claim 11, wherein:

the index configuration register is further to define a first set of bits of a second address associated with a second memory location from the main memory as a third index portion and a second set of bits of the second address as a fourth index portion;

the index generation module is further to receive the third index portion and the fourth index portion, and to generate a second combined index by concatenating the third index portion and the fourth index portion; and

the memory address mapping module is further to map at least the second memory location to a second cache line of the plurality of cache lines based on the second combined index.

20. A non-transitory computer readable storage medium comprising computer executable instructions that, when executed by a computer system, cause the computer system to at least:

associate respective ones of a plurality of cache lines of a cache with different ones of a plurality of indexes;

define a first set of bits of a first address associated with a first memory location of a main memory as a first index portion and define a second set of bits of the first address as a second index portion;

generate a the first combined index by concatenating the first index portion and the second index portion; and

store data from at least the first memory location to a first cache line of the plurality of cache lines based on the first combined index.

21. The computer readable storage medium of claim 20, wherein the instructions, when executed, further cause the computer system to define a third set of bits of the first address as an offset, the offset to determine a position within the first cache line of the first memory location.

22. The computer readable storage medium of claim 21, wherein the instructions, when executed, further cause the computer system to:

define a fourth set of bits of the first address as a lower tag and a fifth set of bits of the first address as an upper tag; and

generate a combined tag that identifies the first address stored in the first cache line, the combined tag to be generated by concatenating the lower tag and the upper tag.

23. The computer readable storage medium of claim 20, wherein the instructions, when executed, further cause the computer system to:

store, within the plurality of cache lines, a plurality of blocks of data from a frame of a high-definition video stored in the main memory; and

map at least two of the plurality of blocks of data from one row of the frame of the high-definition video to one cache line of the plurality of cache lines.

24. The computer readable storage medium of claim 20, wherein the instructions, when executed, further cause the computer system to:

schedule read and write requests to the cache memory from a first processor and a second processor; and

simultaneously store a first block of data read via the processor and a second block of data read via the second processor into the cache memory, the first block of data located in a first column of the main memory, the second block of data located in the first column of the main memory.

25. The computer readable storage medium of claim 20, wherein the instructions, when executed, further cause the computer system to:

define a first set of bits of a second address associated with a second memory location of the main memory as a third index portion and define a second set of bits of the second address as a fourth index portion;

generate a second combined index by concatenating the third index portion and the fourth index portion; and

store data from at least the second memory location to a second cache line of the plurality of cache lines based on the second combined index.