A case study of parallel execution of a rule-based expert system

We report on a case study of the potentials for parallel execution of the inference engine of EMYCIN, a rule-based expert system. Multilisp, which supports parallel execution of tasks by means of thefuture construct, is used to implement the parallel version of the backwards-chaining inference engine. The study uses explicit specification of parallel execution and synchronization to attain parallel execution. It suggests some general techniques for obtaining parallel execution in expert systems and other applications.     

BaLinda Lisp: Design and implementation

BaLinda Lisp is a parallel Lisp dialect employing a shared memory model of parallel processing together with a subset of the Linda tuple space operators. Also included in the design is speculative processing. The aim is to have shared memory multiprocessing with the tuple space acting as the main data structure through which synchronization is done. The result is a flexible programming language. In this paper, we shall describe the design philosophy of BaLinda Lisp, discuss its implementation on three multiprocessing platforms, give examples of programs written in BaLinda Lisp and discuss future work on the language.     

Realtime digital signal processing system using a parallel processing architecture

A low cost, high-speed, general-purpose ditigal signal processing system was constructed using the TMS32010 digital signal processor. The system was designed with simplicity, compactness, flexibility and expandibility in mind. A parallel processing architecture was adopted to achieve realtime performance. Four processors were used in the prototype system, but this can be expanded easily. Interprocessor data transfer and communications with the host computer are facilitated via a single common bus and a bank of shared memory. A one-dimensional digital FIR filter and a realtime FFT program were used to evaluate the performance of the system. In addition, a realtime spectrogram was implemented as an application example.     

基于机群架构的并行数据库实现技术研究

在总结了现有并行数据库实现模型的基础上,基于"半重写变换"模型[1]实现了一个并行数据库系统的原型.通过对数据划分/重划分、并行选择、并行排序、并行连接等关键操作的实验分析,指出了.半重写变换"模型存在的缺陷,并提出了一种混合式的改进模型.从理论上说,在机群架构下实现并行数据库系统,这种混合模型较单一模型更有优势.     

Implementing concurrent scheme for the Mayfly distributed parallel processing system

This paper discusses a parallel Lisp system developed for a distributed memory, parallel processor, the Mayfly. The language has been adapted to the problems of distributed data by providing a tight coupling of control and data, including mechanisms for mutual exclusion and data sharing. The language was primarily designed to execute on the Mayfly, but also runs on networked workstations. Initially, we show the relevant parts of the language as seen by the user. Then we concentrate on the system Lisp level implementation of these constructs with particular attention toagents, a mechanism for limiting the cost of remote operations. Briefly mentioned are the low-level kernel hardware and software support of the system Lisp primitives.Work Supported in part by the Hewlett-Packard Corporation.     

存储器中易失性用户大数据并行处理控制系统

传统的并行处理控制系统在处理存储器中易失性用户大数据时,对CPU的利用率很低,导致处理控制工作精密度差。为了解决此问题,设计了一种新的大数据并行处理控制系统,分别对系统的硬件和软件进行设计,分析了控制系统中各组件的结构关系,重点设计了系统总线、中央处理器;软件部分分为打开文件、更新文件、监测运行、数据连接四步。为了检测系统的可行性,与传统并行处理控制系统进行实验对比,结果显示,设计的并行处理控制系统能够充足的利用系统CPU,精确地处理存储器中易失性用户大数据。该系统具有超强的工作能力,值得推广使用。     

E-parser: An implementation of a deterministic GB-related parsing system

This paper describes an implementation of a deterministic parsing system, described in Nordgård (1993). The syntax of heuristic rules and how the rules interact with the basic operations of the parser constitute the bulk of the article. The implementation is written in Medley Interlisp, and the system can be run on Sun or Xerox workstations. Torbjørn Nordgård is associate professor of computational linguistics in the Department of Linguistics and Phonetics, University of Bergen. His research interests include computational linguistics, theoretical linguistics, in particular formal syntax and semantics, and philosophy of science. He has published A GB-Related Parser for Norwegian(Bern: Peter Lang) and he is one of the authors of Generativ syntaks: Ei innføring via norsk(Oslo: Novus).     

基于WordSmith软件的平行语料库加工处理系统设计

平行语料库加工处理过程中,传统的系统很难将当前字的标记与其它序列字符的同现特征统计出来,导致切分错误情况频频发生.为此,设计基于WordSmith软件的平行语料库加工处理系统.在硬件设计上,使用S3C6410处理器实现文本分析功能,生成标注文件,用于后续加工处理;在软件设计上,使用WordSmith软件提取出语料库中的...     

并行概念学习的探讨

为了解决机器学习的低效问题,将并行技术中引入概念学习。在深入探讨概念学习本质的基础上,分析了并行概念学习的可能性及其前景;研究了建立一个并行概念学习系统所需考虑的几个问题;探索性地给出了一种特殊的实例——概念描述语言;在此语言基础上提出了一种并行概念学习系统的实现方案,并详细讨论了系统的体系结构和学习算法。     

Formulation of parallel image processing tasks

An increasing awareness of the need for high speed parallel processing systems for image analysis has stimulated a great deal of interest in the study of such systems. These studies have focussed primarily on specific algorithms and while they demonstrated the utility of such an approach, few general principles have evolved. As a result, it is still uncertain how one may go about addressing a given application. This paper first presents techniques for formulating parallel image processing tasks by focussing on one or more components of an image processing environment. Then a parallel processing model is proposed which specifies the interaction among tasks formulated in this manner. The techniques and model enable one to determine constraints on architectural features required to achieve predefined performance levels and compare and contrast different formulations.     

Mathematical modeling of a parallel global optimization algorithm

We describe the formation of a mathematical model of a reasonably complex parallel global optimization program, and the use of this model to assist in the development and understanding of the underlying parallel algorithm. First we discuss the formation of a model that accurately matched execution times of the parallel program on an Intel hypercube. Then we discuss the use of this model to simulate the behavior of our parallel algorithm in a variety of new situations, in order to detect weaknesses in the parallel algorithm and analyze possible improvements to it. We believe that this combination of parallel computer implementation and mathematical modeling is a useful approach in parallel algorithm development.     

Exploitation of parallel processing for implementing high-performance deduction systems

We describe a scheme for parallelizing first-order logic deduction systems. This scheme has been successfully used for parallelizing OTTER, which is a sequential deduction system developed at Argonne National Laboratory. This parallel deduction system, called PARRallel OTter-II (PARROT-II) has attained real speedups in excess of 20 over the best results of current sequential deduction systems. We believe that our results are of interest for two distinct reasons: (1) this is (as far as we know) the first case in which a system has successfully exploited parallelism to outperform the best sequential deduction systems on difficult problems, and (2) we believe that our approach generalizes to other deduction paradigms (e.g., term rewriting systems).This paper discusses the motivation for developing the scheme used by PARROT-II and the implementation details of PARROT-II. It also presents timing results for PARROT-II for some benchmark problems.Work submitted as partial fulfillment of the requirements for the doctoral degree at the Graduate College of the University of Illinois at Chicago. This work was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

A parallel distributed control architecture for multiple robot systems using a network of microcomputers

This paper presents the design and implementation of a parallel distributed control architecture for industrial multiple robot systems. The design methodology is based on a concept of discrete states and actions, and a robotic task is represented as a sequence of primitive actions. For cooperative or exclusive tasks at the synchronous level of multiple robot systems, Petri net representation is applied, and discrete event-driven control is implemented as a data flow network of concurrent processes communicating with each other. Implementation of multiprocessing control on a microcomputer and a network of microcomputers is discussed.     

Direct function calls in lisp

This paper compares implementation strategies for function calls in compiled Lisp. We discuss various ways of allowing compiled call instructions to branch immediately to a callee's code (direct calls), rather than to refer to a symbol that points to the function's definition (indirect calls). We examine the performance of direct and indirect function calls on the VAX and MC68020, and on a RISC architecture—the SPUR multiprocessor. For the SPUR architecture, single indirection slows applications by 3–4%, and double indirection slows applications by 6–8%. The performance benefits of direct function calls are considerably smaller for the VAX and MC68020 architectures. We discuss also the costs and complexities involved in implementing direct function calls.This research was funded by DARPA contract number N00039-85-C-0269 as part of the SPUR research project.     

A parallel multipolar boundary element method for internal stokes flows

A multipolar expansion technique is applied to the Boundary Element Method (direct and indirect formulation) in order to solve the two-dimensional internal Stokes Flow with first kind boundary conditions. The algorithm is based on a multipolar expansion for the far field and numerical evaluation for the inner field. Due to the nature of the algorithm, it is necessary to resort to the use of an iterative solver for the resulting algebraic linear system of equations. In comparison with the direct BEM formulation, the indirect formulation is more stable with iterative solvers, and does not need to be preconditioned to obtain a fast rate of convergence. A parallel implementation is designed to take advantage of the natural domain decomposition of fast multipolar techniques and bring further improvement. A good result in memory saving and computing time is obtained that enable us to run huge examples which are prohibitive for traditional BEM implementations.     

An efficient implementation of parallel eigenvalue computation for massively parallel processing

This paper describes an efficient implementation and evaluation of a parallel eigensolver for computing all eigenvalues of dense symmetric matrices. Our eigensolver uses a Householder tridiagonalization method, which has higher parallelism and performance than conventional methods when problem size is relatively small, e.g., the order of 10,000. This is very important for relevant practical applications, where many diagonalizations for such matrices are required so often. The routine was evaluated on the 1024 processors HITACHI SR2201, and giving speedup ratios of about 2–5 times as compared to the ScaLAPACK library on 1024 processors of the HITACHI SR2201.     

发动机ECU标定系统的实时数据处理设计与应用

发动机ECU标定系统需要标定人员根据实时工况数据来即时调整ECU的控制策略。即时显示发动机运行状态,同时存储实时数据对于标定工作意义重大。提出一种发动机ECU标定系统结构实现方法,实现工况数据的实时采集与标定数据的在线标定。设计一种改进的行程编码算法对数据进行无损压缩,便于数据的传输、存储、查询;利用数据缓存队列、优化线程调度策略,将任务分配到不同处理器上运行,保证系统的实时响应与数据处理效率。在发动机ECU标定系统的应用中表明该方法满足了标定系统对实时性、准确性、高效性的要求。     

Continuation-based control in the implementation of parallel logic programs

Continuations are used to define the flow of messages between low level tasks in a parallel logic programming language. A combination of compiler and runtime operations reduces message traffic by up to 50% when success continuations are passed as parameters in messages that start new processes. Continuations are also the key to fast task switching, a critical operation in this fine grain parallel system. Data from sample programs shows the effectiveness of continuations in reducing message traffic and the speed with which task switches are performed on a typical host architecture.Supported by NSF Grant CCR-8707177 and grants from Motorola, Inc, and Hewlett-Packard Corp.     

NCL电路并行处理结构研究

针对NCL电路数据编码方式的特点,提出了一种并行数据处理的NCL电路结构,通过同时对两路双轨编码数据流的并行处理,提前计算出下一个无效数据,缩短了无效数据维持时间。此结构应用到4×4乘法器的设计,采用COMS 0.18 ?滋m工艺,乘法器在非流水模式下和2级流水模式下分别进行了综合、布局布线和仿真,与传统NCL 4×4乘法器相比,无效数据维持时间分别缩短了32.9%和33.2%。