Processor management policies for multiprocessors
Chita R. Das, Chansu Yu · 1994
Processor management in parallel systems is a crucial issue for improving the performance of these machines in a multiuser environment. Processor management consists of two basic steps: allocation and scheduling. A processor allocation algorithm gives priority to a task structure and allocates an independent subsystem to it while the scheduling technique gives priority to system resources compared to the task communication requirement. In this research, we investigate both these issues for distributed and shared memory multiprocessors. First, we combine the multitasking and multiprogramming principles to propose a unified processor management scheme, called the multitasking and multiprogramming ($M\sp2$) policy for various classes of multiprocessors. Simulation with various kinds of workload shows the benefit of the $M\sp2$ scheme compared to multitasking or multiprogramming. Second, we propose two different scheduling schemes, called Lazy and Reservation Techniques for hypercube multiprocessors. They increase the system utilization of the hypercube by changing the execution order. Next, in order to achieve further enhancement in hypercube multiprocessors, we propose a novel allocation policy, called Limit Allocation, where a job size is scaled down to fit into a fragmented hypercube. It is shown that the approach can outperform all prior schemes. A queueing model is developed to analyze various allocation policies. Finally, we turn our attention to develop a systematic allocation scheme for MIN-based multiprocessors. We show that all topologically equivalent MINs can use the hypercube allocation algorithms. We use the baseline MIN as an example in this work and propose a renaming scheme, called bit reversal (BR) matching pattern. Allocation with the new matching pattern minimizes conflicts and partitions the system completely into independent subsystems.