| Abstract | To achieve the optimal performance of multiprocessor system, the best way seems to be distributing the workload until the system is evenly loaded. But by the effect of communication overhead, pure load balancing can not lead to optimal system performance. Therefore, two scheduling heuristics, considering the influence of communication cost, are proposed in this thesis, to improve the performance of the system. In this study, The heuristics are applied onto pure load balancing scheduler for OR parallel execution of random search tree. The objectives of this study are: firstly, to evaluate performance of the adaptive dynamic scheduling algorithm for ORparallel execution of random search tree on some typical interconnection networks, secondly, to compare the performance from scheduling using pure load balancing and load balancing with heuristics in various cases. From the situation, we found that the heuristics help improve the performance of the scheduler in almost every cases. The heuristic2, which considers the effect of sw of each child process is better than the other, heuristic, which does not consider that effect. |