Parallel processing in knowledge-based diagnostic systems

This paper highlights the use of the parallel processing concept in knowledge-based diagnostic systems. A MIMD machine connected in a cubic mesh fashion using Parlog has been suggested to implement such systems. An algorithm supporting the concurrent execution of multiple conflict set rules of the same production system program is presented. A specific application to communication systems maintenance utilizing these principles has been discussed.     

Thinking in parallel: four steps to Parlog

If you are familiar with Prolog but not with Parlog then this tutorial is aimed at you. In what follows I attempt to:

? explain the basics of Parlog

? demonstrate that Parlog programs can be powerful and elegant

? discuss the relationship of Parlog to Prolog, and

? identify some resources which will take you further.

These are what I call ‘four steps to Parlog’.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Parallel programming with logic languages: A survey

Formal properties of logic languages are largely studied; however, their impact on the practice of software design and programming is currently minimal. In this paper we survey some interesting representatives of the family of logic languages aiming at comparing the different capabilities they offer for designing and programming parallel systems. The logic languages Prolog, Aurora, Flat Concurrent Prolog, Parlog, GHC, and DeltaProlog were chosen, because a suitable set of relevant examples has been published, mostly by the language designers themselves. A number of sample programs is used to expose and compare the languages with respect to their object oriented programming capabilities for multiprocess coordination, interprocess communication, and resource management. Special attention is devoted also to metaprogramming as well, seen as a useful technique for specifying and building the operating environments of the languages themselves. The paper ends with a discussion on positive and negative features found comparing these languages, and indicates some guidelines to be followed in the design of new logic languages.     

Meta-interpreters and partial evaluation in Parlog

Since logic programs are executable specifications, the main concern of logic programming, producing efficient programs, is tangential to the mainstream of formal methods. A fashionable automatic transformation technique for producing efficient programs, partial evaluation, applied to the concurrent logic programming language Parlog is discussed.     

A consistent generation of pipeline parallelism and distribution of operations and data among processors

The problem of mapping affine loop nests onto parallel computers with distributed memory is considered. A technique for algorithm scheduling and distributing operations and data over processors is proposed. This technique makes it possible to generate pipeline parallelism and minimize the amount of data exchanges between the processors. The method is adapted for automation and explicitly allows for dependence on outer variables of loops.     

基于CMAC-PID并行控制的主动队列管理方法

主动队列管理对于解决日益严重的网络拥塞问题具有极其重要的意义。本文针对PID主动队列管理算法的参数整定难且不能实时调整,不能适应复杂、非线性网络环境的缺点,提出了一种基于小脑神经网络(CMAC)与PID控制相结合的主动队列管理算法。该算法利用CMAC前馈补偿来确保跟踪误差的快速收敛,降低超调量,采用PID控制器实现回馈控制,保证系统的稳定性,而且抑制扰动。仿真结果表明,基于CMAC-PID并行控制的主动队列管理方法适应于多变的网络环境,较之常规PID主动队列管理算法具有输出误差小、响应速度快、鲁棒性强的优点。     

A parallel approach for determining confidence intervals of variable statistics in large and sparse linear equations with RHS ranges

This study proposes an algorithm capable of working in parallel for solving variable statistics with large and sparse linear equations under given right hand side ranges. A comparative study to the direct linear programming method is conducted under a main central processor and up to four parallel processors. The studied results are reported computationally and discussed. Moreover, the approach can be adapted for the system under domain decompositions structure leading to a better efficiency experimentally in a case example.     

大型化工系统优化的并行算法开发

目前求解大规模化工过程优化与模拟问题时,必然面临的一个困难就是由于系统的大规模所带来的迅速增长的计算时间,解决该问题的关键在于减少求解稀收 大型线性方程组所需的时间,本文提出将一种基于并行先导表法的并行计算方法用于求解稀疏大型线性方程组,通过重排将大型短阵转化为带边块对角形式,进而可进行并行部分LU分解,算法中应用了隐主元和异常主元下限技术剔除无法参与分解的变量,将其放进接口矩阵,。从而保证处的数值稳定性,对一个常减压装置的数据校正问题应用了该并行算法进行求解,检验了算法的可行性,以此算法为核心可以进一步开发面向大型化工系统优化的并行计算算法,充分发挥分布式并行计算节省时间的优势。     

Dynamically reconfigurable dataflow architecture for high-performance digital signal processing

In this paper a dataflow architecture is introduced that maps efficiently onto multi-FPGA platforms and is composed of communication channels which can be dynamically adapted to the dataflow of the algorithm. The reconfiguration of the topology can be accomplished within a single clock cycle while DSP operations are in progress. Finally, the programmability and scalability of the proposed architecture is demonstrated by a high-performance parallel FFT implementation.     

随机行走的电路分析应用及并行化改进

论述了随机行走算法的基本原理,理论分析了给定允许误差和置信概率下,随机行走算法的结束条件;讨论了随机行走算法在电路分析中的应用,并结合应用实例分析了算法的性能;讨论了算法的时间复杂性和影响算法执行时间的主要因素,重点分析了算法的并行特征,提出了采用并行计算技术提高算法性能的新方法,通过与串行算法的实验比较,表明了并行计算技术是提高随机行走算法执行速度的有效方法,比现有的方法适应性更广。     

A lingua franca for concurrent logic programming

Two of the more important concurrent logic programming languages with nonflat guards are GHC and Parlog. They balance the requirements of having clean semantics and providing good control facilities rather differently, and their respective merits are compared and contrasted. Since concurrent logic programming would benefit from both, but neither language is able to express all the programs expressible in the other language, a lingua franca of these languages is defined and justified. A method is given for translating GHC and Parlog to and from it. The method preserves the arities and execution conditions of each clause. It enables a lingua franca implementation to support both languages transparently, and to provide a simple concurrent logic programming language suitable for programming in its own right     

CTL* Model Checking on a Shared-Memory Architecture

In this paper we present a parallel algorithm for CTL* model checking on a virtual shared-memory high-performance parallel machine architecture. The algorithm is automata-driven and follows a games approach where one player wins if the automaton is empty while the other player wins if the automaton is nonempty. We show how this game can be played in parallel using a dynamic load balancing technique to divide the work across the processors. The practicality and effective speedup of the algorithm is illustrated by performance graphs.     

基于改进PSO算法的LSSVM入侵检测模型

在基本PSO算法和线性权重下降PSO算法的基础上,提出一种并行PSO算法,将粒子群分成两组,分别采用不同的惯性权重,各侧重于全局搜索和局部搜索,根据进化代数动态调整两种算法中进化的粒子数。通过仿真实验,证明了并行PSO算法的寻优性能优于基本PSO算法和线性权重下降PSO算法。     

A parallel algorithm for analyzing elasto-plastic problems

Based on the parametric quadratic programming method, an efficient parallel algorithm for analyzing the elasto-plastic problems of structures is presented in this paper. This algorithm makes full use of the architecture environment of parallel computer efficiently. In view of the concept of substructuring technique, many steps in analyzing process can be performed in parallel. This algorithm is programmed on an ELXSI-6400 parallel computer. The numerical tests illustrate that this parallel algorithm has certain advantages over its corresponding sequential algorithm.     

云环境中海量数据的并行分组密码体制研究

云计算环境中,飞速增长的海量数据的安全性越来越受到关注,分组密码算法是保证海量数据安全性的一个有效手段,但面对超大规模的数据量其效率是一个备受关注的问题。提出了一种基于MapReduce架构的并行分组密码机制,能够使标准的分组密码算法应用于大规模的集群环境中,通过并行化来提高海量数据加密与解密的执行效率,并设计了常用的几种并行工作模式。实验证明,提出的算法具有良好的可扩展性和高效的执行性能,能够适用于云计算环境中海量数据的安全保密,为进一步的研究工作奠定了基础。     

The abstract machine and implementation of parallel Parlog

This paper defines an abstract machine for implementing the logic language Parlog on shared memory multiprocessors. A process oriented execution model is introduced that specifies the mechanisms needed to support Parlog’s control facilities and then the abstract machine is presented, which specifies data structures, the instruction set and basic operations of the machine. An implementation of this abstract machine is then described and finally a brief summary of some performance results are given of benchmark programs executed on a shared memory multiprocessor.     

Parallel algorithms for solving linear systems with sparse triangular matrices

In this article, we present two new algorithms for solving given triangular systems in parallel on a shared memory architecture. Multilevel incomplete LU factorization based preconditioners, which have been very successful for solving linear systems iteratively, require these triangular solves. Hence, the algorithms presented here can be seen as parallelizing the application of these preconditioners. The first algorithm solves the triangular matrix by block anti-diagonals. The drawback of this approach is that it can be difficult to choose an appropriate block structure. On the other hand, if a good block partition can be found, this algorithm can be quite effective. The second algorithm takes a hybrid approach by solving the triangular system by block columns and anti-diagonals. It is usually as effective as the first algorithm, but the block structure can be chosen in a nearly optimal manner. Although numerical results indicate that the speed-up can be fairly good, systems with matrices having a strong diagonal structure or narrow bandwidth cannot be solved effectively in parallel. Hence, for these matrices, the results are disappointing. On the other hand, the results are better for matrices having a more uniform distribution of non-zero elements. Although not discussed in this article, these algorithms can possibly be adapted for distributed memory architectures.