bluuebunny/crossref_metadata_2025_split huggingface dataset:
Methods for saving and restoring register values across function calls
Authors: Davidson Jack W. , Whalley David B. 
Published: November 2006

AbstractThe method used to save and restore the values of registers across function calls can affect performance and influence the design of specific instructions. This paper describes the results of an experiment that empirically evaluated six different schemes for saving and restoring registers on CISC machines. The methods do not require special hardware or interprocedural analysis to be performed. The six schemes were logically divided into two classes. Three of the techniques do not require the compiler to perform data‐flow analysis, whereas the other three schemes do. Within each class one scheme delegates the responsibility of preserving the state of the registers to the calling function. The second scheme of each class delegates the responsibility of saving the registers to the function being called. In the third scheme of the two classes, the registers are partitioned into two disjoint sets. The calling function is responsible for preserving register values in one of the sets whereas the called function is responsible for the other set. For each class the third scheme is shown to produce the most effective code.
Implementing a user interface management system for existing applications using an object‐oriented database tool
Authors: Hardwick Martin , Uejio Wayne , Spooner David , Czechowski Joe , Lohr Phil , Sarachan Brion 
Published: November 2006

AbstractNumerous engineering application systems have been developed over the past twenty years, and many of these applications will continue to be used for many years to come. Examples of such applications include CAD Systems, finite‐element analysis packages and inspection systems. Because many of these applications were developed before graphical workstations became available, they often have simple command‐line user interfaces. Thus, there is a need for a graphical user interface management system (UIMS) that can be used to build point‐and‐click style interfaces for these existing engineering applications.In this paper we describe such a UIMS, and discuss its implementation using an object‐oriented database tool. This UIMS allows users to create and modify user interfaces by editing graphical representations of the interfaces, thus eliminating the need to write code to build or modify an interface. The UIMS is implemented using an object‐oriented database tool to take advantage of the data manipulation and storage management capabilities it provides. This approach reduces both the quantity and complexity of the code needed to implement the UIMS. It also allowed the UIMS to be implemented in a minimal amount of time.
Correcting a widespread error in unification algorithms
Authors: Norvig Peter 
Published: November 2006

AbstractThe unification of two patterns both containing variables is a ubiquitous operation in logic programming and in many artificial intelligence applications. Thus, many texts present unification algorithms. Unfortunately, at least seven of these presentations are incorrect. The common error occurs when logic variables are represented as binding lists; implementations that destructively update variable cells do not manifest the error. This note gives the examples that uncover the error and presents a correction.
A hybrid implementation of a process‐oriented programming language for system simulation
Authors: Rozin Roman , Treu Siegfried 
Published: November 2006

AbstractThe implementation of a hierarchical, process‐oriented programming language for simulation (HSL) is described. It features a hybrid approach, involving the front end of a compiler and the back end of an interpreter. An HSL program is dichotomous in structure. Source statements from each part are translated into three‐address code for an abstract machine, and the resulting code is then interpreted. The algorithms and the supportive data structures that effect the translation and interpretation of HSL are detailed. The host language for HSL is C++. HSL is machine independent and can be ported to any machine on which the host language is available. Its initial implementation was carried out on an NCR Tower. More recently, it was transferred to an NCR PC916.
Style control in the quill document editing system
Authors: Wolfsthal Yaron 
Published: November 2006

AbstractA critical problem in the design of editors for structured documents is that of style control, i.e. mapping the logical elements of the documents to their physical appearance on pages. This paper presents a novel approach to style control, used in the Quill document editing system that has been prototyped at the IBM Almaden Research Center. In our approach, the style control mechanism is an integral part of the editing system and consistent with the overall system architecture, in both its inner structure and its user interface. Properties that specify the formatting process, together with action routines for specifying complex semantics, are the basic style control primitives in the proposed approach.
Reducing and manipulating complex trace data
Authors: Touati Hervé , Smith Alan Jay 
Published: November 2006

AbstractIn performance analysis of computer systems, trace‐driven simulation techniques have the important advantage of credibility and accuracy. Unfortunately, traces are usually difficult to obtain, and little work has been done to provide efficient tools to help in the process of reducing and manipulating them. This paper presents TRAMP, a tool for the data reduction and data analysis phases of trace‐driven simulation studies. TRAMP has three main advantages: it accepts a variety of common trace formats; it provides a programmable user interface in which many actions can be directly specified; and it is easy to extend. TRAMP is particularly helpful for reducing and analysing complex trace data, such as traces of file system or database activity. This paper presents the design principles and implementation techniques of TRAMP and provides a few concrete examples of the use of this tool.
Perly—Unix with buttons
Authors: Hesketh Richard 
Published: November 2006

AbstractModern UNIX‐based graphical workstations still lack really graphical interfaces. Yet recreating existing UNIX tools with graphical interfaces may prove to be a prohibitive task. This paper describes the design and implementation of a set of tools that make the task of providing a graphical UNIX user interface easier. The main tool, called Perly, provides on‐screen graphical buttons connected to UNIX command scripts. When a button is pressed, the associated command script is executed. The buttons are highly configurable, encouraging users to tailor and extend their workstation environment. The idea of onscreen buttons with underlying programmable scripts comes from the work done at Xerox EuroPARC into user‐tailorable systems. Descriptions of Perly buttons are held in plain text files, allowing them to be given to other users via electronic mail. Examples of the use of buttons and the ideas behind the implementation of Perly buttons under the X Window System are discussed.
EcliPse: A system for high performance concurrent simulation
Authors: Sunderam V. S. , Rego Vernon J. 
Published: November 2006

AbstractA description of a system which provides for the concurrent execution of stochastic simulation applications is presented. The EcliPSe system provides high‐level simulation primitives that enable common sawlation tasks. An application programmer describes the simulation process in terms of these primitives using a sequential computation model. The system transparently replicates appropriate sections of the simulation when the program is executed on a concurrent system. By binding to machine‐dependent versions of the EcliPSe library, the simulation program can execute without modification on a variety of architectures including uniprocessors, hypercubes, shared‐memory machines and loosely coupled networks. In those experiments conducted, near‐linear speed‐ups were obtained. The main design aspects of the system, salient implementation features and performance figures for some simulation applications are presented. The usefulness of the system for more general applications is also discussed.
Fast string searching
Authors: Hume Andrew , Sunday Daniel 
Published: November 2006

AbstractSince the Boyer‐Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers.These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer‐Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.
The distributed ada run‐time system darts
Authors: Göthe M. Carlsson , Wengelin D. , Asplund L. 
Published: November 2006

AbstractA distributed Ada run‐time system, DARTS, is presented. DARTS is used with a source code transformation method for pre‐partitioning, and it also allows a late configuration. A single program can be partitioned to run on a loosely coupled multiprocessor system. The distributed units are tasks, task objects, packages, variables, procedures and functions. Task objects can by dynamically distributed. High fault tolerance is assured by unit redistribution. Design decisions, implementation details and ideas are presented.
Case study: Using its style tools to implement IBM's CUA‐2 user interface style
Authors: Ukelson Jacob P. , Gould John D. , Boies Stephen J. , Wiecha Charles 
Published: November 2006

AbstractIn an empirical case study of software tools, two participants used the ITS style designer's language to implement a general purpose, executable, rule‐based user interface style. This language allows style designers to select, combine and modify rule prototypes in order to construct a rule‐based user interface style. The participants implemented the entire IBM CUA‐2 user interface style, plus nine additional human‐computer interaction techniques, in 5–7 person‐weeks. This is impressive productivity. Typically the time to complete a single CUA‐2 application is measured in person‐years, not person‐weeks. The style implemented here is reusable by any ITS‐implemented application. The achievement reported here shows that about half the work of all ITS‐implemented CUA‐2 applications has been completed in a few person‐weeks. This result demonstrates the power and productivity of the ITS approach and tools. The results of this case study showed that key ‘ready‐mades’ (e.g. named attribute groups) provided in the style designer's toolkit could be used intact, which is important for importing or exporting interaction techniques from one style to another style. The results generalize to other computer‐literate designers who may want to use these tools to create other user interface styles.
Using profile information to assist classic code optimizations
Authors: Chang Pohua P. , Mahlke Scott A. , Hwu Wen‐Mei W. 
Published: November 2006

AbstractThis paper describes the design and implementation of an optimizing compiler that automatically generates profile information to assist classic code optimizations. This compiler contains two new components, an execution profiler and a profile‐based code optimizer, which are not commonly found in traditional optimizing compilers. The execution profiler inserts probes into the input program, executes the input program for several inputs, accumulates profile information and supplies this information to the optimizer. The profile‐based code optimizer uses the profile information to expose new optimization opportunities that are not visible to traditional global optimization methods. Experimental results show that the profile‐based code optimizer significantly improves the performance of production C programs that have already been optimized by a high‐quality global code optimizer.
An investigation into concurrent semantic analysis
Authors: Seshadri V. , Wortman D. B. 
Published: November 2006

AbstractConcurrency is an attractive method for reducing the execution time of compilers. By dividing source programs into segments which can be compiled concurrently, the task of compiling programs can be accelerated.Many of the difficult problems which arise when constructing a concurrent compiler occur in the implementation of the semantic analyser. This paper investigates the problems involved in designing the semantic analyser for a concurrent compiler for a modern, block‐structured language. Several approaches to solving the problems which arise are presented. These solutions are then implemented as part of a concurrent Modula‐2 + compiler, running on a shared memory multiprocessor. A performance evaluation of these semantic analysers is presented.
Towards a toolkit for building language implementations
Authors: Fédèle Carine , Lecarme Olivier 
Published: November 2006

AbstractThe current work of the authors in the area of software tools for automatic construction of compilers is described. This focuses on attempts to provide for automatic production of the semantic‐analysis and intermediate‐code‐generation parts of the Cigale compiler‐writing system, developed at the University of Nice. This work relies on use of the Amsterdam Compiler Kit (ACK) to ensure a full set of optimizers and code generators based on a semi‐universal intermediate language, and, therefore, emphasizes the filling of the gap between parsing and the intermediate language. It is intended as a pragmatic contribution to the automation of the production of true compilers (rather than mere program evaluators) that generate efficient machine code.
Hypertext development using a model‐based approach
Authors: Schwabe Daniel , Caloini Andrea , Garzotto Franca , Paolini Paolo 
Published: November 2006

AbstractHypertext development is still, for the most part, at the ‘handcrafting’ level, where each hypertext document must be hand‐designed. We present a compiler which takes hyperdocuments designed using a model‐based approach and generates stacks executable in Hyper Card. This compiler is implemented in standard SQL over a relational database representation of a hyperdocument designed using the hypermedia design model (HDM). The compiling approach, even though illustrated with HDM, can be used with any ‘structured’ design methodology.
The design and implementation of dynamic hashing for sets and tables in icon
Authors: Griswold William G. , Townsend Gregg M. 
Published: November 2006

AbstractTwo key features in the Icon programming language are tables and sets. An Icon program may use one large set or table, or thousands of small ones. To improve space and time performance for these diverse uses, their hashed data structures were reimplemented to dynamically resize during execution, reducing the minimum space requirement and achieving constant‐time access to any element for virtually any size set or table. The implementation is adapted from Per‐Åke Larson's dynamic hashing technique by using well‐known base‐2 arithmetic techniques to decrease the space required for small tables without degrading the performance of large tables. Also presented are techniques to prevent dynamic hashing from interfering with other Icon language features. Performance measurements are included to support the results.
An evaluation of self‐adjusting binary search tree techniques
Authors: Bell Jim , Gupta Gopal 
Published: November 2006

AbstractMuch has been said in praise of self‐adjusting data structures, particularly self‐adjusting binary search trees. Self‐adjusting trees are most suited to skewed key‐access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst‐case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self‐adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key‐access‐frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self‐adjusting trees, in almost all cases the AVL tree outperforms all the self‐adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self‐adjusting trees. Self‐adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition.
Object identification in the lego kernel
Authors: Hughes Larry 
Published: November 2006

AbstractIn a message‐based operating system, the kernel is responsible for forwarding messages to destination objects using a destination identifier. Part of the kernel overhead in processing the message involves mapping the identifier into a network address. This paper describes how the choice of identifier structure has simplified the techniques used by the Lego kernel when handling messages, notably: minimizing the overheads associated with address mapping, eliminating the reception of unwanted network packets, while permitting both individual (unicast) and group (multicast) communications.
A performance comparison of event calendar algorithms: An empirical approach
Authors: Chung Kehsiung , Sang Janche , Rego Vernon 
Published: November 2006

AbstractWe propose a suite of tests based on two‐state Markov chains for experimentally assessing the dynamic performance of a variety of simulation event calendar implementations. In contrast to previous studies based on the standard hold model for evaluation of performance statically, the proposed Markov hold model is more general and can be used to examine how different implementations respond dynamically to dependent sequences of insertion and deletion requests. The Markov hold model is used to conduct tests based on random, stressed, and correlated input sequences of requests, with performance measures including completion times, sensitivity to correlations, sensitivity to duplication, and efficiency of data‐handling. We apply these tests to fourteen different event calendar implementations. To demonstrate the utility of the proposed model, we also include a comparison of the event calendar algorithms on a token ring protocol with bursty Markovian packet‐traffic.
Guarded attribute grammars
Authors: Frost R. A. 
Published: November 2006

AbstractContrary to a widely‐held belief, it is possible to construct executable specifications of language processors that use a top‐down parsing strategy and which have structures that directly reflect the structure of grammars containing left‐recursive productions. A novel technique has been discovered by which the non‐termination that would otherwise occur is avoided by ‘guarding’ top‐down left‐recursive language processors by non‐left‐recursive recognizers. The use of a top‐down parsing strategy increases modularity and the use of left‐recursive productions facilitates specification of semantic equations. A combination of the two is of significant practical value because it results in modular and expressively clear executable specifications of language processors. The new approach has been tested in an attribute grammar programming environment that has been used in a number of projects including the development of natural language interfaces, SQL processors and circuit design transformers within a VLSI design package.
Multiple‐length division revisited: A tour of the minefield
Authors: Hansen Per Brinch 
Published: November 2006

AbstractLong division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.
Signature‐check based unification filter
Authors: Maeda Alfredo M. , Aoe Jun‐Ichi , Tomabechi Hideto 
Published: November 2006

AbstractAmong the different processes that entail unification‐based grammar parsing, the unification of feature structures is by far the most expensive one in terms of execution time. Unification of the feature structures of a given sentence typically takes between 85 and 98 per cent of the total elapsed time during parsing, thus the need to develop faster unification methods. The approach presented in this paper is based on the fact that, in general, between 60 and 85 per cent of unifications attempted in a typical parse result in failure. Our claim is that the efficient treatment of such unification failures reduces unification time significantly. In this paper we present what we call a unification filter or U‐filter, that preprocesses the feature structures to be unified. If the U‐filter succeeds, unification is then skipped because the attempt to unify the involved structures would result in failure. On the other hand, when the U‐filter does not succeed it is not possible to determine at that moment whether or not the structures unify, so unification is performed. The U‐filter stops around 87 per cent of unification failures, and speeds up unification time by an average of around 29 per cent over quasi‐destructive graph unification, the fastest unification method known so far.
Automatic synthesis of state machines from trace diagrams
Authors: Koskimies Kai , Mäkinen Erkki 
Published: November 2006

AbstractThe automatic synthesis of state machines describing the behaviour of a class of objects in object‐oriented software modelling is studied. It is shown that the synthesis can be carried out on the basis of trace diagrams giving possible sequences of events during the execution of the system. An algorithm originally developed for the automatic construction of programs on the basis of their execution traces is applied to the problem, and an experimental state machine synthesizer is implemented. It is demonstrated that such a synthesizer is a highly useful component in a practical object‐oriented CASE system.
The application of prolog to structured design
Authors: Tse T. H. , Chen T. Y. , Chan F. T. , Chen H. Y. , Xie H. L. 
Published: November 2006

AbstractIn this paper, we investigate the feasibility of applying logic programming to structured design. We propose to use Prolog as a common machinery for the representation of various structured tools. We illustrate through examples how to produce structure charts from data flow diagrams, and evaluate them according to commonly recommended design guidelines. If the structure charts produced are not satisfactory, the inherent backtracking mechanism in Prolog will help to produce other versions for further evaluation.
Complex performance measurements with NICE (Notation for interval combinations and events)
Authors: Woodside C. Murray , Schramm Cheryl 
Published: November 2006

AbstractThis paper presents a notation for extracting complex performance measurements of parallel software from an event log. NICE defines a ‘complex interval’ as a sequence of events in the event log that match a rather general template using an interval monitor process (IMP). The IMP process model combines an extended FSM with parametrized event descriptors to provide a generalized description of a sequence of subintervals each one of which may be measured for duration. An interval matching algorithm provides a strategy for distributing the events in the log to multiple concurrent IMPs, thereby handling interval occurrences that overlap and/or share the same event. Practical issues of implementing and using NICE are addressed in a discussion of our performance monitoring tool called Finale.