PERFORMANCE EVALUATION OF SCHEDULING ALGORITHMS FOR IMPRECISE COMPUTER-SYSTEMS

We study the scheduling of tasks in computer systems which utilize imprecise (partial) computations. In our system, tasks arrive randomly during run-time. Each task has two levels of computation time requirements: the full level computation requirement and the reduced level computation requirement. The reduced level computation of a task takes less time to accomplish than the full level, but produces results which are not as precise as those of full-level computation. We assume that the imprecise results are nonetheless acceptable. The tasks are scheduled in the following way: If the total number of tasks in the system is no more than M -a system parameter-the tasks are executed at the full level. When the total number of tasks exceeds M, the tasks are executed at the reduced level. The system performance under this kind of scheduling and computation model is analyzed. Attention is devoted to development of the explicit formulas for the practically important performance metrics such as the normalized mean task waiting time, the mean task served computation time, and the fraction of tasks fully processed. The effect of variations in parameter values on the system performance is also examined in detail.