Improving the efficiency of nondeterministic indepemndent and-parallel systems

We present the design and implementation of the and-parallel component of ACE. ACE is a computational model for the full Prolog language that simultaneously exploits both or-parallelism and independent and-parallelism. A high performance implementation of the ACE model has been realized and its performance reported in this paper. We discuss how some of the standard problems which appear when implementing and-parallel systems are solved in ACE. We then propose a number of optimizations aimed at reducing the overheads and the increased memory consumption which occur in such systems when using previously proposed solutions. Finally, we present results from an implementation of ACE which includes the optimizations proposed. The results show that ACE exploits and-parallelism with high efficiency and high speedups. Furthermore, they also show that the proposed optimizations, which are applicable to many other and-parallel systems, significantly decrease memory consumption and increase speedups and absolute performance both in forwards execution and during backtracking.

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

Abstract is not available.

Using attributed variables in the implementation of concurrent and parallel logic programming systems

Incorporating the possibility of attaching attributes to variables in a logic programming system has been shown to allow the addition of general constraint solving capabilities to it. This approach is very attractive in that by adding a few primitives any logic programming system can be turned into a generic constraint logic programming system in which constraint solving can be user deñned, and at source level - an extreme example of the "glass box" approach. In this paper we propose a different and novel use for the concept of attributed variables: developing a generic parallel/concurrent (constraint) logic programming system, using the same "glass box" flavor. We argüe that a system which implements attributed variables and a few additional primitives can be easily customized at source level to implement many of the languages and execution models of parallelism and concurrency currently proposed, in both shared memory and distributed systems. We illustrate this through examples and report on an implementation of our ideas.

Independent AND-parallel implementation of narrowing

We present a parallel graph narrowing machine, which is used to implement a functional logic language on a shared memory multiprocessor. It is an extensión of an abstract machine for a purely functional language. The result is a programmed graph reduction machine which integrates the mechanisms of unification, backtracking, and independent and-parallelism. In the machine, the subexpressions of an expression can run in parallel. In the case of backtracking, the structure of an expression is used to avoid the reevaluation of subexpressions as far as possible. Deterministic computations are detected. Their results are maintained and need not be reevaluated after backtracking.

Memory performance of and-parallel prolog on shared-memory architectures

The goal of the RAP-WAM AND-parallel Prolog abstract architecture is to provide inference speeds significantly beyond those of sequential systems, while supporting Prolog semantics and preserving sequential performance and storage efficiency. This paper presents simulation results supporting these claims with special emphasis on memory performance on a two-level sharedmemory multiprocessor organization. Several solutions to the cache coherency problem are analyzed. It is shown that RAP-WAM offers good locality and storage efficiency and that it can effectively take advantage of broadcast caches. It is argued that speeds in excess of 2 ML IPS on real applications exhibiting medium parallelism can be attained with current technology.

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.

A note on data-parallelism and (and-parallel) prolog

Abstract is not available.

Mutual Information and Perplexity based Clustering of Dialogue Information for Dynamic Adaptation of Language Models

We present two approaches to cluster dialogue-based information obtained by the speech understanding module and the dialogue manager of a spoken dialogue system. The purpose is to estimate a language model related to each cluster, and use them to dynamically modify the model of the speech recognizer at each dialogue turn. In the first approach we build the cluster tree using local decisions based on a Maximum Normalized Mutual Information criterion. In the second one we take global decisions, based on the optimization of the global perplexity of the combination of the cluster-related LMs. Our experiments show a relative reduction of the word error rate of 15.17%, which helps to improve the performance of the understanding and the dialogue manager modules.

Experimenting with independent and-parallel prolog using standard prolog

This paper presents an approximation to the study of parallel systems using sequential tools. The Independent And-parallelism in Prolog is an example of parallel processing paradigm in the framework of logic programming, and implementations like parallel processing. But this potential can also be explored using only sequential systems. Being the spirit of this paper to show how this can be done with a standard system, only standard Prolog will be used in the implementations included. Such implementations include tests for parallelism in And-Prolog, a correctnesschecking meta-interpreter of and a simulator of parallel execution for

Experimenting with independent and-parallel prolog using standard prolog

This paper presents an approximation to the study of parallel systems using sequential tools. The Independent And-parallelism in Prolog is an example of parallel processing paradigm in the framework of logic programming, and implementations like parallel processing. But this potential can also be explored using only sequential systems. Being the spirit of this paper to show how this can be done with a standard system, only standard Prolog will be used in the implementations included. Such implementations include tests for parallelism in And-Prolog, a correctnesschecking meta-interpreter of and a simulator of parallel execution for

Mutual Information and Perplexity based Clustering of Dialogue Information for Dynamic Adaptation of Language Models

We present two approaches to cluster dialogue-based information obtained by the speech understanding module and the dialogue manager of a spoken dialogue system. The purpose is to estimate a language model related to each cluster, and use them to dynamically modify the model of the speech recognizer at each dialogue turn. In the first approach we build the cluster tree using local decisions based on a Maximum Normalized Mutual Information criterion. In the second one we take global decisions, based on the optimization of the global perplexity of the combination of the cluster-related LMs. Our experiments show a relative reduction of the word error rate of 15.17%, which helps to improve the performance of the understanding and the dialogue manager modules.

Convergent and parallel activation of low-conductance potassium channels by calcium and cAMP-dependent protein kinase.

K+ channels, which have been linked to regulation of electrogenic solute transport as well as Ca2+ influx, represent a locus in hepatocytes for the concerted actions of hormones that employ Ca2+ and cAMP as intracellular messengers. Despite considerable study, the single-channel basis for synergistic effects of Ca2+ and cAMP on hepatocellular K+ conductance is not well understood. To address this question, patch-clamp recording techniques were applied to a model liver cell line, HTC hepatoma cells. Increasing the cytosolic Ca2+ concentration ([Ca2+]i) in HTC cells, either by activation of purinergic receptors with ATP or by inhibition of intracellular Ca2+ sequestration with thapsigargin, activated low-conductance (9-pS) K+ channels. Studies with excised membrane patches suggested that these channels were directly activated by Ca2+. Exposure of HTC cells to a permeant cAMP analog, 8-(4-chlorophenylthio)-cAMP, also activated 9-pS K+ channels but did not change [Ca2+]i. In excised membrane patches, cAMP-dependent protein kinase (the downstream effector of cAMP) activated K+ channels with conductance and selectivity identical to those of channels activated by Ca2+. In addition, cAMP-dependent protein kinase activated a distinct K+ channel type (5 pS). These data represent the differential regulation of low-conductance K+ channels by signaling pathways mediated by Ca2+ and cAMP. Moreover, since low-conductance Ca(2+)-activated K+ channels have been identified in a variety of cell types, these findings suggest that differential regulation of K+ channels by hormones with distinct signaling pathways may provide a mechanism for hormonal control of solute transport and Ca(2+)-dependent cellular functions in the liver as well as other nonexcitable tissues.