waashk/acm huggingface dataset:
efficient atomic broadcast using deterministic merge  we present an approach for merging message streams from producers distributed over a network, using a deterministic algorithm that is independent of any nondeterminism of the system, such as the amount of time the messages are delayed by the network, or their arrival order. thus, if this algorithm is replicated at multiple "mergers", then each merger will merge the message streams in exactly the same way. the technique is therefore a solution to atomic broadcast and global atomic multicast [12]. we assume that each producer has access to (approximately) synchronized clocks and can estimate the expected message rates of all producers. we propose an algorithm, called the bias algorithm. to measure the performance of the bias algorithm, we assume that messages are generated by memoryless processes operating at known message rates, and we measure the expected total merge delay at a given time l. for the case of two producer processes, we give optimal algorithms in this metric, and show that the optimal algorithm converges to our bias algorithm when l ⇒ ∞. we reconfirm our optimality result using dynamic programming theory, and we use simulations to validate the robustness of this optimality result under more realistic conditions.  marcos kawazoe aguilera robert e. strom
microtal - a machine-dependent, high-level microprogramming language  the design and implementation of a high-level microprogramming language is described. the language is a subset of an existing systems programming language, tal, which allows algorithms to be written and debugged using that language. the procedure may then be recompiled using the microtal compiler to produce a semantically equivalent microprogram which is accessed via an opcode rather than a procedure call. the microtal compiler automatically generates code to handle interrupts and page faults which may occur during the execution of the procedure.  joel f. bartlett
compiler support for garbage collection in a statically typed language  we consider the problem of supporting compacting garbage collection in the presence of modern compiler optimizations. since our collector may move any heap object, it must accurately locate, follow, and update all pointers and values derived from pointers. to assist the collector, we extend the compiler to emit tables describing live pointers, and values derived from pointers, at each program location where collection may occur. significant results include identification of a number of problems posed by optimizations, solutions to those problems, a working compiler, and experimental data concerning table sizes, table compression, and time overhead of decoding tables during collection. while gc support can affect the code produced, our sample programs show no significant changes, the table sizes are a modest fraction of the size of the optimized code, and stack tracing is a small fraction of total gc time. since the compiler enhancements are also modest, we conclude that the approach is practical.  amer diwan eliot moss richard hudson
prompter: a knowledge based support tool for code understanding  as an experiment for the application of knowledge-based techniques to large- scale software maintenance, a program called prompter which produces annotations for programs written in an assembly language is being developed. prompter adopts object-oriented approach and represents both hardware and programming knowledge as class/instance definitions. object-oriented representation helps decompose the knowledge and organize it in a hierarchical way. it is shown that most of conventions such as data definitions which are the major obstacles to understanding system programs can be well formalized in this framework.  koichi fukunaga
the apl 90 project: new directions in apl interpreters technology  this paper presents some aspects of a new implementation of apl, the apl 90 system.  this implementation includes concepts inherited from lisp, such as the notion of property lists, or the ability to manipulate simply the internal representation of user defined functions or operators. these two features allow a great flexibility both in describing the system and using it.  the work presented here is being implemented under unix on a sm 90 computer.  jean-jacques girardot
an adaptive tenuring policy for generation scavengers  one of the more promising automatic storage reclamation techniques, generation scavenging, suffers poor performance if many objects live for a fairly long time and then die. we have investigated the severity of this problem by simulating a two- generation scavenger using traces taken from actual 4-h sessions. there was a wide variation in the sample runs, with garbage- collection overhead ranging from insignificant, during three of the runs, to severe, during a single run. all runs demonstrated that performance could be improved with two techniques: segregating large bitmaps and strings, and adapting the scavenger's tenuring policy according to demographic feedback. we therefore incorporated these ideas into a commercial smalltalk implementation. these two improvements deserve consideration for any storage reclamation strategy that utilizes a generation scavenger.  david ungar frank jackson
improving data locality with loop transformations  in the past decade, processor speed has become significantly faster than memory speed. small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. in the this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. the model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. the cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. to validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. experiments illustrate that for kernels our model and algorithm can select and achieve the best loop structure for a nest. for over 30 complete applications, we executed the original and transformed versions and simulated cache hit rates. we collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. to our knowledge, these studies are the first of such breadth and depth. we found performance improvements were difficult to achieve bacause benchmark programs typically have high hit rates even for small data caches; however, our optimizations significanty improved several programs.  kathryn s. mckinley steve carr chau-wen tseng
user manuals: what does the user really need?  the purpose of the user manual is to assist the user in effectively operating a system. this objective is complicated by the wide diversity of user skills, and user tasks. the quality of a user manual is affected not only by the level of effort exerted by the system developer in writing the manual, but also by the degree of matching between the user manual and the user's needs. the documentation writer must supply both effort and direction in writing the user manual. this paper addresses the direction issue.  roy l. chafin
mixjuice (poster session): an object-oriented language with simple and powerful module mechanism  this paper describes an object-oriented language called _mixjuice_, which uses the differences of class hierarchies as a unit of information hiding and reuse. in this language, classes --- templates of objects --- and modules --- units of information hiding and reuse --- are completely orthogonal, thus supporting _separation of concerns_. mixjuice is basically based on java. however, its module mechanism is simpler and more powerful than that of java. the mixjuice programmers can make use of all java libraries and execution platforms1.  yuuji ichisugi
pc++/streams: a library for i/o on complex distributed data sources  the design and implementation of portable, efficient, and expressive mechanisms for i/o on complex distributed data structures---such as found in adaptive parallel applications---is a challenging problem that we address in this paper.  we describe the design, programmer interface, implementation, and performance of pc++/streams, a library that provides an expressive mechanism for i/o on distributed arrays of variable-sized objects in pc++, an object-parallel language. pc++/streams is intended for developers of parallel programs requiring efficient high-level i/o abstractions for checkpointing, scientific visualization, and debugging.  pc++/streams is an implementation of d/streams, a language-independent abstraction for buffered i/o on distributed data structures. we describe the d/streams abstraction and present performance results on the intel paragon and sgi challenge showing that d/streams can be implemented efficiently and portably.  jacob gotwals suresh srinivas dennis gannon
apl: a profitability language  sybron corporation is a diversified manufacturing company operating in twenty- one countries around the world. the complexity and geographical distribution of sybron operations have increased as the company has grown.  in the last eight years, innovative apl systems combined with an extensive communications network have provided corporate and division executives with powerful new tools for management decision making.  timely information is an invaluable resource. at sybron, it is available in similar form from common databases at appropriate levels of management regardless of geographical constraints.  the power to acquire, analyze and distribute information, however, is not an end in itself. it has positive impact on the corporate 'bottom line' only if it is continuously responsive to organizational goals and business objectives. sybron's organizational goal is to provide a favorable return on investment to our shareholders. apl systems are a valuable tool in achieving that objective.  william g. vonberg
the concert signature representation: idl as intermediate language  in the concert multilanguage distributed programming system, interface specification is the responsibility of programming languages, not separate idl. however, an idl is still necessary in order to define equivalence between declarations in different languages. a single representation is also desirable internally to economize on aspects of the implementation. consequently, concert has an idl as an intermediate language, produced by compiler front- ends and not normally manipulated by programmers. it is formally separated into a contract, which defines interoperability and an endpoint modifier, which captures the local choice of representation. only contracts are used to define interface equivalence. our choice of what kinds of information to put in the contract was motivated by a desire to be minimal, thereby enabling maximum feasible interoperability between different expressions of the same abstraction in the same or different languages.  joshua s. auerbach james r. russell
the software knowledge base  we describe a system for maintaining useful information about a software project. the "software knowledge base" keeps track of software components and their properties; these properties are described through binary relations and the constraints that these relations must satisfy. the relations and constraints are entirely user-definable, although a set of predefined libraries of relations with associated constraints is provided for some of the most important aspects of software development (specification, design, implementation, testing, project management).  the use of the binary relational model for describing the properties of software is backed by a theoretical study of the relations and constraints which play an important role in software development.  bertrand meyer
an extensible static analysis tool for cobol programs  software tools are an important part of the programming environment. perhaps one of the most pervasive type of software tools is the "static analyzer", as exemplified by cross reference listing tools, and call graph generators. in this paper, we describe an "extensible" static analysis tool (cesat) which is based on the use of a data base management system and associated query language. the use of the dbms query language allows an virtually unlimited number of tools to be easily constructed, resulting in an "extensible" software tool.  warren harrison
representing monads  we show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations". as part of the development, we extend meyer and wand's characterization of the relationship between continuation-passing and direct style to one for continuation-passing vs. general "monadic" style. we further show that the composable-continuations construct can itself be represented using ordinary, non-composable first-class continuations and a single piece of state. thus, in the presence of two specific computational effects - storage and escapes - any expressible monadic structure (e.g., nondeterminism as represented by the list monad) can be added as a purely definitional extension, without requiring a reinterpretation of the whole language. the paper includes an implementation of the construction (in standard ml with some new jersey extensions) and several examples.  andrzej filinski
retargetable compilation for low power  most research to date on energy minimization in dsp processors has focuses on hardware solution. this paper examines the software-based factors affecting performance and energy consumption for architecture-aware compilation. in this paper, we focus on providing support for one architectural feature of dsps that makes code generation difficult, namely the use of multiple data memory banks. this feature increases memory bandwidth by permitting multiple data memory accesses to occur in parallel when the referenced variables belong to different data memory banks and the registers involved conform to a strict set of conditions. we present novel instruction scheduling algorithms that attempt to maximize the performance, minimize the energy, and therefore, maximize the benefit of this architectural feature. experimental results demonstrate that our algorithms generate high performance, low energy codes for the dps architectural features with multiple data memory banks. our algorithm led to improvements in performance and energy consumption of 48.3% and 66.6% respectively in our benchmark examples.  wen-tsong shiue
cascaded refactoring for framework  refactoring of source code has been studied as a preliminary step in the evolution of object-oriented software. we extend the concept of refactoring to the whole range of models used to describe a framework in our methodology: feature model, use case model, architecture, design, and code. we view framework evolution as a two- step process: refactoring and extension. the refactoring step is a set of refactorings, one for each model, that cascades through them. the refactorings chosen for a model become the rationale or constraints for the choice of refactorings of the next model.  the cascading of refactorings is aided by the alignment of the models. alignment is a traceable mapping between models that preserves the commonality-variability aspects of the models.  greg butler lugang xu
mixin-based inheritance  the diverse inheritance mechanisms provided by smalltalk, beta, and clos are interpreted as different uses of a single underlying construct. smalltalk and beta differ primarily in the direction of class hierarchy growth. these inheritance mechanisms are subsumed in a new inheritance model based on composition of mixins, or abstract subclasses. this form of inheritance can also encode a clos multiple-inheritance hierarchy, although changes to the encoded hierarchy that would violate encapsulation are difficult. practical application of mixin- based inheritance is illustrated in a sketch of an extension to modula-3.  gilad bracha william cook
envy: a non-volatile, main memory storage system  this paper describes the architecture of envy, a large non-volatile main memory storage system built primarily with flash memory. envy presents its storage space as a linear, memory mapped array rather than as an emulated disk in order to provide an efficient and easy to use software interface.  flash memories provide persistent storage with solid-state memory access times at a lower cost than other solid-state technologies. however, they have a number of drawbacks. flash chips are write- once, bulk-erase devices whose contents cannot be updated in-place. they also suffer from slow program times and a limit on the number of program/erase cycles. envy uses a copy-on-write scheme, page remapping, a small amount of battery backed sram, and high bandwidth parallel data transfers to provide low latency, in-place update semantics. a cleaning algorithm optimized for large flash arrays is used to reclaim space. the algorithm is designed to evenly wear the array, thereby extending its lifetime.  software simulations of a 2 gigabyte envy system show that it can support i/o rates corresponding to approximately 30,000 transactions per second on the tpc-a database benchmark. despite the added work done to overcome the deficiencies associated with flash memories, average latencies to the storage system are as low as 180ns for reads and 200ns for writes. the estimated lifetime of this type of storage system is in the 10 year range when exposed to a workload of 10,000 transactions per second.  michael wu willy zwaenepoel
garp: a graphical/textual language for concurrent programming  concurrent systems in which the number of processes and their interconnections can change dynamically suffer from the problem of ensuring that process interconnections are correctly maintained at all times. we propose a hybrid solution to this problem in which processes are described textually, but interconnections are described graphically using a graph grammar to constrain the legal sets of processes and interconnections that the system may evolve. this paper discusses garp, a hybrid graphical/textual concurrent programming language that acts as a testbed for our ideas, and illustrates its use with an example.  s. m. kaplan s. k. goering
-coral: a multigrain, multithreaded processor architecture   recently popularized hardware multithreading (hmt) architectures, such as smt, multiscalar and terra do not provide flexible and efficient methods of thread management and synchronization in hardware. the α-coral architecture is a tool for investigation of a more dynamic approach to thread management. unlike other architectures, there are no strict requirements on timing and size of threads, and no static partitioning of resources. α-coral provides for simultaneous multiprogramming and multithreading environment, which is mostly managed in hardware. to other architectures, α-coral adds on demand register allocation, fast variable size thread creation and destruction, as well as quick synchronization through a shared register file. while other architectures attempt to port existing compilers, the α-coral architecture is supported by a custom compiler system. this system provides for a simple method of mapping hierarchical internal representation of the program to variable size threads.  this paper examines a new approach to hardware multithreading, involving minimal extensions to the instruction set of conventional risc superscalar architectures. the α-coral architecture and compiling support introduce a multi-grain multithreaded architecture which extends wide-superscalar processor cores to support hierarchical multithreading. a simulator was developed and results are presented to demonstrate the feasibility of our design approach.  mark n. yankelevsky constantine d. polychronopoulos
building awareness of system testing issues  managers of large software projects with system test groups face a problem that they may not be aware of. vague notions among project members about the role of system testing tend to cloud the relationship between developers and testers with misunderstanding and disappointment. the main source of the problem is unrealistic expectations about what can be accomplished during the system test phase of the project. this has the effect of de-emphasizing the developers' responsibility for software quality and imposing a definition of success on system testers that is not possible to achieve.  this paper describes a series of role awareness seminars at which a discussion technique was used to clarify expectations between developers and testers. transcending the discussion of roles was a fundamental message: the quality of software is determined during the development phase and cannot be radically improved during the system test phase.  n. h. petschenik
software reliability modeling accounting for program size variation due to integration or design changes  estimation of software reliability quantities has traditionally been on stable systems; i.e., systems that are completely integrated and are not undergoing design changes. also, it is assumed that test results are completely inspected for failures. this paper describes a method for relaxing the foregoing conditions by adjusting the lengths of the intervals between failures experienced in tests as compensation. the resulting set of failure intervals represents the set that would have occured for a stable system in its final configuration with complete inspection. the failure intervals are then processed as they would be for a complete system. the approach is developed for the execution time theory of software reliability, but the concepts could be applied to many other models the estimation of quantities of interest to the software manager are illustrated.  j. d. musa a. iannino
generic programming: apl and smalltalk  early generic concepts in programming languages were mixed-type arithmetic (e.g., "+" used with any combination of fixed- and floating-point numbers) and "print" functions which could be applied to any of a language's objects. generic concepts reduce the number of terms which must be remembered and permit considerable condensation of language design. three different paths in the development of generic-concept languages have been followed by apl, algol 68, and object-oriented languages such as simula 67 and smalltalk. apl was the earliest and one of the most interesting applications of generic-concept methods, but now makes the weakest use of these ideas.  my talk will use slides and movies to show how the message-object programming system smalltalk makes use of generic concepts embedded in class descriptions to give rise to a wide variety of simply programmed dynamic simulations including graphic animation, music synthesis, document layout and retrieval, and apl-like calculation features. many of these systems have been brought to life by child and adult novice programmers.  a short list of references is given for those wishing more introductory information about smalltalk.  alan c. kay
oop in the real world  some advocates of oop have promised that it will make all code reusable, shorten development cycles, remove the applications backlog, cure the common cold and plug the hole in the ozone layer.  how well does actual experience bear this out?  success stories are published much more often than failures and false starts. this is very unfortunate since the former two are often much more instructive.  this panel will attempt to bring the less successful experiences to light, and hopefully, will provide lessons on how to do better.  rick denatale charles irby john lalonde burton leathers reed phillips