This invention relates to digital data processing systems and, more particularly, to multiprocessing systems with distributed hierarchical memory architectures.
The art provides a number of configurations for coupling the processing units of multiprocessing systems. Among the earlier designs, processing units that shared data stored in system memory banks were coupled to those banks via high-bandwidth shared buses or switching networks. During periods of heavy usage, bottlenecks were likely to develop as multiple processing units simultaneously contended for access to the shared data.
In order to minimize the risk of formation of transmission bottlenecks, distributed memory systems were developed coupling individual processing units with local memory elements to form semi-autonomous processing cells. To achieve the benefits of multiprocessing, some of the more recently designed systems established cell communications through utilization of hierarchical architectures.
The distributed memory systems, however, permit multiple copies of single data items to reside within multiple processing cells; hence, it is difficult insure that all processing cells maintain identical copies of like data elements. Conventional efforts to resolve this problem, i.e., to preserve data coherency, rely upon software oriented techniques utilizing complex signalling mechanisms.
To avoid processing and signalling overhead associated with these software oriented solutions, Frank et al, U.S. Pat. No. 4,622,631, discloses a multiprocessing system in which a plurality of processors, each having an associated private memory, or cache, share data contained in a main memory element. Data within that common memory is partitioned into blocks, each of which can be owned by any one of the main memory and the plural processors. The current owner of a data block is said to have the correct data for that block.
A hierarchical approach is disclosed by Wilson Jr. et al, United Kingdom Patent Application No. 2,178,205, wherein a multiprocessing system is said to include distributed cache memory elements coupled with one another over a first bus. A second, higher level cache memory, attached to the first bus and to either a still higher level cache or to the main system memory, retains copies of every memory location in the caches below it. The still higher level caches, if any, and system main memory, in turn, retain copies of each memory location of cache below them. The Wilson Jr. et al processors are understood to transmit modified copies of data from their own dedicated caches to associated higher level caches and to the system main memory, while concurrently signalling other caches to invalidate their own copies of that newly-modified data.
Notwithstanding the solutions proposed by Frank et al and Wilson Jr. et al proposal, data coherency and bus contention remain significant problems facing both designers and users of multiprocessing systems. With respect to Wilson Jr. et al, for example, these problems may be attributed, at least in part, to the requirement that data in main memory must always be updated to reflect permanent modifications introduced to the data elements by each of the processors in the system. Moreover, neither of the proposed designs is capable of supporting more than a limited number of processing units. This restriction in xe2x80x9cscalabilityxe2x80x9d arises from a requirement of both the Wilson Jr. et al and Frank et al systems that the size of main memory must increase to accommodate each additional processor.
It is therefore an object of this invention to provide an improved multiprocessing system with improved data coherency, as well as reduced latency and bus contention. A further object is to provide a multiprocessing system with unlimited scalability.
Other objects of the invention are to provide a physically distributed memory multiprocessing system which requires little or no software overhead to maintain data coherency, as well as to provide a multiprocessing system with increased bus bandwidth and improved synchronization.
The invention attains the aforementioned objects by providing, in one broad aspect, a digital data processing system comprising a plurality of processing cells arranged in a hierarchy of rings. The system selectively allocates storage and moves exclusive data copies from cell to cell in response to access requests generated by the cells. Routing elements are employed to selectively broadcast data access requests, updates and transfers on the rings.
A system of the type provided by the invention does not require a main memory element, i.e., a memory element coupled to and shared by the systems many processors. Rather, data maintained by the system is distributed, both on exclusive and shared bases, among the memory elements associated with those processors. Modifications to datum stored exclusively in any one processing cell do not have to be communicated along the bus structure to other storage areas. As a result of this design, only that data which the processors dynamically share, e.g., sharing required by the executing program themselves, must be transmitted along the bus structure. These aspects, along with the systems hierarchical structure, localize signal traffic greatly, thereby reducing bus contention and bottlenecks.
With further attention to system structure and element interconnection, the processing cells include central processing units coupled with memory elements, each including a physical data and control signal store, a directory, and a control element. Groups of cells are interconnected along unidirectional intercellular bus rings, forming units referred to as segments. These segments together form a larger unit referred to as xe2x80x9cinformation transfer domain(0).xe2x80x9d While cells residing within each segment may communicate directly with one another via the associated intercellular bus, the associated central processing units are not themselves interconnected. Rather, intersegment communications are carried out via the exchange of data and control signals stored in the memory elements. A memory management element facilitates this transfer of information.
Communications between cells of different domain(0) segments are carried out on higher level information transfer domains. These higher level domains are made up of one or more segments, each comprising a plurality of domain routing elements coupled via a unidirectional bus ring. It will be appreciated that the segments of higher level domains differ from those of domain(0) insofar as the former comprise a ring of routing elements, while the latter comprise a ring of processing cells. Each routing element is connected with an associated one of the segments of the next lower information transfer domain. These connected lower segments are referred to as xe2x80x9cdescendants.xe2x80x9d Every information transfer domain includes fewer segments than the next lower domain. Apart from the single segment of the system""s highest level domain, signals are transferred between segments of each information transfer domain via segments of the next higher domain.
An exemplary system having six domain(0) segments includes two domain(1) segments, the first which transfers data between a first three of the domain(0) segments, and the second of which transfers data between the other three domain(0) segments. Data is transferred between the two domain(1) segments over a domain(2) segment having two domain routing elements, each connected with a corresponding one of the domain(1) segments.
The system""s memory elements each include a directory element that maintains a list of descriptors reflecting the identity and state of each datum stored in the corresponding memory. One portion of each descriptor is derived from the associated datum""s system address, while another portion represents an access state governing the manner in which the local central processing unit may utilize the datum. This access state may include any one of an xe2x80x9cownershipxe2x80x9d state, a read-only state, and an invalid state. The first of these states is associated with data which can be modified by the local central processing unit, i.e., that unit included within the cell in which the datum is stored. The read-only state is associated with data which may be read, but not modified, by the local central processing unit. The invalid state is associated with invalid data copies.
The domain routing elements themselves maintain directories listing all descriptors stored in their descendant domain(0) segments. Thus, in the above example, the routing elements of first domain(1) segments maintain directories reflecting the combined content of the cells of their respective domain(0) segment. Moreover, the single routing element of the domain(2) segment maintains a directory listing all descriptors retained in all of the system""s processing cells.
Data access requests generated by a processor are handled by the local memory element whenever possible. More particularly, a controller coupled with each memory monitors the cell""s internal bus and responds to local processor requests by comparing the request with descriptors listed in the corresponding directory. If found, matching data is transmitted back along the internal bus to the requesting processor.
Data requests that cannot be resolved locally are passed from the processing cell to the memory management system. The management element selectively routes those unresolved data requests to the other processing cells. This routing is accomplished by comparing requested descriptors with directory entries of the domain routing units. Control elements associated with each of those other cells, in turn, interrogate their own associated directories to find the requested data. Data satisfying a pending request is routed along the domain segment hierarchy from the remote cell to the requesting cell.
Data movement between processing cells is governed by a protocol involving comparative evaluation of each access request with the access state associated with the requested item. The memory management system responds to a request for exclusive ownership of a datum by moving that datum to the memory element of the requesting cell. Concurrently, the memory management element allocates physical storage space for the requested item within the requesting cell""s data storage area. The management element also invalidates the descriptor associated with the requested item within the data store of the remote cell, thereby effecting subsequent deallocation of the physical storage space which had retained the requested item prior to its transfer to the requesting cell.
While the aforementioned operations result in exclusive storage of the requested datum within the requesting cell, other cells may subsequently gain concurrent access to that datum, for example, on a read-only basis. Particularly, the memory management system responds to a request by a first cell for read-only access to datum exclusively owned by a second cell by transmitting a copy of that datum to the first cell while simultaneously designating the original copy of that data, stored in the second cell, as xe2x80x9cnonexclusively owned.xe2x80x9d
The system permits an owning cell to disable the copying of its data by providing a further ownership state referred to as the xe2x80x9catomicxe2x80x9d state. The memory management system responds to requests for data in that state by transmitting a wait, or xe2x80x9ctransient,xe2x80x9d signal to requestors and by broadcasting the requested data over the hierarchy once atomic ownership is relinquished.
A system of the type described above provides improved multiprocessing capability with reduced bus and memory contention. The dynamic allocation of exclusive data copies to processors requiring exclusive access, as well as the sharing of data copies required concurrently by multiple processors reduces bus traffic and data access delays. Utilization of a hardware-enforced access protocol further reduces bus and memory contention, while simultaneously decreasing software overhead required to maintain data coherency. The interconnection of information transfer domain segments permits localization of data access, transfer and update requests.
These and other aspects of the invention are evident in the description which follows.