METHOD AND AN APPARATUS FOR WORK PACKET QUEUING, SCHEDULING, AND ORDERING WITH CONFLICT QUEUING

1 . A method for processing conflicting work, comprising:

receiving a work request, the work request indicating one or more groups from a plurality of groups;

finding work by arbitrating among a plurality of queues of the one or more groups;

determining whether the found work conflicts with another work;

returning the found work when the determination is negative; and

adding the found work into a tag-chain when the determination is affirmative.

2 . The method as claimed in claim 1 , wherein the finding work by arbitrating among a plurality of queues of the one or more groups comprises:

determining whether at least one of the one or more groups has work in a de-scheduled queue; and

finding the work by arbitrating among the at least one group when the determination is affirmative.

3 . The method as claimed in claim 2 , further comprising:

determining whether at least one of the one or more groups have work in a conflicted queue when none of the one or more groups has work in the de-scheduled queue; and

finding the work by arbitrating among the at least one group when the determination is affirmative.

4 . The method as claimed in claim 3 , further comprising:

determining whether at least one of the one or more groups has work in an admission queue when none of the one or more groups has work in the conflicted queue; and

finding the work by arbitrating among the at least one groups when the determination is affirmative.

5 . The method as claimed in claim 4 , further comprising:

providing indication that no work is available when none of the one or more groups ha work in the admission queue.

6 . The method as claimed in claim 1 , wherein the determining whether the found work conflicts with another work comprises:

determining whether the found work was found in a de-scheduled queue; and

declaring the found work non-conflicting.

7 . The method as claimed in claim 1 , wherein the determining whether the found work conflicts with another work comprises:

determining whether the found work conflicts with another work when the found work was found in a conflicted queue or in an admission queue.

8 . The method as claimed in claim 1 , wherein the determining whether the found work conflicts with another work comprises:

determining whether the found work conflicts with a currently executed work.

9 . The method as claimed in claim 1 , wherein the determining whether the found work conflicts with another work comprises:

determining whether the found work conflicts with work in a conflicted queue.

10 . The method as claimed in claim 1 , wherein the determining whether the found work conflicts with another work comprises:

determining whether the found work conflicts with work in a de-scheduled queue.

11 . The method as claimed in claim 1 , further comprising:

re-scheduling the found work added into the tag-chain.

12 . The method as claimed in claim 11 , wherein the rescheduling the found work added into the tag-chain comprises:

ascertaining that execution of work ahead of the found work has finished;

determining whether the found work has been de-scheduled; and

moving the found work to a de-scheduled queue when the determining is affirmative.

13 . The method as claimed in claim 12 , further comprises:

moving the found work to a conflicted queue when the determining is negative.

14 . An apparatus for processing conflicting work, comprising:

at least one work-slot configured to receive work request, the work request indicating one or more groups from a plurality of groups;

and a get-work arbiter configured to:

find work by arbitrating among a plurality of queues of the one or more groups;

determine whether the found work conflicts with another work; and

return the found work when the determination is negative; and

a tag-chain manager configured to add the found work into a tag-chain when the determination is affirmative.

15 . The apparatus as claimed in claim 14 , wherein the get-work arbiter finds a work by arbitrating among a plurality of queues of the one or more groups by being configured to:

determine whether at least one of the one or more groups has work in a de-scheduled queue; and

find the work by arbitrating among the at least one group when the determination is affirmative.

16 . The apparatus as claimed in claim 15 , wherein the get-work arbiter is further configured to:

determine whether at least one of the one or more groups has work in a conflicted queue when none of the one or more groups have work in the de-scheduled queue; and

find the work by arbitrating among the at least one group when the determination is affirmative.

17 . The apparatus as claimed in claim 16 , wherein the get-work arbiter is further configured to:

determine whether at least one of the one or more groups has work in an admission queue when none of the one or more groups has work in the conflicted queue; and

find the work by arbitrating among the at least one group when the determination is affirmative.

18 . The apparatus as claimed in claim 17 , wherein the get-work arbiter is further configured to:

provide indication that no work is available when none of the one or more groups has work in the admission queue.

19 . The apparatus as claimed in claim 14 , wherein the get-work arbiter determines whether the found work conflicts with another work by being configured to:

determine whether the found work was found in a de-scheduled queue; and

declare the found work non-conflicting when the determination is positive.

20 . The apparatus as claimed in claim 14 , wherein the get-work arbiter determines whether the found work conflicts with another work by being configured to:

determine whether the found work conflicts with another work when the found work was found in a conflicted queue or in an admission queue.

21 . The apparatus as claimed in claim 14 , wherein the get-work arbiter determines whether the found work conflicts with another work by being configured to:

determine whether the found work conflicts with a currently executed work.

22 . The apparatus as claimed in claim 14 , wherein the get-work arbiter determines whether the found work conflicts with another work by being configured to:

determine whether the found work conflicts with work in a conflicted queue.

23 . The apparatus as claimed in claim 14 , wherein the get-work arbiter determines whether the found work conflicts with another work by being configured to:

determine whether the found work conflicts with work in a de-scheduled queue.

24 . The apparatus as claimed in claim 14 , wherein the schedule, synchronize, and order unit is further configured to:

re-schedule the found work added into the tag-chain.

25 . The apparatus as claimed in claim 24 , wherein the schedule, synchronize, and order unit reschedules the found work added into the tag-chain by being configured to:

ascertain that execution of work ahead of the found work has finished; and

determine whether the found work has been de-scheduled; and

wherein the tag-chain manager is configured to move the found work to a de-scheduled queue when the determination is affirmative.

26 . The apparatus as claimed in claim 25 , the tag-chain manager is further configure to:

move the found work to a conflicted queue when the determination is negative.