Multiprocessor digital data processing system

Claim 2

Digital data processing apparatus comprising A. plural processing cells, each including a central processing unit coupled to an associated memory element, 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 requesting one of said central processing units including access request means for generating an access request signal representative of a request for access to an information-representative signal, said access request means including means for generating an ownership-request signal representative of a request for priority access to an information-representative signal, at least the memory element associated with the requesting central processing unit including control means for slectively transmitting said access-request signal to said memory management element, and D. said memory management means including memory coherence means responsive to selected ones of said ownership-request signals for allocating, exclusively, within the memory element associated with the requesting central processing unit, physical storage space for the requested information-representative signal and for storing that signal therein.

Claim 3

Digital data processing apparatus as claimed in claim 1, characterised in that said memory management means comprises means responsive to selected ones of said ownership-request signal for deallocating physical storage space maintained in a memory element, other than the one associated with the requesting central processing unit, for storage of the requested information-representative signal, said deallocation being effected substantially concurrently with the allocation of physical storage space for the requested information-representative signal in the memory element associated with the requesting central processing unit.

Claim 4

Digital data processing apparatus as claimed in claim 2, characterised in that at least one said memory element includes an associated directory means for storing an SA address signal uniquely identifying at least selected information-representative signals stored in that memory element.

Claim 5

Digital data processing apparatus as claimed in claim 3, characterised in that said access request means includes means for generating, along with said access request signal, an SA request signal identifying the requested information-representative signal, said memory management means includes interface means coupled with said directory means for comparing an SA request signal with one or more SA address signals stored in that directory means for determining whether the requested information-representative signal is stored in the memory element associated with that directory means.

Claim 6

Digital data processing apparatus as claimed in claim 3, characterised in that each said directory means includes one or more address storage locations for storing SA address signals, said memory management element includes means for storing in one of said address storage locations an SA address signal associated with an information-representative signal for which physical storage space has been allocated within the associated memory element, and said memory management element includes means for invalidating an SA address signal corresponding to an information-representative signal for which physical storage space has been deallocated within the associated memory element.

Claim 7

Digital data processing apparatus as claimed in claim 1, characterised in that said access request means includes means for generating a read-only request signal representative of a request for secondary access to an information-­representative signal, and wherein said memory management means includes means selectively responsive to a read-only signal generated by a requesting one of said central processing units, said read-only signal being representative of a request for secondary access to an information-representative signal stored in a memory element associated with another of said other central processing units, for transferring a copy of that information-representative signal to the memory element associated with the requesting central processing unit.

Claim 8

Digital data processing apparatus as claimed in claim 1, characterised in that said central processing units includes means for selectively generating an update signal representative of modification of an information-representative signal, said memory management means includes means responsive to an update signal generated by an updating one of said central processing units for modifying a corresponding information-representative signal stored in the memory element associated with that central processing unit.

Claim 9

Digital data processing apparatus as claimed in claim 7,characterised in that said memory management means includes means responsive to an update signal generated by said updating central processing unit, said update signal being representative of modification of a corresponding information-­representative signal stored in a memory element associated with another said central processing unit, for modifying that corresponding information-­representative signal.

Claim 10

Digital data processing apparatus as claimed in claim 1, characterised in that said access request means includes atomic-ownership means for generating a atomic-request signal representative of a request for exclusive priority access to one or more information-representative signals, said memory coherence means includes means selectively responsive to an atomic-request signal generated by a first one of said central processing units for allocating, exclusively, in the memory element associated with the first central processing unit physical storage space for said one or more requested information-representative signals and for storing those information-representative signals therein, while preventing access to any of those information-representative signals in response to a first selected access request signal generated by a second one of said central procesing units.

Claim 11

Digital data processing apparatus as claimed in claimed 9, characterised in that said memory coherence means includes means for responding to a second selected access request generated by said second central processing unit for effecting exclusive transfer of requested information-representative signals to the memory element associated with that central processing unit and for preventing access to any of those information request signals generated by the first or any other central process unit.

Claim 12

Digital data processing apparatus as claimed in claim 9, characterised in that said access request means further includes atomic-transaction termination means for generating a release signal representative of termination of said request for priority access to said one or more information-representative signals, and said memory coherence means includes means responsive to said transaction-termination signal for re-enabling selective access to those information-representative signals in response to access request signals generated by any of said central processing units.

Claim 13

Digital data processing apparatus comprising plural central processing units, and plural memory elements for storing digital signals representative of information, each memory element being coupled for information transfer with an associated one of said central processing units, the apparatus being characterised by A. memory management means coupled to said plural memory elements for accessing one or more information-representative signals stored therein, and B. said memory management means including state-defining means coupled with said plural memory elements for associating an access state with one or more information-representative signals stored therein, said access state being selected from a group of access states including one or more of i) an invalid access state associable with an invalid information-representative signal, ii) a read-only access state associable with an information-representative signal subject to read-only access by a central processing unit associated with a memory element in which that information-representative signal is stored, iii) a nonexclusive owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, a copy of which information-representative signal is stored in a memory element associated with another said central processing unit, an exclusive owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, no copy of which information-representative signal is stored in a memory element associated with another said central processing unit, that information-representative signal, or a copy thereof, being accessible for transfer to a memory element associated with another said central processing unit, and an atomic owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, no copy of which information-representative signal is stored in a memory element associated with another said central processing unit, neither that information-­representative signal, nor a copy thereof, being selectively accessible for transfer to a memory element associated with another said central processing unit.

Claim 14

Digital data processing apparatus comprising plural central processing units, and plural memory elements for storing digital signals representative of information, each memory element being coupled for information transfer with an associated one of said central processing units, the apparatus being characterised by A. memory management means coupled to said plural memory elements for accessing one or more information-representative signals stored therein, and B. said memory management means including state-defining means coupled with said plural memory elements for associating an access state with one or more information-representative signals stored therein, said access state being selected from a group of access states including one or more of i) an invalid access state associable with an invalid information-representative signal, ii) a read-only access state associable with an information-representative signal subject to read-only access by a central processing unit associated with a memory element in which that information-representative signal is stored, iii) a nonexclusive owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, a copy of which information-representative signal is stored in a memory element associated with another said central processing unit, an exclusive owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, no copy of which information-representative signal is stored in a memory element associated with another said central processing unit, that information-representative signal, or a copy thereof, being accessible for transfer to a memory element associated with another said central processing unit, and an atomic owner access state associable with an information-representative signal modifiable by a central processing unit associated with a memory element in which that information-­representative signal is stored, no copy of which information-representative signal is stored in a memory element associated with another said central processing unit, neither that information-­representative signal, nor a copy thereof, being selectively accessible for transfer to a memory element associated with another said central processing unit.

Claim 15

Digital data processing apparatus as claimed in claim 12, characterised in that said state-defining means includes means for selectively and exclusively associating any one of said atomic owner access state, and said exclusive owner access state with an information-representative signal stored in said plural memory elements, and means for selectively and exclusively associating said nonexclusive owner access state with one of (n) copies of an information-representative signal stored in said plural memory elements, where (n) is an integer greater than or equal to one.

Claim 16

Digital data processing apparatus as claimed in claim 13, characterised in that said state-defining means includes means for slectively associating any one of said read-only access state, and said invalid access state with (n-1) copies of an information-representative signal stored in said plural memory elements.

Claim 17

Digital data processing apparatus as claimed in claim 12, characterised in that said memory management means includes means responsive to association of said atomic access state with an information-representative signal stored in a memory element associated with a first central processing unit for preventing access to that information-representative signal in response to a first selected access request signal generated by any other said control processing unit.

Claim 18

Digital data processing apparatus as claimed in claim 15, characterised in that said memory management means includes means for responding to a second selected access request signal generated by a second central processing unit, and directed to one or more information representative signals associated with the atomic owner access state, for effecting transfer of those requested signals to the memory element associated with said second central processing unit, and said state-defining means includes means for associating the atomic owner state with those transferred signals for allocating, exclusively, in the memory element associated with the second central processing unit physical storage space for said one or more requested information-representative signals.

Claim 19

Digital data processing apparatus as claimed in claim 12, characterised in that said state-defining means includes means responsive to an access request signal generated by a requesting central processing unit and directed to an information-representative signal stored in a memory element associated with an owning central processing unit, said information-representative signal being associated with said atomic access state, for associating with that information-representative signal a transient atomic state, said owning central processing unit includes means for generating a release signal representative of a release of said requested information-representative signal from said atomic access state, said memory management means includes means responsive to a release signal generated by said owning central processing unit and directed to said requested information-representative signal for transmitting a copy of that information-representative signal to the memory element associated with the requesting central processing unit.

Claim 20

Digital data processing apparatus as claimed in claim 12, the further improvement, character­ised in that at least a requesting one of said central processing units includes access request means coupled to said state-defining means for generating an access request signal representative of a request for access to an information-representative signal, said access request means including means for generating an exclusive access request signal representative of a request for exclusive access to an information-representative signal, and said state-defining means includes means responsive to an exclusive access request signal generated by said requesting central processing unit, said exclusive access request being representative of a request for exclusive access to an information-representative signal stored in a memory element associated with another of said central processing units, wherein that information-­representative signal is associated with said read-­only access state, for effecting exclusive transfer of that information-representative signal to said requesting central processing unit and for associating the copy of that information-­representative signal stored in the memory element associated with that other central processing unit with said invalid access state.

Claim 21

Digital data processing apparatus as claimed in claim 12, characterised in that at least a requesting one of said central processing units includes access request means coupled to said state-defining means for generating an access request signal representative of a request for access to an information-representative signal, said access request means includes means for generating a nonexclusive access-request signal representative of a request for nonexclusive access to an information-representative signal, and said state-defining means includes means responsive to a nonexclusive access request signal generated by said requesting central processing unit, said nonexclusive access request signal being representative of a request for nonexclusive access to an information-representative signal stored in a memory element associated with another of said central processing units, wherein that information-representative signal is associated with any one of an exclusive access state and a nonexclusive access state, for effecting exclusive transfer of that information-representative signal to said requesting central processing unit and for associating the information-representative signal stored in the memory element associated with that other central processing unit with said read-only access state.

Claim 22

Digital data processing apparatus as claimed in claim 12, characterised in that the access request means associated with a requesting one of said central processing units includes stop request means for generating a stop request signal representative of a pending request for atomic owner access to an information-representative signal said memory management means includes means responsive to said stop request signal for effecting exclusive storage of a next available copy of the requested information-representative signal in the memory element associated with a requesting central processing unit, and said state-defining means includes means responsive to said stop request signal for assigning said atomic owner access state to said next available copy of the requested information-representative signal stored in the memory element associated with said requesting central processing unit.

Claim 23

Digital data processing apparatus as claimed in claim 12, characterised in that said memory management means includes means responsive to a request for priority access to an information-representative signal generated by a first central processing unit for responding to subsequent requests for access to that same information-representative generated by others of said central processing units for generating a transient signal for transmission to said other central processing units, said transient signal being representative of current ownership of said requested information-representative signal by said first central processing unit.

Claim 24

Digital data processing apparatus comprising a plurality of information transfer domains each including one or more segments, said plurality of information transfer domains including a first information transfer domain having a plurality of domain(0) segments, each including an associated unidirectional bus element and a first plurality of processing cells connected in a ring configuration to said bus element for transferring information-­representative signals. each of said cells including a central processing unit and an associated content-addressable memory means, said memory means for storing information-representative signals, said memory means including interface means connected with the associated central processing unit and with said bus element for transferring information-representative signals, the cells being so that arranged that the transfer of information-representative signals between the associated central processing units takes place only through the respective memory means, domain(1) segment comprising an associated unidirectional bus element and a plurality of routing elements, each said routing element being connected to the bus element associated with the domain(1) segment and to the bus element associated with one of said domain(0) segments for transferring information-representative signals between the domain(1) segment and the associated domain(0) segment, the processing cells associated with each of said domain(0) segments being capable of information-representative signal transfer with the processing cells associated with the remainder of said domain(0) segments only through the domain(1) segment.

Claim 25

Digital data processing apparatus comprising a plurality of information transfer domains each including one or more segments, said plurality of information transfer domains including a first information transfer domain having a plurality of domain(0) segments, each including an associated unidirectional bus element and a first plurality of processing cells connected in a ring configuration to said bus element for transferring information-­representative signals. each of said cells including a central processing unit and an associated content-addressable memory means, said memory means for storing information-representative signals, said memory means including interface means connected with the associated central processing unit and with said bus element for transferring information-representative signals, the cells being so that arranged that the transfer of information-representative signals between the associated central processing units takes place only through the respective memory means, domain(1) segment comprising an associated unidirectional bus element and a plurality of routing elements, each said routing element being connected to the bus element associated with the domain(1) segment and to the bus element associated with one of said domain(0) segments for transferring information-representative signals between the domain(1) segment and the associated domain(0) segment, the processing cells associated with each of said domain(0) segments being capable of information-representative signal transfer with the processing cells associated with the remainder of said domain(0) segments only through the domain(1) segment.

Claim 26

Digital data processing apparatus 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 (0) and (n-1), inclusive, B. information transfer domain(0) including a plurality of domain(0) segments, each such segment including i) a plurality of processing cells, each processing cell including a central processing unit connected for information-representative signal transfer with an associated memory means, said memory means for storing information-representative signals, ii) a bus element connected to those plural memory means for transferring information-representative signals within the domain(0) segment, C. each information transfer domain(k), wherein (k) represents successive integers 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, each domain(k) segment including i) a bus element for transferring information-representative signals within that domain(k) segment, ii) plural domain routing elements for transferring information representative signals between that domain(k) segment and a domain(k-1) segment, each such routing element being connected for information-representative signal transfer with the respective domain(k), segment bus element and with the respective domain(k-1) segment bus element.

Claim 27

Digital data processing apparatus 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 (0) and (n-1), inclusive, B. information transfer domain(0) including a plurality of domain(0) segments, each such segment including i) a plurality of processing cells, each processing cell including a central processing unit connected for information-representative signal transfer with an associated memory means, said memory means for storing information-representative signals, ii) a bus element connected to those plural memory means for transferring information-representative signals within the domain(0) segment, C. each information transfer domain(k), wherein (k) represents successive integers 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, each domain(k) segment including i) a bus element for transferring information-representative signals within that domain(k) segment, ii) plural domain routing elements for transferring information representative signals between that domain(k) segment and a domain(k-1) segment, each such routing element being connected for information-representative signal transfer with the respective domain(k), segment bus element and with the respective domain(k-1) segment bus element.

Claim 28

Digital data processing apparatus as claimed in claim 23, characterised in that at least a requesting one of said central processing units includes means for generating an access-request signal representative of a request for access to an information-representative signal stored in any one of said memory means, memory means associated with the requesting central processing unit includes control means responsive to an access-request signal directed to an information-representative signal not stored within that memory element for generating a domain-­request signal and transmitting that signal on the associated domain(0) bus element.

Claim 29

Digital data processing apparatus as claimed in claim 24, characterised in that one or more said processing cells includes means for receiving an access-request signal transferred along an associated domain(0) bus for selectively generating a signal representative of the requested information-representative signal.

Claim 30

Digital data processing apparatus as claimed in claim 24, characterised in that each said bus element comprises a unidirectional information-representative signal flow path, and said control means includes means for driving said domain-request signal along the flow path defined by the associated but element.

Claim 31

Digital data processing apparatus as claimed in claim 24, characterised in that said domain routing element includes at least one of means for receiving a domain-request signal transferred along a bus element associated with a domain(k-1) segment, where (k) is an integer between (1) and (n-1), and for selectively transmitting a copy of that signal along the bus element associated with a corresponding domain(k) segment, and means for receiving a domain-request signal transferred along a bus element associated with a domain(k) segment, where (k) is an integer between (1) and (n-1), and for selectively transmitting a copy of that signal along the bus element associated with a corresponding domain(k-1) segment.

Claim 32

Digital data processing apparatus as claimed in claim 27, characterised in that a domain routing element connected with a domain(k) segment, where (k) is an integer between (1) and (n-1), inclusive, includes directory means for storing SA address signals corresponding to information-representative signals stored in the plurality of memory elements contained in processing cells of domain(j) segments associated with that domain(k) segment, where (j) is an integer between (k-1) and (0), and said routing element includes interface means coupled with said directory element and with said access request means for comparing a domain-request signal with an SA address signal to determine whether a copy of that domain request signal should be transmitted to the associated domain(k) segment.

Claim 33

Digital data processing apparatus comprising A. a plurality of processing cells, including at least a remote processing cell, each said cell including a central processing unit coupled for information transfer with an associated memory element, each said central processing unit including ownership-request means for generating an ownership-request signal representative of a request for priority access to an information-representative signal, B. bus means for transmitting information-representative signals between said memory elements, C. remote interface means coupled to said remote cell for transferring information-representative signals between the associated memory element and the bus means, and D. memory management means coupled to said memory elements for accessing information-representative signals stored therein, each said central processing unit including control means for selectively transmitting said access-request signal to said memory management element, said memory management means including memory coherence means responsive to selected ones of said ownership-request signals for effecting exclusive storage of said requested information-representative signal in the memory element associated with the requesting central processing unit.

Claim 34

Digital data processing apparatus comprising A. a plurality of processing cells, including at least a remote processing cell, each said cell including a central processing unit coupled for information transfer with an associated memory element, each said central processing unit including ownership-request means for generating an ownership-request signal representative of a request for priority access to an information-representative signal, B. bus means for transmitting information-representative signals between said memory elements, C. remote interface means coupled to said remote cell for transferring information-representative signals between the associated memory element and the bus means, and D. memory management means coupled to said memory elements for accessing information-representative signals stored therein, each said central processing unit including control means for selectively transmitting said access-request signal to said memory management element, said memory management means including memory coherence means responsive to selected ones of said ownership-request signals for effecting exclusive storage of said requested information-representative signal in the memory element associated with the requesting central processing unit.

Claim 35

Digital data processing apparatus as claimed in claim 29, characterised in that said memory coherence means includes means for allocating, within the memory element associated with the requesting central processing unit, physical storage space for storing the requested information-representative signal, means for storing the requested information-representative signal in said allocated storage space, and means for deallocating physical storage space associated with the requested information-representative signal within the memory element associated with said other cell.

Claim 36

Digital data processing apparatus as claimed in claim 30, characterised in that said remote cell resides at a point physically remote from said bus means, and wherein said interface means includes means for transmitting said information-representative signal between said physically remote point and said bus means.

Claim 37

Digital data processing apparatus as claimed in claim 31, characterised in that said remote interface means includes fiber optic transmission media for carrying information-representative signals between said remote cell and said bus means.

Claim 40

A method as claimed in claim 33, characterised in that said responding step includes the further steps of i) allocating, within the memory element associated with the requesting central processing unit, physical storage space for storing the requested information-representative signal, ii) storing the requested information-representative signal in said allocated storage space, and iii) deallocating physical storage space associated with the requested information-representative signal within the memory element associated with cell from which the requested information-representative signal was transferred.

Claim 43

A method as claimed in claim 35, characterised by the steps of generating, within a requesting one of said central processing units, an exclusive access request signal representative of a request for priority access to an information-representative signal, and responding to an exclusive access request signal generated by requesting central processing unit, said exclusive access request being representative of a request for exclusive access to an information-representative signal stored in a memory element associated another of said central processing units, wherein that information-representative signal is associated with an access state other than said atomic ownership state, for effecting exclusive transfer of that information-representative signal to said requesting central processing unit and for associating the copy of that information-representative signal stored in the memory element associated with that other central processing unit with the invalid access state.