Minimizing Parallel Virtual Machine [PVM] Tasks Execution Times Through Optimal Host Assignments

PVM is a message passing system that is designed to run parallel programs across a network of workstations. Its default scheduler uses the round-robin scheduling algorithm to assign tasks to hosts on the virtual machine. This task assignment strategy is deficient when it comes to a network of heterogeneous workstations. Heterogeneity could be software related, hardware related or both. The default scheduler does not attempt to assign a PVM task to a node within the virtual machine that best services the PVM task. The problem with this allocation scheme is that resource requirements for each task that must be assigned to a computer vary. The default scheduler could assign a computation intensive parallel task to a computer that has a slow central processing unit (CPU) thus taking longer to execute the task to completion (Ju and Wang, 1996). It is also possible that a communication bound process is assigned to a computer with very low bandwidth. The scheduler needs to assign tasks to computers in such a way that tasks are assigned to computers that will fulfill the resource requirements of a given task: schedule and balance the work load in such a way that the overall execution time is minimized. In this dissertation, a stochastic task assignment method was developed that not only takes into account the heterogeneity of the hosts but also utilizes state information for the tasks to be assigned, and hosts onto which they are assigned. Task assignment methods that exist today, such as used in Condor, PvmJobs, CROP, and Matchmaker tend to be designed for a homogenous environment using the UNIX operating system or its variants. They also tend to use operating system data structures that are sometimes not common across most architectures. This makes it difficult to port them to other architectures. The task assignment method that was developed in this dissertation was initially implemented across a PVM environment consisting of a network of Win32® architecture, Linux architecture, and Sun Solaris architecture. A portable prototype implementation that runs across these architectures was developed. A simulator based on the CSIMIS toolkit was developed and utilized to study the behavior of the M/G/I queueing model on which the task assignment is based. Four PVM programs were run on a PVM environment that consisted of six nodes. The run-times of these progran1s were measured for both the default scheduler and the method proposed in this dissertation. The analysis of the run-times suggests that the proposed task assignment method works better for PVM programs that are CPU intensive than those that are small and do not require a lot of CPU time. The reason for this behavior can be attributed to high overheard that is required to compute the task assignment probabilities for all the hosts in the PVM environment. However, the proposed method appears to minimize execution times for the CPU intensive tasks. The ease with which external resource managers in the PVM environment can be incorporated into the PVM environment at run-time makes this proposed method an alternative to the default scheduler. More work needs to be done before the results that were obtained from this dissertation could be generalized, if at all possible, across the board. A number of recommendations on the reduction of overheard are specified at the end of this report