Elastic Buffer With Bidirectional Phase Detector

1. Technical Field

The invention relates to buffering received data on plesiochronous nodes of a data processing system and more particularly to application of elastic buffers in such nodes where the nodes are linked by extremely high speed unidirectional data links such as provided for the scalable coherent interface (SCI).

2. Description of the Related Art

In digital data processing systems, particularly multiple processor systems, the conventional backplane multi-drop bus has become a serious constraint on system performance because of throughput limitations, bus access contention problems and electro-magnetic interference generation. To move past the multidrop bus the Institute of Electrical and Electronics Engineers (IEEE) has established the IEEE Standard for Scalable Coherent Interface (IEEE Std 1596-1992) to provide computer bus like services using a collection of fast node to node unidirectional links for multiprocessor systems using a distributed coherent shared memory configuration.

The SCI and the similar IBM SCIL system provide local clocks, which are preferably tuned to a nominal transmission clock frequency, e.g. 500 Megahertz. No node is master of the system, and thus while the nodes preferably operate at the same clock speed, each node is clocked by a local oscillator. Oscillators are subject to unsynchronized drift with the result that each node actually operates at its own, varying frequency. Typically an allowance for difference between consecutive nodes (an external and an internal clock) must allow for a variation of 1000 ppm in frequency.

An SCI node is itself almost entirely synchronous. The only asynchronous part of the node is the first stage for receiving data. The clock for the received data is the same as the clock for the node which transmitted data.

SCI and SCIL provide for transmission of parallel data over the unidirectional links in delimited packets with the transmission clock for the data. These symbols are spaced by idle packets at a sufficient frequency to allow symbol skipping when required to realign the phase of a lower frequency receiving node to a higher frequency transmitting node. When a skip occurs, an idle symbol is discarded. Where the receiving node is faster, the opposite operation, i.e. idle symbol stuffing occurs. That is, an extra symbol is added to the packet sequence. The use of elastic buffers for skipping and stuffing operations to overcome phase drift is well known. Idle symbols are in fact sometimes called elasticity symbols.

Unfortunately, operation at high frequencies which are close to the physical limitations of a technology, such as 500 Megahertz for silicon based technology, can make idle symbol stuffing difficult if not impossible. To stuff a symbol, a node is called on to carry out two cycles in almost exactly the period allowed for one cycle. Such an operating speed may simply be unobtainable, even for short periods. It would be valuable to avoid the need to engage in symbol stuffing.

It is an object of the invention to provide for buffering received data on plesiochronous or mesochronous interfaces for nodes of a data processing system.

It is another object of the invention to provide an elastic buffers for receiving data over an extremely high speed unidirectional data link such as provided by the scalable coherent interface (SCI) or similar systems.

The above and other objects are achieved as is now described. An elastic buffer has a circular buffer with a plurality of symbol storage registers. As is conventional in the art, successive symbols are stored in each symbol storage register as clocked by the external or transmit clock received over a transmission link. Symbols are successively read from the symbol storage register as clocked by a node internal clock. Preferably, the reading of symbols trails the writing of symbols by .pi. radians. A phase comparator takes the external clock and the internal clock as inputs and generates a first input when the input clock has gained on the phase of the external clock and a second input when the input clock has lost on the phase of the external clock.

An idle symbol detector takes the received data as an input and generates an idle signal in response to each idle symbol in the data stream received over the transmission link. Responsive to an indication that the internal clock has gained on the phase of the external clock, a beat of the internal clock is skipped in reading the circular buffer. Responsive to indication that the internal clock has lost on the phase of the external clock and the concurrent presence of an idle signal, a beat of the external clock is skipped resulting in dropping a concurrent idle symbol from the successive sequence of symbols.

By skipping idle symbols on the input side, or periodically postponing reading of successive symbols on the output side of the elastic buffer, the phase of the external and internal clocks may be maintained in the proper relationship without the use of symbol stuffing.

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:

FIG. 1 is a high level block diagram of a multiple SCI node data processing system;

FIG. 2 is a block diagram of an SCI node;

FIG. 3 is a block diagram of an elastic buffer suitable for use in an SCI or SCIL node; and

FIG. 4 is a timing diagram for the elastic buffer of FIG. 3.

With reference now to the figures and in particular with reference to FIG. 1, there is depicted in a block diagram a distributed data processing system 10 comprising a plurality of nodes 12, 14, 16, 18 and 20. A given node is typically a memory node, a processing node or both. Both memory and data processing are distributed. Nodes 12, 14, 16, 18 and 20 are interconnected by a plurality of unidirectional data transmission links. In the preferred embodiment, data are sent in parallel over the unidirectional links clocked by the transmitting node. Data packets are sent at each clock cycle with idle symbols periodically interspersed among data symbols. The parallel format is 18 bits wide and includes 16 bits of data, a clock signal (1 bit) and a framing flag (1 bit). Node clocks are independent of one another.

FIG. 2 is a block diagram of an SCI node 21 suitable for inclusion in distributed data processing 10. Node 21 is connected to receive data packets on an address decoder 23 which routes data packets based on intended destination. Data packets intended for node 21 are routed to a First-In, First-Out (FIFO) input buffer 25. Data packets addressed to nodes other than the node 21 are routed to FIFO bypass buffer 27. Processing or memory circuitry are represented by node internal circuitry 29 which utilizes data packets received from FIFO input buffer 25 and which places data packets for transmission onto a FIFO output buffer 31. A multiplexor 33 controls sequencing of data for transmission between FIFO bypass buffer 27 and FIFO output buffer 31.

The clock of data transmitted from multiplexor 33 is the same, or at least has a fixed relationship to, the clock of node internal circuitry 29. The clock for data received by address decoder 23 is that for the immediately preceding node. The internal clock for node 21 and the transmission clock received by FIFO buffers 25 and 27 are independent and the clocks may drift in an unpredictable fashion relative to one another in phase and frequency although both clocks are designed to operate at the same frequency. Therefore data is docked into buffers 25 and 27 by a clock signal with an unpredictable phase and frequency relationship to the clock used on reading the data packets out of the buffers.

Unpredictable frequency and phase differentials over an interface have commonly been met by use of elastic buffers which skip idle symbols when the transmission frequency exceeds the receiving frequency and by stuffing idle symbols in the sequence of packets when the opposite is true. However, at the preferred operating speeds of the unidirectional data links utilized with node 21, data packet stuffing is not practical.

FIG. 3 is an elastic buffer 45 which may be advantageously utilized to implement either FIFO bypass buffer 27 or FIFO input buffer 25. In elastic buffer 45 data and the framing flag are received by buffering stages 47. The transmission (external) clock of the sequence of received data packets is regenerated by a clock recovery circuit 49, which may be provided by a phase lock loop or other regeneration circuit. The framing flag of the data packet is also applied to an idle detect circuit 51 which utilizes the framing flag to indicate if a packet is an idle symbol (ISIDLE high) or not.

The regenerated external clock is used to clock the input side of elastic buffer 45. The regenerated clock 49 is directly applied to buffering stages 47, idle detect circuitry 51 and a counter 53. Counter 53 in effect divides the regenerated clock into four phase staggered transmission subclocks W.sub.1, W.sub.2, W.sub.3 and W.sub.4, which are staggered in phase by .pi./2 radians and which have a frequency of 1/4 the external clock. Subclocks W.sub.1, W.sub.2, W.sub.3 and W.sub.4 are applied to four parallel symbol storage registers 63, 61, 59 and 57, respectively, which together form a circular buffer 55. Under normal conditions, each symbol storage register receives a data packet from buffer staging 47 every fourth clock pulse.

The symbols or data packets stored in registers 57, 59, 61 and 63 are reserialized by multiplexor 65 which is used to read each of the registers of circular buffer 55 in sequence and to place the packets into symbol buffer 67. Symbol buffer 67 is clocked by an internal clock. Multiplexor 65 is clocked by phase staggered internal subclocks R.sub.1, R.sub.2, R.sub.3 and R.sub.4 which are generated by counter 69, which in turn is clocked by the internal clock. Counter 69 produces subclocks R.sub.1, R.sub.2, R.sub.3 and R.sub.4 which are phase staggered by .pi./2 radians and which have a frequency of 1/4 the internal clock.

Nominally, the operations of writing to and reading from circular buffer 55 are separated by .pi. radians, with the internal clock "trailing" the external clock. Subclocks W.sub.1, W.sub.2, W.sub.3 and W.sub.4 should be synchronized with subclocks R.sub.3, R.sub.4, R.sub.1 and R.sub.2, respectively. That is, when symbol register 63 is being loaded (W.sub.4 being asserted) then symbol register 59 is being read (responsive to subclock R.sub.2 being asserted). Similarly, when symbol register 57 is being loaded then register 61 is being read. When register 59 is being loaded then register 63 is being read and when register 61 is being loaded then register 57 is being read.

Counters 53 and 69 each receive skip inputs which when asserted cause the counters to, in effect, "hang" on a current output. In other words, a particular subclock is held high for as long as the skip signal is asserted. If counter 53 holds one of subclocks W.sub.1, W.sub.2, W.sub.3 and W.sub.4 high for one cycle of the external clock, one symbol in the incoming sequence of packets is skipped. If counter 69 holds one of subclocks R.sub.1, R.sub.2, R.sub.3 and R.sub.4 high for one cycle of the internal clock, then the reading of a symbol from circular buffer 55 into symbol buffer 67 is delayed by one cycle. As long as the external clock does not overrun the relative phase of the internal clock no data is lost however. By delaying one or the other clocks the preferred phase relationship between the two sets of subclocks is restored.

Application of the input side skip signal and the output side skip signal to counters 53 and 69, respectively, is based on the phase relationship of the external clock and the internal clock. A bidirectional phase detector 71 utilizes the two sets of subclocks to provide for comparison of the phases of the external and internal clocks.

When the external clock has a higher frequency than the internal clock, the external clock gains (or increases its phase lead) on the phase of the internal clock. To detect gain in the phase of the external clock on the phase of the internal clock, one of the subclocks W.sub.1 is used to clock each of three latches 73, 75 and 77. Latches 73, 75 and 77 are set by internal subclocks R.sub.4, R.sub.3 and R.sub.2, respectively. Thus latch 73 generates an output in response to subclocks W.sub.1 and R.sub.4 coinciding. This occurs when the relative phase of the internal clock has gained on the phase of the external clock relative to the nominal phase relationship, as would happen if the internal clock is running faster than the external clock. Latch 73 going high results in random walk filter 79 being decremented. Latch 75 generates an output in response to subclocks W.sub.1 and R.sub.3 partially or fully coinciding. This occurs when the internal clock has the desired phase relationship with the external clock. Latch 73 going high results in random walk filter 79 being decremented. Latch 77 generates an output in response to subclocks W.sub.1 and R.sub.2 partially or fully coinciding. This occurs when the relative phase of internal clock has lost ground against the phase of the external clock, as happens if the internal clock runs slower than the external clock. Latch 77 going high results in random walk filter 79 being incremented.

Random walk filter 79 is intended to accumulate net phase gain by the external clock on the internal clock. Random walk filter 79 is essentially a two directional count register which is reset to its midrange value each time net subtractions from the count reduce the value past 0. Similarly, filter 79 is reset to its midrange value whenever the net accumulated count overflows the register. An accumulated count overflow results in generation of an input side skip signal Skip.sub.1 which is latched by latch 81. No output results from the count of random walk filter 79 passing 0. The input side skip signal is applied to an input of AND gate 83. If ISIDLE is high, or as soon as ISIDLE goes high, the input side skip signal is propagated through AND gate 83 to the skip input of counter 53 and to the reset input of latch 81. As a result, the output of counter 53 is delayed by one external clock cycle and one idle symbol is overwritten in buffer stages 47 before it can be written into circular buffer 55. Because the frequencies of the internal clock and the external clock are very close (differing by at most a few hundred parts per million) such a delay inserts a phase compensation between the clocks of almost exactly .pi./2 radians.

When the internal clock has a higher frequency than the external clock, the internal clock gains (or decreases its phase lag) on the phase of the external clock. To detect gain in the phase of the internal clock on the phase of the external clock, one of the internal subclocks R.sub.1 is used to clock each of three latches 85, 87 and 89. Latches 85, 87 and 89 are set by external subclocks W.sub.4, W.sub.3 and W.sub.2, respectively. Thus latch 85 generates an output in response to subclocks R.sub.1 and W.sub.4 partially or fully coinciding. This occurs when the relative phase of the external clock has gained on the phase of the internal clock relative to the nominal phase relationship, as would happen if the external clock is running faster than the internal clock. Latch 85 going high results in random walk filter 91 being decremented. Latch 87 generates an output in response to subclocks R.sub.1 and W.sub.3 partially or fully coinciding. This occurs when the internal clock has the desired phase relationship with the external clock. Latch 87 going high results in random walk filter 91 being decremented. Latch 89 generates an output in response to subclocks R.sub.1 and W.sub.2 partially or fully coinciding. This occurs when the relative phase of internal clock has gained on the phase of the external clock, as happens if the internal clock runs faster than the external clock. Latch 89 going high results in random walk filter 91 being incremented.

Random walk filter 91 is intended to accumulate net phase gain by the internal clock on the external clock. Random walk filter 91 is essentially a two directional count register which is reset to its midrange value each time net subtractions from the count reduce the value past 0. Similarly, filter 91 is reset to its midrange value whenever the net accumulated count overflows the register. An accumulated count overflow results in generation of an output side skip signal which is latched by latch 93. No output results from the count of random walk filter 91 passing 0 in the negative direction. The output side skip signal is applied a skip input of counter 67 and through a delay element 95 to the reset input of latch 93. As a result, the output of counter 69 is delayed by one internal clock cycle in turn delaying the reading of symbols into symbol buffer 67 by one clock cycle. Because the frequencies of the internal clock and the external clock are very close (differing by at most a few hundred parts per million) such a delay inserts a phase compensation between the clocks of almost exactly .pi./2 radians.

FIG. 4 is a timing diagram illustrative of the circumstance where the internal clock has a higher frequency than the external clock. The differences in frequency are greatly exaggerated over what is encountered in actual practice for purposes of the illustration. The external clock is divided into four external subclocks W.sub.1, W.sub.2, W.sub.3 and W.sub.4, which are phase staggered with respect to one another and which each have a frequency equal to one fourth the external clock. The internal clock is similarly divided into four subclocks R.sub.1, R.sub.2, R.sub.3 and R.sub.4. At T0, R.sub.3 is in phase with W.sub.1. By T1, the subclock W.sub.4 is in phase with subclock R.sub.1, consistent with a faster running external clock. For purposes of illustration, Skip 1 is shown as going high as R.sub.1 and W.sub.4 come to coincide, which is the nominal time to introduce of phase correction of .pi./2 radians. The skip signal is shown as being propagated as ISIDLE goes high at T2. An earlier logic high going transition of ISIDLE had no effect.

The invention provides a phase detector which determines if the pointers for reading and writing are properly separated or whether a clock cycle has to skipped on either the input or output side of the buffer. The internal and external subclocks may be considered to be in the form of four (corresponding to the number of registers in the circular buffer) phase clocks to provide the appropriate pointers. Although not logically required, the random walk filters ensure that no action is taken as a result of short term phase jitter. Phase detection occurs on both the input side as well as the output side of the FIFO buffer. While symbols are deleted on the input side, none are on the output side. Any need to stuff symbols is avoided.

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.