Title of Invention

''A SYSTEM FOR MONOTONIC TIME SYNCHRONIZATION FOR A MULTINODE DATA PROCESSING SYSTEM"

Abstract

In a multi-node non-uniform memory access (NUMA.) multiprocessor system, a designated node synchronization processor on each node, is synchronized. Individual nodes accomplish internal synchronization of the other processors on each node utilizing well known techniques. Thus it is sufficient to synchronize one processor on each node. Node zero, a designated system node that acts as a synchronization manager, estimates the time it takes to transmit information in packet form to a particular, remote node in the system. As a result a time value is transmitted from the remote node to node zero. Node zero projects the current time on the remote node, based on the transmission time estimate and compares that with its own time and either updates its own clock to catch up with a leading remote node or sends a new time value to the other node, requiring the remote node to advance its time to catch up with that on node zero. Code on the remaining nodes is mostly passive, responding to packets coming from node zero and setting the time base value when requested. Monotonicity of the time bases is maintained by always advancing the earliest of the two time bases so as to catch up with the later one.

Full Text

A Method and system for nwnotric time syncheonization for a multinode dada procesing system. 1. Technical Field: The present invention relates in general to a data processing system and in particular to a multi-processor data processing system. Still more particularly, the present invention relates to scalable shared memory multi- processor data processing systems. 2. Description of the Related Art: Symmetrical multiprocessing (SMP) and Non-Uniform Memory Access (NUMA.) architecture are scalable data processing technologies that utilize multiple processors and shared memory to handle large applications or multiple applications at the same time. Scalable shared memory multi-processors are often built by interconnecting symmetric shared memory multi-processor systems with relatively small numbers of processors per system with an interconnect that maintains cache coherency. Doing so makes good use of other, pre-existing and often high volume products to create larger systems. The result is a cache-coherent non-uniform memory access multi-processor. (ccNUMA. or simply NUMA) . In addition, some" architectures such as the PowerPC™ (a product of International Business Machines of Armonk, New York) provide individual processor time registers that increment at some divisor of the processor's own frequency - on the PowerPC the register is called the "time base register." The PowerPC architecture requires that the program-perceptible values of the time base on a multi-processor system increase monotonically, meaning that if a program reads the time base and then reads it again, the second value must be greater than or equal to the first value. The values of the time base registers on multiple processors have to be close enough to each other that if a program runs first on one processor and then on another, the program reads a second time base value that is greater than or equal to the first one. The time to move a program from one processor to another is greater than 103 processor cycle times and the time base divisor is on the order of tens of cycles, which will force a multi-node NUMA system to synchronize the time base registers of all the processors in the system, to within approximately 102 time base ticks of each other. Time will be expressed in this disclosure in units of the time base cycles or values and the terms "cycle" and "tick" are used interchangeably. There is often no common oscillator on a NUMA system and the time base registers drift apart from each other over time so the time base registers must also be re-synchronized with each other periodically. Although some hardware interconnection mechanisms do have a common oscillator that can be used for this purpose and others have a special packet format that carries a time value in its payload and ages this value as it is transmitted through the network, such hardware is not always present. Thus, some mechanism using standard hardware and appropriate logic is required. While time base synchronization is important, it must not be too expensive in terms of network load or specialized hardware. However, a time base synchronization mechanism to maintain the required level of synchronization is still needed. It would be desirable, therefore, to provide a time base synchronization system for a multi-node NUMA multiprocessor system. It is further desirable that the synchronization system be used with current interconnect implementations requiring no specialized hardware features. It would also be desirable to provide the synchronization system without imposing significant overhead on either the interconnect or the processors within the system. SUMMARY OF THE INVENTION It is therefore one object of the present invention to provide a time base synchronization system for a multi-node NUMA multi-processor system that will utilize available interconnect implementations without requiring specialized hardware features. It is another object of the present invention to provide a time base synchronization system for a multi-node NUMA. multi-processor system that does not impose significant operating overhead on the interconnect or processors in the system. The foregoing objects are achieved as is now described. In a multi-node non-uniform memory access (NUMA.) multiprocessor system, a designated node synchronization processor on each node, is synchronized. Individual nodes accomplish internal synchronization of the other processors on each node utilizing well known techniques. Thus it is sufficient to synchronize one processor on each node. Node zero, a designated system node that acts as a synchronization manager, estimates the time it takes to transmit information in packet form to a particular, remote node in the system. As a result a time value is transmitted from the remote node to node zero. Node zero projects the current time on the remote node, based on the transmission time estimate and compares that with its own time and either updates its own clock to catch up with a leading remote node or sends a new time value to the other node, requiring the remote node to advance its time to catch up with that on r.ode zero. Code on the remaining nodes is mostly passive, responding to packets coming from node zero and setting the time base value when requested. Monotonicity of the time bases is maintained by always advancing the earliest of the two time bases so as to catch up with the later one. To achieve the said objectives the present invention provides a method for monotonic time synchronization for a multinode data processing system comprising steps of: designating one of n number of nodes as node zero; initiating re-synchronization; estimating a period of time necessary for transmitting data from said node zero to a target node in said multi-node data processing system; updating said node zero time if said target node time is leading said node zero time; updating said target node time if said node zero time is leading said target node time; and repeating previous said steps for all other nodes in said multi-node data processing system. Further, the present invention provides a multinode data processing system comprising: • a system interconnect for transmitting data; • n number of nodes, wherein each node comprises: o a plurality of processors connected to a local bus; o at least one memory connected to said local bus for storing said data; and o a controller connected to said local bus for controlling said memory, wherein said controller is also connected to a said system interconnect; • a register within each of said plurality of processors for recording and reporting time values in each of said plurality of nodes; • a designated node zero; and logic means for synchronizing time values between said n number of nodes. Thus, the present invention provides a method and system for monotonic time synchronization for a multinode data processing system. 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 objects 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: Figure 1 depicts a high level block diagram of three nodes of a multi-node configuration of a data processing system in which a preferred embodiment of the present invention may be implemented; Figure 2 is an algorithm for synchronizing nodes in a multiple node NUMA system in accordance with an embodiment of the present invention; Figure 3 depicts a calculation of a round trip time from node zero to node k and back in a procedure for synchronizing nodes in a multiple node NUMA. system in accordance with an embodiment of the present invention; and Figure 4 is a process for synchronizing nodes in a multiple node NUMA. system in accordance with an embodiment of the present invention. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT With reference now to the figures, and in particular with reference to Figure 1, a high-level block diagram of three nodes of a multi-node configuration of a data processing system in which a preferred embodiment of the present invention may be implemented, is depicted. Data processing system 100 is composed of multiple nodes of which three nodes l00a, l00b and l00c are depicted. The nodes are connected together by interconnect 130. Each node has local bus 110, 111 and 112; one or more microprocessors (CPUs) per node, and memories 121. 123 and 125 connected to each local bus 110, 111 and 112. Cache and Directory Controllers (CDC) 122, 124 and 125 are also connected to local bus 110, 111 and 112, and interconnect 130. The general operation of data processing systems as depicted in Figure 1 is understood by those of ordinary skill in this art. Data processing system 100 depicts only three nodes: l00a, l00b and l00c. Each node utilizes multiple processors for each node and a typical NUMA system would utilize more nodes. It will be understood that there may be more than two, three or more microprocessors on any local bus and there may be two, three or more nodes on interconnect 130. A system bus may also be implemented in a number of different ways from a classic backplane bus to a full crossbar switch or any other viable connection scheme. A key property of a NUMA data processing system is that combined memories 121, 123 and 125 are treated as a single address space. Memory 1 121 may hold addresses from 0 to 4000 (address location numbers are strictly for illustration and do not necessarily represent actual memory addresses) and Memory 2 123 may hold addresses from 4001 to 10000. When CPU2 102 needs to access memory location 5000, for example, CDC 122 on node 100a routes the request to interconnect 130 and CDC 124 on node 100b receives the request from the interconnect 130 and routes it to Memory 2 123. Any memory on the NUMA system is available to any node and node 100a may access node 100c as well. Memory on the same node as a CPU is termed "local memory" and memory on a different node is termed "remote memory." Nodes do not need to all have the same amount of memory or the same number of CPUs. Referring to Figure 2, an algorithm for synchronizing nodes in a multiple node NUMA. system in accordance with an embodiment of the present invention is illustrated. The present invention is a modification and extension of an algorithm presented in "Performance Monitoring in a Myrinet-Connected Shrimp Cluster" Cheng Liao, Margaret Martonosi, and Douglas W. Clark, presented at the ACM Sigmetrics Symposium on Parallel and Distributed Tools (SPOT), August, 1998. The algorithm, as shown in Figure 2, presents the two sides of the present invention: one side executes on the node synchronization processor (NSP), that is designated on each node of the NUMA system, of node zero and one that executes on the NSP of each of the other nodes in the NUMA. system. Node zero intelligently estimates how long it takes currently to transmit information, in the form of a packet, to some other particular node in the system. Coincidentally, this provides a time value from the designated node to node zero. Based on the transmission time estimate, node zero projects the current time onto the other node, compares that with its time and either updates its own clock to catch up with a leading remote node or sends a new time value to the other node, telling it to advance its time to catch up with that time on node zero. The code on the other nodes is largely passive, responding to the packets coming from node zero and setting the time base value when requested. In the algorithm shown in Figure 2, let n be the number of nodes in the system, Ertt be the expected round-trip time value on the interconnect from a node to another node and back again, STDrtt be the standard deviation and MINrtt be the absolute minimum value of the round-trip time value. Each of the previously described are design time values based on the design of the interconnect mechanism. DI, an observed value, is the drift of the NSP on node i where the sign of DI indicates the direction of the drift relative to the NSP of node zero. A negative sign indicates that the time base of the NSP of node i is lagging or falling behind that of node zero while a positive sign indicates that the time base is leading or moving ahead of that of node zero. Re-synchronization is always initiated by node zero and targeted to a particular non-zero node in the system. Re-synchronization interval is adjusted based on how much node zero and the target node are drifting away from each other. Let Xi be the cross-node re-synchronization interval for node i where X0 is not defined. The initial value of Xj is a design time parameter and reflects the anticipated drift values of the time bases of the NSPs on the nodes. To reduce overhead of synchronization further, the algorithm can reduce the frequency of re-synchronization where possible and increase the frequency when necessary. The adaptation is two-way between node zero and a single target node. Nodes that drift very rapidly versus node zero are re-synchronized more frequently than nodes which drift more slowly. UTHRES is the upper threshold indicating that the error between node zero and the target node is too large and re-synchronization should be more frequent. LTHRES is the lower threshold indicating that the error between node zero and the target is small enough that re-synchronization should be less frequent. XNMORE is the factor used to increase the frequency of cross-node synchronization and XNLESS a factor to decrease the frequency of cross-node synchronization. Referring now to Figure 3, a calculation of a round trip time from node zero to node k and back in a procedure for synchronizing nodes in a multiple node NUMA. system in accordance with an embodiment of the present invention is illustrated. Mechanisms on node zero and node k that are used to estimate the current value for Round Trip Time to node k (RTTk) must be specified. This RTT value is estimated on every node re-synchronization. Essentially, the pseudo-code determines an average time by having node zero save TS (the time sent) and sending it to the target node, in this case node k. Node zero receives a responding packet, containing node k time value Tk, from node k and RTT is set to the arrival time of the node k packet less TS. If RTT is not valid, e.g., the time is negative, node zero gives up on this re-synchronization and re-starts the wait for the node k synchronization to expire. RTT is compared to three times standard deviation, STDrtt and the absolute minimum value of the round trip time value, MINrtt to determine further its validity. If RTT is valid, then RTTk is incremented by RTT. This procedure is repeated n, a fixed number of times determined by the design of the interconnect. At the end of the nth pass, RTTk value is set to I/nth of the calculated value. In the present invention, synchronization is internal to the data processing system. Time values of the time base registers are kept within a relatively small range, but there is no external time source against which the nodes are to be calibrated. There is no particular numerical setting required, therefore, time may be expressed in units of the time base cycles or values. Monotonicity requires that adjustment of a time base register may only increase its value and cannot decrease the value. Hardware generally permits arbitrary values to be set in the time base registers. In particular, changing the time base register does not force it to reset to zero. However, there are processors (e.g., IA-32 processors from Intel, Inc. of San Jose, California) that violate this assumption. The NUMA. system consists of multiple, interconnected nodes. The interconnect has well-defined, design-specified values of the expected value of the round-trip time for a packet sent from one node to another and returned to the originating node and the standard deviation of the round-trip time. There is also a well-defined, absolute minimum round-trip time. Moreover, the interconnect is assumed to be approximately symmetric, so if the round-trip time is RTT, the transit time from the sending node to the target node is RTT/2. Each NUMA node may be an SMP system and there is a designed node zero in the NUMA system which acts as the manager in the synchronization algorithm. The present invention synchronizes NSPs in the system and it is assumed that some pre-existing mechanism synchronizes the remaining processors in a node to the node's NSP. Each node of the NUMA. system has a designated NSP processor that participates in synchronization. Every NSP may have its own oscillator and the NSP time base registers may drift forward or backward relative to each other. Typically, the oscillators are accurate and the rate of drift is small. Referring now to Figure 4, a method for synchronizing nodes in a multiple node NUMA system in accordance with an embodiment of the present invention is illustrated. Refer to Figure 2 for a pseudo-code structure of the present invention. The process begins with step 402, which illustrates initialization of cross node intervals. The process then proceeds to step 404, which depicts waiting for a particular cross node interval to expire. In this case, cross node interval k expires first. The process proceeds to step 406, which illustrates the estimation of Round Trip Time (RTTk) between node zero and node k. This estimate is accomplished utilizing the method illustrated in Figure 3. The process next proceeds to step 408, which depicts a determination of whether step 406 produced a valid RTTk estimate. Synchronization relies on an accurate estimate of the time that it will take for a packet carrying time information to arrive at its destination. Since this can be affected by various network conditions, recent packet round-trip times to estimate the delivery time of the next packet are utilized. If the packet round-trip times are normally distributed around their design-time expected value, almost all of them will be within three standard deviations of the design-time expected value. Utilizing multiple valid estimating packets is important to ensure that the value of RTTk is one that predicts the behavior of the next packet sent. If the determination is made that RTTk is not valid, the process passes to step 410, which depicts restarting the wait for cross-node interval k (Xk) . If the determination is made that RTTk is valid the process instead passes to step 412, which illustrates the system determining the current time on node k. Next the process passes to step 414, which depicts a determination of whether T0 is less than or equal to the current time of node k (CTk) . If the time on node zero, T0, is less than or equal to the current time on node k, the process proceeds to step 416, which illustrates setting the time base of node zero to the current time of node k. If the determination is made, in step 414 that time on node zero is greater than the time on node k, the process passes instead to step 418, which depicts re-reading the time value from the time base register on node zero. The process continues to step 420, which illustrates sending the new time base value to node k, thus re-synchronizing node k with node zero. The process then passes to step 422, which depicts a determination of how rapidly the node time bases are drifting apart rapidly. If the node time base is drifting apart rapidly, the process proceeds to step 426, which illustrates decreasing re-synchronization intervals since the error between node zero and the target node is too large. The process then passes to step 410. If the node time base is not drifting apart rapidly, the process passes instead to step 424, which depicts increasing the re-synchronization interval because the error between node zero and the target node is small and re-synchronization should be less frequent. The process then moves to step 410, which depicts restarting the wait cycle for Xk/ the cross-node synchronization interval for node k. The process continues to step 404, which illustrates waiting for the cross-node interval to expire and repeating the re-synchronization process. The present invention relies on an accurate estimate of the time it will take for a packet, carrying time information, to arrive at its destination. Since the time may be affected by various network conditions, the algorithm uses recent packet round-trip times to estimate the delivery time of the next packet. The present invention avoids re-synchronizations during periods of serious overload by omitting re-synchronizations when they are detected. If the packet round-trip times are normally distributed around the design-time expected value, most of the packets will be within three standard deviations of the value. Since the drift is small, the interconnect must be severely overloaded for significant drift to occur. Using a small number of estimating packets is important to ensure that the value of RTTk predicts the behavior of the next packet sent. The present invention maintains the ffionotonicity o^ the time bases by always advancing the earlier of the two time bases to catch up to the later one. Adjusting node zero may create a temporary drift away by the time bases on other nodes, but that is corrected at the next re-synchronization. If the drift is small, the adjustments in time base value also tend to be small. A feature may be added to the present invention to allow a node to predict how it is drifting relative to node zero. It is important to note that while the present invention has been described in the context of a fully functional data processing system, those skilled in the art will appreciate that the mechanism of the present invention is capable of being distributed in the form of a computer readable medium of instructions in a variety of forms, and that the present invention applies equally, regardless of the particular type of signal bearing media utilized to actually carry out the distribution. Examples of computer readable media include: nonvolatile, hard-coded type media such as read only memories (ROMs) or erasable, electrically programmable read only memories (EEPROMs), recordable type media such as floppy disks, hard disk drives and CD-ROMs, and transmission type media such as digital and analog communication links. While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. We Claim: 1. A multi-node data processing system (100), comprising: • a system interconnect (130) for transmitting data; • n number of nodes (!00 a-c), wherein each node comprises: o a plurality of processors (101-109) connected to a local bus; o at least one memory (121, 123, 125) connected to said local bus for storing said data; and o a controller connected to said local bus for controlling said memory, wherein said controller is also connected to a said system interconnect; • a register within each of said plurality of processors for recording and reporting time values in each of said plurality of nodes; • a designated node zero; and • logic means for synchronizing time values between said n number of nodes. 2. A multi-node data processing system as claimed in claim 1, wherein said logic means for synchronizing time values between said n number of nodes, comprising: • discrimination means for designating one of n number of nodes as node zero; • means for initiating synchronization; • calculation means for estimating a period of time necessary for transmitting data from said node zero to a target node in said multi-node data processing system; • validation means for determining validity of said transit time; • update means for updating said node zero time if said target node time is leading said node zero time; • means for updating said target node time if said node zero time is leading said target node time; and • logic means for setting a time base value on all other nodes in said multi- node data processing system. 3. A multi-node data processing system in as claimed in claim 2, wherein said validation means for determining validity, comprising: • discrimination means for comparing each round trip time estimate with a calculation wherein said calculation comprises: • a known minimum value, an expected value less three times a standard deviation and an expected value plus three times said standard deviation, wherein said minimum value, said standard deviation and said expected value are known from design-time information. 4. A multi-node data processing system in as claimed in claim 3, wherein said estimating means for estimating said period of time necessary for transmitting data from said node zero to a target node in said multi-node data processing system, comprising: • transmission means for sending a data packet from said node zero to said target node; • means for receiving a time value from said target node at said node zero; and • discrimination means for comparing said target node time to said node zero time. 5. A multi-node data processing system as claimed in claim 4, comprising: • logic means for adjusting time base value on said node zero or said target node based on said time value received from said target node. 6. A multi-node data processing system in as claimed in claim 5, comprising: • logic means for adjusting a re-synchronization interval based on a determination of the speed with which said target node time base is drifting away from said node zero time base. 7. A multi-node data processing system as claimed in claim 6, comprising: • synchronization means for re-synchronizing nodes more frequently when said target node time base drifts rapidly with respect to said node zero time base; and • synchronization means for re-synchronizing nodes less frequently when said target node time base drifts slowly with respect to said node zero time base.

Documents:

999-del-2000-abstract.pdf

999-del-2000-assignment.pdf

999-del-2000-claims.pdf

999-del-2000-correspondence-others.pdf

999-del-2000-correspondence-po.pdf

999-del-2000-description (complete).pdf

999-del-2000-drawings.pdf

999-del-2000-form-1.pdf

999-del-2000-form-19.pdf

999-del-2000-form-2.pdf

999-del-2000-form-3.pdf

999-del-2000-form-5.pdf

999-del-2000-gpa.pdf

999-del-2000-petition-others.pdf