Consistent Global States (CGS) detection is a costly process. If CGS are constructed using real-time timestamps, then their hierarchical detection is possible. In a hierarchical detection scheme the load of a single c...
详细信息
ISBN:
(纸本)0769520804
Consistent Global States (CGS) detection is a costly process. If CGS are constructed using real-time timestamps, then their hierarchical detection is possible. In a hierarchical detection scheme the load of a single central monitor is distributed among a number of monitors. We show, that hierarchical CGS detection has advantages over centralized detection: it allows for online monitoring of larger systems and for a more effective application control based on observed CGS. Hierarchical CGS detection can be coupled with a hierarchical application control scheme for better results. Further improvement is obtained if a timeout mechanism allows unterminated local states to be used for CGS construction. Relevant algorithms and simulation results are presented and discussed.
In an attempt to devise a general notion of model for spatial logic, we have been led to consider transition systems with an additional so-called spatial structure on the states, with both the tran- sition and the spa...
详细信息
View-Centric Reasoning (VCR) replaces CSP's perfect observer with multiple, possibly imperfect observers. To employ view-centric reasoning within existing CSP models requires a bookkeeping change. Specifically, VC...
详细信息
View-Centric Reasoning (VCR) replaces CSP's perfect observer with multiple, possibly imperfect observers. To employ view-centric reasoning within existing CSP models requires a bookkeeping change. Specifically, VCR introduces parallel events as a new primitive for constructing traces, and distinguishes two types of traces: histories and views. Previously, we gave the operational semantics of VCR, and demonstrated the utility of parallel traces to reason for the first time unambiguously about the meaning of the Linda predicate operations rdp ( ) and inp ( ). The choice of using an operational semantics to describe VCR makes direct comparison with CSP difficult;therefore, work is ongoing to recast VCR denotationally, then link VCR with the other CSP models within Hoare and He's Unifying Theories of programming. Initial efforts in this direction led to a comparison of VCR with Lawrence's HCSP. In this paper, we present some recent insights and abstractions - inspired by modern quantum physics - that have emerged whilst contemplating parallel traces in light of the unifying theories. These insights lead to a more natural expression of VCR. traces, in the sense that they more closely resemble CSP traces, thus forming a basis for linking VCR and CSP.
The growth of manufacturing control software from simple NC and PLC-based systems to concurrent networked systems incorporating PC's, PLC's, CNC's, and enterprise databases has created new challenges to th...
详细信息
The growth of manufacturing control software from simple NC and PLC-based systems to concurrent networked systems incorporating PC's, PLC's, CNC's, and enterprise databases has created new challenges to the design, implementation, and maintenance of safe and dependable manufacturing systems. Key milestones in this evolution, and the prospects for the use of formal verification methods in achieving enhanced dependability of future manufacturing software, are examined in this paper and presentation.
In this paper we develop a variant, regenerative randomization with Laplace transform inversion, of a previously proposed method (the regenerative randomization method) for the transient analysis of rewarded continuou...
详细信息
In this paper we develop a variant, regenerative randomization with Laplace transform inversion, of a previously proposed method (the regenerative randomization method) for the transient analysis of rewarded continuous time Markov models. Those models find applications in dependability and performability analysis of computer and telecommunication systems. The variant differs from regenerative randomization in that the truncated transformed model obtained in that method is solved using a Laplace transform inversion algorithm instead of standard randomization. As regenerative randomization, the variant requires the selection of a regenerative state on which the performance of the method depends. For a class of models, class C', including typical failure/repair models, a natural selection for the regenerative state exists and, with that selection, theoretical results are available assessing the performance of the method in terms of 'visible' characteristics. Using dependability class C' models of moderate size of a RAID 5 architecture we compare the performance of the variant with those of regenerative randomization and randomization with steady-state detection for irreducible models, and with those of regenerative randomization and standard randomization for models with absorbing states. For irreducible models, the new variant seems to be about as fast as randomization with steady-state detection for models which are not too small when the initial probability distribution is concentrated in the regenerative state, and significantly faster than regenerative randomization when the model is stiff and not very large. For stiff models with absorbing states, the new variant is much faster than standard randomization and significantly faster than regenerative randomization when the model is not very large. In addition, the variant seems to be able to achieve stringent accuracy levels safely.
Given a collection of points in the plane, one may draw a cell around each point in such a way that each point's cell is the portion of the plane consisting of all locations closer to that point than to any of the...
详细信息
Given a collection of points in the plane, one may draw a cell around each point in such a way that each point's cell is the portion of the plane consisting of all locations closer to that point than to any of the other points. The resulting geometric figure is called a Dirichlet tessellation. An algorithm for obtaining the boundaries of the cells given the points was derived by Green and Sibson in 1978. Here, methods are described for obtaining the locations of the points, given only the cell boundaries.
We study a typing scheme derived from a semantic situation where a single category possesses several closed structures, corresponding to different varieties of function type. In this scheme typing contexts are trees b...
详细信息
We study a typing scheme derived from a semantic situation where a single category possesses several closed structures, corresponding to different varieties of function type. In this scheme typing contexts are trees built from two (or more) binary combining operations, or in short, bunches. Bunched typing and its logical counterpart, bunched implications, have arisen in joint work of the author and David Pym. The present paper gives a basic account of the type system, and then focusses on concrete models that illustrate how it may be understood in terms of resource access and sharing. The most basic system has two context-combining operations, and the structural rules of Weakening and Contraction are allowed for one but not the other. This system includes a multiplicative, or substructural, function type --> alongside the usual (additive) function type -->;it is dubbed the alphalambda-calculus after its binders, alpha for the additive binder and lambda for the multiplicative, or lambdainear, binder. We show that the features of this system are, in a sense, complementary to calculi based on linear logic;it is incompatible with an interpretation where a multiplicative function uses its argument once, but perfectly compatible with a reading based on sharing of resources. This sharing interpretation is derived from syntactic control of interference, a type-theoretic method of controlling sharing of storage, and we show how bunch-based management of Contraction can be used to provide a more flexible type system for interference control.
This paper describes a framework for modeling macroscopic program behavior and applies it to optimizing prescient instruction prefetch - a novel technique that uses helper threads to improve single-threaded applicatio...
详细信息
ISBN:
(纸本)1581136641
This paper describes a framework for modeling macroscopic program behavior and applies it to optimizing prescient instruction prefetch - a novel technique that uses helper threads to improve single-threaded application performance by performing judicious and timely instruction prefetch. A helper thread is initiated when the main thread encounters a spawn point, and prefetches instructions starting at a distant target point. The target identifies a code region tending to incur I-cache misses that the main thread is likely to execute soon, even though intervening control flow may be unpredictable. The optimization of spawn-target pair selections is formulated by modeling program behavior as a Markov chain based on profile statistics. Execution paths are considered stochastic outcomes, and aspects of program behavior are summarized via path expression mappings. Mappings for computing reaching, and posteriori probability;path length mean, and variance;and expected path footprint are presented. These are used with Tarjan's fast path algorithm to efficiently estimate the benefit of spawn-target pair selections. Using this framework we propose a spawn-target pair selection algorithm for prescient instruction prefetch. This algorithm has been implemented, and evaluated for the Itanium® Processor Family architecture. A limit study finds 4.8% to 17% speedups on an in-order simultaneous multithreading processor with eight contexts, over nextline and streaming I-prefetch for a set of benchmarks with high I-cache miss rates. The framework in this paper is potentially applicable to other thread speculation techniques. Copyright 2003 ACM.
An evolutionary programming method for synthesizing advanced fiber gratings is developed. Two practical design examples including dispersion-less FBGs with shorter grating-length and gain flattening LPGs for entire ED...
详细信息
The possibility of employing the semantic theory of programming languages to analyze Win32 applications for detecting locks and deadlocks in them is proved. An appropriate formal method is developed. The use of the pr...
详细信息
The possibility of employing the semantic theory of programming languages to analyze Win32 applications for detecting locks and deadlocks in them is proved. An appropriate formal method is developed. The use of the proposed approach is demonstrated on examples.
暂无评论