Dynamic task allocation models for large distributed computing systems

The goal of this research is to develop new task allocation methods for large DCSs in a dynamic environment. One of the basic requirements of any method is that it be capable of providing solutions faster but with quality nearly equal, for practical purposes, to that of the simulated annealing. Another requirement is that the method must yield satisfactory solutions while limited time is allowed for making the decisions. In this dissertation, we develop two dynamic task allocation models which meet these requirements. They are 1) the clustering simulated annealing model (CSAM) and 2) the mean field annealing model (MFAM). Both of these models combine characteristics of the statistical technique and differing deterministic approaches. These models are capable of performing rapid convergence of the deterministic approaches while preserving the solution quality afforded by simulated annealing. The research presented in this dissertation includes the development of theory and simulations of the CSAM and MFAM for large DCSs in a dynamic environment. Theory of the CSAM is developed by combining the simulated annealing technique with a well performed clustering algorithm. The MFAM is derived from the Gibb's distribution. Both of the CSAM and MFAM apply a new annealing schedule which provides fast convergence. In this research, the CSAM and MFAM are simulated in a large DCS with various load balance conditions. Tasks with various execution costs and intertask communication costs are created and completed in each processor at different rates, presenting a dynamic environment. Performance of the CSAM and MFAM are evaluated and compared with both the simulated annealing method and a deterministic method by a variety of statistics collected from the simulations. Simulation results show that the CSAM and MFAM perform much better in general than the simulated annealing method and the deterministic method in making dynamic task allocation decisions. In the two typical system conditions simulated, the CSAM and MFAM are capable of providing a stable and balanced system with 1/2 and 1/10 of the convergence time needed by the simulated annealing, respectively.