waashk/acm huggingface dataset:
faults on its sleeve: amplifying software reliability testing  most of the effort that goes into improving the quality of software paradoxically does not lead to quantitative, measurable quality. software developers and quality- assurance organizations spend a great deal of effort preventing, detecting, and removing "defects"\---parts of software responsible for operational failure. but software quality can be measured only by statistical parameters like hazard rate and mean time to failure, measures whose connection with defects and with the development process is little understood.  at the same time, direct reliability assessment by random testing of software is impractical. the levels we would like to achieve, on the order of 106 \\- 108 executions without failure, cannot be established in reasonable time. some limitations of reliability testing can be overcome but the "ultrareliable" region above 108 failure-free executions is likely to remain forever untestable.  we propose a new way of looking at the software reliability program. defect- based efforts should amplify the significance of reliability testing. that is, developers should demonstrate that the actual reliability is better than the measurement. we give an example of a simple reliability-amplification technique, and suggest applications to systematic testing and formal development methods.  dick hamlet jeff voas
software pipelining  utilizing parallelism at the instruction level is an important way to improve performance. because the time spent in loop execution dominates total execution time, a large body of optimizations focuses on decreasing the time to execute each iteration. software pipelining is a technique that reforms the loop so that a faster execution rate is realized. iterations are executed in overlapped fashion to increase parallelism.  let {abc}n represent a loop containing operations a, b, c that is executed n times. although the operations of a single iteration can be parallelized, more parallelism may be achieved if the entire loop is considered rather than a single iteration. the software pipelining transformation utilizes the fact that a loop {abc }n is equivalent to a{bca}n 1bc. although the operations contained in the loop do not change, the operations are from different iterations of the original loop.  various algorithms for software pipelining exist. a comparison of the alternative methods for software pipelining is presented. the relationships between the methods are explored and possibilities for improvement highlighted.  vicki h. allan reese b. jones randall m. lee stephen j. allan
debugging distributed programs using controlled re-execution  distributed programs are hard to write. a distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. this approach gives rise to a general problem, called predicate control problem, which takes a computation and a safety property specified on the computation, and outputs a controlled computation that maintains the property.  we define a class of global predicates, called region predicates, that can be controlled efficiently in a distributed computation. we prove that the synchronization generated by our algorithm is optimal. further, we introduce the notion of an admissible sequence of events and prove that it is equivalent to the notion of predicate control. we then give an efficient algorithm for the class of disjunctive predicates based on the notion of an admissible sequence.  neeraj mittal vijay k. garg
a programmer controlled approach to data and control abstraction  traditionally, data abstraction languages have only provided a means to extend the language "upward" to include new procedures and data types not present in the base language. this paper introduces a complementary approach, which also allows programmers to extend the language "downward" and thus to override many of the previously preempted decisions concerning the nature and implementation of various language constructs. in order to illustrate the approach, several extension examples are presented that involve control of decisions below the level of pascal-like languages. implementation of the programmer defined language constructs is also discussed and benchmark results are reported that show them comparable---and in many cases exceeding---in efficiency the corresponding built-in constructs of conventional languages.  juha heinänen
proposal for a monotonic multiple inheritance linearization  previous studies concerning multiple inheritance convinced us that a better analysis of conflict resolution mechanisms was necessary. in [dhhm92], we stated properties that a sound mechanism has to respect. among them, a monotonicity principle plays a critical role, ensuring that the inheritance mechanism behaves "naturally" relative to the incremental design of the inheritance hierarchy. we focus here on linearizations and present an intrinsically monotonic linearization, whereas currently used linearizations are not. this paper describes the algorithm in detail, explains the design choices, and compares it to other linearizations, with loops and clos taken as references. in particular, this new linearization extends clos and loops linearizations, producing the same results when these linearizations are sound.  r. ducournau m. habib m. huchard m. l. mugnier
data abstraction and hiding in fortran  few computing techniques have been as successful for software development as fortran's external procedure facilities. these may be viewed as a practical way to provide libraries of abstract operators for manipulating numeric and boolean, and in fortran 77 also character, data objects. the implementation details of such operators are hidden from, and are of no concern to, the user.  proposed fortran 8x allows programmers to define new data objects. intrinsic operations do not exist for programmer-defined objects, and procedural abstraction is the only mechanism for providing operations for such objects. thus implementation details of programmer-defined object operators may also be hidden from the user. moreover, data object definitions themselves may be made externally, and used without local redefinition. thus the implementation details of any data object may also be ignored by the user. fortran 8x therefore provides many of the features of data abstraction as well as procedural abstraction.  the proposed fortran 8x mechanisms for data object definition and external data libraries will be described, with examples of their use as data abstraction facilities.  jerrold l. wagener
higher-order abstract syntax  we describe motivation, design, use, and implementation of higher-order abstract syntax as a central representation for programs, formulas, rules, and other syntactic objects in program manipulation and other formal systems where matching and substitution or unification are central operations. higher-order abstract syntax incorporates name binding information in a uniform and language generic way. thus it acts as a powerful link integrating diverse tools in such formal environments. we have implemented higher-order abstract syntax, a supporting matching and unification algorithm, and some clients in common lisp in the framework of the ergo project at carnegie mellon university.  f. pfenning c. elliot
testing the correctness of tasking supervisors with tsl specifications  this paper describes the application of behavior specifications to the testing of tasking supervisors, an important component of an implementation of a concurrent programming language. the goal of such testing is to determine whether or not a tasking supervisor correctly implements the semantics of its associated language. we have tested a distributed tasking supervisor for the ada programming language by monitoring the execution behavior of ada tasking programs that have been compiled and linked with the supervisor. this behavior is checked for consistency with an event-based formalization of the ada tasking semantics expressed in the tsl specification language. the tsl runtime system automatically performs all monitoring and consistency checking at runtime. our approach improves upon other approaches to testing tasking supervisors, particularly the ada compiler validation capability (acvc), and also an approach described by klarund. in contrast with these other approaches, in our approach (1) we test only the behavior of the tasking supervisor, not the behavior of the test programs; and (2) any ada tasking program may be employed as test data, because the tsl specifications we construct describe the semantics of ada language statements, not the semantics of application programs.  d. rosenblum d. luckham
a documentation system, philosophy and implementation at the uab university computer center  the university computer center at the university of alabama at birmingham (uab/tucc) supports the primary administrative functions of the university, as well as some research and academic programs. a relatively small, specialized user services staff must provide assistance to several hundred users with widely varying needs. the traditional methods of maintaining documentation, which require dedicated people and resources to update and enter the information, are impossible to implement here given the size and makeup of the staff and the diversity of the user base. the solution to this problem has been the development of an on-line system, called usdr (user services documentation retrieval), which permits information in many forms (e.g., script output, tapes from vendors, word processing files) to be retrieved and printed, without the need to rekey or reformat documentation into a common form or location in the system. this paper will discuss the underlying concepts of usdr and an overview of the system which is actually run at uab/tucc.  landy manderson
generators and the replicator control structure in the parallel environment of alloy  the need for searching a space of solutions appears often. many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. serial programming languages typically support solutions of these problems by providing some form of generators or backtracking.  a parallel programming language is more demanding since it needs to be able to express parallel generation and processing of elements. failure driven computation is no longer sufficient and neither is multiple-assignment to generated values.  we describe the replicator control operator used in the high level parallel programming language alloy. the replicator control operator provides a new view of generators which deals with these problems.  thanasis mitsolides malcolm harrison
apl as a prototyping language: case study of a compiler development project  we are applying prototyping method using apl to a commercial compiler's development project.  this paper will discuss the following matters based on our one year experience of the project:  merits of apl as a prototyping language.  an environment of the prototype.  a representation of tables and the intermediate language of compilers in an apl environment.  a strategy of transforming the apl prototype into final product written in pascal.  evaluation of this method.  matsuki yoshino
locality, causality and continuations  concurrency and distribution are topics exacerbated by the omnipresence of internet. although many languages address these topics, few offer a real opportunity to control and coordinate widely spread dynamic computations. this paper presents such a language and its prominent features. besides explaining the software architecture of the implementation (based on objects and generic functions), it also presents an original coherency protocol for shared mutable variables.  we first recall, in section 1, the main features of our scheme-based, concurrent, distributed and computation-oriented language already presented in more details and examples in [qd93].  section 2 explains how to systematically implement a concurrent and distributed interpreter for that language, using a set of program transformations combining abstract continuation passing style (acps) and object-oriented lifting. the originality of this implementation is that it chiefly uses objects and generic functions in a style that allows to concentrate the problems related to concurrency and migration of computations into the sole discriminating behavior of generic functions. acps is not only used to reify continuations but also to enforce locality of computations in presence of distal objects.  in section 3, we propose a new (to our knowledge) protocol to manage shared mutable variables. this protocol enhances [msrn92], does not require atomic broadcast, tolerates short communication breakdowns and uses bounded circular clocks. this result comes from the use of a distributed gc (which allows us to maintain an approximation of global virtual time) and from the exploitation of causality as stated by continuations. to give a continuation a value (and a store) clearly expresses that the computations that are present in the continuation causally depend on the invoker of the continuation.  finally the computation- orientation of our language and mainly the ability to control groups of threads, concurrently running on multiple sites for the completion of the evaluation of a single expression, is shortly sketched in section 4.  as usual, related works and conclusions end this paper.  christian queinnec
a suite of www-based tools for advanced course management a collection of tools for creation of advanced and comprehensive course home pages is presented. the tools cover the spectrum from course overview pages and hypertext teaching materials to interactive services that support the teaching activities during the course. from the teacher's perspective the tools allow for abstraction from details and automation of routine work in the authoring process. seen from a student's perspective the comprehensive linking of course plans, teaching material, and interactive services provides for a valuable organization of a large body of information. kurt nørmark
evaluating the locality benefits of active messages  a major challenge in fine-grained computing is achieving locality without excessive scheduling overhead. we built two j-machine implementations of a fine-grained programming model, the berkeley threaded abstract machine. one implementation takes an active messages approach, maintaining a scheduling hierarchy in software in order to improve data cache performance. another approach relies on the j-machine's message queues and fast task switch, lowering the control costs at the expense of data locality. our analysis measures the costs and benefits of each approach, for a variety of programs and cache configurations. the active messages implementation is strongest when miss penalties are high and for the finest-grained programs. the hardware- buffered implementation is strongest in direct-mapped caches, where it achieves substantially better instruction cache performance.  ellen spertus william j. dally
synchronization primitives for a multiprocessor: a formal specification  formal specifications of operating system interfaces can be a useful part of their documentation. we illustrate this by documenting the threads synchronization primitives of the taos operating system. we start with an informal description, present a way to formally specify interfaces in concurrent systems, give a formal specification of the synchronization primitives, briefly discuss the implementation, and conclude with a discussion of what we have learned from using the specification for more than a year.  a. birrell j. guttag j. horning r. levin
performance evaluation of the orca shared-object system  orca is a portable, object-based distributed shared memory (dsm) system. this article studies and evaluates the design choices made in the orca system and compares orca with other dsms. the article gives a quantitative analysis of orca's coherence protocol (based on write-updates with function shipping), the totally ordered group communication protocol, the strategy for object placement, and the all-software, user-space architecture. performance measurements for 10 parallel applications illustrate the trade-offs made in the design of orca and show that essentially the right design decisions have been made. a write-update protocol with function shipping is effective for orca, especially since it is used in combination with techniques that avoid replicating objects that have a low read/write ratio. the overhead of totally ordered group communication on application performance is low. the orca system is able to make near-optimal decisions for object placement and replication. in addition, the article compares the performance of orca with that of a page- based dsm (treadmarks) and another object-based dsm (crl). it also analyzes the communication overhead of the dsms for several applications. all performance measurements are done on a 32-node pentium pro cluster with myrinet and fast ethernet networks. the results show that orca programs send fewer messages and less data than the treadmarks and crl programs and obtain better speedups.  henri e. bal raoul bhoedjang rutger hofman ceriel jacobs koen langendoen tim ruhl m. frans kaashoek
an efficient implementation scheme of concurrent object-oriented languages on stock multicomputers  several novel techniques for efficient implementtion of concurrent object- oriented languages on general purpose, stock multicomputers are presented. these techniques have been developed in implementing our concurrent object- oriented language abcl on a fujitsu laboratory's experimental multicomputer ap1000 consisting of 512 sparc chips. the propsed intra-node scheduling mechanism reduces the cost of local message passing. the cost of intra-node asynchronous message passing is about 20 sparc instructions in the bst case, including locality checking, dynamic method lookup, and scheduling. the minimum latency of asynchronous internode message passing is about 9μs, or about 120 instructions, employing the self- dispatching mechanism independently proposed by eicken et al. a large scale benchmark which involves 9,000,000 message passings shows 440 times speedup on the 512 nodes system compared to the sequential version of the same algorithm. we rely on simple hardware support for message passing and use no specialized architectural supports for object-oriented computing. thus, we are able to enjoy the benefits of future progress in standard processor technology. our result shows that concurrent object-oriented languages can be implemented efficiently on conventional multicomputers.  kenjiro taura satoshi matsuoka akinori yonezawa
checking progress with action priority: is it fair?  the liveness characteristics of a system are intimately related to the notion of fairness. however, the task of explicitly modelling fairness constraints is complicated in practice. to address this issue, we propose to check lts (labelled transition system) models under a strong fairness assumption, which can be relaxed with the use of action priority. the combination of the two provides a novel and practical way of dealing with fairness. the approach is presented in the context of a class of liveness properties termed progress, for which it yields an efficient model- checking algorithm. progress properties cover a wide range of interesting properties of systems, while presenting a clear intuitive meaning to users.  dimitra giannakopoulou jeff magee jeff kramer
the charrette ada compiler  the charrette ada compiler is a working compiler for a substantial subset of the preliminary ada language. the ada source program is translated into an equivalent program in an intermediate implementation language. the result of the compilation process is machine language generated for this intermediate program.  this paper provides a brief overview of the compiler with special attention given to the primary translation phase. emphasis is placed on the transformation of ada type and subtype information and the representation of objects. the translation of several interesting statement and expression forms is also outlined.  jonathan rosenberg david alex lamb andy hisgen mark sherman
editing apl objects with cms xedit  the vm/sp system editor xedit is used to edit apl objects. two approaches are possible: with an apl function, or with an exec written in rexx (the new vm/sp system interpreter). the advantages of the latter are that nothing need be copied into the user's workspace, and that apl code can be executed from xedit, and xedit commands from apl. no new auxiliary processor is needed. the technique is in use at ibm yorktown.  norman brenner
managing reentrant structures using reference counts  automatic storage management requires that one identify storage unreachable by a user's program and return it to free status. one technique maintains a count of the references from user's programs to each cell, since a count of zero implies the storage is unreachable. reentrant structures are self-referencing; hence no cell in them will have a count of zero, even though the entire structure is unreachable. a modification of standard reference counting can be used to manaage the deallocation of a large class of frequently used reentrant structures, including two-way and circularly linked lists.  all the cells of a potentially reentrant structure are considered as part of a single group for deallocation purposes. information associated with each cell specifies its group membership. internal references (pointers from one cell of the group to another) are not reference counted. external references to any cell of this group are counted as references to the group as a whole. when the external reference count goes to zero, all the cells of the group can be deallocated. this paper describes several ways of specifying group membership, properties of each implementation, and properties of mutable and immutable group membership.  daniel g. bobrow
automatic isolation of compiler errors  this paper describes a tool called vpoiso that was developed to isolate errors automatically in the vpo compiler system. the two general types of compiler errors isolated by this tool are optimization and nonoptimization errors. when isolating optimization errors, vpoiso relies on the vpo optimizer to identify sequences of changes, referred to as transformations, that result in semantically equivalent code and to provide the ability to stop performing improving (or unnecessary) transformations after a specified number have been performed. a compilation of a typical program by vpo often results in thousands of improving transformations being performed. the vpoiso tool can automatically isolate the first improving transformation that causes incorrect output of the execution of the compiled programs by using a binary search that varies the number of improving transformation performed. not only is the illegal transformation automatically isolated, but vpoiso also identifies the location and instant the transformation is performed in vpo. nonoptimization errors occur from problems in the front end, code generator, and necessary transformations in the optimizer. if another compiler is available that can produce correct (but perhaps more inefficient) code, then vpoiso can isolate nonoptimization errors to a single function. automatic isolation of compiler errors facilitates retargeting a compiler to a new machine, maintenance of the compiler, and supporting experimentation with new optimizations.  david b. whalley