bluuebunny/crossref_metadata_2025 huggingface dataset:
Software tools for micro‐analysis of programs
Authors: Cohen Jacques , Weitzman Aline
Published: November 2006

The paper proposes and describes several tools enabling their user to estimate the efficiency of Pascal or C‐like programs. The approach consists of generating symbolic formulas expressing the efficiency of the programs being analyzed. The formulas are applicable to a variety of compiler‐machine configurations. The actual numeric values of the variables in the symbolic formula are determined using linear programming techniques. The proposed approach reduces considerably the amount of benchmarking needed to analyze programs. Several examples are presented showing the applicability of the tools. The effort necessary to implement them is considerably reduced by the combined usage of Prolog and a symbolic formula manipulation package (Maple).
cxterm: A Chinese terminal emulator for the X window system
Authors: Pong Man‐Chi , Zhang Yongguang
Published: November 2006

Computing involving data in a logo‐syllabic oriental language like Chinese is more difficult than in English. Many attempts have been made to develop bilingual or multilingual processing systems.1–3 Most of them are based on microcomputers like the IBM‐PC. With the widespread use of workstations and window systems, much better multi‐lingual processing environments can be provided.

This paper describes the design and implementation of the program cxterm, a Chinese terminal emulator for the X Window System. We discuss the representation of multi‐byte international characters, the problems of Chinese character input and output, the pros and cons of various approaches, and the design decisions for cxterm. A feature of cxterm is its independence of input methods. A user can incorporate new input methods into cxterm at run‐time, without changing the program code. We also compare our approach with related work in multi‐lingual input/output in X, and describe how cxterm performs better in terms of efficiency, flexibility, and user‐friendliness.
Monitoring and debugging distributed realtime programs
Authors: Dodd Paul S. , Ravishankar Chinya V.
Published: November 2006

In this paper we describe the design and implementation of an integrated monitoring and debugging system for a distributed real‐time computer system. The monitor provides continuous, transparent monitoring capabilities throughout a real‐time system's lifecycle with bounded, minimal, predictable interference by using software support. The monitor is flexible enough to observe both high‐level events that are operating system‐ and application‐specific, as well as low‐level events such as shared variable references. We present a novel approach to monitoring shared variable references that provides transparent monitoring with low overhead. The monitor is designed to support tasks such as debugging realtime applications, aiding real‐time task scheduling, and measuring system performance. Since debugging distributed real‐time applications is particularly difficult, we describe how the monitor can be used to debug distributed and parallel applications by deterministic execution replay.
Tuning the boyer‐moore‐horspool string searching algorithm
Authors: Raita Timo
Published: November 2006

Substring search is a common activity in computing. The fastest known search method is that of Boyer and Moore with the improvements introduced by Horspool. This paper presents a new implementation which takes advantage of the dependencies between the characters. The resulting code runs 25 per cent faster than the best currently‐known routine.
Tm: A code generator for recursive data structures
Authors: van Reeuwijk C.
Published: November 2006

The transfer of data structures between programs is often carried out using binary or ad‐hoc textual formats. However, this can result in ambiguous and non‐portable file formats. The program ‘Tm’ (for ‘template manager’) prevents these problems by using a textual representation of the data structures and generating the code to read and write this representation from an abstract definition of the data structures. The same program is used to generate code for the simple data‐structure manipulations that are necessary in almost every program. At the moment, code can be generated for the programming languages C, Pascal, Lisp and Miranda. Support for other languages is easily added.
CCIGS: A data compression system for Chinese fonts and binary images using classification techniques
Authors: Chang Kuang‐Yao , Tang Gregory Y.
Published: November 2006

To achieve a high compression ratio when storing a large amount of Chinese characters is a problem in applications using Chinese characters. In this paper, we present a data compression software system which can reduce the storage requirement of Chinese characters and binary images. This system is composed of a Chinese font compressing subsystem and a binary image compressing subsystem. In the Chinese font compressing subsystem we have improved the traditional methods of feature extraction and classification techniques so as to achieve a high compression ratio in the compression of Chinese characters. Based on the technique of this subsystem, we have combined the block segmentation technique to compress a binary image. In addition to achieving a good data compression ratio the encoding‐decoding process is computationally very efficient in our system. We also show that with our system the quality and accuracy of the reconstructed pattern and image are very close to those of the original pattern and image.
Reusability through fine‐grain inheritance
Authors: Johnson Paul , Rees Ceri
Published: November 2006

Object‐oriented languages are often promoted as encouraging the production of flexible, reusable software. Unfortunately, experience suggests that although individual classes may be reusable, large class libraries seem to lack flexibility in the face of circumstances unforeseen by the designer.

This paper explores the problems associated with flexibility and reuse in large libraries, and shows how fine‐grain inheritance can alleviate some of these problems. A methodology for designing fine‐grain inheritance graphs is proposed and a detailed case study is presented.
An exercise in formalizing the description of a concurrent system
Authors: Bustard D. W. , Norris M. T. , Orr R. A. , Winstanley A. C.
Published: November 2006

LOTOS is one of the most recent formal description languages to appear and one of very few with a standard definition. It has both a process algebra and an abstract data‐type component, and these facilities are used in combination to describe the behaviour of concurrent systems. The purpose of this paper is to examine, in a tutorial style, what is involved in constructing and taking benefit from such descriptions. The presentation is illustrated through the development of two formal descriptions for the children's game of pass‐the‐parcel. These descriptions and a concise summary of the main features of LOTOS are given as appendices. Many of the points made in the paper apply equally well to other process‐oriented languages such as CCS and CSP.
Rapid prototyping of protocols from LOTOS specifications
Authors: Valenzano A. , Sisto R. , Ciminiera L.
Published: November 2006

A new tool for generating implementation prototypes of communication protocols and concurrent systems specified using the ISO LOTOS language is presented in this paper. A brief introduction to LOTOS and a discussion of the main problems related to the efficient execution of specifications written in LOTOS are presented first. The design and implementation of the tool are then considered: LOTOS specifications are analysed and translated into C functions which are executed by co‐operating processes in the Unix environment. The set of LOTOS process definitions is first translated into a suitable number of extended finite‐state machines (EFSMs). The method proposed allows the problem of deriving unbounded EFSMs to be circumvented and a sort of control on the process number/size trade‐off to be obtained at the same time.

The problem of implementing the LOTOS multi‐way rendezvous mechanism for process synchronization is solved by using an algorithm based on message‐passing techniques. An example of prototype derivation is also described, showing the form of C code generated by translating a simple specification. Finally, some performance figures are presented.
PDB: A pictorial database oriented to data analysis
Authors: Maccarone Maria Concetta , Tripiciano Mario , Gesù Vito Di , Tegolo Domenico
Published: November 2006

The paper describes a new pictorial database oriented to image analysis, implemented inside the MIDAS data analysis system. Pictorial databases need expressive data structures in order to represent a wide class of information from the numerical to the visual. The model of the database is relational; however, a full normalization is not achievable, owing to the complexity of the visual information. The paper reports the general design and notes on the software implementation. Preliminary experiments show the performance of the pictorial database.
A first exploration of PrologIII's capabilities
Authors: Rueher Michel
Published: November 2006

This paper explores PrologIII's capabilities through the study of two short but non‐trivial applications that are chosen to show the advantages of constraint logic programming languages over conventional Prologs, especially for tackling combinatorial problems.

The first application (manipulation of causal graphs) highlights the expressive power of the constraints on booleans and shows that constraint logic programming techniques provide great flexibility for the exploration of the domain of an application, and therefore significantly improve Prolog's prototyping capabilities.

The second application (map colouring) demonstrates that a combined use of numerical constraints and constraints on trees of PrologIII enables one to improve solutions based on standard backtracking, through the use of simple heuristics. Such heuristics allow drastic reduction of the search space and yield good performance even for quite complex problems. The adaptability of the approach to other combinatorial problems is shown on several examples.
The peregrine high‐performance RPC system
Authors: Johnson David B. , Zwaenepoel Willy
Published: November 2006

The Peregrine RPC system provides performance very close to the optimum allowed by the hardware limits, while still supporting the complete RPC model. Implemented on an Ethernet network of Sun‐3/60 workstations, a null RPC between two user‐level threads executing on separate machines requires 573μs. This time compares well with the fastest network RPC times reported in the literature, ranging from about 1100 to 2600 μs, and is only 309 μs above the measured hardware latency for transmitting the call and result packets in our environment. For large multi‐packet RPC calls, the Peregrine user‐level data transfer rate reaches 8.9 Mbit/s, approaching the Ethernet's 10 Mbit/s network transmission rate. Between two user‐level threads on the same machine, a null RPC requires 149 μs. This paper identifies some of the key performance optimizations used in Peregrine, and quantitatively assesses their benefits.
Application integration: Constructing composite applications from interactive components
Authors: Cowan D. D. , Stepien T. M. , Ierusalimschy R. , Lucena C. J. P.
Published: November 2006

Creating new applications by integrating user interface and application components is a relatively new idea which is currently of wide interest. A significant part of this problem is clearly defining the separation between user interface and application components. This paper proposes a new design methodology based on the concept of an abstract data view (ADV), a structuring method which cleanly defines this separation. A number of examples of composite interactive documents, ones which could contain several different user interfaces with entities such as text, calculations, drawings and possibly even multi‐media presentations, illustrate the ADV concept. These examples lead naturally to the introduction of the concept ofhole, a user interface area in a composite interactive document which is managed by an external program, and uses ADVs. Prototypes of a number of systems supporting ADVs and holes are currently running in our laboratory.
CIRL/PIWI: A GUI toolkit supporting retargetability
Authors: Cowan D. D. , Durance C. M. , Giguère E. , Pianosi G. M.
Published: November 2006

Writing applications that are easily moved to various computer platforms with different graphical user interfaces (GUIs) is a complex task. Yet this concept is important for the creator of commercial software, as it is not likely to be clear for many years whether one or two GUIs will survive and become industry ‘standards’ or whether the growth in GUIs will continue because of new developments in human‐computer interfaces. Providing a user interface abstraction that maps into all toolkits seems to be an appropriate way to proceed, but is fraught with difficulty. For example, different GUIs present a different look‐and‐feel that often causes system‐specific information to be embedded in an application. This paper surveys the problems inherent in designing a user interface abstraction, and describes the experiences gained from a specific implementation called CIRL/PIWI.

CIRL and PIWI are acronyms for Co‐ordinate‐Independent Resource Language and Presentation‐Independent Windowed Interface.

The user interface abstraction contains a knowledge base that allows many components of the user interface to be defined independent of look‐and‐feel thereby increasing the portability of an application.
Multi‐way versus one‐way constraints in user interfaces: Experience with the deltablue algorithm
Authors: Sannella Michael , Maloney John , Freeman‐Benson Bjorn , Borning Alan
Published: November 2006

The efficient satisfaction of constraints is essential to the performance of constraint‐based user interfaces. In the past, most constraint‐based user interfaces have used one‐way rather than multi‐way constraints because of a widespread belief that one‐way constraints were more efficient. In this paper we argue that many user interface construction problems are handled more naturally and elegantly by multi‐way constraints than by one‐way constraints. We present pseudocode for an incremental multi‐way constraint satisfaction algorithm, DeltaBlue, and describe experience in using the algorithm in two user interface toolkits. Finally, we provide performance figures demonstrating that multi‐way constraint solvers can be entirely competitive in performance with one‐way constraint solvers.
Extensions to the C programming language for enhanced fault detection
Authors: Plater David W. , Yesha Yelena , Park E. K.
Published: November 2006

The acceptance of the C programming language by academia and industry is partially responsible for the ‘software crisis’. The simple, trusting semantics of C mask many common faults, such as range violations, which would be detected and reported at run‐time by programs coded in a robust language such as Ada.

Ada is a registered trademark of the U.S. Government (Ada Joint Program Office)

This needlessly complicates the debugging of C programs. Although the assert macro lets programmers add run‐time consistency checks to their programs, the number of instantiations of this macro needed to make a C program robust makes it highly unlikely that any programmer could correctly perform the task. We make some unobtrusive extensions to the C language which support the efficient detection of faults at run‐time without reducing the readability of the source code. Examples of the extensions are automatic checking of error codes returned by library routines, constrained subtypes and detection of references to uninitialized and/or non‐existent array elements.
Executable specifications with data‐flow diagrams
Authors: Fuggetta Alfonso , Ghezzi Carlo , Mandrioli Dino , Morzenti Angelo
Published: November 2006

Specifications of information systems applications are often based on the use of entity‐relationship (ER) and data‐flow diagrams (DFD), which cover, respectively, the conceptual modelling of data and funtions. This paper introduces VLP: an executable visual language for formal specifications and prototyping which integrates ER and DFD diagrams in a semantically rigorous and clear way. Unlike existing commercial products (so‐called CASE tools), which can support good‐quality documentation, simple forms of consistency checking and bookkeeping, VLP also supports executable specifications, which provide a prototype of the desired application. After reviewing the principles of VLP, the paper outlines the structure of the ECASET environment in which VLP is embedded. In particular, it shows how the environment supports the stepwise derivation of specifications, from informal to formal, and how it supports specification‐in‐the‐large.
Standardized protocol interfaces
Authors: Holzmann Gerard J.
Published: November 2006

A traditional protocol implementation typically consists of at least two distinct parts, a sender and a receiver. Each part runs on a distinct machine, with the implementation provided by a local expert. At best, the two machines are of the same type and the protocol implementations are provided by the same person. More likely, however, the machines are not of the same type and the implementations of the two halves of the protocol are provided by two different people, working from an often loosely defined protocol specification. It seems almost unavoidable that the two implementations are not quite compatible.

In this paper we consider an alternative technique. With this method, one of the two implementors can design, formally validate, and implement all the relevant protocol parts, including those parts that are to be executed remotely. Each communication channel is now terminated on the receiving side, by a single standard protocol interface, which can be called a universal asynchronous protocol interface, or UAPI.

Though it is likely that the UAPI is most efficiently implemented in hardware, it can also trivially run as a software module, e.g. under a standard UNIX® operating system (in our case under 10th Edition Research Unix). This paper introduces the concept of a UAPI and explains how the sample software controller was constructed.
The measured cost of conservative garbage collection
Authors: Zorn Benjamin
Published: November 2006

Because dynamic memory management is an important part of a large class of computer programs, high‐performance algorithms for dynamic memory management have been, and will continue to be, of considerable interest. Experience indicates that for many programs, dynamic storage allocation is so important that programmers feel compelled to write and use their own domain‐specific allocators to avoid the overhead of system libraries. As an alternative to explicit storage management techniques, conservative garbage collection has been suggested as an important algorithm for dynamic storage management in C programs. In this paper, I evaluate the costs of different dynamic storage management algorithms, including domain‐specific allocators, widely‐used general‐purpose allocators, and a publicly available conservative garbage collection algorithm. Surprisingly, I find that programmer enhancements often have little effect on program performance. I also find that the true cost of conservative garbage collection is not the CPU overhead, but the memory system overhead of the algorithm. I conclude that conservative garbage collection is a promising alternative to explicit storage management and that the performance of conservative collection is likely to improve in the future. C programmers should now seriously consider using conservative garbage collection instead of explicitly calling free in programs they write.
Vartalaap: A distributed multicast communication system
Authors: Lashkari Yezdezard , Ramachandran Viswanath , Malpani Sanjay , Mehndiratta S. L.
Published: November 2006

With the increasing proliferation of computer networks and distributed systems, there is a growing number of applications using multicast communication. This paper presents the Vartalaap system developed at IIT, Bombay. Vartalaap is an hierarchical distributed system for multicast communication over a network, implemented in a hardware‐independent fashion. The multicast is achieved without resorting to unnecessary broadcasting of messages over the network. Issues covered in this paper include the primitives for multicast, the multicast model and the system architecture. We discuss the implementation of Vartalaap and compare it with some other systems. We conclude with a discussion on the limitations of the current implementation and directions for future work.
Parsing Non‐LR(k) grammars with yacc
Authors: Merrill Gary H.
Published: November 2006

Of the parser generating tools currently in use, yacc (or one of its several variants) is perhaps the most frequently employed. However, because of inherent ambiguities there are some languages (such as C++) that a yacc‐generated parser cannot successfully compile. This paper describes a set of minor modifications to yacc‐like tools that allows them to be used in a straightforward way to parse ambiguities and, more generally, grammars that require an indefinite amount of lookahead. Required changes to the lexical analyzer are also discussed, and the application of these techniques is illustrated within the context of specific examples.
Customalloc: Efficient synthesized memory allocators
Authors: Grunwald Dirk , Zorn Benjamin
Published: November 2006

The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. Yet, in some applications, programmers use domain‐specific knowledge in an attempt to improve the speed or memory utilization of memory allocators.

In this paper, we describe a program (CustoMalloc) that synthesizes a memory allocator customized for a specific application. Our experiments show that the synthesized allocators are uniformly faster and more space efficient than the Berkeley UNIX allocator. Constructing a custom allocator requires little programmer effort, usually taking only a few minutes. Experience has shown that the synthesized allocators are not overly sensitive to properties of input sets and the resulting allocators are superior even to domain‐specific allocators designed by programmers. Measurements show that synthesized allocators are from two to ten times faster than widely‐used allocators.
Differential evaluation: A cache‐based technique for incremental update of graphical displays of structures
Authors: Dunlavey Michael R.
Published: November 2006

Many 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

The 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

We 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

C++ 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

Janus 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

The 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

Several 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

The 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

Most 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

Experimental 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

In 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

This 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

We 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.
Correction to ‘producing good code for the case statement’
Authors: Kannan Sampath , Proebsting Todd A.
Published: November 2006

An O(n2) algorithm for splitting a case statement's jump table into the minimum number of subtables (of a given density) is presented. Previously, the problem was thought to be NP‐complete.
A method of compressing trie structures
Authors: Morimoto Katsushi , Iriguchi Hirokazu , Aoe Jun‐Ichi
Published: November 2006

A 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

Lime 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

A 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

Given 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

This 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

This 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

To 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

The 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

Developing 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

In 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

It 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.
Mirage+: A kernel implementation of distributed shared memory on a network of personal computers
Authors: Fleisch Brett D. , Hyde Randall L. , Juul Niels Christian
Published: November 2006

We describe the evolution of a distributed shared memory (DSM) system, Mirage, and the difficulties encountered when moving the system from a Unix‐based* kernel on the VAX to a Unix‐based kernel on personal computers. Mirage provides a network transparent form of shared memory for a loosely coupled environment. The system hides network boundaries for processes that are accessing shared memory and is upward compatible with the Unix System V Interface Definition.

This paper addresses the architectural dependencies in the design of the system and evaluates performance of the implementation. The new version, MIRAGE+, performs well compared to Mirage even though eight times the amount of data is sent on each page fault because of the larger page size used in the implementation. We show that performance of systems with a large page size to network packet size can be dramatically improved on conventional hardware by applying three well‐known techniques: packet blasting, compression, and running at interrupt level.

The measured time for a page fault in MIRAGE+ has been reduced 37 per cent by sending a page using packet blasting instead of using a handshake for each portion of the page. When compression was added to MIRAGE+, the time to fault a page across the network was further improved by 47 per cent when the page was compressed into one network packet. Our measured performance compares favorably with the amount of time it takes to fault a page from disk. Lastly, running at interrupt level may improve performance 16 per cent when faulting pages without compression.