Analysis of job arrival patterns and parallel scheduling performance

In this paper we present a study of the job arrival patterns from a paralle l computing system and the impact of such arrival patterns on the performan ce of parallel scheduling strategies. Using workload data from the Cornell Theory Center, we develop a class of traffic models to characterize these a rrival patterns. Our analysis of the job arrival data illustrates traffic p atterns 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 traffi c patterns on the performance of parallel space-sharing strategies, includi ng the derivation of some scheduling optimality results. (C) 1999 Published by Elsevier Science B.V. All rights reserved.