Apparatus and method for high-throughput asynchronous communication with flow control

One embodiment of the present invention provides a system that asynchronously controls sending data items from a sender to a receiver. This system includes a set of sending FIFOs, a set of receiving FIFOs, as well as a shared data path between the sender and the receiver. The system also includes a set of control paths that operate in parallel between the sender and the receiver, wherein a given control path controls the transmission of data items between a corresponding sending FIFO and a corresponding receiving FIFO through the shared data path. The system further includes a round-robin scheduling mechanism which activates one control path at a time in a predetermined sequence. An activated control path asynchronously controls the sending of a data item from a corresponding sending FIFO to a corresponding receiving FIFO. By operating the control paths in parallel in the predetermined sequence, the system does not have to wait a request-acknowledge cycle time between the sender and the receiver before sending consecutive data items through the shared data path, but can instead send multiple data items through the shared data path within a single request-acknowledge cycle time.

BACKGROUND

1. Field of the Invention

The present invention relates to communication networks. More specifically, the present invention relates to an apparatus and a method for high-throughput asynchronous communication over high-latency communication channels.

2. Related Art

Dramatic increases in computational speed in recent years have largely been facilitated by improvements in semiconductor integration densities, which presently allow hundreds of millions of transistors to be integrated into a single semiconductor chip. This makes it possible to incorporate a large amount of computational circuitry onto a semiconductor chip. Moreover, the small circuit dimensions made possible by improved integration densities have enabled this computational circuitry to operate at greatly increased speeds. While computational circuitry within semiconductor chips continues to grow increasingly faster, the delay involved in communicating data between semiconductor chips has not decreased significantly. Consequently, communication delay is beginning to create a significant bottleneck to computer system performance.

For example,FIG. 1illustrates a typical communication system that includes sender100, receiver102, and communication channel104, wherein sender100comprises sending control module106and sending data latch108, and wherein receiver102comprises receiving control module110and receiving data latch112. The control modules106and110have inputs marked with triangles, and outputs, which have no triangles. Sending control module106is coupled to receiving control module110through request line114and acknowledge line116. Sending data latch108is coupled to receiving data latch112through data path118. Request line114, acknowledge line116, and data path118are collectively referred to as “communication channels”104.

During operation, when data is available in sending data latch108and data path118is free, sending control module106sends a request signal on request line114and simultaneously causes sending data latch108to send a data item onto data path118. After a transit time, the request signal and the data item arrive at receiving control module110and receiving data latch112, respectively.

In response to the request signal, if the downstream channel is available, receiving control module110causes the data to be latched into receiving data latch112and simultaneously sends an acknowledge signal on acknowledge line116. After an additional transit time, the acknowledge signal arrives at sending control module106, which causes sending control module106to send a subsequent data item from sending data latch108onto data path118. Note that above steps can be repeated.

Unfortunately, the above-described communication scheme has a serious drawback. The data rate of the communication channels is restricted by a request-acknowledge cycle time required to send a request signal and to receive a corresponding acknowledge signal for each data item. Note that while the acknowledge signal is in-flight, data path118is idle. Thus, data path118is busy at most half of the time, and is hence significantly underutilized.

In order to alleviate this problem, a previous invention described alternately using two sets of control paths to asynchronously control transmission of consecutive data items between the sender and the receiver, thereby allowing an improved data rate up to twice as high as the implementation illustrated inFIG. 1. However, this technique does not provide a solution for a communication system that requires an even higher data rate.

Hence, what is needed is an apparatus and a method for high-throughput asynchronous communication between a sender and a receiver without the above-described limitation.

SUMMARY

One embodiment of the present invention provides a system that asynchronously controls sending data items from a sender to a receiver. This system includes a set of sending first-in-first-out buffers (FIFOs), a set of receiving FIFOs, as well as a shared data path between the sender and the receiver. The system also includes a set of control paths that operate in parallel between the sender and the receiver, wherein a given control path controls the transmission of data items between a corresponding sending FIFO and a corresponding receiving FIFO through the shared data path. The system further includes a round-robin scheduling mechanism which activates one control path at a time in a predetermined sequence. An activated control path asynchronously controls the sending of a data item from a corresponding sending FIFO to a corresponding receiving FIFO. By operating the control paths in parallel in the predetermined sequence, the system does not have to wait a request-acknowledge cycle time between the sender and the receiver before sending consecutive data items through the shared data path, but can instead send multiple data items through the shared data path within a single request-acknowledge cycle time.

In a variation on this embodiment, each control path comprises a sending control module which generates a request signal, a receiving control module which generates an acknowledge signal, a request control path which carries the request signal from the sending control module to the receiving control module, and an acknowledge control path which returns the acknowledge signal from the receiving control module to the sending control module. In this variation, the sending control module is controlled by the round-robin scheduling mechanism.

In a variation on this embodiment, the sending control module is coupled to a sending data latch in a corresponding sending FIFO while the receiving control module is coupled to a receiving data latch in a corresponding receiving FIFO.

In a variation on this embodiment, the sending control module activates the sending data latch upon receiving the acknowledge signal from the receiving control module and when the sending control module is activated by the round-robin scheduling mechanism. Activating the sending data latch causes a subsequent data item in the corresponding sending FIFO to be sent onto the shared data path.

In a variation on this embodiment, the receiving control module provides data underflow protection in the control path by not acknowledging a request to output data when no data is available in the receiving FIFO and by keeping the data latch at the output of the FIFO inactive.

In a variation on this embodiment, the sending control module provides data overflow protection in the control path by not acknowledging a request to input data when the sending FIFO is full and by keeping the data latch at the input of the FIFO inactive.

In a variation on this embodiment, the round-robin scheduling mechanism activates consecutive control paths at an activation interval, wherein the activation interval is less than the request-acknowledge cycle time, and the activation interval multiplied by the number of control paths is greater than or equal to the request-acknowledge cycle time.

In a variation on this embodiment, the sending and receiving control modules are implemented using GasP modules.

In a variation on this embodiment, each of the control signals is a differential signal sent through two wires.

In a variation on this embodiment, each control path provides underflow and overflow protections on the shared data path.

DETAILED DESCRIPTION

FIG. 2illustrates a high-throughput asynchronous communication system in accordance with an embodiment of the present invention.

From left to right inFIG. 2, the system has a sender202which includes all the components to the left of dash line204, and a receiver206which includes all the components to the right of dash line208. Sender202and receiver206communicate through communication channels210which include all the components between dash lines204and208.

From top to bottom inFIG. 2, the system includes a set of three control paths212,214, and216which operate in parallel between sender202and receiver206. Each control path comprises a sending control module218which generates a request signal, a receiving control module220which generates an acknowledge signal, a request control path222which carries the request signal from sending control module218to receiving control module220, and an acknowledge control path224which returns the acknowledge signal from receiving control module220to sending control module218.

Sender202further includes three sets of sending first-in first-out buffers (FIFOs)226which facilitate queuing and temporarily storing data items for transmission. In one embodiment inFIG. 2, sending FIFO226comprises three stages, and data items propagate from left to right through these stages. Each stage of sending FIFO226further comprises a sending FIFO control module228which is coupled to a sending data latch230. Note that the sending FIFO control module in the last stage of sending FIFO226is also sending control module218.

Receiver206includes three sets of receiving FIFO232which facilitate queuing and temporarily storing the data items received from sending FIFO226. Note that the first stage of receiving FIFO232includes receiving control module220, which additionally comprises two components. In one embodiment inFIG. 2, receiving FIFO232comprises three stages, and the data items propagate from left to right through these stages.

In the system inFIG. 2, a given control path controls the transmission of data items between a corresponding sending FIFO and a corresponding receiving FIFO by using a corresponding sending control module, a corresponding receiving control module, and corresponding request and acknowledge control paths.

The system further includes a shared data path236between sender202and receiver206which is shared by control paths212,214, and216. Specifically, all three sending control modules transmit corresponding data items to the corresponding receiving control modules through shared data path236.

In the heart of the system is a round-robin ring238which couples together control paths212,214and216through the corresponding sending control modules in the control paths. During operation, round-robin ring238activates one control path at a time in a predetermined sequence. For example, round-robin ring238activates the control paths212,216,214sequentially and repeats the sequence indefinitely. In this fashion, round-robin ring238ensures that one sending FIFO at a time can send a data item onto shared data path236. Meanwhile, an activated control path asynchronously controls the sending of a data item from the corresponding sending FIFO to the corresponding receiving FIFO. Note that, the asynchronous control of each control path ensures that the request-acknowledge cycle time between sending consecutive data items by each control path is still the latency between sending a request signal and receiving a corresponding acknowledge signal, which does not change. In other words, each control path inFIG. 2behaves like the communication system inFIG. 1. On the other hand, once a data item is sent onto the shared data path, the system does not have to wait the request-acknowledge cycle time of each control path before sending the next data item onto the shared data path. Instead, the round-robin ring activates consecutive control paths at an activation interval less than the request-acknowledge cycle time, which facilitates sending multiple data items through the shared data path within a single cycle time, while the multiple data items are controlled by their corresponding parallel control paths asynchronously.

Note that the system achieves high-throughput through aggregation of multiple control paths. The number of aggregated control paths determines the throughput. In one embodiment of the present invention, the activation interval which is the interval between consecutive data items on the shared data path, is a constant. In this embodiment, each control path in the set of control paths is activated once during a round-robin cycle. Consequently, if the round-robin cycle time is at least the request-acknowledge cycle time, then the round-robin cycle time divided by the number of control paths determines the activation interval. For example, the three control paths in the embodiment illustrated inFIG. 2imply that the activation interval is ⅓ of the round-robin cycle time. Hence the data rate and throughput is 3 times those of a simple communication system with only one control path. It will be apparent to one with ordinary skills in the art that more aggregation of control paths subsequently facilitates even higher throughput. In designing the system, the number of parallel control paths to be used may be determined in accordance to a system throughput requirement.

During operation, sending control module218activates sending data latch240upon receiving a request signal from control module228, and upon receiving the acknowledge signal from receiving control module220, and when sending control module218is activated by round-robin ring238. Upon activation, sending data latch240causes the last data item in sending FIFO226to be sent onto shared data path236. On the receiver side, the data item is captured in receiving data latch242in receiving FIFO232some fixed delay later. Note the asymmetric designs of sending control module218and receiving control module220. The asymmetry is desired for flow control purpose which will be described later.

Also note that sending and receiving control modules are implemented using GasP modules. For example, GasP module218is used in the sending FIFO and the two GasP modules220are used in the receiving FIFO. GasP modules are selected, because they are fast and efficient asynchronous controllers. The design of a GasP module is described in more detail below with reference toFIGS. 6-8.

Differential Signaling

The request and acknowledge signaling between sending control module218and receiving control module220in control path212uses two-phase signaling on two wires, wherein the two wires carry a differential signal. Each connection that uses two-phase signaling is labeled with a “2” inFIG. 2.

Note that in the two-phase signaling scheme, for each request or acknowledge signal sent, each wire transitions only once (either “up” or “down”) with each communication, whereas in four-phase signaling, each communication requires two transitions per wire. Using two wires allows sending a control signal as differential signals, thereby facilitating noise cancellation during transmission. Additionally, using two wires provides a return path for the current. Furthermore, the combination of two wires carrying the differential signal and two-phase signaling also simplifies some of the logic in the circuit and avoids using expensive gates like XOR gates.

FIGS. 3A and 3Billustrate an implementation of communication channels210in accordance with an embodiment of the present invention. More specifically,FIG. 3Aillustrates a schematic diagram of request control path222, andFIG. 3Billustrates an implementation of request control path222using two wires and circuit components in accordance with an embodiment of the present invention.

InFIG. 3B, a signal is capacitively coupled across the boundary300between a sender and a receiver through coupling capacitances302and304in wire306and wire308, respectively. The capacitances310and312before and after coupling capacitance302are parasitic capacitances. All these capacitances directly influence the latency of the communication channel. Each wire further includes two inverters before the coupling capacitance and two inverters after the coupling capacitance. With proper sizing, the two inverters before the coupling capacitance drive the large parasitic and coupling capacitances with little delay, and the two inverters after the coupling capacitance amplify a small signal swing to a full signal swing with little delay.

InFIG. 3Bdifferential signaling on wires306and308is implemented by means of complementary signals that both change at the same time. Here, both wires have separate amplifying inverters. Alternatively, the amplifying inverters from the two wires can be replaced by differential amplifiers.

Flow Control

The control paths have special precautions to ensure proper flow control, which includes both FIFO underflow and overflow protection. During operation, FIFO underflow protection ensures that a FIFO does not output invalid data items when the FIFO is empty, while FIFO overflow protection ensures that a FIFO does not input data items when the FIFO is full.

For example inFIG. 2, sending control module218provides FIFO overflow protection in the control path by not acknowledging a request to input data and keeping data latch240inactive when the FIFO is full. The use of GasP modules in the configuration ofFIG. 2guarantees such overflow protection.

FIGS. 4A and 4Billustrate how to guarantee FIFO overflow protection in the control path in accordance with an embodiment of the present invention. More specifically,FIG. 4Aillustrates an obvious but erroneous implementation of the control path that does not provide FIFO overflow protection. During operation, assume a data item arrives at receiving data latch402and corresponding request arrives at GasP module400. If the next FIFO stage, which is the stage associated with GasP module400, is empty, then GasP module400will activate latch402and the data will be latch in the next FIFO stage. Furthermore, GasP module400issues an acknowledge signal to the sending FIFO, which means that the sending FIFO can send the next data item. This acknowledge signal is issued even if the receiving FIFO has become full. If such a scheme is used with the implementation illustrated inFIG. 2, in a case that all receiving FIFOs are full upon receiving a data item, each of the three sets of sending FIFOs can still send a data item on shared data path236, one at a time. Because no receiving FIFO can accept another data item, all three data items must remain on the shared data path236. Consequently, the first two data items will be overwritten by the third data item on shared data path236and will be lost in transmission.

FIG. 4Billustrates the control path implementation used inFIG. 2that provides FIFO overflow protection in the control path in accordance with an embodiment of the present invention. InFIG. 4B, receiving control model404comprises the first two stages of the receiving FIFO instead of just one stage as inFIG. 4A. Note that the receiving data latch406is normally empty. During operation, a data item arriving at receiving data latch406will be latched. If the FIFO stage associated with GasP module414is not full, GasP module414passes the data item onto downstream receiving data latch412upon receiving the request signal associated with the data item, which then causes GasP module414to issue an acknowledge signal. On the other hand, if the FIFO stage associated with GasP module414is full after receiving a data item, the data item remains latched in receiving data latch406, and therefore cannot cause GasP module414to issue an acknowledge signal. This subsequently prevents sending control module416from sending another data item onto the shared data path236until the FIFO stage full condition is cleared. Hence, the receiving control module404provides data overflow protection in the control path by not issuing an acknowledge signal for the last data item, if the data item arrives at the receiver when the receiving FIFO stage associated with GasP module414is full.

Implementation of Control Path

FIG. 5illustrates an implementation of a control path using GasP modules that have complementary wires as inputs and outputs in accordance with an embodiment of the present invention.

Sending control module416inFIG. 4Bis implemented using two GasP modules502and504. These two GasP modules are connected to a round-robin ring by means of dashed lines506. The round-robin ring ensures that the two GasP modules fire alternately. The right GasP module414inFIG. 4Bis also implemented using two GasP modules508and510, and the middle GasP module410inFIG. 4Bis similarly implemented using two GasP modules512and514. InFIG. 5, GasP modules502,504,508, and510with two outputs labeled0and1means that upon firing the GasP modules set the output labeled0to0and simultaneously the output labeled1to1. Following the firings of the GasP modules inFIG. 5and assuming that module502fires first, the following firing sequence will repeat indefinitely:502→512→508→504→514→510.
GasP Module Implementations

We denote a GasP module by means of a rectangular box with a label inside and a series of connections. The label denotes the event that is associated with the GasP module. Each GasP module can have three different types of connections.FIGS. 6 and 7give the three types of connections of a GasP module together with their 2-4 GasP implementations.FIG. 6shows the symbols and their implementations for connections between GasP modules where the time separation between the “firings” of two modules is two gate delays.FIG. 7shows the symbols and their implementations for connections between GasP modules where the time separation between the “firings” of two modules is four gate delays. Both figures show connections attached to the left and the right of a GasP module. Apart from a reflection, the implementations of the left-side and right-side connections are the same.

FIG. 6Aillustrates a GasP module with a so-called self-resetting input.FIG. 6Bshows a GasP module with a so-called non-resetting input.FIG. 6Cillustrates a GasP module with an output. Common in all GasP module implementations is a NAND gate. To complete the implementation of the GasP Module, circuitry is added to the NAND gate for each connection. When all inputs of a GasP module are set, which means HI in the implementations ofFIGS. 6A and 6B, the NAND gate will eventually “fire,” i.e., go LO. The firing of the NAND gate defines the occurrence of the event. After the NAND gate fires, a pull-down transistor resets each self-resetting input. The non-resetting input has no reset capability. When the NAND gate fires, the pull-up transistor sets the output.

FIG. 7illustrates the same ideas as inFIG. 6, except that now “setting” and “resetting” are implemented differently. Here, an input is set when the input is LO. Thus, resetting an input happens by means of a pull-up transistor, and setting an output happens by means of a pull-down transistor.

Each connection is implemented as a tri-state wire with a keeper. A tri-state wire is a wire that is either “driven HI”, “driven LO”, or “not driven.” To avoid clutter, connections in schematics appear as lines between GasP modules, and keepers are not shown. When a connection is driven HI or LO, the connection will be driven for a short period only, a period that is long enough to set the keeper and wire HI or LO. The keeper will then keep the state of the connection when the wire is not driven. Using the GasP implementations ofFIGS. 6 and 7, the period that a wire is driven is about three gate delays. Notice that each pull-down or pull-up transistor conducts for a period of about three gate delays.

In order for these implementations to work properly, all transistors must be properly sized. Here, this means that all gates must have the same step-up ratio, i.e., the ratio between each gate's drive strength and output load is the same. When properly sized, each gate has about the same delay, and thus we can justifiably speak about units of delay between any two events.

The label P on the connections to the GasP modules inFIGS. 6 and 7gives a name to the connections and is often associated with the name of the state to which the connection corresponds. The labels2and4indicate whether the implementation of the connection must realize a time separation of two or four gate delays, respectively, between firings of successive GasP modules.FIG. 8illustrates this idea.FIG. 8Ashows a simple connection between GasP modules andFIG. 8Bshows its implementation. The label4indicates that the connection must realize time separation of four gate delays between the firings of modules a and b. Notice that between node a going LO and node b going LO inFIG. 8Bthere are four gate delays. Similar remarks can be made forFIGS. 8C and 8D, where the label2denotes a time separation of two gate delays. The labels2and4will come in handy later when we want to calculate cycle times in GasP networks.

In an implementation we indicate the initial state of each connection by darkening the arrowheads or diamonds inside the modules that are associated with the connection. A connection with a darkened arrowhead or diamond is initially set, that is, the connection is initialized HI when the connection has the label2and initialized LO when the connection has the label4.