The authors consider multiprogrammed multiprocessors and parallel programs modeled as random task graphs. A theoretical analytical model for studying combinations of extreme cases of workload parallelism (highly parallel versus highly sequential) and of system utilization (light versus heavy load) is presented. A simulation model was used to study intermediate cases. From these two models, conditions under which heterogeneity presents a significant performance improvement over homogeneous architectures are derived. A study of the effect of scheduling policies for heterogeneous architectures on workloads of different degrees of parallelism under various system load conditions is presented.>