US 7,640,315 B1Granted

Implementing locks in a distributed processing system

AssigneesAdvanced Micro Devices, Inc., Alpha Processor, Inc.

InventorsDerrick R. Meyer, Jonathan M. Owen, Mark D. Hummel, James B. Keller

Life of this patent

Estimating the term…

Loading patent…

Abstract

A messaging scheme to synchronize processes within a distributed memory multiprocessing computer system having two or more processing nodes interconnected using an interconnect structure of dual-unidirectional links. Each unidirectional link forms a point-to-point interconnect to transfer packetized information between two processing nodes. A lock acquisition request from a lock requesting node is placed into service by an arbitrating node when no previous lock requests are pending for service. The arbitrating node transmits a broadcast message to all nodes in the system, which, in turn, respond with a corresponding probe response message to inform the arbitrating node of cessation of issuance of new requests by the node sending the probe response message. The arbitrating node informs the lock requesting node of the requesting node's lock ownership by transmitting a target done message thereto. After completion of lock operations, the lock requesting node sends a lock release request to the arbitrating node, which, in turn, informs all processing nodes of lock release by transmitting another broadcast message within the system. The messaging protocol is completed when each node sends another probe response to the arbitrating node, which, in turn, sends a final target done message to the lock requesting node. Lock operations are performed without contention for system resources and without deadlocks among various processing nodes.

Claims15

Dependent claims

In a multiprocessing computer system comprising a plurality of processing nodes interconnected through an interconnect structure, wherein the plurality of processing nodes includes a first processing node, a second processing node, and a third processing node, a method for lock request arbitration comprising:

receiving a lock request at the second processing node from the first processing node;
determining, at the second processing node, whether the lock request is ready for service, wherein determining whether the lock request is ready for service comprises the second processing node placing the lock request in a queue and the second processing node monitoring the queue to determine whether the lock request is ready for service;
issuing a broadcast message from the second processing node to the first and the third processing nodes in response to determining that the lock request is ready for service, wherein the broadcast message informs the third processing node of servicing of the lock request, and wherein the broadcast message includes a lock bit to inform the third processing node of the servicing of the lock request;
receiving a first probe response at the second processing node from the first processing node in response to sending the broadcast message;
receiving a second probe response at the second processing node from the third processing node in response to sending the broadcast message, wherein the probe response is sent from the third processing node in response to the third processing node ceasing issuance of new requests;
in response to receiving the first and second probe response messages, granting lock ownership to the first processing node and transmitting from the second processing node to the first processing node a lock response message to inform the first processing node of the lock ownership.

3 more elements

A multiprocessing computer system comprising:

a plurality of processing nodes interconnected through an interconnect structure to each other and to shared system resources, wherein the plurality of processing nodes comprises:
a first processing node configured to generate a lock request prior to commencing execution of an operation required access to the shared system resources;
a second processing node;
and
a third processing node configured to receive and process the lock request, and transmit a first broadcast message to the first and the second processing nodes in response to determining that the lock request is ready for service, wherein the third processing node comprises a queue for pending lock requests, wherein the third processing node is configured to place the lock request in the queue and to monitor the queue to determine when the lock request is ready for service, wherein the first broadcast message comprises a lock bit, wherein the third processing node is configured to set the lock bit in response to determining the lock request ready for service;
wherein each of the first and the second processing nodes is configured to transmit a corresponding first probe response message to the third processing node in response to receiving the first broadcast message, wherein the second processing node is further configured to cease issuance of new requests and to transmit the corresponding first probe response message upon the cessation of the issuance;
wherein, in response to receiving the corresponding first probe response message from the first and the second processing nodes, the third processing node is configured to grant lock ownership to the first processing node and transmit lock response message to the first processing node to inform the first processing node of the lock ownership.

4 more elements

Dependencies are inferred from the claim text.