bluuebunny/crossref_metadata_2025_split huggingface dataset:
Differential evaluation: A cache‐based technique for incremental update of graphical displays of structures
Authors: Dunlavey Michael R. 
Published: November 2006

AbstractMany applications of graphical man‐machine interfaces require incremental update of an image, with controllable time granularity, having multiple views of the information, generated by modular, maintainable software having minimal resource overhead. A technique called differential evaluation is presented that addresses these needs. Instead of driving the display from a data structure, it uses an ad‐hoc display procedure in conjunction with a FIFO cache to generate and maintain the display. Maintaining displays of variable structure is accomplished through the use of conditional mechanisms in the display procedure. The technique has been extended to meet many different needs, such as the use of graphic contexts, display of overlapping objects, double‐buffering, and a variety of user input schemes. The efficiency of the technique, in time and storage, permits its use with modest equipment. It has been used for several years in a number of industrial user interfaces.
A distributed development environment for embedded software
Authors: Tzou Shin‐Yuan , Lim Jyh‐Jang , Menon Jai , Palmer David 
Published: November 2006

AbstractThe HAGAR project is building a high‐performance disk controller. It is an embedded system for which many hundreds of thousands of lines of embedded software will have to be developed concurrently with the development of the hardware. We found existing methods for embedded software development, such as simulation and remote cross development, to be inadequate for us. To meet our special needs, we developed a distributed development environment that combines and extends the capabilities of existing methods while fixing their drawbacks.Our environment is based on a processor‐pool architecture, in which multiple hardware sets are pooled and managed systematically. It supports embedded software development for many programmers at different sites. It allows for the emulation of non‐existing hardware adaptor cards and for the integration of embedded software testing with hardware simulation. The environment provides a single system image, hiding many hardware and configuration details from its users. From the perspective of the programmers, our environment makes developing embedded software for special hardware systems as easy as developing application programs for a UNIX workstation.
Engineering a sort function
Authors: Bentley Jon L. , McIlroy M. Douglas 
Published: November 2006

AbstractWe recount the history of a new qsortfunction for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.
Making C++ objects persistent: The hidden pointers
Authors: Biliris A. , Dar S. , Gehani N. H. 
Published: November 2006

AbstractC++ objects of types that have virtual functions or virtual base classes contain volatile (‘memory’) pointers. We call such pointers ‘hidden pointers’ because they were not specified by the user. If such C++ objects are made persistent, then these pointers become invalid across program invocations. We encountered this problem in our implementation of O++, which is a database language based on C++. O++ extends C++ with the ability to create and access persistent objects.In this paper, we describe the hidden pointers problem in detail and present several solutions to it. Our solutions are elegant in that they do not require modifying the C++ compiler or the semantics of C++. We also discuss another problem that arises because C++ allows base class pointers to point to derived class objects. C++ has emerged as the de facto standard language for software development, and database systems based on C++ have attracted much attention. We hope that the details and techniques presented will be useful to database researchers and to implementors of object‐oriented database systems based on C++.
QD‐Janus: A sequential implementation of Janus in Prolog
Authors: Debray Saumya K. 
Published: November 2006

AbstractJanus is a language designed for distributed constraint programming. This paper describes QD‐Janus, a sequential implementation of Janus in Prolog. The compiler uses a number of novel analyses and optimizations to improve the performance of the system. The choice of Prolog as the target language for a compiler, although unusual, is motivated by the following: (i) the semantic gap between Janus and Prolog is much smaller than that between Janus and, say, C or machine language—this simplifies the compilation process significantly, and makes it possible to develop a system with reasonable performance fairly quickly; (ii) recent progress in Prolog implementation techniques, and the development of Prolog systems whose speeds are comparable to those of imperative languages, indicates that the translation to Prolog need not entail a significant performance loss compared to native code compilers; and (iii) compilation to Prolog can benefit immediately from a significant body of work on, and implementations of, parallel Prolog systems. Our experience indicates that translation of logic programming languages to Prolog, accompanied by the development of good program analysis and optimization tools, is an effective way to quickly develop flexible and portable implementations with good performance and low cost.
Experiences in database system implementation using a persistent programming language
Authors: Hanson Eric N. , Harvey Tina M. , Roth Mark A. 
Published: November 2006

AbstractThe EXODUS database toolkit, and in particular the E persistent programming language, have been used in two substantial database system implementation efforts by the authors, the Ariel database rule system and the Triton nested relation DBMS. An important advantage of using a persistent programming language for database system implementation is that it is easy to implement special‐purpose persistent objects used by the DBMS such as catalogs, rule indexes, and nested relational structures. Support for transactions built into a persistent programming language greatly reduces the effort required to implement a database system. A disadvantage observed is that it is not possible to map the type system of the DBMS to the type system of the underlying programming language while still retaining good performance for ad hoc queries. Also, software engineering difficulties arise when a persistent language makes a distinction between database types and main‐memory types.
Executing continuation semantics: A comparison
Authors: Slonneger Ken 
Published: November 2006

AbstractSeveral authors have suggested translating denotational semantics into prototype interpreters written in high‐level programming languages to provide evaluation tools for language designers. These implementations have generally been understandable when restricted to direct denotational semantics. This paper considers using two declarative programming languages, Prolog and Standard ML, to implement an interpreter that follows the continuation semantics of a small imperative programming language, called Gull. Each of the two declarative languages presents certain difficulties related to evaluation strategies and expressiveness. The implementations are compared in terms of their ease of use for prototyping, their resemblance to the denotational definitions, and their efficiency.
Using the programming walkthrough to aid in programming language design
Authors: Bell Brigham , Citrin Wayne , Lewis Clayton , Rieman John , Weaver Robert , Wilde Nick , Zorn Benjamin 
Published: November 2006

AbstractThe programming walkthrough is a method for assessing how easy or hard it will be for users to write programs in a programming language. It is intended to enable language designers to identify problems early in design and to help them choose among alternative designs. We describe the method and present experience in applying it in four language design projects. Results indicate that the method is a useful supplement to existing design approaches.
Scalar replacement in the presence of conditional control flow
Authors: Carr Steve , Kennedy Ken 
Published: November 2006

AbstractMost conventional compilers fail to allocate array elements to registers because standard data‐flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating‐point registers, which are most often used as temporary repositories for subscripted variables.This paper presents a source‐to‐source transformation, called scalar replacement, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The scalar replaced variables are more likely to be assigned to registers by the coloring‐based register allocators found in most compilers than are their unreplaced counterparts. The algorithm presented here extends previous techniques for scalar replacement by allowing the presence of forward conditional control flow within loop bodies through the mapping of partial redundancy elimination to scalar replacement. Finally, experimental results show that scalar replacement is extremely effective. On kernels, integer‐factor improvements over code generated by a good optimizing compiler of conventional design are possible.
Fast string matching using an n‐gram algorithm
Authors: Kim Jong Yong , Shawe‐Taylor John 
Published: November 2006

AbstractExperimental results are given for the application of a new n‐gram algorithm to substring searching in DNA strings. The results confirm theoretical predictions of expected running times based on the assumption that the data are drawn from a stationary ergodic source. They also confirm that the algorithms tested are the most efficient known for searches involving larger patterns.
Efficient timestamp input and output
Authors: Dyreson Curtis E. , Snodgrass Richard T. 
Published: November 2006

AbstractIn this paper we provide efficient algorithms for converting between timestamp values that signify some number of seconds from an arbitrary origin, and character strings specifying Gregorian dates, such as ‘January 1, 1993’. We give several algorithms that explore a range of time and space trade‐offs. Unlike previous algorithms, those discussed here have a constant time cost over a greatly extended range of timestamp values. These algorithms are especially useful in operating systems and in database management systems.
Automating data conversion for heterogeneous distributed shared memory
Authors: Wortman D. B. , Zhou S. , Fink S. 
Published: November 2006

AbstractThis paper describes the issues involved in sharing data among processes executing co‐operatively in a heterogeneous computing environment. In a heterogeneous environment, the physical representation of a data object may need to be transformed when the object is moved from one type of processor to another. As a part of a larger project to build a heterogeneous distributed shared memory system we developed an automated tool for generating the conversion routines that are used to implement representation conversion for data objects. We developed a novel method for processing source programs that allowed us to extract detailed information about the physical representation of data objects without access to the source code of the compilers that were generating those representations. A performance comparison with the more general XDR heterogeneous data conversion package shows that the customized conversion routines that we generate are 4 to 8 times faster.
A prototyping environment for specifying, executing and checking communicating real‐time state machines
Authors: Raju Sitaram C. V. , Shaw Alan C. 
Published: November 2006

AbstractWe describe a toolset, consisting of a graphical editor, a simulator, and an assertion checker, for prototyping real‐time systems that are specified as Communicating Real‐Time State machines (CRSMs). CRSMs are timed state machines that communicate synchronously over unidirectional channels. The system behavior of CRSMs is characterized by a time‐stamped trace of communication events. Safety and timing assertions on the trace of communication events are expressed in a notation based on Real‐Time Logic. We illustrate the simulator and assertion checker by specifying a traffic‐light controller and other real‐time systems. There are two main contributions in this work: first, the prototyping environment serves as a validation of the model, the execution algorithm and paper design of example CRSMs, demonstrating that the ideas are realizable and potentially useful. Secondly, the paper presents a novel and useful method of specifying safety and timing properties, and checking them during simulation.
A method of compressing trie structures
Authors: Morimoto Katsushi , Iriguchi Hirokazu , Aoe Jun‐Ichi 
Published: November 2006

AbstractA trie structure can immediately determine whether a desired key is in a given key set or not, and can find its longest match easily. Thanks to these attractive properties, a trie structure is frequently used for various fields, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie becomes large, so space requirements are not good for a huge key set. To resolve this disadvantage a new structure which reduces the total number of states in a traditional trie, called a double‐trie, is introduced in this paper. Insertion and deletion operations, as well as key retrieval for this double‐trie, are presented. The efficiency of this method is shown by the results of simulations for various key sets.
The lime music editor: A diagram editor involving complex translations
Authors: Blostein D. , Haken L. 
Published: November 2006

AbstractLime is a music editor, oriented to the production of printed music. A user manipulates the information content of the music notation, while viewing the physical appearance of the notation. To implement this, Lime must perform a complex translation from an abstract musical source representation to a graphical product. Techniques are discussed for providing automation without loss of customizability, for implementing WYSIWYG editing, for supporting multiple products (e.g. orchestral score and parts), and for providing good response time despite a slow translator. Similar design issues are encountered by editors for other types of diagrams, such as schematics, chemical formulas, and maps.
A new data structure for cumulative frequency tables
Authors: Fenwick Peter M. 
Published: November 2006

AbstractA new method (the ‘binary indexed tree’) is presented for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions which parallel the binary representation of the index of the table element (or symbol). The operations to traverse the data structure are based on the binary coding of the index. In comparison with previous methods, the binary indexed tree is faster, using more compact data and simpler code. The access time for all operations is either constant or proportional to the logarithm of the table size. In conjunction with the compact data structure, this makes the new method particularly suitable for large symbol alphabets.
Approximate string matching using withinword parallelism
Authors: Wright Alden H. 
Published: November 2006

AbstractGiven a text string, a pattern string, and an integer k, the problem of approximate string matching with k differences is to find all substrings of the text string whose edit distance from the pattern string is less than k. The edit distance between two strings is defined as the minimum number of differences, where a difference can be a substitution, insertion, or deletion of a single character. An implementation of the dynamic programming algorithm for this problem is given that packs several characters and mod‐4 integers into a computer word. Thus, it is a parallelization of the conventional implementation that runs on ordinary processors. Since a small alphabet means that characters have short binary codes, the degree of parallelism is greatest for small alphabets and for processors with long words. For an alphabet of size 8 or smaller and a 64 bit processor, a 21‐fold parallelism over the conventional algorithm can be obtained. Empirical comparisons to the basic dynamic programming algorithm, to a version of Ukkonen's algorithm, to the algorithm of Galil and Park, and to a limited implementation of the Wu‐Manber algorithm are given.
Description of essential system behaviour using message‐state tables
Authors: Paton Keith 
Published: November 2006

AbstractThis paper describes a step‐by‐step method for reaching agreement between the client and the software builder concerning how a system should interact with its user. The method springs from the view of McMenamin and Palmer that all physical systems have both essential behaviour (what is to be done) and physical behaviour (how it is to be done) and that it is useful to define the essential behaviour before discussing how to implement it using real hardware and software. The method leads to an essential system behaviour guide that combines completeness and brevity; it encourages client and builder to share the task of describing essential system behaviour in a language that both can understand. The method is illustrated for the case of a system that manipulates elements and sets.
Remote database access in the distributed computing environment
Authors: And Johnny Wong , Marshall William , Goodman Robert 
Published: November 2006

AbstractThis paper describes the design, implementation and testing of a set of software modules that are used for remote database access in a distributed computing environment.The goal of our research and development is to implement a client server model using Structured Query Language (SQL) functions in the Open Software Foundation's (OSF) distributed computing environment (DCE). This design is compared with another which simply uses the sockets application programming interface (API), running over the transmission control protocol/internet protocol (TCP/IP), and is implemented in subroutines that act similar to the remote procedure call (RPC) generated stub code.The prototypes for the remote SQL access project are implemented using an IBM RISC System/6000 (the client) running the AIX operating system and an IBM AS/400 (the server) running the OS/400 operating system. We selected the AS/400 for its database abilities, and the RISC System/6000 since the DCE software is available for it.
Adding fault‐tolerant transaction processing to LINDA
Authors: Cannon Scott R. , Dunn David 
Published: November 2006

AbstractTo simplify the difficult task of writing fault‐tolerant parallel software, we implemented extensions to the basic functionality of the LINDA or tuple‐space programming model. Our approach implements a mechanism oftransaction processingto ensure that tuples are properly handled in the event of a node or communications failure. If a process retrieving a tuple fails to complete processing or a tuple posting or retrieval message is lost, the system is automatically rolled back to a previous stable state. Processing failures and lost messages are detected by time‐out alarms. Roll‐back is accomplished by reposting pertinent tuples. Intermediate tuples produced during partial processing are not committed or made available until a process completes. In the absence of faults, system overhead is low. The fault‐tolerance mechanism is implemented at the system level and requires little programmer effort or expertise. Two implementations of the model are discussed, one using a UNIX network of workstations and one using a Transputer network. Data measuring model overhead and some aspects of system performance in the presence of faults is presented for an example system.
A simulation testbed based on lightweight processes
Authors: Sang Janche , Chung Ke‐Hsiung , Rego Vernon 
Published: November 2006

AbstractThe Si lightweight‐process based system for simulating process interactions is an enhancement to the C programming languge in the form of library primitives with sets of predefined data structures. The Si system encapsulates an existing lightweight‐process library to provide a discrete‐event simulation environment supporting the process view. It was developed as a research testbed for investigating methods which support simulations efficiently. Easy extensions and modifications to the Si system are a major design objective, accomplished through modularity and layering. This paper describes the system, our experiences with its implementation, and its applicability to simulation modeling. We report on performance measurements of different implementations of the simulation scheduler, and of different algorithms for simulating service disciplines.
A debugger for distributed programs
Authors: Side R. S. , Shoja G. C. 
Published: November 2006

AbstractDeveloping a distributed debugger is much more complex than developing a sequential debugger. This added complexity is mainly due to the non‐determinism of events that communication delays introduce into distributed systems. We explore the problems that one must address when designing a distributed program debugger and then describe our design and implementation of DPD (distributed program debugger). Problems addressed include non‐determinism of events, finding consistent system states, setting breakpoints, recording events, and checkpointing. Important features of DPD include dynamic roll back and replay, as well as a graphical user interface. DPD has been tested successfully in debugging distributed programs within a distributed facility called REM (remote execution manager).
A matrix model for the flow of control in prolog programs with applications to profiling
Authors: Matos Armando B. 
Published: November 2006

AbstractIn Prolog the flow of control is relatively complex; four counts (which we call currents)—call, fail, succeed and redo—and two intrinsic properties—the failure and the ‘alternative’ probabilities—can be associated with every literal in a clause body. In this work we describe a new matrix model where those currents and properties are related at the literal, clause and predicate definition levels. This model is useful for predicate classification, execution profiling and program debugging. The application to profilers is discussed in detail.
Assignment as the sole means of updating objects
Authors: Buhr P. A. , Till David , Zarnke C. R. 
Published: November 2006

AbstractIt is possible, by appropriate programming language extensions, to use the assignment statement as the sole means of changing the value of a variable, thereby eliminating the need to modify routine arguments by output parameters. Several suggestions are made to enhance the syntax and semantics of routine definition and assignment to maintain notational convenience and efficient execution normally associated with output parameters. Finally, an almost complete implementation of the ideas is presented in C.