waashk/acm huggingface dataset:
long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)  long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. in [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. however, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. the number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is o(nk3) and  o(nk4) respectively where n is the total number of processes in the system and k is the encountered contention. here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, o(k4) for the snapshot implementation.  yehuda afek gideon stupp dan touitou
polylith: an environment to support management of tool interfaces  polylith is the name of a set of enhanced execution time system services along with development tools and an interfacing methodology.1 as a system, polylith supports the reliable union of many component tools, addressing the problems of data interchange and synchronization between these tools. it facilitates reuse of code, and promotes the notion that construction of large programs should be viewed instead as orchestration of services. the polylith is visible as a grammar in which instances of environments2 are precisely and rapidly specified; it is, through compilation and execution of assertions in that language, a medium through which many programs and tools can be united with impunity.  this paper presents an overview of the polylith architecture, along with some brief remarks on the requirements analysis leading to project polylith at the university of illinois. section 2 presents this architecture, summarizing language and data transformation issues. simple examples are included. section 3 introduces one particular instance of an environment specified within polylith called minion. it is presented as an extended example, showing how the polylith is utilized to construct an enthusiastic assistant for mathematical problem solving. the closing section contains some evaluation of how polylith affects the task of environment development.  james purtilo
the point of view notion for multiple inheritance  we examine several problems related to the preservation of the independence principle inheritance. this principle states that all the characteristics of independent superclasses must be inherited by subclasses, even if there are name conflicts. in this context, a conventional approach is to use explicit class selection. we show that this mechanism suffers from serious limitations, and leads to inhibition of refinement and genericity. our experimental object- oriented language rome introduces the "point of view" notion (using an "as- expressions" mechanism) which solves these problems.  bernard carre jean-marc geib
experience report: using resolve/c++ for commercial software  academic research sometimes suffers from the "ivory tower" problem: ideas that sound good in theory do not necessarily work well in practice. an example of research that potentially could impact practice over the next few years is a novel set of component-based software engineering design principles, known as the _resolve discipline_. this discipline has been taught to students for several years [23], and previous papers (e.g., [24]) have reported on student- sized software projects constructed using it. here, we report on a substantial commercial product family that was engineered using the same principles --- an application that we designed, built, and continue to maintain for profit, not as part of a research project. we discuss the impact of adhering to a very prescriptive set of design principles and explain our experience with the resulting applications. lessons learned should benefit others who might be considering adopting such a component-based software engineering discipline in the future.  joseph e. hollingsworth lori blankenship bruce w. weide
what are race conditions?: some issues and formalizations  in shared- memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. race conditions are often considered to be manifestations of bugs, since their presence can cause the program to behave unexpectedly. unfortunately, there has been little agreement in the literature as to precisely what constitutes a race condition. two different notions have been implicitly considered: one pertaining to programs intended to be deterministic (which we call general races) and the other to nondeterministic programs containing critical sections (which we call data races). however, the differences between general races and data races have not yet been recognized. this paper examines these differences by characterizing races using a formal model and exploring their properties. we show that two variations of each type of race exist: feasible general races and data races capture the intuitive notions desired for debugging and apparent races capture less accurate notions implicitly assumed by most dynamic race detection methods. we also show that locating feasible races is an np-hard problem, implying that only the apparent races, which are approximations to feasible races, can be detected in practice. the complexity of dynamically locating apparent races depends on the type of synchronization used by the program. apparent races can be exhaustively located efficiently only for weak types of synchronization that are incapable of implementing mutual exclusion. this result has important implications since we argue that debugging general races requires exhaustive race detection and is inherently harder than debugging data races (which requires only partial race detection). programs containing data races can therefore be efficiently debugged by locating certain easily identifiable races. in contrast, programs containing general races require more complex debugging techniques.  robert h. b. netzer barton p. miller
control flow and data structure documentation: two experiments  two experiments were carried out to assess the utility of external documentation aids such as macro flowcharts, pseudocode, data structure diagrams, and data structure descriptions. a 223 line pascal program which manipulates four arrays was used. the program interactively handles commands that allow the user to manage five lists of items. a comprehension test was given to participants along with varying kinds of external documentation. the results indicate that for this program the data structure information was more helpful than the control flow information, independently of whether textual or graphic formats were used.  ben shneiderman
building analytical models into an interactive performance prediction tool  in this paper we describe an interactive tool designed for performance prediction of parallel programs. static performance prediction, in general, is a very difficult task. in order to avoid some inherent problems, we concentrate on reasonably structured scientific programs. our prediction system, which is built as a sub-system of a larger interactive environment, uses a parser, dependence analyzer, database and an x-window based front end in analyzing programs. the system provides the user with execution times of different sections of programs. when there are unknowns involved, such as number of processors or unknown loop bounds, the output is an algebraic expression in terms of these variables. we propose a simple analytical model as an attempt to predict performance degradation due to data references in hierarchical memory systems. the predicted execution times of some lawrence livermore loop kernels are given together with the experimental values obtained by executing the loops on alliant fx/8.  d. arapattu d. gannon
an incremental approach to structural testing of concurrent software structural testing of a concurrent program p involves the selection of paths of p according to a structure-based criterion. a common approach is to derive the reachability graph (rg) of p, select a set of paths of p, derive one or more inputs for each selected path, and force deterministic executions of p according to the selected paths and their inputs. the use of rg(p) for test path selection has the state explosion problem, since the number of states of rg(p) is an exponential function of the number of processes in p.in this paper, we present a new incremental approach to structural testing of p. based on the hierarchy of processes in p, our incremental testing approach is to integrate processes in p in a bottom-to-top manner. when a set s of processes in p at the same level are integrated, we construct a reduced rg for s such that the reduced rg contains all synchronizations involving the processes in s and some of the synchronizations involving processes at lower levels in order to connect synchronizations involving processes in s. based on the reduced rg for s, we can select test paths to focus on the detection of interface faults involving processes in s. after the selection of paths, rg(s) is further reduced in order to retain only some of the synchronizations involving processes in s that are needed in order to connect synchronizations between s and other processes in p. our incremental approach alleviates the state explosion problem and offers other advantages. pramod v. koppol kuo-chung tai
some experiments in global microcode compaction  global microcode compaction is an open problem in firmware engineering. although fisher's trace scheduling method may produce significant reductions in the execution time of compacted microcode, it has some drawbacks. there have been four methods. tree, srdag, itsc , and gddg, presented recently to mitigate those drawbacks in different ways.  the purpose of the research reported in this paper is to evaluate these new methods. in order to do this, we have tested the published algorithms on several unified microcode sequences of two real machines and compared them on the basis of the results of experiments using three criteria: time efficiency, space efficiency, and complexity.  b. su s. ding
recovery management in quicksilver  one price of extensibility and distribution, as implemented in quicksilver, is a more complicated set of failure modes, and the consequent necessity of dealing with them. in traditional operating systems, services (e.g., file, display) are intrinsic pieces of the kernel. process state is maintained in kernel tables, and the kernel contains explicit cleanup code (e.g., to close files, reclaim memory, and get rid of process images after hardware or software failures). quicksilver, however, is structured according to the client-server model, and as in many systems of its type, system services are implemented by user-level processes that maintain a substantial amount of client process state. examples of this state are the open files, screen windows, address space, etc., belonging to a process. failure resilience in such an environment requires that clients and servers be aware of problems involving each other. examples of the way one would like the system to behave include having files closed and windows removed from the screen when a client terminates, and having clients see bad return codes (rather than hanging) when a file server crashes. this motivates a number of design goals:  properly written programs (especially servers) should be resilient to external process and machine failures, and should be able to recover all resources associated with failed entities.  server processes should contain their own recovery code. the kernel should not make any distinction between system service processes and normal application processes.  to avoid the proliferation of ad-hoc recovery mechanisms, there should be a uniform system- wide architecture for recovery management.  a client may invoke several independent servers to perform a set of logically related activitites (a unit of work) that must execute atomically in the presence of failures, that is, either all the related activities should occur or none of them should. the recovery mechanism should support this.  in quicksilver, recovery is based on the database notion of atomic transactions, which are made available as a system service to be used by other, higher-level servers. this allows meeting all the above design goals. software portability is important in the quicksilver environment, dictating that transaction-based recovery be accessible to conventional programming languages rather than a special-purpose one such as argus [liskov84]. to accommodate servers with diverse recovery demands, the low-level primitives of commit coordination and log recovery are exposed directly rather than building recovery on top of a stable-storage mechanism such as in cpr [attanasio87] or recoverable objects such as those in camelot [spector87] or clouds [allchin&amp;mckendry83;].  r. haskin y. malachi w. sawdon g. chan
software environments workshop report  a recent workshop identified a variety of issues fundamental to advanc ing the state-of-the-art in software environments. in addition, activities were specified to address these issues and provide incremental improvement in the near and medium term. even though the sets of issues and activities are incomplete, they are reported here to seed the community's thinking about what is needed to advance the state-of- the-art for software environments and assist in establishing long-range goals, identifying and defining specific projects, and identifying the coordination needed among the projects.  william e. riddle lloyd g. williams
apl thinking: examples  in an effort to understand "apl thinking", we examine a few selected examples of using apl to solve specific problems, namely: compute the median of a numerical vector; simulate the replicate function; string search; carry forward work-to-be-done in excess of capacity; rotate concentric rectangular rings in a matrix; find column indices of pivots in an echelon matrix.  these examples are drawn from our teaching experience as well as from apl literature. we are particularly interested in studying thinking processes underlying alternative solutions to such problems --- i.e., our goal is to "get inside the head" of the apl programmer. analyses include reconstructing thoughts, comparing alternative approaches, and, in general, scrutinizing supposed characteristics of apl thinking.  murray eisenberg howard a. peelle
a retargetable instruction reorganizer  extant peephole optimizers can perform many optimizations that are handled by higher-level optimizers. this paper describes a retargetable instruction reorganizer that performs targeting and evaluation order determination by applying a well known algorithm for optimal code generation for expressions to object code. by applying the algorithm to object code after code generation and optimization, a phase ordering problem often encountered by higher-level optimizers is avoided. it minimizes the number of registers and temporaries required to compile expressions by rearranging machine instructions. for some machines, this can result in smaller and faster programs. by generalizing its operation, the reorganizer can also be used to reorder instructions to avoid delays in pipelined machines. for one pipelined machine, it has provided a 5 to 10 percent improvement in the execution speed of benchmark programs.  jack w. davidson
compiling c for vectorization, parallelization, and inline expansion  practical implementations of real languages are often an excellent way of testing the applicability of theoretical principles. many stresses and strains arise from fitting practicalities, such as performance and standard compatibility, to theoretical models and methods. these stresses and strains are valuable sources of new research and insight, as well as an oft-needed check on the egos of theoreticians.  two fertile areas that are often explored by implementations are  places where tractable models fail to match practice. this can lead to new models, and may also affect practice (e.g., the average programming language has become more context free over the last several decades).  places where existing algorithms fail to deal with practical problems effectively, frequently because the problems are large in some dimension that has not been much explored.  the present paper discusses the application of a much studied body of algorithms and techniques [alle 83, kklw 80, bane 76, wolf 78, wolf 82, kenn 80, lamp 74, huso 82] for vectorizing and optimizing fortran to the problem of vectorizing and optimizing c. in the course of this work some algorithms were discarded, others invented, and many were tuned and modified. the experience gave us insight into the strengths and weaknesses of the current theory, as well as into the strong and weak points of c on vector/parallel machines. this paper attempts to communicate some of those insights.  r. allen s. johnson
type-based hot swapping of running modules (extended abstract) while dynamic linking has become an integral part of the run-time execution of modem programming languages, there is increasing recognition of the need for support for hot swapping of running modules, particularly in long-lived server applications. the interesting challenge for such a facility is to allow the new module to change the types exported by the original module, while preserving type safety. this paper describes a type-based approach to hot swapping running modules. the approach is based on a reflective mechanism for dynamically adding type sharing constraints to the type system, realized by programmer-defined version adapters in the run-time. dominic duggan
area-efficient buffer binding based on a novel two-port fifo structure  in this paper, we address the problem of minimizing buffer storage requirement in buffer binding for sdf (synchronous dataflow) graphs. first, we propose a new two-port fifo buffer structure that can be efficiently shared by two producer/consumer pairs. then we propose a buffer binding algorithm based on this two-port buffer structure for minimizing the buffer size requirement. experimental results demonstrate 9.8%~37.8% improvement in buffer requirement compared to the conventional approaches.  kyoungseok rha kiyoung choi
pclos: stress testing clos experiencing the metaobject protocol  this paper demonstrates that the clos metaobject protocol approach to defining and implementing an object model is very powerful. clos is an object-oriented language that is based on common lisp and is in the process of being standardized. implementations of clos are themselves object-oriented with all major building blocks of the language being instances of system classes. a metaobject protocol provides a framework for clos implementations by specifying the hierarchy of these classes and the order and contents of the communication among their instances. this design has made clos both flexible and portable, two design goals that traditionally conflict. in support of this suggestion we present a detailed account of how we added object persistence to clos without modifying any of the language's implementation code.  andreas paepcke
product assurance program analyzer (p.a.p.a.) a tool for program complexity evaluation  this tool has been developed to assist in the software validation process. p.a.p.a. will measure the complexity of programs and detect several program anomalies. the resulting list of analyzed programs is sorted in order of descending complexity. since high complexity and error- proneness are strongly related, the "critical" programs will be found earlier within the development cycle.  p.a.p.a. provides syntax analyzers for rpg (ii/iii), pseudocode (design and documentation language) and pl/siii (without macro language). it may be applied during the design-, coding- and testphase of software development (e.g. for design- and code inspections).  karl ernst schnurer
scale and performance in a distributed file system  andrew is a distributed computing environment being developed in a joint project by carnegie mellon university and ibm. one of the major components of andrew is a distributed file system which constitutes underlying mechanism for sharing information. the goals of the andrew file system are to support growth up to at least 7000 workstations (one for each student, faculty member, and staff at carnegie mellon) while providing users, application programs, and system administrators with the amenities of a shared file system.  a fundamental result of our concern with scale is the design decision to transfer whole files between servers and workstations rather than some smaller unit such as records or blocks, as almost all other distributed file systems do. this paper examines the consequences of this and other design decisions and features that bear on the scalability of andrew.  large scale affects a distributed system in two ways: it degrades performance and it complicates administration and day-to-day operation. this paper addresses both concerns and shows that the mechanisms we have incorporated cope with them successfully. we start the initial prototype of the system, what we learned from it, and how we changed the system to improve performance. we compare its performance with that of a block-oriented file system, sun microsystems' nfs, in order to evaluate the whole file transfer strategy. we then turn to operability, and finish with issues related peripherally to scale and with the ways the present design could be enchanced.  j. howard m. kazar s. menees d. nichols m. west
an alternative to the use of patterns in string processing  snobol4 is best known for its string processing facilities, which are based on patterns as data objects. despite the demonstrated success of patterns, there are many shortcomings associated with their use. the concept of patterns in snobol4 is examined and problem areas are discussed. an alternative method for high-level string processing is described. this method, implemented in the programming language icon, employs generators, which are capable of producing alternative values. generators, coupled with a goal- driven method of expression evaluation, provide the string processing facilities of snobol4 without the disadvantages associated with patterns. comparisons between snobol4 and icon are included and the broader implications of the new approach are discussed.  ralph e. griswold david r. hanson
language constructs and support systems for distributed computing  this paper describes programming constructs and system support functions that are intended to facilitate the programming of reliable distributed systems. the systems considered include very different kinds of computers communicating through a network. such a heterogeneous network offers a number of advantages to designers of applications software. different machines emphasize different capabilities and many problems naturally break down into subproblems that are best solved with specialized resources. there is clearly a need for programming tools that will allow users to exploit this kind of environment.  c. s. ellis j. a. feldman j. e. heliotis