Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-09-28
2004-02-17
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
Reexamination Certificate
active
06694412
ABSTRACT:
BACKGROUND OF THE INVENTION
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 “scalability” 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.
SUMMARY OF THE INVENTION
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 “information transfer domain(
0
).” 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 “descendants.” 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 “ownership” state, a read-only state,
Burkhardt, III Henry
Frank Steven J.
Goodman Nathan
Lee Linda O.
Margulies Benson I.
Ellis Kevin L.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Rankin Rory D.
Sun Microsystems Inc.
LandOfFree
Multiprocessor digital data processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprocessor digital data processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor digital data processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326268