Rapid developments of multicore processors in the last ten years have accelerated the advancements in concurrency platforms. Performance of bottom-up resolution algorithms used in logicprogramming and artificial inte...
详细信息
ISBN:
(纸本)9781479929719
Rapid developments of multicore processors in the last ten years have accelerated the advancements in concurrency platforms. Performance of bottom-up resolution algorithms used in logicprogramming and artificial intelligent systems, can potentially be improved using the parallelprogramming constructs offered by these platforms (e.g., OpenMP, Cilk++, etc.). In this work we use cilk++ to implement a parallel bottom-up resolution algorithm, and study how different parallelprogramming constructs affect its performance. Our experimental results show that a careful cilk++ implementation of the algorithm can lead to significant speedup w.r.t. its traditional serial implementation.
logicprogramming, a class of programming languages based on first-order logic, provides simple and efficient tools for goal-oriented proof-search. logicprogramming supports recursive computations, and some logic pro...
详细信息
ISBN:
(纸本)9783642177958
logicprogramming, a class of programming languages based on first-order logic, provides simple and efficient tools for goal-oriented proof-search. logicprogramming supports recursive computations, and some logic programs resemble the inductive or coinductive definitions written in functional programming languages. In this paper, we give a coalgebraic semantics to logicprogramming. We show that ground logic programs can be modelled by either P-f P-f-coalgebras or P-f List-coalgebras on Set. We analyse different kinds of derivation strategies and derivation trees (proof-trees, SLD-trees, and-or parallel trees) used in logicprogramming, and show how they can be modelled coalgebraically.
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 differ...
详细信息
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 logicprogramming systems can still achieve good performance on modern scalable architectures, such its 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. bat 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 those other PLP systems. (C) 2000 Academic Press.
We present a new model for parallel evaluation of logic programs. This model can exploit the main sources of parallelism that the language of logic expresses: Independent AND parallelism and OR parallelism, together w...
详细信息
We present a new model for parallel evaluation of logic programs. This model can exploit the main sources of parallelism that the language of logic expresses: Independent AND parallelism and OR parallelism, together with a secondary source emerging as a consequence of the Independent AND parallelism: the producer/consumer parallelism. The efficiency is derived from the use of ordered structures for managing the information generated throughout the search process. The model is suitable for evaluating programs with a high degree of non-determinism because it never generates two processes for solving the same subgoal and hence it can exploit the same real parallelism generating a lower number of processes than other models. As an application example, we consider the Job Shop Scheduling problem. We report experimental results showing that logic programs can be designed that exhibit parallelism, and that the use of heuristic information translates into speedup in obtaining answers.
In the fifth generation computer systems (FGCS) project, a parallel logic programming language, KL1, was adopted as the project's kernel language. It was not only used to determine architectures of highly parallel...
详细信息
In the fifth generation computer systems (FGCS) project, a parallel logic programming language, KL1, was adopted as the project's kernel language. It was not only used to determine architectures of highly parallel machines called parallel inference machines (PIMs) consisting of about 1000 element processors but also used as a system description language to develop basic software such as a parallel operating system (PIMOS), and symbolic processing and knowledge processing application systems such as knowledge description languages, a parallel theorem prover, and a protein sequence analysis program. It achieved great success in exploiting of parallelism involved in several important application systems. The prototype of the FGCS attained a linear speed-up that was proportional to the number of processing elements (PEs) for the application systems we had targeted. The MGTP parallel theorem prover was one of such application systems, and can prove theorems based on full first-order logic. Thus, it indicates the possibility of designing a new practical knowledge representation language whose expressive power will be much greater than that of conventional ones. In the FGCS follow-on project, KL1 and its programming system were ported to Unix-based stock parallel machines. This new system called KLIC is expected to greatly extend the use of highly parallel systems. (C) 1999 Elsevier Science B.V. All rights reserved.
Tabling or memoing is a technique where one stores intermediate answers to a problem so that they can be reused in further calls. Tabling is of interest to logicprogramming because it addresses some of the most signi...
详细信息
In this paper we present an effective strategy to compute a partial order relation among the literals of a query given by a conjuction of first order literals. This ordering expresses sufficient conditions in order fo...
详细信息
In this paper we present an effective strategy to compute a partial order relation among the literals of a query given by a conjuction of first order literals. This ordering expresses sufficient conditions in order for the subgoals of the query were independent each one to the others and hence they can be evaluated in parallel. To represent the partial ordering so that an efficient strategy to join partial solutions from the subgoals can be obtained, we introduce a structure named the Data Flow Lattice. ne problem of determining the optimum partial ordering is proved to be NP-hard, therefore we propose an heuristic algorithm that requires polynomial time in the number of literals and variables of the query. We add also an illustrative example of the algorithm performance.
A truly parallel logic programming system is proposed. The system is based on the commercially available parallel logic programming language STRAND, which has been extended in order to overcome the inherent limitation...
详细信息
A truly parallel logic programming system is proposed. The system is based on the commercially available parallel logic programming language STRAND, which has been extended in order to overcome the inherent limitations of such systems, like AND-type of parallelism, lack of backtracking, limited unification, etc. The system has been tested using an example from the area of natural language processing.
A transformational approach for proving termination of parallellogic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed;it exploits the fact that unif...
详细信息
A transformational approach for proving termination of parallellogic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed;it exploits the fact that unifications in GHC-resolution correspond to matchings. The termination of a GHC program for a class of queries is implied by the termination of the resulting rewrite system. This approach facilitates the applicability of a wide range of termination techniques developed for rewrite systems in proving termination of GHC programs. The method consists of three steps: (a) deriving moding information from a given GHC program, (b) transforming the GHC program into a term rewriting system using the moding information, and finally (c) proving termination of the resulting rewrite system. Using this method, the termination of many benchmark GHC programs such as quick-sort, merge-sort, merge, split, fair-split and append, etc., can be proved.
Much work has been done in the areas of and-parallelism and data-parallelism in logic Programs. Such work has proceeded to a certain extent in an independent fashion. Both types of parallelism offer advantages and dis...
详细信息
Much work has been done in the areas of and-parallelism and data-parallelism in logic Programs. Such work has proceeded to a certain extent in an independent fashion. Both types of parallelism offer advantages and disadvantages. Traditional (and-) parallel models offer generality, being able to exploit parallelism in a large class of programs (including that exploited by data-parallelism techniques). Data-parallelism techniques on the other hand offer increased performance for a restricted class of programs. The thesis of this paper is that these two forms of parallelism are not fundamentally different and that relating them opens the possibility of obtaining the advantages of both within the same system. Some relevant issues are discussed and solutions proposed. The discussion is illustrated through visualizations of actual parallel executions implementing the ideas proposed. Copyright (C) 1996 Elsevier Science Ltd
暂无评论