Electrical computers and digital processing systems: interprogra – Interprogram communication using message – Agent
Reexamination Certificate
2000-05-11
2004-09-07
An, Meng-Al T. (Department: 2126)
Electrical computers and digital processing systems: interprogra
Interprogram communication using message
Agent
C709S241000
Reexamination Certificate
active
06789258
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of computer systems and, more particularly, to performing a synchronization operation for multiple devices in a computer system.
2. Description of the Related Art
A central resource in a computer system may be configured to perform multiple processing operations simultaneously. The central resource may perform these multiple processing operations by including multiple processing elements, or agents. In some cases, the agents may be synchronized where all agents begin processing at the same time, spend the same amount of time processing, and thus finish processing their tasks at the same time. In other cases, the agents may be unsynchronized where individual agents may begin tasks at different times and may take different amounts of time to perform those tasks.
A central resource that includes multiple agents may receive a varying inflow of work from a variety of devices. As the agents in the central resource finish tasks, they may begin new tasks if new tasks are available or wait for new tasks if no tasks are pending. Agents that are currently performing or processing a task may be termed “busy” while agents that are not performing or processing a task may be termed “idle.” The act of an agent finishing a task, whether or not another task is waiting to be processed, may be termed “cycling.” Accordingly, an agent that has finished its task may be said to have cycled. In order to more efficiently utilize the central resource, the devices that use it need to be able to detect when tasks that have been submitted to the central resource have completed by the agents.
A device may detect the completion of a task or a set of tasks by a central resource by initiating a synchronization operation, referred hereafter as a sync operation. A sync operation may be described as the process of determining when all tasks being performed at a given time have completed. A device that initiates a sync operation may be called an “observer.”
Several possible implementations of a sync operation exist. In one implementation, a system may simply stop processing new tasks until all outstanding tasks have been completed to complete a sync operation. In this case, the sync operation may undesirably delay the processing of new tasks. In another implementation, a system could require that agents signal completion of a task to the device that requested the task by sending a message or an interrupt. This implementation, however, may result in increased traffic on a system bus such that fewer devices may be connected to the bus and included in the system. In a further implementation, each agent could include a state bit that was visible to an observer and that was indicative of whether the agent was busy or not. To perform a sync operation in this implementation, an observer could monitor the state bits for each agent and determine that all tasks have been completed when the state bits indicate that all agents are idle. If the agents receive a steady supply of tasks, however, there is no assurance that all agents would ever be idle and the sync operation may not be able to complete. Yet a further sync operation implementation may involve including a dedicated synchronization resource in the central resource. Such an implementation may not allow multiple observers to be running sync operations concurrently and may not be fully scalable as additional observers may require additional resources to be added to the synchronization resource.
A system and method is needed to efficiently perform a sync operation for multiple devices in a computer system. In addition, a system and method is needed to allow for multiple concurrent sync operations and for scalability in a system that performs a sync operation for multiple devices.
SUMMARY
The problems outlined above are in large part solved by the use the system and method described herein. Generally speaking, a system and method for performing a sync operation for multiple devices in a computer system is provided. The computer system may include a plurality of devices and a plurality of agents. The agents may be configured to perform tasks on behalf of the devices. A busy bit and a counter may be included for each of the agents. One of the devices may become an observer by initiating a sync operation. In response to a sync operation, busy agents may be identified using the busy bit for each agent. The busy agents may then be monitored to determine when each one has cycled using the busy bit and the counter for each busy agent. A busy agent may be determined to have cycled in response to its busy bit indicating that it is no longer busy or in response to its counter value differing from the counter value at the time the sync operation was initiated. Once all of the busy agents have cycled, the observer may determine that the sync operation is complete.
In one particular embodiment, the counter for each agent may comprise a one bit counter. The one bit counters for each agent may be stored in a counter register and the busy bits for each agent may be stored in a busy register. In response to a sync operation, the values in these registers may be monitored to determine when all busy agents have cycled. Once all of the busy agents have cycled, the observer may determine that the sync operation is complete.
Certain embodiments described herein may allow for advantages over other systems and methods that are configured to implement a sync operation. For example, certain embodiments may allow for a relatively inexpensive hardware or software implementation using a busy bit and a counter for each agent in the system. In addition, certain embodiments may be fully scalable for any number of observers and different observers may perform sync operations concurrently without the need for additional hardware.
REFERENCES:
patent: 4590555 (1986-05-01), Bourrez
patent: 5450573 (1995-09-01), Gronemeyer
patent: 5822571 (1998-10-01), Goodrum et al.
patent: 5832254 (1998-11-01), Brewer
patent: 5915111 (1999-06-01), Ouchi
patent: 5958019 (1999-09-01), Hagersten et al.
patent: 6117181 (2000-09-01), Dearth et al.
patent: 6266745 (2001-07-01), de Backer et al.
patent: 6385743 (2002-05-01), Huckfeldt et al.
patent: 0 817 075 (1998-01-01), None
“Lock-Free Garbage Collection for Multiprocessors”, Herlihy, et al,IEEE Transactions on Parallel and Distributed Systems, IEEE Inc., New York, vol. 3, No. 3, May 1, 1992, pp. 304-311.
“Comparing Barrier Algorithms”, Arenstorf, et al,Parallel Computing, Elsevier Publishers, Amsterdam, NL, vol. 12, No. 2, Nov. 1, 1989, pp. 157-180.
“Barrier Synchronization Using Fetch-and-Add and Broadcast”,IBM Technical Disclosure Bulletin, IBM Corp., New York, vol. 34, No. 8, Jan. 1992, pp. 33-34.
“Low-Cost Device for Contention-Free Barrier Synchronization”,IBM Technical Disclosure Bulletin, IBM Corp., New York, vol. 31, No. 11, Apr. 1, 1989, pp. 382-389.
International search report application No. PCT/US01/15269 mailed Dec. 10, 2002.
Jackson Christopher J.
Zak, Jr. Robert C.
An Meng-Al T.
Merkel Lawrence J.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Nguyen Van
Sun Microsystems Inc.
LandOfFree
System and method for performing a synchronization operation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing a synchronization operation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing a synchronization operation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204499