prialt in Handel-C: an operational semantics

We describe an operational semantics for the hardware compilation language Handel-C [7], which is a C-like language with channel communication and parallel constructs which compiles down to mainly synchronously clocked hardware. The work in this paper builds on previous work describing the semantics of the “prialt” construct within Handel-C [5] and a denotational semantics for part of the language [6]. We describe a key subset of the language and show how a design decision for the real language, namely that default guards in a prialt statement executed in “zero-time”, has consequences for the complexity of the operational semantics. We present the operational semantics, along with a revised and completed prialt semantics, indicating clearly the interface between them. We then describe a notion of observational equivalence and present an example illustrating how we handle the complexity of nested prialts in default guards.     

Compositional operational semantics for Prolog programs

To relate operational semantics of logic programs to its declarative semantics, we have to rely on SLD-trees. But this form of operational semantics does not make it easy to relate execution behaviour to program structure. The reason is that the traversal of SLD-trees decomposes in a way that is different from the decomposition (which is by disjunction and conjunction) of programs. We propose SLD-contours, a variant of SLD-trees, that are, like programs, built up out of simpler components by means of disjunction and conjunction. The traversal of SLD-trees carries over to the traversal of SLD-contours in such a way that the trace events of the Box Model (Try, Succeed, Retry, Fail) are reproduced in the same way as during the execution of the program. ThusSLD-contours relate the trace more closely to the program than SLD-trees. SLD-contours specify the trace more completely than the Box Model does.     

Use of a formal notation for static semantics in compiler design

Formal notations for the specification of the syntax and the dynamic semantics of languages exist and are of great benefit to the compiler writer. However, formal notations for the static semantics of languages have tended to be tools of the language designer and of little practical significance to the compiler writer. This paper describes how a particular notation was used to assist in the implementation of a Cobol compiler and of an interpreter for a simulation language.     

An operational semantics for a calculus for wireless systems

In wireless systems, the communication mechanism combines features of broadcast, synchrony, and asynchrony. We develop an operational semantics for a calculus of wireless systems. We present different Reduction Semantics and a Labelled Transition Semantics and prove correspondence results between them. Finally, we apply CWS to the modelling of the Alternating Bit Protocol, and prove a simple correctness result as an example of the kind of properties that can be formalized in this framework.A major goal of the semantics is to describe the forms of interference among the activities of processes that are peculiar of wireless systems. Such interference occurs when a location is simultaneously reached by two transmissions. The Reduction Semantics differ on how information about the active transmissions is managed.We use the calculus to describe and analyse a few properties of a version of the Alternating Bit Protocol.     

Distributed speculative execution for reliability and fault tolerance: an operational semantics

This paper examines the use of speculations, a form of distributed transactions, for improving the reliability and fault tolerance of distributed systems. A speculation is defined as a computation that is based on an assumption that is not validated before the computation is started. If the assumption is later found to be false, the computation is aborted and the state of the program is rolled back; if the assumption is found to be true, the results of the computation are committed. The primary difference between a speculation and a transaction is that a speculation is not isolated—for example, a speculative computation may send and receive messages, and it may modify shared objects. As a result, processes that share those objects may be absorbed into a speculation. We present a syntax, and an operational semantics in two forms. The first one is a speculative model, which takes full advantage of the speculative features. The second one is a nonspeculative, nondeterministic model, where aborts are treated as failures. We prove the equivalence of the two models, demonstrating that speculative execution is equivalent to failure-free computation.     

Linking operational semantics and algebraic semantics for a probabilistic timed shared-variable language

Complex software systems typically involve features like time, concurrency and probability, with probabilistic computations playing an increasing role. However, it is currently challenging to formalize languages incorporating all those features. Recently, the language PTSC has been proposed to integrate probability and time with shared-variable concurrency (Zhu et al. (2006, 2009) [51] and [53]), where the operational semantics has been explored and a set of algebraic laws has been investigated via bisimulation. This paper investigates the link between the operational and algebraic semantics of PTSC, highlighting both its theoretical and practical aspects.The link is obtained by deriving the operational semantics from the algebraic semantics, an approach that may be understood as establishing soundness of the operational semantics with respect to the algebraic semantics. Algebraic laws are provided that suffice to convert any PTSC program into a form consisting of a guarded choice or an internal choice between programs, which are initially deterministic. That form corresponds to a simple execution of the program, so it is used as a basis for an operational semantics. In that way, the operational semantics is derived from the algebraic semantics, with transition rules resulting from the derivation strategy. In fact the derived transition rules and the derivation strategy are shown to be equivalent, which may be understood as establishing completeness of the operational semantics with respect to the algebraic semantics.That theoretical approach to the link is complemented by a practical one, which animates the link using Prolog. The link between the two semantics proceeds via head normal form. Firstly, the generation of head normal form is explored, in particular animating the expansion laws for probabilistic interleaving. Then the derivation of the operational semantics is animated using a strategy that exploits head normal form. The operational semantics is also animated. These animations, which again supports to claim soundness and completeness of the operational semantics with respect to the algebraic, are interesting because they provide a practical demonstration of the theoretical results.     

Extracting a formally verified, fully executable compiler from a proof assistant

Compilers that have been formally verified in theorem provers are often not directly usable because the formalization language is not a general-purpose programming language or the formalization contains non-executable constructs. This paper takes a comprehensive, even though simplified model of Java, formalized in the Isabelle proof assistant, as starting point and shows how core functions in the translation process (type checking and compilation) are defined and proved correct. From these, Isabelle's program extraction facility generates ML code that can be directly interfaced with other, possibly “unsafe” code.     

Direct microprogrammed execution of the intermediate text from a high-level language compiler

Microprogramming commonly executed operations can improve the computational speed of data processing systems. This paper describes how microprogramming may be used to execute directly the intermediate text generated by a high-level language compiler after syntactic and semantic analysis of the input source program.Direct microprogrammed execution of common forms of intermediate text—i.e. quadruples, triples, and duos—has been simulated. A comparison is made, in terms of storage requirements and execution time, of this direct microprogrammed system with the present methods which result in machine language representation and execution of the intermediate text. Direct generation of a microprogram from the high-level language statements is also examined.Timing assumptions for comparative purposes have been based on the IBM 360 MOD 50 system. Simulation and timing estimates for the microprograms have been carried out on a microprogram directed simulator which closely represents the architectural organization of the MOD 50.     

Design space exploration of an optimized compiler approach for a generic reconfigurable array architecture

Several mesh-like coarse-grained reconfigurable architectures have been devised in the last few years accompanied with their corresponding mapping flows. One of the major bottlenecks in mapping algorithms on these architectures is the limited memory access bandwidth. Only a few mapping methodologies encountered the problem of the limited bandwidth while none has explored how the performance improvements are affected, from the architectural characteristics. We study in this paper the impact that the architectural parameters have on performance speedups achieved when the PEs’ local RAMs are used for storing the variables with data reuse opportunities. The data reuse values are transferred in the internal interconnection network instead of being fetched, from external memories, in order to reduce the data transfer burden on the bus network. A novel mapping algorithm is also proposed that uses a list scheduling technique. The experimental results quantified the trade-offs that exist between the performance improvements and the memory access latency, the interconnection network and the processing element’s local RAM size. For this reason, our mapping methodology targets on a flexible architecture template, which permits such an exploration. More specifically, the experiments showed that the improvements increase with the memory access latency, while a richer interconnection topology can improve the operation parallelism by a factor of 1.4 on average. Finally, for the considered set of benchmarks, the operation parallelism has been improved from 8.6% to 85.1% from the application of our methodology, and by having each PE’s Local RAM a size of 8 words.

Deriving occlusions in static scenes from observations of interactions with a moving figure

Many applications in computer vision are based on a single static camera observing a scene which is static except for one or more figures (people, vehicles, etc.) moving through it. In these applications it is useful to understand whether the moving figure is partially occluded by some static element of the scene. Such partial occlusions, when undetected, confuse the analysis of the figure's pose and activity. We present an algorithm that uses only the information provided by moving figures to simply and efficiently derive the position of static occluding bodies. Once these occlusions are obtained, we demonstrate successful reasoning about the occlusion status of future figures within the same scene. The occlusion positions from multiple views of the same scene are used to extract an estimate of the three-dimensional position and shape of the occlusion. Experimental results validating the method are included.     

Extracting a largest redundancy-free XML storage structure from an acyclic hypergraph in polynomial time

Given a hypergraph and a set of embedded functional dependencies, we investigate the problem of determining the conditions under which we can efficiently generate redundancy-free XML storage structures with as few scheme trees as possible. Redundancy-free XML structures guarantee both economy in storage space and the absence of update anomalies, and having the least number of scheme trees requires the fewest number of joins to navigate among the data elements. We know that the general problem is intractable. The problem may still be intractable even when the hypergraph is acyclic and each hyperedge is in Boyce–Codd normal form (BCNF). As we show here, however, given an acyclic hypergraph with each hyperedge in BCNF, a polynomial-time algorithm exists that generates a largest possible redundancy-free XML storage structure. Successively generating largest possible scheme trees from among hyperedges not already included in generated scheme trees constitutes a reasonable heuristic for finding the fewest possible scheme trees. For many practical cases, this heuristic finds the set of redundancy-free XML storage structures with the fewest number of scheme trees. In addition to a correctness proof and a complexity analysis showing that the algorithm is polynomial, we also give experimental results over randomly generated but appropriately constrained hypergraphs showing empirically that the algorithm is indeed polynomial.     

Asymmetric Adjustment and Bias in Estimation of an Equilibrium Relationship from a Cointegrating Regression

This paper uses Monte Carlo methods to investigate the effects of asymmetricadjustment on estimates of the parameters of the equilibrium relationshipbetween a set of variables. We demonstrate that simple least squares estimatesand the implicit estimates from a symmetric error correction model both leadto biases in the constant term. This bias increases with the size of theasymmetry and shows no tendency to decline with the sample size. We also showthat if the biased estimates of the equilibrium relationship are then used todevide the sample into different regimes to test for assymmetric adjustment,then the resulting test has low power. The power of tests for asymmetry canbe increased significantly by using simultaneous estimation of the parametersof the equilibrium relationship and the asymmetric adjustment process.     

High-order scheme for determination of a control parameter in an inverse problem from the over-specified data

The problem of finding the solution of partial differential equations with source control parameter has appeared increasingly in physical phenomena, for example, in the study of heat conduction process, thermo-elasticity, chemical diffusion and control theory. In this paper we present a high order scheme for determining unknown control parameter and unknown solution of parabolic inverse problem with both integral overspecialization and overspecialization at a point in the spatial domain. In these equations, we first approximate the spatial derivative with a fourth order compact scheme and reduce the problem to a system of ordinary differential equations (ODEs). Then we apply a fourth order boundary value method for the solution of resulting system of ODEs. So the proposed method has fourth order accuracy in both space and time components and is unconditionally stable due to the favorable stability property of boundary value methods. Several numerical examples and also some comparisons with other methods in the literature will be investigated to confirm the efficiency of the new procedure.     

A Nash equilibrium solution in an oligopoly market: The search for Nash equilibrium solutions with replicator equations derived from the gradient dynamics of a simplex algorithm

The present analysis applies continuous time replicator dynamics to the analysis of oligopoly markets. In the present paper, we discuss continuous game problems in which decision-making variables for each player are bounded on a simplex by equalities and non-negative constraints. Several types of problems are considered under conditions of normalized constraints and non-negative constraints. These problems can be classified into two types based on their constraints. For one type, the simplex constraint applies to the variables for each player independently, such as in a product allocation problem. For the other type, the simplex constraint applies to interference among all players, creating a market share problem. In the present paper, we consider a game problem under the constraints of allocation of product and market share simultaneously. We assume that a Nash equilibrium solution can be applied and derive the gradient system dynamics that attain the Nash equilibrium solution without violating the simplex constraints. Models assume that three or more firms exist in a market. Firms behave to maximize their profits, as defined by the difference between their sales and cost functions with conjectural variations. The effectiveness of the derived dynamics is demonstrated using simple data. The present approach facilitates understanding the process of attaining equilibrium in an oligopoly market.