Task Scheduling of Processor Pipelines with Application to Network Processors

Chip Multi-Processors (CMPs) are now available in a variety of systems and provide the opportunity for achieving high computational performance by exploiting application-level parallelism. In the communications environment, network processors (NPs) are often designed around CMP architectures and in this context the processors may be used in a pipelined manner. This leads to the issue of scheduling tasks on processor pipelines. This paper considers problems associated with determining optimal application task assignments for such pipelines. A system and algorithm called Greedy Pipe is presented and its performance analyzed. The algorithm employs a greedy heuristic to schedule tasks derived from multiple application flows on pipelines with an arbitrary number of stages. Tasks associated with multiple applications may also be shared. Experimental results indicate that over a wide range of conditions, 95% of the time Greedy Pipe quickly obtains schedules within 10% of optimal