waashk/acm huggingface dataset:
a balanced code placement framework  give-n-take is a code placement framework which uses a generic producer- consumer mechanism. an instance of this could be a communication step between a processor that computes (produces) some data, and other processors that subsequently reference (consume) these data in an expression. an advantage of give-n-take over traditional partial redundancy elimination techniques is its concept of production regions, instead of single locations, which can be beneficial for general latency hiding. give-n-take also guarantees balanced production, i.e., each production will be started and stopped exactly once. the framework can also take advantage of production coming "for free," as induced by side effects, without disturbing balance. give-n-take can place production either before or after consumption, and it also provides the option to speculatively hoist code out of potentially zero-trip loop (nest) constructs. give-n-take uses a fast elimination method based on tarjan intervals, with a complexity linear in the program size in most cases. we have implemented give- n-take as partof a fortran d compiler prototype, where it solves various communication generation problems associated with compiling data-parallel languages onto distributed-memory architectures.  reinhard von hanxleden ken kennedy
attacking the process migration bottleneck  moving the contents of a large virtual address space stands out as the bottleneck in process migration, dominating all other costs and growing with the size of the program. copy-on- reference shipment is shown to successfully attack this problem in the accent distributed computing environment. logical memory transfers at migration time with individual on-demand page fetches during remote execution allows relocations to occur up to one thousand times faster than with standard techniques. while the amount of allocated memory varies by four orders of magnitude across the processes studied, their transfer times are practically constant. the number of bytes exchanged between machines as a result of migration and remote execution drops by an average of 58% in the representative processes studied, and message-handling costs are cut by over 47% on average. the assumption that processes touch a relatively small part of their memory while executing is shown to be correct, helping to account for these figures. accent's copy-on-reference facility can be used by any application wishing to take advantage of lazy shipment of data.  e. zayas
an exemplar based smalltalk  two varieties of object-oriented systems exist: one based on classes as in smalltalk and another based on exemplars (or prototypical objects) as in act/1. by converting smalltalk from a class based orientation to an exemplar base, independent instance hierarchies and class hierarchies can be provided. decoupling the two hierarchies in this way enables the user's (logical) view of a data type to be separated from the implementer's (physical) view. it permits the instances of a class to have a representation totally different from the instances of a superclass. additionally, it permits the notion of multiple representations to be provided without the need to introduce specialized classes for each representation. in the context of multiple inheritance, it leads to a novel view of inheritance (or-inheritance) that differentiates it from the more traditional multiple inheritance notions (and- inheritance). in general, we show that exemplar based systems are more powerful than class based systems. we also describe how an existing class based smalltalk can be transformed into an exemplar-based smalltalk and discuss possible approaches for the implementation of both and- inheritance and or-inheritance.  wilf r. lalonde dave a. thomas john r. pugh
on the optimality of change propagation for incremental evaluation of hierarchical attribute grammars  several new attribute grammar dialects have recently been developed, all with the common goal of allowing large, complex language translators to be specified through a modular composition of smaller attribute grammars. we refer to the class of dialects as hierarchical attribute grammars. in this short article, we present a characterization of optimal incremental evaluation that indicates the unsuitability of change propagation as the basis of an optimal incremental evaluator for hierarchical attribute grammars. this result lends strong support to the use of incremental evaluators based on more applicative approaches to attribute evaluation, such as carle and pollock's evaluator based on more applicative approaches to attribute evaluation, such as carle and pollock's evaluator based on caching of partially attributed subtree, pugh's evaluator based on function caching of semantic functions, and swierstra and vogt's evaluator based on functions, and swierstra and vogt's evaluator based on function caching of visit sequences.  alan carle lori pollock
evolving object oriented design, a case study  handling the complexity of hierarchical object oriented design (ood) decomposition and dealing with the subjective nature of the supporting pictorial representations have historically been two relatively undeveloped aspects of the design methodology. by defining decomposition rules, a requirements allocation scheme, and an organized method of uniquely cataloging objects, the overall complexity of the hierarchical design decomposition process can be reduced. the addition of documentation standards, which are used to formally record and track the assignment of requirements, further reduces the complexity. the documentation standards also require that all relevant information concerning objects and operations, as well as their interactions, be formally recorded. the subjective nature of ood pictorial representations can be eliminated by incorporating data couples and control arrow and using support documentation to record that information which can not be represented pictorially. the intent of this paper is to illustrate, by case study, method improvements to further evolve ood. by incorporating these improvements into the ood process, the portability, reusability and maintainability of the resulting software can be increased.  m. p. schuler
off-line variable substitution for scaling points-to analysis  most compiler optimizations and software productivity tools rely oninformation about the effects of pointer dereferences in a program.the purpose of points- to analysis is to compute this informationsafely, and as accurately as is practical. unfortunately, accuratepoints-to information is difficult to obtain for large programs,because the time and space requirements of the analysis becomeprohibitive.  we consider the problem of scaling flow- and context-insensitivepoints-to analysis to large programs, perhaps containing hundreds ofthousands of lines of code. our approach is based on a variable substitution transformation, which is performed off-line, i.e.,before a standard points-to analysis is performed. the general idea ofvariable substitution is that a set of variables in a program can be replaced by a single representative variable, thereby reducing the input size of the problem. our main contribution is a linear-time algorithm which finds a particular variable substitution that maintains the precision of the standard analysis, and is also very effective in reducing the size of the problem.  we report our experience in performing points-to analysis on largec programs, including some industrial-sized ones. experiments show thatour algorithm can reduce the cost of andersen's points-to analysis substantially: on average, it reduced the running time by 53% and the memory cost by 59%, relative to an efficient baseline implementation of the analysis.  atanas rountev satish chandra
interactive multilevel definition of apl functions  an attempt is made to establish a convention that will make possible an interactive multilevel definition of apl functions. in accordance with this convention, functions can be defined at two levels: first an outline (flow- chart) is specified, this being followed by a detailed specification of the outline, prompted by the apl system. the convention is based on iverson's direct definition form and enables the user to define long functions in an interactive manner. preliminary experience with this convention indicates that it can improve the readability of apl functions  moshe sniedovich
a hybrid approach to software reuse  we describe a hybrid approach to software reuse in an ongoing project that addresses a challenging software engineering task. the approach is driven by an architectural design and makes use of both code components and program synthesis technology. we describe criteria that were used in choosing the reuse strategy for different parts of the application and argue that to be successful a reuse strategy must be driven by the needs of an application program instead of adapting a software development strategy around a reuse program.  sanjay bhansali
metrics based asset assessment the re-use of software components during the software development is considered to be an important factor to improve the quality and productivity and thus to reduce the time to market of the final product. in this paper we will present a proposal for a description model for re-usable components. we will also present the results of case studies concerned with both telecom specific and ,,generic" it-components. these components have been examined using the description model and a further set of (empirical) criterions. based on the results a model concept for the empirical assessment of javabeans, which is currently under development, is presented.. andreas schmietendorf reiner dumke erik foltin
whole program compilation for embedded software: the adsl experiment  the increasing complexity and decreasing time-to-market of embedded software forces designers to write more modular and reusable code, using for example object-oriented techniques and languages such as c++. the resulting memory and runtime overhead cannot be removed by traditional optimizing compilers; a global, whole program analysis is required. to evaluate the potential of whole program optimization techniques, we have manually optimized the embedded software of a commercial adsl modem. using only techniques that can be automated, a memory footprint reduction of newly 60% has been achieved. we conclude that a consistent and aggressive use of whole system optimization techniques is feasible and worthwhile, and that the implementation of such techniques in a compiler for embedded software will allow software designers to write more modular and reusable code without suffering the associated implementation overhead.  a. johan cockx
efficient mutation analysis: a new approach  in previously reported research we designed and analyzed algorithms that improved upon the run time complexity of all known weak and strong mutation analysis methods at the expense of increased space complexity. here we describe a new serial strong mutation algorithm whose running time is on the average much faster than the previous ones and that uses significantly less space than them also. its space requirement is approximately the same as that of mothra, a well-known and readily available implemented system. moreover, while this algorithm can serve as basis for a new mutation system, it is designed to be consistent with the mothra architecture, in the sense that, by replacing certain modules of that system with new ones, a much faster system will result. such a mothra-based implementation of the new work is in progress.  like the previous algorithms, this one, which we call lazy mutant analysis or lma, tries to determine whether a mutant is strongly killed by a given test only if it is already known that it is weakly killed by that test. unlike those algorithms, lma avoids executing many mutants by dynamically discovering classes of mutants that have the "same" behavior, and executing representatives of those classes. the overhead it incurs is small in proportion to the time saved, and the algorithm has a very natural parallel implementation.  in comparison to the fastest known algorithms for strong mutation analysis, in the best case, lma can improve the speed by a factor proportional to the average number of mutants per program statement. in the worst case, there is no improvement in the running time, but such a case is hard to construct. this work enables us to apply mutation analysis to significantly larger programs than is currently possible.  vladimir n. fleyshgakker stewart n. weiss
egregion: a branch coverage tool for apl this article describes our experience with test suites and automated branch coverage tools for apl software maintenance, based on our use of them to verify y2k compliance of an apl-based database system. we introduce _egregion,_ a simple, easy-to- use tool that assesses branch coverage in apl functions. the tool comprises a pair of apl functions that report detailed and summary function-level information about code coverage of test suites. the _egregion_ tool provides a line-by-line analysis of statement coverage, labels not branched to, branches never taken, branches always taken, transfer of control via non-branches, and branches to non-labeled lines. although we do not consider this groundbreaking work, we do believe that the coverage tool will be valuable to apl programmers who are engaged in the creation of large, reliable applications. robert bernecky
overcoming the challenges to feedback-directed optimization (keynote talk)  _feedback-directed optimization (fdo) is a general term used to describe any technique that alters a program's execution based on tendencies observed in its present or past runs. this paper reviews the current state of affairs in fdo and discusses the challenges inhibiting further acceptance of these techniques. it also argues that current trends in hardware and software technology have resulted in an execution environment where immutable executables and traditional static optimizations are no longer sufficient. it explains how we can improve the effectiveness of our optimizers by increasing our understanding of program behavior, and it provides examples of temporal behavior that we can (or could in the future) exploit during optimization._  michael d. smith
coloring register pairs  many architectures require that a program use pairs of adjacent registers to hold double-precision floating-point values. register allocators based on chaitin's graph-coloring technique have trouble with programs that contain both single-register values and values that require adjacent pairs of registers. in particular, chaitin's algorithm often produces excessive spilling on such programs. this results in underuse of the register set; the extra loads and stores inserted into the program for spilling also slow execution.  an allocator based on an optimistic coloring scheme naturally avoids this problem. such allocators delay the decision to spill a value until late in the allocation process. this eliminates the over-spilling provoked by adjacent register pairs in chaitin's scheme.  this paper discusses the representation of register pairs in a graph coloring allocator. it explains the problems that arise with chaitin's allocator and shows how the optimistic allocator avoids them. it provides a rationale for determining how to add larger aggregates to the interference graph.  preston briggs keith d. cooper linda torczon
apl extensions - a users view  there has been much heated argument about extensions in apl. this paper reflects 5 years' experience with one brand of extensions (stsc's nested array system). useful and irritating features are discussed.  facilities available are compared with other implementations - apl2, dyalog, and ipsa. topics covered include event handling, file systems, strand notation, indexing, the each dual and rank operators, and interfaces to other languages. the paper is illustrated with examples drawn from code produced internally, and from vector competitions.  maurice h. jordan
organizing software in a distributed environment  the system modeller provides automatic support for several different kinds of program development cycle in the cedar programming system. it handles the daily evolution of a single module or a small group of modules modified by a single person, the assembly of numerous modules into a large system with complex interconnections, and the formal release of a system. the modeller can also efficiently locate a large number of modules in a big distributed file system, and move them from one machine to another to meet operational requirements or improve performance.  butler w. lampson eric e. schmidt
an interactive debugger for a concurrent language  this work deals with issues of interactive debugging for the concurrent language ecsp. the debugger matches a formal specification of the expected behavior of a program against its actual behaviour. this specification can be given at different levels of abstraction. control is returned to the user when an error is detected. the user can then modify the flow of the computation and/or dynamically change the specification of the expected behavior. the debugger implementation is based on program transformation techniques.  n. de francesco d. latella g. vaglini
interacting with an active, integrated environment  software engineering environments are intended to provide a cohesive and integrated set of tools to support the process of software engineering with much current research into environment design focussed on maximising the degree to which these tools can be integrated. this paper describes the architecture of a prototype environment which attempts to achieve a high degree of integration using techniques drawn from artificial intelligence, office automation and object-oriented programming. this environment is implemented as a federation of intelligent, co-operating agents which communicate, with each other and with users, by message passing. this paper is particularly concerned with user interface integration including the mechanisms employed to permit inter-agent and agent-user communications.  thomas rodden pete sawyer ian sommerville
the evolution of an integrated testing environment by the domain testing strategy  for the past several years a research approach has been developed in the area of program testing; this automated testing approach is called the domain testing strategy. this paper examines broader implications of that research, together with several new testing research approaches which have been motivated by this work. for example, recently some new results which characterize a set of paths which are sufficient for path-oriented testing have been obtained, motivated to a great extent by domain testing. this approach, in turn, has led to some positive and exciting results in the area of reliable module integration testing. a number of researchers are examining the issue of specification testing, combining information from the program specification with a structural testing approach which utilizes only program information; they have found domain testing to be helpful in this regard. combining all these aspects of the testing problem indicates the evolution of an integrated testing environment.  lee j. white
an apl batch scheduler improves service and system management  an apl.ms2 system is described which enhances the behavior of the batch task scheduler for the univac 90 series system: vs/9. in addition to permitting customized task control on a per-shift basis the system manager can interactively tune the system's batch load. the workspace communicates through operator commands and implements a simple algorithm which spreads the batch load so that both large and small tasks can execute. this work is an instance of the application of apl to systems programming in order to provide elegant interactive operating system tools.  jeff shrager lyle hartman
a preliminary study of ada expansion ratios  since the mandate (dodd 5001.31) requiring the use of the ada language in all mission critical software, a need for revised expansion ratios for estimating ada software has emerged. this paper describes a study to determine a set of preliminary ada expansion ratios. three classes of ada programming features were identified, also has a corresponding expansion ratio. these ratios are used to determine memory requirements which are input to cost estimation models such as cocomo and slim [1].  the results of this research will have dire ct bearing on future ada projects by helping to develop improved software costing and sizing estimates. this will lead to improved reliability on design requirements for program memory and execution timing specifications. a special note on the effect of timing and complier optimization is also included in this paper.  james v. chelini edmund b. hudson stephen m. reidy
finite state verification (abstract only): an emerging technology for validating software systems  ever since formal verification was first proposed in the late sixties, the idea of being able to definitively determine if a program meets its specifications has been an appealing, but elusive, goal. although verification systems based on theorem proving have improved considerably over the years, they are still inherently undecidable and require significant guidance from mathematically astute users. the human effort required for formal verification is so significant that it is usually only applied to the most critical software components.  alternative approaches to theorem proving based verification have also been under development for some time. these approaches usually restrict the problem domain in some way, such as focusing on hardware descriptions, communication protocols, or a limited specification language. these restrictions allow the problem to be solved by using reasoning algorithms that are guaranteed to terminate and by representing the problem with a finite state model, and thus these approaches have been called finite state verification. systems based on these approaches are starting to be effectively applied to interesting software systems and there is increasing optimism that such approaches will become widely applicable.  in this presentation, i will overview some of the different approaches to finite state verification. in particular i will describe symbolic model checking, integer necessary constraints, and incremental data flow analysis approaches. the strengths and weaknesses of these approaches will be described. in addition, i will outline the major challenges that must be addressed before finite state verification will become a common tool for the typical well-trained software engineer.  lori a. clarke
(isef): an integrated industrial-strength software engineering framework  isef is an environment for programming-in-the-large that integrates disparate software engineering principles, methods and tools into an industrial- strength, automated software development framework. projects using isef have reported increased software quality, improved software manageability and decreased software production costs. this paper presents the basic principles and mechanisms that enable isef to achieve environment/process integration as well as integration within the environment itself, describes the isef approach to software development, provides comparisons with related work, and reports on experience in using isef.  shaye koenig
prioritizing remote procedure calls in ada distributed systems in this paper we discuss the assignment of priorities to the execution of remote procedure calls in distributed real-time systems that are programmed using the distributed systems annex (dsa) of ada 95. we first discuss the current priority model used in the glade implementation of the dsa. we then present some theoretical results that show that a more flexible priority assignment methodology can provide much better schedulable utilization levels. based upon these results we propose an implementation that would allow using this priority assignment methodology in glade. finally, we propose new features for a future dsa that would allow prioritizing remote procedure calls in a flexible manner. j. j. gutierrez garcía m. gonzalez harbour