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.
The recent idea of logical stochastic resonance is verified in synthetic gene networks induced by non-Gaussian noise. We realize the switching between two kinds of logic gates under optimal moderate noise intensity by...
详细信息
The recent idea of logical stochastic resonance is verified in synthetic gene networks induced by non-Gaussian noise. We realize the switching between two kinds of logic gates under optimal moderate noise intensity by varying two different tunable parameters in a single gene network. Furthermore, in order to obtain more logic operations, thus providing additional information processing capacity, we obtain in a two-dimensional toggle switch model two complementary logic gates and realize the transformation between two logic gates via the methods of changing different parameters. These simulated results contribute to improve the computational power and functionality of the networks.
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.
The problem of writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although auto-parallelization has been studied for many decades, it has succeed...
详细信息
The problem of writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although auto-parallelization has been studied for many decades, it has succeeded only in a few application areas such as dense matrix computations. In particular, auto-parallelization of irregular programs, which are organized around large, pointer-based data structures like graphs, has seemed intractable. The Galois project is taking a fresh look at auto-parallelization. Rather than attempt to parallelize all programs no matter how obscurely they are written, we are designing programming abstractions that permit programmers to highlight opportunities for exploiting parallelism in sequential programs, and building a runtime system that uses these hints to execute the program in parallel. In this paper, we describe the design and implementation of a system based on these ideas. Experimental results for two real-world irregular applications, a Delaunay mesh refinement application and a graphics application that performs agglomerative clustering, demonstrate that this approach is promising.
The article discusses the manner in which transactional memory can ease parallel computer programming. The increased number of execution units, or CPU (Central Processing Unit) cores, provided by CPU manufacturers is ...
详细信息
The article discusses the manner in which transactional memory can ease parallel computer programming. The increased number of execution units, or CPU (Central Processing Unit) cores, provided by CPU manufacturers is allowing programmers to increased the speeds of applications, the author states. Topics of discussion include multiple paths of execution having to work together to complete tasks, attempting to split a computer program into multiple pieces that can be executed in parallel, and the controlled fashion required to write access to shared data.
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.
暂无评论