waashk/acm huggingface dataset:
distributed compilation metrics (abstract)  software metrics typically are used to determine the complexity of code, the cost of software development, the effort required to develop software, or the probability of software errors. as programs increase in size and complexity, more of the limited cpu resource is consumed during compilation. in an effort to reduce the overall time for compilation of large (in excess of 1,000,000 lines of code) embedded ada programs, a distributed ada compilation system implemented on a network of computers has been developed. tests of this system, using small to medium size (1,000 to 50,000 lines of code) ada programs, have shown various levels of performance improvement over sequential compiles. the level of improvement, however, has not been consistent. at times, when the system is executing multiple concurrent compiles, there is a significant loss of efficiency. there has been relatively little work done on compilation time metrics [1,2]; and even less work done on distributed compilation time metrics which could be used to predict these major reductions in compilation performance.  our research presents two models for predicting compilation time for large ada programs in a distributed environment. the first model involves the application of several standard metrics (lines of code, data structures, i/o intensity) and some non-standard metrics for compilation time. the weaknesses discovered in this model for a distributed environment are discussed. the second model combines some standard metrics with a scheduling algorithm to both predict distributed compilation time and determine an allocation of packages among distributed processors to optimize compilation time.  we present tests of both of these models using modified piwg z tests. compilation time predictions from these models are also shown for larger programs. problems with an approach based on compilation time efficiency and recommendations for continued research in compilation metrics are discussed.  donal gotterbarn timothy d. hammer
reflections on metaclass programming in som  this paper reports on the evolution of metaclass programming in som (the ibm system object model). initially, som's use of explicit metaclasses introduced metaclass incompatibilities. this was cured by having som dynamically derive an appropriate metaclass by interpreting the "metaclass declaration" as a constraint. in effect, inheritance is given a new dimension, because the constraint is also inherited. the derived metaclass is the least solution to all these constraints. subsequently, this cure led to the possibility of metaclasses conflicting over the need to assign meaning to a method. the cure for this problem is a framework that facilitates the programming of metaclasses that cooperate on the assignment of meaning to methods.  scott danforth ira r. forman
program integration for languages with procedure calls  given a program base and two variants, a and b, each created by modifying separate copies of base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of base preserved in both variants. text-based integration techniques, such as the one used by the unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of base, a, and b. the first program integration algorithm to provide such guarantees was developed by horwitz, prins, and reps. however, a limitation of that algorithm is that it only applied to programs written in a restricted language---in particular, the algorithm does not handle programs with procedures. this article describes a generalization of the horwitz-prins-reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures.  we show that two straightforward generalizations of the horwitz-prins-reps algorithm yield unsatisfactory results. the key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants a and b. our solution to this problem involves identifying two different kinds of affected components of a and b: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. the algorithm makes use of interprocedural program slicing to identify these components, as well as components in base, a, and b with the same behavior.  david binkley susan horwitz thomas reps
an open-ended data representation model for eu_lisp  the goal of this paper is to describe an open-ended type system for lisp with explicit and full control of bit-level data representations. this description uses a reflective architecture based on a metatype facility. this low-level formalism solves the problem of an harmonious design of a class taxononomy inside a type system.  a prototype for this framework has been written in le-lisp and is used to build the integrated type and object systems of the eu_lisp proposal.  christian queinnec pierre cointe
disconnected operation in the coda file system  disconnected operation is a mode of operation that enables a client to continue accessing critical data during temporary failures of a shared data repository. an important, though not exclusive, application of disconnected operation is in supporting portable computers. in this paper, we show that disconnected operation is feasible, efficient and usable by describing its design and implementation in the coda file system. the central idea behind our work is that caching of data, now widely used for performance, can also be exploited to improve availability.  james j. kistler m. satyanarayanan
pdl/ada - a design language based on ada  this paper discusses (1) some general concepts of design languages, (2) the development of the specific design language denoted as pdl/ada, (3) the specific features of pdl/ada, and (4) some problems encountered and techniques used in defining pdl/ada. an appendix shows two examples. because of space constraints, each of these items can only be touched on briefly. this paper assumes that the reader has a basic familiarity with the ada language (herein after referred to as ada), but detailed knowledge is not required.  the prime technical focus of the work has been to replace an existing design language and notation which supports a specific design methodology with a design language based on ada without impacting the methodology. there was a clearcut decision to use ada to obtain the dual benefits of having a design language which was a subset of a programming language while still retaining just the concepts needed for a design (rather than a programming) language.  jean e. sammet douglas w. waugh robert w. reiter
designing components versus objects: a transformational approach  a good object-oriented design does not necessarily make a good component-based design, and vice versa. what design principles do components introduce? this paper examines component-based programming and how it expands the design space in the context of an event-based component architecture. we present a conceptual model for addressing new design issues these components afford, and we identify fundamental design decisions in this model that are not a concern in conventional object-oriented design. we use javabeans-based examples to illustrate concretely how expertise in component-based design, as embodied in a component taxonomy and implementation space, impacts both design and the process of design. the results are not exclusive to javabeans---they can apply to any comparable component architecture.  david h. lorenz john vlissides
a retargetable debugger  we are developing techniques for building retargetable debuggers. our prototype, 1db, debugs c programs compiled for the mips r3000, motorola 68020, sparc, and vax architectures. it can use a network to connect to faulty processes and can do cross-architecture debugging. 1db's total code size is about 16,000 lines, but it needs only 250--550 lines of machine-dependent code for each target.  1db owes its retargetability to three techniques: getting help from the compiler, using a machine-independent embedded interpreter, and choosing abstractions that minimize and isolate machine-dependent code. 1db reuses existing compiler function by having the compiler emit postscript code that 1db later interprets; postscript works well in this unusual context.  norman ramsey david r. hanson
implementation strategies for continuations  scheme and smalltalk continuations may have unlimited extent. this means that a purely stack-based implementation of continuations, as suffices for most languages, is inadequate. several implementation strategies have been described in the literature. determining which is best requires knowledge of the kinds of programs that will commonly be run.  danvy, for example, has conjectured that continuation captures occur in clusters. that is, the same continuation, once captured, is likely to be captured again. as evidence, danvy cited the use of continuations in a research setting. we report that danvy's conjecture is somewhat true in the commercial setting of macscheme+toolsmith , which provides tools for developing macintosh user interfaces in scheme. these include an interrupt- driven event system and multitasking, both implemented by liberal use of continuations.  we describe several implementation strategies for continuations and compare four of them using benchmarks. we conclude that the most popular strategy may have a slight edge when continuations are not used at all, but that other strategies perform better when continuations are used and danvy's conjecture holds.  will clinger anne hartheimer eric ost
cilk: an efficient multithreaded runtime system  cilk (pronounced "silk") is a c-based runtime system for multi-threaded parallel programming. in this paper, we document the efficiency of the cilk work-stealing scheduler, both empirically and analytically. we show that on real and synthetic applications, the "work" and "critical path" of a cilk computation can be used to accurately model performance. consequently, a cilk programmer can focus on reducing the work and critical path of his computation, insulated from load balancing and other runtime scheduling issues. we also prove that for the class of "fully strict" (well-structured) programs, the cilk scheduler achieves space, time and communication bounds all within a constant factor of optimal.  the cilk runtime system currently runs on the connection machine cm5 mpp, the intel paragon mpp, the silicon graphics power challenge smp, and the mit phish network of workstations. applications written in cilk include protein folding, graphic rendering, backtrack search, and the *socrates chess program, which won third prize in the 1994 acm international computer chess championship.  robert d. blumofe christopher f. joerg bradley c. kuszmaul charles e. leiserson keith h. randall yuli zhou
fixpoint computation for polyvariant static analyses of higher-order applicative programs  this paper presents an optimized general-purpose algorithm for polyvariant, static analyses of higher-order applicative programs. a polyvariant analysis is a very accurate form of analysis that produces many more abstract descriptions for a program than does a conventional analysis. it may also compute intermediate abstract descriptions that are irrelevant to the final result of the analysis. the optimized algorithm addresses this overhead while preserving the accuracy of the analysis. the algorithm is also parameterized over both the abstract domain and degree of polyvariance. we have implemented an instance of our algorithm and evaluated its performance compared to the unoptimized algorithm. our implementation runs significantly faster on average than the other algorithm for benchmarks reported here.  j. michael ashley charles consel
an object-oriented approach to educational software in building physics an object-oriented building-physics software a.t.o.n. (which is the acronym for the german "general thermal and ecological verifications") is described as an example for educational software written in apl. the software was developed at the department for structural analysis at the technical university of graz, and has been successfully used for teaching building-physics. a.t.o.n. was designed in only four months. it comes with an user-friendly interface, which is easy and effortless to learn. every manipulation of data is immediately monitored in graphical windows. in order to achieve this "question & answer"-concept a hybrid system was set up. this system consists of quick c- and fortran-dlls combined with the dyalogapl interpreter using causewaypro as an interactive development environment. georg reichard
apl procedures (user defined operators, functions and token strings)  this paper describes some central aspects of an apl implementation on a hewlett packard minicomputer. the development of these ideas led to an elegant, consistent underlying structure for all procedures, where a procedure is defined as a structured sequence of apl expressions, instances of which are niladic functions, ambivalent functions, monadic operators and dyadic operators. further to this idea, the introduction of two new functions (tokenize and detokenize) and a single hyperoperator ( ) gave rise to the following features;  ability to manipulate functions and operators as apl objects  extended assignment applied to all apl objects  ability to store preset (or initialized) values into the header of any procedure  make direct use of the (usually restricted) facet of tokenizing and detokenizing in apl to generate token strings, which may be applied by the programmer to form individual variants of fx, cr and/or editing.  these extensions have been superimposed upon a basic imprint of sharp apl.  robert hodgkinson
adaptive and efficient mutual exclusion (extended abstract)  a distributed algorithm is adaptive if its performance depends on k, the number of processes that are concurrently active during the algorithm execution (rather than on n, the total number of processes). this paper presents adaptive algorithm for mutual exclusion using only read and write operations.  the worst case step complexity cannot be a measure for the performance of mutual exclusion algorithms, because it is always unbounded in the presence of contention. therefore, a number of different parameters are used to measure the algorithm's performance: the remote step complexity is the maximal number of steps performed by a process where a wait is counted as one step. the system response time is the time interval between subsequent entries to the critical section, where one time unit is the minimal interval in which every active process performs at least one step.  the algorithm presented here has o(k) remote step complexity and o(log k) system response time, where k is the point contention. the space complexity of this algorithm is o(nn), where n is the range of processes' names.  the space complexity of all previously known adaptive algorithms for various long-lived problems depends on n. we present a technique that reduces the space complexity of our algorithm to be a function of n, while preserving the other performance measures of the algorithm.  hagit attiya vita bortnikov
data space testing  a complete software testing process must concentrate on examination of the software characteristics as they may impact reliability. software testing has largely been concerned with structural tests, that is, test of program logic flow. in this paper, a companion software test technique for the program data called data space testing is described.  an approach to data space analysis is introduced with an associated notation. the concept is to identify the sensitivity of the software to a change in a specific data item. the collective information on the sensitivity of the program to all data items is used as a basis for test selection and generation of input values.  michael paige
object oriented design in a real-time multiprocessor environment  object oriented design (ood), with its emphasis on data encapsulation and rigorously defined message passing interfaces, offers great possibilities for improving the reliability and maintainability of large-scale software. these improvements are made feasible for the first time in military avionics applications by the recent emergence of new computers with significant increases in processing power and memory capacity. ironically, this newly available hardware, because it features modularity and multiprocessing, calls for distributed software, and thereby introduces an interesting challenge to the object oriented software view. the message passing or operation invoking interface between two objects which reside on the same processor is well defined and readily handled within the ood paradigm. how to extend the paradigm to cover two objects hosted on two different processors requires some thought, since only data, not tasks, can be passed from one processor to another  this distributed- objects challenge was faced early on in the development of ada software for the f-16a/b vhsic1 core avionics processor (vcap). this thirty month project, initiated in december 1987 by the ogden air logistics command (oo-alc), is prototyping hardware and software for a possible advanced avionics architecture (a3) upgrade to the f-16a/b fire control and stores management systems. the solution devised for vcap is called the remote object paradigm (rop). this paper describes relevant features of the vcap architecture and application, explains the rop methodology, and presents performance statistics to show the adequacy of rop to support hard real-time requirements.  k. mcquown
regions: an abstraction for expressing array computation most array languages, including fortran 90, matlab, and apl, provide support for referencing arrays by extending the traditional array subscripting construct found in scalar languages. we present an alternative to subscripting that exploits the concept of _regions_\\---an index set representation that can be named, manipulated with high-level operators, and syntactically separated from array references. this paper develops the concept of region-based programming and describes its benefits in the context of an idealized array language called _rl._ we show that regions simplify programming, reduce the likelihood of errors, and enable code reuse. furthermore, we describe how regions accentuate the locality of array expressions and how this locality is important when targeting parallel computers. we also show how the concepts of region-based programming have been used in zpl, a fully- implemented practical parallel programming language in use by scientists and engineers. in addition, we contrast region-based programming with the array reference constructs of other array languages. bradford l. chamberlain e. christopher lewis calvin lin lawrence snyder
on the relationships among three software metrics  automatable metrics of software quality appear to have numerous advantages in the design, construction and maintenance of software systems. while numerous such metrics have been defined, and several of them have been validated on actual systems, significant work remains to be done to establish the relationships among these metrics. this paper reports the results of correlation studies made among three complexity metrics which were applied to the same software system. the three complexity metrics used were halstead's effort, mccabe's cyclomatic complexity and henry and kafura's information flow complexity. the common software system was the unix operating system. the primary result of this study is that halstead's and mccabe's metrics are highly correlated while the information flow metric appears to be an independent measure of complexity.  sallie henry dennis kafura kathy harris
gc: the data-flow graph format of synchronous programming  based on an abstraction of the time as a discrete logical time, the synchronous languages, armed with a strong semantics, enable the design of safe real-time applications. some of them are of imperative style, while others are declarative. academic and industrial teams involved in synchronous programming defined together three intermediate representations, on the way to standardization:  • ic, a parallel format of imperative style,  • gc, a parallel format of data- flow style,  • oc, a sequential format to describe automata.  in this paper, we describe more specifically the format gc, and its links with the synchronous data-flow language signal. thanks to the first experimentations, gc reveals itself as a powerful representation for graph transformations, code production, optimization, hardware synthesis, etc.  pascal aubry thierry gautier
integrating program transformations in the memory-based synthesis of image and video algorithms  in this paper we discuss the interaction and integration of two important program transformations in high-level synthesis \---tree height reduction and redundant memory-access elimination. intuitively, these program transformations do not interfere with one another as they optimize different operations in the program graph and different resources in the synthesized system. however, we demonstrate that integration of the two tasks is necessary to better utilize available resources. our approach involves the use of a "meta-transformation" to guide transformation application as possibilities arise. results observed on several image and video benchmarks demonstrate that transformation integration increases performance through better resource utilization.  david j. kolson alexandru nicolau nikil dutt
parallelizing nonnumerical code with selective scheduling and software pipelining  instruction-level parallelism (ilp) in nonnumerical code is regarded as scarce and hard to exploit due to its irregularity. in this article, we introduce a new code-scheduling technique for irregular ilp called "selective scheduling" which can be used as a component for superscalar and vliw compilers. selective scheduling can compute a wide set of independent operations across all execution paths based on renaming and forward-substitution and can compute available operations across loop iterations if combined with software pipelining. this scheduling approach has better heuristics for determining the usefulness of moving one operation versus moving another and can successfully find useful code motions without resorting to branch profiling. the compile- time overhead of selective scheduling is low due to its incremental computation technique and its controlled code duplication. we parallelized the spec integer benchmarks and five aix utilities without using branch probabilities. the experiments indicate that a fivefold speedup is achievable on realistic resources with a reasonable overhead in compilation time and code expansion and that a solid speedup increase is also obtainable on machines with fewer resources. these results improve previously known characteristics of irregular ilp.  soo-mook moon kemal ebcioglu