Abstract:
An apparatus and a method for node synchronization that can be used in a heterogeneous computer system where nodes in the system do not share a common system clock. Time stamps, which are critically important, are attached to transaction requests. Time stamps are based on a “time of day” value, which may simply be a register incremented by a system clock. Since each node has its own system clock, the frequency of these clocks may drift which results in variation in the time stamp values. If the values drift too far apart, data updates may be lost. A frequency synthesizer capable of high resolution and rapid frequency adjustments can be connected to system clock. When a shift in phase between the master and slave time of day values is detected, the frequency synthesizer output can be changed by a small amount to bring the two signals back into phase.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present invention is related to the following applications entitled “AN APPARATUS AND METHOD FOR HIGH RESOLUTION FREQUENCY ADJUSTMENT IN A MULTISTAGE FREQUENCY SYNTHESIZER”, U.S. application Ser. No. 09/631,718, now issued as U.S. Pat. No. 6,566,921; “AN APPARATUS AND METHOD FOR DYNAMIC FREQUENCY ADJUSTMENT IN A FREQUENCY SYNTHESIZER”, U.S. application Ser. No. 09/631,720, now issued as U.S. Pat. No. 6,522,207; which are incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     The present invention relates generally to an improved method for system synchronization and in particular to an apparatus and a method for adjusting the time of day clocks in a heterogeneous computer system. Still more particularly, the present invention provides an apparatus and a method for high resolution frequency adjustment for node synchronization that can be used in a non-uniform memory access (NUMA) computer system. 
     2. Description of the Related Art 
     A phase locked loop (PLL) is a very interesting integrated circuit that blends analog and digital techniques. Although the basic design of a PLL has been known for decades, the circuit only became a practical building block in integrated circuit form where the cost has become affordable and the design has become more reliable. 
     The PLL contains a phase detector, an amplifier, a voltage controlled oscillator (VCO), and a feedback loop that allows the output frequency to be a replication of the input signal with noise removed or a multiple of the frequency of the input signal. PLLs have been used for demodulation of FM signals, for tone decoding, for frequency generation, for generation of “clean” signals, and for pulse synchronization, to name but a few of the applications. Because the output frequency is a multiple of the input frequency, it is difficult to make fine frequency adjustments using such a frequency synthesizer. 
     A non-uniform memory access (NUMA) computer system is a multiple processor architecture where there is a single memory address space but where memory is separated into “close” banks of memory and “distant” banks of memory. Access is “non-uniform” because the access times for the close banks of memory directly associated with the node that contains the CPU are much faster than the access times for distant memory banks at other nodes in the system. A distinct advantage of a NUMA architecture is that it scales well, in the sense that adding more nodes and processors to the system does not create bottlenecks that degrade performance in the same way as other parallel architectures. 
     One problem with NUMA architectures is to keep the nodes synchronized. Transactions are often labeled with time stamps that are generated by the time of day at each node in the system. Since these nodes have independent clocks, even though they are initialized at precisely the same time, they will eventually drift apart and require re-synchronization. It is important to have precise time stamps with as little “cycle slippage” as possible between the nodes. 
     Therefore, it would be advantageous to have a method for high resolution frequency adjustment for node synchronization that can be used in a non-uniform memory access (NUMA) computer system. 
     SUMMARY OF THE INVENTION 
     An apparatus and a method is presented for node synchronization that can be used in a heterogeneous computer system where nodes in the system do not share a common system clock. A non-uniform memory access (NUMA) computer system is one such system where this method and apparatus can be applied. 
     Transactions in a multiprocessor computer system must be coordinated precisely for correct operation. Time stamps are attached to transaction requests and when data is changed in the system, the relative values of time stamps are critically important. These time stamps are based on a “time of day” value, which may simply be a register incremented by a system clock. Since each node has its own system clock, the frequency of these clocks may drift which results in variation in the time stamp values. If the values drift too far apart, data updates in the multiprocessor computer system may be lost. 
     This invention monitors the relative phase of a “master” time of day register with one or more “slave” time of day registers. A frequency synthesizer capable of high resolution and rapid frequency adjustments can be connected to system clock. When a shift in phase between the master and slave time of day values is detected, the frequency synthesizer output can be changed by a small amount to bring the two signals back into phase. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: 
     FIG. 1 is a pictorial representation of a multiprocessor system with a non-uniform memory access (NUMA) architecture in which the present invention may be implemented; 
     FIG. 2 illustrates multiple nodes in a NUMA architecture in which the present invention may be implemented; 
     FIG. 3 shows a conventional frequency synthesizer as it exists in the prior art; 
     FIG. 4 shows a plot of instantaneous frequency error versus instantaneous phase error for a conventional frequency synthesizer; 
     FIG. 5 shows a frequency synthesizer as it exists in a preferred embodiment of this invention; 
     FIG. 6 shows a three stage frequency adjuster in accordance with a preferred embodiment of this invention; 
     FIG. 7 shows the detailed circuitry of a dynamic frequency divider as it exists in a preferred embodiment of this invention; and 
     FIG. 8 is a plot for phase and frequency adjustments as a function of time in accordance with a preferred embodiment of this invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     With reference now to the figures, and in particular with reference to FIG. 1, a pictorial representation of a multiprocessor system with a non-uniform memory access (NUMA) architecture. This simplified diagram shows a system with three nodes:  100 ,  120 , and  140 . Node  100  contains four CPUs,  102 ,  104 ,  106 , and  108 , local memory  110 , input/output channels  112 , and communications channels,  114 . Node  120  contains four CPUs,  122 ,  124 ,  126 , and  128 , local memory  130 , input/output channels  132 , and communications channels,  134 . Node  140  contains four CPUs,  142 ,  144 ,  146 , and  148 , local memory  150 , input/output channels  152 , and communications channels,  154 . 
     External disk drive  156  is connect to input/output channel  152 . The nodes are interconnected using high speed channels  116  and  136 . This system contains a single address space composed of memory banks  110 ,  130 , and  150 . Access of a CPU to its local memory bank, such as CPU  102  accessing memory  110 , will be very fast since it does not need to use the node interconnections  116  or  136 . Access by a CPU to a distant memory bank, such as CPU  102  accessing memory  130 , will be slower since data must be transferred on communications channel  116 . 
     Those of ordinary skill in the art will appreciate that the hardware depicted in FIG. 1 may vary. For example, the nodes may be arranged in a hypercube network where the number of nodes is a power of two (2 n ) and each node is connected to exactly n other nodes. For example, each node in a hypercube with 16 nodes would be connected to four other nodes. The depicted example in FIG. 1 is less complex than this and is not meant to imply architectural limitations with respect to the present invention. 
     FIG. 1 is intended as an example and not as an architectural limitation for the processes of the present invention. The type of processor in a NUMA system may be homogeneous, but the present invention is also applicable to a heterogeneous system where processors or computers of different types are all part of multiprocessor computing environment. It is assumed these separate processors do not share a common clock so there relative frequencies can shift, as illustrated in FIG. 2 given next. 
     FIG. 2 illustrates multiple nodes in a NUMA architecture, such as the architecture shown in FIG.  1 . The n nodes are labeled Node  0 , Node  1 , Node  2 , and so forth through Node n- 2 , and Node n- 1 . Each node has an independent frequency source denoted f 0  through f n−1 . These frequency sources are used to generate the timestamp stored in the time of day (TOD) register. Since these nodes have independent clocks, even when the timestamps are initialized at precisely the same time, they will eventually drift apart and require re-synchronization. 
     Even if the nodes are architecturally similar, one of the nodes needs to be designated the master, in this diagram Node  0 , and the other nodes are “slaves” , in the sense that their time of day is re-synchronized to the “master” time of day. It is important to have precise frequency generation with as little “cycle slippage” as possible between the nodes. What is required is a frequency generation system with the possibility of making fine adjustments to the system clock frequency on a dynamic basis so that the time of day register value can be changed. 
     FIG. 3 shows a conventional frequency synthesizer as it exists in the prior art. The input to the phase locked loop is reference frequency  302 . Frequency divider  304  divides the reference frequency by K 2 , which is an integer value in the range of 1, 2, . . . , N 2 . The output of frequency divider  304  is fed into phase detector  306 . The other input to the phase detector will be discussed below. The output of phase detector  306  is fed into charge pump  308 . The charge pump creates a current for the period of time during which the phase error exists, which is integrated by capacitor Cl  310  to create a voltage Vc which is fed into voltage controlled oscillator (VCO)  312 . VCO output is the frequency output from the circuit and equals (K 1 /K 2 ) f ref . This signal is fed into frequency divider  316  that divides f out  by K 1 , which is an integer value in the range of 1, 2, . . . , N 1 . The output of frequency divider  316  equals f ref /K 2  at steady-state and this is the second input to phase detector  306 . This completes the feedback loop. Since both inputs to phase detector  306  equal f ref /K 2 , any shift in one of these frequencies will be detected by phase detector  306  and feed through charge pump  308  to voltage controlled oscillator  312 . This results in f out  being adjusted to bring it back into sync to a value (K 1 /K 2 ) f ref . 
     The values of K 1  and K 2  must be fixed to avoid cycle-slipping due to PLL pullout frequency. The value of f out  is equal to (K 1 /K 2 ) f ref . By setting K 1  and K 2  to different integer values, the output frequency is synthesized based on the input frequency. However, these values cannot be changed dynamically, as explained below. 
     FIG. 4 shows a plot of instantaneous frequency error versus instantaneous phase error. A pure frequency error introduced from the steady-state condition at the origin will cause cycle slippage if it exceeds the pullout frequency of approximately 2.5 MHz. In FIG. 4 it can be seen that frequency deviations less than the pullout frequency will naturally go back towards the origin, however, frequency deviations greater than the pullout frequency will result in large instantaneous frequency errors and cycle slipping when the divider settings K 1  and/or K 2 , as shown FIG. 3, are changed. Therefore, when using a conventional phase locked loop, the values of K 1  and K 2  are fixed which makes fine adjustments of the output frequency impractical. 
     FIG. 5 shows a frequency synthesizer as it exists in an embodiment of this invention. As in FIG. 3 the input is still f ref  and the output is (K 1 /K 2 ) f ref . The major difference is that the divide by K 2  frequency divider is moved from the input of the circuit to the output of the circuit. As is detailed in the explanation below, this allows the value of K 2  to be varied which results in the ability to make fine adjustments to the output frequency. Such adjustments are not possible using the circuit in FIG. 3 due to the problem of cycle slipping. 
     The input to the phase locked loop is reference frequency  502 , which is fed into phase detector  504 . The other input to the phase detector will be discussed below. The output of phase detector  504  is fed into charge pump  506 . The charge pump creates a current for the period of time during which the phase error exists, which is integrated by capacitor C 1   310  to create a voltage Vc which is fed into voltage controlled oscillator (VCO)  512 . VCO output equals K 1  f ref . This signal is fed into frequency divider  516  that divides it by K 1 , which is an integer value in the range of 1, 2, . . . , N 1 . The output of frequency divider  516  equals f ref  and this is the second input to phase detector  504 . This completes the feedback loop. Since both inputs to phase detector  506  equal f ref  any shift in one of these frequencies will be detected by phase detector  504  and fed through charge pump  508  to voltage controlled oscillator  512 . 
     Circuit output f out    514  is generated by feeding the output of VCO  510  into frequency divider  512  which divides its input by K 2  to produce the value (K 1 /K 2 ) f ref . This is the same output value as the circuit in FIG. 3, but there is one major difference. The value of K 2  can be varied without causing cycle slipping. 
     Of particular interest is the case where K 1 , is approximately equal to K 2  so that the ratio K 1 /K 2  is equal to 1 plus or minus a small delta factor. Substituting these values in the equation for the output frequency results in f out =(1±Δ)f ref . So by varying the value of K 2 , which can be changed without cycle slipping, the output frequency can be adjusted up or down by small amounts relative to the input frequency. 
     The circuit in FIG. 5 can be cascaded to produce even finer frequency adjustments. A three stage frequency adjuster is shown in FIG.  6 . The front end of stage  1  is a conventional frequency synthesizer, similar to that shown in FIG.  3 . In particular, frequency divider  602  divides the input frequency, f ref , by L. This is fed to the forward path of phase lock loop  604 , which contains a phase detector, such as  306 , a charge pump, such as  308 , a capacitor, such as  310 , and a voltage controlled oscillator, such as  312 . In FIG. 6 these components are lumped together and referred to as a phase lock loop. 
     To close the loop, the output of phase lock loop  604  is fed through frequency divider  606  where the division is by K 1 . This output is fed back as the second input to the phase detector that is part of phase lock loop  604 . The frequency output from this conventional frequency synthesizer is K 1  f ref /L, where both K 1  and L are fixed. 
     To allow for dynamic frequency adjustment, the output of phase lock loop  604  is the input to frequency divider  608  that divides its input frequency by K 2 . The value for K 2  can be varied dynamically, in a manner similar to the dynamic adjustments to frequency divider  512  in FIG.  5 . The detailed circuitry of this dynamic frequency divider are disclosed in FIG.  7 . The output from stage  1  of the three stage frequency adjuster is (K 1  f ref )/(K 2  L) where K 1  and L are fixed and K 2  is variable label this output as f 2 . 
     Stage  2  of the three stage frequency adjuster contains the forward path of phase locked loop  610 , the feedback circuit with frequency divider  612  that divides by K 3 , and the frequency divider  614  at the output that divides by K 4 . The frequency output of stage  2  equals (K 3 /K 4 ) f 2 ; this frequency is referred to as f 3 . The value of K 3  is fixed but the value of K 4  is variable. 
     Stage  3  of the three stage frequency adjuster has the same structure as stage  2 . It contains the forward path of phase locked loop  618 , feedback loop with frequency divider  620  that divides by M, and frequency divider  622  on the output that divides by N. The frequency output, f out , of this final stage equals (M/N) f 3 . The values of M and N are both fixed. 
     Substituting the various formulas for each stage of the circuit, it can be seen that f out =(K 1 /K 2 ) (K 3 /K 4 ) (M/N) (f ref /L) where K 2  and K 4  are variable. It is instructive to substitute typical frequency values to see how the output frequency can be tuned with high refinement. Let f ref  be 150 MHz. The values of the various dividers will be chosen so that the output frequency will also be 150 MHz, but by varying the values of K 2  and K 4 , fine adjustments can be obtained. L, K 1 , and K 3  are set to 100. M and N are set to 200 and 2, respectively. In case  1 , K 2  is set to 119 and K 4  is set to 84. The resultant output frequency is 150.06 MHz; this is a change of +60,000 Hz for 150 MHz or +400 parts per million (PPM). In case  2 , K 2  is set to 122 and K 4  is set to 82. The resultant output frequency is 149.94 MHz; this is a change of −60,000 Hz for 150 MHz or −400 PPM. 
     By carrying through the calculations stage-by-stage, it is found the frequency shifts at stage  2  are less than 2.5% and at stage  3  are less than 0.08%. As one of ordinary skill in the art will appreciate, greater refinement of frequency adjustment can be obtained when more stages are cascaded. The frequency divider at the output of each stage, except for the last stage, can be made variable. 
     Frequency dividers in the prior art are hardwired to a particular divisor value. Therefore, a new circuit had to be devised that could divide by any integer value and that could change the divisor value very quickly. 
     With reference now to FIG. 7, a circuit diagram is given for a dynamic frequency divider. REG_A  704  holds the divisor, call it K. REG_B  712  holds the current counter value. REG_OUT  716  is a one-bit register that holds the output state. All three registers are clocked synchronously by the input frequency. MUX (multiplexer)  702  has two inputs, NEW_K and CURRENT_K, and one of these is selected based on the value of CHANGE_K. When CHANGE_K is activated, the output of the MUX is the input NEW_K. If CHANGE_K is not activated, then the output of the MUX is input CURRENT_K. 
     Comparator A&gt;B COMP  706  is on whenever the current counter value is less than the current divisor value. Whenever the comparator  706  is on, the incrementer INC  710  increases the counter value by 1 and saves the new value in REG_B  712 . The output state based on the setting of REG_OUT  716  remains the same. When the counter value exceeds the divisor value, then the output of comparator  706  is off, which causes the incrementer to be set back to 1 and the value of REG_OUT  716  to be toggled resulting in the output frequency changing state. 
     Examination of particular frequency values helps understand operation of this circuit. Suppose the output of the multiplexer is a divisor value of 120 and the value in REG_B  712  has just been reset, so REG_B  712  counts from the value 1 up to the divisor value. When this counter equals the divisor value, it triggers the output of A&gt;B COMP  706  to change state. This has two effects: it resets the value in REG_B to 1 and it toggles the output frequency from REG_OUT  716 . For every  120  pulses on the input, there is one pulse on the output. So the circuit functions like a “divide by 120” circuit. 
     Suppose that the value of NEW_K is 110 and the CHANGE_K command is received; this transfers the value of 110 to the “A INPUT” of the multiplexer. There are two possible cases: the counter value in REG_B is less than 110 or the counter value is between 110 and 120. If the case the counter is less than 110, REG_B  712  continues to count but now will be reset when 110 is reached. If the value in REG_B is already greater than 110, then the output of comparator A&gt;B COMP is switched which results in toggle of the output frequency and a reset of the counter. 
     As one of ordinary skill in the art will appreciate, the case where NEW_K is larger than CURRENT_K is even easier. The current counter value is less than NEW_K, so once the multiplexer switches the input to the comparator, the counter will continue to count up until the new divisor value is reached. 
     With reference now to FIG. 8, a plot is given for phase and frequency adjustments as a function of time. The phase of the slave frequency φ s  appears as sawtooth  802  at the top of the figure while the phase of the master frequency φ m  appears as horizontal line  804 . The term “phase” here is not to be interpreted in an analog sense, rather it is applied to the digital contents of the two time of day registers. There registers are incremented by their respective system clocks, so as these clock frequencies slowly drift apart, the register values represent the accumulation of the phase slippage between the two clocks. The phase of the slave frequency is initially declining and will eventually cross the phase of the master frequency. Once this crossing is detected, the clock frequency of the slave will be adjusted. 
     The master frequency f m  appears as horizontal line  806  at the bottom of the figure. Slave frequency  808  is shown as a dashed line at the bottom of the figure; it is shown initially 200 PPM greater than the master frequency  806 . Vertical dashed lines  810 ,  812 ,  814 ,  816 ,  818 ,  820 ,  822 , and  824  indicate the times that the phases of the master and slave signals are compared and, when required, corrections are applied. 
     At times  810 ,  812 ,  814 , and  816  the phase of the slave  802  is greater than the phase of the master  804 . During these same intervals, the frequency of the slave  808  is 200 PPM greater than the frequency of the master  806 . At synchronization time  818 , the phase of the slave  802  is less than the phase of the master  804 . When this is detected, the variable dividers in the multistage frequency synthesizer associated with the slave are adjusted to produce a frequency of the slave  808  200 PPM less than the frequency of the master  806 . This causes the phase of the slave  802  to rise quickly until at time  820  it is again greater than the master. This causes the frequency of the slave  808  to switch between being 200PPM less than the master  806  to being 200 PPM greater than the master. During time intervals  822  and  824  the phase of the slave  802  is still greater than the phase of the master  804 , so the frequency of the slave  808  remains at 200 PPM greater than the frequency of the master  806 . 
     As one of ordinary skill in the art will appreciate, once the phase of the slave  802  becomes less than the phase of the master  804 , the frequency of the slave  808  will drop to 200 PPM less than the frequency of the master  806  to bring the system back into balance. This continual detection of phase differences and resulting frequency adjustments will keep the time of day registers synchronized during the operation of the computer system. If these adjustments were not made, over a longer period of time the register discrepancies would become so large as to cause system malfunctions as a result of timestamp problems. However, since these synchronization times occur every thousand clock cycles or so in a typical embodiment, the time of day values never shift enough to cause any serious problems. Solutions to this problem in the prior art involved expensive hardware, such as using an external atomic clock, to provide synchronization. Using this invention, two or more time of day registers at different nodes in a multiple processor system can be synchronized with a minimum of additional hardware. 
     The description of the present invention has been presented for purposes of illustration and description but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.