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

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

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

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

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服务组合的效率和成功率。     

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完全的.提出一种启发式调度算法,解决与或优先约束任务调度最小完成时间问题.仿真结果表明,该算法在降低算法复杂度的同时较其它相关算法具有更好的调度性能,从而证明在实时优先约束任务调度中引入图优化的理论是解决优先约束任务调度问题的一个有效途径.     

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

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

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图中去。     

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~*是可采纳的,即定能找到最佳解树,进而求解出广义与或树的耗散值。     

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log²n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.     

A parallel hybrid optimization algorithm for fitting interatomic potentials

In this work we present the parallel implementation of a hybrid global optimization algorithm assembled specifically to tackle a class of time consuming interatomic potential fitting problems. The resulting objective function is characterized by large and varying execution times, discontinuity and lack of derivative information. The presented global optimization algorithm corresponds to an irregular, two-level execution task graph where tasks are spawned dynamically. We use the OpenMP tasking model to express the inherent parallelism of the algorithm on shared-memory systems and a runtime library which implements the execution environment for adaptive task-based parallelism on multicore clusters. We describe in detail the hybrid global optimization algorithm and various parallel implementation issues. The proposed methodology is then applied to a specific instance of the interatomic potential fitting problem for the metal titanium. Extensive numerical experiments indicate that the proposed algorithm achieves the best parallel performance. In addition, its serial implementation performs well and therefore can also be used as a general purpose optimization algorithm.     

基于GPU的海量离散点高程并行插值算法

提出一种基于GPU的高程并行插值算法,实现了对三维地表上海量离散点的并行加速渲染。通过高程纹理组织三维地表网格高程数据作为离散点渲染的基础,并通过GLSL编写GPU着色器程序动态控制图形渲染管线,实现视点相关的高程并行插值算法。实验结果表明,提出的基于GPU的高程并行插值算法较传统的内存插值算法,将三维地表上海量离散点的渲染量级从百万级提高到了千万级。     

A massively parallel genetic algorithm for RNA secondary structure prediction

We present a new method for predicting RNA secondary structure based on a genetic algorithm. The algorithm is designed to run on a massively parallel SIMD computer. Statistical analysis shows that the program performs well when compared to a dynamic programming algorithm used to solve the same problem. The program has also pointed out a long-standing simplification in the implementation of the original dynamic programming algorithm that sometimes causes it not to find the optimal secondary structure.     

A parallel alpha/beta tree searching algorithm

This paper gives a theoretical foundation for using parallel processing to search an alpha/beta minimax game tree. A mathematical discussion predicts the behavior of a particular parallel algorithm, Principle Variation Splitting (PVS), along with an enhancement that improves performance for most test cares. After the theoretical discussion, some practical results obtained by running two implementations of the PVS algorithm on a 30-processor tightly coupled shared memory machine are given to show the speedup obtained by parallel processing.