Abstract

We have developed a formal definition of correctness for pipelines that ensures that transactions terminate and satisfy a functional specification. This definition separates the correctness criteria associated with the pipelining aspects of a design from the functional relationship between input and output transactions. Using this definition, we developed and formally verified a technique that divides the verification of a pipeline into two separate tasks: proving that the pipelining circuitry meets the pipelining correctness criteria and that the datapath and control circuitry meet the functional specification. The first proof is data independent (except for pipelines that use data-dependent control). The second proof is purely combinational: there is no notion of time and each possible input transaction can be dealt with independently. In addition, we have created a framework that structures and simplifies the proof of the pipelining circuitry. Document type: Part of book or chapter of book

Abstract

Service-oriented computing is calling for novel computational models and languages with primitives for client-server interaction, orchestration and unexpected events handling. We present CaSPiS , a process calculus where the notions of session and pipelining play a central role. Sessions are two-sided and can be equipped with protocols executed by each side. Pipelining permits orchestrating the flow of data produced by different sessions. The calculus is also equipped with operators for handling (unexpected) termination of the partner's side of a session. Several examples are presented to provide evidence for the flexibility of the chosen set of primitives. Our main result shows that in CaSPiS it is possible to program a "graceful termination" of nested sessions, which guarantees that no session is forced to hang forever after the loss of its partner. Document type: Part of book or chapter of book

Abstract

We describe a methodology for the formal verification of complex out-of-order pipelines as they may be used as execution units in out-of-order processors. The pipelines may process multiple instructions simultaneously, may have branches and cycles in the pipeline structure, may have variable latency, and may reorder instructions internally. The methodology combines model-checking for the verification of the pipeline control, and theorem proving for the verification of the pipeline functionality. In order to combine both techniques, we formally verify that the FairCTL operators defined in ?-calculus match their intended semantics expressed in a form where computation traces are explicit, since this form is better suited for theorem proving. This allows the formally safe translation of model-checked properties of the pipeline control into a theorem-proving friendly form, which is used for the verification of the overall correctness, including the functionality. As an example we prove the correctness of the pipeline of a multiplication/division floating point unit with all the features mentioned above. Document type: Part of book or chapter of book

Abstract

Since its inception, a main objective of the Ada language has been to assist in the development of large and robust applications. In addition to that, the language also provides support for building safety-critical applications, e.g. by facilitating validation and verification of such programs. The latest revision of the language has brought some additional improvements in the safety area, such as the Normalize_Scalars pragma, which ensures an automatic initialization of the nonexplicitly initialized scalars. This paper presents Initialize Scalars, an enrichment of the Normalize_Scalars concept, and an extended mode to verify at run-time the validity of scalars, both designed for easy use in existing large applications. Their implementation in GNAT Pro (the GNU Ada 95 compiler) is discussed. The practical results obtained on a large Air Traffic Flow Management application are presented. Document type: Part of book or chapter of book

Abstract

A joint project of the Austrian company Frequentis1 and the Technical University Graz demonstrates the applicability of executable formal models2. The formal method VDM++ has been applied to specify a safety critical voice communication system (VCS) for air-traffic control. Besides the expected improvement of the informal speciffication documents, 64 defects have been found, the efficiency of the system test-cases to cover the functionality of the VCS has been analyzed. In order to get a test-coverage measure, the formal specification has been animated with existing system test-cases using IFAD’s VDMTools. Document type: Part of book or chapter of book

Abstract

We present a two-part approach for verifying out-of-order execution. First, the complexity of out-of-order issue and scheduling is handled by creating an in-order abstraction of the out-of-order execution core. Second, incremental flushing addresses the complexity difficulties encountered by automated abstraction functions on very deep pipelines. We illustrate the techniques on a model of a simple out-of-order processor core. Document type: Part of book or chapter of book

Abstract

Open Distributed Processing (ODP) is a framework for specifying open distributed systems, under development by the International Standards Organisation (ISO). It is based on the general idea of viewpoints - i.e. partial specifications of an overall system, from different perspectives - but assumes five specific, named viewpoints, which are described informally in the ODP Reference Model (RM-ODP). This paper summarises some observations regarding an attempt to use ODP to specify a complex air traffic control system. Some of the key issues that arise are discussed further in the context of the formal specification of a simpler, idealised model, involving two formalised viewpoints - the Information Viewpoint (a high-level, abstract specification, in Z), and the Computational Viewpoint (a specification of distributed components and objects, in Object-Z). Document type: Book