Electrical computers and digital processing systems: support – Synchronization of clock or timing signals – data – or pulses
Reexamination Certificate
2000-02-29
2003-09-09
Lee, Thomas (Department: 2185)
Electrical computers and digital processing systems: support
Synchronization of clock or timing signals, data, or pulses
C709S248000, C709S241000, C375S356000
Reexamination Certificate
active
06618815
ABSTRACT:
PARTIAL WAIVER OF COPYRIGHT
All of the material in this patent application is subject to copyright protection under the copyright laws of the United States and of other countries. As of the first effective filing date of the present application, this material is protected as unpublished material. However, permission to copy this material is hereby granted to the extent that the copyright owner has no objection to the facsimile reproduction by anyone of the patent documentation or patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
CROSS-REFERENCE TO RELATED APPLICATIONS
Not Applicable
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and apparatus for a distributed parallel processing system in which there is a need for a single Time Of Day (TOD) or incrementor to synchronize (order) events across the different processors.
2. Description of the Related Art
To order events accurately that occur on a distributed processing system, the difference between TODs read on two different processors simultaneously must be less than the smallest latency for a message between the two processors, and must be continuously increasing. Today this is done by either having a single central TOD repository or by running the entire system off a single clock propagated to all the processors (nodes). The central repository has the disadvantage of being a bottleneck to processing because all nodes need to query this single node, and as a consequence, all these queries are serialized, reducing the speed up that is intended to be achieved by parallelizing the application. Using a single system oscillator that is propagated through the system has the disadvantage of requiring specific links between nodes to be operational, or the system fails. Since on a large distributed system these links are required to be cables that can be accidently pulled, a real concern exists.
SUMMARY OF THE INVENTION
The present invention overcomes the disadvantages of the known art by a hardware and software implementation that allows all the processing nodes to increment their TOD off a local oscillator and keeps them within the minimum latency by broadcasting periodic updates. In essence, the invention provides a TOD incrementor throughout a distributed system without requiring a clock to be distributed, and with a maximum difference less than the minimum latency, as opposed to prior art solutions that either had a larger maximum difference or distribute a clock to run the TOD synchronously. Through the use of the present invention, the reading of the TOD to all of the processing nodes is distributed thereby removing the need for a single centralized TOD source. The present invention also removes the need for specific cables being operational (as in a single system oscillator design). As long as there is a path from a “TOD Master Chip” to a node, the TOD is kept within tolerance.
The present invention utilizes a switch design that is implemented in hardware and software to accurately update and distribute a received TOD to all its neighbors. The method and apparatus of the present invention includes the capability of calculating the delay of the cables connected to the switch designated as the “TOD Master Chip”, and the capability to receive a special TOD broadcast packet and update it with the calculated cable delay. The invention further includes the capability to adjust the local TOD to the received broadcast value without decrementing the value, and the capability to send the TOD broadcast packet to all it neighbors. The last-mentioned capability serves to detect whether the neighbor has already received a specific update, in which case, the received packet is discarded (ending the feedback loop).
In the method and apparatus of the present invention, the TOD adjustments can be simple loads of the received broadcast when the newly received value is greater than the local copy. However, if the local copy is greater than the received broadcast, the local copy must be held or incremented at a slower rate until the difference is removed (in the design according to the invention, the local value is incremented at a fractional value, e.g. half speed, until it matches the received value which is being incremented at normal speed).
From a system perspective, the invention is implemented with the capability to select a single switch or node to be the “TOD Master Chip”. This “TOD Master Chip” periodically initiates a TOD broadcast by sending TOD broadcast packets to all of its neighbors. The TOD broadcast packet contains the current TOD value and a sequence number (used to detect feedback loops). The TOD broadcast packet may also include a flag indicating that it is a TOD broadcast packet, rather than a normal data packet, and may also include a checksum to detect errors in the packet. For system reliability, a backup that monitors the “TOD Master Chip” and takes over its function when that chip fails may be provided.
REFERENCES:
patent: 4531185 (1985-07-01), Halpern et al.
patent: 4882739 (1989-11-01), Potash et al.
patent: 4890222 (1989-12-01), Kirk
patent: 5327468 (1994-07-01), Edblad et al.
patent: 5416808 (1995-05-01), Witsaman et al.
patent: 5504878 (1996-04-01), Coscarella et al.
patent: 5530846 (1996-06-01), Strong
patent: 5537549 (1996-07-01), Gee et al.
patent: 5579513 (1996-11-01), Strohmer
patent: 5636373 (1997-06-01), Glendening et al.
patent: 5712882 (1998-01-01), Miller
patent: 5925107 (1999-07-01), Bartfai et al.
patent: 6246701 (2001-06-01), Slattery
patent: 6449291 (2002-09-01), Burns et al.
patent: WO 9856135 (1998-12-01), None
Abali, B., Stunkel, C.B., and Benveniste, C., “Clock Synchronization on a Multicomputer”, Journal of Parallel and Distributed Computing, vol. 40, pp. 119-130 (1997).*
Abali, B. and Stunkel, C.B., “Time Synchronization on SP1 and SP2 Parallel Systems”, Parallel Processing Symposium, pp. 666-672, (1995).
Atkins Mark G.
Herring Jay R.
Cutter Lawrence D.
Fleit Kain Gibbons Gutman & Bongini P.L.
Gibbons Jon A.
Lee Thomas
Wang Albert
LandOfFree
Accurate distributed system time of day does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accurate distributed system time of day, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurate distributed system time of day will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3014110