Soft real-time environments consist of jobs that must receive service within a particular time interval. If service for a specific job is not completed by the end of its time interval, it is said to be lost; in addition, the computation time expended on the job is wasted, and any further computation for the job is discontinued. The goal of a system designer is to provide an environment that minimizes the number of jobs that are lost. If a parallel environment is available, the system designer has two options: Allow each processor to execute a job individually, or let multiple processors cooperate in executing a job. This article shows, for two classes of static allocation policies, that simple comparative analytical models may be used to indicate which option minimizes the number of lost jobs, as a function of workload intensity. The first class of policies, called equal partitions, statically decomposes the system into equal-size sets of processors and executes one job per partition. These policies are frequently employed in other contexts. The second class of policies, called two partitions, statically partitions the processors into two sets, not necessarily of the same size. Surprisingly, it is observed mathematically that even for statistically identical jobs, this class of policies is superior to equal partitions under certain loadings. The analysis is validated experimentally with a workload executed on a 16-node iPSC/2 hypercube.>

In a closed, separable, queuing network model of a computer system, the number of customer classes is an input parameter. The number of classes and the class compositions are assumptions regarding the characteristics of the system's workload. Often, the number of customer classes and their associated device demands are unknown or are unmeasurable parameters of the system. However, when the system is viewed as having a single composite customer class, the aggregate single-class parameters are more easily obtainable. This paper addresses the error made when constructing a single-class model of a multi-class system. It is shown that the single-class model pessimistically bounds, the performance of the multi-class system. Thus, given a multi-class system, the corresponding single-class model can be constructed with the assurance that the actual system performance is better than that given by the single-class model. In the worst case, it is shown that the throughput given by the single-class model underestimates the actual multi-class throughput by, at most, 50%. Also, lower bounds are provided for the number of necessary customer classes, given observed device utilizations. This information is useful to clustering analysis techniques as well as to analysts who must obtain class-specific device demands.

Parallel programs are characterized by their speedup behavior. As more processors are allocated to a particular parallel program, the program (potentially) executes faster. However, there is often a point of diminishing returns, beyond which extra allocated processors cannot be used effectively. Extra processors would be better utilized by allocating them to another program. Thus, given a set of processors in a multiprocessor system, and a set of parallel programs, a partitioning problem naturally arises which seeks to allocate processors to programs optimally.