Apparatus and method for high-throughput asynchronous communication

1. An apparatus for high-throughput asynchronous communication, comprising:

a sender;

a receiver;

a sender's first-in, first-out (FIFO) buffer coupled to an input of the sender;

a receiver's FIFO buffer coupled to an input of the receiver;

a forward communication channel coupled between the sender and the receiver's FIFO buffer; and

a reverse communication channel coupled between the receiver and the sender's FIFO buffer;

wherein the forward communication channel, the receiver's FIFO buffer, the reverse communication channel, and the sender's FIFO buffer operate collectively as a network FIFO between the sender and the receiver, wherein each time the sender removes a white token, which is an acknowledge token, from the sender's FIFO buffer, the sender inserts a black token, which is a request token, into the forward communication channel, and each time the receiver removes a black token from the receiver's FIFO buffer, the receiver inserts a white token into the reverse communication channel; and

wherein the network FIFO is configured to ensure that asynchronous communication between the sender and the receiver takes place reliably and without unnecessary waiting by the sender or the receiver.

2. The apparatus of claim 1 ,

wherein the sender's FIFO buffer and the reverse communication channel are initialized with nw send white tokens and nb send black tokens; and

wherein the receiver's FIFO buffer and the forward communication channel are initialized with nw rec white tokens and nb rec black tokens.

3. The apparatus of claim 2 , wherein the sender is configured to:

remove a white token from the sender's FIFO buffer; and

upon removing the white token, to

insert a first black token into the sender's FIFO buffer, and to

simultaneously insert a second black token into the forward communication channel.

4. The apparatus of claim 3 , wherein the second black token comprises a data item.

5. The apparatus of claim 2 , wherein the receiver is configured to:

remove a black token from the receiver's FIFO buffer; and

upon removing the black token, to

insert a first white token into the receiver's FIFO buffer, and to

simultaneously insert a second white token into the reverse communication channel.

6. The apparatus of claim 2 ,

wherein a number of white tokens in the sender's FIFO buffer is less than or equal to a number of white tokens in the receiver's FIFO buffer;

wherein a cycle time of the receiver's FIFO buffer is less than a cycle time of the sender; and

wherein a reverse latency in the receiver's FIFO buffer is less than or equal to (nw send −nw rec ) times the sum of the receiver's cycle time, the latency of the reverse channel, the reverse latency of the sender's FIFO buffer, and the latency of the forward channel.

7. The apparatus of claim 2 ,

wherein a number of black tokens in the receiver's FIFO buffer is less than or equal to a number of black tokens in the sender's FIFO buffer;

wherein a cycle time for the sender's FIFO buffer is less than a cycle time for the receiver; and

wherein a forward latency in the sender's FIFO buffer is less than or equal to (nb send −nb rec ) times the sum of the sender's cycle time, the latency of the forward channel, the forward latency of the receiver's FIFO buffer, and the latency of the reverse channel.

8. The apparatus of claim 2 , wherein the sum of a latency of the forward communication channel, a forward latency for the receiver's FIFO buffer, a latency of the reverse communication channel, and a reverse latency for the sender's FIFO buffer is less than or equal to the sum of the number of white tokens in the sender's FIFO buffer and the number of black tokens in the receiver's FIFO buffer times the minimum of the sender's and receiver's cycle times.

9. A computer system for high-throughput asynchronous communication, comprising:

a sender;

a receiver;

a sender's first-in, first-out (FIFO) buffer coupled to an input of the sender;

a receiver's FIFO buffer coupled to an input of the receiver;

a forward communication channel coupled between the sender and the receiver's FIFO buffer; and

a reverse communication channel coupled between the receiver and the sender's FIFO buffer;

wherein the forward communication channel, the receiver's FIFO buffer, the reverse communication channel, and the sender's FIFO buffer operate collectively as a network FIFO between the sender and the receiver, wherein each time the sender removes a white token, which is an acknowledge token, from the sender's FIFO buffer, the sender inserts a black token, which is a request token, into the forward communication channel, and each time the receiver removes a black token from the receiver's FIFO buffer, the receiver inserts a white token into the reverse communication channel; and

wherein the network FIFO is configured to ensure that asynchronous communication between the sender and the receiver takes place reliably and without unnecessary waiting by the sender or the receiver.

10. The computer system of claim 9 ,

wherein the sender's FIFO buffer and the reverse communication channel are initialized with nw send white tokens and nb send black tokens; and

wherein the receiver's FIFO buffer and the forward communication channel are initialized with nw rec white tokens and nb rec black tokens.

11. The computer system of claim 10 , wherein the sender is configured to:

remove a white token from the sender's FIFO buffer; and

upon removing the white token, to

insert a first black token into the sender's FIFO buffer, and to

simultaneously insert a second black token into the forward communication channel.

12. The computer system of claim 11 , wherein the second black token comprises a data item.

13. The computer system of claim 10 , wherein the receiver is configured to:

remove a black token from the receiver's FIFO buffer; and

upon removing the black token, to

insert a first white token into the receiver's FIFO buffer, and to

simultaneously insert a second white token into the reverse communication channel.

14. The computer system of claim 10 ,

wherein a number of white tokens in the sender's FIFO buffer is less than or equal to a number of white tokens in the receiver's FIFO buffer;

wherein a cycle time of the receiver's FIFO buffer is less than a cycle time of the sender; and

wherein a reverse latency in the receiver's FIFO buffer is less than or equal to (nw send −nw rec ) times the sum of the receiver cycle time, the latency of the reverse channel, the reverse latency of the sender's FIFO buffer, and the latency of the forward channel.

15. The computer system of claim 10 ,

wherein a number of black tokens in the receiver's FIFO buffer is less than or equal to a number of black tokens in the sender's FIFO buffer;

wherein a cycle time for the sender's FIFO buffer is less than a cycle time for the receiver; and

wherein a forward latency in the sender's FIFO buffer is less than or equal to (nb send -nb rec ) times the sum of the sender cycle time, the latency of the forward channel, the forward latency of the receiver's FIFO buffer, and the latency of the reverse channel.

16. The computer system of claim 10 , wherein the sum of a latency of the forward communication channel, a forward latency for the receiver's FIFO buffer, a latency of the reverse communication channel, and a reverse latency for the sender's FIFO buffer is less than or equal to the sum of the number of white tokens in the sender's FIFO buffer and the number of black tokens in the receiver's FIFO buffer times the minimum of the sender and the receiver cycle times.

17. A method for high-throughput asynchronous communication, comprising:

removing a white token, which is an acknowledge token, from a sender's first-in, first-out (FIFO) storage unit at the sender; and

upon removing the white token,

inserting a first black token, which is a request token, into the sender's FIFO storage unit, and

simultaneously inserting a second black token into a forward communication channel, which is coupled to a receiver's FIFO storage unit;

whereby removing the white token ensures that the forward communication channel has room for the second black token;

removing a black token from a receiver's FIFO storage unit; and

upon removing the black token,

inserting a first white token into the receiver's FIFO storage unit, and

simultaneously inserting a second white token into a reverse communication channel which is coupled to the sender's FIFO storage unit;

whereby removing the black token ensures that the reverse communication channel has room for the second white token.

18. The method of claim 17 , wherein the second black token comprises a data item.

19. The method of claim 18 ,

wherein a count of white tokens in the sender's FIFO storage unit is less than or equal to a count of white tokens in the receiver's FIFO storage unit; and

wherein a cycle time for the receiver's FIFO storage unit is less than a cycle time for the sender.

20. The method of claim 18 , wherein a count of black tokens in the receiver's FIFO storage unit is less than or equal to a count of black tokens in the sender's FIFO storage unit; and

wherein a cycle time for the sender's FIFO storage unit is less than a cycle time for the receiver.

21. The method of claim 18 , wherein the sum of a latency of the forward communication channel, a forward latency for the receiver's FIFO storage unit, a latency of the reverse communication channel, and a reverse latency for the sender's FIFO storage unit is less than or equal to the sum of a count of white tokens in the sender's FIFO storage unit and the count of black tokens in the receiver's FIFO storage unit times the sender's cycle time.