This paper studies the importance of accounting for a neglected facet of overall workload behavior, the pattern of task arrival. A stochastic characterization is formulated that defines regularity in the task arrival pattern. This characterization is used as the basis for a quantitative evaluation of the importance of accurately accounting for the task arrival behavior in the design of the processing cores of a Chip Multi-processor (CMP). The results of this study show that because the methodologies traditionally used for evaluating overall performance do not accurately account for task arrival behavior, they can lead to significantly suboptimal design solutions. For instance, it is found that, for an unvarying mix of benchmarks, the best dual-core design for harmonic mean performance can result in up to 21% suboptimality depending on the task arrival pattern. In addition, it is shown that when the pattern of task arrival is prone to change, simply accounting for average task arrival behavior can result in up to 12% inaccuracy, and suboptimality in employed design solutions. A practical conclusion that can be drawn from the results of this study is that benchmark vendors need to provide not only a representative mix of instruction level behavior (the traditional application benchmarks), but also representative task arrival patterns. In addition, robustness to variation in the task arrival pattern needs to be accounted for as an overall merit in the evaluation of potential design solutions.