bluuebunny/crossref_metadata_2025_split huggingface dataset:
Testing for software reliability
Authors: Brown J. R. , Lipow M. 
Published: November 2005

This paper presents a formulation of a novel methodology for evaluation of testing in support of operational reliability assessment and prediction. The methodology features an incremental evaluation of the representativeness of a set of development and validation test cases together with definition of additional test cases to enhance those qualities.
If test cases are derived in typical fashion (i.e., to find and remove bugs, to investigate software performance under off-nominal conditions, to exercise structural elements and functional capabilities of the software, and to demonstrate satisfaction of software requirements), then the complete set of test cases is not necessarily representative of anticipated operational usage. The paper reports on initial research into formulation of valid measures of testing representativeness.
Several techniques which permit specification of expected operational usage are described, and a technique for evaluating the correlation between actual testing accomplished and expected operational usage is defined. An unbiased estimator for operational usage reliability is proposed and justified as a function of a specified operational profile; confidence in the estimate is derived from a measure of the degree to which testing is representative of expected operational application.
An experimental application of the techniques to a small program is provided as an illustration of the proposed use of the methodology for operational software reliability estimation. The relationship between structural exercise testing thoroughness and operational usage representativeness is discussed; the specification of a quantified reliability requirement and an explicit, required representativeness measure (or confidence) is identified as integral to effective application of the proposed reliability testing methodology; efforts to extend, formalize and generalize the methodology are described; and expected benefits, as well as potential problems and limitations are identified.
Language support for Morton-order matrices
Authors: Wise David S. , Frens Jeremy D. , Gu Yuhong , Alexander Gregory A. 
Published: November 2005

The uniform representation of 2-dimensional arrays serially in Morton order (or {\eee} order) supports both their iterative scan with cartesian indices and their divide-and-conquer manipulation as quaternary trees. This data structure is important because it relaxes serious problems of locality and latency, and the tree helps to schedule multi-processing. Results here show how it facilitates algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment.We have built a rudimentary C-to-C translator that implements matrices in Morton-order from source that presumes a row-major implementation. Early performance from LAPACK's reference implementation of \texttt{dgesv} (linear solver), and all its supporting routines (including \texttt{dgemm} matrix-multiplication) form a successful research demonstration. Its performance predicts improvements from new algebra in back-end optimizers.We also present results from a more stylish \texttt{dgemm} algorithm that takes better advantage of this representation. With only routine back-end optimizations inserted by hand (unfolding the base case and passing arguments in registers), we achieve machine performance exceeding that of the manufacturer-crafted {\tt dgemm} running at 67% of peak flops. And the same code performs similarly on several machines.Together, these results show how existing codes and future block-recursive algorithms can work well together on this matrix representation. Locality is key to future performance, and the new representation has a remarkable impact.
Accurate data redistribution cost estimation in software distributed shared memory systems
Authors: Morris Donald G. , Lowenthal David K. 
Published: November 2005

Distributing data is one of the key problems in implementing efficient distributed-memory parallel programs. The problem becomes more difficult in programs where data redistribution between computational phases is considered. The
global data distribution
problem is to find the optimal distribution in multi-phase parallel programs. Solving this problem requires accurate knowledge of data redistribution cost.

We are investigating this problem in the context of a software distributed shared memory (SDSM) system, in which obtaining accurate redistribution cost estimates is difficult. This is because SDSM communication is implicit: It depends on access patterns, page locations, and the SDSM consistency protocol.
We have developed integrated compile- and run-time analysis for SDSM systems to determine accurate redistribution cost estimates with low overhead. Our resulting system, SUIF-Adapt, can efficiently and accurately estimate execution time, including redistribution, to within 5% of the actual time in all of our test cases and is often much closer. These precise costs enable SUIF-Adapt to find efficient global data distributions in multiple-phase programs.
Blocking and array contraction across arbitrarily nested loops using affine partitioning
Authors: Lim Amy W. , Liao Shih-Wei , Lam Monica S. 
Published: November 2005

Applicable to arbitrary sequences and nests of loops, affine partitioning is a program transformation framework that unifies many previously proposed loop transformations, including unimodular transforms, fusion, fission, reindexing, scaling and statement reordering. Algorithms based on affine partitioning have been shown to be effective for parallelization and communication minimization. This paper presents algorithms that improve data locality using affine partitioning.
Blocking and array contraction are two important optimizations that have been shown to be useful for data locality. Blocking creates a set of inner loops so that data brought into the faster levels of the memory hierarchy can be reused. Array contraction reduces an array to a scalar variable and thereby reduces the number of memory operations executed and the memory footprint. Loop transforms are often necessary to make blocking and array contraction possible.
By bringing the full generality of affine partitioning to bear on the problem, our locality algorithm can find more contractable arrays than previously possible. This paper also generalizes the concept of blocking and shows that affine partitioning allows the benefits of blocking be realized in arbitrarily nested loops. Experimental results on a number of benchmarks and a complete multigrid application in aeronautics indicates that affine partitioning is effective in practice.
An overview of DOD-STD-1838A (proposed) the common APSE interface set: revision
Authors: Munck Robert , Oberndorf Patricia , Ploedereder Erhard , Thall Richard 
Published: November 2005

A five-year effort under the Ada Joint Program Office has developed a proposed standard for a host system interface as seen by tools running in an Ada Programming Support Environment (APSE). Standardization of this interface as DOD-STD-1838A will have a number of desirable effects for the Department of Defense, including tool portability, tool integration, data transportability, encouragement of a market in portable tools, and better programmer productivity.
As the capability of tools to communicate with each other is a central requirement in APSEs, the Common APSE Interface Set (CAIS) has paid particular attention to facilitate such communication in a host-independent fashion. CAIS incorporates a well-integrated set of concepts tuned to the needs of writers and users of integrated tool sets.

This paper covers several of these concepts:

• the entity management system used in place of a traditional filing system,

• object typing with inheritance,

• process control including atomic transactions,

• access control and security,

• input/output methods,

• support for distributed resource control, and

• facilities for inter-system data transport.
Experience with topaz telebugging
Authors: Redell David D. 
Published: November 2005

The Topaz TeleDebug (TTD) facility provides a remote debugging capability supporting software development in the Topaz environment. Topaz is a software environment providing rich support for programming in Modula2+, and extended version of Modula 2. TTD allows uniform use of the same high level source language debugger for all debugging (both local and remote) of software at all levels of the system. Special care has been taken to maximize TTD's reliability and robustness. Our experience suggests that such a facility can be extremely useful, very dependable and quite inexpensive. It also suggests that the implementation issues can be somewhat subtle, and that correct choices in this area are vital if the promise of such a scheme is to be fully realized. This paper focuses on those implementation issues in a fair amount of detail, analyzing the limitations of our first TTD implementation and the redesign that produced a second, improved version. Our main conclusion is that the target (debuggee) end of such a facility should be implemented at the lowest possible level in the operating system, and that a uniformly applicable remote invocation (e.g. remote procedure call) facility is key to enabling this approach. We also conclude that strict adherence to layered information hiding can lead to serious difficulties in the implementation of a remote debugging protocol.
The discussion should be of particular interest to others designers of remote debugging facilities. While the paper does not devote much attention to higher level issues (e.g. novel user interfaces for debugging concurrent or distributed programs) most of the ideas discussed should be applicable to a wide class of debuggers, including those with higher aspirations for debugging such programs.
IGOR: a system for program debugging via reversible execution
Authors: Feldman Stuart I. , Brown Channing B. 
Published: November 2005

Typical debugging tools are insufficiently powerful to find the most difficult types of program misbehaviors. We have implemented a prototype of a new debugging system, IGOR, which provides a great deal more useful information and offers new abilities that are quite promising. The system runs fast enough to be quite useful while providing many features that are usually available only in an interpreted environment. We describe here some improved facilities (reverse execution, selective searching of execution history, substitution of data and executable parts of the programs) that are needed for serious debugging and are not found in traditional single-thread debugging tools. With a little help from the operating system, we provide these capabilities at reasonable cost without modifying the executable code and running fairly close to full speed. The prototype runs under the DUNE distributed operating system.
The current system only supports debugging of single-thread programs. The paper describes planned extensions to make use of extra processors to speed the system and for applying the technique to multi-thread and time dependent executions.
High-level debugging in parasight
Authors: Aral Ziya , Gertner Ilya 
Published: November 2005

Debugging parallel programs with time critical dependencies is difficult due to subtle race conditions that may cause deadlock, starvation, and other errors. These errors can be detected by multiple instrumentation points triggered by logical assertions. Although some advanced debuggers provide a programmer with the ability to define complex logical assertions, they are inadequate for debugging parallel programs due to the high overhead of monitoring these assertions.
This paper describes the facilities for high-level debugging in Parasight™ a parallel programming environment. In Parasight, high-level debugging facilities are implemented as separate programs that are linked dynamically to a target program. The target program is controlled by attaching these debugging programs to light-weight instrumentation points that are dynamically inserted and deleted. Different facilities of arbitrary complexity may be created to support high-level debugging. Parasight has been implemented on Multimax™ a shared-memory multiprocessor. It has been used for debugging and profiling “C” programs.
Concurrent algorithmic debugging
Authors: Lichtenstein Yossi , Shapiro Ehud 
Published: November 2005

Algorithmic Debugging is a theory of debugging that uses queries on the compositional semantics of a program in order to localize bugs. It uses the following principle: if a computation of a program's component gives an incorrect result, while all the subcomputations it invokes compute correct results, then the code of this component is erroneous.
Algorithmic Debugging is applied, in this work, to reactive systems, in particular to programs written in Flat Concurrent Prolog (FCP). Debugging reactive systems is known to be more difficult than the debugging of functional systems. A functional system is fully described by the relation between its initial input and final output; this context-freedom is used in debugging. A reactive system continuously responds to external inputs, thus its debugging cannot make use of context-free input/output relations.

Given a compositional semantic model for a concurrent programming language, we demonstrate how one can directly apply the ideas of Algorithmic Debugging to obtain a theory of program debugging for the considered language. The conflict between the context-freedom of input/ output relations and the reactive nature of concurrent systems is resolved by using semantic objects which record the reactive nature of the system's components. In functional algorithmic debugging the queries relate to input/output relations; in concurrent algorithmic debugging the queries refer to semantic objects called
processes
which capture the reactive nature of FCP computations.

A diagnosis algorithm for incorrect FCP programs is proposed. The algorithm gets an erroneous computation and using queries isolates an erroneous clause or an incomplete procedure. An FCP implementation of the diagnosis algorithm demonstrates the usefulness as well as the difficulties of Algorithmic Debugging of FCP programs.
Generational reference counting: a reduced-communication distributed storage reclamation scheme
Authors: Goldberg B. 
Published: November 2005

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.
The communication overhead for generational reference counting is one message for each copy of an interprocessor reference (pointer). Unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. A message is sent only when a reference is discarded. Unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures.
In this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. We also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.
Object-oriented design: a responsibility-driven approach
Authors: Wirfs-Brock R. , Wilkerson B. 
Published: November 2005

Object-oriented programming languages support encapsulation, thereby improving the ability of software to be reused, refined, tested, maintained, and extended. The full benefit of this support can only be realized if encapsulation is maximized during the design process.
We argue that design practices which take a data-driven approach fail to maximize encapsulation because they focus too quickly on the implementation of objects. We propose an alternative object-oriented design method which takes a responsibility-driven approach. We show how such an approach can increase the encapsulation by deferring implementation issues until a later stage.
Mandatory security in object-oriented database systems
Authors: Thuraisingham M. B. 
Published: November 2005

A multilevel secure object-oriented data model (using the ORION data model) is proposed for which mandatory security issues in the context of a database system is discussed. In particular the following issues are dealt with: (1) the security policy for the system, (2) handling polyinstantiation, and (3) handling the inference problem.
A set of security properties that has been established in this paper is more complete than those that have been proposed previously. Finally we describe how certain security constraints are handled by our model.
Is continuation-passing useful for data flow analysis?
Authors: Sabry Amr , Felleisen Matthias 
Published: November 2005

The widespread use of the continuation-passing style (CPS) transformation in compilers, optimizers, abstract interpreters, and partial evaluators reflects a common belief that the transformation has a positive effect on the analysis of programs. Investigations by Nielson [13] and Burn/Filho [5,6] support, to some degree, this belief with theoretical results. However, they do not pinpoint the source of increased abstract information and do not explain the observation of many people that continuation-passing confuses some conventional data flow analyses.
To study the impact of the CPS transformation on program analysis, we derive three canonical data flow analyzers for the core of an applicative higher-order programming language. The first analyzer is based on a direct semantics of the language, the second on a continuation-semantics of the language, and the last on the direct semantics of CPS terms. All analyzers compute the control flow graph of the source program and hence our results apply to a large class of data flow analyses. A comparison of the information gathered by our analyzers establishes the following points:
In view of these results, we argue that, in practice, a direct data flow analysis that relies on some amount of duplication would be as satisfactory as a CPS analysis.
Experience with porting techniques on a COBOL 74 compiler
Authors: Kipps I. M. 
Published: November 2005

The problems of compiler construction have largely been solved for COBOL '74, but a remaining fundamental consideration in a commercial environment is the cost of compiler development. This can be reduced by the use of portable software, but the cost of porting to a new system remains significant. In the microprocessor system market, two approaches have been followed. The first is to produce software for a virtual machine environment and simulate this on real hardware be means of an interpreter. Most software, including language processors and large parts of the operating system, can be transferred almost unchanged to a new processor. Nearly all commercial software for microprocessors has been developed on this basis. The alternative approach is to produce software which, by virtue of certain characteristics, can be made to be portable to new real machine environments, provided the appropriate high level language compiler is available.
We have developed an ANS COBOL 74 compiler for microprocessors using this second approach [1]. Since the compiler compiles COBOL at a level approaching level 2 in the main modules to the true machine code of the target machine, the same approach becomes available to the applications programmer. As far as can be established, this work is unique. Both compiler and object code interface directly to the machine environment. No interpreter is required for their execution. The compiler system runs on, and generates code for, three machines. In addition, since the compiler is written in a high level language, portable cross compilers are available.
A flexible compiler structure that allows dynamic phase ordering
Authors: LaLonde Wilf R. , Rivieres Jim des 
Published: November 2005

Traditionally, compilers have been internally organized into separate phases that are invoked in a fixed, predetermined order. However, the optimal phase invocation order is usually different for different contexts, such as (1) large batch-oriented production environments, (2) small batch-oriented student environments, and (3) interactive programming environments.
We discuss the constraints that must be met in order to obtain a compiler with flexible phase ordering, a property that allows the compiler to be designed and implemented without consideration for the intended operating environment. Flexible phase ordering allows the compiler to be specially configured after the fact. A production compiler based on this principle is also discussed.
The linear graph package, a compiler building environment
Authors: Marshall Howard Z. 
Published: November 2005

The Linear Graph package is a collection of software tools that provides a software development environment particularly well suited to compiler construction. More precisely, the Linear Graph (or “LG”) package is a generic specification of these tools. No specific implementation language or host computer system is presumed, and, in fact, LG packages have been built in several languages on a variety of computers.
These LG packages have proved to be powerful tools. We have used LG to build two FORTRAN-77 compilers, a JOVIAL compiler, and a Pascal compiler; we are presently using LG to build a CHILL compiler, an Ada* compiler, a third FORTRAN-77 compiler, and an optimizer for the JOVIAL compiler. We have also used LG to build some related support software: the linker used with the Pascal compiler, and a global symbol data base system for the JOVIAL and Pascal compilers. The LG package simplified the design, implementation, and maintenance of these compilers and support programs.
An attribute grammar for Ada
Authors: Drossopoulou S. , Uhl J. , Persch G. , Goos G. , Dausmann M. , Winterstein G. 
Published: November 2005

We describe the development of a formal specification of the static semantics of Ada in form of an attribute grammar. This specification is complete, and was tested extensively with automatically generated equivalent Pascal programs. From this specification we systematically developed the semantic analysis part of our Ada Compiler Front End. We outline the general proceeding when specifying semantic analysis with attribute grammars and then discuss to some extent examples about declaration elaboration and overloading resolution.
CR Categories and Subject Descriptors: D.3.1 [Programming Languages]: Formal definitions and Theory - semantics; D.3.4 [Programming Languages]: Processors - Translator writing systems and compiler generators; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages - algebraic approaches to semantics.