bluuebunny/crossref_metadata_2025_split huggingface dataset:
A streams‐based communications subsystem in turing plus for protocol development
Authors: Atwood J. William , Prager Walter 
Published: November 2006

AbstractThe Homogeneous Multiprocessor (HM) has a linear‐array topology, with interprocessor communications achieved by the sharing of memory between nearest neighbours, by adjacent‐processor signalling, and through a high‐speed network (the H‐Network). The operating system nucleus (the HM‐Nucleus) for the HM contains a communications subsystem that provides low‐overhead communications, both for user processes and for the rest of the HM‐Nucleus, using the shared memory, the signalling capability, and the H‐Network.The design for the communications subsystem provides uniformity of access to the three mechanisms by following the IEEE 802.2/802.3 LLC/MAC specifications. Flexibility of access is achieved by adopting the STREAMS facility from System V UNIX.A new implementation of STREAMS has been built using Turing Plus for both the programming and the simulation/testing, with no need to access the actual hardware until final test. Completion of the STREAMS framework has made it possible subsequently to code an 802.2 LLC module and an 802.3‐based shared memory driver very quickly.The STREAMS framework has also made it feasible to cast some algorithms used by other parts of the HM‐Nucleus as protocols, and implement them as STREAMS modules, resulting in considerable simplification in the design process. Since the framework was designed to be completely independent of the host processor, it provides a very general vehicle for protocol development.
Specification and quality assurance of timing constraints in real‐time systems development
Authors: Lien Chih‐Cheng , Yang Chien‐Chiao 
Published: November 2006

AbstractA representation for specifying the timing constraints of real‐time systems is presented. Four parts of descriptions in a timing constraint: the path of events, timer, types of constraints and quantities of time, are explained. Under the relations among the paths, the hierarchical and network structures can be conducted. The former can be associated with the structure resulting from applying top‐down decomposition in software development. The latter represents the execution dependence of the paths. Based upon these clear and manageable structures, the completeness and consistency of timing constraints specification can be rigorously analysed. Thus, the quality of the specification of timing constraints can be improved during software development. A frame‐like software requirements specification language (FSRSL) is extended to specify timing constraints and the related descriptions in the paper.
A comparison of two paradigms for distributed shared memory
Authors: Levelt Willem G. , Kaashoek M. Frans , Bal Henri E. , Tanenbaum Andrew S. 
Published: November 2006

AbstractTwo paradigms for distributed shared memory on loosely‐coupled computing systems are compared: the shared data‐object model as used in Orca, a programming language specially designed for loosely‐coupled computing systems, and the shared virtual memory model. For both paradigms two systems are described, one using only point‐to‐point messages, the other using broadcasting as well.The two paradigms and their implementations are described briefly. Their performances are compared on four applications: the travelling‐salesman problem, alpha‐beta search, matrix multiplication and the all‐pairs shortest‐paths problem. Measurements were obtained on a system consisting of 10 MC68020 processors connected by an Ethernet. For comparison purposes, the applications have also been run on a system with physical shared memory. In addition, the paper gives measurements for the first two applications above when remote procedure call is used as the communication mechanism.The measurements show that both paradigms can be used efficiently for programming large‐grain parallel applications, with significant speed‐ups. The structured shared data‐object model achieves the highest speed‐ups and is easiest to program and to debug.
ALADIN: A scanner generator for incremental programming environments
Authors: Fischer Bernd , Hammer Carsten , Struckmann Werner 
Published: November 2006

AbstractA large number of scanner generators have been developed. Since they are restricted to the longest‐match rule, they are unsuitable for an incremental environment. We present the ALADIN system, which is able to deliver more than a single token if required. Thus, an ambiguity may be passed to the calling instance. Beyond this ‘incremental feature’, ALADIN is a well‐structured and easy‐to‐understand language. In contrast to existing systems, the desired behaviour of the generated scanners is completely specified explicitly. Thus, the specifications are more abstract than in other systems. A prototype implementation has shown that ALADIN‐generated scanners have about the same performance as those generated by Lex.
Generic abstract interpretation algorithms for Prolog: Two optimization techniques and their experimental evaluation
Authors: Englebert Vincent , Charlier Baudouin Le , Roland Didier , Van Hentenryck Pascal 
Published: November 2006

AbstractThe efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after References 1 and 2. Two new optimization techniques are proposed and applied to the original algorithm of Reference 1: dependency on clause prefixes and caching of operations. The first improvement avoids re‐evaluating a clause prefix when no abstract value which it depends on has been updated. The second improvement consists of caching all operations on substitutions and reusing the results whenever possible. The algorithm and the two optimization techniques have been implemented in C (about 8000 lines of code each), tested on a large number of Prolog programs, and compared with the original implementation on an abstract domain containing modes, types and sharing. In conjunction with refinements of the domain algorithms, they produce an average reduction of more than 58 per cent is computation time. Extensive experimental results on the programs are given, including computation times, memory consumption, hit ratios for the caches, the number of operations performed, and the time distribution. As a main result, the improved algorithms exhibit the same efficiency as the specific tools of References 3 and 4, despite the fact that our abstract domain is more sophisticated and accurate. The abstract operations also take 90 per cent of the computation time, indicating that the overhead of the control is very limited. Results on a simpler domain are also given and show that even extremely basic domains can benefit from the optimizations. The general‐purpose character of the optimizations is also discussed.
A unix tool for managing reusable software components
Authors: Plaice John , Wadge William W. 
Published: November 2006

AbstractSloth is a simple Unix‐based tool for creating and maintaining large C programs built from reusable ‘modules’. Sloth is a collection of UNIX shell commands for creating and editing modules, and for producing executables by linking compiled code from the modules comprising a program. Sloth in a sense extends C by providing module facilities similar to those built in to newer languages such as Modula‐II. The Sloth ‘extensions’, however, are at the shell level only. No changes are required in C itself; in fact, the Sloth commands invoke the standard Unix C compiler.A Sloth module contains a set of C procedures and local declarations, a set of global definitions and variable declarations, an initialization routine and an ‘import’ list of other modules containing declarations referred to, but not defined by, the module in question. The Sloth link command has one argument, the name of a ‘root’ directory. The link command automatically identifies all those modules imported directly or indirectly by the root module, checks that the object code for each module is up‐to‐date and recompiles where necessary. It then creates a main program in which the various initialization routines are executed in the correct order (most primitive first), compiles it and links it with all the object files and produces an executable program.Individual modules can be compiled without any knowledge of the application that uses, directly or indirectly, the module in question. Two applications that both use a collection of modules can therefore share the object code for these modules.The use and implementation of Sloth are presented, as are the experience in using it, programming techniques developed to take full advantage of its facilities, as well as several extensions, either completed or planned.
On‐line software version change using state transfer between processes
Authors: Gupta Deepak , Jalote Pankaj 
Published: November 2006

AbstractThe usual way of installing a new version of a piece of software is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An on‐line software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. In this paper, we describe a system for on‐line software version change for software written in the C language. When the change is initiated by the user, the system instantiates a new process with the new version of the software, transfers state from the old process to the new one at an appropriate time, and transfers the control to the new process. The user sees a minimal delay in this switchover.
Reverse reachability analysis: A new technique for deadlock detection on communicating finite state machines
Authors: Hung Yung‐Chen , Chen Gen‐Huey 
Published: November 2006

AbstractThe communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock‐free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.
Implementing a graphical multi‐user interface toolkit
Authors: Kohlert Doug , Rodham Ken , Olsen Dan 
Published: November 2006

AbstractMulti‐user applications allows users in different locations to simultaneously interact with a common interface. Creating multi‐user applications is complicated by issues such as process synchronization, replicated window management, and floor control. As a result, several papers describing toolkits that simplify programming of multi‐user applications have appeared in the literature. This paper discusses several low‐level issues that must be addressed when implementing such a toolkit. Issues relating to replicated window management, supporting heterogeneous hardware environments, and multi‐user event handling are discussed.
The design and implementation of the lout document formatting language
Authors: Kingston Jeffrey H. 
Published: November 2006

AbstractLout is a high‐level language for document formatting, whose ease of use has permitted an unprecedented number of advanced features to be added quickly and reliably. This paper charts the evolution of the design and implementation of Lout from conception in mid‐1984 to public release in October 1991. It includes extensive discussions of remaining problems and possible solutions.
Backtalk: A generalized dynamic communication system for DAI
Authors: Sayre Kirk , Gray Michael A. 
Published: November 2006

AbstractIn order to expand the domain of problems addressable by expert systems, co‐operation is required. To enable this co‐operation, a free exchange of ‘thoughts’ between individual expert systems must be provided. A transparent, modularized communication system, called Backtalk, consisting of a router process and an incoming and outgoing message process pair associated with each expert system has been developed. All messages are sent to the router, which is responsible for determining the exact address of the destination agent and passing the message to the agent. The system uses Unix pipes to pass information between different agents, thereby providing generality in the system. The Backtalk system is similar to the communication system put forth by Bridgeland, Huhns and Arni, but has advantages in dynamic systems. This paper also describes a solution to the issue of defining when messages are allowed to affect the problem‐solving activity of a receiving agent. The system has been tested with communicating expert systems written in the Accord system.
Experience with modularity in consul
Authors: Mishra Shivakant , Peterson Larry L. , Schlichting Richard D. 
Published: November 2006

AbstractThe use of modularity in the design and implementation of complex software simplifies the development process, as well as facilitating the construction of customized configurations. This paper describes our experience using modularity in Consul, a communication substrate used for constructing fault‐tolerant distributed programs. First, Consul is presented as a case study of how modularity is feasible in both the design and the implementation of such systems. Secondly, general lessons about modularity in fault‐tolerant systems based on our experience with Consul are given. Issues that are addressed include deciding how the system is divided into various modules, dealing with problems that result when protocols are combined, and ensuring that the underlying object infrastructure provides adequate support. The key observation is that the modularization process is most affected by dependencies between modules, both direct dependencies caused by one module explicitly using another's operation and indirect dependencies where one module is affected by another without direct interaction. Although our observations are based on designing and implementing Consul, the lessons are applicable to any fault‐tolerant distributed system.
A generational and conservative copying collector for hybrid object‐oriented languages
Authors: Onodera Tamiya 
Published: November 2006

AbstractA copying collector has two excellent properties: it compacts the heap, and the execution time depends solely on the number of live objects. Use of a copying collector is thought by some to be a more efficient way of managing the heap than explicit freeing of objects. This paper describes a high‐performance copying collector for a hybrid object‐oriented language. The collector is both conservative and generational. It relies on the overlying compiler to identify most true pointers, and on the underlying operating system to detect pointers to younger generations. The implementation described here uses a modified version of the compiler for a C‐based object‐oriented language, and the Mach operating system. The performance results have confirmed the author's expectation: the collector has been faster than explicit freeing.
An application of causal analysis to the software modification process
Authors: Collofello James S. , Gosalia Bakul P. 
Published: November 2006

AbstractThe development of high quality large‐scale software systems within schedule and budget constraints is a formidable software engineering challenge. The modification of these systems to incorporate new and changing capabilities poses an even greater challenge. This modification activity must be performed without adversely affecting the quality of the existing system. Unfortunately, this objective is rarely met. Software modifications often introduce undesirable side‐effects, leading to reduced quality.In this paper, the software modification process for a large, evolving real‐time system is analysed using causal analysis. Causal analysis is a process for achieving quality improvements via fault prevention. The fault prevention stems from a careful analysis of faults in search of their causes. This paper reports our use of causal analysis on several significant modification activities resulting in about two hundred defects. Recommendations for improved software modification and quality assurance processes based on our findings are also presented.
Static analysis of exception handling in Ada
Authors: Schaefer Carl F. , Bundy Gary N. 
Published: November 2006

AbstractSince the signature of an Ada subprogram does not specify the set of exceptions that the subprogram can propagate, computing the set of exceptions that a subprogram may encounter is not a trivial task. This is a source of error in large Ada systems: for example, a subprogram may not be prepared to handle an exception propagated from another subprogram several layers lower in the call‐tree. In a large system, the number of paths in exceptional processing is so great that it is unlikely that testing will uncover all errors in inter‐procedural exception handling. Nor are compilers or code inspections likely to locate all such errors. Exception handling is an area where static analysis has a high potential payoff for systems with high reliability requirements. We discuss fundamental notions in computing exception propagation and describe an analysis tool that has proved to be effective in detecting inconsistencies in the exception‐handling code of Ada applications.
Memory allocation costs in large C and C++ programs
Authors: Detlefs David , Dosser Al , Zorn Benjamin 
Published: November 2006

AbstractDynamic storage allocation is an important part of a large class of computer programs written in C and C + +. High‐performance algorithms for dynamic storage allocation have been, and will continue to be, of considerable interest. This paper presents detailed measurements of the cost of dynamic storage allocation in 11 diverse C and C + + programs using five very different dynamic storage allocation implementations, including a conservative garbage collection algorithm. Four of the allocator implementations measured are publicly available on the Internet. A number of the programs used in these measurements are also available on the Internet to facilitate further research in dynamic storage allocation. Finally, the data presented in this paper is an abbreviated version of more extensive statistics that are also publicly available on the Internet.
STRESS: A simulator for hard real‐time systems
Authors: Audsley N. C. , Burns A. , Richardson M. F. , Wellings A. J. 
Published: November 2006

AbstractThe STRESS environment is a collection of CASE tools for analysing and simulating the behaviour of hard real‐time safety‐critical applications. It is primarily intended as a means by which various scheduling and resource management algorithms can be evaluated, but can also be used to study the general behaviour of applications and real‐time kernels. This paper describes the structure of the STRESS language and its environment, and gives examples of its use.
Algorithm‐oriented generic libraries
Authors: Musser David R. , Stepanov Alexander A. 
Published: November 2006

AbstractWe outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the object‐oriented programming paradigm. Our approach is to consider algorithms first, decide what types and access operations they need for efficient execution, and regard the types and operations as formal parameters that can be instantiated in many different ways, as long as the actual parameters satisfy the assumptions on which the correctness and efficiency of the algorithms are based. The means by which instantiation is carried out is language dependent; in the C + + examples in this paper, we instantiate generic algorithms by constructing classes that define the needed types and access operations. By use of such compile‐time techniques and careful attention to algorithmic issues, it is possible to construct software components of broad utility with no sacrifice of efficiency.
Multistage indexing algorithms for speeding prolog execution
Authors: And Ta Chen , Ramakrishnan I. V. , Ramesh R. 
Published: November 2006

AbstractIn a previous article we proposed a new and efficient indexing technique that utilizes all the functors in the clause‐heads and the goal. The salient feature of this technique is that the selected clause‐head unifies (modulo nonlinearity) with the goal. As a consequence, our technique results in sharper discrimination, fewer choice points and reduced backtracking.A naïve and direct implementation of our indexing algorithms considerably slowed down the execution speeds of a wide range of programs typically seen in practice. This is because it handled deep and shallow terms, terms with few indexable arguments, small and large procedures uniformly. To beneficially extend the applicability of our algorithms we need mechanisms that are ‘sensitive’ to term structures and size and complexity of procedures. We accomplish this in the v‐ALS compiler by carefully decomposing our indexing process into multiple stages. The operations performed by these stages increase in complexity ranging from first argument indexing to unification (modulo nonlinearity). Further the indexing process can be terminated at any stage if it is not beneficial to continue further.We have now completed the design and implementation of v‐ALS. Using it we have enhanced the performance of a broad range of programs typically encountered in practice. Our experience strongly suggests that indexing based on unification (modulo nonlinearity) is a viable idea in practice and that a broad spectrum of useful programs can realize all of its benefits.
Incremental compiler transformations for multiple instruction retry
Authors: Chen Shyh‐Kwei , Alewine Neal J. , Fuchs W. Kent , Hwu Wen‐Mei W. 
Published: November 2006

AbstractPrevious work on compiler‐based multiple instruction retry has utilized a series of compiler transformations, loop protection, node splitting, and loop expansion, to eliminate anti‐dependencies of length ≤Nin the pseudo register, the machine register, and the post‐pass resolver phases of compilation.1The results have provided a means of rapidly recovering from transient processor failures by rolling backNinstructions. This paper presents techniques for improving compilation and run‐time performance in compiler‐based multiple instruction retry. Incremental updating enhances compilation time when new instructions are added to the program. Post‐pass code rescheduling and spill register reassignment algorithms improve the run‐time performance and decrease the code growth across the application programs studied. Branch hazards are shown to be resolvable by simple modifications to the incremental updating schemes during the pseudo register phase and to the spill register reassignment algorithm during the post‐pass phase.
Coupling hundreds of workstations for parallel molecular sequence analysis
Authors: Strumpen Volker 
Published: November 2006

AbstractWe present a highly scalable approach to distributed parallel computing on workstations in the Internet which provides significant speed‐up to molecular biology sequence analysis. Recent developments show that smaller numbers of workstations connected via a local area network can be used efficiently for parallel computing. This work emphasizes scalability with respect to the number of workstations employed. We show that a massively parallel approach using several hundred workstations, dispersed over all continents, can successfully be applied for solving problems with low requirements on communication bandwidth. We calculated the optimal local alignment scores between a single genetic sequence and all sequences of a genetic sequence database using the ssearch code that is well known among molecular biologists. In a heterogeneous network with more than 800 workstations this job terminated after several minutes, in contrast to several days it would have taken on a single machine.