Dynamic hierarchial associative memory

• US 5,341,483 A
• Filed: 05/31/1990
• Issued: 08/23/1994
• Est. Priority Date: 12/22/1987
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Kendall Square Research Corp.
• Inventors: Frank, Steven J., Binder, Paul A.
• Primary Examiner(s): RUDOLPH, REBECCA
• Application Number:
  US07/531,506
• Time in Patent Office: 1,545 Days
• Field of Search: 395/400, 395/425
• US Class Current: 711/206
• CPC Class Codes: G06F 11/004 Error avoidance G06F11/07 and subgroups take precedence
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0772 Means for error signaling, e.g. using interrupts, exception flags, dedicated error registers
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 2212/272 Cache only memory architecture [COMA]
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3865 using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 12/4637 Interconnected ring systems
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

An associative memory having an associativity of 2^q, where (q) is an integer greater than or equal to one, is provided for storing information relating to data. The memory includes (n) tables, each having a plurality of entries for storing signals associated with data descriptors having a common set portion and common other portions. The entries of table (k), where (k) represents successive integers between (1) and (n-1), store pointers to respective entries of table (k+1). The entries of table (1) are arranged for access as a function of the common set portion and the common portion (1) with which they are respectively associated. The entries of the other tables are arranged for access as a function of (i) a value of the common set portion, (ii) a value of a pointer-respresentative signal of the respective table (m-1) entry means, and (iii) the value of the common portion(m) with which such table(m) entry means is respectively associated. The entries of table(n) store information relating to one or more data having a common portion(n).

Claims

1. An associative memory for information-representative signals representative of information relating to a plurality of descriptors, each descriptor including a set portion and (n) other portions, where (n) is an integer greater than or equal to two, said associative memory having an associativity of two to the (q)th power, where (q) is an integer greater than or equal to one, said associative memory comprising

A. input means for receiving a candidate descriptor,

B. directory means for storing and accessing said information-representative signals, said directory means including:

i. (n) table means including table means(n) for storing said information-representative signals and table means (j), where (j) where (j) represents successive integers between (1) and (n-1), inclusive, for storing pointer-representative signals, and

ii. each said table means (j) including a plurality of entry means, each for storing a (q)-bit pointer-representative signal directed to at least one respective entry means of table means (j+1), said table means (n) including a plurality of entry means, each for storing an information-representative signal relating to at least one said descriptor,

iii. each said entry means of table means (1) being accessible as a function of a common set portion and a common portion (1) of a plurality of descriptors with which that entry means is respectively associated, said table means (1) including memory means responsive to values of a common set portion and a common portion (1) of a candidate descriptor for accessing the entry means of table means (1) respectively associated with that candidate descriptor and for generating a pointer signal representative of the pointer stored therein,

iv. each said entry means of table means (m), where (m) represents successive integers between (2) and (n), being accessible as a function of values of a common set and a common portion (m) of a plurality of descriptors with which such table means (m) entry means is respectively associated, and a value of a pointer signal of the respective table means (m-1) entry means with which such table means (m) entry means is respectively associated, each said table means (m) including memory means responsive to values of a common set and a common portion (m) of candidate descriptors with which such table means (m) entry means is respectively associated, as well as to a value of a pointer signal of the respective table means (m-1) entry means with which such table means (m) entry means is respectively associated, for accessing the entry means of table means (m) respectively associated with that candidate descriptor and for generating a signal representative of the information stored therein,

C. look-up means connected to said input means and to said directory means for determining whether said directory means stores an information-representative signal relating to said candidate descriptor, and for generating a signal representative of that determination, and

D. update means, coupled to said input means and to said look-up means and to said directory means, selectively responsive to a determination that an information-representative signal relating to said candidate descriptor is not stored in said directory means for updating at least one of said (n) table means to include a signal representative of said candidate descriptor.

2. An associative memory according to claim 1, wherein said directory means includes means for accessing an information-representative signal, if any, relating to said candidate descriptor in a time period that is dependent upon (n), and that is independent of (q), and that is independent of the value of any portion of that candidate descriptor.

3. An associative memory according to claim 2, wherein

A. the memory means of table means (1) comprises a memory element including

i) address input means for receiving signals representative of values of a set portion and a portion (1) of said candidate descriptor,

ii) means responsive to that input signal for generating a signal representative of the pointer stored in the entry means of table means (1) entry means corresponding to those values,

i) row-address input coupled to output means of table means (t-1) for receiving a pointer-representative signal output thereby,

ii) a column-address input for receiving a signal representative of the value of a set portion and a portion(t) of said candidate descriptor,

iii) means responsive to said signals received by said row-address input and said column-address input for generating an information-representative signal stored in the table means(t) entry means corresponding to the value represented thereby,

iv) means for outputting that information-representative signal.

4. An associative memory according to any of claims 1 or 3, wherein

A. said look-up means includes means responsive to a determination that said table means(n) stores an information-representative signal relating to said candidate descriptor for accessing that information-representative signal, and

B. means for generating a signal representative of said accessed information-representative signal.

5. An associative memory according to any of claims 1 or 3, wherein at least one said table means (n) entry means comprises means for storing a sub-data signal representative of information relating to one or more descriptors having a common portion (n+1), if any, said sub-data signals being arranged for access as a function of

i) the value of said set portion,

ii) the value of the pointer-representative signal of the respective table means (n-1) entry means corresponding to that table means (n) entry means,

iii) the value of the common (n) portion with which that table means (n) entry means is associated, and

iv) the value of the common (n+1) portion, if any, with which that sub-data signal is associated.

6. An associative memory according to any of claims 1 or 3, wherein said look-up means includes means for determining whether table means (j), where (j) represents at least one integer between one and (n), includes an entry means associated with respective portions of said candidate descriptor.

7. An associative memory according to claim 6, wherein said look-up means includes means responsive to a determination that table means (k), where (k) represents at least one integer between one and (n-1), includes an entry means associated with a common set portion and with common other portions (p) of said candidate descriptor, where (p) represents successive integers between 1 and (k), inclusive, for generating a signal representative of the pointer-representative signal stored in that entry means.

8. An associative memory according to claim 6, wherein said look-up means includes means responsive to a determination that means (k), where (k) represents at least one integer between one and (n-1), does not include an entry means associated with a common set portion and with common other portions (p) of said candidate descriptor, where (p) represents successive integers between 1 and (k), inclusive, for generating a level (k) miss signal indicative of such determination.

9. An associative memory according to claim 8, wherein said directory means includes update means responsive to said level (k) miss signal for updating at least one of said (n) table means entry means to include an information-representative signal relating to said candidate descriptor.

10. An associative memory according to claim 9, comprising

A. free list means comprising physical storage space,

B. said update means including means responsive to said level (k) miss signal for allocating in said free list means physical storage space for one or more entry means for table means (k), where (k) represents at least one integer between 2 and (n), and

C. said update means further including means for generating signal representative of a pointer to that allocated physical storage space and storing that pointer-representative signal in a corresponding entry means of table means (k-1).

11. An associative memory according to claim 10, including deallocate means selectively responsive to a deallocated signal for deallocating an entry means of table means (k), where (k) represents a least one integer between 2 and (n).

12. An associative memory according to any of claims 1 or 3, wherein (n) is 3.

13. An associative memory according to claim 12 wherein each said descriptor includes a set portion, a first tag portion, a second tag portion, and a page portion, each said portion being an information signal representing a value, said (n) table means including:

A. an L1 table means including a plurality of L1 entry means for storing digital signals representative of pointers to respective L2 rentry means, said L1 entry means being associated with one or more of said descriptors having common set and first tag portions, said L1 entry means being arranged for access as a function of the values of those common set and first tag portions,

B. an L2 table means including a plurality of L2 entry means for storing digital signals representative of pointers to respective L3 entry means, said L2 entry means being associated with one or more of said descriptors having common set and second tag portions, each said L2 entry means being arranged for access as a function of

i) value of a pointer-representative signal of the respective L1 entry means,

ii) the value of the common set and second tag portions with which that L2 entry means is associated, and

C. an L3 table mans including a plurality of L3 entry means for storing signals representative of information relating to said one or more descriptors that have a common set and page portions, each said L3 entry means being arranged for access as a function of

i. a value of a pointer-representative signal of the respective L2 entry means, and

ii) the value of the common set and page portions with which that L2 entry means is associated.

14. An associative memory according to claim 13, wherein at least one said L3 entry means comprises means for storing a subpage signal representative of information relating to one or more descriptors that have common subpage portions, said subpage signals being arranged for access as a function of

i) the value of the pointer-representative signal of the respective L2 entry means of that L3 entry means,

ii) the value of the common set and page portions with which that L3 means is associated, and

iii) the value of the common subpage portion with which that subpage signal is associated.

15. An associative memory according to claim 13, wherein said look-up means includes means for determining whether said L1 table means includes an L1 entry that corresponds to the set and first tag portions of said candidate descriptor and that includes a valid L2 pointer.

16. An associative memory according to claim 15, wherein said look-up means includes means responsive to a determination that said L1 table means includes an L1 entry means that corresponds to the set and first tag portions of said candidate descriptor that and that includes a valid entry pointer for generating a signal representative of that pointer.

17. An associative memory according to claim 16, wherein said look-up means includes means responsive to said L2 pointer-representative signal for determining whether said L2 table means includes an L2 entry corresponding to the set and second tag portions of said candidate descriptor.

18. An associative memory according to claim 17, wherein said look-up means includes means responsive to a determination that said L2 table means includes an L2 entry means corresponding to the set and second tag portions of said candidate descriptor for generating a signal representative of the L3 pointer stored in that entry means.

19. An associative memory according to claim 17, wherein said look-up means includes means responsive to a determination that said L2 table means does not include an L2 entry means corresponding an L2 miss signal.

20. An associative memory according to claim 19, including

A. means for allocating in said L3 table means an L3 means corresponding to said set and page portions of said candidate descriptor, and for storing in said L2 entry means corresponding to the set and second tag portion of said candidate descriptor a signal representative of a pointer to that L3 entry means, and

B. means for in said L3 entry means corresponding to said set and page portion said candidate descriptor at least default information relating to that descriptor.

21. An associative memory according to claim 17, wherein said look-up means includes means responsive to said L3 pointer-representative signal for identifying in said L3 table means an L3 entry means corresponding to said portion of said candidate descriptor, and for generating of said information stored in that entry means.

22. An associative memory according to claim 15, wherein said look-up means includes means responsive to a determination that said L1 table means does not include an L1 entry means corresponding to the set and first tag portions of said candidate descriptor and including a valid L2 entry pointer for generating an L1 miss signal.

23. An associative memory according to claim 22, comprising

A. free list means comprising physical storage space,

B. said directory means includes update means responsive to said L1 miss signals for updating said directory means, said update means including

i) means for selectively allocating in said free list means physical storage space for an L2 entry means corresponding to the set and second tag portions of said candidate descriptor, and for storing in the L1 entry means corresponding to the set and first tag portions of said candidate descriptor a signal representative of a pointer to that L2 entry means,

ii) means for selectively allocating in said free list means physical storage space for an L3 entry means corresponding to said set and page portions of said candidate descriptor, and for storing in the L2 entry means corresponding to the set and second tag portions of said candidate descriptor a signal representative of a pointer to that L3 entry means, and

iii) means for storing in said L3 entry means corresponding to said set and page portions of said candidate descriptor information relating to that descriptor.

24. An associative memory according to claim 23, including deallocate means selectively responsive to a deallocate signal for deallocate signal for deallocating an entry means of at least one of said L2 table means and said L3 table means.

30. A method according to any claims 2 or 27, comprising determining whether table (j), where (j) represents at least one integer between one and (n), includes an entry associated with respective portions of said candidate descriptor.

31. A method according to claim 30, comprising responding to a determination that table (k), where (k) represents at least one integer between one and (n-1), includes an entry associated with a common set portion and with common other portions (p) of said candidate descriptor, where (p) represents successive integers between 1 and (k), inclusive, for generating a signal representative of the pointer-representative signal stored in that entry.

32. A method according to claim 30, comprising responding to a determination that table (k), where (k) represents at least one integer between one and (n-1), does not include an entry associated with a common set portion and with common other portions (p) of said candidate descriptor, where (p) represents successive integers between 1 and (k), inclusive, for generating a level (k) miss signal indicative of such determination.

33. A method according to claim 32, comprising responding to said level (k) miss signal for updating at least one of said (n) tables entries to include an information-representative signal relating to said candidate descriptor.

34. A method according to claim 33, comprising

A. providing free list means comprising physical storage space,

B. responding to said level (k) miss signal for allocating in said free list means physical storage space for one or more entries for table (k), where (k) represents at least one integer between 2 and (n), and

C. generating a signal representative of a pointer to that allocated physical storage space and storing that pointer-representative signal in a corresponding entry of table (k-1).

35. A method according to claim 34 including responding to a deallocate signal for deallocating an entry of table (k), where (k) represents at least one integer between 2 and (n)

25. A method for storing and accessing information-representative signals representative of information relating to a plurality of descriptors, each descriptor including a set portion and (n) other portions, where (n) is an integer greater than or equal to two, said associative memory having an associativity of two to the (q)th power, where (q) is an integer greater than or equal to one, the method comprising

A. inputting a candidate descriptor,

B. providing a directory for storing and accessing said information-representative signals, said directory including:

i) (n) tables, including table (n) for storing said information-representative signals and tables (j), where (j) represents successive integers between (1) and (n-1), inclusive, for storing pointer-representative signals, and

ii) each said table (j) including a plurality of entries, each for storing a (q) bit pointer-representative signal directed to at least one respective entry of table (j+1), said table (n) including a plurality of entries, each for storing an information-representative signal relating to at least one said descriptor,

iii) each said entry of table (1) being accessible as a function of a common set portion and a common portion (1) of a plurality of descriptors with which that entry is respectively associated, said table means (1) including memory means responsive to values of a common set portion and a common portion (1) of a candidate descriptor for accessing the entry means of table means (1) respectively associated with that candidate descriptor and for generating a pointer signal representative of the pointer stored therein,

iv) each said entry of table (m), where (m) represents successive integers between (2) and (n), being accessible as a function of values of a common set and a common portion (m) of a plurality of descriptors with which such table (m) entry is respectively associated, and a value of a pointer signal of the respective table (m-1) entry with which such table (m) entry is respectively associated, each said table means (m) including memory means responsive to values of a common set and a common portion (m) of candidate descriptors with which such table means (m) entry means is respectively associated, as well as to a value of a pointer signal of the respective table means (m-1) entry means with which such table means (m) entry means is respectively associated, for accessing the entry means of table means (m) respectively associated with that candidate descriptor and for generating a signal representative of the information stored therein,

C. determining whether said director stores an information-representative signal relating to said candidate descriptor, and generating a signal representative of that determination, and

D. responding to a determination that an information-representative signal relating to said candidate descriptor is not stored in said directory for updating at least one said (n) tables to include a signal representative of said candidate descriptor.

26. A method according to claim 25, comprising accessing an information-representative signal, if any, relating to said candidate descriptor in a timer period that is dependent upon (n), and that is independent of (q), and that is independent of the value of any of said portions of that candidate descriptor.

27. A method according to claim 26, comprising

A. providing, as the memory means of table (1), a memory element including

i) address input means for receiving signals representative of values of a set portion and a portion (1) of a candidate descriptor,

ii) means responsive to that input signal for generating a signal representative of the pointer stored in the entry of table (1) entry corresponding to those values,

iii) means for outputting that pointer representative signal,

B. providing, as the memory means of each said table (t), for (t) representing successive integers between (2) and (n), a memory element including

i) a row-address input coupled to output means of table (t-1) for receiving a pointer-representative signal output thereby,

ii) a column-address input for receiving a signal representative of the value of a set portion and a portion (t) of said candidate descriptor,

iii) means responsive to said signals received by said row-address input and said column-address input for generating an information-representative signal stored in the table (t) entry corresponding to the value represented thereby,

iv) means for outputting that information-representative signal.

28. A method according to any of claims 25 or 27, comprising

A. responding to a determination that said table (n) stores an information-representative signal relating to said candidate descriptor for accessing that information-representative signal, and

B. generating a signal representative of that accessed information-representative signal.

29. A method according to any of claims 25 or 27, comprising

A. selectively storing in at least one of said table (n) entries a sub-data signal representative of information relating to one or more descriptors having a common portion (n+1), if any, and

B. arranging said sub-data signals for access as a function of

i) the value of said set portion,

ii) the value of the pointer-representative signal of the respective table (n-1) entry corresponding to that table (n) entry,

iii) the value of the common (n) portion with which that table (n) entry is associated, and

iv) the value of the common (n+1) portion, if any, with which that sub-data signal is associated.

36. A method according to any of claims 25 or 27, wherein (n) is 3.

37. A method according to claim 36, wherein each said descriptor includes a set portion, a first tag portion, a second tag portion, and a page portion ,each said portion being a information signal representing a value, comprising

A.

providing an L1 table including a plurality of L1 entries for storing digital signals representative of pointers to respective L2 entries, said L1 entry being associated with one or more of said descriptors having common set and first tag portions,

arranging said L1 entries for access as function of the values of those common set and first tag portions,

B.

providing an L2 table including a plurality of L2 entries for storing digital signals representative of pointers to respective L3 entries, said L2 entry being associated with one or more of said descriptors having common set and second tag portions,

arranging said L2 entries for access as a function of

i) a value of a pointer-representative signal of the respective L1 entry,

ii) the value of the common set and second tag portions with which that L2 entry is associated, and

C. providing an L3 table including a plurality of L3 entries for storing signals representative of information relating to said one or more descriptors that have a common set and page portions, each said L3 entry being arranged for access as a function of

i) a value of a pointer-representative signal of the respective L2 entry, and

ii) the value of the common set and page portions with which that L2 entry is associated.

38. A method according to claim 37, comprising

A. Storing in at least one said L3 entries a subpage signal representative of information relating to one or more descriptors that have common subpage portions,

B. arranging said subpage signals for access as a function of

i) the value of the pointer-representative signal of the respective L2 entry of that L3 entry,

ii) the value of the common set and page portions with which that L3 means is associated, and

iii) the value of the common subpage portion with which that subpage signal is associated.

39. A method according to claim 37 comprising determining whether said L1 table includes an L1 entry that corresponds to the set and first tag portions of said candidate descriptor and that includes a valid L2 pointer.

40. A method according to claim 39, comprising responding to a determination that said L1 table includes an L1 entry that corresponds to the set and first tag portions of said candidate descriptor that and that includes a valid entry pointer for generating a signal representative of that pointer.

41. A method according to claim 40, comprising responding to said L2 pointer-representative signal for determining whether said L2 table includes an L2 entry corresponding to the set and second tag portions of said candidate descriptor.

42. A method according to claim 41, comprising responding to a determination that said L2 table includes an L2 entry corresponding to the set and second tag portions of said candidate descriptor for generating a signal representative of the L3 pointer stored in that entry.

43. A method according to claim 41, comprising responding to a determination that said L2 table does not include an L2 entry corresponding to the set and second tag portions of said candidate descriptor for generating an L2 miss signal.

44. A method according to claim 43, comprising

A. allocating in said L3 table an L3 entry corresponding to said set and page portions of said candidate descriptor, and for storing in said L2 entry corresponding to the set and second tag portion of said candidate descriptor a signal representative of a pointer to that L3 entry, and

B. storing in said L3 entry corresponding to said set and page portion of said candidate descriptor at least default information relating to that descriptor.

45. A method according to claim 41, comprising responding to said L3 pointer-representative signal for identifying in said L3 table an L3 entry corresponding to said portion of said candidate descriptor, and for generating of said information stored in that entry.

46. A method according to claim 39, comprising responding to a determination that said L1 table does not include an L1 entry corresponding to the set and first tag portions of said candidate descriptor and including a valid L2 entry pointer for generating an L1 miss signal.

47. A method according to claim 46, comprising

A. providing free list means comprising physical storage space,

B. responding to said L1 miss signal for updating said director, said responding step including

i) selectively allocating in said free list means physical storage space for an L2 entry corresponding to the set and second tag portions of said candidate descriptor, and for storing in the L1 entry corresponding to the set and first tag portions of said candidate descriptor a signal representative of a pointer to that L2 entry,

ii) selectively allocating in said free list means physical storage space for an L3 entry corresponding to said set and page portions of said candidate descriptor, and for storing in the L2 entry corresponding to the set and second tag portions of said candidate descriptor a signal representative of a pointer to that L3 entry, and

iii) storing in said L3 entry corresponding to said set and page portions of said candidate descriptor information relating to that descriptor.

48. A method according to claim 47, selectively responding to a deallocate signal for deallocating an entry of at least one of said L2 table and said L3 table.