A systematic incrementalization technique and its application to hardware design

A systematic transformation method based on incrementalization and value caching generalizes a broad family of program optimizations. It yields significant performance improvements in many program classes, including iterative schemes that characterize hardware specifications. CACHET is an interactive incrementalization tool. Although incrementalization is highly structured and automatable, better results are obtained through interaction, where the main task is to guide term rewriting based on data-specific identities. Incrementalization specialized to iteration corresponds to strength reduction, a familiar program improvement technique. This correspondence is illustrated by the derivation of a hardware-efficient nonrestoring square-root algorithm, which has also served as an example of theorem prover-based implementation verification. Published online: 9 October 2001 RID="*" ID="*"S.D. Johnson supported, in part, by the National Science Foundation under grant MIP-9601358. RID="**" ID="**"Y.A. Liu supported in part by the National Science Foundation under grant CCR-9711253, the Office of Naval Research under grant N00014-99-1-0132, and Motorola Inc. under a Motorola University Partnership in Research Grant. RID="***" ID="***"Y. Zhang is a student recipient of a Motorola University Partnership in Research Grant.     

Preface by the section editor

Preliminary versions of the papers of this special section originally appeared in the proceedings of the 6th edition of the conference “Tools and Algorithms for the Construction and Analysis of Systems” (Tacas) held in Berlin early April 2000 as a constituent event of the European joint conferences on Theory and Practice of Software. All papers present tools relevant in the context of systems validation. The first three focus on extensions or particular applications of model-checking techniques, whereas the fourth is about integration of design tools with validation tools, in particular theorem provers and model-checkers. Published online: 24 January 2003     

X-Ability: a theory of replication

Summary.   Different replication algorithms provide different solutions to the same basic problem. However, there is no precise specification of the problem itself, only of particular classes of solutions, such as active replication and primary-backup. Having a precise specification of the problem would help us better understand the space of possible solutions and possibly come out with new ones. We present a formal definition of the problem solved by replication in the form of a correctness criterion called x-ability (exactly-once ability). An x-able service has obligations to its environment and its clients. It must update its environment under exactly-once semantics. Furthermore, it must provide idempotent, non-blocking request processing and deliver consistent results to its clients. We illustrate the value of x-ability through a novel replication protocol that handles non-determinism and external side-effects. The replication protocol is asynchronous in the sense that it may vary, at run-time and according to the asynchrony of the system, between some form of primary-backup and some form of active replication. Received: December 2000 / Accepted: September 2001     

The Tenet experience and the design of protocols for integrated-services internetworks

The research done by the Tenet Group in multimedia networking has reached a point where it may be useful to reflect on the significance of its results for the current debate on how integrated-services internetworks should be designed. Such reflections constitute the main subject of this paper. The principles of the work and the conclusions reached so far by the Tenet researchers are discussed in the light of the conflict between the two major technologies being proposed to build future information infrastructures: namely, the Internet and the ATM technologies. The Tenet approach suggests one feasible way for resolving the conflict to the advantage of all the users of those infrastructures. This paper discusses various fundamental aspects of integrated-services network design: the choice of the service model, the type of charging policy to be adopted, and the selection of a suitable architecture.     

Grammar-based articulation for multimedia document design

This paper describes an approach to the problem of articulating multimedia information based on parsing and syntax-directed translation that uses Relational Grammars. This translation is followed by a constraint-solving mechanism to create the final layout. Grammatical rules provide the mechanism for mapping from a representation of the content and context of a presentation to forms that specify the media objects to be realized. These realization forms include sets of spatial and temporal constraints between elements of the presentation. Individual grammars encapsulate the “look and feel” of a presentation and can be used as generators of such a style. By making the grammars sensitive to the requirements of the output medium, parsing can introduce flexibility into the information realization process.     

Model checking: a hardware design perspective

Current practices in the verification of commercial hardware designs (digital, synchronous, and sequential semiconductors) are described. Recent advances in verification by the mathematical technique called model checking are described, and requirements for the successful application of model checking in commercial design are discussed.     

Generating FSMs from interworkings

Summary. A technique for the automated synthesis of FSMs (finite state machines) from sets of interworkings (synchronous sequence charts) is described. This is useful for obtaining feedback from a set of scenarios during a system's definition phase or test phase. It is sound in the sense that the generated FSM only exhibits traces that correspond to one of the interworkings from the given set. It preserves deadlock freedom in the sense that no behaviours are lost. The concrete syntax of SDL is used to represent the resulting FSMs. Received: December 1996 / Accepted: September 1998     

Generating diagnostic information for behavioral preorders

Summary.  This paper describes a method for generating diagnostic information that explains why a given finite-state system fails to be greater than its specification with respect to the prebisimulation preorder. The information takes the form of a logical formula satisfied by the specification but not by the system and thus may be used by system designers for debugging purposes. Our technique relies on modifying an algorithm for computing the prebisimulation preorder so that information needed for generating these distinguishing formulas is saved appropriately. As a number of other behavioral preorders may be characterized in terms of prebisimulation preorder, our approach may be used as a basis for computing diagnostic information for these relations as well. Received: August 1992/Accepted: May 1995     

Verification and optimization of a PLC control schedule

We report on the use of model checking techniques for both the verification of a process control program and the derivation of optimal control schedules. Most of this work has been carried out as part of a case study for the EU VHS project (Verification of Hybrid Systems), in which the program for a Programmable Logic Controller (PLC) of an experimental chemical plant had to be designed and verified. The original intention of our approach was to see how much could be achieved here using the standard model checking environment of SPIN/Promela. As the symbolic calculations of real-time model checkers can be quite expensive it is interesting to try and exploit the efficiency of established non-real-time model checkers like SPIN in those cases where promising work-arounds seem to exist. In our case we handled the relevant real-time properties of the PLC controller using a time-abstraction technique; for the scheduling we implemented in Promela a so-called variable time advance procedure . To compare and interpret the results we carried out the same case study with the aid of the real-time model checker Uppaal, enhanced with facilities for cost-guided state space exploration. Both approaches proved sufficiently powerful to verify the design of the controller and/or derive (time-)optimal schedules within reasonable time and space requirements. Published online: 2 October 2002 The work reported here was carried out while the second and third authors were employed by the Computer Science Department of the University of Nijmegen, Netherlands. The second author was supported by an NWO postdoc grant, the third author by an NWO PhD grant, and both were supported by the EU LTR project VHS (Project No. 26270).     

Context-based prefetch – an optimization for implementing objects on relations

When implementing persistent objects on a relational database, a major performance issue is prefetching data to minimize the number of round-trips to the database. This is especially hard with navigational applications, since future accesses are unpredictable. We propose the use of the context in which an object is loaded as a predictor of future accesses, where a context can be a stored collection of relationships, a query result, or a complex object. When an object O's state is loaded, similar state for other objects in O's context is prefetched. We present a design for maintaining context and for using it to guide prefetch. We give performance measurements of its implementation in Microsoft Repository, showing up to a 70% reduction in running time. We describe several variations of the optimization: selectively applying the technique based on application and database characteristics, using application-supplied performance hints, using concurrent database queries to support asynchronous prefetch, prefetching across relationship paths, and delayed prefetch to save database round-trips. Received May 3, 2000 / Accepted October 26, 2000     

Sequential consistency and the lazy caching algorithm

Summary. I introduce and discuss sequential consistency, a relaxed memory model, and define what it means for a protocol to implement sequential consistency. Then, I introduce the lazy caching protocol of Afek, Brown and Merrit [ABM93] and formalize it as a labeled transition system.     

Type-safe relaxing of schema consistency rules for flexible modelling in OODBMS

Object-oriented databases enforce behavioral schema consistency rules to guarantee type safety, i.e., that no run-time type error can occur. When the schema must evolve, some schema updates may violate these rules. In order to maintain behavioral schema consistency, traditional solutions require significant changes to the types, the type hierarchy and the code of existing methods. Such operations are very expensive in a database context. To ease schema evolution, we propose to support exceptions to the behavioral consistency rules without sacrificing type safety. The basic idea is to detect unsafe statements in a method code at compile-time and check them at run-time. The run-time check is performed by a specific clause that is automatically inserted around unsafe statements. This check clause warns the programmer of the safety problem and lets him provide exception-handling code. Schema updates can therefore be performed with only minor changes to the code of methods. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

Analysis and design of Hermite subdivision schemes

Published online: 14 May 2002     

Preface by the section editor

The papers in this special section present a sampling of new symbolic approaches for determining whether or not a system satisfies its specification. Abstracts of these articles appeared originally in the Proceedings of the 1999 Symposium on Tools and Algorithms for the Construction and Analysis of Systems (TACAS ’99). Published online: 18 July 2001     

Display Design of Process Systems Based on Functional Modelling

The prevalent way to present information in industrial computer displays is by using piping and instrumentation diagrams. Such interfaces have sometimes resulted in difficulties for operators because they are not sufficient to fulfil their needs. A systematic way that supports interface design therefore has to be considered. In the new design framework, two questions must be answered. Firstly, a modelling method is required to describe a process system. Such a modelling method can define the information content that must be displayed in interfaces. Secondly, how to communicate this information to operators efficiently must be considered. This will provide a basis for determining the visual forms that the information should take. This study discusses interface design of human–machine systems from these two points of view. Based on other scholars’ work, a comprehensive set of functional primitives is summarised as a basis to build a functional model of process systems. A library of geometrical presentations for these primitives is then developed. To support effective interface design, the concept of ‘functional macro’ is introduced and a way to map functional model to interface display is illustrated by applying several principles. To make our ideas clear, a central heating system is taken as an example and its functional model is constructed. Based on the functional model, the information to be displayed is determined. Several functional macros are then found in the model and their corresponding displays are constructed. Finally, by using the library of geometrical presentations for functional primitives and functional macros, the display hierarchy of the central heating system is developed. Reusability of functional primitives makes it possible to use the methodology to support interface design of different process systems.     

Proof engineering in the large: formal verification of Pentium®4 floating-point divider

We examine the challenges presented by large-scale formal verification of industrial-size circuits, based on our experiences in verifying the class of all micro-operations executing on the floating-point division and square root unit of the Intel IA-32 Pentium?4 microprocessor. The verification methodology is based on combining human-guided mechanised theorem-proving with low-level steps verified by fully automated model-checking. A key observation in the work is the need to explicitly address the issues of proof design and proof engineering, i.e., the process of creating proofs and the craft of structuring and formulating them, as concerns on their own right. Published online: 19 November 2002