Analysis of job arrival patterns and parallel scheduling performance

In this paper we present a study of the job arrival patterns from a parallel computing system and the impact of such arrival patterns on the performance of parallel scheduling strategies. Using workload data from the Cornell Theory Center, we develop a class of traffic models to characterize these arrival patterns. Our analysis of the job arrival data illustrates traffic patterns that exhibit heavy-tailed behavior and other characteristics which are quite different from the arrival processes used in previous studies of parallel scheduling. We then investigate the impact of these arrival traffic patterns on the performance of parallel space-sharing strategies, including the derivation of some scheduling optimality results.