The file paper.ps contains the CSRI technical report: Benefits of Speedup Knowledge in Memory-Constrained Multiprocessor Scheduling by Eric W. Parsons and Keneth C. Sevcik If you have the UNIX uncompress program, get the paper.ps.Z file. Remember to transfer the file in binary mode. Uncompress it, and print it on a postscript printer. If you do not have uncompress, get the paper.ps file in ascii mode, and print it on a postscript printer. This report was made available for anonymous ftp by: eparsons@cs.toronto.edu ABSTRACT Recently, research on scheduling for large-scale multiprocessor systems has begun to take into consideration the memory sizes of jobs. In general, the approach used to ensure good performance is to increase the multiprogramming level as the load increases. But if jobs require significant amounts of memory, then there will be a point at which the system can no longer fit additional jobs in memory. The scheduler will then have to carefully choose the way it allocates processors to jobs that are running in order to optimize performance. In this paper, we investigate the benefit of having speedup knowledge about individual jobs in making such a choice. We find that if memory sizes and speedup characteristics of jobs are uncorrelated, then there may be moderate benefits in having speedup information, but if large-sized jobs tend to have better speedup than small-sized ones, as might occur in real systems, then much more significant benefits can be obtained. We propose scheduling strategies that exploit speedup information to improve performance, and evaluate them under a variety of workloads.