We present a novel optimization called Last parallel Call Optimization (LPCO) for parallel systems. The last parallel call optimization can be regarded as a parallel extension of last call optimization found in sequen...
详细信息
ISBN:
(纸本)0818672552
We present a novel optimization called Last parallel Call Optimization (LPCO) for parallel systems. The last parallel call optimization can be regarded as a parallel extension of last call optimization found in sequential systems. While the LPCO is fairly general, we use and-parallel logic programming systems to illustrate it and to report its performance on multiprocessor systems. The last parallel call optimization leads to improved time and space performance for a majority of and-parallel programs. We also present a generalization of the Last parallel Call Optimization called Nested parallel Call Optimization (NPCO). A major advantage of LPCO and NPCO is that parallel systems designed for exploiting control parallelism can automatically exploit data parallelism efficiently.
Most models that have been proposed, or implemented, so far for exploiting both or-parallelism and independent and-parallelism have only considered pure logic programs (pure Prolog). We present an abstract model, call...
详细信息
Most models that have been proposed, or implemented, so far for exploiting both or-parallelism and independent and-parallelism have only considered pure logic programs (pure Prolog). We present an abstract model, called the Composition-Tree, for representing and-or parallelism in full Prolog. The Composition-Tree recomputes independent goals to ensure that Prolog semantics is preserved. We combine the idea of Composition-Tree with ideas developed earlier, to develop an abstract execution model that supports full Prolog semantics while at the same time avoiding redundant inferences when computing solutions to (purely) independent and-parallel goals. This is accomplished by sharing solutions of independent goals when they are pure (i.e. have no side-effects or cuts in them). The Binding Array scheme is extended for and-or parallel execution based on this abstract execution model. This extension enables the Binding Array scheme to support or-parallelism in the presence of independent and-parallelism, both when solutions to independent goals are recomputed as well as when they are shared. We show how extra-logical predicates, such as cuts and side-effects, are supported in this model.
This paper presents a new constructive form of the negation-as-failure rule dedicated to concurrent executions and, based on it, a parallel execution model of general Horn clauses. Referring to the completion understa...
详细信息
ISBN:
(纸本)9783540554370
This paper presents a new constructive form of the negation-as-failure rule dedicated to concurrent executions and, based on it, a parallel execution model of general Horn clauses. Referring to the completion understanding of the programs, this model has been proved sound and as complete as possible when the resolution rule and the negation-as-failure rule are used. Furthermore, it does not suffer from the floundering problem : in contrast, negative literals can be used to produce computed answers as the positive literals can. This new form of negation is based on an equational framework. It introduces generalizations of substitutions, terms and related concepts of instantiation and unification. A theory of such concepts is also presented in the paper.
This paper presents a technique for achieving a class of optimizations related to the reduction of checks within cycles. The technique uses both Program Transformation and Abstract Interpretation. After a first pass o...
详细信息
CARMEL-2 is a high performance VLSI uniprocessor, tuned forFlat Concurrent Prolog (FCP). CARMEL-2 shows almost 5-fold speedup over its predecessor, CARMEL-1, and it achieves 2,400 KLIPS executingappend. This high exec...
详细信息
CARMEL-2 is a high performance VLSI uniprocessor, tuned forFlat Concurrent Prolog (FCP). CARMEL-2 shows almost 5-fold speedup over its predecessor, CARMEL-1, and it achieves 2,400 KLIPS executingappend. This high execution rate was gained as a result of an optimized design, based on an extensive architecture-oriented execution analysis of FCP, and the lessons learned with CARMEL-1. CARMEL-2 is a RISC processor in its character and performance. The instruction set includes only 29 carefully selected instructions. The 10 special instructions, the prudent implementation and pipeline scheme, as well as sophisticated mechanisms such as intelligent dereference, distinguish CARMEL-2 as a RISC processor for FCP.
An abstract machine that supports the parallel logic programming language PARLOG is presented. This abstract machine is designed for the efficient execution of PARLOG on conventional uniprocessors and is thus named th...
详细信息
An abstract machine that supports the parallel logic programming language PARLOG is presented. This abstract machine is designed for the efficient execution of PARLOG on conventional uniprocessors and is thus named the Sequential PARLOG Machine (SPM). The machine’s architecture and instruction set are described and the principles of compilation of PARLOG programs to sequences of abstract machine instructions explained. The machine supports systems programming in PARLOG and in particular PARLOG’s powerful control metacall, which permits programs to initiate, monitor and control subcomputations.
There is a direct correspondence between semantic networks and a subset of logic programs, restricted only to binary predicates. The advantage of the latter is that it can describe not only the nodes and arcs comprisi...
详细信息
There is a direct correspondence between semantic networks and a subset of logic programs, restricted only to binary predicates. The advantage of the latter is that it can describe not only the nodes and arcs comprising a semantic net, but also the data-retrieval operations applied to such nets. The main objective of this paper is to present a data-driven model of computation that permits this subset of logic programs to be executed on a highly parallel computer architecture. We demonstrate how logic programs may be converted into collections of data-flow graphs in which resolution is viewed as a process of finding matches between certain graph templates and portions of the data-flow graphs. This graph fitting process is carried out by messages propagating asynchronously through the data-flow graph; thus computation is entirely data driven, without the need for any centralized control and centralized memory. This permits a potentially large number of independent processing elements to cooperate in solving a given query.
parallel-logicprogramming of analogue computers often presents difficulties to all but the most experienced users. The paper describes an inexpensive method of simplifying the control of iterative problem solutions r...
详细信息
parallel-logicprogramming of analogue computers often presents difficulties to all but the most experienced users. The paper describes an inexpensive method of simplifying the control of iterative problem solutions run on parallel-logic analogue computers by employing a special-purpose sequence controller. The controller stores up to 16 64 bit words, which are transferred in sequence to an output buffer. Most of the bits within each word form the control signals for analogue components. This is mechanised by connections from the controller-output buffer to the analogue-component control lines via an existing parallel-logic patchboard. Conditional (i.e. comparator-controlled) operations and manual control (using logic switches) are possible with only a limited number of analogue components. A compiler for a digital computer enables the user to define the modes and states of analogue components as a sequence of events in time. These events, and the periods of time between them, may be defined by a list of digital-program-source statements, or, conversationally, by replying to questions typed at the user's teleprinter. Either form of input is compiled into the sequence-controller machine code, which is then loaded into the controller memory ready for execution.
暂无评论