Electrical computers and digital processing systems: support – Synchronization of clock or timing signals – data – or pulses – Using delay
Reexamination Certificate
2000-01-20
2003-04-22
Butler, Dennis M. (Department: 2185)
Electrical computers and digital processing systems: support
Synchronization of clock or timing signals, data, or pulses
Using delay
C713S503000
Reexamination Certificate
active
06553504
ABSTRACT:
FIELD OF THE INVENTION
The present invention is concerned with multiprocessor system in which the processors operate together to perform coordinated calculations; more specifically, the present invention is concerned with methods and apparatus for clock synchronization among the processors.
BACKGROUND OF THE INVENTION
A system called the Supercomputer Toolkit is known in the art and in the literature. Reference is made to H. Abelson, et al., “The Supercomputer Toolkit: A general framework for special-purpose computing,” International Journal of High Speed Electronics, Vol. 3, Nos. 3 and 4, pp 337-361, 1992, and J. Katzenelson, et al., “The Supercomputer Toolkit and Its Applications,” EE Memo 1165, Department of Electrical Engineering, Technion, June 1998.
The Supercomputer Toolkit is a family of hardware and software modules from which high-performance special-purpose computers for scientific/engineering use can be easily constructed and programmed. The hardware modules include processors, memory, I/O and communication devices; the software modules include an operating system, compilers, debuggers, simulators, scientific libraries, and high-level front ends.
The following example illustrates the use of the Supercomputer Toolkit. When faced with a suitable problem, the engineer/scientist connects the modules by means of static-interconnect technology (ribbon cables) and constructs a parallel computation network. The network is loaded from a workstation that serves as a host. The program is run; the results are collected and displayed by the host. The host handles files, does compilation, etc. The computation network, the hardware portion of the Toolkit, does the heavy computation.
An interesting and important characteristics of the Toolkit's parallel computation network is its high-speed communication links. In general, the Toolkit comprises a plurality, often very many processor boards. Each of the links connects between two or more processor boards. The computation network can be viewed as a graph where the nodes (vertices) are processors (each processor is a board) and the branches (arcs) are the high-speed links. This structure is described, for example in the second reference cited above. This reference reports maximum communication rate of 0.5 Gigabit per second per link (or per processor port) and claims that with better design the maximum rate per link is the rate in which data can be retrieved/stored from/in memory.
The high speed of the communication is based on the synchronization of all processors in the computation networks. This synchronization means the following:
a. The clocks of all processors have the same frequency. This is referred to herein as “frequency sychronization”.
b. The phase difference between the clocks of an two neighbors is less than a certain amount called &dgr;, which is the tolerance or the phase difference that allows bidirectional synchronous communication between adjacent neighbors. This condition is referred to herein as “phase synchronization”.
c. The instructions of all neighbors have to be synchronized in the sense that if a processor sends data to a second processor to which it is connected (and phase synchronized) by a ‘write’ instruction, a ‘read’ instruction has to appear in the second processor's program at the exactly the right place that enables reading the information sent to it. This condition is referred to herein as “instruction synchronization.”
Two Toolkit systems have been implemented and published. One of these, referred to herein as the “MIT Toolkit” is described in the above referenced Abelson et al. reference; the other is referred to herein as the “Technion Toolkit” is described in the Katzenelson, et al. reference.
The two Toolkit systems implemented frequency synchronization by having one clock generator whose signal is distributed to all processor boards. Phase synchronization was achieved by hand trimming of the length of the wire that distributes the clock. Instructional synchronization was achieved somewhat differently in MIT Toolkit and the Technion Toolkit. The MIT Toolkit has data independent instructions (i.e., the time required to carry out an instruction is independent of the data) and therefore, if all processors are started together they remain synchronized. The Technion Toolkit relied on a synchronization line, as described in the Abelson, et al., reference. The MIT Toolkit also had a synchronization line that could be used for instruction synchronization. Note that both Toolkit systems are meant to run one program at a time; that program is parallelized and put on all processors. Thus, the support of instructional synchronization is relatively simple for a phase synchronized Toolkit system, while for a general purpose distributed computing system that supports several independent programs at a time the support of instruction synchronization is not straight forward, to say the least.
In the Toolkit systems the processors are inter alia arranged in a general network, i.e., which may include a series of ring or loop configurations. In this manner these systems different from synchronized systems of the prior art, in which a tree structure is utilized. In such tree structure systems, the synchronization between one processor and a second adjacent processor is relatively independent of the synchronization of the adjacent processor and other processors to which it is connected. For loop connected processor systems, the phase synchronization between adjacent processors must be preserved all around the loop. For large or complicated loop systems, the achievement of phase synchronization is difficult to achieve by hand.
One major drawback of the existing synchronous systems is thus seen to be the requirement to hand-trim the clocks to achieve the phase synchronization. Furthermore, this requirement limits the use of the Toolkit to systems in which there is no change in the timing of the clocks or of the transit time between the processors.
Communication engineers are well aware that, given the maximum speed of the clocks, synchronous communication is the best type of connection between processors. In most common communication environments, however, frequency, phase and instruction synchronization cannot always all be satisfied. Therefore, sophisticated asynchronous algorithms have been developed that approach the performance of synchronous communication as the length of the message are increased. These asynchronous methods require instrumentation and/or introduce latency.
SUMMARY OF THE INVENTION
One aspect of some preferred embodiments of the present invention is concerned with a systematic method for providing phase synchronization between clocks of neighbors in a network containing loops. Preferably, the phase synchronization is achieved automatically.
One aspect of some preferred embodiments of the invention is concerned with reducing the phase difference between adjacent processors. If the phase difference between any two processors in the network is within ±T/4 (where T is the period of the clock), a preferred method of the invention reduces the phase difference between any pair of neighbors to less than a desired amount &dgr;. In a preferred embodiment of the invention, this starting point is achieved by increasing T until the condition is met. Preferably, the phase difference is then decreased, and T decreased to a desired clock rate.
When implementable, synchronous communication is both fast and simple. Note that implementing the method depends on the ability to measure phase differences between neighbor processors; that ability requires transmission lines of substantially time-invariant delay. For a Toolkit-like supercomputer, where a few dozens (or few hundreds or more) processors occupy a room, such transmission lines are available and the conditions can be satisfied. Synchronous transmission may be achieved with stable or with slowly varying phase differences. When the phase between processors varies slowly, the system can track the changes and continuously adjust the phase betwe
Erez Doron Moshe
Katzenelson Jacob
Butler Dennis M.
Fenster & Company
LandOfFree
Clock synchronization of multiprocessor systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Clock synchronization of multiprocessor systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clock synchronization of multiprocessor systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102253