waashk/acm huggingface dataset:
rs-fdra: a register sensitive software pipelining algorithm for embedded vliw processors  the paper proposes a novel software-pipelining algorithm, _register sensitive force directed retiming algorithm (rs- fdra)_, suitable for optimizing compilers targeting embedded vliw processors. the key difference between rs- fdra and previous approaches is that our algorithm can handle _code size constraints_ along with latency and resource constraints. this capability enables the exploration of pareto "optimal" points with respect to _code size_ and _performance_. rs-fdra can also minimize the increase in "_register pressure_" typically incurred by software pipelining. this ability is critical since, the need to insert spill code may result in significant performance degradation. extensive experimental results are presented demonstrating that the extended set of optimization goals and constraints supported by rs-fdra enables a thorough compiler-assisted exploration of trade-offs among performance, code size, and register requirements, for time critical segments of embedded software components.  cagdas akturan margarida f. jacome
conservative garbage collection for general memory allocators  this paper explains a technique that integrates conservative garbage collection on top of general memory allocators. this is possible by using two data structures named malloc-tables and jump-tables that are computed at garbage collection time to map pointers to beginning of objects and their sizes. this paper describes malloc-tables and jump-tables, an implementation of a malloc/jump-table based conservative garbage collector for doug lea's memory allocator, and experimental results that compare this implementation with boehm-demers-weiser gc, a state-of-the-art conservative garbage collector.  gustavo rodriguez-rivera
introduction to special section on software testing  the field of software testing spans mathematical theory, the art and practice of validation, and methodology of software development. to cover this range would require a textbook (or several texts), not a trio of articles. but the work presented in this special section is a kind of "test set." each paper is a significant contribution within one of the three broad areas. the reader must now make the assessment that is critical to any review of test points: are they representative? my own answer is 'no'; these articles are provocative and revealing rather than routine summaries. and perhaps that is what software testing is all about: good tests are the ones that provide new insights, not the ones that cover well worn ground.  r. hamlet
embedded uml: a merger of real-time uml and co-design  in this paper, we present a proposal for a uml profile called `embedded uml'. embedded uml represents a synthesis of various ideas in the real-time uml community, and concepts drawn from the hardware-software co-design field. embedded uml first selects from among the competing real-time uml proposals, the set of ideas which best allow specification and analysis of mixed hw-sw systems. it then adds the necessary concept of underlying deployment architecture that uml currently lacks in complete form, using the notion of an embedded hw-sw `platform'. it supplements this with the concept of a `mapping', which is a platform-dependent refinement mechanism that allows efficient generation of an optimised implementation of the executable specification in both hw and sw. finally, it provides an approach which supports the development of automated analysis, simulation, synthesis and code generation tool capabilities which can be provided for design usage even while the embedded uml standardisation process takes place.  grant martin luciano lavagno jean louis-guerin
the pan language-based editing system  powerful editing systems for developing complex software documents are difficult to engineer. besides requiring efficient incremental algorithms and complex data structures, such editors must accommodate flexible editing styles, provide a consistent, coherent, and powerful user interface, support individual variations and projectwide configurations, maintain a sharable database of information concerning the documents being edited, and integrate smoothly with the other tools in the environment. pan is a language-based editing and browsing system that exhibits these characteristics. this paper surveys the design and engineering of pan, paying particular attention to a number of issues that pervade the system: incremental checking and analysis, information retention in the presence of change, tolerance for errors and anomalies, and extension facilities.  robert a. ballance susan l. graham michael l. van de vanter
a case-tool for supporting navigation in the class hierarchy the central role that class hierarchy plays in object-oriented systems is discussed. the study focuses on design and maintenance stages where the requirements of navigation facilities are greater than at other stages of the systems lifecycle. it will be shown that different kinds of navigation are needed and it is necessary to browse up and down the class hierarchy before it is possible to decide which classes have to be changed. a flexible navigation tool which can support these design and maintenance stages is also presented. the tool helps the designer to navigate the class hierarchy and to investigate the effect of the intended changes on the entire class hierarchy. a. putkonen m. kiekara
step development tools: metastep language system  step development tools (sdt) is a general-purpose microprogram development system. the metastep language system is composed of four tools of the sdt needed to write microprograms: a definition processor, a retargetable assembler, a retargetable cross-assembler, and a relocatable linker.  these tools are of commercial quality, providing complete languages, quality diagnostics, full interface to other support tools, and high performance. the language system supports microcode debug by providing complete run-time information and by interacting directly with other debug tools provided in sdt.  d. l. wilburn s. schleimer
a truly generative semantics-directed compiler generator  this paper describes semantic processing in the compiler generating system mug2. mug2 accepts high-level descriptions of the semantics of a programming language including full runtime semantics, data flow analysis, and optimizing transformations. this distinguishes mug2 from systems such as yacc [joh75], hlp [hlp78], pqcc [pqc79], or its own former version [grw77] with respect to expressive power and convenience. in this respect, mug2 comes close to semantics-directed systems such as [mos76], [jos80], [set81], [pau82]. in contrast to these, mug2 is not a universal translator system where program independent semantic properties have to be evaluated at compilation time. the description concepts of mug2 allow a far reaching separation of language vs. program dependent semantics, thus constituting a truly generative approach to semantics-directed compiler generation.  harald ganzinger robert giegerich ulrich möncke reinhard wilhelm
a technique for the architectural implementation of software subsystems  this paper presents a technique to implement operating system software more efficiently: as part of the processor architecture. such an'architectural'implementation has two significant advantages over a conventional'software'implementation. first, it allows performance critical modules of the operating system to be implemented through specialized hardware or firmware. second, it allows the implementation of the operating system to evolve with technology without any change to the basic design structure. the basis for the proposed technique is the application of a software structuring methodology called'type extension'. a model for the architectural implementation of a subsystem, which is structured through this methodology, is presented. it is shown that this model encompasses all conventional forms of implementation--- hardware, firmware, software. the model establishes that architectural implementation allows a range of implementation choices; a software implementation utilizes only a small subset of these choices.  anand jagannathan
some experimental estimators for developmental and delivered errors in software development projects  experimental estimators are presented relating the expected number of software problem reports (b) in a software development project to  the overall reported professional effort (e) in "man months"  the number of subprograms (n)  the overall count of thousands of coded source statements of software(s).  [equation]  these estimators are shown to be consistent with data obtained from the air force's rome air development center, the naval research laboratory, and japan's fujitsu corporation. although the results are promising, more data is needed to support the validity of these estimators.  victor schneider
type extensions  software systems represent a hierarchy of modules. client modules contain sets of procedures that extend the capabilities of imported modules. this concept of extension is here applied to data types. extended types are related to their ancestor in terms of a hierarchy. variables of an extended type are compatible with variables of the ancestor type. this scheme is expressed by three language constructs only: the declaration of extended record types, the type test, and the type guard. the facility of extended types, which closely resembles the class concept, is defined in rigorous and concise terms, and an efficient implementation is presented.  n. wirth
application of axiomatic methods to a specification analyser  the goal of this paper was to model a specification language and its analyser using axiomatic methods derived from those applied previously to abstract data type and state transition specifications. the models attempt to cover many interesting features of psl/psa, a widely used specification language and analyser for information systems. simple properties expected to hold for actual psl/psa were formalized and proved about some models, with assumptions about undefined parts. both model formulation and property proofs were performed within the affirm specification and verification system. the results show (1) the applicability of axiomatic methods for modeling a new kind of software system, (2) insights into the psl/psa class of specification system, (3) a possible route for formal definition of such analysers, and (4) additional lessons on the art of specification, modeling, verification, and validation.  susan l. gerhart
cryptographic sealing for information secrecy and authentication  the problem of computer security can be considered to consist of four distinct components: secrecy (ensuring that information is only disclosed to authorized users), authentication (ensuring that information is not forged), integrity (ensuring that information is not destroyed), and availability (ensuring that access to information can not be maliciously interrupted).  the paper describes a new protection mechanism called cryptographic sealing that provides primitives for secrecy and authentication. the mechanism is enforced with a synthesis of classical cryptography, public-key cryptography, and a threshold scheme.  david k. gifford
software reliability modeling (tutorial)  there are a number of views as to what software reliability is and how it should be quantified. some people believe that this measure should be binary in nature so that an imperfect program would have zero reliability while a perfect one would have a reliability value of one. this view parallels that of program proving whereby the program is either correct or incorrect. others, however, feel that software reliability should be defined as the relative frequency of the times that the program works as intended by the user. this view is similar to that taken in testing where a percentage of the successful ewes is used as a measure of program quality. according to the latter viewpoint, software reliability is a probabilistic measure and can be defined as follows:  let f be a class of faults, defined arbitrarily, and t be a measure of relevant time, the units of which are dictated by the application at hand. then the reliability of the software package with respect to the class of faults f and with respect to the metric t, is the probability that no fault of the class occurs during the execution of the program for a prespecified period of relevant time.  a number of models have been proposed during the past fifteen years to estimate software reliability and several other performance measures. these are based mainly on the failure history of software and can be classified according to the nature of the failure process studied as indicated below.  times between failures models: in this class of models the process under study is the time between failures. the most common approach is to assume that the time between, say, the (i-1)st and ith failures, follows a distribution whose parameters depend on the number of faults remaining in the program during this interval.  failure count models: the interest of this class of models is in the number of faults or failures in specified time intervals rather than in times between failures. the failure counts are assumed to follow a known stochastic process with a time dependent discrete or continuous failure rate.  fault seeding models: the basic approach in this class of models is to "seed" a known number of faults in a program which is assumed to have an unknown number of indigenous faults.  input domain based models: the basic approach taken here is to generate a set of test cases from an input distribution which is assumed to be representative of the operational usage of the program. because of the difficulty in obtaining this distribution, the input domain is partitioned into a set of equivalence classes, each of which is usually associated with a program path.  in this tutorial we discuss the key models from the above classes and the related issues of parametric estimation, unification of models, bayesian interpretation, validation and comparison of models, and determination of optimum release time.  amrit l. goel
deciding when to forget in the elephant file system modern file systems associate the deletion of a file with the immediate release of storage, and file writes with the irrevocable change of file contents. we argue that this behavior is a relic of the past, when disk storage was a scarce resource. today, large cheap disks make it possible for the file system to protect valuable data from accidental delete or overwrite.this paper describes the design, implementation, and performance of the elephant file system, which automatically retains all important versions of user files. users name previous file versions by combining a traditional pathname with a time when the desired version of a file or directory existed. storage in elephant is managed by the system using file-grain user-specified retention policies. this approach contrasts with checkpointing file systems such as plan-9, afs, and wafl that periodically generate efficient checkpoints of entire file systems and thus restrict retention to be guided by a single policy for all files within that file system.elephant is implemented as a new virtual file system in the freebsd kernel. douglas s. santry michael j. feeley norman c. hutchinson alistair c. veitch ross w. carton jacob ofir
task time lines as a debugging tool debugging distributed programs is more difficult than debugging sequential ones. this paper describes a means of making this easier by presenting the user with a "time line" view of an ada program. each time line shows the successive states of an ada task as easily recognisable symbols on a time axis. communication and sychronisation between tasks is shown graphically by lines connecting the time lines. the paper shows how this representation can be used to depict typical ada tasking activity, and describes a tool that provides a useful interface to the representation. j. s. briggs s. d. jamieson g. w. randall i. c. wand
virtual classes: a powerful mechanism in object-oriented programming  the notions of class, subclass and virtual procedure are fairly well understood and recognized as some of the key concepts in object-oriented programming. the possibility of modifying a virtual procedure in a subclass is a powerful technique for specializing the general properties of the superclass.  in most object-oriented languages, the attributes of an object may be references to objects and (virtual) procedures. in simula and beta it is also possible to have class attributes. the power of class attributes has not yet been widely recognized. in beta a class may also have virtual class attributes. this makes it possible to defer part of the specification of a class attribute to a subclass. in this sense virtual classes are analogous to virtual procedures. virtual classes are mainly interesting within strongly typed languages where they provide a mechanism for defining general parameterized classes such as set, vector and list. in this sense they provide an alternative to generics.  although the notion of virtual class originates from beta, it is presented as a general language mechanism.  o. l. madsen b. moller-pedersen
structure exits, not loops until recently, pascal was the first programming language taught to students. as more schools choose ada or c++ as a first language, the debate on structured programming has been reopened ([rob95]). we are no longer restricted to the while-statement: exit/break-statements can be used to exit a loop from the middle, and return from a procedure or function is allowed within a loop statement. do these constructs violate the principle of structure programming? this article claims that more general loop constructs can be objectively justified, because they simplify the verification of programs. a program that is simple to verify is also easy to explain and understand. mordechai ben-ari
improving the accuracy of petri net-based analysis of concurrent programs spurious results are an inherent problem of most static analysis methods. these methods, in an effort to produce conservative results, overestimate the executable behavior of a program. infeasible paths and imprecise alias resolution are the two causes of such inaccuracies. in this paper we present an approach for improving the accuracy of petri net-based analysis of concurrent programs by including additional program state information in the petri net. we present empirical results that demonstrate the improvements in accuracy and, in some cases, the reduction in the search space that result from applying this approach to concurrent ada programs. a. t. chamillard lori a. clarke
a simple technique for handling multiple polymorphism  certain situations arise in programming that lead to multiply polymorphic expressions, that is, expressions in which several terms may each be of variable type. in such situations, conventional object-oriented programming practice breaks down, leading to code which is not properly modular. this paper describes a simple approach to such problems which preserves all the benefits of good object-oriented programming style in the face of any degree of polymorphism. an example is given in smalltalk-80 syntax, but the technique is relevant to all object-oriented languages.  daniel h. h. ingalls
memory management support for tiled array organization (abstract)  a novel method is described which adds support for sub-array ordered (tiled) arrays to a conventional mmu. the resulting pages contain two dimensional tiles of data rather than one dimensional strips, making tiled virtual memory transparently available to general purpose application programs. the method is further extended to support sub-arrays with three or more dimensions. the image mmu of the kodak prophecy color publishing system is shown as a product implementation for color picture arrays.  gary newman
distributed ada: a suggested solution for ada 9x  this paper contains a suggested solution to the problems of implementing ada in non-shared memory distributed systems for incorporation into ada9x. the solution is based on three fundamental principles: firstly that there should be minimal disturbance to the existing ada language definition; secondly that the security aspects of the language are not compromised; and thirdly that the requirements of implementors of distributed systems be met in full.  b. dobbing
documentation testing one definition of documentation is 'any written or pictorial information describing, defining, specifying, reporting, or certifying activities, requirements, procedures, or results.' (1). documentation is as important to a product's success as the product itself. if the documentation is poor, non-existent, or wrong, it reflects on the quality of the product and the vendor.at the bell atlantic systems integration & testing center documentation testing is an important function that receives as much attention as the testing of software and hardware. because the bell atlantic systems integration & testing center is iso9001 certified, an enormous effort was undertaken to ensure quality assurance of all products including documentation. both a test procedure and test plan for documentation has been implemented to ensure this quality.this article will describe what documentation is, why document testing is important, and how document testing is performed at the bell atlantic systems integration & testing center.other information pertaining to documentation, such as human factors, how to achieve document comprehensiveness, and comprehensibility, although important, are beyond the reach of this report. salvatore mamone
the universe model: an approach for improving the modularity and reliability of concurrent programs  we present the universe model, a new approach to concurrency management that isolates concurrency concerns and represents them in the modular interface of a component. this approach improves program comprehension, module composition, and reliability for concurrent systems. the model is founded on designer- specified invariant properties, which declare a component's dependencies on other concurrent components. process scheduling is then automatically derived from these invariants. we illustrate the advantages of this approach by applying it to a real-world example.  reimer behrends r. e. kurt stirewalt
apl as the foundation for a universal computer language  some ways in which universal computer languages differ from those in common use today. universal dictionary. universal alphabet. universal character representation. universal keyboard. universal communication among computer systems. elimination of an operating system as a separate entity.  some advantages of universal computer languages over those in common use today. easier to teach and to learn. easier and faster creation and modification of software. faster execution. easier transfer of software from one system to another. fewer application software packages required.  some of the changes and additions required to make apl an acceptable universal computer language. implement the apl interpreter at the chip level. add language features to meet operating system requirements. eliminate the features now required to communicate with operating systems of the present kind. improve communication among users of a system. improve the handling of integers. improve the handling of graphics. improve alphabet, character representation, and keyboard.  the second edition of my monograph on this subject will be available at the copenhagen apl conference.  stephen w. dunwell