Parallel execution of Prolog programs: a survey

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.

Forced response of Bladed Disks with Damping Mistuning

The effect of mistuning on the vibration of bladed disks has been extensively studied in the past 30 years. Most of these analysis typically cover the case of small variations of the elastic characteristics (mass and stiffness) of the blades. In this work we study the not so common case of the forced response of a stable rotor with damping mistuning. The Asymptotic Mistuning Model (AMM) is used to analyze this problem. The AMM methodology provides a simplified model that describes the effect of blade to blade damping variation, and gives precise information on the underlying mechanisms involved in the action of damping mistuning.

Flexible scheduling for non-deterministic, and-parallel execution of logic programs

Abstract is not available.

ACE: And/or-parallel copying-based execution of logic programs

In this paper we present a novel execution model for parallel implementation of logic programs which is capable of exploiting both independent and-parallelism and or-parallelism in an efficient way. This model extends the stack copying approach, which has been successfully applied in the Muse system to implement or-parallelism, by integrating it with proven techniques used to support independent and-parallelism. We show how all solutions to non-deterministic andparallel goals are found without repetitions. This is done through recomputation as in Prolog (and in various and-parallel systems, like &-Prolog and DDAS), i.e., solutions of and-parallel goals are not shared. We propose a scheme for the efficient management of the address space in a way that is compatible with the apparently incompatible requirements of both and- and or-parallelism. We also show how the full Prolog language, with all its extra-logical features, can be supported in our and-or parallel system so that its sequential semantics is preserved. The resulting system retains the advantages of both purely or-parallel systems as well as purely and-parallel systems. The stack copying scheme together with our proposed memory management scheme can also be used to implement models that combine dependent and-parallelism and or-parallelism, such as Andorra and Prometheus.

Some paradigms for visualizing parallel execution of logic programs

This paper addresses the design of visual paradigms for observing the parallel execution of logic programs. First, an intuitive method is proposed for arriving at the design of a paradigm and its implementation as a tool for a given model of parallelism. This method is based on stepwise reñnement starting from the deñnition of basic notions such as events and observables and some precedence relationships among events which hold for the given model of parallelism. The method is then applied to several types of parallel execution models for logic programs (Orparallelism, Determinate Dependent And parallelism, Restricted and-parallelism) for which visualization paradigms are designed. Finally, VisAndOr, a tool which implements all of these paradigms is presented, together with a discussion of its usefulness through examples.

Relating goal scheduling, precedence, and memory management in and-parallel execution of logic programs

The interactions among three important issues involved in the implementation of logic programs in parallel (goal scheduling, precedence, and memory management) are discussed. A simplified, parallel memory management model and an efficient, load-balancing goal scheduling strategy are presented. It is shown how, for systems which support "don't know" non-determinism, special care has to be taken during goal scheduling if the space recovery characteristics of sequential systems are to be preserved. A solution based on selecting only "newer" goals for execution is described, and an algorithm is proposed for efficiently maintaining and determining precedence relationships and variable ages across parallel goals. It is argued that the proposed schemes and algorithms make it possible to extend the storage performance of sequential systems to parallel execution without the considerable overhead previously associated with it. The results are applicable to a wide class of parallel and coroutining systems, and they represent an efficient alternative to "all heap" or "spaghetti stack" allocation models.

An abstract machine for restricted and-parallel execution of logic programs

Although the sequential execution speed of logic programs has been greatly improved by the concepts introduced in the Warren Abstract Machine (WAM), parallel execution represents the only way to increase this speed beyond the natural limits of sequential systems. However, most proposed parallel logic programming execution models lack the performance optimizations and storage efficiency of sequential systems. This paper presents a parallel abstract machine which is an extension of the WAM and is thus capable of supporting ANDParallelism without giving up the optimizations present in sequential implementations. A suitable instruction set, which can be used as a target by a variety of logic programming languages, is also included. Special instructions are provided to support a generalized version of "Restricted AND-Parallelism" (RAP), a technique which reduces the overhead traditionally associated with the run-time management of variable binding conflicts to a series of simple run-time checks, which select one out of a series of compiled execution graphs.

B-LOG: A branch and bound methodology for the parallel execution of logic programs

We propose a computational methodology -"B-LOG"-, which offers the potential for an effective implementation of Logic Programming in a parallel computer. We also propose a weighting scheme to guide the search process through the graph and we apply the concepts of parallel "branch and bound" algorithms in order to perform a "best-first" search using an information theoretic bound. The concept of "session" is used to speed up the search process in a succession of similar queries. Within a session, we strongly modify the bounds in a local database, while bounds kept in a global database are weakly modified to provide a better initial condition for other sessions. We also propose an implementation scheme based on a database machine using "semantic paging", and the "B-LOG processor" based on a scoreboard driven controller.

Implementation of an event driven scheme for visualizing parallel execution of logic programs

This article presents in an informal way some early results on the design of a series of paradigms for visualization of the parallel execution of logic programs. The results presented here refer to the visualization of or-parallelism, as in MUSE and Aurora, deterministic dependent and-parallelism, as in Andorra-I, and independent and-parallelism as in &-Prolog. A tool has been implemented for this purpose and has been interfaced with these systems. Results are presented showing the visualization of executions from these systems and the usefulness of the resulting tool is briefly discussed.

Implementation of an event driven scheme for visualizing parallel execution of logic programs.

This article presents in an informal way some early results on the design of a series of paradigms for visualization of the parallel execution of logic programs. The results presented here refer to the visualization of or-parallelism, as in MUSE and Aurora, deterministic dependent and-parallelism, as in Andorra-I, and independent and-parallelism as in &-Prolog. A tool has been implemented for this purpose and has been interfaced with these systems. Results are presented showing the visualization of executions from these systems and the usefulness of the resulting tool is briefly discussed.

A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs

In this paper, we examine the issue of memory management in the parallel execution of logic programs. We concentrate on non-deterministic and-parallel schemes which we believe present a relatively general set of problems to be solved, including most of those encountered in the memory management of or-parallel systems. We present a distributed stack memory management model which allows flexible scheduling of goals. Previously proposed models (based on the "Marker model") are lacking in that they impose restrictions on the selection of goals to be executed or they may require consume a large amount of virtual memory. This paper first presents results which imply that the above mentioned shortcomings can have significant performance impacts. An extension of the Marker Model is then proposed which allows flexible scheduling of goals while keeping (virtual) memory consumption down. Measurements are presented which show the advantage of this solution. Methods for handling forward and backward execution, cut and roll back are discussed in the context of the proposed scheme. In addition, the paper shows how the same mechanism for flexible scheduling can be applied to allow the efficient handling of the very general form of suspension that can occur in systems which combine several types of and-parallelism and more sophisticated methods of executing logic programs. We believe that the results are applicable to many and- and or-parallel systems.

Forced Response of Mistuned Bladed Disks: Quantitative Validation of the Asymptotic Description

The effect of small mistuning in the forced response of a bladed disk is analyzed using a recently introduced methodology: the asymptotic mistuning model. The asymptotic mistuning model is an extremely reduced, simplified model that is derived directly from the full formulation of the mistuned bladed disk using a consistent perturbative procedure based on the relative smallness of the mistuning distortion. A detailed description of the derivation of the asymptotic mistuning model for a realistic bladed disk configuration is presented. The asymptotic mistuning model results for several different mistuning patterns and forcing conditions are compared with those from a high-resolution finite element model. The asymptotic mistuning model produces quantitatively accurate results, and, probably more relevant, it gives precise information about the factors (tuned modes and components of the mistuning pattern) that actually play a role in the vibrational forced response of mistuned bladed disks.

The forced oscillations of submerged bodies

The increasing use of very light structures in aerospace applications are given rise to the need of taking into account the effects of the surrounding media in the motion of a structure (as for instance, in modal testing of solar panels or antennae) as it is usually performed in the motion of bodies submerged in water in marine applications. New methods are in development aiming at to determine rigid-body properties (the center of mass position and inertia properties) from the results of oscillations tests (at low frequencies during modal testing, by exciting the rigid-body modes only) by using the equations of the rigid-body dynamics. As it is shown in this paper, the effect of the surrounding media significantly modifies the oscillation dynamics in the case of light structures and therefore this effect should be taken into account in the development of the above-mentioned methods. The aim of the paper is to show that, if a central point exists for the aerodynamic forces acting on the body, the motion equations for the small amplitude rotational and translational oscillations can be expressed in a form which is a generalization of the motion equations for a body in vacuum, thus allowing to obtain a physical idea of the motion and aerodynamic effects and also significantly simplifying the calculation of the solutions and the interpretation of the results. In the formulation developed here the translational oscillations and the rotational motion around the center of mass are decoupled, as is the case for the rigid-body motion in vacuum, whereas in the classical added mass formulation the six motion equations are coupled. Also in this paper the nonsteady motion of small amplitude of a rigid body submerged in an ideal, incompressible fluid is considered in order to define the conditions for the existence of the central point in the case of a three-dimensional body. The results here presented are also of interest in marine applications.

The future obligations of "project manager" as construction integral director (DIPE) in the law of buildings construction in spain (LOE)

In the year 1999 approves the Law of Construction Building (LOE, in Spanish) to regulate a sector such as construction, which contained some shortcomings from the legal point of view. Currently, the LOE has been in force 12 years, changing the spanish world of the construction, due to influenced by internationalization. Within the LOE, there regulating the different actors involved in the construction building, as the Projects design, the Director of Construction, the developer, The builder, Director of execution of the construction (actor only in Spain, similar as construcion engineer and abroad in), control entities and the users, but lacks figure Project manager will assume the delegation of the promoter helping and you organize, direct and management the process. This figure assumes that the market and contracts are not legally regulated in Spain, then should define and establish its regulation in the LOE. (Spain Construction Law) The translation in spanish of the words "Project Manager is owed to Professor Rafael de Heredia in his book Integrated Project Management, as agent acting on behalf of the organization and promoter assuming control of the project, ie Integraded Project Management . Already exist in Spain, AEDIP (Spanish Association Integrated of Project Construction management) which comprises the major companies in “Project Management” in Spain, and MeDIP (Master in Integrated Construction Project) the largest and most advanced studies at the Polytechnic University of Madrid, in "Construction Project Management" they teach which is also in Argentina. The Integrated Project ("Project Management") applied to the construction process is a methodological technique that helps to organize, control and manage the resources of the promoters in the building process. When resources are limited (which is usually most situations) to manage them efficiently becomes very important. Well, we find that in this situation, the resources are not only limited, but it is limited, so a comprehensive control and monitoring of them becomes not only important if not crucial. The alternative of starting from scratch with a team that specializes in developing these follow directly intervening to ensure that scarce resources are used in the best possible way requires the use of a specific methodology (Manual DIP, Matrix Foreign EDR breakdown structure EDP Project, Risk Management and Control, Design Management, et ..), that is the methodology used by "Projects managers" to ensure that the initial objectives of the promoters or investors are met and all actors in process, from design to construction company have the mind aim of the project will do, trying to get their interests do not prevail over the interests of the project. Among the agents listed in the building process, "Project Management" or DIPE (Director Comprehensive building process, a proposed name for possible incorporation into the LOE, ) currently not listed as such in the LOE (Act on Construction Planning ), one of the agents that exist within the building process is not regulated from the legal point of view, no obligations, ie, as is required by law to have a project, a builder, a construction management, etc. DIPE only one who wants to hire you as have been advanced knowledge of their services by the clients they have been hiring these agents, there being no legal obligation as mentioned above, then the market is dictating its ruling on this new figure, as if it were necessary, he was not hired and eventually disappeared from the building process. As the aim of this article is regular the process and implement the name of DIPE in the Spanish Law of buildings construction (LOE)

An abstract machine based execution model for computer architecture design and efficient implementation of logic programs in parallel.

The term "Logic Programming" refers to a variety of computer languages and execution models which are based on the traditional concept of Symbolic Logic. The expressive power of these languages offers promise to be of great assistance in facing the programming challenges of present and future symbolic processing applications in Artificial Intelligence, Knowledge-based systems, and many other areas of computing. The sequential execution speed of logic programs has been greatly improved since the advent of the first interpreters. However, higher inference speeds are still required in order to meet the demands of applications such as those contemplated for next generation computer systems. The execution of logic programs in parallel is currently considered a promising strategy for attaining such inference speeds. Logic Programming in turn appears as a suitable programming paradigm for parallel architectures because of the many opportunities for parallel execution present in the implementation of logic programs. This dissertation presents an efficient parallel execution model for logic programs. The model is described from the source language level down to an "Abstract Machine" level suitable for direct implementation on existing parallel systems or for the design of special purpose parallel architectures. Few assumptions are made at the source language level and therefore the techniques developed and the general Abstract Machine design are applicable to a variety of logic (and also functional) languages. These techniques offer efficient solutions to several areas of parallel Logic Programming implementation previously considered problematic or a source of considerable overhead, such as the detection and handling of variable binding conflicts in AND-Parallelism, the specification of control and management of the execution tree, the treatment of distributed backtracking, and goal scheduling and memory management issues, etc. A parallel Abstract Machine design is offered, specifying data areas, operation, and a suitable instruction set. This design is based on extending to a parallel environment the techniques introduced by the Warren Abstract Machine, which have already made very fast and space efficient sequential systems a reality. Therefore, the model herein presented is capable of retaining sequential execution speed similar to that of high performance sequential systems, while extracting additional gains in speed by efficiently implementing parallel execution. These claims are supported by simulations of the Abstract Machine on sample programs.