Formal modelling and verification of GALS systems using GRL and CADP

A GALS (Globally Asynchronous, Locally Synchronous) system consists of several synchronous components that evolve concurrently and interact with each other asynchronously. The design of GALS systems is tedious and error-prone due to the high degree of synchronous and asynchronous concurrency present in complex architectures. In this paper, we present GRL (GALS Representation Language), a formal language designed to model GALS systems, for the purpose of formal verification of the asynchronous aspects. GRL combines the synchronous reactive model underlying dataflow languages and the asynchronous concurrent model underlying process algebras. We propose a translation from GRL to LNT, a value-passing concurrent language with classical process algebra flavour. This makes possible the analysis of GRL specifications using all the state-of-the-art simulation and verification functionalities provided by the CADP toolbox.     

Performance modelling of a network processor using POOSL

The increasing complexity of innovative real-time hardware/software systems forced industry to consider system-level design methods. Before actually implementing a system with hardware and software components, system-level design methods enable analysing the performance of different design alternatives that realise the required functionality. In order to develop performance models early in the design process, the parallel object-oriented specification language (POOSL) can be used. POOSL is an expressive modelling language for analysing complex real-time distributed hardware/software systems. Being equipped with a formal semantics, POOSL ensures unambiguous execution of models and proper application of performance analysis techniques. This paper discusses the use of POOSL for analysing the performance of a network processor. A network processor consists of components that perform their behaviour in a synchronously concurrent way, whereas POOSL is based on an asynchronous modelling paradigm. In this paper, we illustrate that constructing abstract models of synchronous systems for the purpose of performance analysis may benefit from an asynchronous modelling approach.     

Group communication in partitionable systems: specification andalgorithms

Gives a formal specification and an implementation for a partitionable group communication service in asynchronous distributed systems. Our specification is motivated by the requirements for building “partition-aware” applications that can continue operating without blocking in multiple concurrent partitions and can reconfigure themselves dynamically when partitions merge. The specified service guarantees liveness and excludes trivial solutions, it constitutes a useful basis for building realistic partition-aware applications, and it is implementable in practical asynchronous distributed systems where certain stability conditions hold     

基于16C954的异步串行模块驱动设计

介绍了基于16C954的异步串行模块的硬件组成与驱动软件开发,描述了驱动开发过程中的环境搭建、接口设计、框架生成、代码实现以及软件调试,重点对端口打开、波特率设置和数据收发功能代码实现进行了详细说明。经验证,该异步串行模块驱动满足可靠串行通信需求,可实现四串口多线程同步满负荷运行。目前,该模块已成功应用于工业控制等多个领域。     

单片机串行通讯技术在数据采集系统中的应用

能够完成异步通信的硬件电路称为UART,即通用异步接收器/发送器(Universal Asynchronous Receiver/Transmitter),本文介绍了应用8051单片机一主机多从机组成的串行异步通讯接口技术进行数据采集,采用RS-485标准接口通信,其抗干扰能力强,可与32台从机通讯,传输距离可达1200m,最大传送速率1Mb/S.     

Asynchronous communication model based on linear logic

We propose a new framework called ACL for concurrent computation based on linear logic. ACL is a kind oflinear logic programming framework, where its operational semantics is described in terms ofproof construction in linear logic. We also give a model-theoretic semantics based onphase semantics, a model of linear logic. Our framework well captures concurrent computation based on asynchronous communication. It will, therefore, provide us with a new insight into other models of asynchronous concurrent computation from alogical point of view. We also expect ACL to become a formal framework for analysis, synthesis and transformation of concurrent programs by the use of techniques for traditional logic programming. ACL's attractive features for concurrent programming paradigms are also discussed.     

On the Need for Mixed Media in Distributed Requirements Negotiations

Achieving agreement with respect to software requirements is a collaborative process that traditionally relies on same-time, same-place interactions. As the trend toward geographically distributed software development continues, colocated meetings are becoming increasingly problematic. Our research investigates the impact of computer-mediated communication on the performance of distributed client/developer teams involved in the collaborative development of a requirements specification. Drawing on media-selection theories, we posit that a combination of lean and rich media is needed for an effective process of requirements negotiations when stakeholders are geographically dispersed. In this paper, we present an empirical study that investigates the performance of six educational global project teams involved in a negotiation process using both asynchronous text-based and synchronous videoconferencing-based communication modes. The findings indicate that requirement negotiations were more effective when the groups conducted asynchronous structured discussions of requirement issues prior to the synchronous negotiation meeting. Asynchronous discussions were useful in resolving issues related to uncertainty in requirements, thus allowing synchronous negotiations to focus more on removing ambiguities in the requirements.     

SystemJ: A GALS language for system level design

In this paper we present the syntax, semantics, and compilation of a new system-level programming language called SystemJ. SystemJ is a multiclock language supporting the Globally Asynchronous Locally Synchronous (GALS) model of computation. The synchronous reactive (SR) model is used for synchronous parts of the modelled system, and those parts, which represent individual clock-domains, are coupled asynchronously each to the other on the top-level of system design. SystemJ is based on Java language, which is used to describe “instantaneous” data transformations. Hence, SystemJ is well suited for both software-based embedded and distributed systems. SystemJ offers effective modelling of (1) data transformations through the power of Java, (2) control and synchronous concurrency through the SR paradigm and (3) asynchronous concurrency through clock domains and rendezvous. The language is based on semantics that is amenable to efficient code generation and partial automatic verification. The SystemJ micro-step semantics provide asynchronous and synchronous extensions over the semantics of other SR languages such as Esterel and provide an ideal platform for efficient software implementation.     

Reactive Modules

We present a formal model for concurrent systems. The model represents synchronous and asynchronous components in a uniform framework that supports compositional (assume-guarantee) and hierarchical (stepwise-refinement) design and verification. While synchronous models are based on a notion of atomic computation step, and asynchronous models remove that notion by introducing stuttering, our model is based on a flexible notion of what constitutes a computation step: by applying an abstraction operator to a system, arbitrarily many consecutive steps can be collapsed into a single step. The abstraction operator, which may turn an asynchronous system into a synchronous one, allows us to describe systems at various levels of temporal detail. For describing systems at various levels of spatial detail, we use a hiding operator that may turn a synchronous system into an asynchronous one. We illustrate the model with diverse examples from synchronous circuits, asynchronous shared-memory programs, and synchronous message-passing protocols.     

A component- and message-based architectural style for GUI software

While a large fraction of application code is devoted to graphical user interface (GUI) functions, support for reuse in this domain has largely been confined to the creation of GUI toolkits (“widgets”). We present a novel architectural style directed at supporting larger grain reuse and flexible system composition. Moreover, the style supports design of distributed, concurrent applications. Asynchronous notification messages and asynchronous request messages are the sole basis for intercomponent communication. A key aspect of the style is that components are not built with any dependencies on what typically would be considered lower-level components, such as user interface toolkits. Indeed, all components are oblivious to the existence of any components to which notification messages are sent. While our focus has been on applications involving graphical user interfaces, the style has the potential for broader applicability. Several trial applications using the style are described     

Quasi-synchronous checkpointing: Models, characterization, andclassification

Checkpointing algorithms are classified as synchronous and asynchronous in the literature. In synchronous checkpointing, processes synchronize their checkpointing activities so that a globally consistent set of checkpoints is always maintained in the system. Synchronizing checkpointing activity involves message overhead and process execution may have to be suspended during the checkpointing coordination, resulting in performance degradation. In asynchronous checkpointing, processes take checkpoints without any coordination with others. Asynchronous checkpointing provides maximum autonomy for processes to take checkpoints; however, some of the checkpoints taken may not lie on any consistent global checkpoint, thus making the checkpointing efforts useless. Asynchronous checkpointing algorithms in the literature can reduce the number of useless checkpoints by making processes take communication induced checkpoints besides asynchronous checkpoints. We call such algorithms quasi-synchronous. In this paper, we present a theoretical framework for characterizing and classifying such algorithms. The theory not only helps to classify and characterize the quasi-synchronous checkpointing algorithms, but also helps to analyze the properties and limitations of the algorithms belonging to each class. It also provides guidelines for designing and evaluating such algorithms     

异步片上网络研究综述

异步片上网络具有低动态功耗、对延迟抖动的不敏感、统一的网络接口、较低的系统集成复杂度和较好的电磁兼容能力等众多特性,是下一代片上多核微处理器和多核片上系统的标准片上通信架构之一.在简单介绍异步电路的相关理论后,从多个方面概述了当前异步片上网络的研究成果,包括网络拓扑、同步?异步接口、流控制、服务质量、路由算法、低功耗设计、容错和可测性设计以及设计自动化;然后介绍并分析了一些具有代表性的异步片上网络设计案例.研究显示,异步片上网络具有众多同步片上网络所不具备的优点,大量的片上多核系统将使用异步片上网络作为其片上通信系统,但它们的易用性和网络性能亟待提高.     

An overview of the K semantic framework

K is an executable semantic framework in which programming languages, calculi, as well as type systems or formal analysis tools can be defined, making use of configurations, computations and rules. Configurations organize the system/program state in units called cells, which are labeled and can be nested. Computations carry “computational meaning” as special nested list structures sequentializing computational tasks, such as fragments of program; in particular, computations extend the original language or calculus syntax. K (rewrite) rules generalize conventional rewrite rules by making explicit which parts of the term they read, write, or do not care about. This distinction makes K a suitable framework for defining truly concurrent languages or calculi, even in the presence of sharing. Since computations can be handled like any other terms in a rewriting environment, that is, they can be matched, moved from one place to another in the original term, modified, or even deleted, K is particularly suitable for defining control-intensive language features such as abrupt termination, exceptions, or call/cc.This paper gives an overview of the K framework: what it is, how it can be used, and where it has been used so far. It also proposes and discusses the K definition of Challenge, a programming language that aims to challenge and expose the limitations of existing semantic frameworks.     

“腾越-Ⅱ”嵌入式异步微处理器的设计与实现

嵌入式系统对处理器功耗开销有严格的限制,异步电路技术可以作为设计低功耗处理器的有效方法之一。针对嵌入式多媒体应用,本文设计实现了一款低功耗异步微处理器——腾越-Ⅱ。处理器中包含一个异步TTA微处理器内核、一个同步TTA微处理器内核、两个存储控制器和多个外部通信接口。异步内核通过基于宏单元的异步电路设计方法实现,其它部分通过基于标准单元的半定制设计流程实现。处理器芯片采用UMC0.18μmCMOS工艺实现,基片面积为4.89×4.89mm2,工作电压为1.8V。经测试,处理器工作主频达到200MHz,且异步内核的功耗开销低于同步内核的50%。     

PMaude: Rewrite-based Specification Language for Probabilistic Object Systems

We introduce a rewrite-based specification language for modelling probabilistic concurrent and distributed systems. The language, based on PMaude, has both a rigorous formal basis and the characteristics of a high-level rule-based programming language. Furthermore, we provide tool support for performing discrete-event simulations of models written in PMaude, and for statistically analyzing various quantitative aspects of such models based on the samples that are generated through discrete-event simulation. Because distributed and concurrent communication protocols can be modelled using actors (concurrent objects with asynchronous message passing), we provide an actor PMaude module. The module aids writing specifications in a probabilistic actor formalism. This allows us to easily write specifications that are purely probabilistic – and not just non-deterministic. The absence of such (un-quantified) non-determinism in a probabilistic system is necessary for a form of statistical analysis that we also discuss. Specifically, we introduce a query language called Quantitative Temporal Expressions (or QuaTEx in short), to query various quantitative aspects of a probabilistic model. We also describe a statistical technique to evaluate QuaTEx expressions for a probabilistic model.     

An Asynchronous Protocol for Release Consistent Distributed Shared Memory Systems

Distributed shared memory (DSM) systems provide a simple programming paradigm for networks of workstations, which are gaining popularity due to their cost-effective high computing power. However, DSM systems usually exhibit poor performance due to the large communication delay between the nodes; and a lot of different memory consistency models have been proposed to mask the network delay. In this paper, we propose an asynchronous protocol for the release consistent memory model, which we call an Asynchronous Release Consistency (ARC) protocol. Unlike other protocols where the communication adheres to the synchronous request/receive paradigm, the ARC protocol is asynchronous, such that the necessary pages are broadcast before they are requested. Hence, the network delay can be reduced by proper prefetching of necessary pages. We have also compared the performance of the ARC protocol with the lazy release protocol by running standard benchmark programs; and the experimental results showed that the ARC protocol achieves a performance improvement of up to 29%.     

Evaluation of Error Recovery Blocks Used for Cooperating Processes

Three alternatives for implementing recovery blocks (RB's) are conceivable for backward error recovery in concurrent processing. These are the asynchronous, synchronous, and the pseudorecovery point implementations. Asynchronous RB's are based on the concept of maximum autonomy in each of concurrent processes. Consequently, establishment of RB's in a process is made independently of others and unbounded rollback propagations become a serious problem. In order to completely avoid unbounded rollback propagations, it is necessary to synchronize the establishment of recovery blocks in all cooperating processes. Process autonomy is sacrificed and processes are forced to wait for commitments from others to establish a recovery line, leading to inefficiency in time utilization. As a compromise between asynchronous and synchronous RB's we propose to insert pseudorecovery points (PRP's) so that unbounded rollback propagations may be avoided while maintaining process autonomy. We developed probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, i.e., exponential distributions for related random variables. With these models we have estimated 1) the interval between two successive recovery lines for asynchronous RB's, 2) mean loss in computation power for the synchronized method, and 3) additional overhead and rollback distance in case PRP's are used.     

基于去同步技术的异步8051设计与实现

随着半导体工艺的发展,同步电路面临的时钟偏差、功耗等问题日益突出,异步设计方法得到广泛研究和关注。去同步技术可以方便地实现从同步向异步的转化,成为很有前途的异步电路设计方法。基于去同步技术设计实现了一款异步8051微控制器,着重介绍了基于去同步技术的设计流程与异步控制器设计方法。分析表明,在相同的电压、温度条件下,该异步8051性能与同步8051相当,而功耗约为1/2。