Distributed ordering system

• US 9,934,184 B1
• Filed: 09/25/2015
• Issued: 04/03/2018
• Est. Priority Date: 09/25/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Nakibly, Guy, Habusha, Adi, Bshara, Nafea, Avron, Itai
• Primary Examiner(s): Zaman, Faisal M
• Application Number:
  US14/865,431
• Time in Patent Office: 921 Days
• Field of Search: 710 5, 710 19, 710110, 710316
• CPC Class Codes: G06F 13/1626 by reordering requests
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: G06F 13/4054 where the function is bus cycle extension, e.g. to meet the timing requirements of the target bus
• CPC Class Codes: G06F 13/4282 on a serial bus, e.g. I2C bus, SPI bus on daisy chain buses G06F13/4247

Abstract

Provided are systems and methods for distributing ordering tasks in a computing system that includes master and target devices. In some implementations, a computing device is provided. The computing device may include a master device that is operable to initiate transactions. The computing device may further include a target device that is operable to receive transactions. In some implementations, the master device may be configured to transmit one or more transactions to the target device. The master device may further asynchronously indicate to the target device a number of transactions to execute. The master device may further asynchronously receive from the target device a number of transactions executed. The master device may then signal that at least one transaction from the one or more transactions it sent has completed.

Claims

1. A system-on-a-chip, comprising:

a first master device, wherein a first master device is operable to initiate transactions;

a second master device, wherein the second master device is operable to initiate transactions;

a target device, wherein a target device is operable to receive transactions;

a communication channel for transmitting transactions between the first master device and the target device and between the second master device and the target device;

a first execute token bus communicatively coupled between the first master device and the target device;

a release token bus communicatively coupled between the target device and the first master device; and

a second execute token bus communicatively coupled between the second master device and the target device;

wherein the first master device is configured to;

transmit a first transaction to the target device using the communications channel;

transmit a first execute counter to the target device using the first execute token bus, wherein the first execute token bus operates independently of the communication channel, wherein the first execute counter indicates to the target device a number of transactions associated with the first master device to execute, and wherein the first execute counter is transmitted without being synchronized to transmission of the first transaction;

receive a release counter from the target device over the release token bus, where the release token bus operates independently of the communication channel and the first execute token bus, wherein the release counter indicates a number of transactions completed by the target device; and

signal to the second master device that the ft transaction has been completed;

and wherein the second master device is configured to;

transmit a second transaction to the target device using the communication channel, wherein the second transaction is dependent on the first transaction; and

upon receiving the signal that the first transaction has been completed, transmit a second execute counter using the second execute token bus, where the second execute token bus operates independently of the communication channel, where the second execute counter indicates to the target device a number of transactions associated with the second master device to execute, and wherein the second execute counter is transmitted without being synchronized to the second transaction.

2. The system-on-a-chip of claim 1, wherein the first execute token bus and the release token bus are asynchronous with respect to the communication channel.

3. The system-on-a-chip of claim 1, wherein the first execute counter and the release counter use a Gray code.

19. The system-on-a-chip of claim 1, wherein the first transaction is associated with an address, and wherein the second transaction is dependent on the first transaction by being associated with the address.

20. The system-on-a-chip of claim 1, wherein the first transaction is associated with a value, and wherein the second transaction uses the value.

4. A computing device, comprising:

a master device, wherein the master device is operable to initiate transactions;

a target device, wherein the target device is operable to receive transactions;

a communication channel for transmitting transactions between the master device and the target device;

a first bus; and

a second bus;

wherein the master device is configured to;

transmit one or more transactions to the target device using the communication channel;

transmit to the target device a number of transactions to execute, wherein the number of transactions to execute is transmitted using the first bus, wherein the first bus operates independently of the communication channel, and wherein the number of transactions to execute are transmitted without being synchronized to transmission of the one or more transactions;

receive from the target device a number of transactions executed, wherein the number of transactions executed is received using the second bus, and wherein the second bus operates independently of the communication channel; and

signal that at least one transaction from the one or more transactions has completed.

5. The computing device of claim 4, wherein the number of transactions to execute is indicated using a Gray code.

6. The computing device of claim 4, wherein the number of transactions executed is indicated using a Gray code.

7. The computing device of claim 4, wherein the number of transactions to execute is fewer than a number of transactions transmitted to the target device.

8. The computing device of claim 4, wherein the number of transactions to execute is greater than a number of transactions transmitted to the target device.

9. The computing device of claim 4, wherein the computing device is a system-on-a-chip.

10. The computing device of claim 4, wherein the computing device is a board, and wherein the master device and the target device are components on the board.

11. The computing device of claim 4, wherein the master device comprises a processor.

12. The computing device of claim 4, wherein the target device comprises a memory-mapped device.

21. The computing device of claim 4, wherein the first bus and the second bus are routed between the master device and the target device separately from the communication channel.

22. The computing device of claim 4, wherein the first bus is a point-to-point bus between the master device and the target device, and the second bus is a point-to-point bus between the target device and the master device.

23. The computing device of claim 4, wherein the first bus and the second bus are a same bidirectional bus.

24. The computing device of claim 4, wherein the first bus does not include a clock signal, and wherein the second bus does not include a clock signal.

13. A computer-implemented method, comprising:

transmitting, by a master device, a first transaction to a target device, wherein the first transaction is transmitted using a communication channel;

transmitting to the target device a number of transactions to execute, wherein the number of transactions to execute is transmitted using a first bus, wherein the first bus operates independently of the communication channel, and wherein the number of transactions to execute are transmitted without being synchronized to transmission of the first transaction;

receiving, from the target device, a number of transactions executed, wherein the number of transactions executed is received using a second bus, and wherein the second bus operates independently of the communication channel; and

signaling that the first transaction has completed.

14. The method of claim 13, wherein the number of transactions to execute and the number of transactions executed is each indicated use a Gray code.

15. The method of claim 13, wherein the number of transactions to execute is fewer than a number of transactions transmitted to the target device.

16. The method of claim 13, wherein the number of transactions to execute is greater than a number of transactions transmitted to the target device.

17. The method of claim 13, wherein the master device comprises a processor.

18. The method of claim 13, wherein the target device comprises a memory-mapped device.

25. The computer-implemented method of claim 13, further comprising:

transmitting, by a second master device, a second transaction to the target device, wherein the second transaction is dependent on the first transaction, and wherein the target device receives the second transaction before executing the first transaction;

receiving, by the second master device, the signal that the first transaction has completed; and

transmitting, by the second master device, a second number of transactions to execute.