Task allocation in parallel and distributed computer system

Abstract

The allocation problem is known to be NP-Hard in the most general case where both the number of modules and the number of processors is arbitrary, and it is also Np-Complete in some of the restricted cases. Also, the general scheduling problem, where no restrictions are imposed on the interconnection structure between modules, on the modules processing time and on the number of parallel processors, is NP-Hard in the strong sense. Even under some restrictions, the scheduling problem is NP-Hard. In some other restricted cases, it is known to be NP-Complete. In this thesis, we first review fifty algorithms on both the allocation and the scheduling problem. Next we suggest a reduced layered graph and a variation of Bokhari's [4,6,7] solution to the mapping chains of m tasks onto chains of n heterogeneous processors to achieve better space complexity. We also suggest two heuristic solutions for the same problem in both cases where processors are homogenous or heterogeneous in O(m) and O(nm) running time, respectively. We also adapt Lee and Shin [24] approach, to optimal task assignment in homogenous systems having an n-dimensional array or tree interconnection structure in the presence of attached tasks, on systems having a star graph interconnection structure. We generate the neighborhood tree and solve the problem with O(Nm³) running time where m is the number of tasks to be assigned, and N is the total number of nodes processors in the star graph. We mention that the suggested solution problem can be applied in the case of group graphs on any other type of graphs that can be generated by a permutation of a set of symbols. Finally, we generalize our result for systems having an arbitrary interconnection structure with a run time complexity of O(Nm³).