Highly parallel inference engine PIE —Goal rewriting model and machine architecture—

Logic programming is expected to make knowledge information processing feasible. However, conventional Prolog systems lack both processing power and flexibility for solving large problems. To overcome these limitations, an approach is developed in which natural execution features of logic programs can be represented using Proof Diagrams. AND/ OR parallel processing based on a goal-rewriting model is examined. Then the abstract architecture of a highly parallel inference engine (PIE) is described. PIE makes it possible to achieve logic/control separation in machine architecture. The architecture proposed here is discussed from the viewpoint of its high degree of parallelism and flexibility in problem solving in comparison with other approaches.     

Architecture of a Reduction-Based Parallel Inference Machine: PIM-R

This paper presents a highly parallel machine architecture for logic programs. We propose a Reduction-Based Parallel Inference Machine: PIM-R and describe the parallel execution mechanisms for PIM-R to run Prolog and Concurrent Prolog programs and sofware simulation results. PIM-R uses the structure-copy method. It also uses the only reducible goal copy method, a unique process-structuring method, and the reverse compaction method to decrease the amount, of copying and various copyingrelated operations and the number of packets passing through the network. PIM-R architecture features include the distributed shared memory for Concurrent Prolog, network nodes for efficient packet distribution, and the structure memory to store a part of structured data for reducing the copying overhead.     

A logic programming language based on the Andorra model

The Andorra model is a parallel execution model of logic programs which exploits the dependent and-parallelism and or-parallelism inherent in logic programming. We present a flat subset of a language based on the Andorra model, henceforth called Andorra Prolog, that is intended to subsume both Prolog and the committed choice languages. Flat Andorra, in addition todon’t know anddon’t care nondeterminism, supports control of or-parallel split, synchronisation on variables, and selection of clauses. We show the operational semantics of the language, and its applicability in the domain of committed choice languages. As an examples of the expressiveness of the language, we describe a method for communication between objects by time-stamped messages, which is suitable for expressing distributed discrete event simulation applications. This method depends critically on the ability to expressdon’t know nondeterminism and thus cannot easily be expressed in a committed choice language.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the “polynomial fringe property,” this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the “linear” and “piecewise linear” classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an “elementary chain.” We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the “polynomial fringe property;” hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.     

P-Prolog: A parallel logic language based on exclusive relation

This paper presents a parallel logic programming language named P-Prolog which is being developed as a logic programming language featuring both and- and or-parallelism. Compared with the other parallel logic programming languages, syntactic constructs such as read-only annotation,⁶⁾ mode declaration²⁾ and communication constraints⁷⁾ are not used in P-Prolog. A new concept introduced in P-Prolog is the exclusive relation of guarded Horn clauses. Advances included in P-prolog. are:

1. The synchronization mechanism can determine the direction of data flow dynamically.
2. Guarded Horn clauses can be interpreted as eitherdon’t care nondeterminism ordon’t know non-determinism.

A prototype interpreter of P-Prolog has been implemented in C-Prolog. We are now implementing a P-Prolog interpreter in the C language.     

The occur-check problem in Prolog

We present a method for preprocessing Prolog programs so that their operational semantics will be given by the first-order predicate calculus. Most Prolog implementations do not use a full unification algorithm, for efficiency reasons. The result is that it is possible to create terms having loops in them, whose semantics is not adequately described by first-order logic. Our method finds places where such loops may be created, and adds tests to detect them. This should not appreciably slow down the execution of most Prolog programs.     

A novel architecture of dynamically reconfigurable fused multiply–adder for digital signal processing

Introduction

Multiply-accumulate operation is the most fundamental operation in digital signal processing for image processing, robotics and automatic control. In this paper, a novel architecture of dynamically reconfigurable fused multiply-adder (FMA) is proposed.

Methods

Dynamic reconfiguration is a method that can change the circuit configuration without stop of operation. The proposed circuit provides the following four calculation modes by dynamic reconfiguration: (1) complex number FMA mode, (2) real number FMA mode, (3) complex number parallel calculation mode, and (4) real number parallel calculation mode.  The data format is single precision floating point format based on IEEE754. The proposed circuit was designed using Verilog-HDL. It was simulated by logic circuit simulator, and implemented on FPGA.

Result

As a result of circuit synthesis, we confirmed the reduction of resource in the proposed circuit. Furthermore, we confirmed proper result for each calculation mode by logic simulation and experiment on FPGA.

Conclusion

The proposed circuit provides the four calculation modes by dynamic reconfiguration. We confirmed the reduction of resource and proper result for each calculation mode.     

Set abstraction—An extension of all solutions predicate in logic programming language

The concept of set abstraction is introduced as a simple analogy of that of lambda abstraction in the theory of lambda calculus. The set abstraction is concerned with two extensions concerning Prolog language features: “set expression” and “predicate variable.” It has been argued in the literature that the set expression extension to Prolog does really contribute to the power of the language, while the extension of predicate variables does not add anything to Prolog. Combining these two concepts of extensions to Prolog, we define “set abstraction” as the set expression in which predicate variables are allowed as data objects. In other words, the set abstraction gets involved in the higher order predicate logic. By showing some application examples, it is demonstrated that with the help of predicate variables set abstractions can nicely handle the issues of the second order predicate logic. Further, the implementation programs written in Prolog and Concurrent Prolog are presented.     

Spreadsheets with Incremental Queries as a user interface for logic programming

We believe that currently marketed programs leave unexploited much of the potential of the spreadsheet interface. The purpose of our work is to obtain suggestions for wider application of this interface by showing how to obtain its main features as a subset of logic programming. Our work is based on two observations. The first is that spreadsheets would already be a useful enhancement to interactive languages such as APL and Basic. Although Prolog is also an interactive language, this interface cannot be used in the same direct way. Hence our second observation: the usual query mechanism of Prolog does not provide the kind of interaction this application requires. But it can be provided by the Incremental Query, a new query mechanism for Prolog. The two observations together yield the spreadsheet as a display of the state of the substitution of an incremental query in Prolog. Recalculation of dependent cells is achieved by automatic modification of the query in response to a new increment that would make it unsolvable without the modification.     

Bounded buffer communication in Concurrent Prolog

Concurrent Prolog is a logic-based parallel programming language which was designed and implemented experimentally in Prolog by E. Shapiro. In this paper, we examine the expressive power of communication mechanism based on shared logical variables and show that the language can express both unbounded buffer and bounded buffer stream communication only by shared logical variables and read-only annotation. We will also present the abstraction technique which hides buffer control such as unbounded and bounded inside stream operations and makes it invisible from user programs.     

Data-flow based execution mechanisms of Parallel and Concurrent Prolog

Study attempts to show that our machine architecture based on the data flow model is suitable for two types of logic programming languages with different aims: one is Parallel Prolog and the other is Concurrent Prolog. The data flow model can naturally implement parallel computation, and it has close similarity to these languages. Unification and nondeterministic control, two basic functions of these languages, are represented by data flow graphs and interpreted by the machine. Several representations of variables, that facilitate the development of parallel unification and nondeterministic control mechanisms for these languages, the unification and control primitives needed to execute these languages on this architecture are presented.     

A knowledge assimilation method for logic databases

In this paper we consider a deductive question-answering system for relational databases as a logic database system, and propose a knowledge assimilation method suitable for such a system. The concept of knowledge assimilation for deductive logic is constructed in an implementable form based on the notion of amalgamating object language and metalanguage. This concept calls for checks to be conducted on four subconcepts, provability, contradiction, redundancy, independency, and their corresponding internal database updates. We have implemented this logic database knowledge assimilation program in PROLOG, a logic programming language, and have found PROLOG suitable for knowledge assimilation implementation.     

ORBIT: A parallel computing model of Prolog

This paper proposes a parallel processing model of the Prolog language. The model modifies Or-parallelism by introducing the “process bundle” as a candidate for simultaneous execution. The Process bundle is a subset of backtrack points stacked in depth-first execution. The process bundle includes one or more backtrack points, so it provides a longer process life cycle than the Or-parallel process. A process bundle is dispatched when an idle processor requests a job from an executing processor. The executing processor dispatches a message containing the full environment by which the idle processor can execute the process without any communication with other processors.     

Specialisation of Prolog and FCP programs using abstract interpretation

This paper presents an approach to specialising logic programs which is based on abstract interpretation. Program specialisation involves two stages, the construction of an abstract computation tree and a program construction stage. For the tree construction stage, abstract OLDT resolution is defined and used to construct a complete and finite tree corresponding to a given logic program and a goal. In the program construction stage, a specialised program is extracted from this tree. We focus on two logic programming languages: sequential Prolog and Flat Concurrent Prolog. Although the procedural reading of concurrent logic programs is very different from that of sequential programs, the techniques presented provide a uniform approach to the specialisation of both languages. We present the results for Prolog rigorously, and extend them less formally to Flat Concurrent Prolog. There are two main advantages of basing program specialisation on abstract interpretation. Firstly, termination can be ensured by using abstract interpretations over finite domains, while performing a complete flow analysis of the program. Secondly, correctness of the specialised program is closely related to well-defined consistency conditions on the concrete and abstract interpretations.     

Knowledge information processing language: ShapeUp

A new logic programming language, ShapeUp, is developed. ShapeUp is an expanded Prolog system with string matching facilities. The language has been developed to give programmers a new computer programming environment, especially for knowledge information processing. This area includes natural language comprehension and intelligent text processing systems with better man-machine interfaces. For this kind of application, character string data play a principal part rather than conventional numerical data. In ShapeUp, string patterns are introduced as Prolog ‘terms’. Their matching process is performed inside the unification. Thus, a program is far simpler and easier to write and read in ShapeUp, than in conventional Prolog systems, and program size is extremely reduced.     

Performance analysis of SSE and AVX instructions in multi-core CPUs and GPU computing on FDTD scheme for solid and fluid vibration problems

In this work a unified treatment of solid and fluid vibration problems is developed by means of the Finite-Difference Time-Domain (FDTD). The scheme here proposed takes advantage from a scaling factor in the velocity fields that improves the performance of the method and the vibration analysis in heterogenous media. Moreover, the scheme has been extended in order to simulate both the propagation in porous media and the lossy solid materials. In order to accurately reproduce the interaction of fluids and solids in FDTD both time and spatial resolutions must be reduced compared with the set up used in acoustic FDTD problems. This aspect implies the use of bigger grids and hence more time and memory resources. For reducing the time simulation costs, FDTD code has been adapted in order to exploit the resources available in modern parallel architectures. For CPUs the implicit usage of the advanced vectorial extensions (AVX) in multi-core CPUs has been considered. In addition, the computation has been distributed along the different cores available by means of OpenMP directives. Graphic Processing Units have been also considered and the degree of improvement achieved by means of this parallel architecture has been compared with the highly-tuned CPU scheme by means of the relative speed up. The speed up obtained by the parallel versions implemented were up to 3 (AVX and OpenMP) and 40 (CUDA) times faster than the best sequential version for CPU that also uses OpenMP with auto-vectorization techniques, but non includes implicitely vectorial instructions. Results obtained with both parallel approaches demonstrate that massive parallel programming techniques are mandatory in solid-vibration problems with FDTD.