Shared memory multiprocessor with data hiding and post-store

• US 5,251,308 A
• Filed: 06/22/1989
• Issued: 10/05/1993
• Est. Priority Date: 12/22/1987
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Kendall Square Research Corp.
• Inventors: Steven J. Frank, Dudek, Glen, Kittlitz, Edward N., Shelley, Ruth, Mann, William F., Margulies, Benson I., Weber, Frederick D., Burkhardt, Henry III, Lee, Linda Q., Rothnie, James B.
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): Rudolph, Rebecca L.
• Application Number:
  US07/370,287
• Time in Patent Office: 1,566 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/400, 395/425
• US Class Current: 711/163
• 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/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/50 Allocation of resources, e.g. of the central processing unit [CPU]
• 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/4637 Interconnected ring systems
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A digital data processing system includes a plurality of central processor units which share and access a common memory through a memory management element. The memory management element permits, inter alia, data in the common memory to be accessed in at least two modes. In the first mode, all central processing units requesting access to a given datum residing in memory are signalled of the datum'"'"'s existence. In the second mode, only selected central processing units requesting access to a resident datum are notified that it exists, while others requesting access to the datum are signalled that it does not exist. The common memory can include a plurality of independent memory elements, each coupled to and associated with, a respective one of the central processing units. A central processing unit can include a post-store element for effecting the transfer of copies of data stored in its associated memory element to a memory element associated with another central processing unit.

Claims

1. A digital data processing system comprising

A. plural processing cells, each comprising a central processing unit and an associated memory element for storing information-representative signals, said plural memory elements together forming a common memory,

B. each said central processing unit including access request means for generating an access-request signal representative of a request for access to an information-representative signal stored in said common memory, and

C. each said processing cell including memory management means, coupled to the corresponding central processing unit and memory element of that processing cell, for selectively responding to an access-request signal for at least signaling the availability of an information-representative signal stored in that corresponding memory element,

the memory management means of respective processing cells being coupled to one another for selective transfer of access-request signals therebetween,

D. each said memory management means including directory means for storing an ANCHOR signal corresponding to each of at least selected information-representative signals in the corresponding memory element, said ANCHOR signal being indicative of a mode by which the corresponding information-representative signal is accessible,

E. said memory management means including means for responding to an access-request signal generated by any of said central processing units directed to an information-representative signal having an ANCHOR signal indicative of a first alternative mode of access for at least signaling the requesting central processing unit that the requested information-representative signal is stored in said common memory, and

F. said memory management means including means for responding to an access-request signal

i) generated by the central processing unit corresponding to that memory management means and directed to an information-representative signal stored within the corresponding memory element, which information-representative signal is associated with an ANCHOR signal indicative of a second alternative mode of access, for signaling that corresponding central processing unit that the requested information-representative signal is stored in said common memory, and

ii) generated by any other of said central processing units directed to that same information-representative signal for signaling the requesting central processing unit that the requested information-representative signal is not stored in said common memory.

2. A digital data processing apparatus according to claim 1, wherein

A. said access request means include means for generating an ownership-request signal representative of a request for priority access to an information-representative signal,

B. said memory management means include means for accessing information-representative signals stored in the respective memory elements and for responding to selected ones of said ownership-request signals for

allocating, only within the memory element associated with the requesting central processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive physical storage space for the requested information-representative signal with respect to all of said memory elements, and

storing the requested information-representative signal in that exclusive physical storage space.

3. A digital data processing apparatus according to claim 2, wherein said memory management means comprise means responsive to selected ones of said ownership-request signals for deallocating physical storage space allocated in a memory element, other than the one associated with the requesting central processing unit, for storage of the requested information-representative signal.

4. A digital data processing system according to claim 1, wherein

A. at least said selected central processing unit includes anchor request means for generating a request for placing an information-representative signal stored in the common memory in a selected one of said first and second alternative access modes, and

B. the memory management means corresponding to the memory element storing that information-representative signal includes means selectively responsive to such request for setting corresponding the ANCHOR signal to be indicative of the selected access mode.

5. A digital data processing apparatus according to claim 4, wherein

A. said access request means include means for generating an ownership-request signal representative of a request for priority access to an information-representative signal,

B. said memory management means include means for accessing information-representative signals stored in the respective memory elements and for responding to selected ones of said ownership-request signals for

allocating, only within the memory element associated with the requesting central processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive physical storage space for the requested information-representative signal with respect to all of said memory elements, and

storing the requested information-representative signal in that exclusive physical storage space.

6. A digital data processing apparatus according to claim 5, wherein said memory management means comprise means responsive to selected ones of said ownership-request signals for deallocating physical storage space allocated in a memory element, other than the one associated with the requesting central processing unit, for storage of the requested information-representative signal.

7. A digital data processing system according to claim 1, wherein

A. at least said selected central processing unit includes anchor request means for generating a request for placing an information-representative signal stored in the corresponding memory element in a selected one of said first and second alternative access modes, and

B. the memory management means corresponding to that central processing unit includes means selectively responsive to such request for setting the ANCHOR signal corresponding to that information-representative signal to be indicative of the selected access mode.

8. A digital data processing apparatus according to claim 7, wherein

A. said access request means include means for generating an ownership-request signal representative of a request for priority access to an information-representative signal,

B. said memory management means include means for accessing information-representative signals stored in the respective memory elements and for responding to elected ones of aid ownership-request signals for

allocating, only within the memory element associated with the requesting central processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive physical storage space for the requested information-representative signal with respect to all of said memory elements, and

storing the requested information-representative signal in that exclusive physical storage space.

9. A digital data processing apparatus according to claim 8, wherein said memory management means comprise means responsive to selected ones of said ownership-request signals for deallocating physical storage space allocated in a memory element, other than the one associated with the requesting central processing unit, for storage of the requested information-representative signal.

11. A digital data processing apparatus according to any of claims 1-10, comprising:

A. (n) information transfer domains, each respectively designated as information transfer domain(k), wherein (n) is an integer greater than or equal to two, and wherein (k) represents successive integers between (o) and (n-1), inclusive,

B. information transfer domain (O) including a plurality of domain(O) segments, each such segment including a bus element connected to said memory management means for transferring signals between a plurality of said processing cells,

C. each information transfer domain(k), for (k) between (1) and (n-1), inclusive including one or more corresponding domain(k) segments, wherein the number of segments in information domain(k) is less than the number of segments in domain(k-1), for each value of (k), and wherein information transfer domain(n-1) includes only one such segment.

12. A digital data processing apparatus according to claim 11, wherein each said domain(k) segment includes

A. a bus element for transferring signals within that domain(k) segment,

B. plural domain routing elements for transferring signals between that domain(k) segment and a domain(k-1) segment, each such routing element being connected for signal transfer with the respective domain(k) segment bus element and with the respective domain(k-1) segment bus element.

10. A digital data processing system comprising

A. plural processing cells, each including a central processing unit coupled to an associated memory element, each said memory element being capable of storing one or more information-representative signals,

B. memory management means coupled to said plural memory elements for accessing one or more information-representative signals stored in said plural memory elements,

C. at least a first central processing unit including means for generating a request for priority access to a selected information-representative signal for which physical storage space is allocated in the memory element associated with another central processing unit,

D. said memory management means including means responsive to such request for

i) allocating, within the memory element associated with the first central processing unit, physical storage space for said selected information-representative signal, and for storing that signal therein, and

ii) invalidating copies of said selected information-representative signal, if any, stored in said physical storage space allocated to that information-representative signal in said other memory elements,

E. said first central processing unit including means for generating a POST-STORE signal representative of a request for transfer of a copy of said selected information-representative signal to other memory elements having space allocated to that information-representative signal, and

F. said memory management means including means responsive to such POST-STORE signal for transferring and storing a copy of said selected information-representative signal to the other processing cells having physical storage space allocated for said selected information-representative signal in the memory elements thereof.

13. A method of operating a digital data processing system comprising

A. providing plural processing cells, each comprising a central processing unit and an associated memory element for storing information-representative signals, wherein said plural memory elements together form a common memory,

B. storing, within each said processing cells, ANCHOR signals indicative of a mode by which each of at least selected information-representative signals is accessible,

C. generating, within any of said central processing units, an access-request signal representative of a request for access to an information-representative signal stored in said common memory, and

D. responding, within each of said processing cells, to an access-request signal generated by any of said central processing units directed to an information-representative signal having an ANCHOR signal indicative of a first alternative mode of access for signaling the requesting central processing unit that the requested information-representative signal is stored in said common memory, and

E. responding, within a processing cell, to an access-request signal generated by the central processing unit of that cell directed to an information-representative signal stored in the memory element of that cell and having access for signaling that central processing unit that the requested information-representative signal is stored in said common memory, and responding to an access-request signal generated by any other of said central processing units directed to that same information-representative signal for signaling the requesting central processing unit that the requested information-representative signal is not stored in said common memory.

14. A method of operating a multiprocessor digital data processing system according to claim 13, including the steps of

A. generating, within a selected one of central processing units, a request for placing an information-representative signal stored in the common memory in a selected one of said first and second alternative access modes, and

B. selectively responding to such request for setting the ANCHOR signal corresponding to that information-representative signal to be indicative of the selected access mode.

15. A method of operating a multiprocessor digital data processing system according to claim 13, including the steps of

generating, within a selected one of central processing units, a request for placing an information-representative signal stored in the corresponding memory element in a selected one of said first and second alternative access modes, and

B. selectively responding to such request for setting the ANCHOR signal corresponding to that information-representative signal to be indicative of the selected access mode.

16. A method of operating a multiprocessor digital data processing system according to any of claims 13-15 comprising the steps of

A. generating within a requesting one of said central processing units an ownership-request signal representative of a request for priority access to an information-representative signal,

B. responding to at least selected such ownership-request signals for

allocating, only within the memory element associated with the requesting central processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive physical storage space for the requested information-representative signal with respect to all of said memory elements, and

storing the requested information-representative signal in that exclusive physical storage space.

17. A method of operating a multiprocessor digital data processing system according to claim 16, wherein said responding step includes the further step of deallocating physical storage space, if any, allocated to the requested information-representative signal within the memory elements associated with central processing units other than the requesting one.

18. A method for operating a multiprocessor digital data comprising

A. providing plural processing cells, each including a central processing unit coupled to an associated memory element, each said memory element being capable of storing one or more information-representative signals,

B. generating, within at least a first one of said central processing units, a request for priority access to a selected information-representative signal, said selected information-representative signal being one for which physical storage space is allocated in another of said memory elements,

C. responding to said ownership-request signal for

i) allocating within the memory element associated with the first central processing unit, physical storage space for said selected information-representative signal, and for storing that signal therein,

ii) invalidating an information-representative signal stored in the physical storage space allocated to said selected information-representative signal in said other memory element,

D. generating, within said first central processing unit, a post-store signal representative of a request for transfer of a copy of said information-representative signal to said other memory elements, and

E. responding to said post-store signal for transferring a copy of said selected information-representative signal to said other processing cells for storage in the physical storage space allocated for said selected information-representative signal in said other memory elements.

19. A digital data processing system comprising

A. plural processing cells, each including a central processing unit coupled to an associated memory element, each said memory element being capable of storing one or more information-representative signals,

B. memory management means coupled to said plural memory elements for accessing one or more information-representative signals stored in said plural memory elements,

C. at least a first central processing unit including means for executing an ownership-access instruction for generating a request for priority access to a selected information-representative signal for which physical storage space is allocated in the memory element associated with another central processing unit,

D. said memory management means including means responsive to such request for

i) allocating, within the memory element associated with the first central processing unit, physical storage space for said selected information-representative signal, and for storing that signal therein, and

ii) invalidating copies of said selected information-representative signal, if any, stored in said physical storage space allocated to that information-representative signal in said other memory elements,

E. said first central processing unit including means for executing a POST-STORE instruction for generating a POST-STORE signal representative of a request for transfer of a copy of said selected information-representative signal to other memory elements having space allocated to that information-representative signal, and

F. said memory management means including means responsive to such POST-STORE signal for transferring and storing a copy of said selected information-representative signal to the other processing cells having physical storage space allocated for said selected information-representative signal in the memory elements thereof.

20. A method for operating a multiprocessor digital data comprising

A. providing plural processing cells, each including a central processing unit coupled to an associated memory element, each said memory element being capable of storing one or more information-representative signals,

B. executing, with at least a first one of said central processing units, an ownership-access instruction for generating a request for priority access to a selected information-representative signal, said selected information-representative signal being one for which physical storage space is allocated in another of said memory elements,

C. responding to said ownership-request signal for

i) allocating within the memory element associated with the first central processing unit, physical storage space for said selected information-representative signal, and for storing that signal therein,

ii) invalidating an information-representative signal stored in the physical storage space allocated to said selected information-representative signal in said other memory element,

D. executing, with said first central processing unit, a POST-STORE instruction for generating a POST-STORE signal representative of a request for transfer of a copy of said information-representative signal to said other memory elements, and

E. responding to said POST-STORE signal for transferring a copy of said selected information-representative signal to said other processing cells for storage in the physical storage space allocated for said selected information-representative signal in said other memory elements.