Analysis of Parallel Scheduling Performance

Mark Squillante

IBM Watson Research Center


We first present a matrix-analytic analysis of stochastic parallel-server scheduling models, which yields exact solutions of matrix-geometric form and includes a closed-form solution for the $R$ matrix in certain model instances. A set of numerical experiments based on our analysis are used to establish several results for parallel-server queues under a particular class of scheduling disciplines. We then present a study of the job arrival patterns from a real parallel computing system, i.e., the Cornell Theory Center. Our analysis of the parallel workload data illustrates traffic patterns that exhibit heavy-tailed behavior and other characteristics which are quite different from the arrival processes used in previous studies. We then investigate the impact of these arrival traffic patterns on parallel scheduling performance.

[Mark Squillante]
[IBM Watson Research Center]