Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1998-10-23
2002-05-28
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S150000, C711S163000
Reexamination Certificate
active
06397306
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to distributed memory multiprocessor architectures, and more particularly to methods and devices for providing atomic access in distributed memory multiprocessor architectures.
In distributed memory multiprocessor architectures, also known as non-uniform memory architectures (NUMAs), each processor has a direct physical connection to a local memory associated with the processor and an indirect physical connection to remote memories associated with other processors. The physical connections are used for executing read and write transactions. To sustain operation within such an architecture, any read-modify-write sequence initiated at a shared memory location must be completed before another such sequence is initiated in the memory location. This typically requires that a processor conducting a read-modify-write sequence have exclusive, or “atomic”, access to the shared memory during the interval in which the sequence is executed. Conventionally, atomic access has been ensured through global blocking. In global blocking, all processors except one granted atomic access are inhibited from using any shared transmission medium in the architecture during the atomic access interval. That way, the inhibited processors are unable to disrupt the read-modify-write sequence in progress.
Global blocking has obvious disadvantages in terms of efficiency. Sustained operation only demands that a processor executing a read-modify-write sequence have atomic access to a particular memory during an interval. However, global blocking prevents other processors from accessing any memory during an atomic access interval. Global blocking therefore results in gross underutilization of shared transmission media and memory resources. This underutilization yields slower operating performance.
Accordingly, there is a need for methods and devices for providing atomic access to shared memories in distributed memory multiprocessor architectures which do not suffer from the disadvantages of global blocking.
SUMMARY OF THE INVENTION
In its most basic feature, the present invention provides “per memory” atomic access for a distributed memory multiprocessor architecture. A bit mask having a plurality of bits is retained for each shared memory to indicate the access privileges of a plurality of processors to the memory. A processor has access privileges to a shared memory if the bit mask retained for the memory is marked at a bit position reserved for the processor and does not have access privileges if the bit mask is not so marked. A processor must establish and confirm access privileges before initiating a read-modify-write sequence in the shared memory. If the processor is able to establish and confirm access privileges, the processor may initiate the sequence. However, if the processor is unable to establish and confirm access privileges, the processor may not initiate the sequence. A bit mask is permitted to have only one mark at a given time to guarantee that access to each shared memory is atomic.
In a preferred atomic access establishment and confirmation protocol, when a processor wishes to initiate a read-modify-write sequence in a shared memory, the processor attempts to establish atomic access by issuing a write instruction to mark the bit mask retained for the memory at the processor's reserved bit position. The write is successful if the bit mask is not already marked. However, the write is unsuccessful if the bit mask is already marked. The processor attempts to confirm atomic access by reading the bit mask. If the bit mask is marked at the processor's reserved bit position, atomic access is confirmed. If the bit mask is not marked at the processor's reserved bit position, atomic access is not confirmed.
REFERENCES:
patent: 5175829 (1992-12-01), Stumpf
patent: 5297269 (1994-03-01), Donaldson et al.
Ciavaglia Stephen
Spang Edward
Szajner, Jr. Edward C.
Zaifman Arthur L.
Alcatel Internetworking, Inc.
Reader, Esq. Scot A.
Verbrugge Kevin
LandOfFree
Per memory atomic access for distributed memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Per memory atomic access for distributed memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Per memory atomic access for distributed memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2894879