Or-Parallel Scheduling Strategies Revisited - Dutra, Inês de Castro; Carrusca, Adriana Marino (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2000)
Parallel logic programming systems have been studied for more than a decade. Techniques and scheduling strategies for or-parallel systems have been established for systems that run on centralised memory architectures. As new parallel platforms such as clusters of workstations or clusters of PCs gain populariry, these techniques vastly studied for centralised memory systems may become obsolete and inefficient. In this work we study several scheduling strategies commonly used in or-parallel systems designed for centralised memory architetcures. We simulate these strategies on different parallel environments in order to estimate the costs associated to these scheduling strategies in each environment. We use a benchmark set commonly studied by the or-parallel community. Our study concentrates on simulating top-most, bottom-most, and left-most strategies while modeling costs associated to centralised and distributed memory architectures. We then aimplement our own strategy that selects best work based on the costs to move to a piece of work. Our results show that depending on the characteristics of the search tree none of the three strategies: top, bottom or lefr-most can yield good results. Our proposed strategy based on taking minor costs tasks proved to produce better results than any of these fixed strategies, particulary for distributed-memory platforms.