一个支持副作用处理的受限AND／OR并行执行模型

本文将对开发ＡＮＤ／ＯＲ并行性时的副作用问题加以讨论，并给出一个支持副作用处理的并行执行模型Ｓ－ＲＡＰ／ＬＯＰ。在该模型中，我们在预编译时给子目标分类并加标记ＰＶＳ，这些标记规定了相应子目标的执行条件。在动态运行中，我们使用多机分级同步控制方法管理子目标及子句的并行执行。本文还将对回溯及数据库的维护等问题加以讨论。我们希望以最小的时空代价及最小的并行度损失控制副作用。     

一个并行Prolog系统中的处理机分配算法及实现

本文介绍了一个适用于并行Ｐｒｏｌｏｇ系统的处理机分配算法，利用群调度，通过将空闪处理机有选择地分配给适当的任务。实现了处理机间的负载平衡，并获得高的加速比。     

基于OBDD的含圈与或图搜索算法研究*

与或图搜索是人工智能领域一项一定范围内通用的问题求解技术。基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模。本文在Mahanti等提出的含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明：该算法在处理大规模含圈与或图时具有明显优势。     

A parallel language and its programming system for heterogeneous networks

The paper presents a new parallel language, mpC, designed specially for programming high‐performance computations on heterogeneous networks of computers, as well as its supportive programming environment. The main idea underlying mpC is that an mpC application explicitly defines an abstract network and distributes data, computations and communications over the network. The mpC programming environment uses, at run time, this information as well as information on any real executing network in order to map the application to the real network in such a way that ensures the efficient execution of the application on this real network. Experience of using mpC for solving both regular and irregular real‐life problems on networks of heterogeneous computers is also presented. Copyright © 2000 John Wiley & Sons, Ltd.     

A garbage collection algorithm for shared memory parallel processors

This paper describes a technique for adapting the Morris sliding garbage collection algorithm to execute on parallel machines with shared memory. The algorithm is described within the framework of an implementation of the parallel logic language Parlog. However, the algorithm is a general one and can easily be adapted to parallel Prolog systems and to other languages. The performance of the algorithm executing a few simple Parlog benchmarks is analyzed. Finally, it is shown how the technique for parallelizing the sequential algorithm can be adapted for a semi-space copying algorithm.     

基于AND／OR故障树的数字系统诊断方法

本文给出的基于ＡＮＤ／ＯＲ故障树的诊断方法,具有逻辑严密,表达直观,可进行定量分析等特点。该方法不同于传统的算法诊断,而是通过对故障树节点“与”及“或”逻辑关系的分析,以推理的方式找出故障元件。此外本文所采用的ＡＮＤ／ＯＲ故障树对传统的故障树作了改进、使得它能更加简单明了地表示有故障的数字电路,从而为诊断推理提供方便。最后用Ｐａｓｃａｌ语言编程实现了该方法。     

基于与或图的Web服务组合的研究

现在Web服务技术的应用变得更为普及。单个Web服务只提供有限的功能,难以满足实际应用的需要。Web服务组合已经成为Web服务应用中一个非常重要的研究方面。本文提出了一种基于与或图的Web服务组合方法,该方法通过对已经访问过的服务进行标记,以服务代价作为在与或图中进行搜索的依据,缩小了搜索空间,能够快速找到一种代价很小的服务组合方法。仿真实验表明,该方法提高了Web服务组合的效率和成功率。     

一种求解与/或树的Petri网方法

研究了用Petri网求解人工智能中与/或树的问题,提出了一种把与/或树转换成相应的Petri网,并通过其逆网求得原与/或树的解树的方法,可进而利用模糊Petri网的推理得到与/或树的最优解树。该方法直观高效,拓宽了Petri网的应用领域。     

The BLAZE language: A parallel language for scientific programming

Programming multiprocessor parallel architectures is a complex task. This paper describes a block-structured scientific programming language, BLAZE, designed to simplify this task. BLAZE contains array arithmetic, ‘forall’ loops, and APL-style accumulation operators, which allow natural expression of fine grained parallelism. It also employs an applicative or functional procedure invocation mechanism, which makes it easy for compilers to extract coarse grained parallelism using machine specific program restructuring. Thus BLAZE should allow one to achieve highly parallel execution on multiprocessor architectures, while still providing the user with conceptually sequential control flow.

A central goal in the design of BLAZE is portability across a broad range of parallel architectures. The multiple levels of parallelism present in BLAZE code, in principle, allow a compiler to extract the types of parallelism appropriate for the given architecture, while neglecting the remainder. This paper describes the features of BLAZE, and show how this language would be used in typical scientific programming.     

显式与或图的一种新的贪心搜索算法

文中提出了一种性能很好的能找出显式含圈与或图的最佳解图的贪心算法，给出了其严格的正确性证明，并简单分析了其复杂性。     

一种启发式与/或优先约束任务调度算法

系统描述了与或网模型及与或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与或优先约束任务调度最小完成时间问题.仿真结果表明,该算法在降低算法复杂度的同时较其它相关算法具有更好的调度性能,从而证明在实时优先约束任务调度中引入图优化的理论是解决优先约束任务调度问题的一个有效途径.     

一种基于与或图的语义Web服务自动组合方法研究

单个Web服务提供的功能有限,服务组合成为Web服务应用的一个重要研究方向。提出了一种基于与或图的语义服务自动组合方法。该方法为Web服务引入语义,能将服务搜索空间受限于服务组合与或图中,并能从服务组合与或图中选出最佳组合图,从而达到优化服务组合的目的。仿真实验证明,该方法提高了Web服务组合的成功率和效率。     

A load-balanced parallel sorting algorithm for shared-nothing architectures

With the popularity of parallel database machines based on the shared-nothing architecture, it has become important to find external sorting algorithms which lead to a load-balanced computation, i.e., balanced execution, communication and output. If during the course of the sorting algorithm each processor is equally loaded, parallelism is fully exploited. Similarly, balanced communication will not congest the network traffic. Since sorting can be used to support a number of other relational operations (joins, duplicate elimination, building indexes etc.) data skew produced by sorting can further lead to execution skew at later stages of these operations. In this paper we present a load-balanced parallel sorting algorithm for shared-nothing architectures. It is a multiple-input multiple-output algorithm with four stages, based on a generalization of Batcher's odd-even merge. At each stage then keys are evenly distributed among thep processors (i.e., there is no final sequential merge phase) and the distribution of keys between stages ensures against network congestion. There is no assumption made on the key distribution and the algorithm performs equally well in the presence of duplicate keys. Hence our approach always guarantees its performance, as long asn is greater thanp ³, which is the case of interest for sorting large relations. In addition, processors can be added incrementally. Recommended by: Patrick Valduriez     

基于与或树的柔性BOM结构及其产品配置算法

形式化定义和描述了一种基于与或树的产品结构及其相关特性,基于该结构的BOM设计具有更好的产品配置柔性。在此基础上,还提出了一种面向任务的产品配置算法,能使产品的结构配置适应企业的特定生产任务要求。     

模S下的AND/OR图的启发式搜索算法NAO

本文首先定义了一类新的AND/OR图:图中的结点或为AND结点或为OR结点,而不能是混合型结点,并定义其路径耗散值用三角模S来度量和计算,使其更具有普遍意义,作为通常的AND/OR图AO~*算法的推广,本文依照普通图A~*算法中的启发式估价函数f=g+h,将新AND/OR图中的启发式估价函数F分成G、H两部分,并据此提出了NAO~*算法。本文的结论表明:NAO~*算法与AO~*算法有本质的不同;当H≤H~*时NAO~*可采纳,而且其结果极易推广到一般的AND/OR图中去。     

New Heuristic Distributed Parallel Algorithms for Searching and Planning

This paper proposes new heuristic distributed parallel algorithms for searching and planning,which are based on the concepts of wave concurrent propagations and competitive activation mechanisms.These algorithms are characterized by simplicity and clearness of control strategies for earching,and distinguished abilities in many aspects,such as high speed processing,wide suitability for searching AND/OR implicit graphs,and ease in hardware implementation.     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．     

PProto: An environment for prototyping parallel programs

This paper describes Parallel Proto (PProto), an integrated environment for constructing prototypes of parallel programs. Using functional and performance modeling of dataflow specifications, PProto assists in analysis of high-level software and hardware architectural tradeoffs. Facilities provided by PProto include a visual language and an editor for describing hierarchical dataflow graphs, a resource modeling tool for creating parallel architectures, mechanisms for mapping software components to hardware components, an interactive simulator for prototype interpretation, and a reuse capability. The simulator contains components for instrumenting, animating, debugging, and displaying results of functional and performance models. The Pproto environment is built on top of a substrate for managing user interfaces and database objects to provide consistent views of design objects across system tools.     

A parallel logic language for transaction specification in multidatabase systems

The realization of truly heterogeneous database systems is hampered by two principal obstacles. One is the unsuitability of traditional transaction models; this has led to the proposal of a number of new, advanced transaction models. The second is the lack of appropriate programming support for these advanced concepts. This paper addresses these two issues by pointing out the advantages of using a logic-based approach for the integration of autonomous software systems.The work is supported by the Austrian FWF (Fonds zur Förderung der wissenschaftlichen Forschung), project Multidatabase Transaction Processing, contract number P09020-MAT.     

广义与或树的启发式搜索算法BTAO

本文根据乐观决策准则提出了广义与或树这一新概念,证明了广义与或树的耗散值与其最佳解树的耗散值是等价的。根据新定义的启发式函数h~(Tr)(n,x),提出了广义与或树的自底向上的启发式算法BTAO~*。算法BTAO~*是可采纳的,即定能找到最佳解树,进而求解出广义与或树的耗散值。