数据并行语言中的扩展结构

本文通过对并行程序设计的三个步骤及数据并行问题特点的分析，论述了数据并行语言应支持程序员对数据划分和映射的描述，并讨论了为此应对串行语言扩展的几个结构。通过四个成功的数据并行语言，说明了这几个扩展结构存在的必要性和合理性。     

C＊数据并行语言

Ｃ＊语言是通过对ＡＮＳＩＣ语言进行语法和语义的扩展得到的支持ＳＩＭＤ模式的数据并行语言。它允许用户基于一个ＳＩＭＤ虚拟机描述数据在各个虚处理机上的分布以及对这些数据的并行计算操作，提供了一种简单，有效并与任何特定的机器无关的数据并行编程模型。     

实时时序逻辑语言XYZ/RE到时间自动机的映射

时间自动机是一种重要的实时系统建模工具。本文建立了实时时序逻辑语言XYZ/RE到时间自动机的一种映射机制,将XYZ/RE所描述的系统进程直接转换为时间自动机,这样不但可以准确捕获实时系统功能和控制行为,还可以利用基于时间自动机的验证工具UPPAAL对XYZ/RE描述的系统正确性进行检测。最后本文通过一个实例的描述与检测,验证了映射机制的有效性。     

UML状态机模型元素的RSL形式化定义

UML状态机作为UML动态描述机制的重要组成部分,在描述系统及模型的动态行为时扮演着重要的角色,但已有的UML动态语义缺乏准确的形式化描述。首先将UML状态机抽象成图;再将图通过传统的有穷自动机进行语义扩展,同时增加状态分层,形成一个基于UML状态机的有穷自动机;然后用RAISE规约语言RSL对扩展后的自动机进行形式化定义,使UML状态机中的模型元素的语义更加清晰、精确,为后期的UML状态机的操作语义形式化研究打下基础。     

基于并行状态自动机的工作流建模

为了实现工作流管理功能，首先要把业务过程从现实世界抽象出来，并用一种形式化方法对其进行描述，其结果就是工作流模型。该文讨论利用并行自动机对工作流的形式化问题。基于对工作流和并行自动机的分析，提出了将工作流的概念映射到并行自动机概念上的方法，该方法可以把工作流联盟提出的工作流的4种结构映射到并行自动机的结构上。给出了并行自动机的结点转化图，即给出了工作流引擎的框架。并行自动机是一种图形的、数学化的计算模型，当工作流的模型——并行自动机建立起来后，为工作流的静态特性和动态特性的分析打下不坚实的基础，为进一步的研究作好了准备。     

基于并行状态自动机的工作流建模

为了实现工作流管理功能，首先要把业务过程从观实世界抽象出来，并用一种形式化疗法对其进行描述，其结果就是工作流模型。该文讨论利用并行自动机对工作流的形式化问题。基于对工作流和并行自动机的分析，提出了将工作流的概念映射到并行自动机概念上的方法，该方法可以把工作流联盟提出的工作流的4种结构映射到并行自动机的结构上。给出了并行自动机的结点转化图，即给出了工作流引擎的框架。并行自动机是一种图形的、数学化的计算模型，当工作流的模型一并行自动机建立起来后，为工作流的静态特性和动态特性的分析打下不坚实的基础，为进一步的研究作好了准备。     

并行语言MODULA-S的设计

本文叙述基于顺序语言MODULA-2的并行扩展语言MODULA-S,对它的设计目标及其扩展的并行结构成份进行了讨论。该语言已在面向数据结构的小巨型机STARLET-Ⅱ上实现。     

PSL构造双向交换自动机及非确定自动机的方法

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值.     

C^＊数据并行语言及其应用

Ｃ＊语言是通过对ＡＮＳＩＣ语言进行进行语法和语义的扩展得的支持ＳＩＭＤ模式的数据并行语言。它允许用户基于一个ＳＩＭＤ虚机描述数据在各个虚处理机上的分布以及对这些数据的并行计算操作，提供了一处简单，有效并与任何特定的机器无关的数据并行编程模型。介绍了Ｃ＊语言在超级计算机领域中的应用和Ｃ＊并行扩成分，并给出了典型的编程实例。     

LS SIMD C编译器的数据通信优化算法

1 引言当前理想的程序自动并行化系统的实现存在许多难于解决的问题,因此较为流行的并行计算方法是利用并行语言编写并行程序,编译器对并行程序进行编译生成相应的节点程序执行。并行语言按并行执行的粒度分为基于任务的并行语言(主要面向一般应用领域的计算)和数据并行语言(主要应用于科学数值计算),典型的数据并行语言如HPF。对于数据并行语言而言,程序执行的并行性已由程序设计人员根据程序中的数据相关性给出。因此,如何确定数据的分布、优化数据的通信是影响并行程序执行效率的重要问题。数据分布大致可以分为两个阶段:首先对源程序中数据的相关性分析得到数据在抽象处理机上的分布,然后将抽象处理机上的数据分布映射到物理处理机上。数据分布的确定通常有以下几种实现方式:一种是由程序员给出抽象数据分布,编译     

A portfolio of classification problems by one-dimensional cellular automata,over cyclic binary configurations and parallel update

Decision problems addressed by cellular automata have been historically expressed either as determining whether initial configurations would belong to a given language, or as classifying the initial configurations according to a property in them. Unlike traditional approaches in language recognition, classification problems have typically relied upon cyclic configurations and fully paralell (two-way) update of the cells, which render the action of the cellular automaton relatively less controllable and difficult to analyse. Although the notion of cyclic languages have been studied in the wider realm of formal languages, only recently a more systematic attempt has come into play in respect to cellular automata with fully parallel update. With the goal of contributing to this effort, we propose a unified definition of classification problem for one-dimensional, binary cellular automata, from which various known problems are couched in and novel ones are defined, and analyse the solvability of the new problems. Such a unified perspective aims at increasing existing knowledge about classification problems by cellular automata over cyclic configurations and parallel update.     

Representing and computing regular languages on massively parallelnetworks

A general method is proposed for incorporating rule-based constraints corresponding to regular languages into stochastic inference problems, thereby allowing for a unified representation of stochastic and syntactic pattern constraints. The authors' approach establishes the formal connection of rules to Chomsky grammars and generalizes the original work of Shannon on the encoding of rule-based channel sequences to Markov chains of maximum entropy. This maximum entropy probabilistic view leads to Gibbs representations with potentials which have their number of minima growing at precisely the exponential rate that the language of deterministically constrained sequences grow. These representations are coupled to stochastic diffusion algorithms, which sample the language-constrained sequences by visiting the energy minima according to the underlying Gibbs probability law. This coupling yields the result that fully parallel stochastic cellular automata can be derived to generate samples from the rule-based constraint sets. The production rules and neighborhood state structure of the language of sequences directly determine the necessary connection structures of the required parallel computing surface. Representations of this type have been mapped to the DAP-510 massively parallel processor consisting of 1024 mesh-connected bit-serial processing elements for performing automated segmentation of electron-micrograph images.     

On the Computational Complexity of P Automata

We characterize the classes of languages over finite alphabets which may be described by P automata, i.e., accepting P systems with communication rules only. Motivated by properties of natural computing systems, and the actual behavior of P automata, we study computational complexity classes with a certain restriction on the use of the available workspace in the course of computations and relate these to the language classes described by P automata. We prove that if the rules of the P system are applied sequentially, then the accepted language class is strictly included in the class of languages accepted by one-way Turing machines with a logarithmically bounded workspace, and if the rules are applied in the maximally parallel manner, then the class of context-sensitive languages is obtained.     

基于元胞自动机的小样本集分类算法

样本集中的数据数量过少会影响最后的分类精度。为此,提出基于元胞自动机模型的小样本集分类算法,利用元胞自动机的状态转换规则和分类规则,通过元胞空间的演化实现对数据集的分类。对标准数据集的测试结果表明,在小样本集和样本集中数据分布不均匀的情况下,该算法具有较高的分类精度。     

Parallel genetic algorithms for optimising cellular automata models of natural complex phenomena: An application to debris flows

Cellular automata models of natural complex phenomena may depend on a set of parameters which can significantly influence the global dynamics of the simulated events. In order to reliably apply such models for predictive purposes, their parameters have to be estimated with the greatest possible accuracy. However, no standardised optimisation techniques exist in this specific research field. Genetic Algorithms (GAs) offer a possible solution: they are parallel algorithms, and can be easily implemented to exploit the simultaneous use of multiple CPUs, thereby greatly reducing the execution time.An application of a parallel GA to the optimisation of a cellular automata model for the simulation of debris flows characterised by strong inertial effects is presented. The May 1998, Curti-Sarno (Italy) debris flow has been selected as a case study for the optimisation of the model. Theoretical considerations on the dynamics of the adopted GA are discussed, with reference to two different fitness functions applied to an idealised case study.Results demonstrated the usefulness of the approach, in terms of both computing time and quality of performed simulations. Moreover, experiments on the idealised case study pointed out that the simplest fitness function (only based on the comparison of affected areas) could conveniently be adopted for calibration purposes.     

Timed automata with urgent transitions

We propose an extension to the formalism of timed automata by allowing urgent transitions. An urgent transition is a transition which must be taken within a fixed time interval from its enabling time and it has higher priority than other non-urgent transitions enabled in the same state. We give a set of rules formally describing the behavior of urgent transitions and we show that, from a language theoretic point of view, the addition of urgency does not improve the expressive power of timed automata. From a specification point of view, the use of urgent transitions allows shorter and clear specifications of behaviors involving urgency and priority. We use timed automata with urgent transitions for specifying a multicast protocol for mobile computing.Received: 10 January 2003, Published online: 17 February 2004A first version of this paper appeared in [15]     

支持多种并行计算模型的面向对象框架研究

为了支持并行程序设计,几乎所有的程序设计语言均通过提供并行与同步通信机制来支持某一高级并行计算模型,如Ada语言的任务与会合机制以及Java语言的线程和同步方法.显然,这样的程序设计语言仅能支持一种高级并行计算模型.尽管单模型的途径对某些应用来说简单而有效,但由于现实世界中的问题往往较为繁杂而难以完全用单一模型来解决.文章采用面向对象的语言机制和框架技术来解决此问题.通过分析现有各种语言中高级并行计算模型的共性,提出了若干新的面向对象语言机制.以此为基础,提出了并行面向对象框架的概念,并讨论用其表达和使用     

Experience of multilevel parallelizing of the branch and bound method in discrete optimization problems

Various schemes are considered of the parallel implementation of the branch and bound method, as applied to multiprocessor computing systems (clusters) with the distributed memory. In the language of informal automata, questions are set out of the organization of the exchange of data and signals within the cluster, which afford the asynchronous operation of its processors. Common ideas are illustrated by the example of the classical traveling salesman problem and data of numerical experiments performed on the multiprocessor computing system-100 (MCS-100) are given.     

Emergence and control of macro-spatial structures in perturbed cellular automata, and implications for pervasive computing systems

Predicting the behavior of complex decentralized pervasive computing systems before their deployment in a dynamic environment, as well as being able to influence and control their behavior in a decentralized way, will be of fundamental importance in the near future. In this context, this paper describes the general behavior observed in a large set of asynchronous cellular automata when external perturbations influence the internal activities of cellular automata cells. In particular, we observed that stable macrolevel spatial structures emerge from local interactions among cells, a behavior that does not emerge when cellular automata are not perturbed. Similar sorts of macrolevel behaviors are likely to emerge in the context of pervasive computing systems and need to be studied, controlled, and possibly fruitfully exploited. On this basis, the paper also reports the results of a set of experiments, showing how it is possible to control, in a decentralized way, the behavior of perturbed cellular automata, to make any desired patterns emerge.