ON MAPPING PRODUCTION SYSTEMS ONTO MULTIPROCESSORS

In this paper, we consider the problem of mapping rules in a productio n system onto nodes in a multiprocessor system. Since this problem is NP-hard, we present an efficient heuristic algorithm based on simulate d annealing to solve this mapping problem. Compared to conventional si mulated annealing algorithms to solve this problem, where moves or exc hanges are used exclusively as perturbation functions, we use a combin ation of moves and exchanges to achieve consistently better solutions in a reasonable amount of computation time. Further, by restricting th e random acceptance of configurations (mappings) during the annealing process, we achieve a faster convergence. We demonstrate the effective ness of our algorithm by comparing its performance with that of anothe r recently proposed algorithm for mapping rule based systems onto mult iprocessors.