Efficient scheduling in asynchronous contention-based system
In an operation scheduler adapted to schedule in an asynchronous contention-based system a first FIFO queue is adapted to store one trigger message or one operation request. A message router is coupled to the first FIFO queue and is adapted to route instructions to a second FIFO queue or a memory and locate in the memory the instructions of a suspended operation associated with a trigger message and authorize execution of the suspended operation. An arbitration unit is coupled to the second FIFO queue and to the memory, and is adapted to schedule the execution of instructions associated with a standalone non-preemptable operation during a period of time within which at least one operation of the first sequence is being suspended.
1. An operation scheduler adapted to schedule, in an asynchronous contention-based system, the execution of a standalone non-preemptable operations and of sequences of non-preemptable operations wherein after completion of a first operation of a sequence of the sequences of non-preemptable operations, the execution of a second operation of the sequence of the sequences of non-preemptable operations is suspended until a trigger message associated with the second operation is detected by the asynchronous contention-based system, the operation scheduler comprising:
first and second first-in-first-out (FIFO) queues adapted to store asynchronous inputs in a first-in-first-out fashion, wherein the first FIFO queue is adapted to store trigger messages and operation requests, said operation requests comprising instructions associated with the execution of the standalone non-preemptable operations and instructions associated with the sequences of non-preemptable operations, and wherein the second FIFO queue is adapted to store instructions associated with the standalone non-preemptable operations;
a memory adapted to store instructions associated with the sequences of non-preemptable operations;
a message router coupled to the first and second FIFO queues and to the memory; and
an arbitration circuit coupled to the second FIFO queue and to the memory
wherein the message router is adapted to:
route a first instruction associated with a particular standalone non-preemptable operation to the second FIFO queue; and
store a second instruction associated with a first sequence of non-preemptable operations to the memory, wherein the first sequence of non-preemptable operations is suspended while a first trigger message associated with the second instruction has not been received by the first FIFO queue; and
wherein the arbitration circuit is further adapted to:
determine whether the first instruction was routed to the second FIFO queue before the first trigger message was received by the first FIFO queue;
schedule the execution of the first instruction when the first instruction was routed to the second FIFO queue before the first trigger message was received by the first FIFO queue; and
schedule the execution of the second instruction when the first instruction was not routed to the second FIFO queue before the first trigger message was received by the first FIFO queue.
2. The operation scheduler of claim 1 , wherein:
the message router is further adapted to route a third instruction associated with a second sequence of non-preemptable operations to the memory, wherein the second sequence of non-preemptable operations is a suspended operation while a second trigger message associated with the third instruction has not been received by the first FIFO queue; and
the arbitration circuit is further adapted to:
determine whether the second trigger message was received by the first FIFO queue before the first trigger message was been received by the first FIFO queue;
schedule the execution of the third instruction when the second trigger message was received by the first FIFO queue before the first trigger message was received by the first FIFO queue; and;
schedule the execution of the second instruction when the second trigger message was not received by the first FIFO queue before the first trigger message was received by the first FIFO queue.
3. The operation scheduler of claim 1 , wherein the arbitration circuit is further adapted to schedule the execution of instructions associated with at least one of a standalone non-preemptable operation or a non-suspended operation of the second sequence based on a priority associated with the instructions.
4. The operation scheduler of claim 1 , further comprising:
a resource controller coupled to the arbitration circuit and adapted to determine an amount of available execution resources available in the system;
wherein the arbitration circuit is further adapted to schedule the execution of instructions associated with at least one of a standalone non-preemptable operation or a non-suspended operation of the second sequence based on the amount of available execution resources.
5. A method of scheduling, in an asynchronous contention-based system, the execution of standalone non-preemptable operations and of sequences of non-preemptable operations wherein after completion of a first operation of a sequence of the sequences of non-preemptable operations, the execution of a second operation of the sequence of the sequences of non-preemptable operations is suspended until a trigger message associated with the second operation is detected by the asynchronous contention-based system, the method comprising:
storing in a first first-in-first-out (FIFO) queue, in a first-in-first-out fashion, trigger messages and operation requests, said operation requests comprising instructions associated with the execution of the standalone non-preemptable operations and instructions associate with the sequences of non-preemptable operations;
routing instructions associated with standalone non-preemptable operations to a second FIFO queue, in a first-in-first-out fashion, wherein the second FIFO queue is adapted to store instructions associated with the standalone non-preemptable operations and to not store instructions associated with the sequences of non-preemptable operations;
storing instructions associated with sequences of non-preemptable operations to a memory, wherein the memory is adapted to store instructions associated with sequences on non-preemptable operations and to not store instructions associated with standalone non-preemptable operations;
locating in the memory the instructions of a suspended operation associated with a trigger message and authorizing execution of the suspended operation;
based on the second FIFO queue and the memory, arbitrating the schedule of the execution of instructions associated with the at least one standalone non-preemptable operation during a period of time within which at least one operation of the first sequence is being suspended.
6. The method of claim 5 , further arbitrating the schedule of the execution of instructions associated with a non-suspended operation of a second sequence during a period of time within which at least one operation of the first sequence is being suspended.
7. The method of claim 5 , further comprising:
arbitrating the schedule of the execution of instructions associated with at least one of a standalone non-preemptable operation or a non-suspended operation of the second sequence based on a priority associated with the instructions.
8. The method of claim 5 , further comprising:
determining an amount of available execution resources available in the system; and
further arbitrating the schedule of the execution of instructions associated with at least one of a standalone non-preemptable operation or a non-suspended operation of the second sequence based on the amount of available execution resources.
9. An operation scheduler of an asynchronous contention-based system, the operation scheduler comprising:
a first first-in-first-out (FIFO) queue configured to store instructions of non-preemptable stand alone operations, to store instructions of non-preemptable sequence operations, and to store trigger messages associated with particular instruction of the sequence operations;
a message router coupled to the first FIFO queue;
a second FIFO queue coupled to the message router and configured to store instructions of the stand alone non-preemptible operations and to not store instructions of the sequences of non-preemptable operations;
a memory coupled to the message router and configured to store instructions of the sequences of non-preemptible operations and to not store instructions of the standalone non-preemptable operations; and
an arbitration circuit coupled to the second FIFO queue and to the memory;
wherein the message router is configured to:
route a first instruction of a particular standalone non-preemptable operation to the second FIFO queue; and
store a second instruction of a first sequence of non-preemptible operations in the memory, wherein the first sequence of non-preemptable operations is suspended while a first trigger message associated with the second instruction has not been received by the first FIFO queue; and
wherein the arbitration circuit is configured to:
determine whether the first instruction was routed to the second FIFO queue before the first trigger message was received by the first FIFO queue;
schedule the execution of the first instruction when the first instruction was routed to the second FIFO queue before the first trigger message was received by the first FIFO queue; and
schedule the execution of the second instruction when the first instruction was not routed to the second FIFO queue before the first trigger message was received by the first FIFO queue.