The processor working set and its use in scheduling multiprocessor systems

The concept of a processor working set (PWS) as a single value parameter for characterizing the parallel program behavior is introduced. Through detailed experimental studies of different algorithms on a transputer-based multiprocessor machine, it is shown that the PWS is a robust measure for characterizing the workload of a multiprocessor system. It is shown that processor allocation strategies based on the PWS provide significantly better throughput-delay characteristics. The robustness of PWS is further demonstrated by showing that allocation policies that allocate processors more than the PWS are inferior in performance to those that never allocate more than the PWS-even at a moderately low load. Based on the results, a simple static allocation policy that allocates the PWS at low load and adaptively fragments at high load to one processor per job is proposed