bluuebunny/crossref_metadata_2025_split huggingface dataset:
Automated generation of testcase datasets
Authors: Miller E. F. , Melton R. A. 
Published: November 2005

Software quality enhancement can be achieved in the near term through use of a systematic program testing methodology. The methodology attempts to relate functional software testcases with formal software specifications as a means to achieve correspondence between the software and its specifications. To do this requires generation of appropriate testcase data.

Automatic testcase generation is based on
a priori
knowledge of two forms of internal structure information: a representation of the tree of subschema automatically identified from within each program text, and a representation of the iteration structure of each subschema. This partition of a large program allows for efficient and effective automatic testcase generation using straightforward backtracking techniques.

During backtracking a number of simplifying, consolidating, and consistency analyses are applied. The result is either (1) early recognition of the impossibility of a particular program flow, or (2) efficient generation of input variable specifications which cause the testcase to traverse each portion of the required program flow.
A number of machine output examples of the backtracking facility are given, and the general effectiveness of the entire process is discussed.
New assertion concepts for self-metric software validation
Authors: Stucki Leon G. , Foshee Gary L. 
Published: November 2005

Automated tools and structured programming techniques are in use on a variety of scientific and business application programming projects within the McDonnell Douglas Corporation. An examination of the resulting programs reveals certain development and maintenance characteristics that suggest new and very interesting applications for automated tools.
An extension of PET (a currently operational McDonnell Douglas validation tool for FORTRAN) to include a user embedded assertion capability offers a step in the direction of automatically verifying the dynamic execution of programs. A user-oriented local and global assertion capability is introduced and its implementation is discussed.
Application of these tools within a well-conceived structured programming environment offers a positive step forward in the development of more reliable software systems.
Some experience with automated aids to the design of large-scale reliable software
Authors: Boehm B. W. , McClean R. K. , Urfrig D. B. 
Published: November 2005

This paper summarizes some recent experience in analyzing and eliminating sources of error in the design phase of large software projects. It begins by pointing out some of the significant differences in software error incidence between large and small software projects. The most striking contrast, illustrated by project data, is the large preponderance of design errors over coding errors on large-scale projects, not only with respect to numbers of errors, but also with respect to the relative time and effort required to detect them and correct them.
The paper next presents a taxonomy of software error causes, and some analyses of the design error data, performed to obtain a better understanding of the nature of large-scale software design errors and to evaluate alternative methods of preventing, detecting, and eliminating them.
Based on this analysis of observational data, a hypothesis was derived regarding the potential cost-effectiveness of an automated aid to detecting inconsistencies between assertions about the nature of inputs and outputs of the various elements (functions, modules, data bases, data sources, etc.) of the software design. This hypothesis was tested by developing a prototype version of such an aid, the Design Assertion Consistency Checker (DACC), using TRW's Generalized Information Management (GIM) system, and using it on a large-scale software project with 186 elements and 967 assertions about their inputs and outputs.
Of the 121,000 possible mismatches between input and output assertions, DACC found 818, at a cost in computer time of $30. Most of the mismatches resulted from shortfalls in the initial version of DACC or the initial data preparation, such as a lack of a synonym capability and a lack of a explicit statements about external inputs and outputs. However, a number of serious mismatches were exposed at a time when they were easy to correct, and a most useful work-list generated of items needing resolution before allowing the design effort to proceed to further detail.
In general, the data confirmed the hypothesis about the general utility of a DACC capability for large software projects. However, a number of additional features should be considered to compensate for current deficiencies (in areas such as manuscript preparation) and to fully take advantage of having the software design in machine-readable form.
The purpose of concurrent Pascal
Authors: Hansen Per Brinch 
Published: November 2005

This is the first of three papers that describe a new programming language for structured programming of computer operating systems [1, 2, 3]. It extends the sequential programming language Pascal with concurrent programming tools called processes and monitors. These concepts are explained informally by means of pictures that illustrate a hierarchical design of a simple spooling system. The main contribution of Concurrent Pascal is to extend the monitor concept with an explicit hierarchy of access rights to shared data structures that can be stated in the program text and checked by a compiler.
[1]Brinch Hansen, P. The purpose of Concurrent Pascal. Information Science, California Institute of Technology, November 1974.
[2]Brinch Hansen, P. The use of Concurrent Pascal. Information Science, California Institute of Technology, November 1974.
[3]Brinch Hansen, P. Job control in Concurrent Pascal. Information Science, California Institute of Technology. November 1974.
The effect of certain modular design principles on testability
Authors: Edwards N. P. 
Published: November 2005

This paper is a nonprogrammers view of design principles which are considered essential to testability of complex structures. The principles are related to the programming problem.
The basic problems in verifying the function of any complex structure derive from: inadequate specification of function, the very large number of possible structures (most of which are “mistakes”) and the very large number of possible outputs for specified and unspecified inputs.
Present trends in programming techniques are towards various forms of controlled modularity. If modularity is controlled so that the function of a module is independent of the source of its input, the destination of its output, and the past history of use of the module, the difficulty of testing the modules and structures assembled from the modules is greatly reduced. Multilevel modularity also powerfully reduces the complexity of modules and structures. Controlled modularity requires that the separation of certain variables be rigorously maintained. Controlled branching also reduces complexity and testing requirements. These are examined with mathematical examples and it is concluded that if the proper principles of controlled modularity are observed, it should be technically feasible to design software to achieve specified function and that under certain conditions it should be economically feasible to test software so designed to practical levels of accuracy and reliability.
Contract Soundness for object-oriented languages
Authors: Findler Robert Bruce , Felleisen Matthias 
Published: November 2005

Checking pre- and post-conditions of procedures and methods at runtime helps improve software reliability. In the procedural world, pre- and post-conditions have a straightforward interpretation. If a procedure's pre-condition doesn't hold, the caller failed to establish the proper context. If a post-condition doesn't hold, the caller failed to establish the proper context. If a post-condition doesn't hold, the procedure failed to compute the expected result.
In the object-oriented world, checking pre- and post-conditions for methods, often called contracts in this context, poses complex problems. Because methods may be overridden, it is not sufficient to check only pre- and post-conditions. In addition, the contract hierarchy must be checked to ensure that the contracts on overridden methods are properly related to the contracts on overriding methods. Otherwise, a class hierarchy may violate the substitution principle, that is, it may no longer be true that an instance of a class is substitutable for objects of the super-class.
In this paper, we study the problem of contract enforcement in an object-oriented world from a foundational perspective. More specifically, we study contracts as refinements of types. Pushing the analogy further, we state and prove a contract soundness theorem that captures the essential properties of contract enforcement. We use the theorem to illustrate how most existing tools suffer from a fundamental flaw and how they can be improved.
How to invent distributed implementation schemes of an object-based concurrent language: a transformational approach
Authors: Shibayama Etsuya 
Published: November 2005

A design and verification technique for implementation schemes of distributed software is presented. In this technique, first, the specification is modelled by a concurrent object system, that is, one which is constituted of computational agents with capability of concurrent execution and message passing. Then, such a concurrent object system is transformed into another concurrent object system, which models a sophisticated implementation scheme.
Our transformation technique is mainly based on fusing and splitting concurrent objects. The correctness of transformation rules can be proven formally.
Non-intrusive and interactive profiling in parasight
Authors: Aral Ziya , Gertner Ilya 
Published: November 2005

Debugging the performance of parallel applications is crucial for fully utilizing the potential of multiprocessor hardware. This paper describes profiling tools in Parasight, a programming environment that is geared towards non-intrusive performance analysis and high-level debugging. In Parasight, profilers execute as observer programs which run concurrently with the target program and monitor its behavior. This design grew out of our experience in debugging and monitoring the performance of real parallel programs.
Parasight is used to implement an interactive profiler based on gprof, a standard UNIX profiling tool. The new profiler is an interactive tool that is dynamically controlled by the programmer and can run concurrently with the target program. It is also less intrusive than the original. This was achieved in part by off-loading the profile gathering computations to an adjacent processor and in part by allowing selective profiling.
In conjunction with the new profiler, Parasight is used to implement high-level custom profiling routines that may be inserted at arbitrary locations in a target program to measure user-defined abstractions. One outcome has been to develop the beginnings of a profiling methodology in which high-level performance problems are detected through a function profiler and detailed performance bottlenecks are analyzed with custom profiling routines.
Parasight, the new profiler and their associated tools have been implemented on the Encore Multimax, a shared-memory multiprocessor running UNIX. They have been used to profile both parallel and sequential programs.
Applications experience with Linda
Authors: Carriero Nicholas , Gelernter David 
Published: November 2005

We describe three experiments using C-Linda to write parallel codes. The first involves assessing the similarity of DNA sequences. The results demonstrate Linda's flexibility—Linda solutions are presented that work well at two quite different levels of granularity. The second uses a prime finder to illustrate a class of algorithms that do not (easily) submit to automatic parallelizers, but can be parallelized in straight-forward fashion using C-Linda. The final experiment describes the process lattice model, an “inherently” parallel application that is naturally conceived as multiple interacting processes. Taken together, the experience described here bolsters our claim that Linda can bridge the gap between the growing collection of parallel hardware and users eager to exploit parallelism.
This work is supported by the NSF under grants DCR-8601920 and DCR-8657615 and by the ONR under grant N00014-86-K-0310. We are grateful to Argonne National Labs for providing access to a Sequent Symmetry.
Extending the operating system to support an object-oriented environment
Authors: Marques J. A. , Guedes P. 
Published: November 2005

Comandos is a project within the European Strategic Programme for Research on Information Technology -
ESPRIT
and it stems from the identified need of providing simpler and more integrated environments for application development in large distributed systems.

The fundamental goal of the project is the definition of an integrated platform providing support for distributed and concurrent processing in a LAN environment, extensible and distributed data management and tools for monitoring and administrating the distributed environment.
An object oriented approach was used as the ground level for the integration of the multidisciplinary concepts addressed in the project.
This paper starts by describing the basic model and architecture of Comandos, which results from a common effort by all the partners in the project. We focus then on the description of a first prototype of the system, which implements a subset of the architecture and is currently running on a set of personal computers and workstations at INESC. The prototype is a testbed for the architecture, providing dynamic linking, access to persistent objects and transparent distribution. Special attention is given to the performance aspects of object invocation in virtual memory.
An object-oriented modelling enviornment
Authors: Page T. W. , Berson S. , Cheng W. , Muntz R. R. 
Published: November 2005

Many tools and techniques exist for the modeling and analysis of computer and communication systems. These tools are often complex and tailored to a narrow range of problems. The system analysis task often requires coordinated use of multiple tools and techniques which is not supported by currently available systems. The Tangram project goal is to develop an environment which makes a large set of tools and techniques readily accessible and is easily tailored to specialized applications.
This system has been prototyped in an object-oriented extension to Prolog. The impact that these two paradigms, logic and objects, have had on the design is discussed. Several example applications are presented to illustrate the extensibility of the system.
An environment for literate Smalltalk programming
Authors: Reenskaug T. , Skaar A. L. 
Published: November 2005

The programming environment described in this paper is an adaptation of Donald Knuth's concept of literate programming, applied to Smalltalk programs. The environment provides a multi-media document production system including media for Smalltalk class and method definitions.
There are two outputs from the system. The first output is a document which contains general descriptions and discussions intermixed with precise definitions of program fragments, test inputs and test results. The second output consists of compiled Smalltalk programs installed and ready for execution.
The main idea was to produce program documentation that was just as interesting and fascinating to read as ordinary literature. Our experience showed an added benefit, namely that the literate programming environment was an active aid in the problem solving process. The simultaneous programming and documentation lead to significantly improved quality of both programs and documentation.
Extending ordinary inheritance schemes to include generalization
Authors: Pedersen C. H. 
Published: November 2005

The arrangement of classes in a specialization hierarchy has proved to be a useful abstraction mechanism in class-based object oriented programming languages. The success of the mechanism is based on the high degree of code reuse that is offered, along with simple type conformance rules.
The opposite of specialization is generalization. We will argue that support of generalization in addition to specialization will improve class reusability. A language that only supports specialization requires the class hierarchy to be constructed in a top down fashion. Support for generalization will make it possible to create super-classes for already existing classes, hereby enabling exclusion of methods and creation of classes that describe commonalties among already existing ones.
We will show how generalization can coexist with specialization in class-based object oriented programming languages. Furthermore, we will verify that this can be achieved without changing the simple conformance rules or introducing new problems with name conflicts.
VLIW compilation techniques in a superscalar environment
Authors: Ebcioglu Kemal , Groves Randy D. , Kim Ki-Chang , Silberman Gabriel M. , Ziv Isaac 
Published: November 2005

We describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. The algorithms, based on novel parallelization techniques for
Very Long Instruction Word (VLIW)
architectures, find and place together independently executable operations that may be far apart in the original code. i.e., they may be separated by many conditional branches or belong to different iterations of a loop. As a result, the functional units in the superscalar are presented with more work that can proceed in parallel, thus achieving higher performance than the approach of using hardware instruction dispatch techniques alone.

While general scheduling techniques improve performance by removing idle pipeline cycles, to further improve performance on a superscalar with only a few functional units requires a reduction in the pathlength. We have designed a set of new algorithms for reducing pathlength and removing stalls due to branches, namely speculative load-store motion out of loops, unspeculation, limited combining, basic block expansion, and prolog tailoring. These algorithms were implemented in a prototype version of the IBM RS/6000 xlc compiler and have shown significant improvement in SPEC integer benchmarks on the IBM POWER machines.
Also, we describe a new technique to obtain profiling information with low overhead, and some applications of profiling directed feedback, including scheduling heuristics, code reordering and branch reversal.
ATOM
Authors: Srivastava Amitabh , Eustace Alan 
Published: November 2005

ATOM (Analysis Tools with OM) is a single framework for building a wide range of customized program analysis tools. It provides the common infrastructure present in all code-instrumenting tools; this is the difficult and time-consuming part. The user simply defines the tool-specific details in instrumentation and analysis routines. Building a basic block counting tool like Pixie with ATOM requires only a page of code.
ATOM, using OM link-time technology, organizes the final executable such that the application program and user's analysis routines run in the same address space. Information is directly passed from the application program to the analysis routines through simple procedure calls instead of inter-process communication or files on disk. ATOM takes care that analysis routines do not interfere with the program's execution, and precise information about the program is presented to the analysis routines at all times. ATOM uses no simulation or interpretation.
ATOM has been implemented on the Alpha AXP under OSF/1. It is efficient and has been used to build a diverse set of tools for basic block counting, profiling, dynamic memory recording, instruction and data cache simulation, pipeline simulation, evaluating branch prediction, and instruction scheduling.
Cache performance of garbage-collected programs
Authors: Reinhold Mark B. 
Published: November 2005

As processor speeds continue to improve relative to main-memory access times, cache performance is becoming an increasingly important component of program performance. Prior work on the cache performance of garbage-collected programs either argues or assumes that conventional garbage-collection methods will yield poor performance, and has therefore concentrated on new collection algorithms designed specifically to improve cache-level reference locality.
This paper argues to the contrary: Many programs written in garbage-collected languages are naturally well-suited to the direct-mapped caches typically found in modern computer systems. Garbage-collected programs written in a mostly-functional style should perform well when simple linear storage allocation and an infrequently-run generational compacting collector are employed; sophisticated collectors intended to improve cache performance are unlikely to be necessary. As locality becomes ever more important to program performance, programs of this kind may turn out to have a significant performance advantage over programs written in traditional languages.
A general data dependence test for dynamic, pointer-based data structures
Authors: Hummel Joseph , Hendren Laurie J. , Nicolau Alexandru 
Published: November 2005

Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations.
In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.
Context-sensitive interprocedural points-to analysis in the presence of function pointers
Authors: Emami Maryam , Ghiya Rakesh , Hendren Laurie J. 
Published: November 2005

This paper reports on the design, implementation, and empirical results of a new method for dealing with the aliasing problem in C. The method is based on approximating the points-to relationships between accessible stack locations, and can be used to generate alias pairs, or used directly for other analyses and transformations.
Our method provides context-sensitive interprocedural information based on analysis over invocation graphs that capture all calling contexts including recursive and mutually-recursive calling contexts. Furthermore, the method allows the smooth integration for handling general function pointers in C.
We illustrate the effectiveness of the method with empirical results from an implementation in the McCAT optimizing/parallelizing C compiler.