waashk/acm huggingface dataset:
derive: a tool that automatically reverse-engineers instruction encodings  many binary tools, such as disassemblers, dynamic code generation systems, and executable code rewriters, need to understand how machine instructions are encoded. unfortunately, specifying such encodings is tedious and error-prone. users must typically specify thousands of details of instruction layout, such as opcode and field locations values, legal operands, and jump offset encodings. we have built a tool called derive that extracts these details from existing software: the system assembler. users need only provide the assembly syntax for the instructions for which they want encodings. derive automatically reverse-engineers instruction encoding knowledge from the assembler by feeding it permutations of instructions and doing equation solving on the output.  derive is robust and general. it derives instruction encodings for sparc, mips, alpha, powerpc, arm, and x86. in the last case, it handles variable- sized instructions, large instructions, instruction encodings determined by operand size, and other cisc features. derive is also remarkably simple: it is a factor of 6 smaller than equivalent, more traditional systems. finally, its declarative specifications eliminate the mis-specification errors that plague previous approaches, such as illegal registers used as operands or incorrect field offsets and sizes. this paper discusses our current derive prototype, explains how it computes instruction encodings, and also discusses the more general implications of the ability to extract functionality from installed software.  dawson r. engler wilson c. hsieh
a generic model for reflective design  rapid technological change has had an impact on the nature of software. this has led to new exigencies and to demands for software engineering paradigms that pay particular atttention to meeting them. we advocate that such demands can be met, at least in large parts, through the adoption of software engineering processes that are founded on a reflective stance. to this end, we turn our attention to the field of design rationale. we analyze and characterize design rationale approaches and show that despite surface differences between different approaches, they all tend to be variants of a relatively small set of static and dynamic affinities. we use the synthesis of static and dynamic affinities to develop a generic model for reflective design. the model is nonprescriptive and affects minimally the design process. it is context-independent and is intended to be used as a facilitator in participative design, supporting group communication and deliberation. the potential utility of the model is demonstrated through two examples, one from the world of business design and the other from programming language design
frequency interleaving as a codesign scheduling paradigm  frequency interleaving is introduced as a means of conceptualizing and co- scheduling hardware and software behaviors so that software models with conceptually unbounded state and execution time are resolved with hardware resources. the novel mechanisms that result in frequency interleaving are a shared memory foundation for all system modeling (from gates to software- intensive subsystems) and de-coupled, but interrelated time- and state- interleaved scheduling domains. the result for system modeling is greater accommodation of software as a configuration paradigm that loads system resources, a greater accommodation of shared memory modeling, and a greater representation of software schedulers as a system architectural abstraction. the results for system co-simulation are a lessening of the dependence on discrete event simulation as a means of merging physical and non-physical models of computation, and a lessening of the need to partition a system as computation and communication too early in the design. we include an example demonstrating its implementation.  joann m. paul simon n. peffers donald e. thomas
reliability mechanisms for adams  the goal of checkpointing in database management systems is to save database states on a separate secure device so that the database can be recovered when errors and failures occur. this paper presents a non-interfering checkpointing mechanism being developed for adams. instead of waiting for a consistent state to occur, our checkpointing approach constructs a state that would result by completing the transactions that are in progress when the global checkpoint begins. the checkpointing algorithm is executed concurrently with transaction activity while constructing a transaction-consistent checkpoint on disk, without requiring the database quiesce. this property of non-interference is highly desirable to real-time applications, where restricting transaction activity during the checkpointing operation is in many cases not feasible. two main properties of this checkpointing algorithm are global consistency and reduced interference, both of which are crucial for achieving high availability.  s. h. son j. l. pfaltz
sorting out signature schemes  digital signature schemes are a fundamental tool for secure distributed systems. it is important to have a formal notion of what a secure digital signature scheme is, so that there is a clear interface between designers and users of such schemes. a definition that seemed final was given by goldwasser, micali, and rivest in 1988, and although most signature schemes used in practice cannot be proved secure with respect to it, they are all built so that they hopefully fulfil it, e.g., by the inclusion of hash functions or redundancy to counter active attacks.  recently, however, several signature schemes with new security properties have been presented. most of them exist in several variants, and some of them pay for the new properties with restrictions in other respects, whose relation is not always clear. obviously, these new properties need definitions and some classification. unfortunately, however, none of the new schemes is covered by the definition mentioned above. hence the new properties cannot be defined as additions, but each new type of scheme needs a new definition from scratch, although there are similarities between the definitions. this is unsatisfactory.  this paper presents (an overview of) a general definition of digital signature schemes that covers all known schemes, and hopefully all that might be invented in future. additional properties of special types of schemes are then presented in an orthogonal way, so that existing schemes can be classified systematically.  it turns out that signature schemes are best defined by a separation of service, structure, and degree of security, with a service specification in temporal logic. several parts of such a definition can easily be reused for general definitions of other classes of cryptologic schemes.  relations to secure multi-party protocols and logics of authentication are discussed.  birgit pfitzmann
linear scan register allocation  we describe a new algorithm for fast global register allocation called linear scan. this algorithm is not based on graph coloring, but allocates registers to variables in a single linear-time scan of the variables' live ranges. the linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring. the algorithm is of interest in applications where compile time is a concern, such as dynamic compilation systems, "just-in-time" compilers, and interactive development environments.  massimiliano poletto vivek sarkar
an object-oriented approach to software process modeling and definition  this paper describes an approach to software process modeling that uses dragoon, an object-oriented programming language with ada-like syntax, to capture software process models. these models share the advantages of object- oriented software. they can be easily modified or extended. they allow the modeled process to be viewed at appropriate levels of abstraction. the use of a compilable programming language allows automated consistency checking and can help support automated enactment. dragoon is a particularly appropriate language for this task. it supports both full object-oriented programming, and concurrency.  john d. riley
a task- and data-parallel programming language based on shared objects  many programming languages support either task parallelism, but few languages provide a uniform framework for writing applications that need both types of parallelism or data parallelism. we present a programming language and system that integrates task and data parallelism using shared objects. shared objects may be stored on one processor or may be replicated. objects may also be partitioned and distributed on several processors.task parallelism is achieved by forking processes remotely and have them communicate and synchronize through objects. data parallelism is achieved by executing operations on partitioned objects in parallel. writing task-and data-parallel applications with shared objects has several advantages. programmers use the objects as if they were stored in a memory common to all processors. on distributed-memory machines, if objects are remote, replicated, or partitioned, the system takes care of many low-level details such as data transfers and consistency semantics. in this article, we show how to write task-and data-parallel programs with our shared object model. we also desribe a portable implementation of the model. to assess the performance of the system, we wrote several applications that use task and data parallelism and excuted them on a collection of pentium pros connected by myrinet. the performance of these applications is also discussed in this article.  saniya ben hassen henri e. bal ceriel j. h. jacobs
an operational requirement description model for open systems  requirement engineering has been successfully applied to many superficial problems, but there has been little evidence of transfer to complex system construction. in this paper we present a new conceptual model which is for incomplete requirement descriptions. the model is especially designed for supporting the requirement specification and the analysis of open systems. an analysis of existing models and languages shows the main problem in requirement engineering: the harmony between a well-defined basic model and a convenient language. the new model remos combines the complex requirements of open systems with the basic characteristics of transaction-oriented systems. transaction-oriented systems are fault-tolerant and offer security and privacy mechanisms. such systems provide such excellent properties - why don't we already profit from it during requirement specification? the model remos and the applicative language relos take advantage of transaction properties. the idea remos is based on is the definition of scenarios and communicating subsystems. remos guides the users to making their requirements more clear, and relos offers a medium for requirement definition.  m. hallman
comparison of the functional power of apl2 and fortran 90 apl and fortran, although very different, share the challenge of remaining "competitive" in the light of an onslaught of "modern" computer languages. to meet this challenge, both have attempted to enhance their position by adding significant new features to their language. for example, apl2 is an extension of apl.fortran has also attempted to meet the challenges of modern programming by developing a new fortran standard called fortran 90. this standard revises many areas of fortran, but this paper will only concentrate on those that affect the computational power of fortran. many of the changes were motivated by the increased use of vector and array "supercomputers." therefore, array features, the ability to act on entire arrays instead of individual elements, are an important part of this new standard. in doing this work, the fortran community looked to apl as an example of a powerful array language.this paper will answer several questions regarding this new standard. first, from a computational or functional point of view, what are the major features of fortran 90? next, how do these features compare with apl2? and finally, what can apl2 learn from the fortran 90 work? robert g. willhoft
graphically-oriented reverse engineering tools for ada software (abstract)  computer professionals have long promoted the idea that graphical representations of software are extremely useful as comprehension aids when used to supplement textual descriptions and specifications of software, especially for large complex systems. the general goal of this research is the study and formulation of graphical representations of algorithms, structures, and processes for ada (grasp/ada). the research is presently focused on the extraction and generation of graphical representations from ada source code to directly support the process of reverse engineering.  our primary motivation for reverse engineering is increased support for software reusability and software maintenance. while applications written in ada may seem somewhat young to benefit from reverse engineering, nasa and others are quickly amassing libraries of ada packages. both reuse and maintenance should be greatly facilitated by automatically generating a set of "formalized diagrams" to supplement the source code and other forms of existing documentation.  the first tool implemented was the control structure diagram (csd generator. the csd is representative of a new group of graphical representations for algorithms that can co-exist with pdl or source code. the csd generator has the potential to increase the comprehensibility of ada pdl and/or source code, which may have wide-ranging implications for the design, implementation, and maintenance of software written in ada. in particular, the tool can provide graphical representations which are more easily understood than their textual equivalents. graphical aids which can increase the efficiency of understanding will ultimately reduce the overall cost of software.  james h. cross
implementaion of a parallel subsumption algorithm (abstract only)  many current automated theorem provers use a refutation procedure based on some version of the principle of resolution. these methods normally lead to the generation of large numbers of new clauses. subsumption is a process that eliminates the superfluous clauses from the clause space, thus speeding up the proof. the research presented here is concerned with the design and implementation of a subsumption algorithm which exploits the parallelism provided by a multiprocessor. all coding is being done in the programming language c, for portability. monitors [1] are used as the synchronization mechanism. correct performance in both a multiprocessor and uniprocessor mode has been stressed. the parallel tests are run on a denelcor hep located at argonne national laboratories.  ralph m. butler arlan r. dekock
a software science analysis of programming size  programming development at ibm's santa teresa laboratory has been investigating "the elements of software science" as defined by maurice h. halstead.1,2 this report summarizes the findings after several large ibm products have been counted and analyzed. program vocabulary, length, volume and lines of code are discussed and compared. it is shown that the size of a program can be estimated with reasonable accuracy once the vocabulary is known.  within the programming community the traditional measures of quality and productivity have been based upon the number of lines of source statements which have been coded for a given product. estimating the costs, time duration, number of programmers required, and quality levels also hinge upon "lines-of-code" predictions for the product. maurice h. halstead 1,2 has suggested a comprehensive set of software metrics which we are using to examine the characteristics of existing program products. these software metrics do not hinge upon lines-of- code counts but rather upon the counting of operators and operands. this report explains how the "elements of software science" as defined by professor halstead relate to ibm data from large programming products. the software science formulas are neither derived nor altered in this paper but are treated as theorems which we have set out to prove or to disprove by measuring santa teresa laboratory program products. we were motivated to look for measures other than lines-of-code because of our historic inability to estimate the size of a project with any consistent degree of accuracy. in performing this study, we have counted and analyzed large volumes of existing program product code. this report focuses upon the software science size metrics (length and volume) in comparison to the traditional lines-of-code measure.  charles p. smith
software counting rules: will history repeat itself?  counting rules in the software metrics field have been developed for counting such software measurables as the occurence of operators, operands and the number of lines of code. a variety of software metrics, such as those developed by halstead and others, are computed from these numbers. published material in the software metrics field has concentrated on relationships between various metrics, comparisions of values obtained for different languages, etc. yet, little, if anything has been published on assumptions, experimental designs, or the nature of the counting tools (or programs) themselves used to obtain the basic measurements from which these metrics are calculated.  mitchell g. spiegel
chime: a metadata-based distributed software development environment  we introduce chime, the columbia hypermedia immersion environment, a metadata- based information environment, and describe its potential applications for internet and intranet-based distributed software development. chime derives many of its concepts from multi-user domains (muds), placing users in a semi- automatically generated 3d virtual world representing the software system. users interact with project artifacts by "walking around" the virtual world, where they potentially encounter and collaborate with other users' avatars. chime aims to support large software development projects, in which team members are often geographically and temporally dispersed, through novel use of virtual environment technology. we describe the mechanisms through which chime worlds are populated with project artifacts, as well as our initial experiments with chime and our future goals for the system.  stephen e. dossick gail e. kaiser
a model and compilation strategy for out-of-core data parallel programs  it is widely acknowledged in high-performance computing circles that parallel input/output needs substantial improvement in order to make scalable computers truly usable. we present a data storage model that allows processors independent access to their own data and a corresponding compilation strategy that integrates data-parallel computation with data distribution for out-of- core problems. our results compare several communication methods and i/o optimizations using two out-of-core problems, jacobi iteration and lu factorization.  rajesh bordawekar alok choudhary ken kennedy charles koelbel michael paleczny
multilevel atomicity - a new correctness criterion for database concurrency control  multilevel atomicity, a new correctness criteria for database concurrency control, is defined. it weakens the usual notion of serializability by permitting controlled interleaving among transactions. it appears to be especially suitable for applications in which the set of transactions has a natural hierarchical structure based on the hierarchical structure of an organization. a characterization for multilevel atomicity, in terms of the absence of cycles in a dependency relation among transaction steps, is given. some remarks are made concerning implementation.  nancy a. lynch
assembler utility functions for apl2/pc some general guidelines are discussed on why and how to develop utility functions in assembler for the apl2/pc environment. assembler utility functions may replace some most heavily used idiomatic apl auxiliary functions and boost the efficiency of apl applications. about twenty such functions are presented, some of them perhaps useful as temporary extensions of the apl2/pc interpreter. the collection of assembler utility functions is available in the public domain, and should be extended by the joint efforts of the international apl community. tauno ylinen
replica management in real-time ada 95 applications in this paper, we present some of the fault tolerance management mechanisms being implemented in the multi-mu- architecture, namely its support for replica non-determinism. in this architecture, fault tolerance is achieved by node active replication, with software based replica management and fault tolerance transparent algorithms. a software layer implemented between the application and the real- time kernel, the fault tolerance manager (ftmanager), is the responsible for the transparent incorporation of the fault tolerance mechanismsthe active replication model can be implemented either imposing replica determinism or keeping replica consistency at critical points, by means of interactive agreement mechanisms. one of the multi-mu architecture goals is to identify such critical points, relieving the underlying system from performing the interactive agreement in every ada dispatching point. luís miguel pinho francisco vasques
an intelligent dynamic load balancer for workstation clusters a key issue of dynamic load balancing in a loosely couple distributed system is selecting appropriate jobs to transfer. in this paper, a job selection policy based on on-line predicting behaviors of jobs is proposed. tracing is used at the beginning of execution of a job to predicate the approximate execution time and resource requirements of the job to make a correct decision about whether transferring the job is worthwhile. a dynamic load balancer using the job selection policy has been implemented. experimental measurement results show that it is able to improve mean response time of jobs and resource utilization of systems substantially compared with the one without selecting job policy. jiubin ju gaochao xu kun yang
an evaluation of a compiler optimization for improving the performance of a coherence directory  both hardware-controlled and compiler-directed mechanisms have been proposed for maintaining cache coherence in large-scale shared-memory multiprocessors, but both of these approaches have significant limitations. we examine the potential performance improvement of a new software-hardware controlled cache coherence mechanism. this approach augments the run-time information available to a directory-based coherence mechanism with compile-time analysis that statically identifies write references that cannot cause coherence problems and writes that should be written through to memory. these references are marked as not needing to send invalidation messages to thereby reduce the network traffic produced by the directory while maintaining cache consistency. for those memory references that are ambiguous, due to conditional branches, or due to the need for complex data flow analysis, for instance, the compiler conservatively marks the references and relies on the hardware directory to ensure coherence. trace-driven simulations are used to emulate the compile- time analysis on memory traces and to estimate potential performance improvement that could be expected from a compiler performing this optimization on the perfect club benchmark programs. by reducing the number of invalidations, this optimized directory scheme is capable of reducing the processor-memory network traffic by up to 54 percent compared to an unoptimized directory mechanism. in addition, the overall miss ratio can be reduced up to 42 percent due to a corresponding reduction in the number of write misses.  farnaz mounes-toussi david j. lilja zhiyuan li