waashk/acm huggingface dataset:
incorporating load dependent servers in approximate mean value analysis  queueing network performance modelling technology has made tremendous strides in recent years. two of the most important developments in facilitating the modelling of large and complex systems are hierarchical modelling, in which a single load dependent server is used as a surrogate for a subsystem, and approximate mean value analysis, in which reliable approximate solutions of separable models are efficiently obtained. unfortunately, there has been no successful marriage of these two developments; that is, existing algorithms for approximate mean value analysis do not accommodate load dependent servers reliably.  this paper presents a successful technique for incorporating load dependent servers in approximate mean value analysis. we consider multiple class models in which the service rate of each load dependent server is a function of the queue length at that server. in other words, load dependent center k delivers "service units" at a total rate of f@@@@ (n@@@@) when n@@@@ customers are present. we present extensive experimental validation which indicates that our algorithm contributes an average error in response times of less than 1% compared to the (much more expensive) exact solution.  in addition to the practical value of our algorithm, several of the techniques that it employs are of independent interest.  john zahorjan edward d. lazowska
modlisp  this paper discusses the design and implementation of modlisp, a lisp-like language enhanced with the idea of modes. this extension permits, but does not require, the user to declare the types of various variables, and to compile functions with the arguments declared to be of a particular type. it is possible to declare several functions of the same name, with arguments of different type (e.g. plus could be declared for integer arguments, or rational, or real, or even polynomial arguments) and the system will apply the correct function for the types of the arguments.  the modlisp language differs from other abstract data type languages such as clu [liskov & zilles, 1974; liskov et al, 1977] and russell [donahue,1977] in that it allows dynamic construction of new parametrised data types and possesses a unified semantics covering interpreted and compiled code, which can call one another at will. in short, it is lisp-like.  james h. davenport richard d. jenks
failure correction techniques for large disk arrays  the ever increasing need for i/o bandwidth will be met with ever larger arrays of disks. these arrays require redundancy to protect against data loss. this paper examines alternative choices for encodings, or codes, that reliably store information in disk arrays. codes are selected to maximize mean time to data loss or minimize disks containing redundant data, but are all constrained to minimize performance penalties associated with updating information or recovering from catastrophic disk failures. we also codes that give highly reliable data storage with low redundant data overhead for arrays of 1000 information disks.  g. a. gibson l. hellerstein r. m. karp d. a. patterson
the shared regions approach to software cache coherence on multiprocessors  the effective management of caches is critical to the performance of applications on shared-memory multiprocessors. in this paper, we discuss a technique for software cache coherence tht is based upon the integration of a program-level abstraction for shared data with software cache management. the program-level abstraction, called shared regions, explicitly relates synchronization objects with the data they protect. cache coherence algorithms are presented which use the information provided by shared region primitives, and ensure that shared regions are always cacheable by the processors accessing them. measurements and experiments of the shared region approach on a shared-memory multiprocessors accessing them. measurements and experiments of the shared region approach on a shared-memory multiprocessor are shown. comparisons with other software based coherence strategies, including a user- controlled strategy and an operating system-based strategy, show that this approach is able to deliver better performance, with relatively low corresponding overhead and only a small increase in the programming effort. compared to a compiler-based coherence strategy, the shared regions approach still performs better than a compiler that can achieve 90% accuracy in allowing cacheing, as long as the regions are a few hundred bytes or larger, or they are re-used a few times in the cache.  harjinder s. sandhu benjamin gamsa songnian zhou
mpc++ approach to parallel computing environment mpg++ is an extension of c++, which supports control parallel programming and metalevel programming. the mpg++ metalevel programming facility enables users to extend or modify c++ language features. library designers may supply abstractions in mpg++ source files where those abstractions are defined by the mpg++ metalevel programming facility. the users can use the right abstractions for their demands by just including files in their source files. yutaka ishikawa
towards a practical specification language  recognition of the value of formal specifications in the design and verification of large software systems is becoming more widespread. specification languages themselves, however, are difficult to develop in part because of the inherent conflict between the goals of clarity and formalism required by these languages. this paper discusses the role of specification languages, examples of specifications in two currently implemented languages, affirm and special, and makes some suggestions towards a more practical specification language.  anne-marie g. discepolo
dynamic currency determination in optimized programs  compiler optimizations pose many problems to source-level debugging of an optimized program due to reordering, insertion, and deletion of code. on such problem is to determine whether the value of a varible is current at a breakpoint---that is, whether its actual value is the same as its expected value. we use the notion of dynamic currency of a variable in source-level debugging and propose the use of a minimal unrolled graph to reduce the run- time overhead of dynamic currency determination. we prove that the minimal unrolled graph is an adequate basis for performing bit-vector data flow analyses at a breakpoint. this property is used to perform dynamic currency determination. it is also shown to help in recovery of a dynamically noncurrent variable.  d. m. dhamdhere k. v. sankaranarayanan
screen management in the "real world"  an application-based screen management system was developed in apl for a mainframe-based interactive database. it requires no special hardware or software support and therefore runs on any asynchronous communications device. the system includes features unique to most on-line databases yet common to many screen-oriented pc systems.  the foundation of the design is the division of all report information into discrete, logical sections. by dividing a report in this way and by providing the user with a powerful set of commands to allow movement both between and within these logical sections, one achieves a very flexible and user-friendly interface.  edmund w. stawick
three approximation techniques for astral symbolic model checking of infinite state real-time systems  astral is a high-level formal specification language for real-time systems. it has structuring mechanisms that allow one to build modularized specifications of complex real-time systems with layering. based upon the astral symbolic model checler reported in [13], three approximation techniques to speed-up the model checking process for use in debugging a specification are presented. the techniques are random walk, partial image and dynamic environment generation. ten mutation tests on a railroad crossing benchmark are used to compare the performance of the techniques applied separately and in combination. the test results are presented and analyzed.  zhe dang richard a. kemmerer
a project-based course in compiler construction  the paper describes the experience gained by teaching a project-based course in compiler construction. the course is a blend of theoretical concepts and practical considerations that go into the development of a compiler. a project in compiler writing is an important component of this course. asp, a subset of standard pascal, is used as the source language. the compiler for asp is to be developed in various phases: character manipulator, lexical analyzer, syntax analyzer, semantic analyzer, and code generator. recursive descent method is used to parse the various syntactic entities. the code generator emits code for a hypothetical machine called aoc (algol object code). a simulator executes this code.  harbans l. sathi
object identity  identity is that property of an object which distinguishes each object from all others. identity has been investigated almost independently in general- purpose programming languages and database languages. its importance is growing as these two environments evolve and merge.  we describe a continuum between weak and strong support of identity, and argue for the incorporation of the strong notion of identity at the conceptual level in languages for general purpose programming, database systems and their hybrids. we define a data model that can directly describe complex objects, and show that identity can easily be incorporated in it. finally, we compare different implementation schemes for identity and argue that a surrogate-based implementation scheme is needed to support the strong notion of identity.  setrag n. khoshafian george p. copeland
forms based documentation to support structured develomemt and c.a.s.e. implementation  one of the most important aspects of structured development is the creation and enforcement of standards. standards define how a given methodology is to be used within your organization. examples of standards might include  which forms and other documents must be bundled together  steps in the approval process  when and by whom certain project steps must be done  maximum size of a module of code  it is by now common to have some minimal standards for actual program code and program documentation. however, too often only lip service is given to enforcement of organizational standards for system analysis and system design. in my view, documentation and standardization of these development stages is crucial. despite the current vogue, such documentation standards will not be achieved simply by purchasing and adopting a case tool. as a supplement to such a tool, especially at the beginning, a manual forms based method is necessary. through the use of forms, analysts are provided with an initial set of standards which may be used in your projects. there is a learning curve the development team must go through in order to gain experience using standards. after one or more projects, a decision is often made to modify the initial minimum set of standards to fit the needs of a particular company. this process is similar to that which you must carry out in tailoring the software life cycle model to your own framework. in practice, a manual system reduces the time it takes to learn a new set of tools.  d. bellin
viewing a programming environment as a single tool  programming environments support the creation, modification, execution and debugging of programs. the goal of integrating a programming environment is more than simply building tools that share a common data base and provide a consistent user interface. ideally, the programming environment appears to the programmer as a single tool; there are no firewalls separating the various functions provided by the environment. this paper describes the techniques used to integrate magpie, an interactive programming environment for pascal. display windows, called browsers, provide a consistent approach for interacting with the pascal source code or the execution state of the program. incremental compilation allows the programmer to specify debugging actions in pascal, eliminating the need for a separate debugging language.  norman m. delisle david e. menicosy mayer d. schwartz
a global communication optimization technique based on data-flow analysis and linear algebra  reducing communication overhead is extremely important in distributed-memory message-passing architectures. in this article, we present a technique to improve communication that considers data access patterns of the entire program. our approach is based on a combination of traditional data-flow analysis and a linear algebra framework, and it works on structured programs with conditional statements and nested loops but without arbitrary goto statements.the distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distributions including block-cyclic distribu-tions, and the ability to simulate some of the previous approaches with suitable modifications. we also show how optimizations such as message vectorization, message coalescing, and redundancy elimination are supported by our framework. experimental results on several benchmarks show that our technique is effective in reducing the number of messages (anaverage of 32% reduction), the volume of the data communicated (an average of 37%reduction), and the execution time (an average of 26% reduction).  m. kandemir p. banerjee a. choudhary j. ramanujam n. shenoy
combinatory representation of mobile processes  a theory of combinators in the setting of concurrent processes is formulated. the new combinators are derived from an analysis of the operation called asynchronous name passing, just as an analysis of logical substitution gave rise to the sequential combinators. a system with seven atoms and fixed interaction rules, but with no notion of prefixing, is introduced, and is shown to be capable of representing input and output prefixes over arbitrary terms in a behaviourally correct way, just as sk-combinators are closed under functional abstraction without having it as a proper syntactic construct. the basic equational correspondence between concurrent combinators and a system of asynchronous mobile processes, as well as the embedding of the finite part of π-calculus in concurrent combinators, is proved. these results will hopefully serve as a cornerstone for further investigation of the theoretical as well as pragmatic possibilities of the presented construction.  kohei honda nobuko yoshida
an empirical study of a wide-area distributed file system  the evolution of the andrew file system (afs) into a wide-area distributed file system has encouraged collaboration and information dissemination on a much broader scale than ever before. we examine afs as a provider of wide-area file services to over 100 organizations around the world. we discuss usage characteristics of afs derived from empirical measurements of the system. our observations indicate that afs provides robust and efficient data access in its current configuration, thus confirming its viability as a design point for wide-area distributed file systems.  mirjana spasojevic m. satyanarayanan
interfaces for strongly-typed object-oriented programming  this paper develops a system of explicit interfaces for object-oriented programming. the system provides the benefits of module interfaces found in languages like ada and modula-2 while preserving the expressiveness that gives untyped object- oriented languages like smalltalk their flexibility. interfaces are interpreted as polymorphic types to make the system sufficiently powerful. we use interfaces to analyze the properties of inheritance, and identify three distinct kinds of inheritance in object- oriented programming, corresponding to objects, classes, and interfaces, respectively. object interfaces clarify the distinction between interface containment and inheritance and give insight into limitations caused by equating the notions of type and class in many typed object-oriented programming languages. interfaces also have practical consequences for design, specification, and maintenance of object-oriented systems.  p. s. canning w. r. cook w. l. hill w. g. olthoff
debugging optimized code with dynamic deoptimization  self's debugging system provides complete source-level debugging (expected behavior) with globally optimized code. it shields the debugger from optimizations performed by the compiler by dynamically deoptimizing code on demand. deoptimization only affects the procedure activations that are actively being debugged; all other code runs at full speed. deoptimization requires the compiler to supply debugging information at discrete interrupt points; the compiler can still perform extensive optimizations between interrupt points without affecting debuggability. at the same time, the inability to interrupt between interrupt points is invisible to the user. our debugging system also handles programming changes during debugging. again, the system provides expected behavior: it is possible to change a running program and immediately observe the effects of the change. dynamic deoptimization transforms old compiled code (which may contain inlined copies of the old version of the changed procedure) into new versions reflecting the current source-level state. to the best of our knowledge, self is the first practical system providing full expected behavior with globally optimized code.  urs hölzle craig chambers david ungar
on the inevitable intertwining of specification and implementation  contrary to recent claims that specification should be completed before implementation begins, this paper presents two arguments that the two processes must be intertwined. first, limitations of available implementation technology may force a specification change. for example, deciding to implement a stack as an array (rather than as a linked list) may impose a fixed limit on the depth of the stack. second, implementation choices may suggest augmentations to the original specification. for example, deciding to use an existing pattern-match routine to implement the search command in an editor may lead to incorporating some of the routine's features into the specification, such as the ability to include wild cards in the search key. this paper elaborates these points and illustrates how they arise in the specification of a controller for a package router.  william swartout robert balzer
reasoning about continuations with control effects  we present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. we introduce two new control effects, goto and comefrom, that describe the control flow properties of expressions. an expression that does not have a goto effect is said to be continuation following because it will always call its passed return continuation. an expression that does not have a comefrom effect is said to be continuation discarding because it will never preserve its return continuation for later use. unobservable control effects can be masked by the effect system. control effect soundness theorems guarantee that the effects computed statically by the effect system are a conservative approximation of the dynamic behavior of an expression.  the effect system that we describe performs certain kinds of control flow analysis that were not previously feasible. we discuss how this analysis can enable a variety of compiler optimizations, including parallel expression scheduling in the presence of complex control structures, and stack allocation of continuations. the effect system we describe has been implemented as an extension to the fx-87 programming language.  p. jouvelot d. k. gifford
strategies for data abstraction in lisp  the benefits of abstract data types are many and are generally agreed upon [liskov and zilles 1974, linden 1976]. new languages are being constructed which provide for and enforce the use of data abstractions [liskov et al 1977, wulf et al 1976]. however, many of us are not in a position to use these new languages, but must stick to our installation's compiler. how then can we obtain the benefits of data abstraction? we discuss the implementation of data abstraction in a lisp program and the subtleties involved in doing so: specifically, how it is possible to enforce proper data abstraction in a language which does not provide for abstract data types.  barbara k. steele
the gnat compilation model  one of the novel features of gnat is its unusual approach to the compilation process and the handling of the ada library. the words novel and unusual only apply from a traditional ada compilation perspective. by contrast, a typical c or c++ programmer would find many aspects of the model quite familiar. in gnat, sources are independently compiled to produce a set of objects, and the set of object files thus produced is submitted to the binder/linker to generate the resulting executable. this approach removes all order-of- compilation considerations, and eliminates the traditional monolithic library structure. not only is the model very simple to understand, but it makes it easier to build hybrid systems in multiple languages, and is much more compatible with conventional configuration management tools (ranging from the simple unix make program to sophisticated compilation management environments) than the conventional library structure. needless to say, the approach we present is fully compatible with the ada rules of compilation.  robert dewar
fuzzy array dataflow analysis  exact array dataflow analysis can be achieved in the general case if the only control structures are do-loops and structural ifs, and if loop counter bounds and array subscripts are affine expressions of englobing loop counters and possibly some integer constants. in this paper, we begin the study of dataflow analysis of dynamic control programs, where arbitrary ifs and whiles are allowed. in the general case, this dataflow analysis can only be fuzzy.  jean-françois collard denis barthou paul feautrier
the measurement of software science parameters in software designs  metrics of software quality have historically focused on code quality despite the importance of early and continuous quality evaluation in a software development effort. while software science metrics have been used to measure the psychological complexity of computer programs as well as other quality related aspects of algorithm construction, techniques to measure software design quality have not been adequately addressed. in this paper, software design quality is emphasized. a general formalism for expressing software designs is presented, and a technique for identifying and counting software science parameters in design media is proposed.  paul a. szulewski mark h. whitworth philip buchan j. barton dewolf
pi: a case study in object-oriented programming  pi is a debugger written in c + +. this paper explains how object-oriented programming in c + + has influenced pi's evolution. the motivation for object- oriented programming was to experiment with a browser-like graphical user interface. the first unforeseen benefit was in the symbol table: lazy construction of an abstract syntax-based tree gave a clean interface to the remainder of pi, with an efficient and robust implementation. next, though not in the original design, pi was easily modified to control multiple processes simultaneously. finally, pi was extended to control processes executing across multiple heterogeneous target processors.  t. a. cargill