An experiment for truly parallel logic programming

A truly parallel logic programming system is proposed. The system is based on the commercially available parallel logic programming language STRAND, which has been extended in order to overcome the inherent limitations of such systems, like AND-type of parallelism, lack of backtracking, limited unification, etc. The system has been tested using an example from the area of natural language processing.     

应用要求与计算机体系结构

本文将从数据通讯、并行计算与人工智能等三方面讨论应用要求对计算机体系结构正在产生的影响.     

Recognition of hand-printed characters based on structural description and inductive logic programming

Character recognition systems can contribute tremendously to the advancement of the automation process and can improve the interaction between man and machine in many applications, including office automation, cheque verification and a large variety of banking, business and data entry applications. The main theme of this paper is the automatic recognition of hand-printed Arabic characters using machine learning. Conventional methods have relied on hand-constructed dictionaries which are tedious to construct and difficult to make tolerant to variation in writing styles. The advantages of machine learning are that it can generalize over the large degree of variation between writing styles and recognition rules can be constructed by example.

The system was tested on a sample of handwritten characters from several individuals whose writing ranged from acceptable to poor in quality and the average correct recognitions rate obtained using cross-validation was 86.65%.     

Runtime support for scalable programming in Java

The paper research is concerned with enabling parallel, high-performance computation—in particular development of scientific software in the network-aware programming language, Java. Traditionally, this kind of computing was done in Fortran. Arguably, Fortran is becoming a marginalized language, with limited economic incentive for vendors to produce modern development environments, optimizing compilers for new hardware, or other kinds of associated software expected of by today’s programmers. Hence, Java looks like a very promising alternative for the future. The paper will discuss in detail a particular environment called HPJava. HPJava is the environment for parallel programming—especially data-parallel scientific programming—in Java. Our HPJava is based around a small set of language extensions designed to support parallel computation with distributed arrays, plus a set of communication libraries. A high-level communication API, Adlib, is developed as an application level communication library suitable for our HPJava. This communication library supports collective operations on distributed arrays. We include Java Object as one of the Adlib communication data types. So we fully support communication of intrinsic Java types, including primitive types, and Java object types.     

The suitability for master/slave concurrency of concurrent euclid,ada and modula

The suitability of Concurrent Euclid, Ada and Modula for a special form of asynchronous concurrency, called master/slave concurrency, is investigated. No language is ideal, with Concurrent Euclid and Modula having major drawbacks. The conclusion lists the features desirable in a language for master/slave concurrency.     

Parallel Difference Schemes For Heat Conduction Equations * The work is supported by the Chinese National Key Program for Developing Basic Science,G1999032801, the National Natural Science Foundation of China (19932010) and the Foundation of CAEP (2X0107)

In this paper a parallel difference scheme based on Dufort-Frankel scheme and the classic implicit scheme for linear heat conduction equations is studied. In this procedure, the values at subdomain interfaces are calculated by using the Dufort-Frankel scheme, and then these values serve as Dirichlet boundary data for the implicit scheme in the subdomains. The weak necessary condition of the unconditional stability of the parallel difference scheme is proved. Numerical experiments indicates that the parallel difference scheme has good parallelism, and has better accuracy than the fully implicit scheme.     

Genetic programming for prediction and control

The relatively new field of genetic programming has received a lot of attention during the last few years. This is because of its potential for generating functions which are able to solve specific problems. This paper begins with an extensive overview of the field, highlighting its power and limitations and providing practical tips and techniques for the successful application of genetic programming in general domains. Following this, emphasis is placed on the application of genetic programming to prediction and control. These two domains are of extreme importance in many disciplines. Results are presented for an oral cancer prediction task and a satellite attitude control problem. Finally, the paper discusses how the convergence of genetic programming can be significantly speeded up through bulk synchronous model parallelisation.     

有界连续空间中MEC算法的收敛性分析

思维进化计算(MEC)是模拟人类思维进化过程的一种新的进化计算方法,是基于GA存在的问题提出的。MEC主要由趋同和异化两种操作构成。该文从理论上对趋同和异化操作进行了详细的描述,修正了文眼15演中的错误结论,证明了趋同迭代产生的子群体散布中心序列收敛到局部最优态集,给出了收敛速率的上界估计,并分析了算法的全局收敛性。     

Bounded size dictionary compression: SC-completeness and NC algorithms

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(log^kn), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(log^kn) space (that is, SC^k). We also introduce a variation of this heuristic that turns out to be an SC^k-complete problem (the original heuristic belongs to SC^k+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given.     

Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

A tuple channel-based coordination model for parallel and distributed programming

This paper presents tuple channel model (TCM), a new coordination model for parallel and distributed programming. Our proposal is based on the use of tuple channels (TCs) to model the communication and synchronization of different activities. TCs are multi-point channels that allow complex data structures to be communicated among multiple producers and consumers. This communication model allows incremental and backward communication to be expressed, providing an elegant way of implicit and direct communication and reactive control. TCs can be dynamically interconnected through the use of user-defined connectors, providing great flexibility for the definition of complex and dynamic interaction protocols. TCM also provides a simple service management mechanism, by means of which open systems can be implemented in an appropriate way. The suitability, expressiveness and programming techniques of the model are presented by means of some illustrative examples. In addition, some implementation details of the developed prototypes are sketched and we show the preliminary results demonstrating the efficiency of the proposal.     

A concurrency control scheme for mobile transactions in broadcast disk environments

Broadcast disk technique has been often used to disseminate frequently requested data efficiently to a large volume of mobile clients over wireless channels. In broadcast disk environments, a server often broadcasts different data items with differing frequencies to reflect the skewed data access patterns of mobile clients. Previously proposed concurrency control methods for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. These protocols perform poorly in broadcast disk environments where the data access patterns of mobile transactions are skewed. In broadcast disk environments, the time length of a broadcast cycle usually becomes large to reflect the skewed data access patterns. This will often cause read-only transactions to access old data items rather than the latest data items. Furthermore, updating mobile transactions will be frequently aborted and restarted in the final validation stage due to the update conflict of the same data items with high access frequencies. This problem will increase the average response time of the update mobile transactions and waste the uplink communication bandwidth. In this paper, we extend the existing FBOCC concurrency control method to efficiently handle mobile transactions with skewed data access patterns in broadcast disk environments. Our method allows read-only transactions to access the more updated data, and reduces the average response time of updating transactions through early aborts and restarts. Our method also reduces the amount of uplink communication bandwidth for the final validation of the update transactions. We present an in-depth experimental analysis of our method by comparing with existing concurrency control protocols. Our performance analysis shows that it significantly decreases the average response time and the amount of uplink bandwidths over existing methods.     

以太网络并行科学计算中通信损耗的定量描述

大型科学计算中常采用并行算法［１,２］,负载平衡是并行计算中的一个很重要的方面 １３,４１。在平衡负载的过程中需要用到通信损耗来描述网络并行计算的速度。该文探讨分析了影响通信损耗的各种因素,提出了一种新的以太网环境中的通信损耗的定量描述方法;阐述了并行科学计算在进行中通信损耗的实际获得过程。实验结果表明,该通信损耗的表示形式在实际应用中是正确可靠的。     

Synchronization barrier and related tools for shared memory parallel programming

The synchronization barrier is a point in the program where the processing elements (PEs) wait until all the PEs have arrived at this point. In a reduction computation, given a commutative and associative binary operationop, one needs to reduce valuesa ₀,...,a _N-1, stored in PEs 0,...,N-1 to a single valuea _*=a ₀ op a, op...op a _N -1 and then to broadcast the resulta _* to all PEs. This computation is often followed by a synchronization barrier. Routines to perform these functions are frequently required in parallel programs. Simple and efficient, workingC-language routines for the parallel barrier synchronization and reduction computations are presented. The codes are appropriate for a CREW (concurrent-read-exclusive-write) or EREW parallel random access shared memory MIMD computer. They require only shared memory read and write; no locks, semaphores etc. are needed. The running time of each of these routines isO(logN). The amount of shared memory required and the number of shared memory accesses generated are botO(N). These are the asymptotically minimum values for the three parameters. The algorithms employ the obvious computational scheme involving a binary tree. Examples of applications for these routines and results of performance testing on the Sequent Balance 21000 computer are presented.An abstract of this article appeared inProc. 1989 Int. Conf. Parallel Processing, p. II-175.     

加权关联规则的并行挖掘算法

关联规则是数据挖掘的重要研究内容之一,而传统的算法均为串行算法且将数据库项目按平等一致方式加以处理。文章提出了加权关联规则的并行挖掘算法,探讨了相关的数据结构,并对算法进行了定性分析。     

Distributed reasoning with ontologies and rules in order-sorted logic programming

Integrating ontologies and rules on the Semantic Web enables software agents to interoperate between them; however, this leads to two problems. First, reasoning services in SWRL (a combination of OWL and RuleML) are not decidable. Second, no studies have focused on distributed reasoning services for integrating ontologies and rules in multiple knowledge bases. In order to address these problems, we consider distributed reasoning services for ontologies and rules with decidable and effective computation. In this paper, we describe multiple order-sorted logic programming that transfers rigid properties from knowledge bases. Our order-sorted logic contains types (rigid sorts), non-rigid sorts, and unary predicates that distinctly express essential sorts, non-essential sorts, and non-sortal properties. We formalize the order-sorted Horn-clause calculus for such properties in a single knowledge base. This calculus is extended by embedding rigid-property derivation for multiple knowledge bases, each of which can transfer rigid-property information from other knowledge bases. In order to enable the reasoning to be effective and decidable, we design a query-answering system that combines order-sorted linear resolution and rigid-property resolution as top-down algorithms.     

Implementing tactics and tacticals in a higher-order logic programming language

We argue that a logic programming language with a higher-order intuitionistic logic as its foundation can be used both to naturally specify and implement tactic-style theorem provers. The language extends traditional logic programming languages by replacing first-order terms with simply-typed -terms, replacing first-order unification with higher-order unification, and allowing implication and universal quantification in queries and the bodies of clauses. Inference rules for a variety of inference systems can be naturally specified in this language. The higher-order features of the language contribute to a concise specification of provisos concerning variable occurrences in formulas and the discharge of assumptions present in many inference systems. Tactics and tacticals, which provide a framework for high-level control over search for proofs, can be directly and naturally implemented in the extended language. This framework serves as a starting point for implementing theorem provers and proof systems that can integrate many diversified operations on formulas and proofs for a variety of logics. We present an extensive set of examples that have been implemented in the higher-order logic programming language Prolog.     

Query processing in annotated logic programming: Theory and implementation

Annotated logic is a formalism that has been applied to a variety of situations in knowledge representation, expert database systems, quantitative reasoning, and hybrid databases [6], [13], [19], [20], [21], [22], [23], [24], [30], [33], [35], [36]. Annotated Logic Programming (ALP) is a subset of annotated logics that can be used directly for programming annotated logic applications [22], [23]. A top-down query processing procedure containing elements of constraint solving, called ca-resolution, is developed for ALPs. It simplifies a number of previously proposed procedures, and also improves on their efficiency. The key to its development is in observing that satisfaction, as introduced originally for ALPs, may be naturally generalized. A computer implementation of ca-resolution for ALPs is described which offers important theoretical and practical insights. Strategies for improving its efficiency are discussed.This material is based upon work supported by the NSF under Grant CCR9225037. A preliminary version of this paper appears in the proceedings of the International Conference on Logic Programming, 1994.     

Use of parallel deterministic dynamic programming and hierarchical adaptive genetic algorithm for reservoir operation optimization

Reservoir operation optimization (ROO) is a complicated dynamically constrained nonlinear problem that is important in the context of reservoir system operation. In this study, parallel deterministic dynamic programming (PDDP) and a hierarchical adaptive genetic algorithm (HAGA) are proposed to solve the problem, which involves many conflicting objectives and constraints. In the PDDP method, multi-threads are found to exhibit better speed-up than single threads and to perform well for up to four threads. In the HAGA, an adaptive dynamic parameter control mechanism is applied to determine parameter settings, and an elite individual is preserved in the archive from the first hierarchy to the second hierarchy. Compared with other methods, the HAGA provides a better operational result with greater effectiveness and robustness because of the population diversity created by the archive operator. Comparison of the results of the HAGA and PDDP shows two contradictory objectives in the ROO problem-economy and reliability. The simulation results reveal that: compared with proposed PDDP, the proposed HAGA integrated with parallel model appears to be better in terms of power generation benefit and computational efficiency.     

A modified newton method in parallel circular iteration of single-step and double-step

In this paper, two theorems for the convergence of a modified Newton method in parallel circular iteration are given. The convergent condition of single-step method's circular iteration is relaxed compared with the classical theorem in the same field, while the one of the first proposed double-step method of the five-order is obtained accurately as well.