Locked content addressable memory for efficient access

• US 20030131204A1
• Filed: 01/09/2002
• Published: 07/10/2003
• Est. Priority Date: 01/09/2002
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Lin, Chang-Ming P., Zhu, Julianne
• Granted Patent: US 6,779,089 B2
• Time in Patent Office: Days
• US Class Current: 711/152
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A storage element stores entries corresponding to threads. Each of the threads has a request identifier and generates an access request to a memory for a memory usage of a memory block. Each of the threads corresponds to a fixed entry occupied at a predetermined location. A controller controls access to the memory. The access includes a lock phase before the memory usage and an unlock phase after the memory usage.

Claims

1. An apparatus comprising:

a storage element to store entries corresponding to threads, each of the threads having a request identifier and generating an access request to a memory for a memory usage of a memory block, each of the threads corresponding to a fixed entry occupied at a predetermined location; and

a controller coupled to the storage element to control access to the memory, the access including a lock phase before the memory usage and an unlock phase after the memory usage.

2. The apparatus of claim 1 wherein each of the entries includes an owner ID field containing an owner identifier that corresponds to a thread currently having the memory usage, a tail identifier field containing a tail identifier that corresponds to a last thread in a thread queue, and a next identifier field containing a next identifier that corresponds to a next thread requesting the memory usage.

3. The apparatus of claim 2 wherein each of the entries further includes a valid field containing an indicator that indicates if the corresponding identifiers are valid and a tag field containing a memory address of the access request.

4. The apparatus of claim 3 wherein the controller comprises:

a read circuit to read one of the entries according to a result of the access request in a first cycle; and

a write circuit to update one of the entries according to the result in one of the first cycle and a second cycle.

5. The apparatus of claim 4 wherein the read circuit reads at least one of the owner identifier, the tail identifier, and the next identifier when the result indicates a hit.

6. The apparatus of claim 5 wherein during the second cycle of the lock phase, the write circuit writes the memory address to the tag field, a valid indicator to the valid field, and the read tail identifier to the tail identifier field at a location in the storage element corresponding to the request identifier when the result indicates a miss.

7. The apparatus of claim 4 wherein during the second cycle of the lock phase, the write circuit writes the request identifier to the tail identifier field at a location of the storage element corresponding to the read owner identifier when the result indicates a hit.

8. The apparatus of claim 4 wherein during the second cycle of the lock phase, the write circuit writes the request identifier to the next identifier field at a location of the storage element corresponding to the read tail identifier.

9. The apparatus of claim 4 wherein during the first cycle of the unlock phase, the write circuit writes an invalid indicator to the valid field if the result indicates a hit.

10. The apparatus of claim 4 wherein during the second cycle of the unlock phase, the write circuit writes a valid indicator to the valid field if the result indicates a hit and if the read owner identifier is different than the read tail identifier.

11. The apparatus of claim 4 wherein during the second cycle of the unlock phase, the write circuit writes the read tail identifier to the tail identifier field and the memory address to the tag field at a location in the storage element corresponding to the read next identifier.

12. The apparatus of claim 4 wherein the storage element comprises:

a first content addressable memory (CAM) to store the entries containing the tag field, the valid field, the owner identifier field, and the tail identifier field, the first CAM having a first read decoder to decode a read address and a first write decoder to decode a first write address; and

a second CAM to store the entries containing the next identifier field, the second CAM having a second read decoder to decode the read address as the first read decoder and a second write decoder to decode a second write address.

13. The apparatus of claim 12 wherein the write circuit comprises:

a first address selector to select write address for the first write decoder;

a tag register to store the memory address to write to the tag field;

a valid selector to select an indicator to write to the valid field; and

a tail identifier selector to select an identifier to write to the tail identifier field.

14. The apparatus of claim 13 wherein the write circuit further comprises:

a second address selector to select write address of the second write decoder; and

a next identifier selector to select an identifier to write to the next identifier field.

15. The apparatus of claim 13 wherein the first address selector selects the request identifier when the result indicates a miss.

16. The apparatus of claim 13 wherein the first address selector selects the read next identifier when the result indicates a hit in the unlock phase.

17. The apparatus of claim 13 wherein the first address selector selects the read owner identifier when the result indicates a hit in the lock phase.

18. The apparatus of claim 13 wherein the tail identifier selector selects the read tail identifier when the result indicates a hit in the unlock phase.

19. The apparatus of claim 13 wherein the tail identifier selector selects the request identifier when the result indicates a hit in the lock phase.

20. The apparatus of claim 14 wherein the second address selector selects the read tail identifier and the next identifier selector selects the request identifier when the result indicates a hit in the lock phase.

21. A method comprising:

storing entries corresponding to threads in a storage element, each of the threads having a request identifier and generating an access request to a memory for a memory usage of a memory block, each of the threads corresponding to a fixed entry occupied at a predetermined location; and

controlling access to the memory, the access including a lock phase before the memory usage and an unlock phase after the memory usage.

22. The method of claim 21 wherein each of the entries includes an owner ID field containing an owner identifier that corresponds to a thread currently having the memory usage, a tail identifier field containing a tail identifier that corresponds to a last thread in a thread queue, and a next identifier field containing a next identifier that corresponds to a next thread requesting the memory usage.

23. The method of claim 22 wherein each of the entries further includes a valid field containing an indicator that indicates if the corresponding identifiers are valid and a tag field containing a memory address of the access request.

24. The method of claim 23 wherein controlling access to the memory comprises:

reading one of the entries according to a result of the access request in a first cycle; and

updating one of the entries according to the result in one of the first cycle and a second cycle.

25. The method of claim 24 wherein reading one of the entries comprises reading at least one of the owner identifier, the tail identifier, and the next identifier when the result indicates a hit.

26. The method of claim 25 wherein updating one of the entries comprises during the second cycle of the lock phase, writing the memory address to the tag field, a valid indicator to the valid field, and the read tail identifier to the tail identifier field at a location in the storage element corresponding to the request identifier when the result indicates a miss.

27. The method of claim 24 wherein updating one of the entries comprises during the second cycle of the lock phase, writing the request identifier to the tail identifier field at a location of the storage element corresponding to the read owner identifier when the result indicates a hit.

28. The method of claim 24 wherein updating one of the entries comprises during the second cycle of the lock phase, writing the request identifier to the next identifier field at a location of the storage element corresponding to the read tail identifier.

29. The method of claim 24 wherein updating one of the entries comprises during the first cycle of the unlock phase, writing an invalid indicator to the valid field if the result indicates a hit.

30. The method of claim 24 wherein updating one of the entries comprises during the second cycle of the unlock phase, writing a valid indicator to the valid field at a location in the storage element corresponding to the read next identifier if the result indicates a hit and if the read owner identifier is different than the read tail identifier.

31. The method of claim 24 wherein updating one of the entries comprises during the second cycle of the unlock phase, writing the read tail identifier to the tail identifier field and the memory address to the tag field at a location in the storage element corresponding to the read next identifier.

32. The method of claim 24 wherein storing entries comprises:

storing the entries containing the tag field, the valid field, the owner identifier field, and the tail identifier field in a first content addressable memory (CAM), the first CAM having a first read decoder to decode a read address and a first write decoder to decode a first write address; and

storing the entries containing the next identifier field in a second CAM, the second CAM having a second read decoder to decode the read address as the first read decoder and a second write decoder to decode a second write address.

33. The method of claim 32 wherein updating one of the entries comprises:

selecting write address for the first write decoder;

storing the memory address to write to the tag field;

selecting an indicator to write to the valid field; and

selecting an identifier to write to the tail identifier field.

34. The method of claim 33 wherein updating one of the entries further comprises:

selecting write address of the second write decoder; and

selecting an identifier to write to the next identifier field.

35. The method of claim 33 wherein selecting write address for the first write decoder comprises selecting the request identifier when the result indicates a miss.

36. The method of claim 33 wherein selecting write address for the first write decoder comprises selecting the read next identifier when the result indicates a hit in the unlock phase.

37. The method of claim 33 wherein selecting write address for the first write decoder comprises selecting the read owner identifier when the result indicates a hit in the lock phase.

38. The method of claim 33 wherein selecting an identifier comprises selecting the read tail identifier when the result indicates a hit in the unlock phase.

39. The method of claim 33 wherein selecting an identifier comprises selecting the request identifier when the result indicates a hit in the lock phase.

40. The method of claim 34 wherein selecting write address of the second write decoder comprises selecting the read tail identifier and the next identifier selector selects the request identifier when the result indicates a hit in the lock phase.

41. A system comprising:

a memory; and

a processor coupled to the memory, the processor having a memory controller to process access requests to the memory generated by threads, the memory controller comprising;

a storage element to store entries corresponding to the threads, each of the threads having a request identifier and generating an access request to the memory for a memory usage, each of the entries including an owner identifier field corresponding to a predetermined owner identifier that identifies an owner thread currently using the memory; and

a controller coupled to the storage element to control access to the memory, the access including a lock phase before the memory usage and an unlock phase after the memory usage.

42. The system of claim 41 wherein each of the entries includes an owner ID field containing an owner identifier that corresponds to a thread currently having the memory usage, a tail identifier field containing a tail identifier that corresponds to a last thread in a thread queue, and a next identifier field containing a next identifier that corresponds to a next thread requesting the memory usage.

43. The system of claim 42 wherein each of the entries further includes a valid field containing an indicator that indicates if the corresponding identifiers are valid and a tag field containing a memory address of the access request.

44. The system of claim 43 wherein the controller comprises:

a read circuit to read one of the entries according to a result of the access request in a first cycle; and

a write circuit to update one of the entries according to the result in one of the first cycle and a second cycle.

45. The system of claim 44 wherein the read circuit reads at least one of the owner identifier, the tail identifier, and the next identifier when the result indicates a hit.

46. The system of claim 45 wherein during the second cycle of the lock phase, the write circuit writes the memory address to the tag field, a valid indicator to the valid field, and the read tail identifier to the tail identifier field at a location in the storage element corresponding to the request identifier when the result indicates a miss.

47. The system of claim 44 wherein during the second cycle of the lock phase, the write circuit writes the request identifier to the tail identifier field at a location of the storage element corresponding to the read owner identifier when the result indicates a hit.

48. The system of claim 44 wherein during the second cycle of the lock phase, the write circuit writes the request identifier to the next identifier field at a location of the storage element corresponding to the read tail identifier.

49. The system of claim 44 wherein during the first cycle of the unlock phase, the write circuit writes an invalid indicator to the valid field if the result indicates a hit.

50. The system of claim 44 wherein during the second cycle of the unlock phase, the write circuit writes a valid indicator to the valid field if the result indicates a hit and if the read owner identifier is different than the read tail identifier.

51. The system of claim 44 wherein during the second cycle of the unlock phase, the write circuit writes the read tail identifier to the tail identifier field and the memory address to the tag field at a location in the storage element corresponding to the read next identifier.

52. The system of claim 44 wherein the storage element comprises:

a first content addressable memory (CAM) to store the entries containing the tag field, the valid field, the owner identifier field, and the tail identifier field, the first CAM having a first read decoder to decode a read address and a first write decoder to decode a first write address; and

a second CAM to store the entries containing the next identifier field, the second CAM having a second read decoder to decode the read address as the first read decoder and a second write decoder to decode a second write address.

53. The system of claim 52 wherein the write circuit comprises:

a first address selector to select write address for the first write decoder;

a tag register to store the memory address to write to the tag field;

a valid selector to select an indicator to write to the valid field; and

a tail identifier selector to select an identifier to write to the tail identifier field.

54. The system of claim 53 wherein the write circuit further comprises:

a second address selector to select write address of the second write decoder; and

a next identifier selector to select an identifier to write to the next identifier field.

55. The system of claim 53 wherein the first address selector selects the request identifier when the result indicates a miss.

56. The system of claim 53 wherein the first address selector selects the read next identifier when the result indicates a hit in the unlock phase.

57. The system of claim 53 wherein the first address selector selects the read owner identifier when the result indicates a hit in the lock phase.

58. The system of claim 53 wherein the tail identifier selector selects the read tail identifier when the result indicates a hit in the unlock phase.

59. The system of claim 53 wherein the tail identifier selector selects the request identifier when the result indicates a hit in the lock phase.

60. The system of claim 54 wherein the second address selector selects the read tail identifier and the next identifier selector selects the request identifier when the result indicates a hit in the lock phase.