ASYMPTOTIC OPTIMALITY OF STATISTICAL MULTIPLEXING IN PIPELINED PROCESSING

The throughput of pipelined processing of heterogeneous multitasked jo bs is computed and optimized in this study. There are K job classes. E ach job has M tasks which have to be processed in a given order (same for all tasks) on a pipeline of M processors. Tasks have random proces sing times. The jobs of each class form a stationary and ergodic seque nce (with respect to their task processing times). Classes are differe ntiated by distinct statistics and may not be jointly stationary or er godic. Thus, the jobs are overall statistically heterogeneous. We are interested in the average execution time per job <(tau)over bar>, when the job populations of the various classes become very large (asympto tically). This is shown to depend on the order in which jobs enter the pipeline. Under the natural class-based ordering, where all jobs of t he first class enter first, followed by those of the second, third, an d so on, the quantity <(tau)over bar> is computed, but is shown not to attain its minimal value in general. On the contrary, appropriate sta tistical multiplexing of jobs of different classes on the pipeline is shown to minimize the average execution time per job on every sample p ath (with probability one). The procedure, called balanced statistical multiplexing, is constructed and the minimal <(tau)over bar> is compu ted in terms of the average execution times of the job tasks.