Anna Poplawski http://www.cs.dartmouth.edu/~annap Dartmouth College Advisers: David M. Nicol, Thomas H. Cormen Title: Scheduling Logical Processes and Disk Accesses for Reduced Stall Time Abstract: Even with today's decreasing memory costs, there are still applications for which the data does not fit into RAM. These out-of-core applications include very large scientific computations, run on massively parallel machines, and memory-intensive applications, run on desktop computers. Parallel discrete-event simulations represent a class of out-of-core applications for which the data can be naturally partitioned into logical processes with irregular communication patterns. Each logical process manipulates only its own portion of the data, which is always stored either in a block of contiguous memory addresses or in adjacent disk sectors. At any point during the execution, there is a subset of the processes which are able to make progress without receiving information from other processes. On a machine with P processors, we would like at least P of these to be present in memory at all times. In order to achieve this goal, we determine in what order the processes will be executed. Then we use this information to prefetch the data belonging to processes which will be executed in the near future; but first, to make room for the new data, we must choose a process currently in memory to replace, and save that process's data in secondary storage. Other researchers have independently studied task scheduling algorithms and algorithms for prefetching and caching disk blocks. In general, scheduling algorithms do not consider storage issues. Prefetching and caching algorithms assume either a fixed string of references or only limited knowledge of the future data references. We aim to find a scheduling policy which, when used together with a prefetching and caching algorithm, will significantly reduce the idle time of the CPUs.