Hierarchical GTM: constructing localized nonlinear projectionmanifolds in a principled way

It has been argued that a single two-dimensional visualization plot may not be sufficient to capture all of the interesting aspects of complex data sets and, therefore, a hierarchical visualization system is desirable. In this paper, we extend an existing locally linear hierarchical visualization system PhiVis in several directions: 1) We allow for nonlinear projection manifolds. The basic building block is the Generative Topographic Mapping (GTM). 2) We introduce a general formulation of hierarchical probabilistic models consisting of local probabilistic models organized in a hierarchical tree. General training equations are derived, regardless of the position of the model in the tree. 3) Using tools from differential geometry, we derive expressions for local directional curvatures of the projection manifold. Like PhiVis, our system is statistically principled and is built interactively in a top-down fashion using the EM algorithm. It enables the user to interactively highlight those data in the ancestor visualization plots which are captured by a child model. We also incorporate into our system a hierarchical, locally selective representation of magnification factors and directional curvatures of the projection manifolds. Such information is important for further refinement of the hierarchical visualization plot, as well as for controlling the amount of regularization imposed on the local models. We demonstrate the principle of the approach on a toy data set and apply our system to two more complex 12- and 18-dimensional data sets     

Computer-aided development of a real-time program

The refinement calculus is a well-established theory for formal development of imperative program code and is supported by a number of automated tools. Via a detailed case study, this article shows how refinement theory and tool support can be extended for a program with real-time constraints. The approach adapts a timed variant of the refinement calculus and makes corresponding enhancements to a theorem-prover based refinement tool.     

An action refinement operator for E-LOTOS with true concurrency

Action refinement is an important operation in the hierarchical synthesis of concurrent systems. We propose an action refinement operator for E-LOTOS, a standard process-algebraic language for formal specification of real-time, concurrent and reactive systems. As the first step towards giving E-LOTOS a multitude of refinement operators supporting a variety of strategies for event relationship inheritance, we propose an operator which seems both useful and simple to implement. When the operator is applied to an E-LOTOS process, it modifies its enhanced event structure, i.e. its recently defined true concurrency model. The operator allows multiple alternative implementations even for urgent events and properly reflects the fact that gate actions of E-LOTOS processes are in the general case abstractions of distributed data generation procedures.     

Coupled Transformation of Schemas, Documents, Queries, and Constraints

Coupled transformation occurs when multiple software artifacts must be transformed in such a way that they remain consistent with each other. For instance, when a database schema is adapted in the context of system maintenance, the persistent data residing in the system's database needs to be migrated to conform to the adapted schema. Also, queries embedded in the application code and any declared referential constraints must be adapted to take the schema changes into account. As another example, in XML-to-relational data mapping, a hierarchical XML Schema is mapped to a relational SQL schema with appropriate referential constraints, and the XML documents and queries are converted into relational data and relational queries. The 2LT project is aimed at providing a formal basis for coupled transformation. This formal basis is found in data refinement theory, point-free program calculation, and strategic term rewriting. We formalize the coupled transformation of a data type by an algebra of information-preserving data refinement steps, each witnessed by appropriate data conversion functions. Refinement steps are modeled by so-called two-level rewrite rules on type expressions that synthesize conversion functions between redex and reduct while rewriting. Strategy combinators are used to composed two-level rewrite rules into complete rewrite systems. Point-free program calculation is applied to optimized synthesize conversion function, to migrate queries, and to normalize data type constraints. In this paper, we provide an overview of the challenges met by the 2LT project and we give a sketch of the solutions offered.     

Minimax program control for the approach process in a two-level hierarchical discrete dynamical system

We consider a dynamical system consisting of three objects whose dynamics is given by vector linear discrete recurrent equations. The system contains two levels of managerial decision making, basic and secondary, that have different operational criteria and are united by informational and managerial connections defined in advance. For the dynamical system in question, we propose a mathematical formalization in the form of solving a multistage problem of two-level hierarchical minimax program control over the approach process with incomplete information and give a general scheme for its solution.     

Data refinement by calculation

Summary Data refinement is the systematic substitution of one data type for another in a program. Usually, the new data type is more efficient than the old, but possibly more complex; the purpose of the data refinement in that case is to make progress in program construction from more abstract to more concrete formulations. A recent trend in program construction is to calculate programs from their specifications; that contrasts with proving that a given program satisfies some specification. We investigate to what extent the trend can be applied to data refinement.Supported by British Petroleum Ltd.     

An adaptive multilevel multigrid formulation for Cartesian hierarchical grid methods

A Cartesian grid method with adaptive mesh refinement and multigrid acceleration is presented for the compressible Navier-Stokes equations. Cut cells are used to represent boundaries on the Cartesian grid, while ghost cells are introduced to facilitate the implementation of boundary conditions. A cell-tree data structure is used to organize the grid cells in a hierarchical manner. Cells of all refinement levels are present in this data structure such that grid level changes as they are required in a multigrid context do not have to be carried out explicitly. Adaptive mesh refinement is introduced using phenomenon-based sensors. The application of the multilevel method in conjunction with the Cartesian cut-cell method to problems with curved boundaries is described in detail. A 5-step Runge-Kutta multigrid scheme with local time stepping is used for steady problems and also for the inner integration within a dual time-stepping method for unsteady problems. The inefficiency of customary multigrid methods on Cartesian grids with embedded boundaries requires a new multilevel concept for this application, which is introduced in this paper. This new concept is based on the following novelties: a formulation of a multigrid method for Cartesian hierarchical grid methods, the concept of averaged control volumes, and a mesh adaptation strategy allowing to directly control the number of refined and coarsened cells.     

Human-robot teaming for search and rescue

This work establishes an architecture for Urban Search and Rescue and a methodology for mixing real-world and simulation-based testing. A sensor suite and sensor fusion algorithm for robust victim detection permits aggregation of sensor readings from various sensors on multiple robots. We have embarked on a research program focusing on the enabling technologies of effective USAR robotic rescue devices. The program is also researching system-level design, evaluation, and refinement of USAR rescue architectures that include teams of sensor-laden robots and human rescuers. In this paper, we present highlights from our research, which include our multiagent system (MAS) infrastructure, our simulation environment, and our approach to sensor fusion and interface design for effective robotic control.     

Verifying Contextual Refinement with Ownership Transfer

Contextual refinement is a compositional approach to compositional verification of concurrent objects.There has been much work designing program logics to prove the contextual refinement between the object implementation and its abstract specification.However,these program logics for contextual refinement verification cannot support objects with resource ownership transfer,which is a common pattern in many concurrent objects,such as the memory management module in OS kernels,which transfers the allocated memory block between the object and clients.In this paper,we propose a new approach to give abstract and implementation independent specifications to concurrent objects with ownership transfer.We also design a program logic to verify contextual refinement of concurrent objects w.r.t.their abstract specifications.We have successfully applied our logic to verifying an implementation of the memory management module,where the implementation is an appropriately simplified version of the original version from a real-world preemptive OS kernel.     

The virtual feedback problem in hierarchical representations of combinational circuits

Orders of magnitude of space and time can be saved if hierarchical algorithms are used for automatic synthesis and analysis of regular VLSI circuits. When we tried to apply this technique to compiled simulation of large regular combinational circuits, we observed that hierarchical representations of acyclic circuits often contain cycles. In this paper we study the question of whether this undesired property is necessary or not. We prove, that there are combinational circuits, which have a succinct cyclic hierarchical representation, but where each acyclic hierarchical representation is large. This negative result may be weakened, if we allow the circuits structure to be changed but not its behavior. We also discuss the effect of these observations on hierarchical simulation techniques and the complexity of pragmatic approaches such as the construction of a smallest acyclic refinement of a hierarchical representation.This work was supported by Deutsche Forschungsgemeinschaft under contract SFB 124 B1     

Parallel iterative refinement linear least squares solvers based on all-reduce operations

We present the novel parallel linear least squares solvers ARPLS-IR and ARPLS-MPIR for dense overdetermined linear systems. All internode communication of our ARPLS solvers arises in the context of all-reduce operations across the parallel system and therefore they benefit directly from efficient implementations of such operations. Our approach is based on the semi-normal equations, which are in general not backward stable. However, the method is stabilised by using iterative refinement. We show that performing iterative refinement in mixed precision also increases the parallel performance of the algorithm. We consider different variants of the ARPLS algorithm depending on the conditioning of the problem and in this context also evaluate the method of normal equations with iterative refinement. For ill-conditioned systems, we demonstrate that the semi-normal equations with standard iterative refinement achieve the best accuracy compared to other parallel solvers.We discuss the conceptual advantages of ARPLS-IR and ARPLS-MPIR over alternative parallel approaches based on QR factorisation or the normal equations. Moreover, we analytically compare the communication cost to an approach based on communication-avoiding QR factorisation. Numerical experiments on a high performance cluster illustrate speed-ups up to 3820 on 2048 cores for ill-conditioned tall and skinny matrices over state-of-the-art solvers from DPLASMA or ScaLAPACK.     

Design of an adaptive cache coherence protocol for large scalemultiprocessors

A large scale, cache-based multiprocessor that is interconnected by a hierarchical network such as hierarchical buses or a multistage interconnection network (MIN) is considered. An adaptive cache coherence scheme for the system is proposed based on a hardware approach that handles multiple shared reads efficiently. The new protocol allows multiple copies of a shared data block in the hierarchical network, but minimizes the cache coherence overhead by dynamically partitioning the network into sharing and nonsharing regions based on program behavior. The new cache coherence scheme effectively utilizes the bandwidth of the hierarchical networks and exploits the locality properties of parallel algorithms. Simulation experiments have been carried out to analyze the performance of the new protocol. The simulation results show that the new protocol gives 15% to 30% performance improvement over some existing cache coherence schemes on similar systems for a wide range of workload parameters     

Dynamic Transition Refinement

Refinement of Petri nets is well suited for the hierarchical design of system models. It is used to represent a model at different levels of abstraction.Usually, refinement is a static concept. For many scenarios, however, it is desirable to have a more flexible form of refinement. For example in the context of service updates, e.g. version control in distributed systems, a mechanism for dynamic transition refinement is needed.The requirement of dynamic refinement at runtime is quite strong. Since we would like to redefine the system structure by itself, transition refinement cannot be implemented by a model transformation. Instead, an approach is needed which allows for dynamic net structures that can evolve as an effect of transitions firing. In previous work we introduced nets-within-nets as a formalism for the dynamic refinement of tokens. Here we consider an extension of nets-within-nets that uses special net tokens describing the refinement structure of transitions. Using this formalism it is possible to update refinements, introduce alternative refinements, etc. We present some formal properties of the extended formalism and introduce an example implementation for the tool Renew in the context of workflow modeling.     

A framework for automated and certified refinement steps

The refinement calculus provides a methodology for transforming an abstract specification into a concrete implementation, by following a succession of refinement rules. These rules have been mechanized in theorem provers, thus providing a formal and rigorous way to prove that a given program refines another one. In a previous work, we have extended this mechanization for object-oriented programs, where the memory is represented as a graph, and we have integrated our approach within the rCOS tool, a model-driven software development tool providing a refinement language. Hence, for any refinement step, the tool automatically generates the corresponding proof obligations and the user can manually discharge them, using a provided library of refinement lemmas. In this work, we propose an approach to automate the search of possible refinement rules from a program to another, using the rewriting tool Maude. Each refinement rule in Maude is associated with the corresponding lemma in Isabelle, thus allowing the tool to automatically generate the Isabelle proof when a refinement rule can be automatically found. The user can add a new refinement rule by providing the corresponding Maude rule and Isabelle lemma.     

Conservative extension concepts for nonmonotonic knowledge bases

Conservative extensions of logical theories play an important role in software engineering. They provide a formal basis for program refinement and guarantee the integrity and transparency of modules and objects. This paper provides a detailed analysis of conservative extension concepts in the context of nonmonotonic knowledge bases, in particular default theories. Since there are different approaches to nonmonotonic reasoning based on different strategies for dealing with multiple extensions, we define several alternative refinement concepts and study their interrelationships. We also show that refinement is well behaved with respect to strong stratification, a technique for reducing computational effort in default reasoning. © 2000 John Wiley & Sons, Inc.     

A sequential real-time refinement calculus

We present a comprehensive refinement calculus for the development of sequential, real-time programs from real-time specifications. A specification may include not only execution time limits, but also requirements on the behaviour of outputs over the duration of the execution of the program. The approach allows refinement steps that separate timing constraints and functional requirements. New rules are provided for handling timing constraints, but the refinement of components implementing functional requirements is essentially the same as in the standard refinement calculus. The product of the refinement process is a program in the target programming language extended with timing deadline directives. The extended language is a machine-independent, real-time programming language. To provide valid machine code for a particular model of machine, the machine code produced by a compiler must be analysed to guarantee that it meets the specified timing deadlines. Received: 27 September 1997 / 13 June 2000     

Proving the Correctness of Multiprocess Programs

The inductive assertion method is generalized to permit formal, machine-verifiable proofs of correctness for multiprocess programs. Individual processes are represented by ordinary flowcharts, and no special synchronization mechanisms are assumed, so the method can be applied to a large class of multiprocess programs. A correctness proof can be designed together with the program by a hierarchical process of stepwise refinement, making the method practical for larger programs. The resulting proofs tend to be natural formalizations of the informal proofs that are now used.