On Decidability of Distributed Diagnosis Under Unbounded-Delay Communication

In this note we show that the problem of distributed diagnosis under unbounded communication delay is decidable when there is no inferencing involved among the diagnosers. The notion of joint_infin-diagnosability is introduced to capture the diagnosability property in this setting. We show the equivalence of joint_infin-diagnosability and codiagnosability, which captures the diagnosability property in the decentralized setting (i.e., one involving no communication). Thus the decidability result follows from the decidability of codiagnosability established in a previous paper. We also show that the property of joint_infin-diagnosability is stronger than decentralized-diagnosability introduced in a previous paper     

Decentralized failure diagnosis of discrete event systems

By decentralized diagnosis we mean diagnosis using multiple diagnosers, each possessing its own set of sensors, without involving any communication among diagnosers or to any coordinators. The notion of decentralized diagnosis is formalized by introducing the notion of codiagnosability that requires that a failure be detected by one of the diagnosers within a bounded delay. Algorithms of complexity polynomial in the size of the system and the nonfault specification are provided for: 1) testing codiagnosability, 2) computing the bound in delay of diagnosis, 3) offline synthesis of individual diagnosers, and 4) online diagnosis using them. The notion of codiagnosability and the above algorithms are initially presented in a setting of a specification language (violation of which represents a fault) and are later specialized to the case where faults are modeled as the occurrences of certain events. The notion of strong codiagnosability is also introduced to capture the ability of being certain about both the failure as well as the nonfailure conditions in a system within a bounded delay.     

Optimal sensor activation for diagnosing discrete event systems

The problem of dynamic sensor activation for event diagnosis in partially observed discrete event systems is considered. Diagnostic agents are able to activate sensors dynamically during the evolution of the system. Sensor activation policies for diagnostic agents are functions that determine which sensors are to be activated after the occurrence of a trace of events. The sensor activation policy must satisfy the property of diagnosability of centralized systems or codiagnosability of decentralized systems. A policy is said to be minimal if there is no other policy, with strictly less sensor activation, that achieves diagnosability or codiagnosability. To compute minimal policies, we propose language partition methods that lead to efficient computational algorithms. Specifically, we define “window-based” language partitions for scalable algorithms to compute minimal policies. By refining partitions, one is able to refine the solution space over which minimal solutions are computed at the expense of more computation. Thus a compromise can be achieved between fineness of solution and complexity of computation.     

Decentralized Diagnosis of Stochastic Discrete Event Systems

We investigate the decentralized diagnosis of stochastic discrete event systems (SDESs) by using multiple local stochastic diagnosers, each possessing its own sensors to deal with different information. We formalize the notions of decentralized diagnosis for SDESs by defining the concept of codiagnosability for stochastic automata, in which any communication among the local stochastic diagnosers or to any coordinators is not involved. These notions are weaker than the corresponding notions of decentralized diagnosis of classical DESs. A stochastic system being codiagnosable means that a fault can be detected by at least one local stochastic diagnoser within a finite delay. We construct a codiagnoser from a given stochastic system with a finite number of projections whose each diagnosis component uses the complete model of the system. We also deal with a number of basic properties of the codiagnoser. In particular, a necessary and sufficient condition of the codiagnosability for SDESs is presented, which generalizes the corresponding results of centralized diagnosis for SDESs. Also, we give a computing method in detail to check the codiagnosability of SDESs. As an application of our results, some examples are described.     

Scalable communication architectures for massively parallel hardware multi-processors

Modern complex embedded applications in multiple application fields impose stringent and continuously increasing functional and parametric demands. To adequately serve these applications, massively parallel multi-processor systems on a single chip (MPSoCs) are required. This paper is devoted to the design of scalable communication architectures of massively parallel hardware multi-processors for highly-demanding applications. We demonstrated that in the massively parallel hardware multi-processors the communication network influence on both the throughput and circuit area dominates the processors influence, while the traditionally used flat communication architectures do not scale well with the increase of parallelism. Therefore, we propose to design highly optimized application-specific partitioned hierarchical organizations of the communication architectures through exploiting the regularity and hierarchy of the actual information flows of a given application. We developed related communication architecture synthesis strategies and incorporated them into our quality-driven model-based multi-processor design methodology and related automated architecture exploration framework. Using this framework we performed a large series of architecture synthesis experiments. Some of the results of the experiments are presented in this paper. They demonstrate many features of the synthesized communication architectures and show that our method and related framework are able to efficiently synthesize well scalable communication architectures even for the high-end massively parallel multi-processors that have to satisfy extremely stringent computation demands.     

Decidability of well-connectedness for distributed synthesis

Although the synthesis problem is often undecidable for distributed, synchronous systems, it becomes decidable for the subclass of uniformly well-connected (UWC) architectures, provided that only robust specifications are considered. It is then an important issue to be able to decide whether a given architecture falls in this class. This is the problem addressed in this paper: we establish the decidability and precise complexity of checking this property. This problem is in EXPSPACE and NP-hard in the general case, but falls into PSPACE when restricted to a natural subclass of architectures.     

Program verification with interacting analysis plugins

In this paper we propose and argue for a modular framework for interprocedural program analysis, where multiple program analysis tools are combined in order to exploit the particular advantages of each. This allows for “plugging together” such tools as required by each verification task and makes it easy to integrate new analyses. Our framework automates the sharing of information between plugins using a first order logic with transitive closure, in a way inspired by the open product of Cortesi et al. We describe a prototype implementation of our framework, which performs static assertion checking on a simple language for heap-manipulating programs. This implementation includes plugins for three existing approaches—predicate abstraction, 3-valued shape analysis and a decidable pointer analysis—and for a simple type system. We demonstrate through a detailed example the increase in precision that our approach can provide. Finally we discuss the design decisions we have taken, in particular the tradeoffs involved in the choice of language by which the plugins communicate, and identify some future directions for our work. R. Lazic, R. Nagarajan and J. C. P. Woodcock     

Distributed Diagnosis Under Bounded-Delay Communication of Immediately Forwarded Local Observations

We study distributed failure diagnosis under a -bounded communication delay, where each local site transmits its observations to other sites immediately after each observation and the transmitted observation is received within at most more event executions of the plant. A notion of diagnosability is introduced so that any failure can be diagnosed within a bounded delay of its occurrence by one of the local sites using its own observations and the -bounded delayed observations received from other local sites. The local sites communicate among each other using an ldquoimmediate observation passing (iop)rdquo protocol, forwarding any observation immediately up on its occurrence. We construct models for the -bounded communication delay and use them to extend the system and nonfault specification models for capturing the effect of bounded-delay communication. By using the extended system and specification models, the distributed diagnosis problem under the immediate observation passing protocol is then converted to a decentralized diagnosis problem of our previous work, where the results are applied for verifying diagnosability and for synthesizing local diagnosers. Methods by which complexity of testing diagnosability and of online diagnosis can be reduced are presented. Finally, we compare the notions of diagnosability, codiagnosability, and diagnosability.     

Decentralized Diagnosis of Event-Driven Systems for Safely Reacting to Failures

We introduce the notion of safe-codiagnosability, extending the notion of safe-diagnosability (Paoli and Lafortune, 2005) to the decentralized setting. For a system, a certain subbehavior is deemed safe (captured via a safety specification), and a further subbehavior is deemed nonfaulty (captured via a nonfault specification). Safe-codiagnosability requires that when the system executes a trace that is faulty, there exists at least one diagnoser that can detect this within bounded delay and also before the safety specification is violated. The above notion of safe-codiagnosability may also be viewed as an extension of the notion of codiagnosability (Qiu and Kumar, 2006), where the latter did not have any safety requirement. We show that safe-codiagnosability is equivalent to codiagnosability together with ldquozero-delay codiagnosabilityrdquo of ldquoboundary safe tracesrdquo. (A safe trace is a boundary safe trace if there exists a single-event extension that is unsafe.) We give an algorithm of polynomial complexity for verifying safe-codiagnosability. For a safe-codiagnosable system, the same methods as those proposed in (Qiu and Kumar, 2006) can be applied for offline synthesis of individual diagnosers, as well as for online diagnosis using them.     

Requirements for a Practical Network Event Recognition Language

We propose a run-time monitoring and checking architecture for network protocols called Network Event Recognition. Our framework is based on passively monitoring the packet trace produced by a protocol implementation and checking it for properties written in a formal specification language, NERL. In this paper, we describe the design requirements for NERL. We show how the unique requirements of network protocol monitoring impact design and implementation options. Finally we outline our prototype implementation of NERL and discuss two case studies: checking the correctness of network protocol simulations and privacy issues in packet-mode surveillance.     

A Decomposition of the Tikhonov Regularization Functional Oriented to Exploit Hybrid Multilevel Parallelism

We introduce a decomposition of the Tikhonov Regularization (TR) functional which split this operator into several TR functionals, suitably modified in order to enforce the matching of their solutions. As a consequence, instead of solving one problem we can solve several problems reproducing the initial one at smaller dimensions. Such approach leads to a reduction of the time complexity of the resulting algorithm. Since the subproblems are solved in parallel, this decomposition also leads to a reduction of the overall execution time. Main outcome of the decomposition is that the parallel algorithm is oriented to exploit the highest performance of parallel architectures where concurrency is implemented both at the coarsest and finest levels of granularity. Performance analysis is discussed in terms of the algorithm and software scalability. Validation is performed on a reference parallel architecture made of a distributed memory multiprocessor and a Graphic Processing Unit. Results are presented on the Data Assimilation problem, for oceanographic models.     

Parallel computers for advanced information processing

An overview is given of ESPRIT project 415, which involved the study of object-oriented, functional, and logic programming styles in six subprojects. The parallel languages and architectures designed to implement them are described, and the technology of the object-oriented approach pursued by the authors' team is examined. Their design includes a novel language, decentralized memory architecture, and system software     

Automatic code generation for GPUs in llc

llc is a C-based language where parallelism is expressed using compiler directives. In this paper, we present a new backend of an llc compiler that produces code for GPUs. We have also implemented a software architecture that eases the development of new backends. Our design represents an intermediate layer between a high-level parallel language and different hardware architectures.     

Linear-code multicast on parallel architectures

Parallel architectures involve communication with the aim of fast receiving of complete information at each node. Several architectures have been proposed to overcome the problem of high communicational and computational time complexity for transferring and receiving information. To reduce the complexity of such communication, we have implemented Linear Network Coding (LNC) in the parallel environment. For verification of our approach, we have considered some parallel architecture for implementing network coding approach and examined our results on these networks in a generic environment. We have formulated a standard approach for parallel networks, showing that by applying this approach effect of faulty nodes, information size and communication complexity exponentially decreases with code length.     

Robust diagnosis of discrete event systems against intermittent loss of observations

In the usual approaches to fault diagnosis of discrete event systems it is assumed that not only all sensors work properly but also all information reported by sensors always reaches the diagnoser. Any bad sensor operation or communication failure between sensors and the diagnoser can be regarded as loss of observations of events initially assumed as observable. In such situations, it may be possible that either the diagnoser stands still or report some wrong information regarding the fault occurrence. In this paper we assume that intermittent loss of observations may occur and we propose an automaton model based on a new language operation (language dilation) that takes it into account. We refer to this problem as robust diagnosability against intermittent loss of observations (or simply robust diagnosability, where the context allows). We present a necessary and sufficient condition for robust diagnosability in terms of the language generated by the original automaton and propose two tests for robust language diagnosability, one that deploys diagnosers and another one that uses verifiers. We also extend the results to robust codiagnosability against intermittent loss of observations.     

数据并行计算机体系结构研究

通过对国内外并行计算机体系结构的分析与研究,提出一种面向多媒体应用的嵌入式数据并行计算机体系结构模型,将可重构总线与PIM技术相结合,弥补传统PIM体系结构下处理元之间通信复杂度高、结构可适应性弱等不足.描述其主要部件的功能和结构,定义该体系结构计算机的指令集,通过一个典型的算法样例介绍其汇编语言程序组成和并行计算过程...     

An Empirical Methodology for Exploring Reconfigurable Architectures

Recent research in reduced instruction set computer architectures has emphasized the importance of the empirical approach to designing computer architectures: architectural features are analyzed for utility and cost with respect to the system software that uses them. This approach has resulted in architectural simulators that allow computer designers to vary the features of the architecture being simulated and to analyze how the addition or removal of these features affects the cost and performance of the architecture. In this paper we apply this technique to a new area: reconfigurable architectures. Our approach is to use an empirical methodology that emphasizes the interaction between the target software and the reconfigurability features of parallel architectures. We have developed a set of tools, the reconfigurable architecture workbench, that assists in this methodology by allowing parallel programs to be simulated on a target architecture in order to study the performance implications of various reconfigurability features. The workbench is based on a framework, the PCI model, which describes the range of parallel programs, parallel architectures, and reconfiguration features. We present details of the design and implementation of a prototype workbench, GT-RAW. GT-RAW is being used to study the utility of one dimension of reconfiguration for image processing and image understanding applications. We present an example of the experiments that are being conducted with GT-RAW as a demonstration of our empirical methodology.     

Codiagnosability of networked discrete event systems subject to communication delays and intermittent loss of observation

Failure diagnosis is a crucial task in modern industrial systems, and several works in the literature address this problem by modeling the system as a Discrete-Event System (DES). Most of them assume perfect communication between sensors and diagnosers, i.e., no loss of observation of events, or event communication delays between the measurement sites and the diagnosers. However, industrial systems can be large and physically distributed, in which cases, communication networks are used to provide an efficient way to establish communication between devices. In diagnosis systems, the use of networks can introduce delays in the communication of event occurrences from measurement sites to the local diagnosers, leading to an incorrect observation of the order of occurrence of events generated by the system and, as a consequence, to an incorrect diagnosis decision by the local diagnoser. In this paper, we address the problem of decentralized diagnosis of networked Discrete-Event Systems subject to event communication delays, and we introduce the definition of network codiagnosability of the language generated by a DES subject to both event communication delays and intermittent loss of observation, and present necessary and sufficient conditions for a language to be network codiagnosable, for short. We also propose an algorithm to verify this property.