Method and system for initiating computation upon unordered receipt of data

• US 6,708,282 B1
• Filed: 09/05/2000
• Issued: 03/16/2004
• Est. Priority Date: 09/05/2000
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Raza Microelectronics Inc (Broadcom, Inc.)
• Inventors: Choquette, Jack, McCarthy, Dominic Paul
• Primary Examiner(s): Heckler, Thomas M.
• Assistant Examiner(s): SURYAWANSHI, SURESH
• Application Number:
  US09/654,759
• Time in Patent Office: 1,288 Days
• Field of Search: 713/400, 713/500, 713/502, 712/32, 712/36, 708/100
• US Class Current: 713/400
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

In complex systems, the arrival of data to a computation component is difficult to predict. A method of synchronizing the initiation of computation with the reception of its input data is disclosed. The method allows the input data and computation initiation commands to arrive in any order. The method is dynamically adjustable allowing for varying numbers of data inputs.

Claims

1. A method of synchronization comprising the steps of:

receiving a first command to transfer a first block of data;

receiving a second command to transfer a second block of data; and

receiving a third command to receive the first and second blocks of data; and

after receiving the first and second blocks of data, initiating a computation;

wherein in a first instance, the second block of data is received before receiving the first block of data; and

wherein in a second scenario, the first block of data is received before receiving the second block of data.

2. The method of claim 1 further including the step of:

prior to the initiating the computation, waiting for an available computation indication.

3. The method of claims 2 further including the step of:

adjusting a counter upon receiving said block of data.

4. A synchronization system, comprising:

a scheduler sending a first command, a second command, and a third command;

a first component receiving the first command to transfer a first block of data;

a second component receiving the second command to transfer a second block of data; and

a third component receiving the third command to receive the first and second blocks of data and to begin a computation, wherein the third component does not initiate the computation until the third component received the first and second blocks of data.

5. A synchronization system, comprising:

a scheduler for generating one or more commands;

a routing fabric coupled to the scheduler for receiving one or more input data operands that are uniquely tagged;

a fabric interface having an input coupled to the routing fabric, a first output coupled to the routing fabric, and a second output;

a command queue having an input coupled to the fabric interface, the command queue receiving and storing the one or more commands;

a data queue having an input coupled to the fabric interface for receiving an input data, a second input, a first output, and a second output; and

a synchronization unit having a first input coupled to the output of the command queue, a second input and a first output coupled to a compute block, a third input and a second output coupled to the second input and the first input of the data queue wherein commands that initiate computations are delayed by the synchronization unit until receiving the input data operands and receiving a compute available signal.

6. The system of claim 5, wherein the synchronization unit comprises a signed counter.

7. The system of claim 5, wherein the signed counter is decremented if data is received by the routing fabric.

8. The system of claim 7, wherein the signed counter is incremented by N counts if N commands are received.

9. The system of claim 8, wherein the synchronization unit does not generate a compute available signal if the signed counter is non-zero.

10. The system of claim 9, wherein a positive value of the signed counter indicates that additional input data is required.

11. The system of claim 10, wherein a negative value of the signed counter indicates that input data has been received before an associated computational command is received.

12. The system of claim 5, wherein the synchronization unit comprises two bit-strings having a first bit-string and a second bit-string.

13. The system of claim 12, wherein first bit-string identifies the required input data by setting the bit position associated with the tag of the input data to a one.

14. The system of claim 13, wherein the second bit-string indicates which input data have been received.

15. The system of claim 14, wherein the input data received from the routing fabric is uniquely tagged, indicating a bit position in the two bit-string.