Abstract
This paper discusses the design of Dorpp, an or-parallel Prolog system for distributed memory architectures, The problem of sharing the environment across a set of nodes that do not physically share memory is addressed in a novel manner by designing a Virtual Shared Memory (VSM) scheme to specifically meet the requirements of or-parallelism The aim is to avoid the overheads of a general VSM scheme that would provide a stricter level of memory coherence than is actually required, The paper identifies the requirements for memory coherence in or-parallel Prolog, and describes how they can be met cheaply, Simulation results are presented and analyzed in order to highlight key aspects of the system's run-time behavior.

Abstract

Abstract

Abstract
In this paper we use execution-driven simulation of a scalable multiprocessor to evaluate the performance of the Andorra-I parallel logic programming system under invalidate and update-based protocols. We use two versions of Andorra-I. One of them was originally designed for bus-based multiprocessors, while the other is optimised for scalable architectures. We study a well-known invalidate protocol and two different update-based protocols. Our results show that for our sample logic programs the update-based protocols outperform their invalidate-based counterpart for the original version of Andorra-I. In contrast, the optimised version of Andorra-I benefits the most from the invalidate-based protocol, but a hybrid update-based protocol performs as well as the invalidate protocol in most cases. We conclude that parallel logic programming systems can consistently benefit from hybrid update-based protocols. © Springer-Verlag Berlin Heidelberg 2000.

Abstract
One of the advantages of logic programming is the fact that it offers several sources of implicit parallelism. One particularly interesting form of And-Parallelism is Independent And-Parallelism (IAP). Most work on the implementation of IAP is based on Hermenegildo's RAP-WAM. Unfortunately there are some drawbacks associated with the classical approaches based on the use of parcalls and markers. One first observation is that the introduction of parcall frames significantly slows down sequential execution. Moreover, it may result in fine-grained parallel work. We found these problems to be particularly significant in the context of the implementation of combined AND/OR systems. In this paper we take a fresh look at this issue. Our goal is to start from a standard sequential Prolog implementation and try to discover the minimal number of changes that would be required for an efficient implementation of IAP. The key ideas in our design are to (i) to always take advantage of analogy between or-parallelism and IAP; (ii) to avoid creating new structures by adapting preexistingx WAM data-structures wherever possible; and (iii) to avoid major changes to the compiler. The authors would like to acknowledge and thank the contribution and support from Fernando Silva. The work has also benefitted from discussions with Luis Fernando Castro, Ines de Castro Dutra, Kish Shen, Gopal Gupta, and Enrico Pontelli. Our work has been partly supported by Fundaçã da Ciencia e Tecnologia and JNICT under the projects Melodia (JNICT/PBIC/C/TIT/2495/95) and Dolphin (PRAXIS/2/2.l/TIT/1577/95). © 2000 Published by Elsevier B.V.

Abstract
Parallel logic programming (PLP) systems are sophisticated examples of symbolic computing systems. PLP systems address problems such as allocating dynamic memory, scheduling irregular computations, and managing different types of implicit parallelism. Most PLP systems have been developed for bus-based architectures. However, the complexity of PLP systems and the large amount of data they process raise the question of whether logic programming systems can still achieve good performance on modern scalable architectures, such as distributed shared-memory (DSM) systems. In this work we use execution-driven simulation of a cache-coherent DSM architecture to investigate the performance of Andorra-I, a state-of-the-art PLP system, on a modern multiprocessor. The results of this simulation show that Andorra-I exhibits reasonable running time performance, but it does not scale well. Our detailed analysis of cache misses and their sources expose several opportunities for improvements in Andorra-I. Based on this analysis, we modify Andorra-I using a set of simple techniques that led to significantly better running time and scalability. These results suggest that Andorra-I can and should perform well on modern multiprocessors. Furthermore, as Andorra-I shares its main data structures with several PLP systems, we conclude that the methodology and techniques used in our work can greatly benefit these other PLP systems. © 2000 Academic Press.