Patent ID: 8514874

Claim:
A packet classifier for a network processor having a plurality of processing modules, wherein the network processor generates one or more tasks corresponding to each of a plurality of received packets, the packet processor comprising: a scheduler configured to (i) generate a thread of one or more contexts for each task received by the packet classifier, wherein the thread corresponds to an order of instructions applied to the corresponding packet, and (ii) send the contexts to a multi-thread instruction engine configured to process the one or more threads received from the scheduler, wherein the contexts are temporarily stored in one or more output queues of the scheduler; wherein each thread includes an identifier of a corresponding one of the one or more output queues; an arbiter configured to select one of the one or more output queues in order to provide output packets to the multi-thread instruction engine, one or more of the output packets associated with a corresponding thread of contexts; wherein each output queue transmits output packets corresponding to a given thread contiguously in the order in which the threads started, wherein the scheduler comprises: a completion list having one or more linked lists, each linked list corresponding to the one or more output queues, wherein the scheduler inserts an entry in the completion list corresponding to each received task, the thread entries stored in order in which a first task of each thread is are received; wherein each entry in the completion list comprises an identifier of a corresponding thread, a link to a subsequent entry in the completion list corresponding to the corresponding thread, and an indication if the entry is a last entry of the corresponding thread; wherein an oldest unspecified list specifies an order in which a first context of each thread is received by the scheduler; and the scheduler further configured to (i) track which of the one or more output queues corresponds to each thread with (1) a queue table and (2) a per-thread table, the queue table identifying an output queue corresponding to each thread and the per-thread table having one or more entries corresponding to each of the one or more output queues, each per-thread table entry having a head pointer and a tail pointer of the linked list of each entry in the completion list corresponding to the given thread, (ii) assign one of the one or more output queues to the thread corresponding to an oldest entry of the oldest unspecified list, and (iii) remove the oldest entry from the oldest unspecified list.