Minimize the Flow Time of Multi Stages Jobs on Multi-Purpose Machines

For the pipeline sharing problem consider a set of numbered services, and a flow of incoming packets, where each packet requires different subset of services in a fixed increasing order. A multi-core chip is a chip where each core is specifically designed to implement a single needed service. The various cores in each chip may or may not be linked. The chip should be designed such that links connecting the cores will allow packets to go through their desired rout of required services. In this research we will try to focus on the scheduling aspect of the problem, and so in order to use common scheduling terminology, we will refer in this research to packets as jobs, to chips as machines, to services as processing stages, and to cores as processors. The processing time for each processing stage is one time unit.

Allowing jobs to be processed sequentially without flow control might result in unpredictable queuing delays, and lack of performance guarantees. In this research we design topography for the machine and an algorithm, that when implemented on the machine designed, will minimize the queuing delays in the system, and by that maximize the performance of the system.

The topography suggested in this researched is the 2-flexbility closed chain with logarithmic tree depth. In this topography, each processor is linked to exactly 2 processors in the next stage. The 2 processors are chosen carefully in a way that will maximize the number of available routing options available for each job in the system. 

We present a family of IP based algorithms for the scheduling of the jobs on the processors. We present an optimal algorithm for the off-line model and a near optimal algorithm for online settings.